Comment by quietbritishjim | Hacker News Reader

Comment by quietbritishjim | Hacker News Reader

Parent Full thread

quietbritishjim

It is not true that UTF8 is the right design "everywhere". Perhaps it is the right design when you have strings that are stored and later read by various programs, but it's not necessarily right for in-memory strings.

Python 3 internally uses ASCII, UCS2 or UCS4 for its strings depending on which is most space efficient but still capable of representing the string. It can do that because Python strings are immutable* and because it is impossible for user code to see what the encoding is (to see the bytes of a string you must explicitly convert it, at which point you specify the destination encoding and Python ensures the translation is correct). If you join a UCS2 string with a UCS4 string then the result is automatically UCS4 and there's no way to tell from user code (except by memory usage)!

There's a good reason for this: indexing into a UTF8 string takes O(n) time because you must parse all the bytes before that point in order to count the number of characters. Iterating over a string by index would either take O(n^2) time or you would have to use some sort of awkward string iterator. If you do not provide any way to index by character (rather than byte position) then I would argue that your data structure is not really a "string". I suppose an alternative implementation would be to use UTF-8 but have an auxiliary data structure that maps between character indices and byte positions.

* Immutability matters because if you had a mutable string in ASCII and you changed one character to be a code point >127 then you'd need to copy the string before making the modification, which if possible at all would be O(n) for what you would expect to be O(1).

I agree with much of what you said here, but 'character', and therefore indexing by character, isn't a well behaved concept in the unicode world. Normalization helps somewhat, though it's another expense at string creation time. However, even after normalization there are plenty of graphemes that don't have a precomposed characters.

Our fundamental ideas about how a string should work and what kinds of things we might want to do with one are deeply influenced by the languages spoken by the pioneers of the computer age. Short of someone from a very different language tradition not being exposed to these implicit assumptions in their formative programming years I don't think we are ever going to know what a different path would look like.

> Normalization helps somewhat, though it's another expense at string creation time

And needs to be handled with care...there are edge cases where it can bite you. For example, if Unicode is being used internally to process data in a legacy CJK encoding, normalisation may lose distinctions that are needed for accurate round-trip conversion.

Another surprise "gotcha" is that simply concatenating two already-normalised strings may give you a result that is not normalised.

> There's a good reason for this: indexing into a UTF8 string takes O(n) time

Here's the thing: You simply don't do that, ever. It's a meaningless operation. Most you would do is iterate over a string.

Bookmarks into a string are one such example of the need for this. No need to O(n) iterate over the string again when the bookmarking logic has already done so.

Computed indicies into strings are a no-go but that is far from the only use case.

But you can index UTF-8 strings with precomputed bookmark indices (byte offsets) just fine. Point is, to precompute them, you would surely have iterated the string before.

What I mean is that "extract the 42th codepoint/glyph/whatever from this UTF-8 string" is a pointless operation for free-form strings because in a free-form string the character position is meaningless.

(Basically all non-ASCII UTF-8 is pretty much a black box. You can't do serious computation with general Unicode because it's so complex and, as a consequence, ill-defined in practice).

This is an advanced trick, but I've successfully done this as part of a binary search to find the glyph at the visual mid-point of the string. UTF-8 is self-synchronizing so you can detect if you cut a code point in half. You still need to handle things like ligatures which even UTF-32 won't speak to directly.

Doesn't work well with BIDI languages, or Mongolian. Seriously if you haven't tested with Mongolian your code is probably wrong.

> Bookmarks into a string are one such example of the need for this. No need to O(n) iterate over the string again when the bookmarking logic has already done so.

You can do that just fine with UTF8, both Swift and Rust allow it.

> Python 3 internally uses ASCII, UCS2 or UCS4 for its strings depending on which is most space efficient but still capable of representing the string.

UTF8 is as efficient as ASCII in the ASCII range, and more than or as efficient as UCS4 beyond the BMP.

The only iffy point is the U+0800 ~ U+FFFF range: Samaritan script to the end of the BMP, which mostly affects extremely contents-dense (mostly text, little to no markup) asian, and native scripts, as well as a few african ones.

Reply on news.ycombinator.com