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

[Michael Niedermayer]

On Wed, Nov 10, 2010 at 03:13:09PM +0200, Martin Storsj? wrote:
> On Wed, 10 Nov 2010, Michael Niedermayer wrote:
> 
> > On Wed, Nov 10, 2010 at 11:42:48AM +0200, Martin Storsj? wrote:
> > > On Wed, 3 Nov 2010, Martin Storsj? wrote:
> > > 
> > > > 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.
> > > > 
> > > > This doesn't give identical results to the initial version, since the 
> > > > nodes from the previous round are used for doing the next step in the 
> > > > order they're stored in the array, which is different.
> > > > 
> > > > Instead of chekcing all the frontier/2 leaf nodes to find the worst one, 
> > > > patch #3 just picks one of the leaf nodes and tries replacing that one. By 
> > > > picking a different one of the leaf nodes each time, we more or less 
> > > > achieve the same thing. (If only one spot would be tested, only the path 
> > > > from that node up to the root would be updated once the heap is full.)
> > > > 
> > > > The last patch removes the search for nodes with an equal sample value to 
> > > > the one currently inserted, since it's an O(frontier) operation, which 
> > > > speeds things up immensely, without notably affecting the quality.
> > > > 
> > > > Some numbers, runtime:
> > > > Original: 16.1 s
> > > > After patch #1: 14.8 s
> > > > After patch #3: 10.9 s
> > > > After patch #4: 5.6 s
> > > > 
> > > > 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.
> > > 
> > > Updated benchmarks of this code - the sample in question is a 30 second 
> > > clip, 44 kHz mono. Now I've done the testing with adpcm_ima_wav as codec,
> > 
> > can that clip be downloaded somewhere?
> 
> I uploaded it to http://albin.abo.fi/~mstorsjo/adpcm-input.wav.

ok, testing with some music might make sense too


> 
> For testing, I do e.g. this:
> time ./ffmpeg -y -i adpcm-input.wav -acodec adpcm_ima_wav -trellis 7 adpcm.wav
> ./ffmpeg -y -i adpcm.wav out.wav > /dev/null 2>&1
> tests/tiny_psnr adpcm-input.wav out.wav 2
> 
> 
> > > Also, for reference, the same input with different trellis sizes, after 
> > > patch #4:
> > 
> > it would be interresting to also see this with pre #4 so one can compare it
> 
> Ok, here are even more numbers:

these would be easier to compare with gnuplot printing quality vs time

anyway, so far your patchset looks good and iam not insisting on more testing
it just would be interresting as some of these patches reduce quality and
improve speed so Time vs Distortion curves would more clearly show the
improvment

[...]
-- 
Michael     GnuPG fingerprint: 9FF2128B147EF6730BADF133611EC787040B0FAB

Good people do not need laws to tell them to act responsibly, while bad
people will find a way around the laws. -- Plato
-------------- 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/20101110/47cca152/attachment.pgp>