3 ms·

You are right. Unicode in UTF-8 will have variable char length. Plain ASCII will be one byte for each char, but others might have up to 4 bytes. Anything deali

You are right. Unicode in UTF-8 will have variable char length. Plain ASCII will be one byte for each char, but others might have up to 4 bytes. Anything dealing with it will have to be aware of leading bytes. UTF-32 in other hand will encode all chars, even plain ASCII ones, using 4 bytes. Take the "length of a string" function, for example. Porting that from ASCII to UTF-32 is just dividing the length in bytes by 4. For UTF-8, you'd have to iterate over each character and figure out if there is a combination of bytes that collapse into a single character.

adambatkin 4y ago
Take a step back and ask "why do I need to know the length of this thing?" If it's so you know how much storage to allocate, then the process/time is the same for both (the answer is: however many bytes you happen to have). If your array is bigger than the number of valid characters (code points) and you need to search through it to find the "end" (last valid character), you can do that with almost identical complexity (you don't actually need to iterate over ever byte and Code Point with UTF-8 because of how elegantly the encoding was designed). Why else might you need to know the length? If it's to know how much space to allocate in a GUI (or even on a console) then neither encoding is going to help. Maybe it's because of some arbitrary limitation like "your name must be less than 50 characters" and I'll just say that if that's the case, you are doing it wrong (if you need to limit it for storage/efficiency purposes, fine, but you will probably be better off limiting by bytes and using UTF-8 since most people will be able to squeeze in more of their names). I'm not saying there aren't reasons for needing to know the "length" (number of Code Points) of a string, and certainly many existing algorithms are written in a way that they assume that calculating string length and being able index arbitrarily into the middle of a string are fast (O( 1 ) for indexing) but in reality, for almost any real world problem beyond "how much storage do I need" almost everything you need to do actually requires iterating over a string one Code Point at a time (which is O( n ) for both, with the biggest difference being that UTF-8 may require more branching, but also it's common enough that in many cases between vectorization and just generally better optimizations because of it's popularity, UTF-8 will do just fine while usually using less storage, which can significantly benefit CPU cache locality).
- alganet 4y ago
  It needs the length for operations such as substring, or to apply length modifiers on regular expressions (such as \w{3,5}), which is a common thing in awk programs. In fact, the return value of the u8_rune as implemented in the branch we are discussing (https://github.com/onetrueawk/awk/compare/unicode-support https://github.com/onetrueawk/awk/compare/unicode-support) returns a length to be used as an offset later. This is not me saying, it's the author. There is a code comment there: > For most of Awk, utf-8 strings just "work", since they look like null-terminated sequences of 8-bit bytes. Functions like length(), index(), and substr() have to operate in units of utf-8 characters. The u8_* functions in run.c handle this. I know there might be different ways of doing it, but we're talking about a specific implementation. I was wrong to assume he is storing stuff in UTF-32. He could have, but there was already code in place there to make the UTF-8 storage easier to implement.
jsjohnst 4y ago
> Porting that from ASCII to UTF-32 is just dividing the length in bytes by 4. For UTF-8, you'd have to iterate over each character and figure out if there is a combination of bytes that collapse into a single character. You have to do that with UTF-32 as well. Yes, every codepoint is 32 bits, but every character can be made up of one or more codepoints.
- alganet 4y ago
  What? U+004D in UTF-8 is 4D, in UTF-32 is 0000004D U+0430 in UTF-8 is D0 B0, in UTF-32 is 00000430 I took this examples from page 102 of The Unicode Standard Version 5.0. These leading zeros on the UTF-32 are what is omitted from UTF-8. One of the encodings is optimized for space, the other for processing speed. I am no expert on unicode though, there might be something I'm missing (ligatures, this kind of stuff). I would gladly accept a more in depth expalanation on why I am wrong on this.
  - bzxcvbn 4y ago
    The letter à can be represented in two different ways in Unicode: * As the single code point U+00E0, which encodes 'à'. * Or as the sequence of two code points U+0061 U+0300, which respectively encode the Latin letter 'a' and the combining acute accent (it's hard to display as a standalone character, so go e.g. here: https://www.compart.com/fr/unicode/U+0300 https://www.compart.com/fr/unicode/U+0300). These two code points get combined into a single grapheme cluster, the technical name for what most people consider to be a character, that displays as 'à'. As you can see, there is no difference in the visual representation of à and à. But if you inspect the string (in python or whatever) then you'll see that one of them has one code point (one "char"), while the second has two. If you're on Windows, an easy way is to type it into pwsh: PS> 'à'.EnumerateRunes() | % { "U+{0:X4}" -f $_.Value } U+0061 U+0300 PS> 'à'.EnumerateRunes() | % { "U+{0:X4}" -f $_.Value } U+00E0
    - alganet 4y ago
      The character "à" as a single byte E0, as far as I know, is not UTF-8. This is the 224th character of the extended ASCII table (also ISO 8859). It's another system: https://en.wikipedia.org/wiki/Extended_ASCII https://en.wikipedia.org/wiki/Extended_ASCII This representation is incompatible with UTF-8, which marks the octet series Cx, Dx, Ex and Fx as leading bytes. You can see the table here: https://en.wikipedia.org/wiki/UTF-8#Codepage_layout https://en.wikipedia.org/wiki/UTF-8#Codepage_layout What I believe Kernighan _wants_, is to reuse a lot of code that was designed for ASCII. Code that treats 1 char as 1 byte. In order to do that, he is going to encode each unicode character using 4 of whatever type he was previously using before, zeroing the "pad" bytes, which is exactly what UTF-32 does. This way, he doesn't have to fundamentally change all the types he is already working with. (ps: I looked at the commit after I wrote this, he doesn't seem to be doing what I suggested). Your PS snippet failed for me "Method invocation failed because [System.String] does not contain a method named 'EnumerateRunes'." Dit it in bash, which supports UTF-8 and lets you explicitly set the encoding: $ LC_ALL=C bash -c 'x=à; echo ${#x}' 2 $ LC_ALL=en_US.UTF-8 bash -c 'x=à; echo ${#x}' 1 These snippets count the number of chars according to the selected encoding. If I had UTF-32 locales in my machine, "à" would appear as 4. Unfortunatelly I don't know any system that implements UTF-32 to display its behavior. Let's now reconstruct "à" in UTF-8, telling bash to use only ASCII: $ LC_ALL=C bash -c 'printf %b \\xC3\\xA0' à I've tunneled UTF-8 through an ASCII program, and because my terminal accepts UTF-8, everything is fine. Didn't even had to use \u escapes. This backwards compatibility is by design, and chosing between UTF-8, 16 and 32 plays a role in how you're going to deal with these byte sequences.

adambatkin 4y ago

Take a step back and ask "why do I need to know the length of this thing?" If it's so you know how much storage to allocate, then the process/time is the same for both (the answer is: however many bytes you happen to have). If your array is bigger than the number of valid characters (code points) and you need to search through it to find the "end" (last valid character), you can do that with almost identical complexity (you don't actually need to iterate over ever byte and Code Point with UTF-8 because of how elegantly the encoding was designed). Why else might you need to know the length? If it's to know how much space to allocate in a GUI (or even on a console) then neither encoding is going to help. Maybe it's because of some arbitrary limitation like "your name must be less than 50 characters" and I'll just say that if that's the case, you are doing it wrong (if you need to limit it for storage/efficiency purposes, fine, but you will probably be better off limiting by bytes and using UTF-8 since most people will be able to squeeze in more of their names). I'm not saying there aren't reasons for needing to know the "length" (number of Code Points) of a string, and certainly many existing algorithms are written in a way that they assume that calculating string length and being able index arbitrarily into the middle of a string are fast (O( 1 ) for indexing) but in reality, for almost any real world problem beyond "how much storage do I need" almost everything you need to do actually requires iterating over a string one Code Point at a time (which is O( n ) for both, with the biggest difference being that UTF-8 may require more branching, but also it's common enough that in many cases between vectorization and just generally better optimizations because of it's popularity, UTF-8 will do just fine while usually using less storage, which can significantly benefit CPU cache locality).

alganet 4y ago
It needs the length for operations such as substring, or to apply length modifiers on regular expressions (such as \w{3,5}), which is a common thing in awk programs. In fact, the return value of the u8_rune as implemented in the branch we are discussing (https://github.com/onetrueawk/awk/compare/unicode-support https://github.com/onetrueawk/awk/compare/unicode-support) returns a length to be used as an offset later. This is not me saying, it's the author. There is a code comment there: > For most of Awk, utf-8 strings just "work", since they look like null-terminated sequences of 8-bit bytes. Functions like length(), index(), and substr() have to operate in units of utf-8 characters. The u8_* functions in run.c handle this. I know there might be different ways of doing it, but we're talking about a specific implementation. I was wrong to assume he is storing stuff in UTF-32. He could have, but there was already code in place there to make the UTF-8 storage easier to implement.

jsjohnst 4y ago

> Porting that from ASCII to UTF-32 is just dividing the length in bytes by 4. For UTF-8, you'd have to iterate over each character and figure out if there is a combination of bytes that collapse into a single character. You have to do that with UTF-32 as well. Yes, every codepoint is 32 bits, but every character can be made up of one or more codepoints.

alganet 4y ago
What? U+004D in UTF-8 is 4D, in UTF-32 is 0000004D U+0430 in UTF-8 is D0 B0, in UTF-32 is 00000430 I took this examples from page 102 of The Unicode Standard Version 5.0. These leading zeros on the UTF-32 are what is omitted from UTF-8. One of the encodings is optimized for space, the other for processing speed. I am no expert on unicode though, there might be something I'm missing (ligatures, this kind of stuff). I would gladly accept a more in depth expalanation on why I am wrong on this.
- bzxcvbn 4y ago
  The letter à can be represented in two different ways in Unicode: * As the single code point U+00E0, which encodes 'à'. * Or as the sequence of two code points U+0061 U+0300, which respectively encode the Latin letter 'a' and the combining acute accent (it's hard to display as a standalone character, so go e.g. here: https://www.compart.com/fr/unicode/U+0300 https://www.compart.com/fr/unicode/U+0300). These two code points get combined into a single grapheme cluster, the technical name for what most people consider to be a character, that displays as 'à'. As you can see, there is no difference in the visual representation of à and à. But if you inspect the string (in python or whatever) then you'll see that one of them has one code point (one "char"), while the second has two. If you're on Windows, an easy way is to type it into pwsh: PS> 'à'.EnumerateRunes() | % { "U+{0:X4}" -f $_.Value } U+0061 U+0300 PS> 'à'.EnumerateRunes() | % { "U+{0:X4}" -f $_.Value } U+00E0
  - alganet 4y ago
    The character "à" as a single byte E0, as far as I know, is not UTF-8. This is the 224th character of the extended ASCII table (also ISO 8859). It's another system: https://en.wikipedia.org/wiki/Extended_ASCII https://en.wikipedia.org/wiki/Extended_ASCII This representation is incompatible with UTF-8, which marks the octet series Cx, Dx, Ex and Fx as leading bytes. You can see the table here: https://en.wikipedia.org/wiki/UTF-8#Codepage_layout https://en.wikipedia.org/wiki/UTF-8#Codepage_layout What I believe Kernighan _wants_, is to reuse a lot of code that was designed for ASCII. Code that treats 1 char as 1 byte. In order to do that, he is going to encode each unicode character using 4 of whatever type he was previously using before, zeroing the "pad" bytes, which is exactly what UTF-32 does. This way, he doesn't have to fundamentally change all the types he is already working with. (ps: I looked at the commit after I wrote this, he doesn't seem to be doing what I suggested). Your PS snippet failed for me "Method invocation failed because [System.String] does not contain a method named 'EnumerateRunes'." Dit it in bash, which supports UTF-8 and lets you explicitly set the encoding: $ LC_ALL=C bash -c 'x=à; echo ${#x}' 2 $ LC_ALL=en_US.UTF-8 bash -c 'x=à; echo ${#x}' 1 These snippets count the number of chars according to the selected encoding. If I had UTF-32 locales in my machine, "à" would appear as 4. Unfortunatelly I don't know any system that implements UTF-32 to display its behavior. Let's now reconstruct "à" in UTF-8, telling bash to use only ASCII: $ LC_ALL=C bash -c 'printf %b \\xC3\\xA0' à I've tunneled UTF-8 through an ASCII program, and because my terminal accepts UTF-8, everything is fine. Didn't even had to use \u escapes. This backwards compatibility is by design, and chosing between UTF-8, 16 and 32 plays a role in how you're going to deal with these byte sequences.