Delta compression

[mike....@gmail.com]

I've read through much of the introductory documentation and this library (specifically the documentation) is impressive.

There was a feature I've been looking for that seems impossible to implement in most of these serialization libraries.

That is delta compression.

Delta compression is a pretty core network optimization in games.

If you're unfamiliar with the concept a good overview is provided here:

http://fabiensanglard.net/quake3/network.php

At least one other person wanted a similar feature from protobuf.

https://groups.google.com/forum/#!topic/protobuf/21jobPMlLVw

With protobuf you could approximate this using all optional fields.

But it was incredibly difficult to construct properly.

[Scott Nicol]

Delta is a core optimization in any system that has frequent updates. It would be a nice addition to build-in, but you could DIY. Just add a bitmask field to know what is set in the struct, then use the packing algorithm to get rid of repeated 0's due to unset fields.

--
Scott Nicol
scott...@gmail.com

--
You received this message because you are subscribed to the Google Groups "Cap'n Proto" group.
To unsubscribe from this group and stop receiving emails from it, send an email to capnproto+...@googlegroups.com.
Visit this group at http://groups.google.com/group/capnproto.

[Kenton Varda]

Hi Mike,

It should be easy to implement some sort of delta compression using the Any API (`capnp/any.h`), which provides un-typed access to the contents of a message. You could write code which iterates over two parallel messages and:

- XORs data fields (so that unchanged fields become zero).

- Nulls out pointers when the pointed-to objects are identical (or if you need null pointers as part of your protocol, use some other special sentinel like an empty-struct pointer).

Then send the message in Cap'n Proto's "packed" format, which is a very fast way to compress out zeros. On the receiving end, again use the Any API to unpack.

Keep in mind that Cap'n Proto is not really appropriate for storing the in-memory representation of your game state that is modified over time on the server. Because of the arena-style allocation that essentially releases no memory until the entire message is destroyed, such an approach would leak memory over time. Instead, Cap'n Proto is appropriate for preparing individual messages, where you build the whole message just before sending. But I think for this delta compression technique, you need to keep a copy of the state at each tick anyway, in order to later compare against to perform the compression. So keep the copy in Cap'n Proto format, but the original in native format.

-Kenton

[Michael Marcin]

The Any API is quite interesting, it might be made to work.

Game state snapshots are usually generated at the end of a frame from scratch so that fits well.

There is one other bit of added complexity which is the client PVS (potentially visible set) filtering.

Essentially after building the state of the whole game the server filters it per client which has several benefits:

 - greatly reduces bandwidth requirements (changes the client won't see don't get sent)

 - reduces the ability to cheat (memory inspection or packet sniffing can't reveal information that is never sent)

I suppose this method can handle this case as well by zeroing out any objects excluded from the PVS on the server in the per client copy of the capnproto state object.

Why do you handle pointers differently?

Is it to allow for identical objects to show up at different positions in different capnproto snapshots?

[Andrew Lutomirski]

On Tue, May 26, 2015 at 3:02 PM, Kenton Varda <ken...@sandstorm.io> wrote:
> Hi Mike,
>
> It should be easy to implement some sort of delta compression using the Any
> API (`capnp/any.h`), which provides un-typed access to the contents of a
> message. You could write code which iterates over two parallel messages and:
> - XORs data fields (so that unchanged fields become zero).
> - Nulls out pointers when the pointed-to objects are identical (or if you
> need null pointers as part of your protocol, use some other special sentinel
> like an empty-struct pointer).

Alternatively, one could canonicalize the message :)

I really need to finish my canonicalizer implementation.

--Andy

[Michael Marcin]

I'm not sure what you mean by 'canonicalize the message' could you link me to some information?

Thanks

[Andrew Lutomirski]

On Tue, May 26, 2015 at 6:27 PM, Michael Marcin <mike....@gmail.com> wrote:
> I'm not sure what you mean by 'canonicalize the message' could you link me
> to some information?

https://capnproto.org/encoding.html#canonicalization

--Andy

[Kenton Varda]

On Tue, May 26, 2015 at 5:17 PM, Michael Marcin <mike....@gmail.com> wrote:

The Any API is quite interesting, it might be made to work.

Game state snapshots are usually generated at the end of a frame from scratch so that fits well.

There is one other bit of added complexity which is the client PVS (potentially visible set) filtering.

Essentially after building the state of the whole game the server filters it per client which has several benefits:

 - greatly reduces bandwidth requirements (changes the client won't see don't get sent)

 - reduces the ability to cheat (memory inspection or packet sniffing can't reveal information that is never sent)

I suppose this method can handle this case as well by zeroing out any objects excluded from the PVS on the server in the per client copy of the capnproto state object.

I think what you want to do here is instead of running the delta compression over the entire game state at once, run it on an entity-by-entity basis, and don't even add entities which aren't visible to the per-client messages.

 

Why do you handle pointers differently?

Is it to allow for identical objects to show up at different positions in different capnproto snapshots?

Yes, objects can appear in any order.

Andy's suggestion of canonicalization would force them to appear in a well-defined order. However, if the two object trees have different shapes -- e.g. some objects have been added or removed -- then that could cause lots of objects to be mis-aligned, defeating the delta-compression. So, I don't think that actually helps you; I think you need to walk the tree, not raw bytes.

-Kenton