Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.compression > #2200

Re: Harry Potter: my progress with compression

Show all headers | View raw

BGB <cr88192@hotmail.com> wrote:

(snip)

> Deflate is kind of hard to really beat out significantly short of huge 
> dictionaries and matches (and a data-set prone to said matches), and or 
> throwing an expensive entropy-coding scheme at it (such as arithmetic 
> coding).
 
> for example, I got some (modest) compression gains recently with a 
> recent format, I suspect mostly due to the larger dictionary, and 
> possibly specifics of the format being compressed (video frames).
 
> it also gains some (slightly) via use of an arithmetic coder, 
> but this does not come free:

Some time ago, I was comparing JBIG2 to LZW for bit image
compression for PDFs. JBIG2 compresses better, but is noticeably
slower to decompress. (To compress, too, but one assumes it will
be decompressed more times.) 

When viewed with Adobe Reader, the LZW images update about as
fast as you can watch them, but for JBIG2, you can see the delay.

The arithmetic coder words on one bit at a time, where LZW 
processes the input one byte at a time. 

> in the profiler, around 45% of the running time is spent in the 
> arithmetic decoder: ~35% in the function that reads a bit and updates 
> the probability, and ~10% in the function to re-normalize.

I din't profile it, but that sounds about like I might expect.
 
> it is, I suspect, mostly due to branch mis-predictions in this case 
> (there is an "if()" branch to update a few variables and the model 
> depending on the input bit).
 
> so, for performance-sensitive cases, probably back to Huffman.
> well, and/or use a codec design sufficiently expensive to decode that it 
> mostly hides the cost of the AC (and if it gets extra bad, they resort 
> to a multithreaded decoder or similar...).

I still like LZW, but it depends a lot on the actual data.
 
> still have it decoding now at 210 Mpix/sec for a single-threaded decoder 
> with AC enabled (and 730 Mpix/sec for multithreaded), so probably not 
> too horrible.

Sounds about right. 15Mpix for an 8.5x11 page at 400dpi. My computer
might be slower, too.

-- glen

Back to comp.compression | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Harry Potter: my progress with compression Harry Potter <rose.joseph12@yahoo.com> - 2013-12-17 11:19 -0800
  Re: Harry Potter: my progress with compression earl_colby_pottinger@yahoo.com - 2013-12-17 14:21 -0800
    Re: Harry Potter: my progress with compression Harry Potter <rose.joseph12@yahoo.com> - 2013-12-18 06:20 -0800
      Re: Harry Potter: my progress with compression Harry Potter <rose.joseph12@yahoo.com> - 2014-01-21 08:18 -0800
        Re: Harry Potter: my progress with compression BGB <cr88192@hotmail.com> - 2014-01-21 13:54 -0600
          Re: Harry Potter: my progress with compression glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2014-01-21 22:37 +0000
            Re: Harry Potter: my progress with compression BGB <cr88192@hotmail.com> - 2014-01-21 20:27 -0600
              Re: Harry Potter: my progress with compression glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2014-01-22 03:55 +0000
                Re: Harry Potter: my progress with compression Robert Wessel <robertwessel2@yahoo.com> - 2014-01-21 23:59 -0600
                Re: Harry Potter: my progress with compression BGB <cr88192@hotmail.com> - 2014-01-22 02:35 -0600
  Re: Harry Potter: my progress with compression Harry Potter <rose.joseph12@yahoo.com> - 2014-01-28 10:38 -0800
    Re: Harry Potter: my progress with compression Harry Potter <rose.joseph12@yahoo.com> - 2014-02-10 07:20 -0800
      Re: Harry Potter: my progress with compression Harry Potter <rose.joseph12@yahoo.com> - 2014-02-24 09:13 -0800

csiph-web