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

wm4 nfxjfg at googlemail.com
Sun Oct 18 17:17:44 CEST 2015


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?

It might depend on the actual data to be sorted. Is the data completely
random? Is it already sorted in most cases? etc.

I'm not fond of such frivolous mass-changes.


More information about the ffmpeg-devel mailing list