Subject: Re: [rohc] (deflate) fixed huffman vs. dynamic huffman

From: "West, Mark" <[email-masked]>
Date: Thu, 11 Aug 2005 12:57:36 +0100

Cristian,

In part I guess it could, in part, be a CPU issue, but there are two other
aspects to consider:

i) message compression with available history

Where you are compressing a message based on historical context, it is
possible to achieve better than 10:1 compression even with static codes.
In this case, because of the small size of the messages, the ~60 bytes it
takes to encode the dynamic Huffman codes massively outweighs the saving.

ii) bytecode complexity

Have you tried to write the dynamic Huffman decompression program?

:-)

It *can* be done (UDVM is Turing complete), but it's very definitely
non-trival.

In terms of acceptable CPU time, this is highly dependent upon
circumstances.  However, the simple answer is always, 'as fast as
possible'!  Since SigComp is there to reduce latency, saving a few 10's of
ms in serialisation delay by adding 100's of ms of processing is a bad
bargain.  I'd expect decompression times to be well under 1ms on a desktop
PC...

Cheers,

Mark.

--
Mark A. West, Senior Consultant Engineer
Roke Manor Research Ltd., Romsey, Hants.  SO51 0ZN
Phone +44 (0)1794 833311   Fax  +44 (0)1794 833433

On Thu, 11 Aug 2005, Cristian CONSTANTIN wrote:

> Date: Thu, 11 Aug 2005 11:45:27 +0100
> From: Cristian CONSTANTIN <[email-masked]>
> To: [email-masked]
> Subject: [rohc] (deflate) fixed huffman vs. dynamic huffman
>
> hi!
>
> first of all a question I had in mind for a long time; are the udvm
> impl. of decomp. algorithms (deflate, lz, etc) published in the
> draft-ietf-rohc-sigcomp-user-guide-02.txt intended for real world usage?
>
> now, why using fixed huffman codes and not dynamic ones?
> for example, compressing a real sip packet with both static and
> dynamic codes leads to:
>
> uncompressed size: 1111 bytes
> static huffman codes: 762 bytes (68% of the original)
> dynamic huffman codes: 636 bytes (57% of the original)
>
> so, the one compressed with dynamic huffman codes is sensible smaller;
> is the dynamic codes one not used bec. it would be more intensive
> cpu-wise?
> by the way, what would be an acceptable cpu time spent for decompressing
> an
> sip compressed packet using an udvm decompresor? (ms, hundreds of us,
> tenths of us?)
>
> bye now!
> cristian
> --
>  _          | There are many people who use UNIX or Linux
> (_'_        | who IMHO do not understand UNIX.
>   (_'rist   |              --David Korn
> GPG public key at wwwkeys.de.pgp.net
>
>
_______________________________________________
Rohc mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/rohc

---

From: Cristian CONSTANTIN <[email-masked]>
Date: Thu, 11 Aug 2005 14:24:27 +0200

> Have you tried to write the dynamic Huffman decompression program?

cristian: even though it's not yet ready, I'm working on it...
I have found contrib/puff/puff.c from the zlib-1.2.2 distribution to be
really useful in the process. I have thought someone has already done it
and tried it against the fixed huffmann codes one.

> bargain.  I'd expect decompression times to be well under 1ms on a desktop

cristian: thanks, but does anyone have some real life data here?

again, thanks a lot.
bye now!
cristian

---

From: Herve Siegrist <[email-masked]>
Date: Thu, 11 Aug 2005 15:37:30 +0200

Cristian CONSTANTIN wrote:

Cristian,

ii) bytecode complexity

:-)

FYI, I do have a bench which goes through typical SIP sequences
(Invite, Trying, Ringing, Ok, Ack, Bye, Ok) in loop using dynamic (in
the RFC 3321 way, not dynamic huffman)
deflate with SIP dictionary and a fairly standard set of messages
typical of a live SIP transaction, and I am getting around 3000
messages per second overall, accounting for both the compression and
decompression times of these messages, all that on a 3GHz PC running
RedHat Fedora Core 3.

As far as using dynamic huffman decompression, I'm afraid I'm having
nightmares just thinking about writing the bytecode which goes with
it... I'm crossing my fingers everyday, hoping my boss will not want
that one...

Herve.

again, thanks a lot.
bye now!
cristian

---

From: Cristian CONSTANTIN <[email-masked]>
Date: Thu, 11 Aug 2005 18:12:10 +0200

> bargain.  I'd expect decompression times to be well under 1ms on a desktop

cristian: I think there was a misunderstanding; I was talking about the
following orders of magnitude (in decreasing order):

- ms (milisec)
- hundreds of us (hundreds of microsec)
- tens of us (tens of microsec)

you suggesting hundreds of microsec then?

thanks.
cristian

---

From: Adam Roach <[email-masked]>
Date: Thu, 11 Aug 2005 11:17:25 -0500

>cristian: thanks, but does anyone have some real life data here?

A lot of the answer to this question depends on the platform you're on. 
(For example, my profiling showed that about 20% of the processing time 
used by my SigComp stack was performing SHA-1 hashing; on a Sparc 
processor, this jumps to nearly 30% -- hardly surprising, since the 
Sparc lacks rotate instructions).

In any case, on a low-speed ARM processor (something in the range of 10 
to 20 MHz), using Deflate on approximately 1000 byte messages, I was 
seeing decompression times on the order of 200 ms. On a server, yes, 
this ended up being something more in the hundreds-of-microseconds 
range; we weren't as concerned about characterizing that side of the 
connection, so that number didn't stick with me.

(To address Mark's comment, this 200 ms processing on the terminal plus 
the negligible compression latency introduced on the network server was 
saving us about 900 ms of radio latency, so the trade-off was pretty 
obvious).

/a