[FFmpeg-devel] [PATCH] all: replace qsort with AV_QSORT

Ganesh Ajjanagadde gajjanag at mit.edu
Sun Oct 18 17:40:18 CEST 2015


On Sun, Oct 18, 2015 at 11:25 AM, Ganesh Ajjanagadde <gajjanag at mit.edu> wrote:
> On Sun, Oct 18, 2015 at 11:17 AM, wm4 <nfxjfg at googlemail.com> wrote:
>> On Sun, 18 Oct 2015 11:06:57 -0400
>> Ganesh Ajjanagadde <gajjanag at mit.edu> wrote:
>>
>>> On Sun, Oct 18, 2015 at 11:01 AM, wm4 <nfxjfg at googlemail.com> wrote:
>>> > On Sun, 18 Oct 2015 10:47:52 -0400
>>> > Ganesh Ajjanagadde <gajjanagadde at gmail.com> wrote:
>>> >
>>> >> Commit e11e32686fdb21aded1ccf70202f1fffe87bb6a2 explains why replacing
>>> >> qsort with AV_QSORT yields performance improvements.
>>> >>
>>> >> This replaces all existing uses of libc's qsort with AV_QSORT.
>>> >>
>>> >> Benchmarks deemed unnecessary due to existing claims about AV_QSORT.
>>> >> Tested with FATE.
>>> >>
>>> >> Signed-off-by: Ganesh Ajjanagadde <gajjanagadde at gmail.com>
>>> >> ---
>>> >>  cmdutils.c                       |  3 ++-
>>> >>  cmdutils_opencl.c                |  3 ++-
>>> >>  ffmpeg.c                         |  3 ++-
>>> >>  libavcodec/aacsbr_template.c     | 14 ++++++++------
>>> >>  libavcodec/huffman.c             |  3 ++-
>>> >>  libavcodec/motion_est_template.c |  3 ++-
>>> >>  libavcodec/utvideodec.c          |  4 ++--
>>> >>  libavcodec/utvideoenc.c          |  5 +++--
>>> >>  libavfilter/f_sendcmd.c          |  3 ++-
>>> >>  libavfilter/vf_deshake.c         |  3 ++-
>>> >>  libavfilter/vf_palettegen.c      |  2 +-
>>> >>  libavfilter/vf_paletteuse.c      |  2 +-
>>> >>  libavfilter/vf_removegrain.c     |  7 ++++---
>>> >>  libavformat/subtitles.c          | 10 +++++++---
>>> >>  libswresample/swresample-test.c  |  3 ++-
>>> >>  tests/checkasm/checkasm.c        |  4 ++--
>>> >>  16 files changed, 44 insertions(+), 28 deletions(-)
>>> >
>>> > By how much does this increase binary code size?
>>> >
>>> > Is it really faster? (libc qsort() could use a better algorithm,
>>> > even if it has to go through indirections.)
>>>
>>> Michael has already shown that AV_QSORT is faster. libc's qsort can
>>> easily be looked up: Michael already uses most of the tricks (usage of
>>> stack to avoid recursion, etc). The main benefits come from the
>>> inlining.
>>
>> Where?
>
> The inlining of the comparison callback.
>
>>
>> It might depend on the actual data to be sorted. Is the data completely
>> random? Is it already sorted in most cases? etc.
>
> True, but Michael's implementation and libc's do not do any tricks for
> "almost completely sorted". The time is dominated by the calls to the
> comparator. This is well known, and is why C++'s std::sort is roughly
> 5x faster on basic types.
>
>>
>> I'm not fond of such frivolous mass-changes.

Ok, here are some binary size numbers (most widespread changes are in
libavfilter/libavcodec):
libavfilter:
old 7126048 bytes
new 7169424 bytes
0.6% increase

libavcodec:
old 59719192 bytes
new 59747576 bytes
0.04% increase

>> _______________________________________________
>> ffmpeg-devel mailing list
>> ffmpeg-devel at ffmpeg.org
>> http://ffmpeg.org/mailman/listinfo/ffmpeg-devel


More information about the ffmpeg-devel mailing list