5 ms·

But as lambda points out, that offset could be measured in code units rather than code points. You still don't need random access into variable-width data.

by rectang 11y ago

lisper 11y ago
Read what I wrote more carefully. You have to take that offset, represent it somehow, and then pass that representation off to another part of the code, which then uses that representation to access the part of the string that was found earlier. How do you do that without forcing a re-scan when the only facility that the language provides for accessing a character in a string requires you to represent the location of that character as an integer? Actually, you can do it in C because you can use a raw pointer, but that is fraught with all manner of other perils.
- jcranmer 11y ago
  Just use the octet index instead of the code point index. To use UTF-8-based strings, you do need to distinguish between octet indexes (calling them iterators is probably saner to most people) and character indexes. With UCS-4 (and UCS-2 as implemented in practice), the iterator representation and character index are the same, which makes retrofitting those implementations to use UTF-8-based strings impossible. But for new environments, where UCS-2-backwards-compatibility isn't a requirement, it's not hard to make a string API that properly exposes the difference between iterators and character indexes, which is why newer environments are gravitating towards UTF-8 strings.
  - lisper 11y ago
    > Just use the octet index instead of the code point index. And how, exactly, are you going to do that in any extant programming language other than C or assembler?
    - lambda 11y ago
      This discussion is about what encoding is best to choose for the low-level string types in languages and libraries, as that's what the original article was about. If your language already uses a Unicode-compatible string type, you should probably use that. If you are designing a new language, rewriting a language's basic string primitives, or writing an API or application in a language that doesn't have a well-standardized Unicode string type like C or C++, then it is probably better to pick UTF-8; if your app is necessarily single platform and tied to a platform API, choose that API's encoding, but for anything cross platform, the encoding is going to differ between the platforms so choosing UTF-8 and then transcoding at the API boundaries on the different platforms is fine. By the way, most languages do have the concept of a byte array, and you can provide UTF-8 string operations on top of that; but as I said, in general, you should be using the language's native string type unless you have a very good reason not to. The original article that we're discussing does mention one of those very good reasons; in Python, it uses an 8-bit Latin-1 encoding if the characters can fit, upgrades to 16-bit UCS-2 if they can fit in that range, and finally upgrades to 32-bit UTF-32 if they don't fit in the UCS-2 range. But that means that if you're appending strings, and one of them contains an emoji (for instance, in a web templating system that encounters an emoji in a comment), that can mean that all of a sudden your string has to grow to four times its original size, which can cause serious problems; so one workaround for that may be to actually write everything out to a UTF-8 encoded string (which in Python can be represented as a byte array) rather than trying to append strings together and hitting that behavior. Furthermore, several languages already do use UTF-8 as their internal string type; Rust, Go, and Ruby all use UTF-8 as their default or only string type. And by the way, Rust and Go both use slices to handle the use case you describe; a slice is represented as a pointer to the first byte of interest, and a number representing how many bytes it extends. I don't know about in Go, but in Rust the API guarantees that all string slices created from a string begin and end on proper codepoint boundaries. Go: https://blog.golang.org/slices https://blog.golang.org/slices, Rust: https://doc.rust-lang.org/std/primitive.str.html https://doc.rust-lang.org/std/primitive.str.html.
      - lisper 11y ago
        I think we're in violent agreement here. Keep in mind that the question I was responding to was: > Why would you want constant time access to code points? And the answer is: because you might want to compute an offset into a string in one place in your code, and then use that offset to access the string at that offset somewhere else in your code in constant time.
- TheCoelacanth 11y ago
  Why couldn't the string implementation simply provide a string offset class? Internally, it could be represented as a byte offset but at the point of use it wouldn't have to know that.
  - lisper 11y ago
    Yes, this is the Right Thing. But don't forget the question I was responding to: > Why would you want constant time access to code points? The answer is: because you might want to compute an offset into a string in one place in your code, and then pass that offset to another place in your code which then accesses the string at that offset in constant time. My point is that to make this work you must have string offset be an abstract class, not an integer.
    - TheCoelacanth 11y ago
      It only has to be an abstract class if you want to prevent the existence of invalid offsets, but the same is true if you have constant width code points. For instance, INT_MAX is not a valid offset into almost any string.
      - lisper 11y ago
        > It only has to be an abstract class if you want to prevent the existence of invalid offsets Wouldn't you want that? I would. > the same is true if you have constant width code points True, but the validity check for the constant-width case can be done in constant time.
        TheCoelacanth 11y ago
        > True, but the validity check for the constant-width case can be done in constant time. The same is true of UTF-8 because it is self-synchronizing. You only have to check that the byte at the given offset is either 0xxxxxxx or 11xxxxxx.
        11y ago
- wtetzner 11y ago
  Notice he said code units, not code points. Code units are fixed size. So for example, in Java, you have 16-bit code units, and have constant time indexing into them. So you could use a BreakIterator [1] to iterate through grapheme clusters. The iterator returns the index to the cluster though, not the cluster itself. The index is in terms of code units, not in terms of grapheme clusters. [1] https://docs.oracle.com/javase/6/docs/api/java/text/BreakIterator.html https://docs.oracle.com/javase/6/docs/api/java/text/BreakIte...

