[FFmpeg-devel] [PATCH] adpcm: Store trellis nodes in a heap structure
Tue Nov 9 23:37:13 CET 2010
On Tue, Nov 09, 2010 at 11:07:54PM +0200, Martin Storsj? wrote:
> On Wed, 3 Nov 2010, Martin Storsj? wrote:
> > On Wed, 3 Nov 2010, Michael Niedermayer wrote:
> > > On Wed, Nov 03, 2010 at 02:33:03PM +0200, Martin Storsj? wrote:
> > > > Hi,
> > > >
> > > > As pointed out by Michael when reviewing the G.722 trellis encoder, the
> > > > stored trellis nodes could be stored in a heap-like structure, instead of
> > > > in a straight sorted array.
> > > >
> > > > Currently, when inserting a new trellis node, a linear search (which in
> > > > itself perhaps could be sped up by converting it to a binary search) is
> > > > used to find the spot where it should be inserted, and then all later
> > > > node pointers are moved back one step with memmove. Since only a subset of
> > > > all evaluated nodes are stored, the worst one is removed once the array is
> > > > full.
> > > >
> > > > Instead of doing this, the attached patch set stored the node pointers in
> > > > a heap structure, by first adding all evaluated nodes to a heap, as long
> > > > as they all fit. Once they don't all fit, we check through all the
> > > > frontier/2 leaf nodes to find the worst one, replace that one with the
> > > > current and restore the heap property.
> > >
> > > why dont you store the heap fliped? that is with the worst node at the base
> > > that way removial of it is much faster
> > Yes, that's a good idea, Loren suggested that too. I'll try it, together
> > with doing the testing with adpcm_ima_wav instead of adpcm_ima_qt, since
> > that gives longer runs which gives the trellis much better possibility to
> > actually gain something.
> For some reason, this actually didn't give any performance improvment at
> all, compared to the initial implementation. The current version of this
> is attached.
> The reason seems to be that if inserting/replacing nodes in the heap at
> the bottom, we don't need to move the newly inserted node particularly
> many steps. If using a max heap instead, and replacing the top/root node,
> we need to sift the new node down more iterations, on average, and each
> step of this is a more expensive operation (comparing the current node
> with both children). With the min heap, we need to do on average 1.6
> iterations/comparisons in the sifting routine for each node, while we need
> 2.6-3.2 iterations (which do two comparisons each) when using the max
hmm, ok then lets continue with your original approuch
Michael GnuPG fingerprint: 9FF2128B147EF6730BADF133611EC787040B0FAB
The misfortune of the wise is better than the prosperity of the fool.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Size: 198 bytes
Desc: Digital signature
More information about the ffmpeg-devel