News for hackers. Stuff that matters.
Re:How we made Haskell search strings as fast as Rust by theoh on Wednesday March 13, 2019 @02:20PM (#19381747)
It's what Haskell's 'text' type uses internally. This stackoverflow question seems to discuss why that is the case:

https://stackoverflow.com/questions/23765903/why-is-text-utf...

Re:How we made Haskell search strings as fast as Rust by marcosdumay on Wednesday March 13, 2019 @03:29PM (#19382657)
Just to add, there are a few use cases in what UTF-8 makes a large difference, and there is a UTF-8 version of Text on Hackage for those cases.
Re:How we made Haskell search strings as fast as Rust by spullara on Wednesday March 13, 2019 @03:31PM (#19382682)
Sadly every language developed in the 90s has this flaw. Stuck somewhere between bytes and actual UNICODE.
Re:How we made Haskell search strings as fast as Rust by eridius on Wednesday March 13, 2019 @04:02PM (#19383112)
To be more clear, this flaw happened because way back when we thought UCS-2 was sufficient. Then UTF-16 happened and all these systems designed for UCS-2 had to be hacked up for UTF-16 instead.
Re:How we made Haskell search strings as fast as Rust by stouset on Wednesday March 13, 2019 @05:23PM (#19383982)
To be even more clear, this happened because early versions of Unicode consisted of fewer than 2^16 code points, and this was thought to be enough. In 1996, Unicode 2.0 was published and allowed characters whose encoding required more than 16 bits. This necessitated UTF-16 which allows expansion up to 32 bits to represent characters in higher planes (and is compatible with most text that had been encoded in UCS-2).
Re:How we made Haskell search strings as fast as Rust by chrisseaton on Wednesday March 13, 2019 @05:41PM (#19384169)
> allows expansion up to 32 bits

It doesn't allow expansion up to 32 bits. How would that even be possible? Some of the bits are needed to indicate to use the second two bytes, so there's a hole in the range and it's less than 32 bits.

Re:How we made Haskell search strings as fast as Rust by gowld on Wednesday March 13, 2019 @06:07PM (#19384411)
32 bit-representations (compared to UCS-2), not 32 bits worth of values, so it can represent all of Unicode.

UCS-2 is limited to only 16-bit representation, making it _impossible_ to express Unicode values outside the basic multilingual plane (BMP).

Re:How we made Haskell search strings as fast as Rust by stouset on Wednesday March 13, 2019 @07:21PM (#19384982)
Correct, this is what I meant. UTF-16 can use up to 32 bits to represent a larger number of characters, but cannot uniquely represent 2^32 possible characters.
Re:How we made Haskell search strings as fast as Rust by theoh on Wednesday March 13, 2019 @06:09PM (#19384422)
"Surrogate pairs" use two code units (32 bits total) to increase the number of code points that can be represented. It seems a lot more complicated than UTF-8. I have no idea how many code points can actually be represented in theory. There are under 21 bits' worth of Unicode codepoints, though, so I'm sure the claim that UTF-16 can represent all of them isn't some kind of trick.
Re:How we made Haskell search strings as fast as Rust by eridius on Wednesday March 13, 2019 @06:44PM (#19384722)
A surrogate pair can represent 20 bits, or 2^20 values. A single UTF-16 byte is of course 16 bits, or 2^16 values. 2^20 + 2^16 == 0x110000, which is precisely as many unicode code points as there are (0–0x10FFFF).

Decoding UTF-16 (with surrogate pairs) is pretty similar to decoding UTF-8 except the state machine is simpler (as it's just 1–2 code units per codepoint, instead of 1–3). It also means that if you validate that you have a high surrogate and a low surrogate, the combination is guaranteed to be a valid codepoint (whereas with UTF-8 there are invalid encodings, e.g. any 1-byte codepoint can actually be encoded using 2 or 3 bytes instead, which the state machine must reject).

Re:How we made Haskell search strings as fast as Rust by theoh on Thursday March 14, 2019 @11:00AM (#19389803)
Wait a minute.

"A surrogate pair can represent 20 bits, or 2^20 values. A single UTF-16 byte is of course 16 bits, or 2^16 values. 2^20 + 2^16 == 0x110000, which is precisely as many unicode code points as there are (0–0x10FFFF)."

This explanation can't be quite right, because the possible surrogate code unit values are carved out of the set of 2^16 code units. So you are double counting those surrogate code units.

From Wikipedia: "Since the ranges for the high surrogates (0xD800–0xDBFF), low surrogates (0xDC00–0xDFFF), and valid BMP characters (0x0000–0xD7FF, 0xE000–0xFFFF) are disjoint, it is not possible for a surrogate to match a BMP character, or for two adjacent code units to look like a legal surrogate pair."

Re:How we made Haskell search strings as fast as Rust by theoh on Thursday March 14, 2019 @11:26AM (#19390060)
OK, I've found the gross reason why the 2^16 + 2^20 arithmetic works:

"The Unicode standard permanently reserves these code point values for UTF-16 encoding of the high and low surrogates, and they will never be assigned a character, so there should be no reason to encode them. The official Unicode standard says that no UTF forms, including UTF-16, can encode these code points."

Ugh.

Re:How we made Haskell search strings as fast as Rust by eridius on Wednesday March 13, 2019 @08:55PM (#19385542)
Errata: I stated UTF-8 decoding was 1–3 bytes per codepoint. It's 1–4.
Re:How we made Haskell search strings as fast as Rust by theoh on Wednesday March 13, 2019 @07:37PM (#19385099)
One of us should try to make this clearer on the relevant Wikipedia page.
Re:How we made Haskell search strings as fast as Rust by jcranmer on Thursday March 14, 2019 @12:33AM (#19386543)
UTF-16 encodes a wider character with two surrogate pairs, each pair holding 10 bits of the codepoint. That's why Unicode has 17 planes each containing 65,536 characters, which would otherwise seem odd to have a non-power of two number of Unicode codepoints.
Re:How we made Haskell search strings as fast as Rust by gowld on Wednesday March 13, 2019 @06:02PM (#19384354)
The U in UTF-16 is for Unicode.