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

[Martin Storsjö]

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.

Does this sound sane, or did I miss something in my implementation?

// Martin
-------------- next part --------------
A non-text attachment was scrubbed...
Name: 0001-adpcm-Store-the-trellis-nodes-in-a-max-heap.patch
Type: text/x-diff
Size: 7742 bytes
Desc: 
URL: <http://lists.mplayerhq.hu/pipermail/ffmpeg-devel/attachments/20101109/59e62453/attachment.patch>