[FFmpeg-devel] [PATCH] adpcm: Store trellis nodes in a heap structure
Michael Niedermayer
michaelni
Wed Nov 10 13:37:57 CET 2010
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?
[...]
> 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
>
> 0:
> user 0m0.037s
> stddev: 40.03 PSNR: 64.28 MAXDIFF: 2874 bytes: 2646016/ 2649218
>
> 1:
> user 0m0.191s
> stddev: 37.48 PSNR: 64.85 MAXDIFF: 3026 bytes: 2646016/ 2649218
>
> 2:
> user 0m0.433s
> stddev: 35.22 PSNR: 65.39 MAXDIFF: 2681 bytes: 2646016/ 2649218
>
> 3:
> user 0m0.880s
> stddev: 33.87 PSNR: 65.73 MAXDIFF: 2643 bytes: 2646016/ 2649218
>
> 4:
> user 0m1.684s
> stddev: 32.96 PSNR: 65.97 MAXDIFF: 2650 bytes: 2646016/ 2649218
>
> 5:
> user 0m3.252s
> stddev: 32.34 PSNR: 66.13 MAXDIFF: 2467 bytes: 2646016/ 2649218
>
> 6:
> user 0m6.044s
> stddev: 31.69 PSNR: 66.31 MAXDIFF: 1907 bytes: 2646016/ 2649218
>
> 7:
> user 0m11.906s
> stddev: 31.57 PSNR: 66.34 MAXDIFF: 2105 bytes: 2646016/ 2649218
>
> 8:
> user 0m22.960s
> stddev: 31.35 PSNR: 66.40 MAXDIFF: 1782 bytes: 2646016/ 2649218
>
> // Martin
> _______________________________________________
> ffmpeg-devel mailing list
> ffmpeg-devel at mplayerhq.hu
> https://lists.mplayerhq.hu/mailman/listinfo/ffmpeg-devel
--
Michael GnuPG fingerprint: 9FF2128B147EF6730BADF133611EC787040B0FAB
Observe your enemies, for they first find out your faults. -- Antisthenes
-------------- 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/bfde92f4/attachment.pgp>
More information about the ffmpeg-devel
mailing list