7 ms·

UCS vs. UTF-8 as Internal String Encoding

37 points by romeoonisim 11y ago

TazeTSchnitzel 11y ago
The only reason UTF-16 was so widely used is as a backwards-compatibility measure. All these systems originated in the UCS-2 era, or had to be compatible with ones which did. Then UTF-16 came along, and slotted in where UCS-2 was. This is why you have such sloppiness about treating surrogate pairs as two characters, for instance: the systems were made for UCS-2 and only poorly updated to the UTF-16 reality. Any modern system would use UTF-8.
TazeTSchnitzel 11y ago
Something I've wondered about is why, given Unicode is limited to 21 bits now, nobody seems to be using a 24-bit format ("UTF-24")? If you want constant-time indexing without bit-packing tricks, that'd be the ideal. Though, of course, constant-time indexing isn't what it's hyped up to be. That's only for codepoints. Actual characters you see on screen are often combinations of codepoints. So I've answered my own question really. Why does nobody use it? Because there's no point in it. http://stackoverflow.com/questions/10143836/why-is-there-no-utf-24 http://stackoverflow.com/questions/10143836/why-is-there-no-...
- protomyth 11y ago
  "That's only for codepoints. Actual characters you see on screen are often combinations of codepoints." So, there is no encoding that actually has 1 word (of whatever byte length) to a character on the screen?
  - colanderman 11y ago
    You might be interested in the Supercombiner: http://sbp.so/supercombiner http://sbp.so/supercombiner
    - Aardwolf 11y ago
      What language uses that many diacritics tho? Unicode is supposed to support all written languages - supporting a u with 100 diacritics seems beyond that scope :)
      - colanderman 11y ago
        Mathematics. Not 100, but symbols are often decorated with 3 diacritics or so. That's a lot to cram into one fixed-size word.
  - gsnedders 11y ago
    There's an unbounded number of possible graphemes per Unicode, because they are formed of a start character and an unbounded number of combining characters following them. As such, no fixed-length encoding can actually enumerate all possible graphemes.
    - protomyth 11y ago
      What is the practicality of an unbounded number of possible graphemes? Does anyone in real writing of languages and not some concocted test case need this? I understood there is some conflict in the encoding of kanji into unicode, does this relate?
      - masklinn 11y ago
        > What is the practicality of an unbounded number of possible graphemes? That question doesn't really make sense. Unbounded cluster sizes is simply a result of unicode design because there's no reason to bound it. > Does anyone in real writing of languages and not some concocted test case need this? In the real writing of languages there are languages with grapheme clusters of size 4+ e.g. क्षि (Devanagari kshi) is a single cluster made up of क, ्, ष and ि. > I understood there is some conflict in the encoding of kanji into unicode, does this relate? It's unrelated. Han Unification compressed the number of clusters by unifying han characters across simplified Chinese, traditional Chinese, Japanese and Korean. Han characters were an issue in the original 16 bits unicode because supporting all of them was estimated as possibly topping out 100,000 codepoints (where 16 bits unicode only supported 65k codepoints). AFAIK Han characters don't use much if any composition (outside of romanisation). Brahmic scripts, Hebrew and Arabic scripts, on the other hand, pile on diacritics.
        protomyth 11y ago
        > That question doesn't really make sense. Unbounded cluster sizes is simply a result of unicode design because there's no reason to bound it. If I'm trying to draw a character on the screen, it makes a lot of sense. I guess I'm struck about how hard it would be to select the 4th through 8th character displayed on the screen from rows 3 through 13.
