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

[Martin Storsjö]

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.

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.

Once this issue is settled for the normal ADPCM code, I'll update the 
G.722 trellis encoder similarly.

// Martin
-------------- next part --------------
A non-text attachment was scrubbed...
Name: 0001-adpcm-Store-the-trellis-nodes-in-a-heap-instead-of-a.patch
Type: text/x-diff
Size: 4701 bytes
Desc: 
URL: <http://lists.mplayerhq.hu/pipermail/ffmpeg-devel/attachments/20101103/f9212e54/attachment.patch>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: 0002-Reindent.patch
Type: text/x-diff
Size: 2068 bytes
Desc: 
URL: <http://lists.mplayerhq.hu/pipermail/ffmpeg-devel/attachments/20101103/f9212e54/attachment-0001.patch>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: 0003-adpcm-Replace-any-of-the-leaf-nodes-in-the-heap.patch
Type: text/x-diff
Size: 2023 bytes
Desc: 
URL: <http://lists.mplayerhq.hu/pipermail/ffmpeg-devel/attachments/20101103/f9212e54/attachment-0002.patch>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: 0004-adpcm-Don-t-look-for-nodes-with-the-same-sample-valu.patch
Type: text/x-diff
Size: 1599 bytes
Desc: 
URL: <http://lists.mplayerhq.hu/pipermail/ffmpeg-devel/attachments/20101103/f9212e54/attachment-0003.patch>