[FFmpeg-devel] [PATCH] optimize init_vlc

[Michael Niedermayer]

On Sun, Mar 28, 2010 at 04:17:59AM +0000, Loren Merritt wrote:
> optimize init_vlc().
> Reduce worst case time from O(N^2) to O(N*log(N)).
> Reduce average case by a factor of 7 in ffv2 (total decoding speed +4-25%)
> Reduce average case by a factor of 1.3 in ffvhuff (total decoding speed 
> +0.5%)
> Reduce average case by a factor of 1.05 in mjpeg (total decoding speed 
> +0.05%)
> I haven't extensively benchmarked other codecs, because these are the only 
> ones I know of that use init_vlc during decoding.
>
> I think the relevant difference between the codecs is that ffv2 uses large 
> tables with long codes, ffvhuff uses large tables but mostly fits within 
> one VLC_BITS, and mjpeg uses small tables.
>

> Most (50-80%) of the remaining time is in qsort.
> This could be improved by special-casing qsort so that it doesn't need 
> function pointers and variable-sized memcpies in the inner loop.
> Or by interleaving radix-sort into build_table.

a generic libavutil/sort.h is welcome


>
> --Loren Merritt

>  bitstream.c |  170 ++++++++++++++++++++++++++++++++++++------------------------
>  1 file changed, 103 insertions(+), 67 deletions(-)
> 2ee3cbb283afe0a474dd30f79b70ecf4c1d558b9  init_vlc.diff

ok without the START/STOP_TIMER debug code


[...]
-- 
Michael     GnuPG fingerprint: 9FF2128B147EF6730BADF133611EC787040B0FAB

When you are offended at any man's fault, turn to yourself and study your
own failings. Then you will forget your anger. -- Epictetus
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: Digital signature
URL: <http://lists.mplayerhq.hu/pipermail/ffmpeg-devel/attachments/20100328/cb7f3caf/attachment.pgp>