- vbezhenar 11y ago
  The main problem is that a lot of characters in real world are from ASCII part. So for 24-bit 66% of memory space will be wasted. And it's bad not only because it uses RAM, HDD, bandwidth, but generally because it uses precious processor cache storage.
  - derefr 11y ago
    Given an efficient string processing methodology mostly consisting of 1. holding onto opaque string binaries until you need to compose them all together at the end (i.e. the way Erlang's iolists work) and 2. applying encapsulated operations over a given string (e.g. "split", "scan with regular expression") rather than trying to index into it; I've never understood why we can't just use a really inefficient-but-practical string encoding, e.g. UTF-32, with a very low-cost stream compression algorithm on top.
    - vardump 11y ago
      > I've never understood why we can't just use a really inefficient-but-practical string encoding, e.g. UTF-32, with a very low-cost stream compression algorithm on top. That's right. We could figure out how to represent common characters with less bits. For low-cost character stream compression, byte granularity should work nicely with computers, so we should it. A byte could have a bit that indicates the range is extended, like highest bit, because it's easy to process. Same idea could be chained to represent full range of unicode characters. That way we'd have compressed UTF-32 characters!
      - derefr 11y ago
        I meant more something like RLE or simple Huffman encoding. A "string" type like Redis's dict type or ObjC's array type, where the internal representation changes as the allocated object grows in size and therefore is worth making different trade-offs on. (So, a five-byte string, maybe UTF-8 is a fine encoding. A 3KB string? Worth prepending a compression dictionary to.)
- tormeh 11y ago
  Why not have an array of pointers to an array each, where each pointed-to array holds a single character?
- vardump 11y ago
  24-bit and 21-bit format wouldn't have much difference in terms of performance of constant time indexing. Strlen (for storage space) would be dramatically slower than in any other format.
  - TazeTSchnitzel 11y ago
    Would it really? You can still use SIMD and vectorise.
    - vardump 11y ago
      I don't immediately know how to use SIMD to scan for 24-bit wide zero terminator or for any character for that matter. 128/24 is 5 1/3 or 5.333... Alignment would mean a lot of slow operations to stitch data between memory loads. How would you efficiently scan for a specific 24-bit character by using SIMD? Say you're not running on Haswell, but something older that's not as good with unaligned memory accesses?
userbinator 11y ago
"UTF-24" feels like the right choice for an internal format if you want true constant-time access to code points with 25% less waste than UTF-32. I know it's not a power of 2, and that's the most common reason cited against using it, but multiplying by 3 is basically n + 2n or a shift-and-add so it's not really hard to do.
- vbezhenar 11y ago
  reading or writing arr[i] will require 1 or 2 4-byte memory accesses (or 3 1-byte memory accesses) and few bit operations to construct result value, because generally processors can't access 24-bit value. That probably won't hurt performance a lot, but anyway it's much easier to work with 32-bit arrays.
  - TazeTSchnitzel 11y ago
    Or, it requires a 2-byte memory access and a 1-byte memory access.
    - vardump 11y ago
      Modern CPUs have only one sort of accesses from RAM. 64 byte ones.
- lambda 11y ago
  Why would you want constant time access to code points? What can you do with constant time access to code points that is actually correct? Every time someone tries to promote UTF-16, UTF-32, or some imagined encoding like UTF-24, they bring up constant time access to code points, but I have never heard of a reason why you would want that. Pretty much every use case I have ever heard for constant-time access can be handled just as well by constant-time access at the code unit (byte in UTF-8, 16 bit value in UTF-16, 32 bit value in UTF-32) level. Matching text exactly? Matching works just as well at the code unit level. Doing any kind of fuzzy or regular expression match? You're going to need to iterate over each item anyhow to normalize it or classify it. Need to store offsets? That works just fine at the code unit level. Most of the other suggestions I've heard for what to do with constant-time access to code points is incorrect when you consider combining characters, normalization, different character widths, need for linguistically appropriate word splitting, etc. If you're doing something that doesn't take these into account, why are you using Unicode instead of just ASCII? In addition, for the ASCII range, UTF-24 would take up 3 times the space as UTF-8, and the vast majority of text processed is actually in the ASCII range due to verbose markup formats like HTML, XML, etc. Plus if you do anything with the code points in UTF-24, you need to do a bunch of bit-fiddling to move them into 32 bit alignment, so as far as actually decoding the individual code points, it's pretty much a wash with UTF-8.
rectang 11y ago
Random-access idioms where unicode strings are treated as arrays of character data will result in userland code which is either incorrect or inefficient. Incorrect if the implementation cheats and treats variable-width data as constant-width, resulting in severing of logical units and incorrect length values. Inefficient, if each random-access operation counts variable-width elements from the beginning of the string. It is better to provide string-manipulation facilities which rely on iteration and keep track of offset internally. For an extended explanation, see Tom Christiansen's comment on this old Python issue: http://bugs.python.org/issue12729#msg142036 http://bugs.python.org/issue12729#msg142036
- derefr 11y ago
  How about a higher datatype abstraction, where you have a random-access array of glyphs that can be one or more composed unicode characters, each of which can be variable-length?
  - masklinn 11y ago
    Assuming by glyph you mean grapheme cluster (a glyph is something displayed on screen, talking about accessing glyphs makes absolutely no sense) there are issues with that: 1. you're added a layer of complexity to the system because now your strings are all rope-like, except they're not arbitrarily nested so they don't have the IO and compositional advantages of ropes 2. Unicode provides 3 classes of grapheme clusters (legacy, extended and tailored) at least one of which (tailored) is locale-dependent (`ch` is a single tailored grapheme cluster under the Slovak locale, because it's the ch digraph)
    - derefr 11y ago
      Both of these things are necessary, in the end, for the controller backing any text-editing control, right? A text-editing control is thinking in terms of "grapheme clusters", not in terms of codepoints. The codepoints come out of it when you ask it to export its current value, but otherwise, for layout and such, it's holding on to the moral equivalent of typesetting dice. And, philosophically, I'd say that something close to (but not quite) this, is what people want to know from a lot of systems when they ask for a string's "length." They don't care how much memory the string is taking up (though they can have some low-level assertions to that effect); they care about whether the supplied text will fit in a given em-width container, or a given number of form blanks. This is what Twitter actually cares about these days; this is what wc(1) or Microsoft Word wants to tell you when you look at "character count"; this is what ncurses thinks in terms of in order to lay out monospaced text between various borders. Now, ligatures and digraphs are a slight problem, in that people think of ﬂ/ﬁ/etc. as two characters, even if they are visually composed of one, but they don't think of, for example, ß as two characters. Thus why I said "glyph"—people expect "ss" to be two glyphs; "ﬁ" to be two glyphs, and "ß" to be one glyph. On the other hand, they expect diacritics added to any of those things to not add any additional glyphs, even if they introduce kerning; the Japanese http://en.wikipedia.org/wiki/Sokuon http://en.wikipedia.org/wiki/Sokuon, for example, is part of the glyph that follows it, even though it makes the word wider. It's not a presentation-level characteristic, it's a "the way humans count things on the page" characteristic. But you can very easily build the presentation-level characteristic (grapheme cluster length) from it. Which is all to say, maybe raw Unicode strings are good for systems languages—but in my day-to-day programming solving business-domain problems, I'd much rather be using a "text library" that provides "text objects" with a length measured in glyphs.

