Compression - Arithmetic encoder speed

Author

Arithmetic encoder speed

Randy McNabb

2005-01-17, 3:55 pm

Hello all,
I have been optimizing my arithmetic encoder for speed . I am currently
compressing a little more than 2 meg/sec on a 1Ghz PIII. I was wondering
what would be considered a good speed. Thank you all for your help.

Randy McNabb

Thomas Richter

2005-01-18, 8:55 pm

Hi,

> I have been optimizing my arithmetic encoder for speed . I am currently
> compressing a little more than 2 meg/sec on a 1Ghz PIII. I was wondering
> what would be considered a good speed. Thank you all for your help.

Good speed is if writing is almost as fast as writing the data
unencoded. To get an impression about a very fast (binary) arithmetic
encoder, google for the MQ or QM coder and compare with that. A non-
binary encoder might not be able to get that fast, though.

So long,
Thomas

Matt Mahoney

2005-01-18, 8:55 pm

Randy McNabb wrote:
> Hello all,
> I have been optimizing my arithmetic encoder for speed . I am
currently
> compressing a little more than 2 meg/sec on a 1Ghz PIII. I was
wondering
> what would be considered a good speed. Thank you all for your help.
>
> Randy McNabb

It depends on your application. How fast does it need to be? The
arithmetic coder in PAQ is probably slower than your encoder, but
vastly faster than the predictor, so any optimization would be rather
pointless.

-- Matt Mahoney

Randy McNabb

2005-01-18, 8:56 pm

"Matt Mahoney" <matmahoney@yahoo.com> wrote in message
news:1106061796.577712.116570@c13g2000cwb.googlegroups.com...
>
> Randy McNabb wrote:
> currently
> wondering
>
> It depends on your application. How fast does it need to be? The
> arithmetic coder in PAQ is probably slower than your encoder, but
> vastly faster than the predictor, so any optimization would be rather
> pointless.
>
> -- Matt Mahoney
>
Hi Matt,
My compressor doesn't have to be fast . I am working on it just to see
how fast I can get it. I came up with new algorithms of the encoder, file
i/o, and the model. I was just wondering how fast was fast. the 2 meg/sec
was from source file to encoded file. Just the encoder and writing to file
is running around 3.4 meg/sec. The model I am using is an order0 but there
is only a little more than .1 second increase in time over 4meg of input to
go to order1.

Thank you all for you time
Randy McNabb

rep_movsd

2005-01-29, 8:55 pm

Randy McNabb wrote:
> "Matt Mahoney" <matmahoney@yahoo.com> wrote in message
> news:1106061796.577712.116570@c13g2000cwb.googlegroups.com...
help.[color=darkred]
rather[color=darkred]
> Hi Matt,
> My compressor doesn't have to be fast . I am working on it just to
see
> how fast I can get it. I came up with new algorithms of the encoder,
file
> i/o, and the model. I was just wondering how fast was fast. the 2
meg/sec
> was from source file to encoded file. Just the encoder and writing
to file
> is running around 3.4 meg/sec. The model I am using is an order0 but
there
> is only a little more than .1 second increase in time over 4meg of
input to
> go to order1.
>
> Thank you all for you time
> Randy McNabb

As far as the file I/O goes I would suggest using memory mapped IO on
any platform. It is atleast 30% faster than normal file APIs. However
IO would hardly be your bottleneck i guess!!
You can check out the range coder available in the PPMD source code
for a blazingly simple arith encoder.

Randy McNabb

2005-01-31, 3:55 am

"rep_movsd" <rep.movsd@gmail.com> wrote in message
news:1107034433.826033.303020@f14g2000cwb.googlegroups.com...
>
> Randy McNabb wrote:
> help.
> rather
> see
> file
> meg/sec
> to file
> there
> input to
>
> As far as the file I/O goes I would suggest using memory mapped IO on
> any platform. It is atleast 30% faster than normal file APIs. However
> IO would hardly be your bottleneck i guess!!
> You can check out the range coder available in the PPMD source code
> for a blazingly simple arith encoder.
>
Thanks,
I have been doing much the same as the range coders I have seen do. I xor
the high and low to determine which bits to write. I also use the
difference between high and low to determine the last possible underflow bit
so I only have to test one bit position for underflow. I am able to
determine what to write without checking every bit position, do all the
shifts at one time and write the data in big chunks.

I must say thanks to all the people of this group as I have found more
useful information through this group than I have through the any other
source on the net.

Many thanks,
Randy McNabb

Christian Siebert

2005-01-31, 8:55 am

> As far as the file I/O goes I would suggest using memory mapped IO on
> any platform. It is atleast 30% faster than normal file APIs.
This is what I read very often but this is indeed not true. My own
measurements (swap disabled, reboot between tests, urandom gen. file):

|| Sun-Blade-100, SunOS 5.8 || AMD Athlon, Linux 2.4.22nptl
|| 512MB RAM, 256MB file || 1GB RAM, 512MB file
-------------------++------+--------+-------++------+--------+------
|| user | system | total || user | system | total
-------------------++------+--------+-------++------+--------+------
block wise, ANSI || 3.65 | 8.18 | 44.14 || 0.51 | 2.34 | 24.79
block wise, normal || 1.52 | 21.08 | 44.82 || 0.13 | 6.24 | 24.17
one-time, normal || 0.00 | 10.10 | 20.32 || 0.00 | 3.38 | 23.29
one-time, mmap || 1.44 | 7.66 | 28.22 || 0.73 | 1.30 | 27.69

As you can see (one-time, normal <-> one-time, mmap), normal file
operation are always faster than memory mapped I/O in my test cases!
Only if you choose smaller buffers (e.g. 512 bytes) for normal file I/O,
the used time increases and may become worse depending on your
architecture/OS.
Therefore my suggestion is to use ANSI file I/O everywhere because it is
the most available/compatible way of accessing files. If you worry about
performance than read the complete file in one step and you'll get your
data even faster than with memory mapped I/O.

Chris

buyanovsky@attbi.com

2005-02-03, 8:55 pm

Below you may compare you speed with commercial application.

The compressor was designed for compression of 12bit gray 3D image
datasets (CT data). The combined speed of Encoder and Predictor is
38.748.736 byte per second on Athlon 64 (2.4 GHz). It uses the
adaptive arithmetic encoder (true entropy encoding quality) and
tri-linear predictor with an error prediction correction feed back.

Best regards,
George

buyanovsky@attbi.com

2005-02-03, 8:55 pm

Sponsored Links