4 ms·

When doing ad-hoc space optimized encodings, it’s usually a good idea to compare the compress+decompress speed in addition to the resultant size against just co

When doing ad-hoc space optimized encodings, it’s usually a good idea to compare the compress+decompress speed in addition to the resultant size against just compressing the data. This may win on one-off encodings of strings within an RPC, but the compression mechanism probably wins on the overall RPC message unless the message is very small & you can’t build a more optimized baseline dictionary for small messages. It’s really hard to actually beat something like zstd with these ad-hoc compression since both the compressed size will be bigger than what zstd produces with a dictionary or on larger messages without a dictionary AND the speed of a round trip through zstd is likely faster.

chaokunyang 3y ago
It's not designed to beat zstd, those are used for different scenarios. zstd is used for data compression, the meta string encoding here is used for meta meta encoding. Meta data here are classname/fieldname/packagename/namespace/path/modulename mostly. For such small string, any statistical compression won't have a smaller size.
- vlovich123 3y ago
  > For such small string, any statistical compression won't have a smaller size That is a statement you can make, but you have to actually demonstrate this is true against zstd's --train mechanism [1] which generates a more optimized "small string" dictionary based on representative training data precisely for this use-case. [1] https://github.com/facebook/zstd/blob/dev/programs/zstd.1.md https://github.com/facebook/zstd/blob/dev/programs/zstd.1.md > those are used for different scenarios. zstd is used for data compression, the meta string encoding here is used for meta meta encoding Not sure what this means. The motivating use-case described for the alternate string encoding is precisely compression.
  - chaokunyang 3y ago
    Dictionary encoding is already used in fury. We will encode same string as an varint when it's seen later. The thing here is that many cases the string don't have repeat. Imagine you send `record Point(into x, int y)` in an rpc. You have one 'Point' to send. No dictionary encoding will be used in such cases
    - vlovich123 3y ago
      You seem to be fundamentally misunderstanding how the zstd dictionary works. It’s a dictionary at the statistical level. Your `record Point(int x, int y)` RPC would statistically at the bit level have to look like no other message for it to have no help. That seems unlikely since there’s all sorts of framing. And I question the mindset of ad-hoc compression schemes that are trying to shrink the long tail of “sent only once” messages. zstd’s approach is fundamentally very different from a basic interning dictionary. Seriously, there’s been tons of research on this. It’s also interesting that Fury claims to be 0-copy and then does all these ad-hoc field compression which is the literal definition of not 0-copy (& yes, varint encoding is not 0-copy and neither is this custom string compression). Anyway, unless you actually do a proper comparison against zstd with a trained dictionary against a representative corpus, we’re just going in circles with me saying “you need to evaluate your ad-hoc compression against zstd” and you trying to argue from first principles that the custom compression scheme wins.
      - chaokunyang 3y ago
        Hi, it's not “sent only once” . It's millions of “sent only once” . The thing here are that all those RPC are stateless, so the context for compression are the one message itself. i.e. compress object like `Point(1,2)` only without priori knowledge. Users may use train static zstd. But Fury can't, Fury doesn't know which data will be serialized. And meta string encoding are not statistical, it won't beats zstd. It's just for cases zstd is not suitable.
- taeric 3y ago
  I'm curious on this. Why wouldn't statistical compression go smaller? Assuming you restrict the statistics in question to be tailored to the metadata that is being compressed, it feels like it should be comparable? Yes, you may need/want to store a precomputed dictionary at the receiving end so that you aren't sending that every time, but that is really no different from having custom code that you need at receiving end. Right?
  - chaokunyang 3y ago
    The thing is that we can't store a precomputed dictionary. Fury is just a serialization framework, we don't know which data will be serialized
    - taeric 3y ago
      If you can store new code, you can get a more optimized dictionary for what you are doing, though? Why not?
      - chaokunyang 3y ago
        Yes, if we can. The users of Fury may be able to do this. Fury may only provide such an interface to users to let them pass such an dict/zstd/huffman or something like
