3 ms·

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 d

by 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.
Someone 7y ago
Java’s “String” interface included the fact that indexing a string by character is O(1), so its desire to not break interfaces rules out such choices.
- comex 7y ago
  Yes, and it includes that guarantee because it was designed with UCS-2 in mind. The question is what would have happened if, hypothetically, the mistake of UCS-2 had never been made.
  - jrochkind1 7y ago
    Well, you can't get that easy O(1) charAt with UTF-8 either, so I think it'd actually be in the same spot, is what I'm saying. I think. I guess perhaps it wouldn't ever have said it provided a charAt in O(1), okay. It may have been a mistake to think this mattered, it was just offered because it was easy. In which case I suspect there are actually few programs which would be negatively affected by changing charAt to the most efficient you can do in UTF8. UTF-32 of course has the O(1) property, but nobody wants that memory usage.

by comex 7y ago

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.

Someone 7y ago

Java’s “String” interface included the fact that indexing a string by character is O(1), so its desire to not break interfaces rules out such choices.

comex 7y ago
Yes, and it includes that guarantee because it was designed with UCS-2 in mind. The question is what would have happened if, hypothetically, the mistake of UCS-2 had never been made.
- jrochkind1 7y ago
  Well, you can't get that easy O(1) charAt with UTF-8 either, so I think it'd actually be in the same spot, is what I'm saying. I think. I guess perhaps it wouldn't ever have said it provided a charAt in O(1), okay. It may have been a mistake to think this mattered, it was just offered because it was easy. In which case I suspect there are actually few programs which would be negatively affected by changing charAt to the most efficient you can do in UTF8. UTF-32 of course has the O(1) property, but nobody wants that memory usage.