1. https://blog.mozilla.org/javascript/2014/07/21/slimmer-and-f...
>Gecko is huge and it uses TwoByte strings in most places. Converting all of Gecko to use UTF8 strings is a much bigger project and has its own risks.
But I guess they mean converting it all to support UTF-8 under the described circumstances - not just converting it all to UTF-8.
Edit: I.e. it would be awkward to say you're implementing "UTF-8, but only for these codepoints". That would be equivalent to implementing Latin-1.
Edit: I'm thinking of standard ASCII rather than Latin-1. Above the first 128 code points, UTF-8 switches to two bytes while Latin-1 remains with one byte, so it is much simpler.
* Gecko is huge and it uses TwoByte strings in most places. Converting all of Gecko to use UTF8 strings is a much bigger project and has its own risks. As described below, we currently inflate Latin1 strings to TwoByte Gecko strings and that was also a potential performance risk, but inflating Latin1 is much faster than inflating UTF8.
* Linear-time indexing: operations like charAt require character indexing to be fast. We discussed solving this by adding a special flag to indicate all characters in the string are ASCII, so that we can still use O(1) indexing in this case. This scheme will only work for ASCII strings, though, so it’s a potential performance risk. An alternative is to have such operations inflate the string from UTF8 to TwoByte, but that’s also not ideal.
* Converting SpiderMonkey’s own string algorithms to work on UTF8 would require a lot more work. This includes changing the irregexp regular expression engine we imported from V8 a few months ago (it already had code to handle Latin1 strings).
This is great for ASCII when you know there's no such thing as combining characters/etc, but I would like to remind everyone reading this that there's no such thing as "linear indexing" of user-perceived characters in Unicode.
User-perceived characters need processing in order to index due to Grapheme clusters potentially using many code points together. (https://unicode.org/reports/tr29/#Grapheme_Cluster_Boundarie...)
For instance, (on my machine, a dark-skinned male teacher) is a combination of these characters:
- U+1F468 Man - U+1F3FE Medium-Dark Skin Tone - U+200D Zero Width Joiner - U+1F3EB School
And knowing what the byte index of the start/end of that character in a string cannot be done by just multiplying an offset by some multiple of number of bytes per character.
There is if you dynamically assign virtual code points to grapheme clusters.
> adding a special flag to indicate all characters in the string are ASCII, so that we can still use O(1) indexing in this case
But I got confused and addressed the linear indexing part.
But yeah, ASCII is constant time, but you can’t assume even UTF-32 can be constant time due to variable length grapheme clusters.
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.
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."
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.
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.
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.
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.