[FFmpeg-devel] [PATCH 3/8] avfilter: keep a list of sink links by age.
nicolas.george at normalesup.org
Sat Apr 21 19:56:50 CEST 2012
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.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Size: 198 bytes
Desc: Digital signature
More information about the ffmpeg-devel