[FFmpeg-devel] [RFC] av_tree enumeration

Stefano Sabatini stefano.sabatini-lala
Sat Nov 14 16:53:53 CET 2009


On date Saturday 2009-11-14 03:39:23 +0100, Michael Niedermayer encoded:
> On Sat, Nov 14, 2009 at 01:41:17AM +0100, Stefano Sabatini wrote:
> > Hi all,
> > 
> > I'm considering to use av_tree for storing elements of FFmpeg,
> > e.g. filters, codecs etc.
> > 
> > This should allow two important objectives:
> > * to make insertion / extraction / find operations faster
> 
> thats true but is this even limiting any real case ATM?
> imagine we had 10000 codecs and filters (you can easily simulate this
> with dummy codecs) does this make any meassureable speed difference?

No, and to say the truth I don't care too much about it, but there is
also the other objective, to remove the non-const "next" field from
the element structs.
 
> I am in general in favor of using asymptotically fast algorithms but
> sometimes, like here iam not sure if the asymptotic case exists.
> For example a file can become arbitrary long, continous recording could
> easily create files several weeks long (30fps*3600*24*7 is an amount where
> n vs log n is significant)
> but
> codecs and filters, its one thing to record a video twice as long but
> create twice as many filters or codecs?
> that said, trees are not the correct structure for filters or codecs
> because they do not represent ordered points on a axis like frames in a
> video. We have no need to search for filters between filters, the
> "correct" fast way to store them would be a hash table not a tree
> That said, insert by append, sort, bsearch is the obvious non hash
> solution if log n access is wanted
> 
> Also before you go further with this, think about thread saftey

I'll go for a sorted list of registered element, which then can be
bin-searched.

Regards.
-- 
FFmpeg = Fostering and Furious Muttering Pacific Ecumenical Game



More information about the ffmpeg-devel mailing list