[FFmpeg-devel] [RFC] av_tree enumeration
Sat Nov 14 03:39:23 CET 2009
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)
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.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Size: 189 bytes
Desc: Digital signature
More information about the ffmpeg-devel