From: dcarr@gandalf.ca (Dave Carr)
Subject: Re: V.42bis over V.120? (was Re: Can V.32bis or V.42bis be 'faked' by
Organization: Gandalf Data Ltd.
Distribution: na
Date: Thu, 7 Jan 1993 21:18:20 GMT

In <uiivr48@rhyolite.wpd.sgi.com> vjs@rhyolite.wpd.sgi.com (Vernon Schryver) writes:

>In article <C0Gn8s.721@world.std.com>, ariel@world.std.com (Robert L Ullmann) writes:
>> ...
>> It takes a _lot_ of peak-power CPU to keep the output going at
>> 64kpbs at a high compression ratio, even if the _average_ CPU
>> is small.


>Is it a big deal for an 8088 or even 68000 in a modem doing v.42bis?
>What about a 1000 SPEC multiprocessor?

Here some info.  I hope it doesn't sound like an advertisement or else
I may get flamed.

We have found that the 80960CA processor to be very cost effective in our
bridge.  We have had LZW type code running in the LAB at 384 Kbps, no
problem.  Also, STAC has an optimized version of their LZS ( a LZSS
variant) that runs up to 2.048 Mbps.

We have decided that the extra $60 bucks for the processor (over a 68K)
is well worth the price.

We will release this month a new compression algorithm on our 960 based
bridge.  This is an LZ77 compressor with an arithmetic back end.  This
is far moree CPU intensive (4X at least) of LZW, but we can keep dual
64 Kbps links full.

What it really comes down to is: How much compression do you want/need.
Fully 90% of our CPU is dedicated to compression.  Our goal was to provide
the BEST compression (who cares if we already have the best compression
bridge :-). 

The time to FTP a file over our bridge will be within a few percent of 
ZIPping the file before FTPing it.

>I guess the memory requirements for all reasonable compress schemes
>are in the few KByte/data stream range.  Is that a good guess?

Again, a compression ratio tradeoff.  Typical implementations of V.42 bis
take 32K total.  STAC requires 14K.  Ours, 128K.  

>I assume it's somewhere in between, but where?  How many cycles per
>byte output is "a _lot_"?  With familiar, various assumptions about the
>character of the data stream, what are the average, median, and peak
>cycles/byte for
>    - v.42bis with the various dictionary sizes

Dictionary size not really a factor as long as hash table grows in
proportion (if your using a trie, it becomes a factor).  LZW based 
algorithms have 2 phases.  The parsing of the longest match, and the
dictionary update time.  For V.42 bis, the dictionary update is a 
fixed cost per output symbol.  A variable number of characters from the
newly matched string are added to the previous string.  The parsing of
the longest match varies with the compression ratio.  

The number of cycles per _input_ symbol DECREASES with an increase in the
compression ratio.  The number of cycles per _output_ symbol will
increase non-linearly with compression ratio.  With a good hash, the
longest match algorithm will be about 1.1 memory references per input 
symbol. 

>    - splay trees

Why bother.  Get a real processor.

>    - LZW

See V.42 bis.

Here's a couple of others:

- LZ77 Algorithms: STAC, LZSS

The big tradeoff here is history buffer and hash table memory versus speed.
STAC uses a 2K buffer, 8K of hash table from what I figure.  That seems
about right in terms of optimal ratio between the two.  Info-ZIP, Freeze,
HPACK archivers have at least 2:1 to 4:1 ratio between the hash and history.
Marginal speed improvements are gained with a larger ratio.

LZ77 is one big tradeoff.  All the CPU cycles are spent in the encoder. 
To gaurantee throughput, the encoder must limit the number of searches in the
history, with a coreesponding drop in compression.

The secret here is a good hash function, and a good string match algorithm.
Freeze and ZIP are two good examples.

- LZ77 + Huffman

Popular in archivers to improve the compression ratio.  Used by ZIP, Freeze,
and a few others.  Not that bad in terms of speed, but not applicable to
Wide Area Links.  Archivers have a chance to examine and block the data,
and then proceed to encode it.  An adaptive huffman algorithm could be
used, but will end up about as slow as an arithmetic backend, so why lose
compression efficiency.

- LZ77 + Arithmetic

See LZA or HPACK archivers.  Significantly slower than LZSS or LZ77+Huffman.
The arithmetic backend is quite CPU intensive.  However, adaptive model is
possible.  We use this method because we have a superscalar CPU, and enough
of it to handle the speed.
Xref: sparky comp.dcom.isdn:1096 comp.protocols.ppp:1045