[FFmpeg-devel] [PATCH 3/8] avfilter: keep a list of sink links by age.
michaelni at gmx.at
Sat Apr 21 17:56:31 CEST 2012
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
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
Size: 198 bytes
Desc: Digital signature
More information about the ffmpeg-devel