8 ms·

Meta String: A more space-efficient string encoding than UTF-8 in Fury

75 points by chaokunyang 2y ago

chaokunyang 2y ago
In rpc/serialization systems, we often need to send namespace/path/filename/fieldName/packageName/moduleName/className/enumValue string between processes. Those strings are mostly ascii strings. In order to transfer between processes, we encode such strings using utf-8 encodings. Such encoding will take one byte for every char, which is not space efficient actually. If we take a deeper look, we will found that most chars are lowercase chars, ., $ and _, which can be expressed in a much smaller range 0~32. But one byte can represent range 0~255, the significant bits are wasted, and this cost is not ignorable. In a dynamic serialization framework, such meta will take considerable cost compared to actual data. So we proposed a new string encoding which we called meta string encoding in Fury. It will encode most chars using 5 bits instead of 8 bits in utf-8 encoding, which can bring 37.5% space cost savings compared to utf-8 encoding. For string can't be represented by 5 bits, we also proposed encoding using 6 bits which can bring 25% space cost savings
- masfuerte 2y ago
  You don't include '/' in the list of special characters so how are you using this to encode paths? As an array of strings?
  - chaokunyang 2y ago
    We can use `|` instead, `|` is not used in path. Currently we have only 2 chars can be extended. I haven't decided what to inlucde
chaokunyang 2y ago
For spec details, please see fury meta string spec: https://fury.apache.org/docs/specification/fury_xlang_serialization_spec/#meta-string https://fury.apache.org/docs/specification/fury_xlang_serial...
chaokunyang 2y ago
For implemetation details, https://github.com/apache/incubator-fury/blob/main/java/fury-core/src/main/java/org/apache/fury/meta/MetaStringEncoder.java https://github.com/apache/incubator-fury/blob/main/java/fury... can be taken as an example
weipeng_wang3 2y ago
[dead]
bawolff 2y ago
Seems like they are just using a custom 5 bit charset for strings with a limited alphabet. That's not really a rethink of string encoding, just using a different fixed encoding. Given the usecase, not sure i understand why not just use static huffman.
- chaokunyang 2y ago
  We tried huffman first, But we can't know which string will be serialized. If using huffman, we must collect most strings and compute a static huffman tree. If not, we must send huffman stats to peer, which the cost will be bigger
  - masklinn 2y ago
    > If using huffman, we must collect most strings and compute a static huffman tree. Isn't that essentially what you've done to define your bespoke alphabets / partial encodings?
    - chaokunyang 2y ago
      The thing is that we don't the frequency about every char happens
      - ryan-c 2y ago
        You don't need to. You compute a static huffman tree over fixed probabilities you've estimated or generated from a corpus.
        chaokunyang 2y ago
        Good suggestion, I was planing it as an optional option. We can crawl some github repos, and extract most types, extract their class names, paths, fields names, and use such data as the corpus
        2y ago
agilob 2y ago
If you're intersted in this topic, there exist more string compression algorithms that save data transfer or memory in different ways. Look into Thrift Compact Protocol, MessagePack, Protocol Buffers and Avro.
- chaokunyang 2y ago
  Protobuf only support varint encoding, fury supports that too. But IMO, protobuf use utf-8 for string encoding. Could you share more details how protobuf compress string.
- chaokunyang 2y ago
  And Fury meta string are not used to compress data plane , it's used to compress meta in data plane.
vlovich123 2y ago
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 2y 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 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
eps 2y ago
It's a compression via domain-specific frequency encoding. Good, but that's a pretty common technique for cases where every bit counts.
- chaokunyang 2y ago
  Yes, in many rpc/serialization systems, we need to serialize class name, field names, package names. So we can supprrt dynamic deserialization, type forward/backward compatibility. In such cases, those meta may took more bits than the actual data, this is where meta string bring gains
