[FFmpeg-devel] [RFC] av_tree enumeration
Michael Niedermayer
michaelni
Sun Nov 15 00:35:42 CET 2009
On Sat, Nov 14, 2009 at 10:08:27PM +0100, Stefano Sabatini wrote:
> On date Saturday 2009-11-14 16:53:53 +0100, Stefano Sabatini encoded:
> > 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.
>
> We have different options here:
>
> 1) to keep the next field in the various element and use it, the main
> problem is that this way we have non-const data in the element
> definitions, so the corresponding code cannot be kept in shareable
> memory.
> Performance:
>
> insertion = O(n)
> find = O(n)
> next = O(1)
>
> No need for allocation / free.
>
> 2) to use a list of elements, as it was implemented for libavfilter
> filters before I removed it, the list can be sorted or non-sorted.
>
> insertion = O(n)
> find = O(n)
> next = O(n)
>
> Requires allocation / deallocation of the list elements, so in theory
> a registration may fail for a memory allocation error.
>
> Main problem is that the next operation is slow, this *may* be in
> theory a problem e.g. when enumerating a long list of elements.
>
> 3) to use an array with variable dimension. If the array is sorted we
> can use bsearch for fast searches. We need to allocate such array and
> since we don't know its size we may need to reallocate and/or memcpy
> data.
>
> Performance (sorted):
>
> insertion = O(log(n)) + realloc/memcpy?
insert is O(1) without sort and O(n) when maintaining sort its also
O(1) when doing n inserts and seperate sort after all
> find = O(log(n))
true if sorted
> next = O(log(n))
next is O(1), that is p+1
>
> Looks more complex than 1) and 2).
>
> 4) to use other data structures, e.g. trees or dictionaries.
5)
Use array of compile time constant size
[...]
--
Michael GnuPG fingerprint: 9FF2128B147EF6730BADF133611EC787040B0FAB
It is not what we do, but why we do it that matters.
-------------- 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/20091115/0ccbcf1d/attachment.pgp>
More information about the ffmpeg-devel
mailing list