4 ms·

I've been wondering, how much processor overhead does UTF8 have? Not just because you can't jump N bytes into a string to get a character offset, but because ea

I've been wondering, how much processor overhead does UTF8 have? Not just because you can't jump N bytes into a string to get a character offset, but because each byte has to be inspected to find whether it's the start of a multi-byte segment, how many of the subsequent bytes 1-3 are included. Does that mean there's processor branch-prediction fails and stalling every few bytes in processing UTF8 strings with many multibyte characters in them?

chrisseaton 7y ago
What kind of workload are you thinking about, though? Why are you streaming these characters? What processing are you doing that doesn't already have conditional logic for each character?
raphlinus 7y ago
Yes, the variable length nature of UTF-8 generally means more hard-to-predict branches. But sufficiently clever programmers can find ways around that, see Lemire's work on using SIMD to validate UTF-8 very quickly: https://lemire.me/blog/2018/05/16/validating-utf-8-strings-using-as-little-as-0-7-cycles-per-byte/ https://lemire.me/blog/2018/05/16/validating-utf-8-strings-u...
deleted 7y ago
[deleted]
flohofwoe 7y ago
In many cases the string data is copied around as is, iterating over the code points is hardly needed. And since 7-bit ASCII characters still are unique bytes in an UTF-8 encoded stream, common operations like splitting by comma, whitespace, slash etc... works the same as on ASCII strings (e.g. just look at the byte stream for the splitting characters, and keep the byte ranges inbetween intact, no UTF-8 decoding needed).
blattimwind 7y ago
> Not just because you can't jump N bytes into a string to get a character offset I keep hearing people refer to this operation (mostly in HN threads), I have yet to see an appropriate use of it. So far the only uses I've seen were (for Unicode) misguided attempts at character iteration, which doesn't need this at all.
- magicalhippo 7y ago
  At work we have to parse various different fixed-width column files. We only need data from a handful of the columns, so we use the substring function to extract the data we need. Of course these files are so old they predate proper encoding and are implicitly Windows-1252 or similar.
  - ben509 7y ago
    That's been my experience, I've done it but never anything that a scanning or tokenizing algorithm couldn't do. So being able to iterate over characters is important, but constant time access to a specific character seems very rare. I think the only case where I've wanted a specific character was when I wrote games that loaded maps from text files and those were ASCII regardless.
    - magicalhippo 7y ago
      Some of the records are over 1k chars wide, and we need stuff near the end. Though if one had to decode the line from UTF-8, you're iterating anyway so...
      - ben509 7y ago
        I could see a case for it if you were finding line endings in bytes mode, and then casting a buffer to a UTF-8 string. Then you'd benefit from a reverse iterator, which UTF-8 supports just fine. I imagine the main reason people would use indexing is to scan through strings in lockstep, e.g. to implement comparison, but iterators can cover that case as well, especially if you can copy them.
tialaramex 7y ago
> each byte has to be inspected to find whether it's the start of a multi-byte segment, how many of the subsequent bytes 1-3 are included. Mostly no. Or at least, not if the implementation was written by somebody who knows what they're doing. A lot of multi-byte encodings do have the problem you're worried about but UTF-8 does not, and the definition is even careful to make this true if you're processing malformed UTF-8 which may be invalid. The trick is that the bit pattern alone tells you whether this is a trailing byte. Nothing you could be looking for could _begin_ with a trailing byte, they only make sense in trailing position. Whether you are looking for a colon, or an omega, or the dog emoji, any trailing byte won't match.
rurban 7y ago
CPU overhead is nowadays much less important than cache misses. UTF-8 has the least cache misses, Linux/BSD UTF-32 widechars the most, and Windows UCS-2 in between. UTF-32 wchar_t was a gigantic design failure and should have been deprecated a long time ago. There's still no POSIX u8 api in sight. The branch misses are not that high or costly, as most characters don't need the subsequent branches for 2-4 bytes, but cache misses cost ~50x more than a branch miss. And there are enough parallel pipelines now to avoid most utf-8 branch misses. The new massive parallel SIMD ways to process UTF-8 are so fast because the width is so high, 256 bytes per loop, which is enough for most strings. But avoiding branching has some constant overhead to prepare the loops, for small strings it rarely pays off.
kwillets 7y ago
With SSE it's 2.6-3.4 cycles/byte to unpack UTF-8 into UTF-32 (ie integers). See https://github.com/KWillets/fastdecode-utf-8 https://github.com/KWillets/fastdecode-utf-8 . Selection (extracting the i-th element) is actually quite fast, but there's some overhead in grabbing a whole chunk of characters and extracting all their payload bits at once.

