[FFmpeg-devel] [PATCH] avcodec/bitstream: replace qsort with AV_QSORT

[Ganesh Ajjanagadde]

On Sat, Oct 17, 2015 at 9:30 PM, Ganesh Ajjanagadde
<gajjanagadde at gmail.com> wrote:
> Commit 3a0a2f33a6c955823fa4fb12c0b49cd29a496659 claims large performance
> advantages for AV_QSORT over libc's qsort. The reason is that I suspect
> that libc's qsort (at least on non LTO builds, like the typical FFmpeg config)
> can't inline the comparison callback:
> https://stackoverflow.com/questions/5290695/is-there-any-way-a-c-c-compiler-can-inline-a-c-callback-function.
> AV_QSORT has two things going for it:
> 1. The guaranteed inlining of qsort itself. This yields a negligible
> boost that may be ignored.
> 2. The more serious possibility of potentially allowing the comparison
> function to be inlined - this is likely responsible for the large boosts
> reported.
>
> There is a comment explaining that this is a place that could use some
> performance improvement. Thus AV_QSORT is used to achieve that.
>
> Benchmarks deemed unnecessary due to existing claims about AV_QSORT.
> Tested with FATE.
>
> Signed-off-by: Ganesh Ajjanagadde <gajjanagadde at gmail.com>
> ---
>  libavcodec/bitstream.c | 3 ++-
>  1 file changed, 2 insertions(+), 1 deletion(-)
>
> diff --git a/libavcodec/bitstream.c b/libavcodec/bitstream.c
> index 924cc51..1acb7a3 100644
> --- a/libavcodec/bitstream.c
> +++ b/libavcodec/bitstream.c
> @@ -30,6 +30,7 @@
>
>  #include "libavutil/atomic.h"
>  #include "libavutil/avassert.h"
> +#include "libavutil/qsort.h"
>  #include "avcodec.h"
>  #include "internal.h"
>  #include "mathops.h"
> @@ -333,7 +334,7 @@ int ff_init_vlc_sparse(VLC *vlc_arg, int nb_bits, int nb_codes,
>      }
>      COPY(buf[j].bits > nb_bits);
>      // qsort is the slowest part of init_vlc, and could probably be improved or avoided
> -    qsort(buf, j, sizeof(VLCcode), compare_vlcspec);
> +    AV_QSORT(buf, j, struct VLCcode, compare_vlcspec);
>      COPY(buf[j].bits && buf[j].bits <= nb_bits);
>      nb_codes = j;
>
> --
> 2.6.1
>

Indeed confirmed the difference in inlining: the asm for
compare_vlcspec is gone. Thus performance gains should be obvious.