[FFmpeg-devel] [PATCH] adpcm: Use a hash table to improve chcking for duplicate samples

[Michael Niedermayer]

On Fri, Nov 19, 2010 at 09:42:44AM +0200, Martin Storsj? wrote:
> On Fri, 19 Nov 2010, Michael Niedermayer wrote:
> 
> > On Thu, Nov 18, 2010 at 11:19:04PM +0200, Martin Storsj? wrote:
> > > Hi,
> > > 
> > > With the attached patch #1, the runtime for -trellis 8 drops from 158 to 
> > > 21 seconds, for my 30 second sample, see 
> > > http://albin.abo.fi/~mstorsjo/adpcm-graphs3/hash.pdf for details on that, 
> > > compared to the current trunk and compared to the old original code. This 
> > > speeds up things enough to actually be able to run all the way to -trellis 
> > > 15 within reasonable time (running into the issue with ssd wrapping 
> > > around, as I sent a patch for earlier), and one notices that it exhausts 
> > > all testable combinations at around -trellis 10, where the PSNR doesn't 
> > > really increase any longer.
> > > 
> > > As discussed earlier, the skipping when a matching sample is found could 
> > > also be done only if the ssd actually is worse than for that one. 
> > > Curiously enough, it gives slightly worse results (and slows things down 
> > > quite a bit), see 
> > > http://albin.abo.fi/~mstorsjo/adpcm-graphs3/with_without_check.pdf.
> > > 
> > > The second patch gives a slight, 0.1 dB increase in PSNR.
> > [...]
> > > @@ -393,6 +407,7 @@ static void adpcm_compress_trellis(AVCodecContext *avctx, const short *samples,
> > >                          if (ssd > nodes_next[pos]->ssd)\
> > >                              goto next_##NAME;\
> > >                      }\
> > > +                    *h = generation;\
> > >                      u = nodes_next[pos];\
> > >                      if(!u) {\
> > >                          assert(pathn < FREEZE_INTERVAL<<avctx->trellis);\
> > > @@ -442,6 +457,7 @@ static void adpcm_compress_trellis(AVCodecContext *avctx, const short *samples,
> > >          u = nodes;
> > >          nodes = nodes_next;
> > >          nodes_next = u;
> > > +        generation++;
> > >  
> > >          // prevent overflow
> > >          if(nodes[0]->ssd > (1<<18)) {
> > > @@ -463,6 +479,8 @@ static void adpcm_compress_trellis(AVCodecContext *avctx, const short *samples,
> > >              // checking which nodes do so is too slow, so just kill them all.
> > >              // this also slightly improves quality, but I don't know why.
> > >              memset(nodes+1, 0, (frontier-1)*sizeof(TrellisNode*));
> > > +            memset(hash, 0xff, 65536 * sizeof(*hash));
> > > +            generation = 0;
> > 
> > shouldnt this be
> > if(generation==255)
> >         ...
> > ?
> 
> Yes, it could be moved out from the path freezing routine - then also we 
> won't have the dependency between FREEZE_INTERVAL and the hash element 
> size. As in attached then - this gives the same results as the previous 
> version.
> 
> // Martin
>  adpcm.c |   35 +++++++++++++++++++++++++++--------
>  1 file changed, 27 insertions(+), 8 deletions(-)
> 98600a97b4afbcfe6c093ca86ec3d4d490d2b618  0001-adpcm-Use-a-hash-table-to-improve-checking-for-dupli.patch
> From 45b177b1b13409b58573313c8f04f45aa4786d3a Mon Sep 17 00:00:00 2001
> From: Martin Storsjo <martin at martin.st>
> Date: Sun, 14 Nov 2010 12:41:06 +0200
> Subject: [PATCH 1/2] adpcm: Use a hash table to improve checking for duplicate samples
> 
> This lowers the run time from 158 to 21 seconds, for -trellis 8
> with a 30 second sample on my machine.
> 
> This requires 64 KB additional memory.

lgtm


[...]

>  adpcm.c |    3 ++-
>  1 file changed, 2 insertions(+), 1 deletion(-)
> 3bd5c10e1a6c5753daa71bb0e1d94d43f9bc812d  0002-adpcm-Only-increment-heap_pos-after-finding-a-good-e.patch
> From 1ec0b8bcb7a784e989a9c9975efb1eb3ad209994 Mon Sep 17 00:00:00 2001
> From: Martin Storsjo <martin at martin.st>
> Date: Thu, 18 Nov 2010 22:54:28 +0200
> Subject: [PATCH 2/2] adpcm: Only increment heap_pos after finding a good enough sample
> 
> This increases the PSNR slightly (about 0.1 dB) for trellis sizes
> below 8, and gives equal PSNR for sizes above that.

lgtm

-- 
Michael     GnuPG fingerprint: 9FF2128B147EF6730BADF133611EC787040B0FAB

The greatest way to live with honor in this world is to be what we pretend
to be. -- Socrates
-------------- 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/20101119/58cb4c8d/attachment.pgp>