[FFmpeg-devel] [RFC] av_tree enumeration

[Michael Niedermayer]

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?

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

[...]
-- 
Michael     GnuPG fingerprint: 9FF2128B147EF6730BADF133611EC787040B0FAB

The worst form of inequality is to try to make unequal things equal.
-- Aristotle
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: Digital signature
URL: <http://lists.mplayerhq.hu/pipermail/ffmpeg-devel/attachments/20091114/23f64001/attachment.pgp>