• Ganesh Ajjanagadde's avatar
    avcodec/huffman: replace qsort with AV_QSORT · 9bc3d335
    Ganesh Ajjanagadde authored
    ff_huff_build_tree uses qsort underneath. AV_QSORT is substantially
    faster due to the inlining of the comparison callback. Furthermore, this
    code is reasonably performance critical, since in e.g the fraps codec,
    ff_huff_build_tree is called on every frame. This routine is also called
    in vp6 on every frame in some circumstances.
    
    Sample benchmark (x86-64, Haswell, GNU/Linux), vp6 from FATE:
    vp6 (old):
      78930 decicycles in qsort,       1 runs,      0 skips
      45330 decicycles in qsort,       2 runs,      0 skips
      27825 decicycles in qsort,       4 runs,      0 skips
      17471 decicycles in qsort,       8 runs,      0 skips
      12296 decicycles in qsort,      16 runs,      0 skips
       9554 decicycles in qsort,      32 runs,      0 skips
       8404 decicycles in qsort,      64 runs,      0 skips
       7405 decicycles in qsort,     128 runs,      0 skips
       6740 decicycles in qsort,     256 runs,      0 skips
       7540 decicycles in qsort,     512 runs,      0 skips
       9498 decicycles in qsort,    1024 runs,      0 skips
       9938 decicycles in qsort,    2048 runs,      0 skips
       8043 decicycles in qsort,    4095 runs,      1 skips
    
    vp6 (new):
      15880 decicycles in qsort,       1 runs,      0 skips
      10730 decicycles in qsort,       2 runs,      0 skips
      10155 decicycles in qsort,       4 runs,      0 skips
       7805 decicycles in qsort,       8 runs,      0 skips
       6883 decicycles in qsort,      16 runs,      0 skips
       6305 decicycles in qsort,      32 runs,      0 skips
       5854 decicycles in qsort,      64 runs,      0 skips
       5152 decicycles in qsort,     128 runs,      0 skips
       4452 decicycles in qsort,     256 runs,      0 skips
       4161 decicycles in qsort,     511 runs,      1 skips
       4081 decicycles in qsort,    1023 runs,      1 skips
       4072 decicycles in qsort,    2047 runs,      1 skips
       4004 decicycles in qsort,    4095 runs,      1 skips
    Reviewed-by: 's avatarTimothy Gu <timothygu99@gmail.com>
    Reviewed-by: 's avatarMichael Niedermayer <michael@niedermayer.cc>
    Signed-off-by: 's avatarGanesh Ajjanagadde <gajjanagadde@gmail.com>
    9bc3d335
Name
Last commit
Last update
compat Loading commit data...
doc Loading commit data...
libavcodec Loading commit data...
libavdevice Loading commit data...
libavfilter Loading commit data...
libavformat Loading commit data...
libavresample Loading commit data...
libavutil Loading commit data...
libpostproc Loading commit data...
libswresample Loading commit data...
libswscale Loading commit data...
presets Loading commit data...
tests Loading commit data...
tools Loading commit data...
.gitattributes Loading commit data...
.gitignore Loading commit data...
.travis.yml Loading commit data...
COPYING.GPLv2 Loading commit data...
COPYING.GPLv3 Loading commit data...
COPYING.LGPLv2.1 Loading commit data...
COPYING.LGPLv3 Loading commit data...
CREDITS Loading commit data...
Changelog Loading commit data...
INSTALL.md Loading commit data...
LICENSE.md Loading commit data...
MAINTAINERS Loading commit data...
Makefile Loading commit data...
README.md Loading commit data...
RELEASE Loading commit data...
arch.mak Loading commit data...
cmdutils.c Loading commit data...
cmdutils.h Loading commit data...
cmdutils_common_opts.h Loading commit data...
cmdutils_opencl.c Loading commit data...
common.mak Loading commit data...
configure Loading commit data...
ffmpeg.c Loading commit data...
ffmpeg.h Loading commit data...
ffmpeg_dxva2.c Loading commit data...
ffmpeg_filter.c Loading commit data...
ffmpeg_opt.c Loading commit data...
ffmpeg_qsv.c Loading commit data...
ffmpeg_vdpau.c Loading commit data...
ffmpeg_videotoolbox.c Loading commit data...
ffplay.c Loading commit data...
ffprobe.c Loading commit data...
ffserver.c Loading commit data...
ffserver_config.c Loading commit data...
ffserver_config.h Loading commit data...
library.mak Loading commit data...
version.sh Loading commit data...