chrisseaton 7y ago

What kind of workload are you thinking about, though? Why are you streaming these characters? What processing are you doing that doesn't already have conditional logic for each character?

raphlinus 7y ago

Yes, the variable length nature of UTF-8 generally means more hard-to-predict branches. But sufficiently clever programmers can find ways around that, see Lemire's work on using SIMD to validate UTF-8 very quickly: https://lemire.me/blog/2018/05/16/validating-utf-8-strings-using-as-little-as-0-7-cycles-per-byte/ https://lemire.me/blog/2018/05/16/validating-utf-8-strings-u...

deleted 7y ago

[deleted]

flohofwoe 7y ago

In many cases the string data is copied around as is, iterating over the code points is hardly needed. And since 7-bit ASCII characters still are unique bytes in an UTF-8 encoded stream, common operations like splitting by comma, whitespace, slash etc... works the same as on ASCII strings (e.g. just look at the byte stream for the splitting characters, and keep the byte ranges inbetween intact, no UTF-8 decoding needed).

blattimwind 7y ago

> Not just because you can't jump N bytes into a string to get a character offset I keep hearing people refer to this operation (mostly in HN threads), I have yet to see an appropriate use of it. So far the only uses I've seen were (for Unicode) misguided attempts at character iteration, which doesn't need this at all.

magicalhippo 7y ago
At work we have to parse various different fixed-width column files. We only need data from a handful of the columns, so we use the substring function to extract the data we need. Of course these files are so old they predate proper encoding and are implicitly Windows-1252 or similar.
- ben509 7y ago
  That's been my experience, I've done it but never anything that a scanning or tokenizing algorithm couldn't do. So being able to iterate over characters is important, but constant time access to a specific character seems very rare. I think the only case where I've wanted a specific character was when I wrote games that loaded maps from text files and those were ASCII regardless.
  - magicalhippo 7y ago
    Some of the records are over 1k chars wide, and we need stuff near the end. Though if one had to decode the line from UTF-8, you're iterating anyway so...
    - ben509 7y ago
      I could see a case for it if you were finding line endings in bytes mode, and then casting a buffer to a UTF-8 string. Then you'd benefit from a reverse iterator, which UTF-8 supports just fine. I imagine the main reason people would use indexing is to scan through strings in lockstep, e.g. to implement comparison, but iterators can cover that case as well, especially if you can copy them.

tialaramex 7y ago

> each byte has to be inspected to find whether it's the start of a multi-byte segment, how many of the subsequent bytes 1-3 are included. Mostly no. Or at least, not if the implementation was written by somebody who knows what they're doing. A lot of multi-byte encodings do have the problem you're worried about but UTF-8 does not, and the definition is even careful to make this true if you're processing malformed UTF-8 which may be invalid. The trick is that the bit pattern alone tells you whether this is a trailing byte. Nothing you could be looking for could _begin_ with a trailing byte, they only make sense in trailing position. Whether you are looking for a colon, or an omega, or the dog emoji, any trailing byte won't match.

rurban 7y ago

CPU overhead is nowadays much less important than cache misses. UTF-8 has the least cache misses, Linux/BSD UTF-32 widechars the most, and Windows UCS-2 in between. UTF-32 wchar_t was a gigantic design failure and should have been deprecated a long time ago. There's still no POSIX u8 api in sight. The branch misses are not that high or costly, as most characters don't need the subsequent branches for 2-4 bytes, but cache misses cost ~50x more than a branch miss. And there are enough parallel pipelines now to avoid most utf-8 branch misses. The new massive parallel SIMD ways to process UTF-8 are so fast because the width is so high, 256 bytes per loop, which is enough for most strings. But avoiding branching has some constant overhead to prepare the loops, for small strings it rarely pays off.

kwillets 7y ago

With SSE it's 2.6-3.4 cycles/byte to unpack UTF-8 into UTF-32 (ie integers). See https://github.com/KWillets/fastdecode-utf-8 https://github.com/KWillets/fastdecode-utf-8 . Selection (extracting the i-th element) is actually quite fast, but there's some overhead in grabbing a whole chunk of characters and extracting all their payload bits at once.