[FFmpeg-cvslog] r25733 - trunk/libavcodec/adpcm.c

[mstorsjo]

Author: mstorsjo
Date: Fri Nov 12 13:30:27 2010
New Revision: 25733

Log:
adpcm: Replace any of the leaf nodes in the heap

By not looking for the exactly largest node, we avoid an O(n) seek through
the leaf nodes. Just pick one (not the same one every time) and try replacing
that node with the new one.

For -trellis 8, this lowers the run time from 190 to 158 seconds.

Modified:
   trunk/libavcodec/adpcm.c

Modified: trunk/libavcodec/adpcm.c
==============================================================================
--- trunk/libavcodec/adpcm.c	Fri Nov 12 13:28:02 2010	(r25732)
+++ trunk/libavcodec/adpcm.c	Fri Nov 12 13:30:27 2010	(r25733)
@@ -387,18 +387,10 @@ static void adpcm_compress_trellis(AVCod
                     if (heap_pos < frontier) {\
                         pos = heap_pos++;\
                     } else {\
-                        /* Find the largest node in the heap, which is one \
-                         * of the leaf nodes. */\
-                        int maxpos = 0;\
-                        uint32_t max_ssd = 0;\
-                        for (k = frontier >> 1; k < frontier; k++) {\
-                            if (nodes_next[k]->ssd > max_ssd) {\
-                                maxpos = k;\
-                                max_ssd = nodes_next[k]->ssd;\
-                            }\
-                        }\
-                        pos = maxpos;\
-                        if (ssd > max_ssd)\
+                        /* Try to replace one of the leaf nodes with the new \
+                         * one, but try a different slot each time. */\
+                        pos = (frontier >> 1) + (heap_pos++ & ((frontier >> 1) - 1));\
+                        if (ssd > nodes_next[pos]->ssd)\
                             goto next_##NAME;\
                     }\
                     u = nodes_next[pos];\