[FFmpeg-devel] [PATCH] Optimize packet interleaving

[Baptiste Coudurier]

Hi Michael,

On 09/16/2009 10:38 AM, Michael Niedermayer wrote:
> 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

Patch ok, I trust you on this. I'll have a look to remove the array
used for counting packet of each stream also, same for oggenc.

[...]

-- 
Baptiste COUDURIER
Key fingerprint                 8D77134D20CC9220201FC5DB0AC9325C5C1ABAAA
FFmpeg maintainer                                  http://www.ffmpeg.org