[FFmpeg-devel] [PATCH] Optimize packet interleaving

[Michael Niedermayer]

On Wed, Sep 16, 2009 at 11:50:53AM -0700, Baptiste Coudurier wrote:
> 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.

applied, i also updated oggenc.c that i had missed as it passed regerssion
tests even without the change.

[...]

-- 
Michael     GnuPG fingerprint: 9FF2128B147EF6730BADF133611EC787040B0FAB

Awnsering whenever a program halts or runs forever is
On a turing machine, in general impossible (turings halting problem).
On any real computer, always possible as a real computer has a finite number
of states N, and will either halt in less than N cycles or never halt.
-------------- 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/acefa328/attachment.pgp>