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

[Michael Niedermayer]

On Sat, Apr 21, 2012 at 02:25:07PM +0200, Nicolas George wrote:
> Le tridi 3 floréal, an CCXX, Michael Niedermayer a écrit :
> > LGTM, a binary heap would of course be more ideal, especially with
> > many sinks
> 
> I believe it would take a great deal of sinks for a binary heap to be more
> efficient than this implementation, and even more before the difference
> becomes not negligible compared to other bookkeeping operations in the
> filtergraph (and I am not even referring to actual frame processing or
> encoding).

iam not so sure the sink selection needs negligible time with lets say
15 sinks and small audio packets

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.

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


[...]

-- 
Michael     GnuPG fingerprint: 9FF2128B147EF6730BADF133611EC787040B0FAB

Those who are best at talking, realize last or never when they are wrong.
-------------- 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/fc1564c6/attachment.asc>