37 points by romeoonisim 11y ago

The only reason UTF-16 was so widely used is as a backwards-compatibility measure. All these systems originated in the UCS-2 era, or had to be compatible with ones which did. Then UTF-16 came along, and slotted in where UCS-2 was. This is why you have such sloppiness about treating surrogate pairs as two characters, for instance: the systems were made for UCS-2 and only poorly updated to the UTF-16 reality. Any modern system would use UTF-8.

TazeTSchnitzel 11y ago

Something I've wondered about is why, given Unicode is limited to 21 bits now, nobody seems to be using a 24-bit format ("UTF-24")? If you want constant-time indexing without bit-packing tricks, that'd be the ideal. Though, of course, constant-time indexing isn't what it's hyped up to be. That's only for codepoints. Actual characters you see on screen are often combinations of codepoints. So I've answered my own question really. Why does nobody use it? Because there's no point in it. http://stackoverflow.com/questions/10143836/why-is-there-no-utf-24 http://stackoverflow.com/questions/10143836/why-is-there-no-...

protomyth 11y ago
"That's only for codepoints. Actual characters you see on screen are often combinations of codepoints." So, there is no encoding that actually has 1 word (of whatever byte length) to a character on the screen?
- colanderman 11y ago
  You might be interested in the Supercombiner: http://sbp.so/supercombiner http://sbp.so/supercombiner
  - Aardwolf 11y ago
    What language uses that many diacritics tho? Unicode is supposed to support all written languages - supporting a u with 100 diacritics seems beyond that scope :)
    - colanderman 11y ago
      Mathematics. Not 100, but symbols are often decorated with 3 diacritics or so. That's a lot to cram into one fixed-size word.
