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

[Martin Storsjö]

On Fri, 19 Nov 2010, Michael Niedermayer wrote:

> 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

Thanks, applied.

> >  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

Applied

// Martin