[FFmpeg-devel] [PATCH] Optimize packet interleaving

[Michael Niedermayer]

Hi

Until a few days ago, the muxer code in utils.c always inserted packets
into a ordered buffer by searching over the whole buffer.
That being O(buffer_size) per packet and O(packets_in_file^2) per file
in worst case. (the common case of course was much much faster)
The worst case did actually happen in issue1379 ...
Ive fixed that by adding a O(1) special case for when the given packet is
already interleaved correctly ...

The patch below keeps that O(1) for correctly interleaved input while
improving the worst case
from O(packets_in_file^2) to O(packets_in_file*num_streams)
iam posting it here because i had to change mxfenc.c too ...
regression tests pass, issue1379 still is fast


PS: yes i know it can in theory be done in O(packets_in_file) in
worst case but that would be tricky (radix sorting all packets) or
O(packets_in_file*log(num_streams)) but that would hardly be worth it
as num_streams is unlikly large enough for the extra complexity to
be an advantage, also the packet sorting code speed should only
matter for rather small packets anyway ...

PS2: i intend to commit in a few days if there are no objections

-- 
Michael     GnuPG fingerprint: 9FF2128B147EF6730BADF133611EC787040B0FAB

It is not what we do, but why we do it that matters.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: interleave_opt.diff
Type: text/x-patch
Size: 4084 bytes
Desc: not available
URL: <http://lists.mplayerhq.hu/pipermail/ffmpeg-devel/attachments/20090916/f607fba5/attachment.bin>
-------------- 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/20090916/f607fba5/attachment.pgp>