[FFmpeg-devel] [PATCH] adpcm: Store trellis nodes in a heap structure

[Michael Niedermayer]

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 
> heap.

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.
-- Epicurus
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 198 bytes
Desc: Digital signature
URL: <http://lists.mplayerhq.hu/pipermail/ffmpeg-devel/attachments/20101109/ddb2ba40/attachment.pgp>