4 ms·

The String (and CharSequence) API are already warped around the assumption of underlying UTF-16 storage. In particular `charAt()` refers to a UTF-16 code unit p

The String (and CharSequence) API are already warped around the assumption of underlying UTF-16 storage. In particular `charAt()` refers to a UTF-16 code unit position, and in general all methods [1] that take any kind of index are using an index into an explicit or implicit UTF-16 string. All of these functions need to be fast: certainly at least O(1). So for your narrow encoding you need one that maps 1:1 (in a fixed-length way) to UTF-16. That rules out multi-byte UTF-8. You could of course just restrict it to UTF-8 chars that fit in a single byte – but that's just ASCII! You waste a bit per character. So you might has we'll use a full 8-bit encoding, and Latin-1 is convenient as it covers many more characters likely to be encountered in text that can use single-byte UTF-8 in the first place. It is also convenient in that Latin-1 and Unicode codepoints identical so conversion to and from UTF-16 can be very efficient (in fact there are SIMD instructions which do it exactly). In any case, even in the scenario you could somehow use UTF-8 efficiently, it is likely to be worse in this particular scenario: - They both use 1 byte for code points 0-127 - Latin-1 uses 1 byte for 128-255, while UTF-8 uses 2 - Above 255, UTF-8 uses at least two but the Java hybrid string will be using UTF-16 now, for a common case of 2 bytes. So the only place UTF-8 wins is for the unusual case of characters outside the BMP which are 3 bytes in UTF-8 but 4 bytes in UTF-16. Those aren't common at all, and in many scenarios where you'd have a lot of them UTF-16 would still win because it represents many characters in the BMP in 2 bytes that take 3 in UTF-8. --- [1] One might think there is an exception illustrated by the few methods that mention "code point", like `codePointAt`. Yes, these deal in code points, but their indexes are still indexes into a UTF-16 string. So they are kind of a hybrid API. They let you count N UTF-16 code units (which will represent <= N code points) into a string, and then deal with the code point at that location. That leads to weird cases like asking for the code point starting at the second half of a surrogate pair, which gives you the low surrogate alone.

