3 ms·

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 e

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 2y 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 2y 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 2y 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 2y 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 2y 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 2y 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 2y ago
    If you can store new code, you can get a more optimized dictionary for what you are doing, though? Why not?
    - chaokunyang 2y 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 2y 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

vlovich123 2y 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 2y 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 2y 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 2y 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 2y 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 2y 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 2y ago
  If you can store new code, you can get a more optimized dictionary for what you are doing, though? Why not?
  - chaokunyang 2y 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 2y 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