But as lambda points out, that offset could be measured in code units rather than code points. You still don't need random access into variable-width data.

by rectang 11y ago

But as lambda points out, that offset could be measured in code units rather than code points. You still don't need random access into variable-width data.

lisper 11y ago

Read what I wrote more carefully. You have to take that offset, represent it somehow, and then pass that representation off to another part of the code, which then uses that representation to access the part of the string that was found earlier. How do you do that without forcing a re-scan when the only facility that the language provides for accessing a character in a string requires you to represent the location of that character as an integer? Actually, you can do it in C because you can use a raw pointer, but that is fraught with all manner of other perils.

jcranmer 11y ago
Just use the octet index instead of the code point index. To use UTF-8-based strings, you do need to distinguish between octet indexes (calling them iterators is probably saner to most people) and character indexes. With UCS-4 (and UCS-2 as implemented in practice), the iterator representation and character index are the same, which makes retrofitting those implementations to use UTF-8-based strings impossible. But for new environments, where UCS-2-backwards-compatibility isn't a requirement, it's not hard to make a string API that properly exposes the difference between iterators and character indexes, which is why newer environments are gravitating towards UTF-8 strings.
- lisper 11y ago
  > Just use the octet index instead of the code point index. And how, exactly, are you going to do that in any extant programming language other than C or assembler?
  - lambda 11y ago
    This discussion is about what encoding is best to choose for the low-level string types in languages and libraries, as that's what the original article was about. If your language already uses a Unicode-compatible string type, you should probably use that. If you are designing a new language, rewriting a language's basic string primitives, or writing an API or application in a language that doesn't have a well-standardized Unicode string type like C or C++, then it is probably better to pick UTF-8; if your app is necessarily single platform and tied to a platform API, choose that API's encoding, but for anything cross platform, the encoding is going to differ between the platforms so choosing UTF-8 and then transcoding at the API boundaries on the different platforms is fine. By the way, most languages do have the concept of a byte array, and you can provide UTF-8 string operations on top of that; but as I said, in general, you should be using the language's native string type unless you have a very good reason not to. The original article that we're discussing does mention one of those very good reasons; in Python, it uses an 8-bit Latin-1 encoding if the characters can fit, upgrades to 16-bit UCS-2 if they can fit in that range, and finally upgrades to 32-bit UTF-32 if they don't fit in the UCS-2 range. But that means that if you're appending strings, and one of them contains an emoji (for instance, in a web templating system that encounters an emoji in a comment), that can mean that all of a sudden your string has to grow to four times its original size, which can cause serious problems; so one workaround for that may be to actually write everything out to a UTF-8 encoded string (which in Python can be represented as a byte array) rather than trying to append strings together and hitting that behavior. Furthermore, several languages already do use UTF-8 as their internal string type; Rust, Go, and Ruby all use UTF-8 as their default or only string type. And by the way, Rust and Go both use slices to handle the use case you describe; a slice is represented as a pointer to the first byte of interest, and a number representing how many bytes it extends. I don't know about in Go, but in Rust the API guarantees that all string slices created from a string begin and end on proper codepoint boundaries. Go: https://blog.golang.org/slices https://blog.golang.org/slices, Rust: https://doc.rust-lang.org/std/primitive.str.html https://doc.rust-lang.org/std/primitive.str.html.
    - lisper 11y ago
      I think we're in violent agreement here. Keep in mind that the question I was responding to was: > Why would you want constant time access to code points? And the answer is: because you might want to compute an offset into a string in one place in your code, and then use that offset to access the string at that offset somewhere else in your code in constant time.
TheCoelacanth 11y ago
Why couldn't the string implementation simply provide a string offset class? Internally, it could be represented as a byte offset but at the point of use it wouldn't have to know that.
- lisper 11y ago
  Yes, this is the Right Thing. But don't forget the question I was responding to: > Why would you want constant time access to code points? The answer is: because you might want to compute an offset into a string in one place in your code, and then pass that offset to another place in your code which then accesses the string at that offset in constant time. My point is that to make this work you must have string offset be an abstract class, not an integer.
  - TheCoelacanth 11y ago
    It only has to be an abstract class if you want to prevent the existence of invalid offsets, but the same is true if you have constant width code points. For instance, INT_MAX is not a valid offset into almost any string.
    - lisper 11y ago
      > It only has to be an abstract class if you want to prevent the existence of invalid offsets Wouldn't you want that? I would. > the same is true if you have constant width code points True, but the validity check for the constant-width case can be done in constant time.
      - TheCoelacanth 11y ago
        > True, but the validity check for the constant-width case can be done in constant time. The same is true of UTF-8 because it is self-synchronizing. You only have to check that the byte at the given offset is either 0xxxxxxx or 11xxxxxx.
        11y ago
wtetzner 11y ago
Notice he said code units, not code points. Code units are fixed size. So for example, in Java, you have 16-bit code units, and have constant time indexing into them. So you could use a BreakIterator [1] to iterate through grapheme clusters. The iterator returns the index to the cluster though, not the cluster itself. The index is in terms of code units, not in terms of grapheme clusters. [1] https://docs.oracle.com/javase/6/docs/api/java/text/BreakIterator.html https://docs.oracle.com/javase/6/docs/api/java/text/BreakIte...