jrochkind1 7y ago
Ah, thanks for explaining this. I was confused and thought that Latin-1 fit in UTF-8 in one byte, but I went and confirmed for myself you are right it does not. Hm. In fact this means though that it isn't just the mistake of UCS-2 that results in people wanting "transparent Latin1 under the hood to save space". Even if we had gone right to UTF-8, there would still roughly the same cost savings there. I can't think of any way to deal with unicode that wouldn't have similar cost savings from "transparently doing non-unicode when possible". Well, I suppose unless you made whatever Java (et al) are doing to mark which strings or portions of strings are actually being stored as Latin1, and made that a Unicode encoding. That would of course have it's own... challenges. If you think "transparently storing as Latin1 when possible" is an ugly hack, you'd probably not be happier with it being made a unicode standard encoding. It turns out being able to represent all written human communication is really hard. Unicode actually does a pretty amazing job of it, balancing lots of trade-offs. (And the fact that it has as wide-spread adoption as it does is in part testament to this; just because you make a standard doesn't mean anyone has to or is going ot use it. Some of the trade-offs unicode balanced were making the adoption curve as easy as possible for existing software. Making ascii valid UTF-8 was, I think, proven by history to be the right decision, although it involved trade-offs... such as Latin1 not fitting in one byte :) ). Overall, Unicode is a really succesful standard, technically and in terms of adoption. But UCS-2 was a mistake, that if it had been avoided would avoid some headache. But, i think, not the headache where Java is motivated to "store some things transparently as Latin1 where possible."
- comex 7y ago
  The alternative is to just not provide functions like charAt() that accept a codepoint index and are expected to be O(1). Instead, as Rust, Swift, and Go all do to some extent, you provide functions that accept UTF-8 byte indexes, and complain if they get an index that doesn’t correspond to the beginning of a codepoint (which can be verified in O(1) thanks to UTF-8’s self-synchronizing property). Then you can add higher-level APIs on top that provide non-random-access iterators over things like codepoints and grapheme clusters. After all, if you really want to treat a string as a list of characters, the most sensible default notion of “character” is probably a grapheme cluster rather than a codepoint - but there‘s no encoding that gives you O(1) random access to those anyway. Under such a design, storing the string data as anything other than UTF-8 is unnecessary. In fact, it’s impossible: if you store string data as Latin-1, you can’t index into it with a UTF-8 byte index. That does mean you can’t take advantage of the space savings of Latin-1 over UTF-8, but those are extremely minimal, since both encodings are 1 byte for all ASCII characters.
  - jrochkind1 7y ago
    That is an "alternative", but I'm not sure it's relevant to the motivations people are having to use Latin1 for space savings. I am not sure if the space savings really are extremely minimal or not for Latin1 vs UTF8. You are correct both encodings are one byte for all ASCII characters, but they are choosing to store as Latin1, NOT as ASCII, to get 1 byte for all Latin1 characters beyond ascii. If they didn't care about space savings for anything but ascii -- they could already have chosen UTF8 instead of Latin1. Which makes me think they care about the space savings for non-ascii Latin1. It seems to me an orthogonal question to whether you provide functions like `charAt`, and what big-O performance-complexity.
    - comex 7y ago
      Well, we’re talking about an optimization retrofitted onto a String class which guaranteed O(1) indexing by 16-bit code units. Given that constraint, only a fixed-width encoding can work, so UTF-8 is out. In lieu of that, you may as well pick an encoding that uses the full 8 bits, hence the choice of Latin-1 instead of ASCII. But indexing by code units only really made sense when Unicode was limited to 16-bit codepoints. Back then, “code unit” and “codepoint” were the same thing, so every code unit had some semantic meaning of its own, rather than just being an artifact of the encoding. Thus, programmers could keep treating strings as “arrays of characters” like they were used to, except that “character” now meant a 16-bit integer instead of an 8-bit one. In truth, Unicode code points were never a perfect representation of what a human might think of as a “character”, due to the existence of combining characters like accent marks, but you could still arbitrarily chop them up and combine them and get something roughly sensible. Overall, they seemed like a reasonable compromise that preserved the notion of “array of characters” to as great an extent as possible. But these days, a UTF-16 “code unit” can be half of a surrogate pair: an artifact of the encoding with no semantic meaning of its own, the exact thing we were trying to avoid. It now has the downsides of a variable-width encoding like UTF-8, without the space efficiency or the backwards compatibility. So if Java’s String were being designed from scratch – or if, hypothetically, Unicode had never been intended to be limited to 16-bit codepoints – there’s no way it would provide indexing by 16-bit code units. It might instead opt to provide O(1) access to 32-bit Unicode codepoints. This is what Python 3 does, and so it has to represent strings as UCS-4 in the worst case, but it can store them as UCS-2 or Latin-1 if the string has no codepoints over 65,535 or 255, respectively. In that case, yes, you still end up with Latin-1 as an optimization. But Python has always prioritized ease of use over performance, and it had backwards compatibility constraints as well. For new designs, most people just see the overhead of UCS-4 as a bridge too far. Compared to that, it seems more attractive to bite the bullet and accept the downsides of variable-width encodings. And at that point you may as well pick UTF-8.

jrochkind1 7y ago

Ah, thanks for explaining this. I was confused and thought that Latin-1 fit in UTF-8 in one byte, but I went and confirmed for myself you are right it does not. Hm. In fact this means though that it isn't just the mistake of UCS-2 that results in people wanting "transparent Latin1 under the hood to save space". Even if we had gone right to UTF-8, there would still roughly the same cost savings there. I can't think of any way to deal with unicode that wouldn't have similar cost savings from "transparently doing non-unicode when possible". Well, I suppose unless you made whatever Java (et al) are doing to mark which strings or portions of strings are actually being stored as Latin1, and made that a Unicode encoding. That would of course have it's own... challenges. If you think "transparently storing as Latin1 when possible" is an ugly hack, you'd probably not be happier with it being made a unicode standard encoding. It turns out being able to represent all written human communication is really hard. Unicode actually does a pretty amazing job of it, balancing lots of trade-offs. (And the fact that it has as wide-spread adoption as it does is in part testament to this; just because you make a standard doesn't mean anyone has to or is going ot use it. Some of the trade-offs unicode balanced were making the adoption curve as easy as possible for existing software. Making ascii valid UTF-8 was, I think, proven by history to be the right decision, although it involved trade-offs... such as Latin1 not fitting in one byte :) ). Overall, Unicode is a really succesful standard, technically and in terms of adoption. But UCS-2 was a mistake, that if it had been avoided would avoid some headache. But, i think, not the headache where Java is motivated to "store some things transparently as Latin1 where possible."

