Subject: [hybi] permessage-deflate performance tuning statistics

From: Peter Thorson <[email-masked]>
Date: Tue, 15 Oct 2013 13:34:13 -0500

Hi all,

I've been doing a bit of research and testing on the compression performance and memory usage of permessage-deflate on WebSocket like workloads. I plan to write about this with more final numbers once the spec is official, but some of the intermediate results and tools may be of interest to this group during the standardization process so I'm sharing some of those notes here.

Some highlights:
- Permessage-deflate offers significant bandwidth savings.
- How the extension performs depends greatly on the type of data that is being compressed and the compression settings given to deflate.
- Settings that work well for HTTP and the zlib/permessage-deflate defaults are inefficient for some common WebSocket workflows.
- The two parameters presently in the draft specification both provide significant and meaningful options for tuning compression performance for those workflows. Implementations (especially browsers) are greatly encouraged to support all options.

Details & Methods:

My goal is to explore a number of the settings offered by deflate and determine what effect they have on compression performance, as well as CPU/memory usage. To this end I have written a tool (https://github.com/zaphoyd/ws-pmce-stats) that will produce a report of compression related statistics when fed a transcript of messages.

The first workflow I have explored in detail is a WebSocket service that uses a JSON based protocol to deliver short streaming updates. My some of my sample data is present in the datasets folder of the above git repository. Some examples include a mock chat service with data seeded from publicly logged mediawiki IRC channel and a mock stock ticker service with data seeded with historical stock quote data.

I explored the effects of the context takeover and window bits settings from the permessage-deflate draft spec as well as a few zlib settings that can be unilaterally specified without any extension negotiation. Some, but not all of these, are presently exposed in higher level languages that use zlib as their underlying compression library. I looked at two of these settings in particular, the "Compression Level" and the "Memory Level". The former affects speed vs compression ratio, the latter memory usage vs compression ratio.

Preliminary results for the JSON short message service workflow:

Context Takeover
================
Allowing context takeover drastically improves compression ratios. With other stats at defaults, no_context_takeover achieves a compression ratio of 0.84, with takeover 0.30. This is a significant gain. Note: this gain comes at a fairly high cost. Enabling context takeover requires a separate context to be maintained for every connection, rather than fixed number for all connections.

Window Bits
===========
Window bits has a sizable but well distributed effect on ratios. It has a significant effect on memory usage though. With all other stats at defaults:
window bits = compression ratio / buffer size per connection
08 = 0.510 / 1+128=129KiB
09 = 0.510 / 2+128=130KiB
10 = 0.435 / 4+128=132KiB
11 = 0.384 / 8+128=136KiB
12 = 0.353 / 16+128=144KiB
13 = 0.330 / 32+128=160KiB
14 = 0.315 / 64+128=192KiB
15 = 0.304 / 128+128=256KiB
Reducing window bits from the default (15) to 11 provides an 8% reduction in compression but nearly a 50% savings in per connection memory usage. Reduced window bits to very small values (8-9) also increases compression runtime by 40-50%. 10 Is less slow, 11+ appear to all be about the same speed.

Compression Level
=================
Compression level does not have a material impact on performance or ratios for this workflow.

Memory Level
============
Memory level does not have a significant impact on compression ratios. A value of 9 produces the ratio 0.304 and a value of 1 produces the ratio 0.307. It does affect memory usage and compression speed however:
mem_level value = runtime / memory usage
1 = 13.05ms / 128+1=129KiB
2 = 10.41ms / 128+2=130KiB
3 = 10.15ms / 128+4=132KiB
4 = 8.18ms / 128+8=136KiB
5 = 7.63ms / 128+16=144KiB
6 = 7.69ms / 128+32=160KiB
7 = 7.92ms / 128+64=192KiB
8 = 7.69ms / 128+128=256KiB
9 = 7.84ms / 128+256=386KiB

All of the stats above show the effects of changing one parameter in isolation. Additional gains, especially with respect to memory usage per connection can be had by combinations of parameters. Many of the speed, compression, and memory effects of parameters are dependent on each other. Two nice balances of all factors for the JSON short message service data set (vs defaults) are something like..

context-takeover=on
window bits=11
memory level=4
This provides memory usage of 16KiB/connection vs 256KiB, has no runtime speed penalty, and achieves a 0.384 vs 0.304 compression ratio.

context-takeover=on
window bits=11
memory level=1
This provides memory usage of 5KiB/connection vs 256KiB, runs ~15% slower, and achieves a similar 0.385 vs 0.304 compression ratio.

The ws-pmce-stats tool can help you plug in values and get a sense for which combinations of settings are optimal for your traffic mix. In general I have found that the shorter your messages, the less you benefit from high window bit and memory level values. If you routinely send WebSocket messages with payloads in the high hundreds of KB or MBs you will benefit from higher values for memory level and window bits. If you have extremely limited memory, no context takeover will allow fixed memory usage for all connections. Its price is heavy for small messages & JSON protocols, but less problematic for large ones. I've found that 11 window bits and compression memory level 4 is still quite effective even up to message payloads of ~200KB.

I'd love to hear any feedback anyone has about the methods or results. I am particularly interested in collecting more sample WebSocket workflows. I haven't run any numbers for binary connections yet. I'd love to hear details about other workflows that might have different properties than the ones studied here so far, especially if you have sample transcripts.

I'd also be interested in any feedback on the ws-pmce-stats program. Is something like this useful to anyone else? It meets my needs right now, but I have a few ideas of how to expand it (binary message support, other compression algorithms, machine readable output) if it sounds useful to others.

---

From: Joakim Erdfelt <[email-masked]>
Date: Tue, 15 Oct 2013 11:48:52 -0700

Nice.  Was meaning to do this myself, but just haven't had the free time to
devote to it.
I imagine that the results of this will serve the community well.

Is your experimental data testing if fragmentation has any impact? (lots of
smaller fragments for a larger message, commonly seen in streaming
behaviors)

Are you testing just a single type of data on the connection?
Are you testing multiple types of data during the same connection, such as
a theoretical protocol that has markup + metadata + and pre compressed
media?

--
Joakim Erdfelt <[email-masked]>
webtide.com <http://www.webtide.com/> - intalio.com/jetty
Expert advice, services and support from from the Jetty & CometD experts
eclipse.org/jetty - cometd.org

On Tue, Oct 15, 2013 at 11:34 AM, Peter Thorson <[email-masked]>wrote:

> Hi all,
>
> I've been doing a bit of research and testing on the compression
> performance and memory usage of permessage-deflate on WebSocket like
> workloads. I plan to write about this with more final numbers once the spec
> is official, but some of the intermediate results and tools may be of
> interest to this group during the standardization process so I'm sharing
> some of those notes here.
>
> Some highlights:
> - How the extension performs depends greatly on the type of data that is
> being compressed and the compression settings given to deflate.
> - Settings that work well for HTTP and the zlib/permessage-deflate
> defaults are inefficient for some common WebSocket workflows.
> - The two parameters presently in the draft specification both provide
> significant and meaningful options for tuning compression performance for
> those workflows. Implementations (especially browsers) are greatly
> encouraged to support all options.
>
> Details & Methods:
>
> My goal is to explore a number of the settings offered by deflate and
> determine what effect they have on compression performance, as well as
> CPU/memory usage. To this end I have written a tool (
> https://github.com/zaphoyd/ws-pmce-stats) that will produce a report of
> compression related statistics when fed a transcript of messages.
>
> The first workflow I have explored in detail is a WebSocket service that
> uses a JSON based protocol to deliver short streaming updates. My some of
> my sample data is present in the datasets folder of the above git
> repository. Some examples include a mock chat service with data seeded from
> publicly logged mediawiki IRC channel and a mock stock ticker service with
> data seeded with historical stock quote data.
>
> I explored the effects of the context takeover and window bits settings
> from the permessage-deflate draft spec as well as a few zlib settings that
> can be unilaterally specified without any extension negotiation. Some, but
> not all of these, are presently exposed in higher level languages that use
> zlib as their underlying compression library. I looked at two of these
> settings in particular, the "Compression Level" and the "Memory Level". The
> former affects speed vs compression ratio, the latter memory usage vs
> compression ratio.
>
> Allowing context takeover drastically improves compression ratios. With
> other stats at defaults, no_context_takeover achieves a compression ratio
> of 0.84, with takeover 0.30. This is a significant gain. Note: this gain
> comes at a fairly high cost. Enabling context takeover requires a separate
> context to be maintained for every connection, rather than fixed number for
> all connections.
>
> Window Bits
> ===========
> Window bits has a sizable but well distributed effect on ratios. It has a
> significant effect on memory usage though. With all other stats at defaults:
> Reducing window bits from the default (15) to 11 provides an 8% reduction
> in compression but nearly a 50% savings in per connection memory usage.
> Reduced window bits to very small values (8-9) also increases compression
> runtime by 40-50%. 10 Is less slow, 11+ appear to all be about the same
> speed.
>
> Compression Level
> =================
> Memory level does not have a significant impact on compression ratios. A
> value of 9 produces the ratio 0.304 and a value of 1 produces the ratio
> 0.307. It does affect memory usage and compression speed however:
> All of the stats above show the effects of changing one parameter in
> isolation. Additional gains, especially with respect to memory usage per
> connection can be had by combinations of parameters. Many of the speed,
> compression, and memory effects of parameters are dependent on each other.
> Two nice balances of all factors for the JSON short message service data
> set (vs defaults) are something like..
>
> context-takeover=on
> window bits=11
> memory level=4
> This provides memory usage of 16KiB/connection vs 256KiB, has no runtime
> speed penalty, and achieves a 0.384 vs 0.304 compression ratio.
>
> context-takeover=on
> window bits=11
> memory level=1
> This provides memory usage of 5KiB/connection vs 256KiB, runs ~15% slower,
> and achieves a similar 0.385 vs 0.304 compression ratio.
>
> The ws-pmce-stats tool can help you plug in values and get a sense for
> which combinations of settings are optimal for your traffic mix. In general
> I have found that the shorter your messages, the less you benefit from high
> window bit and memory level values. If you routinely send WebSocket
> messages with payloads in the high hundreds of KB or MBs you will benefit
> from higher values for memory level and window bits. If you have extremely
> limited memory, no context takeover will allow fixed memory usage for all
> connections. Its price is heavy for small messages & JSON protocols, but
> less problematic for large ones. I've found that 11 window bits and
> compression memory level 4 is still quite effective even up to message
> payloads of ~200KB.
>
> I'd love to hear any feedback anyone has about the methods or results. I
> am particularly interested in collecting more sample WebSocket workflows. I
> haven't run any numbers for binary connections yet. I'd love to hear
> details about other workflows that might have different properties than the
> ones studied here so far, especially if you have sample transcripts.
>
> I'd also be interested in any feedback on the ws-pmce-stats program. Is
> something like this useful to anyone else? It meets my needs right now, but
> I have a few ideas of how to expand it (binary message support, other
> compression algorithms, machine readable output) if it sounds useful to
> others.
> _______________________________________________
> hybi mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/hybi
>

---

From: Tobias Oberstein <[email-masked]>
Date: Tue, 15 Oct 2013 12:01:43 -0700

Hi Peter,

this is fantastic empirical evidence - very much appreciated!

As a first concrete action from this, I'll take the following issue to the Python
community:

"Expose the 'Memory Level' knob on the Python zlib wrapper"

Cheers,
Tobias
 
> -----Ursprüngliche Nachricht-----
> Von: [email-masked] [mailto:[email-masked]] Im Auftrag von
> Peter Thorson
> Gesendet: Dienstag, 15. Oktober 2013 20:34
> An: [email-masked]
> Betreff: [hybi] permessage-deflate performance tuning statistics
> 
> Hi all,
> 
> is official, but some of the intermediate results and tools may be of interest
> to this group during the standardization process so I'm sharing some of those
> notes here.
> 
> Some highlights:
> - Settings that work well for HTTP and the zlib/permessage-deflate defaults
> are inefficient for some common WebSocket workflows.
> CPU/memory usage. To this end I have written a tool
> (https://github.com/zaphoyd/ws-pmce-stats) that will produce a report of
> The first workflow I have explored in detail is a WebSocket service that uses a
> JSON based protocol to deliver short streaming updates. My some of my
> sample data is present in the datasets folder of the above git repository.
> Some examples include a mock chat service with data seeded from publicly
> logged mediawiki IRC channel and a mock stock ticker service with data
> seeded with historical stock quote data.
> 
> I explored the effects of the context takeover and window bits settings from
> the permessage-deflate draft spec as well as a few zlib settings that can be
> unilaterally specified without any extension negotiation. Some, but not all of
> these, are presently exposed in higher level languages that use zlib as their
> underlying compression library. I looked at two of these settings in particular,
> the "Compression Level" and the "Memory Level". The former affects speed
> vs compression ratio, the latter memory usage vs compression ratio.
> 
> other stats at defaults, no_context_takeover achieves a compression ratio of
> 0.84, with takeover 0.30. This is a significant gain. Note: this gain comes at a
> fairly high cost. Enabling context takeover requires a separate context to be
> maintained for every connection, rather than fixed number for all
> connections.
> 
> Window Bits
> ===========
> Reducing window bits from the default (15) to 11 provides an 8% reduction in
> compression but nearly a 50% savings in per connection memory usage.
> value of 9 produces the ratio 0.304 and a value of 1 produces the ratio 0.307.
> It does affect memory usage and compression speed however:
> compression, and memory effects of parameters are dependent on each
> other. Two nice balances of all factors for the JSON short message service
> data set (vs defaults) are something like..
> 
> context-takeover=on
> window bits=11
> memory level=4
> The ws-pmce-stats tool can help you plug in values and get a sense for which
> combinations of settings are optimal for your traffic mix. In general I have
> found that the shorter your messages, the less you benefit from high
> connections. Its price is heavy for small messages & JSON protocols, but less
> problematic for large ones. I've found that 11 window bits and compression
> memory level 4 is still quite effective even up to message payloads of
> ~200KB.
> 
> I'd love to hear any feedback anyone has about the methods or results. I am
> particularly interested in collecting more sample WebSocket workflows. I
> haven't run any numbers for binary connections yet. I'd love to hear details
> about other workflows that might have different properties than the ones
> studied here so far, especially if you have sample transcripts.
> 
> something like this useful to anyone else? It meets my needs right now, but I
> have a few ideas of how to expand it (binary message support, other

---

From: Peter Thorson <[email-masked]>
Date: Tue, 15 Oct 2013 15:50:17 -0500

On Oct 15, 2013, at 13:48 , Joakim Erdfelt <[email-masked]> wrote:

> Nice.  Was meaning to do this myself, but just haven't had the free time to devote to it.
> Is your experimental data testing if fragmentation has any impact? (lots of smaller fragments for a larger message, commonly seen in streaming behaviors)

I have not explicitly looked at fragmentation yet. Theoretically...

For cases with context takeover I'd assume a Z_SYNC_FLUSH for each outgoing fragment to align on a byte boundary. In which case, fragmented compression will behave exactly as if you had sent the content in multiple messages but worse than if you had sent it in one un-fragmented message.

For cases without context takeover it would get more complicated, do you retain context between fragments? If so that negates all of the memory benefits of no-context-takeover… This needs to be clarified in the permessage-compress draft spec.

> Are you testing multiple types of data during the same connection, such as a theoretical protocol that has markup + metadata + and pre compressed media?

The ws-pmce-stats utility takes as input right now a line delimited input and considers each line one message. Other than the present restriction of text messages only (not a fundamental restriction, I just haven't written something that handles binary input yet) you can feed any sort of data to the application and get stats. Supporting binary and/or fragmented messages will require a different and more complicated input scheme (probably eat a canned WebSocket feed rather than a unix-like line delimited stream). WebSocket++ will do offline decoding of a stream like that so it should be easy to set up, but not something I'll do unless someone would actually use it. =)

The data I've tested with has been "a single type" in the sense that all messages belong to the same JSON protocol. There are different types of messages though. For example the chat data set starts off with a few setup messages that are largish, including a channel welcome message and full list of channel participants. Future messages are small (individual chat messages going back and forth). The individual messages are also mixed type. A chat message for example has a fixed length numeric timestamp, a username, and an arbitrary length field of english text. The stock ticker example is more uniform, with more numbers and no english. All the JSON data has whitespace removed as I am trying to model as accurately as possible what might really be sent over the wire. For the most part the exact composition of the JSON fields doesn't make as much of a difference as the memory related parameters. Text in general compresses well.

A few things I've done that deviate a bit from the above examples:

I've tried the stock ticker JSON data in two variants, one that uses text labels (larger and more redundant, but more human readable) the other where the order of values in an array determines which field it is. The value with text labels compressed better (13.769KB -> 3.428KB, ratio=0.248965) but not quite better enough (7.417KB -> 2.84KB, ratio=0.382904) to have a smaller wire size . Labels + compression is more than twice as small as no labels without compression however.

I've tried larger chunks of non-JSON text data, like sending entire Project Gutenberg books in a single message. They compress well but not as well as JSON 0.4-0.5 ratios rather than 0.2-0.4. The larger messages are a bit more sensitive to window bits and compress memory level, but not *that* much. 4 is just fine, 8 (default) is overkill.

It would definitely be worth experimenting with a connection that multiplexes small messages with large ones, say for the example case where you are delivering new documents over the WebSocket connection as we'll as small updates. Getting some tests with binary/compressed data intermixed would also be useful it sounds. Does anyone have any sample data for such a connection?

> webtide.com - intalio.com/jetty
> On Tue, Oct 15, 2013 at 11:34 AM, Peter Thorson <[email-masked]> wrote:
> Hi all,
>

---

From: Adam Rice <[email-masked]>
Date: Thu, 17 Oct 2013 15:53:35 +0900

Very interesting results, thank you!

On 16 October 2013 05:50, Peter Thorson <[email-masked]> wrote:
>
> For cases without context takeover it would get more complicated, do you
> retain context between fragments? If so that negates all of the memory
> benefits of no-context-takeover… This needs to be clarified in the
> permessage-compress draft spec.
>

Context *is* retained between frames. This is the meaning of "permessage"
in "permessage-compression". The wording in the spec could maybe be
clearer. I was confused about this myself for a long time.

The consequence is that you are not guaranteed to need less compression
contexts than connections, unless you know something about the traffic you
are handling. Specifically, if you know all your messages will be smaller
than the size of the compression context, then you know you can save memory
by only keeping one compression context around. So a browser or a proxy
cannot be certain to benefit from no-content-takeover, but a server can
usefully use it on applications where it makes sense.

> It would definitely be worth experimenting with a connection that
> multiplexes small messages with large ones, say for the example case where
> you are delivering new documents over the WebSocket connection as we'll as
> small updates. Getting some tests with binary/compressed data intermixed
> would also be useful it sounds. Does anyone have any sample data for such a
> connection?
>
>
An interesting property of valid UTF-8 data is that given a sufficiently
large quantity, it is always compressible. Binary data, on the other hand,
is quite likely to have had compression applied to it already and be
incompressible by a generic algorithm like deflate. So a WebSocket with a
mixture of text and binary messages is challenging to compress effectively
and efficiently.

Thanks,
Adam Rice

---

From: Tobias Oberstein <[email-masked]>
Date: Thu, 17 Oct 2013 01:11:15 -0700

> "Expose the 'Memory Level' knob on the Python zlib wrapper"

http://bugs.python.org/issue19278
http://bugs.python.org/issue19277