- gsnedders 11y ago
  There's an unbounded number of possible graphemes per Unicode, because they are formed of a start character and an unbounded number of combining characters following them. As such, no fixed-length encoding can actually enumerate all possible graphemes.
  - protomyth 11y ago
    What is the practicality of an unbounded number of possible graphemes? Does anyone in real writing of languages and not some concocted test case need this? I understood there is some conflict in the encoding of kanji into unicode, does this relate?
    - masklinn 11y ago
      > What is the practicality of an unbounded number of possible graphemes? That question doesn't really make sense. Unbounded cluster sizes is simply a result of unicode design because there's no reason to bound it. > Does anyone in real writing of languages and not some concocted test case need this? In the real writing of languages there are languages with grapheme clusters of size 4+ e.g. क्षि (Devanagari kshi) is a single cluster made up of क, ्, ष and ि. > I understood there is some conflict in the encoding of kanji into unicode, does this relate? It's unrelated. Han Unification compressed the number of clusters by unifying han characters across simplified Chinese, traditional Chinese, Japanese and Korean. Han characters were an issue in the original 16 bits unicode because supporting all of them was estimated as possibly topping out 100,000 codepoints (where 16 bits unicode only supported 65k codepoints). AFAIK Han characters don't use much if any composition (outside of romanisation). Brahmic scripts, Hebrew and Arabic scripts, on the other hand, pile on diacritics.
      - protomyth 11y ago
        > That question doesn't really make sense. Unbounded cluster sizes is simply a result of unicode design because there's no reason to bound it. If I'm trying to draw a character on the screen, it makes a lot of sense. I guess I'm struck about how hard it would be to select the 4th through 8th character displayed on the screen from rows 3 through 13.
