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

[Nicolas George]

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.

Regards,

-- 
  Nicolas George
-------------- 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/1b2f7516/attachment.asc>