3 ms·

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

by 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...
- chubot 2y ago
  My point was something like - if you want to send a bunch of small strings over the network, you can pick a variable length encoding even more compact than UTF-8 - if you want to pass and return a lot of strings as values, store them in data structures like a List<Str>, then you can pick a variable length encoding even more compact than UTF-8. So you can compute on the entire List<Str> without indirections for the common case of small strings, with good cache locality --- That doesn't really contradict anything you said -- the tagged pointer is in some sense a "wire format", and then you have to do a conversion to actually do something useful with the string. Although sometimes you don't need conversions either. For len() in bytes or code points and graphemes, which are ALL identical for ASCII, you can calculate it directly on the tagged pointer. And you also have random access to bytes, code points, and graphemes in that special case. A lot of the "work" happened when deciding that this encoding is valid for a particular string, which is nice.
  - chaokunyang 2y ago
    Yes, we only use this encoding when it brings benifits. `wire format` is a good term to describe such cases, which the context are constrained to current message only. So the data for compression are small, and many statistical methods won't work since it's a `wire format`. The stats itself must be send to peers, which will have bigger space and cpu cost
  - arcticbull 2y ago
    > For len() in bytes or code points and graphemes, which are ALL identical for ASCII, you can calculate it directly on the tagged pointer. 7-bit ASCII yeah, not 8-bit, which it appears are supported in tagged pointers per your original comment. 8-bit ASCII has fun characters like é (ASCII 130, 0x82) which may be 1 grapheme cluster -- but. There's several ways to represent it in Unicode. You can do it as U+00E9 (NFC) or you can do it as U+0065 U+0301 (the combining acute accent, NFD). This means it's a byte length of 1 in ASCII -- but several in UTF-8 (since UTF-8 only has direct compatibility with the 7-bit plane). And either 2 or 4 in UTF-16. Also, it means this string has a Unicode code point length of 1 or 2 depending on context and normalization form. Again, asking the context-free len() of a string is a meaningless question. > And you also have random access to bytes, code points, and graphemes in that special case. You should never make this assumption. You should treat strings as opaque data blobs. Unicode is just a billion edge cases in a trench coat ;)

by chubot 2y ago

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...

chubot 2y ago
My point was something like - if you want to send a bunch of small strings over the network, you can pick a variable length encoding even more compact than UTF-8 - if you want to pass and return a lot of strings as values, store them in data structures like a List<Str>, then you can pick a variable length encoding even more compact than UTF-8. So you can compute on the entire List<Str> without indirections for the common case of small strings, with good cache locality --- That doesn't really contradict anything you said -- the tagged pointer is in some sense a "wire format", and then you have to do a conversion to actually do something useful with the string. Although sometimes you don't need conversions either. For len() in bytes or code points and graphemes, which are ALL identical for ASCII, you can calculate it directly on the tagged pointer. And you also have random access to bytes, code points, and graphemes in that special case. A lot of the "work" happened when deciding that this encoding is valid for a particular string, which is nice.
- chaokunyang 2y ago
  Yes, we only use this encoding when it brings benifits. `wire format` is a good term to describe such cases, which the context are constrained to current message only. So the data for compression are small, and many statistical methods won't work since it's a `wire format`. The stats itself must be send to peers, which will have bigger space and cpu cost
- arcticbull 2y ago
  > For len() in bytes or code points and graphemes, which are ALL identical for ASCII, you can calculate it directly on the tagged pointer. 7-bit ASCII yeah, not 8-bit, which it appears are supported in tagged pointers per your original comment. 8-bit ASCII has fun characters like é (ASCII 130, 0x82) which may be 1 grapheme cluster -- but. There's several ways to represent it in Unicode. You can do it as U+00E9 (NFC) or you can do it as U+0065 U+0301 (the combining acute accent, NFD). This means it's a byte length of 1 in ASCII -- but several in UTF-8 (since UTF-8 only has direct compatibility with the 7-bit plane). And either 2 or 4 in UTF-16. Also, it means this string has a Unicode code point length of 1 or 2 depending on context and normalization form. Again, asking the context-free len() of a string is a meaningless question. > And you also have random access to bytes, code points, and graphemes in that special case. You should never make this assumption. You should treat strings as opaque data blobs. Unicode is just a billion edge cases in a trench coat ;)