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

[Martin Storsjö]

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.

> [...]
> > Output from tiny-psnr:
> > No trellis:
> > stddev:  101.13 PSNR: 56.23 MAXDIFF: 7183 bytes:  4865398/  4865408
> > -trellis 5, original code:
> > stddev:   81.78 PSNR: 58.08 MAXDIFF: 4798 bytes:  4865398/  4865408
> > After patch #1:
> > stddev:   81.70 PSNR: 58.08 MAXDIFF: 4798 bytes:  4865398/  4865408
> > After patch #3:
> > stddev:   80.77 PSNR: 58.18 MAXDIFF: 4766 bytes:  4865398/  4865408
> > After patch #4:
> > stddev:   80.94 PSNR: 58.17 MAXDIFF: 4524 bytes:  4865398/  4865408
> > 
> > So even if patch #3 and #4 in theory should worsen the output slightly, 
> > they actually seem to improve the result in this case, since other nodes 
> > happen to be stored/thrown away. The main point is that it doesn't seem to 
> > harm the output quality significantly while improving the runtime 
> > performance massively.
> 
> It would be insterresting to know why they improve quality

Yes - my uneducated guess is that we simply keep/throw away other (roughly 
equally good/bad) nodes which happen to be more beneficial later, which 
can't really be predicted at that point.

// Martin