[FFmpeg-devel] [PATCH] adpcm: Store trellis nodes in a heap structure
Michael Niedermayer
michaelni
Wed Nov 3 16:47:10 CET 2010
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
[...]
> 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
[...]
--
Michael GnuPG fingerprint: 9FF2128B147EF6730BADF133611EC787040B0FAB
If you really think that XML is the answer, then you definitly missunderstood
the question -- Attila Kinali
-------------- 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/20101103/70d8e2be/attachment.pgp>
More information about the ffmpeg-devel
mailing list