vbezhenar 11y ago
The main problem is that a lot of characters in real world are from ASCII part. So for 24-bit 66% of memory space will be wasted. And it's bad not only because it uses RAM, HDD, bandwidth, but generally because it uses precious processor cache storage.
- derefr 11y ago
  Given an efficient string processing methodology mostly consisting of 1. holding onto opaque string binaries until you need to compose them all together at the end (i.e. the way Erlang's iolists work) and 2. applying encapsulated operations over a given string (e.g. "split", "scan with regular expression") rather than trying to index into it; I've never understood why we can't just use a really inefficient-but-practical string encoding, e.g. UTF-32, with a very low-cost stream compression algorithm on top.
  - vardump 11y ago
    > I've never understood why we can't just use a really inefficient-but-practical string encoding, e.g. UTF-32, with a very low-cost stream compression algorithm on top. That's right. We could figure out how to represent common characters with less bits. For low-cost character stream compression, byte granularity should work nicely with computers, so we should it. A byte could have a bit that indicates the range is extended, like highest bit, because it's easy to process. Same idea could be chained to represent full range of unicode characters. That way we'd have compressed UTF-32 characters!
    - derefr 11y ago
      I meant more something like RLE or simple Huffman encoding. A "string" type like Redis's dict type or ObjC's array type, where the internal representation changes as the allocated object grows in size and therefore is worth making different trade-offs on. (So, a five-byte string, maybe UTF-8 is a fine encoding. A 3KB string? Worth prepending a compression dictionary to.)
tormeh 11y ago
Why not have an array of pointers to an array each, where each pointed-to array holds a single character?
vardump 11y ago
24-bit and 21-bit format wouldn't have much difference in terms of performance of constant time indexing. Strlen (for storage space) would be dramatically slower than in any other format.
- TazeTSchnitzel 11y ago
  Would it really? You can still use SIMD and vectorise.
  - vardump 11y ago
    I don't immediately know how to use SIMD to scan for 24-bit wide zero terminator or for any character for that matter. 128/24 is 5 1/3 or 5.333... Alignment would mean a lot of slow operations to stitch data between memory loads. How would you efficiently scan for a specific 24-bit character by using SIMD? Say you're not running on Haswell, but something older that's not as good with unaligned memory accesses?

userbinator 11y ago

"UTF-24" feels like the right choice for an internal format if you want true constant-time access to code points with 25% less waste than UTF-32. I know it's not a power of 2, and that's the most common reason cited against using it, but multiplying by 3 is basically n + 2n or a shift-and-add so it's not really hard to do.

vbezhenar 11y ago
reading or writing arr[i] will require 1 or 2 4-byte memory accesses (or 3 1-byte memory accesses) and few bit operations to construct result value, because generally processors can't access 24-bit value. That probably won't hurt performance a lot, but anyway it's much easier to work with 32-bit arrays.
- TazeTSchnitzel 11y ago
  Or, it requires a 2-byte memory access and a 1-byte memory access.
  - vardump 11y ago
    Modern CPUs have only one sort of accesses from RAM. 64 byte ones.
lambda 11y ago
Why would you want constant time access to code points? What can you do with constant time access to code points that is actually correct? Every time someone tries to promote UTF-16, UTF-32, or some imagined encoding like UTF-24, they bring up constant time access to code points, but I have never heard of a reason why you would want that. Pretty much every use case I have ever heard for constant-time access can be handled just as well by constant-time access at the code unit (byte in UTF-8, 16 bit value in UTF-16, 32 bit value in UTF-32) level. Matching text exactly? Matching works just as well at the code unit level. Doing any kind of fuzzy or regular expression match? You're going to need to iterate over each item anyhow to normalize it or classify it. Need to store offsets? That works just fine at the code unit level. Most of the other suggestions I've heard for what to do with constant-time access to code points is incorrect when you consider combining characters, normalization, different character widths, need for linguistically appropriate word splitting, etc. If you're doing something that doesn't take these into account, why are you using Unicode instead of just ASCII? In addition, for the ASCII range, UTF-24 would take up 3 times the space as UTF-8, and the vast majority of text processed is actually in the ASCII range due to verbose markup formats like HTML, XML, etc. Plus if you do anything with the code points in UTF-24, you need to do a bunch of bit-fiddling to move them into 32 bit alignment, so as far as actually decoding the individual code points, it's pretty much a wash with UTF-8.

rectang 11y ago

Random-access idioms where unicode strings are treated as arrays of character data will result in userland code which is either incorrect or inefficient. Incorrect if the implementation cheats and treats variable-width data as constant-width, resulting in severing of logical units and incorrect length values. Inefficient, if each random-access operation counts variable-width elements from the beginning of the string. It is better to provide string-manipulation facilities which rely on iteration and keep track of offset internally. For an extended explanation, see Tom Christiansen's comment on this old Python issue: http://bugs.python.org/issue12729#msg142036 http://bugs.python.org/issue12729#msg142036

derefr 11y ago
How about a higher datatype abstraction, where you have a random-access array of glyphs that can be one or more composed unicode characters, each of which can be variable-length?
- masklinn 11y ago
  Assuming by glyph you mean grapheme cluster (a glyph is something displayed on screen, talking about accessing glyphs makes absolutely no sense) there are issues with that: 1. you're added a layer of complexity to the system because now your strings are all rope-like, except they're not arbitrarily nested so they don't have the IO and compositional advantages of ropes 2. Unicode provides 3 classes of grapheme clusters (legacy, extended and tailored) at least one of which (tailored) is locale-dependent (`ch` is a single tailored grapheme cluster under the Slovak locale, because it's the ch digraph)
  - derefr 11y ago
    Both of these things are necessary, in the end, for the controller backing any text-editing control, right? A text-editing control is thinking in terms of "grapheme clusters", not in terms of codepoints. The codepoints come out of it when you ask it to export its current value, but otherwise, for layout and such, it's holding on to the moral equivalent of typesetting dice. And, philosophically, I'd say that something close to (but not quite) this, is what people want to know from a lot of systems when they ask for a string's "length." They don't care how much memory the string is taking up (though they can have some low-level assertions to that effect); they care about whether the supplied text will fit in a given em-width container, or a given number of form blanks. This is what Twitter actually cares about these days; this is what wc(1) or Microsoft Word wants to tell you when you look at "character count"; this is what ncurses thinks in terms of in order to lay out monospaced text between various borders. Now, ligatures and digraphs are a slight problem, in that people think of ﬂ/ﬁ/etc. as two characters, even if they are visually composed of one, but they don't think of, for example, ß as two characters. Thus why I said "glyph"—people expect "ss" to be two glyphs; "ﬁ" to be two glyphs, and "ß" to be one glyph. On the other hand, they expect diacritics added to any of those things to not add any additional glyphs, even if they introduce kerning; the Japanese http://en.wikipedia.org/wiki/Sokuon http://en.wikipedia.org/wiki/Sokuon, for example, is part of the glyph that follows it, even though it makes the word wider. It's not a presentation-level characteristic, it's a "the way humans count things on the page" characteristic. But you can very easily build the presentation-level characteristic (grapheme cluster length) from it. Which is all to say, maybe raw Unicode strings are good for systems languages—but in my day-to-day programming solving business-domain problems, I'd much rather be using a "text library" that provides "text objects" with a length measured in glyphs.