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

[Ganesh Ajjanagadde]

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), fraps-v2 from FATE:
new:
280110 decicycles in qsort,       1 runs,      0 skips
268260 decicycles in qsort,       2 runs,      0 skips

old:
1469910 decicycles in qsort,       1 runs,      0 skips
 952950 decicycles in qsort,       2 runs,      0 skips

Signed-off-by: Ganesh Ajjanagadde <gajjanagadde at gmail.com>
---
 libavcodec/huffman.c | 3 ++-
 1 file changed, 2 insertions(+), 1 deletion(-)

diff --git a/libavcodec/huffman.c b/libavcodec/huffman.c
index c771bcf..d7403b8 100644
--- a/libavcodec/huffman.c
+++ b/libavcodec/huffman.c
@@ -26,6 +26,7 @@
 
 #include <stdint.h>
 
+#include "libavutil/qsort.h"
 #include "avcodec.h"
 #include "get_bits.h"
 #include "huffman.h"
@@ -170,7 +171,7 @@ int ff_huff_build_tree(AVCodecContext *avctx, VLC *vlc, int nb_codes, int nb_bit
                "Tree construction is not possible\n");
         return -1;
     }
-    qsort(nodes, nb_codes, sizeof(Node), cmp);
+    AV_QSORT(nodes, nb_codes, Node, cmp);
     cur_node = nb_codes;
     nodes[nb_codes*2-1].count = 0;
     for (i = 0; i < nb_codes * 2 - 1; i += 2) {
-- 
2.6.2