comex 7y ago
The alternative is to just not provide functions like charAt() that accept a codepoint index and are expected to be O(1). Instead, as Rust, Swift, and Go all do to some extent, you provide functions that accept UTF-8 byte indexes, and complain if they get an index that doesn’t correspond to the beginning of a codepoint (which can be verified in O(1) thanks to UTF-8’s self-synchronizing property). Then you can add higher-level APIs on top that provide non-random-access iterators over things like codepoints and grapheme clusters. After all, if you really want to treat a string as a list of characters, the most sensible default notion of “character” is probably a grapheme cluster rather than a codepoint - but there‘s no encoding that gives you O(1) random access to those anyway. Under such a design, storing the string data as anything other than UTF-8 is unnecessary. In fact, it’s impossible: if you store string data as Latin-1, you can’t index into it with a UTF-8 byte index. That does mean you can’t take advantage of the space savings of Latin-1 over UTF-8, but those are extremely minimal, since both encodings are 1 byte for all ASCII characters.
- jrochkind1 7y ago
  That is an "alternative", but I'm not sure it's relevant to the motivations people are having to use Latin1 for space savings. I am not sure if the space savings really are extremely minimal or not for Latin1 vs UTF8. You are correct both encodings are one byte for all ASCII characters, but they are choosing to store as Latin1, NOT as ASCII, to get 1 byte for all Latin1 characters beyond ascii. If they didn't care about space savings for anything but ascii -- they could already have chosen UTF8 instead of Latin1. Which makes me think they care about the space savings for non-ascii Latin1. It seems to me an orthogonal question to whether you provide functions like `charAt`, and what big-O performance-complexity.
  - comex 7y ago
    Well, we’re talking about an optimization retrofitted onto a String class which guaranteed O(1) indexing by 16-bit code units. Given that constraint, only a fixed-width encoding can work, so UTF-8 is out. In lieu of that, you may as well pick an encoding that uses the full 8 bits, hence the choice of Latin-1 instead of ASCII. But indexing by code units only really made sense when Unicode was limited to 16-bit codepoints. Back then, “code unit” and “codepoint” were the same thing, so every code unit had some semantic meaning of its own, rather than just being an artifact of the encoding. Thus, programmers could keep treating strings as “arrays of characters” like they were used to, except that “character” now meant a 16-bit integer instead of an 8-bit one. In truth, Unicode code points were never a perfect representation of what a human might think of as a “character”, due to the existence of combining characters like accent marks, but you could still arbitrarily chop them up and combine them and get something roughly sensible. Overall, they seemed like a reasonable compromise that preserved the notion of “array of characters” to as great an extent as possible. But these days, a UTF-16 “code unit” can be half of a surrogate pair: an artifact of the encoding with no semantic meaning of its own, the exact thing we were trying to avoid. It now has the downsides of a variable-width encoding like UTF-8, without the space efficiency or the backwards compatibility. So if Java’s String were being designed from scratch – or if, hypothetically, Unicode had never been intended to be limited to 16-bit codepoints – there’s no way it would provide indexing by 16-bit code units. It might instead opt to provide O(1) access to 32-bit Unicode codepoints. This is what Python 3 does, and so it has to represent strings as UCS-4 in the worst case, but it can store them as UCS-2 or Latin-1 if the string has no codepoints over 65,535 or 255, respectively. In that case, yes, you still end up with Latin-1 as an optimization. But Python has always prioritized ease of use over performance, and it had backwards compatibility constraints as well. For new designs, most people just see the overhead of UCS-4 as a bridge too far. Compared to that, it seems more attractive to bite the bullet and accept the downsides of variable-width encodings. And at that point you may as well pick UTF-8.