[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 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
-------------- next part --------------
A non-text attachment was scrubbed...
Name: 0001-adpcm-Use-a-hash-table-to-improve-checking-for-dupli.patch
Type: text/x-diff
Size: 5150 bytes
Desc: 
URL: <http://lists.mplayerhq.hu/pipermail/ffmpeg-devel/attachments/20101119/2223f218/attachment.patch>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: 0002-adpcm-Only-increment-heap_pos-after-finding-a-good-e.patch
Type: text/x-diff
Size: 1326 bytes
Desc: 
URL: <http://lists.mplayerhq.hu/pipermail/ffmpeg-devel/attachments/20101119/2223f218/attachment-0001.patch>