[FFmpeg-devel] [PATCH 1/2] avfilter: Implement graph_run_once_find_filter() in O(1)

Michael Niedermayer michael at niedermayer.cc
Fri May 27 16:55:26 CEST 2016

On Fri, May 27, 2016 at 04:34:53PM +0200, Nicolas George wrote:
> Le nonidi 9 prairial, an CCXXIV, Michael Niedermayer a écrit :
> > ATM with 10 filters this is 100 times slower than 1 filter
> > with 100 filters its 10000 times slower than 1 filter
> > with 1000 fiters its 1000000 times slower than 1 filter
> What you say seem strange. The code looks O(n×p) with n the number of
> filters and p the average number of pads per filter; p is usually quite
> small.

to pass 1 frame through a simple linear chain each filter might have
to request from the previous (that is n times) and each request needs
to iterate over the whole graph thus O(n*n) per frame
unless i misunderstood the code

from IRC:
<ubitux> michaelni: "no i dont know if someone uses it with 1000 filters" i remember someone doing thousands of drawbox instance of something (one per frame)
<ubitux> michaelni: well, it was pure madness but there is a ticket somewhere
<ubitux> michaelni: http://trac.ffmpeg.org/ticket/5222

> > well, if that patch is incovenient for your work ATM we can drop it.
> Thanks.
> > But i do want this fixed at some point
> > i am alergic to code thats by a factor of "~n" slower than what can
> > reasonable easy be done (unless n is somehow bounded and its just
> > init code or otherwise irrelevant)
> I can ease your mind on that, I am allergic to that kind of thing too.
> Implementing a priority queue of filters that are ready for processing was
> in my TODO queue before this series.


> As always, time available to work on the project is the limiting factor.
> Regards,
> -- 
>   Nicolas George

> _______________________________________________
> ffmpeg-devel mailing list
> ffmpeg-devel at ffmpeg.org
> http://ffmpeg.org/mailman/listinfo/ffmpeg-devel

Michael     GnuPG fingerprint: 9FF2128B147EF6730BADF133611EC787040B0FAB

Concerning the gods, I have no means of knowing whether they exist or not
or of what sort they may be, because of the obscurity of the subject, and
the brevity of human life -- Protagoras
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 181 bytes
Desc: Digital signature
URL: <http://ffmpeg.org/pipermail/ffmpeg-devel/attachments/20160527/621576c8/attachment.sig>

More information about the ffmpeg-devel mailing list