vbezhenar 2y ago
What about using gzip on messages? I'd expect for it to yield similar savings while keeping message format simpler.
- masklinn 2y ago
  You'd never use gzip for that, it has two dozen bytes of overhead before you can even start building a deflate stream. Even a raw deflate stream might not recoup the overhead on values which are only a few dozen bytes at the most, and if you're not using a static huffman tree the overhead for the tree is going to end all possibility of a gain. Furthermore LZ constructions work off of redundancy, which is difficult to find in large amounts in such short strings. The overhead of framing will just increase the size of the payload after construction. You could define just a static huffman tree and make that part of your spec.
  - chaokunyang 2y ago
    Yes, totally agree. I tried gzip first, but it introduce about 10~20 bytes cost first. So I proposed such meta encoding here. If we have a much bigger string, gzip will be better, but all string we want to compress here are just classname/fieldname/packagename/namespace/path/modulename. We don't have enough repete pattern for gzip to work
    - Dylan16807 2y ago
      If you rip off the gzip headers and footers, DEFLATE applied to a small string only has 10 bits of overhead, 2 bytes with padding. The default Huffman table is not suited for this use case, and a Huffman table in general is a waste of space these days, but the overhead is very small and can be reduced to nothing if you know the original string length.
- chaokunyang 2y ago
  Using gzip to the whole stream will introduce extra cpu cost, we try to make out serialization implementation as fast as possible. If we apply gzip only on such small meta string, it emits bigger size. I belive some stats are written in the data.
NohatCoder 2y ago
I can't help but feel like something has gone fundamentally wrong when there are so many arbitrary strings in the system that this optimisation makes a tangible difference.
- chaokunyang 2y ago
  Meta string is not designed for encoding arbitrary strings, they are used to encode limited enumerated string only, such as classname/fieldname/packagename/namespace/path/modulename. This is why we name it as meta string, used in a case where lossless statistical compresion can't provide a gain
- smsm42 2y ago
  Why is it wrong? It is a widely known fact that texts are redundant and compress well. Many systems work with texts and there's an advantage when those texts are human-comprehensible. You can make a system which would auto-compress and decompress any text of sufficient length - and some do - but there's absolutely no surprise that texts are compressible and it doesn't indicate there's something wrong. Texts are not optimized for space, they are optimized for human convenience.
  - zokier 2y ago
    But these are not general text, they are identifiers. If you are building space-efficient RPC system then I do think it is reasonable to question why are these identifiers passed as strings in such quantity that it makes a difference. On top of my head, a better approach could be to have some mechanism to establish mapping from these human-readable identifiers to numeric identifiers (protocol handshake or some other schema exchange), and then use those numeric identifiers in the actual high-volume messages. edit: umm... seems like fury is doing something like that already https://fury.apache.org/docs/guide/java_object_graph_guide#meta-sharing https://fury.apache.org/docs/guide/java_object_graph_guide#m... so I am bit puzzled if this saving really makes meaningful difference?!
    - smsm42 2y ago
amiga386 2y ago
Everything old is new again. This reminds me of ZSCII, which was how Infocom games encoded string data to fit ~100kb of text data into a Commodore 64, packing 3 characters into every 2 bytes. --first byte------- --second byte--- 7 6 5 4 3 2 1 0 7 6 5 4 3 2 1 0 bit --first-- --second--- --third-- The 5-bit character encoding was one of three character sets: Z-char 6789abcdef0123456789abcdef current -------------------------- A0 abcdefghijklmnopqrstuvwxyz A1 ABCDEFGHIJKLMNOPQRSTUVWXYZ A2 ^0123456789.,!?_#'"/\-:() -------------------------- Z-char 0 was space in all character sets, z-char 1 was newline, z-chars 2 and 3 switched to one of the other character sets depending on which one you were already in for the next character only, and z-chars 4 and 5 switched permanently, the "shift-lock". https://inform-fiction.org/zmachine/standards/z1point0/sect03.html https://inform-fiction.org/zmachine/standards/z1point0/sect0...
- chaokunyang 2y ago
  This is interesting, thanks for sharing this. I will take a deep look at it.
