[FFmpeg-devel] [RFC] av_tree enumeration

[Michael Niedermayer]

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>