- Dylan16807 3y ago
  > For such small string, any statistical compression won't have a smaller size. You can hardcode expected frequencies and throw arithmetic encoding at it and the average size will probably drop a meaningful amount. And I can't easily find an example corpus, but the description of these strings sounds like they'd often have repetition, so another symbol to encode repetition and make this into a normal compression algorithm is probably worth it. I wonder how many of these string start with org.apache
chaokunyang 3y ago
We use meta string mainly for object serialization. Users passed an object to Fury, we return a binary to users. In such cases, the serialized binary are mostly in 200~1000 bytes. Not big enough for zstd to work. For dictionary encoding, Fury used similar tech too. When a string first come up, we encoding it as binary, later writing in same object graph will write such string as an varint id. Zstd can be used with Fury too. For multiple serialization across different objects. Fury don't have a context to compression, unless users enable fury meta share mode. If meta share mode not enabled, zstd can be used to compress data across multiple object graph serializaiton
- vlovich123 3y ago
  > In such cases, the serialized binary are mostly in 200~1000 bytes. Not big enough for zstd to work You're not referring to the same dictionary that I am. Look at --train in [1]. If you have a training corpus of representative data, you can generate a dictionary that you preshare on both sides which will perform much better for very small binaries (including 200-1k bytes). It's the same kind of technique but zstd's mechanism is absolutely general whereas purpose-built non-entropy based dictionaries are more limited & less likely to outperform. If you want maximum flexibility (i.e. you don't know the universe of representative messages ahead of time or you want maximum compression performance), you can gather this corpus transparently as messages are generated & then generate a dictionary & attach it as sideband metadata to a message. You'll probably need to defer the decoding if it references a dictionary not yet received (i.e. send delivers messages out-of-order from generation). There are other techniques you can apply, but the general rule is that your custom encoding scheme is unlikely to outperform zstd + a representative training corpus. If it does, you'd need to actually show this rather than try to argue from first principles. [1] https://github.com/facebook/zstd/blob/dev/programs/zstd.1.md https://github.com/facebook/zstd/blob/dev/programs/zstd.1.md
  - irq-1 3y ago
    Wow. Didn't know about Train and custom dictionaries. Very cool.
  - chaokunyang 3y ago

chaokunyang 3y ago

It's not designed to beat zstd, those are used for different scenarios. zstd is used for data compression, the meta string encoding here is used for meta meta encoding. Meta data here are classname/fieldname/packagename/namespace/path/modulename mostly. For such small string, any statistical compression won't have a smaller size.

vlovich123 3y ago
> For such small string, any statistical compression won't have a smaller size That is a statement you can make, but you have to actually demonstrate this is true against zstd's --train mechanism [1] which generates a more optimized "small string" dictionary based on representative training data precisely for this use-case. [1] https://github.com/facebook/zstd/blob/dev/programs/zstd.1.md https://github.com/facebook/zstd/blob/dev/programs/zstd.1.md > those are used for different scenarios. zstd is used for data compression, the meta string encoding here is used for meta meta encoding Not sure what this means. The motivating use-case described for the alternate string encoding is precisely compression.
- chaokunyang 3y ago
  Dictionary encoding is already used in fury. We will encode same string as an varint when it's seen later. The thing here is that many cases the string don't have repeat. Imagine you send `record Point(into x, int y)` in an rpc. You have one 'Point' to send. No dictionary encoding will be used in such cases
  - vlovich123 3y ago
    You seem to be fundamentally misunderstanding how the zstd dictionary works. It’s a dictionary at the statistical level. Your `record Point(int x, int y)` RPC would statistically at the bit level have to look like no other message for it to have no help. That seems unlikely since there’s all sorts of framing. And I question the mindset of ad-hoc compression schemes that are trying to shrink the long tail of “sent only once” messages. zstd’s approach is fundamentally very different from a basic interning dictionary. Seriously, there’s been tons of research on this. It’s also interesting that Fury claims to be 0-copy and then does all these ad-hoc field compression which is the literal definition of not 0-copy (& yes, varint encoding is not 0-copy and neither is this custom string compression). Anyway, unless you actually do a proper comparison against zstd with a trained dictionary against a representative corpus, we’re just going in circles with me saying “you need to evaluate your ad-hoc compression against zstd” and you trying to argue from first principles that the custom compression scheme wins.
    - chaokunyang 3y ago
      Hi, it's not “sent only once” . It's millions of “sent only once” . The thing here are that all those RPC are stateless, so the context for compression are the one message itself. i.e. compress object like `Point(1,2)` only without priori knowledge. Users may use train static zstd. But Fury can't, Fury doesn't know which data will be serialized. And meta string encoding are not statistical, it won't beats zstd. It's just for cases zstd is not suitable.