deleted 2y ago
[deleted]
chubot 2y ago
Apple's NSString apparently uses an in-memory encoding (not wire encoding) that can go as low as 5 bits per byte, as of OS X 10.10 in 2014: https://mikeash.com/pyblog/friday-qa-2015-07-31-tagged-pointer-strings.html https://mikeash.com/pyblog/friday-qa-2015-07-31-tagged-point... If the length is between 0 and 7, store the string as raw eight-bit characters. If the length is 8 or 9, store the string in a six-bit encoding, using the alphabet "eilotrm.apdnsIc ufkMShjTRxgC4013bDNvwyUL2O856P-B79AFKEWV_zGJ/HYX".* If the length is 10 or 11, store the string in a five-bit encoding, using the alphabet "eilotrm.apdnsIc ufkMShjTRxgC4013" --- How about 5 bits? This isn't totally ludicrous. There are probably a lot of strings which are just lowercase, for example. 5 bits gives 32 possible values. If you include the whole lowercase alphabet, there are 6 extra values, which you could allot to the more common uppercase letters, or some symbols, or digits, or some mix. Related thread - https://lobste.rs/s/5417dx/storing_data_pointers#c_l4zfrv https://lobste.rs/s/5417dx/storing_data_pointers#c_l4zfrv It's interesting how network formats and in-memory formats kinda converge in design, because retrieving data from memory to CPU is so expensive now.
- arcticbull 2y ago
  ... only in tagged pointers meaning the total size can't exceed like ~60 bits. After that, the canonical representation of NSString is UTF-16 and in Swift strings is UTF-8. So not "in memory" (although obviously it is in memory) it's when the goal is to fit the totality of the string plus a tag into a register. If they can't completely encode the 10-11 character value using the 5-bit charset it spills to UTF-16 on the heap. > It's interesting how network formats and in-memory formats kinda converge in design, because retrieving data from memory to CPU is so expensive now. Honestly Strings are probably one of the worst examples of this. Strings have like 50 different representations depending on what you're trying to do with them. 1. Wire format for storage and retrieval is generally UTF-8. 2. If you're trying to parse a string you generally want to expand it into code points. 3. If you're trying to sort or compare strings you generally want to expand that into a normalized form like NFC or NFD. 4. If you're trying to edit text, you generally want grapheme clusters. 5. If you're trying to present text, you generally want pixels. The way to think about it is: "there is no such things as the length of a string without context." Strings are basically a bytecode format for representing concepts. [1] https://developer.apple.com/documentation/foundation/nsstring https://developer.apple.com/documentation/foundation/nsstrin...
