[FFmpeg-devel] [PATCH 3/8] avfilter: keep a list of sink links by age.

[Michael Niedermayer]

On Sat, Apr 21, 2012 at 07:56:50PM +0200, Nicolas George wrote:
> Le tridi 3 floréal, an CCXX, Michael Niedermayer a écrit :
> > 15audio streams (in 15 languages) seem a realistic use case
> > 
> > bubble sort needs a worst case of 15 compares&swaps for this, a heap
> > needs a worst case of 6 compares and swaps
> > not sure which is faster,in this case, it probably depends on how
> > close the actual cases are to the worst case.
> 
> I believe the typical actual cases will be near the worst case in both
> situations, since the typical actual case should look like that:
> 
> - find the oldest sink;
> - request a frame on it;
> - a frames arrives on it, it becomes the youngest.
> 
> But on the other hand, note that the sort happens not when we look for the
> oldest, but when a frame reaches the sink. There is a lot that happens at
> that time, I do not think that a few compares and pointer swaps matter much.
> 
> > also i think an array of pointers without swaps or sorting might be
> > faster than a bubble sorted linked list. Similarly i suspect a heap
> > implemented as an array would be faster than a tree, swaps should
> > need fewer operations
> 
> There is the usual catch to use an array in that case: we need to keep the
> index of the link in the array inside the link, and adjust it when
> reordering happens. That makes things a little bit more complicated.
> 

> I will try to implement that and see if the code is not too complicated.

if it ends up complicated / non trivial in any way then its probably
better to push the patch and leave this for later to investigate

[...]

-- 
Michael     GnuPG fingerprint: 9FF2128B147EF6730BADF133611EC787040B0FAB

Good people do not need laws to tell them to act responsibly, while bad
people will find a way around the laws. -- Plato
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 198 bytes
Desc: Digital signature
URL: <http://ffmpeg.org/pipermail/ffmpeg-devel/attachments/20120421/04aa0305/attachment.asc>