[FFmpeg-devel] [RFC] av_tree enumeration

[Stefano Sabatini]

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?
find      = O(log(n))
next      = O(log(n))

Looks more complex than 1) and 2).

4) to use other data structures, e.g. trees or dictionaries.


I don't have a strong opinion about it, I'm also reasonably happy with
1) if we choose that.

Regards.
-- 
FFmpeg = Fundamentalist & Funny Most Peaceful Encoding/decoding Gadget