lifthrasiir 2y ago
In addition to the existing dictionary compression algorithms, it is very important to know the characteristics of string contents. The proposed encoding has a very crude mechanism to describe them, but that's all (and that encoding flag is included to every string encoded, even though the schema could have included that information instead). Namespaces would start with only a small number of fixed prefixes like `java.`, `com.` and `org.`. Namespaces, paths and file names will have a lot of overlapping substrings as well. Class and field names are more chaotic, but some heuristics can be easily extracted as most of them will obey the common naming convention. By the way, the specification is highly confusing to interpret to say the least as well. For example, is the "ref(erence) meta" a separate section in the serialization format or not? The corresponding section never mentions which bytes are to be written, and reference flags apparently describe the state of each object, so it can't be in that section anyway. Providing at least a single worked example would have significantly reduced confusion. (Due to the inability to fully comprehend the specification, I can't give a general criticism and/or advice for now. But it does seem to miss several lessons from existing serialization formats. For instance, a varint encoding based on a contiuation bit is actually the worst encoding for given distribution, even though it is too common! Consider an alternative like `1^n 0 bit^(7n+7)` which can determine the contiuation length from the first byte instead.)
hgs3 2y ago
How does this compare to the official Unicode compression schemes? [1] [2] [1] https://en.wikipedia.org/wiki/Standard_Compression_Scheme_for_Unicode https://en.wikipedia.org/wiki/Standard_Compression_Scheme_fo... [2] https://en.wikipedia.org/wiki/Binary_Ordered_Compression_for_Unicode https://en.wikipedia.org/wiki/Binary_Ordered_Compression_for...
grandinj 2y ago
OOOh, very very nice. I might have to copy this into the H2 database engine. We already use variable-size encoding for numbers, and this would make a nice addition to reducing the size of row data containing text.
- chaokunyang 2y ago
  Glad to see H2 database engine benifits from this. I use H2 too.

75 points by chaokunyang 2y ago

In rpc/serialization systems, we often need to send namespace/path/filename/fieldName/packageName/moduleName/className/enumValue string between processes. Those strings are mostly ascii strings. In order to transfer between processes, we encode such strings using utf-8 encodings. Such encoding will take one byte for every char, which is not space efficient actually. If we take a deeper look, we will found that most chars are lowercase chars, ., $ and _, which can be expressed in a much smaller range 0~32. But one byte can represent range 0~255, the significant bits are wasted, and this cost is not ignorable. In a dynamic serialization framework, such meta will take considerable cost compared to actual data. So we proposed a new string encoding which we called meta string encoding in Fury. It will encode most chars using 5 bits instead of 8 bits in utf-8 encoding, which can bring 37.5% space cost savings compared to utf-8 encoding. For string can't be represented by 5 bits, we also proposed encoding using 6 bits which can bring 25% space cost savings

masfuerte 2y ago
You don't include '/' in the list of special characters so how are you using this to encode paths? As an array of strings?
- chaokunyang 2y ago
  We can use `|` instead, `|` is not used in path. Currently we have only 2 chars can be extended. I haven't decided what to inlucde

chaokunyang 2y ago

For spec details, please see fury meta string spec: https://fury.apache.org/docs/specification/fury_xlang_serialization_spec/#meta-string https://fury.apache.org/docs/specification/fury_xlang_serial...

chaokunyang 2y ago

For implemetation details, https://github.com/apache/incubator-fury/blob/main/java/fury-core/src/main/java/org/apache/fury/meta/MetaStringEncoder.java https://github.com/apache/incubator-fury/blob/main/java/fury... can be taken as an example

weipeng_wang3 2y ago

[dead]

bawolff 2y ago

Seems like they are just using a custom 5 bit charset for strings with a limited alphabet. That's not really a rethink of string encoding, just using a different fixed encoding. Given the usecase, not sure i understand why not just use static huffman.

chaokunyang 2y ago
We tried huffman first, But we can't know which string will be serialized. If using huffman, we must collect most strings and compute a static huffman tree. If not, we must send huffman stats to peer, which the cost will be bigger
- masklinn 2y ago
  > If using huffman, we must collect most strings and compute a static huffman tree. Isn't that essentially what you've done to define your bespoke alphabets / partial encodings?
  - chaokunyang 2y ago
    The thing is that we don't the frequency about every char happens
    - ryan-c 2y ago
      You don't need to. You compute a static huffman tree over fixed probabilities you've estimated or generated from a corpus.
      - chaokunyang 2y ago
        Good suggestion, I was planing it as an optional option. We can crawl some github repos, and extract most types, extract their class names, paths, fields names, and use such data as the corpus
        2y ago

agilob 2y ago

If you're intersted in this topic, there exist more string compression algorithms that save data transfer or memory in different ways. Look into Thrift Compact Protocol, MessagePack, Protocol Buffers and Avro.

chaokunyang 2y ago
Protobuf only support varint encoding, fury supports that too. But IMO, protobuf use utf-8 for string encoding. Could you share more details how protobuf compress string.
chaokunyang 2y ago
And Fury meta string are not used to compress data plane , it's used to compress meta in data plane.

vlovich123 2y ago

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 2y 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 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

eps 2y ago

It's a compression via domain-specific frequency encoding. Good, but that's a pretty common technique for cases where every bit counts.

chaokunyang 2y ago
Yes, in many rpc/serialization systems, we need to serialize class name, field names, package names. So we can supprrt dynamic deserialization, type forward/backward compatibility. In such cases, those meta may took more bits than the actual data, this is where meta string bring gains

vbezhenar 2y ago

What about using gzip on messages? I'd expect for it to yield similar savings while keeping message format simpler.

masklinn 2y ago
You'd never use gzip for that, it has two dozen bytes of overhead before you can even start building a deflate stream. Even a raw deflate stream might not recoup the overhead on values which are only a few dozen bytes at the most, and if you're not using a static huffman tree the overhead for the tree is going to end all possibility of a gain. Furthermore LZ constructions work off of redundancy, which is difficult to find in large amounts in such short strings. The overhead of framing will just increase the size of the payload after construction. You could define just a static huffman tree and make that part of your spec.
- chaokunyang 2y ago
  Yes, totally agree. I tried gzip first, but it introduce about 10~20 bytes cost first. So I proposed such meta encoding here. If we have a much bigger string, gzip will be better, but all string we want to compress here are just classname/fieldname/packagename/namespace/path/modulename. We don't have enough repete pattern for gzip to work
  - Dylan16807 2y ago
    If you rip off the gzip headers and footers, DEFLATE applied to a small string only has 10 bits of overhead, 2 bytes with padding. The default Huffman table is not suited for this use case, and a Huffman table in general is a waste of space these days, but the overhead is very small and can be reduced to nothing if you know the original string length.
chaokunyang 2y ago
Using gzip to the whole stream will introduce extra cpu cost, we try to make out serialization implementation as fast as possible. If we apply gzip only on such small meta string, it emits bigger size. I belive some stats are written in the data.

NohatCoder 2y ago

I can't help but feel like something has gone fundamentally wrong when there are so many arbitrary strings in the system that this optimisation makes a tangible difference.

chaokunyang 2y ago
Meta string is not designed for encoding arbitrary strings, they are used to encode limited enumerated string only, such as classname/fieldname/packagename/namespace/path/modulename. This is why we name it as meta string, used in a case where lossless statistical compresion can't provide a gain
smsm42 2y ago
Why is it wrong? It is a widely known fact that texts are redundant and compress well. Many systems work with texts and there's an advantage when those texts are human-comprehensible. You can make a system which would auto-compress and decompress any text of sufficient length - and some do - but there's absolutely no surprise that texts are compressible and it doesn't indicate there's something wrong. Texts are not optimized for space, they are optimized for human convenience.
- zokier 2y ago
  But these are not general text, they are identifiers. If you are building space-efficient RPC system then I do think it is reasonable to question why are these identifiers passed as strings in such quantity that it makes a difference. On top of my head, a better approach could be to have some mechanism to establish mapping from these human-readable identifiers to numeric identifiers (protocol handshake or some other schema exchange), and then use those numeric identifiers in the actual high-volume messages. edit: umm... seems like fury is doing something like that already https://fury.apache.org/docs/guide/java_object_graph_guide#meta-sharing https://fury.apache.org/docs/guide/java_object_graph_guide#m... so I am bit puzzled if this saving really makes meaningful difference?!
  - smsm42 2y ago

amiga386 2y ago

Everything old is new again. This reminds me of ZSCII, which was how Infocom games encoded string data to fit ~100kb of text data into a Commodore 64, packing 3 characters into every 2 bytes. --first byte------- --second byte--- 7 6 5 4 3 2 1 0 7 6 5 4 3 2 1 0 bit --first-- --second--- --third-- The 5-bit character encoding was one of three character sets: Z-char 6789abcdef0123456789abcdef current -------------------------- A0 abcdefghijklmnopqrstuvwxyz A1 ABCDEFGHIJKLMNOPQRSTUVWXYZ A2 ^0123456789.,!?_#'"/\-:() -------------------------- Z-char 0 was space in all character sets, z-char 1 was newline, z-chars 2 and 3 switched to one of the other character sets depending on which one you were already in for the next character only, and z-chars 4 and 5 switched permanently, the "shift-lock". https://inform-fiction.org/zmachine/standards/z1point0/sect03.html https://inform-fiction.org/zmachine/standards/z1point0/sect0...

chaokunyang 2y ago
This is interesting, thanks for sharing this. I will take a deep look at it.

deleted 2y ago

[deleted]

chubot 2y ago

Apple's NSString apparently uses an in-memory encoding (not wire encoding) that can go as low as 5 bits per byte, as of OS X 10.10 in 2014: https://mikeash.com/pyblog/friday-qa-2015-07-31-tagged-pointer-strings.html https://mikeash.com/pyblog/friday-qa-2015-07-31-tagged-point... If the length is between 0 and 7, store the string as raw eight-bit characters. If the length is 8 or 9, store the string in a six-bit encoding, using the alphabet "eilotrm.apdnsIc ufkMShjTRxgC4013bDNvwyUL2O856P-B79AFKEWV_zGJ/HYX".* If the length is 10 or 11, store the string in a five-bit encoding, using the alphabet "eilotrm.apdnsIc ufkMShjTRxgC4013" --- How about 5 bits? This isn't totally ludicrous. There are probably a lot of strings which are just lowercase, for example. 5 bits gives 32 possible values. If you include the whole lowercase alphabet, there are 6 extra values, which you could allot to the more common uppercase letters, or some symbols, or digits, or some mix. Related thread - https://lobste.rs/s/5417dx/storing_data_pointers#c_l4zfrv https://lobste.rs/s/5417dx/storing_data_pointers#c_l4zfrv It's interesting how network formats and in-memory formats kinda converge in design, because retrieving data from memory to CPU is so expensive now.

arcticbull 2y ago
... only in tagged pointers meaning the total size can't exceed like ~60 bits. After that, the canonical representation of NSString is UTF-16 and in Swift strings is UTF-8. So not "in memory" (although obviously it is in memory) it's when the goal is to fit the totality of the string plus a tag into a register. If they can't completely encode the 10-11 character value using the 5-bit charset it spills to UTF-16 on the heap. > It's interesting how network formats and in-memory formats kinda converge in design, because retrieving data from memory to CPU is so expensive now. Honestly Strings are probably one of the worst examples of this. Strings have like 50 different representations depending on what you're trying to do with them. 1. Wire format for storage and retrieval is generally UTF-8. 2. If you're trying to parse a string you generally want to expand it into code points. 3. If you're trying to sort or compare strings you generally want to expand that into a normalized form like NFC or NFD. 4. If you're trying to edit text, you generally want grapheme clusters. 5. If you're trying to present text, you generally want pixels. The way to think about it is: "there is no such things as the length of a string without context." Strings are basically a bytecode format for representing concepts. [1] https://developer.apple.com/documentation/foundation/nsstring https://developer.apple.com/documentation/foundation/nsstrin...

lifthrasiir 2y ago

In addition to the existing dictionary compression algorithms, it is very important to know the characteristics of string contents. The proposed encoding has a very crude mechanism to describe them, but that's all (and that encoding flag is included to every string encoded, even though the schema could have included that information instead). Namespaces would start with only a small number of fixed prefixes like `java.`, `com.` and `org.`. Namespaces, paths and file names will have a lot of overlapping substrings as well. Class and field names are more chaotic, but some heuristics can be easily extracted as most of them will obey the common naming convention. By the way, the specification is highly confusing to interpret to say the least as well. For example, is the "ref(erence) meta" a separate section in the serialization format or not? The corresponding section never mentions which bytes are to be written, and reference flags apparently describe the state of each object, so it can't be in that section anyway. Providing at least a single worked example would have significantly reduced confusion. (Due to the inability to fully comprehend the specification, I can't give a general criticism and/or advice for now. But it does seem to miss several lessons from existing serialization formats. For instance, a varint encoding based on a contiuation bit is actually the worst encoding for given distribution, even though it is too common! Consider an alternative like `1^n 0 bit^(7n+7)` which can determine the contiuation length from the first byte instead.)

hgs3 2y ago

How does this compare to the official Unicode compression schemes? [1] [2] [1] https://en.wikipedia.org/wiki/Standard_Compression_Scheme_for_Unicode https://en.wikipedia.org/wiki/Standard_Compression_Scheme_fo... [2] https://en.wikipedia.org/wiki/Binary_Ordered_Compression_for_Unicode https://en.wikipedia.org/wiki/Binary_Ordered_Compression_for...

grandinj 2y ago

OOOh, very very nice. I might have to copy this into the H2 database engine. We already use variable-size encoding for numbers, and this would make a nice addition to reducing the size of row data containing text.

chaokunyang 2y ago
Glad to see H2 database engine benifits from this. I use H2 too.