taeric 3y ago
I'm curious on this. Why wouldn't statistical compression go smaller? Assuming you restrict the statistics in question to be tailored to the metadata that is being compressed, it feels like it should be comparable? Yes, you may need/want to store a precomputed dictionary at the receiving end so that you aren't sending that every time, but that is really no different from having custom code that you need at receiving end. Right?
- chaokunyang 3y ago
  The thing is that we can't store a precomputed dictionary. Fury is just a serialization framework, we don't know which data will be serialized
  - taeric 3y ago
    If you can store new code, you can get a more optimized dictionary for what you are doing, though? Why not?
    - chaokunyang 3y ago
      Yes, if we can. The users of Fury may be able to do this. Fury may only provide such an interface to users to let them pass such an dict/zstd/huffman or something like
Dylan16807 3y ago
> For such small string, any statistical compression won't have a smaller size. You can hardcode expected frequencies and throw arithmetic encoding at it and the average size will probably drop a meaningful amount. And I can't easily find an example corpus, but the description of these strings sounds like they'd often have repetition, so another symbol to encode repetition and make this into a normal compression algorithm is probably worth it. I wonder how many of these string start with org.apache

chaokunyang 3y ago

We use meta string mainly for object serialization. Users passed an object to Fury, we return a binary to users. In such cases, the serialized binary are mostly in 200~1000 bytes. Not big enough for zstd to work. For dictionary encoding, Fury used similar tech too. When a string first come up, we encoding it as binary, later writing in same object graph will write such string as an varint id. Zstd can be used with Fury too. For multiple serialization across different objects. Fury don't have a context to compression, unless users enable fury meta share mode. If meta share mode not enabled, zstd can be used to compress data across multiple object graph serializaiton

vlovich123 3y ago
> In such cases, the serialized binary are mostly in 200~1000 bytes. Not big enough for zstd to work You're not referring to the same dictionary that I am. Look at --train in [1]. If you have a training corpus of representative data, you can generate a dictionary that you preshare on both sides which will perform much better for very small binaries (including 200-1k bytes). It's the same kind of technique but zstd's mechanism is absolutely general whereas purpose-built non-entropy based dictionaries are more limited & less likely to outperform. If you want maximum flexibility (i.e. you don't know the universe of representative messages ahead of time or you want maximum compression performance), you can gather this corpus transparently as messages are generated & then generate a dictionary & attach it as sideband metadata to a message. You'll probably need to defer the decoding if it references a dictionary not yet received (i.e. send delivers messages out-of-order from generation). There are other techniques you can apply, but the general rule is that your custom encoding scheme is unlikely to outperform zstd + a representative training corpus. If it does, you'd need to actually show this rather than try to argue from first principles. [1] https://github.com/facebook/zstd/blob/dev/programs/zstd.1.md https://github.com/facebook/zstd/blob/dev/programs/zstd.1.md
- irq-1 3y ago
  Wow. Didn't know about Train and custom dictionaries. Very cool.
- chaokunyang 3y ago