7 ms·

Having the continuation bytes always start with the bits `10` also make it possible to seek to any random byte, and trivially know if you're at the beginning of

• 1oooqooq 1y ago
  so you replace one costly sweeping with a costly sweeping. i wouldn't call that an advantage in any way over junping n bytes. what you describe is the bare minimum so you even know what you are searching for while you scan pretty much everything every time.
  • hk__2 1y ago
    What do you mean? What would you suggest instead? Fixed-length encoding? It would take a looot of space given all the character variations you can have.
    • gertop 1y ago
      UTF-16 is both simpler to parse and more compact than utf-8 when writing non-english characters. UTF-8 didn't win on technical merits, it won becausw it was mostly backwards compatible with all American software that previously used ASCII only. When you leave the anglosphere you'll find that some languages still default to other encodings due to how large utf-8 ends up for them (Chinese and Japanese, to name two).
      • ISV_Damocles 1y ago
        UTF-16 is also just as complicated as UTF-8 requiring multibyte characters to cover the entirety of Unicode, so it doesn't avoid the issue you're complaining about for the newest languages added, and it has the added complexity of a BOM being required to be sure you have the pairs of bytes in the right order, so you are more vulnerable to truncated data being unrecoverable versus UTF-8. UTF-32 would be a fair comparison, but it is 4 bytes per character and I don't know what, if anything, uses it.
        • adgjlsfhk1 1y ago
          python does (although it will use 8 or 16 bits per character if all characters in the string fit)
        • Mikhail_Edoshin 1y ago
          No, UTF-16 is much simpler in that aspect. And its design is no less brilliant. (I've written an state machine encoder and decoder for both these encodings.) If an application works a lot with text I'd say UTF-16 looks more attractive for the main internal representation.
          • rmunn 1y ago
            UTF-16 is simpler most of the time, and that's precisely the problem. Anyone working with UTF-8 knows they will have to deal with multibyte codepoints. People working with UTF-16 often forget about surrogate characters, because they're a lot rarer in most major languages, and then end up with bugs when their users put emoji into a text field.
      • adgjlsfhk1 1y ago
        With BOM issues, UTF-16 is way more complicated. For Chinese and Japenese, UTF8 is a maximum of 50% bigger, but can actually end up smaller if used within standard file formats like JSON/HTML since all the formatting characters and spaces are single bytes.
      • syncsynchalt 1y ago
• PaulHoule 1y ago
  It's not uncommon when you want variable length encodings to write the number of extension bytes used in unary encoding https://en.wikipedia.org/wiki/Unary_numeral_system https://en.wikipedia.org/wiki/Unary_numeral_system and also use whatever bits are left over encoding the length (which could be in 8 bit blocks so you write 1111/1111 10xx/xxxx to code 8 extension bytes) to encode the number. This is covered in this CS classic https://archive.org/details/managinggigabyte0000witt https://archive.org/details/managinggigabyte0000witt together with other methods that let you compress a text + a full text index for the text into less room than text and not even have to use a stopword list. As you say, UTF-8 does something similar in spirit but ASCII compatible and capable of fast synchronization if data is corrupted or truncated.
• Animats 1y ago
  Right. That's one of the great features of UTF-8. You can move forwards and backwards through a UTF-8 string without having to start from the beginning. Python has had troubles in this area. Because Python strings are indexable by character, CPython used wide characters. At one point you could pick 2-byte or 4-byte characters when building CPython. Then that switch was made automatic at run time. But it's still wide characters, not UTF-8. One emoji and your string size quadruples. I would have been tempted to use UTF-8 internally. Indices into a string would be an opaque index type which behaved like an integer to the extent that you could add or subtract small integers, and that would move you through the string. If you actually converted the opaque type to a real integer, or tried to subscript the string directly, an index to the string would be generated. That's an unusual case. All the standard operations, including regular expressions, can work on a UTF-8 representation with opaque index objects.
  • btown 1y ago
    This is Python; finding new ways to subscript into things directly is a graduate student’s favorite pastime! In all seriousness I think that encoding-independent constant-time substring extraction has been meaningful in letting researchers outside the U.S. prototype, especially in NLP, without worrying about their abstractions around “a 5 character subslice” being more complicated than that. Memory is a tradeoff, but a reasonably predictable one.
    • meindnoch 1y ago
      >without worrying about their abstractions around “a 5 character subslice” being more complicated than that Combining characters still exist.
  • nostrademons 1y ago
    PyCompactUnicodeObject was introduced with Python 3.3, and uses UTF-8 internally. It's used whenever both size and max code point are known, which is most cases where it comes from a literal or bytes.decode() call. Cut memory usage in typical Django applications by 2/3 when it was implemented. https://peps.python.org/pep-0393/ https://peps.python.org/pep-0393/ I would probably use UTF-8 and just give up on O(1) string indexing if I were implementing a new string type. It's very rare to require arbitrary large-number indexing into strings. Most use-cases involve chopping off a small prefix (eg. "hex_digits[2:]") or suffix (eg. "filename[-3:]"), and you can easily just linear search these with minimal CPU penalty. Or they're part of library methods where you want to have your own custom traversals, eg. .find(substr) can just do Boyer-Moore over bytes, .split(delim) probably wants to do a first pass that identifies delimiter positions and then use that to allocate all the results at once.
• deepsun 1y ago
  That's assuming the text is not corrupted or maliciously modified. There were (are) _numerous_ vulnerabilities due to parsing/escaping of invalid UTF-8 sequences. Quick googling (not all of them are on-topic tho): https://www.rapid7.com/blog/post/2025/02/13/cve-2025-1094-postgresql-psql-sql-injection-fixed/ https://www.rapid7.com/blog/post/2025/02/13/cve-2025-1094-po... https://www.cve.org/CVERecord/SearchResults?query=utf-8 https://www.cve.org/CVERecord/SearchResults?query=utf-8
  • s1mplicissimus 1y ago
    I was just wondering a similar thing: If 10 implies start of character, doesn't that require 10 to never occur inside the other bits of a character?
    • gavinsyancey 1y ago
      Generally you can assume byte-aligned access. So every byte of UTF-8 either starts with 0 or 11 to indicate an initial byte, or 10 to indicate a continuation byte.
    • dbaupp 1y ago
      UTF-8 encodes each character into a whole number of bytes (8, 16, 24, or 32 bits), and the 10 continuation marker is only at the start of the extra continuation bytes, it is just data when that pattern occurs within a byte. You are correct that it never occurs at the start of a byte that isn’t a continuation bytes: the first byte in each encoded code point starts with either 0 (ASCII code points) or 11 (non-ASCII).
    • pklausler 1y ago
      10 never implies the start of a character; those begin with 0 or 11.
  • restalis 1y ago
    This tendency of requirement overloading, for what can otherwise be a simple solution for a simple problem, is the bane of engineering. In this case, if security is important, it can be addressed separately, e.g. for the underlying text treated as an abstract information block that has to be packaged with corresponding error codes then checked for integrity before consumption. The UTF-8 encoding/decoding process itself doesn't necessarily have to answer the security concerns. Please let the solutions be simple, whenever they can be.
• thesz 1y ago
  > so you can easily find the beginning of the next or previous character. It is not true [1]. While it is not UTF-8 problem per se, it is a problem of how UTF-8 is being used. [1] https://paulbutler.org/2025/smuggling-arbitrary-data-through-an-emoji/ https://paulbutler.org/2025/smuggling-arbitrary-data-through...
  • layer8 1y ago
    Parent means “character” as defined here in Unicode: https://www.unicode.org/versions/Unicode17.0.0/core-spec/chapter-2/#G25564 https://www.unicode.org/versions/Unicode17.0.0/core-spec/cha..., effectively code points. Meanings 2 and 3 in the Unicode glossary here: https://www.unicode.org/glossary/#character https://www.unicode.org/glossary/#character
• procaryote 1y ago
  also, the redundancy means that you get a pretty good heuristic for "is this utf-8". Random data or other encodings are pretty unlikely to also be valid utf-8, at least for non-tiny strings
• spankalee 1y ago
  Wouldn't you only need to read backwards at most 3 bytes to see if you were currently at a continuation byte? With a max multi-byte size of 4 bytes, if you don't see a multi-byte start character by then you would know it's a single-byte char. I wonder if a reason is similar though: error recovery when working with libraries that aren't UTF-8 aware. If you slice naively slice an array of UTF-8 bytes, a UTf-8 aware library can ignore malformed leading and trailing bytes and get some reasonable string out of it.
  • Sharlin 1y ago
    It’s not always possible to read backwards.
    • Dylan16807 1y ago
      Okay so you seek by 3 less bytes. Or you accept that if you're randomly losing chunks, you might lose an extra 3 bytes. The real problem is that seeking a few bytes won't work with EMBL. If continuation bytes store 8 payload bits, you can get into a situation where every single byte could be interpreted as a multi-byte start character and there are 2 or 3 possible messages that never converge.
      • Sharlin 1y ago
        The point is that you don’t have a "seek" operation available. You are given a bytestream and aren’t told if you’re at the start, in a valid position between code points, or in the middle of a code point. UTF-8’s self-synchronizing property means that by reading a single byte you immediately know if you’re in the middle of a code point, and that by reading and discarding at most two additional bytes you’re synchronized and can start/return decoding. That wouldn’t be possible if continuation bytes used all the bits for payload.
        • Dylan16807 1y ago
          Yes, the point is being able to synchronize. But it doesn't matter if it takes 1 byte or 3 bytes to synchronize. And being unable to read backwards is not a problem. (EMBL doesn't synchronize in three bytes but other encodings do.)
• jancsika 1y ago
  > Having the continuation bytes always start with the bits `10` also make it possible to seek to any random byte, and trivially know if you're at the beginning of a character or at a continuation byte like you mentioned, so you can easily find the beginning of the next or previous character. Given four byte maximum, it's a similarly trivial algo for the other case you mention. The main difference I see is that UTF8 increases the chance of catching and flagging an error in the stream. E.g., any non-ASCII byte that is missing from the stream is highly likely to cause an invalid sequence. Whereas with the other case you mention the continuation bytes would cause silent errors (since an ASCII character would be indecipherable from continuation bytes). Encoding gurus-- am I right?
• KingLancelot 1y ago
  [dead]
• jridgewell 1y ago
  This isn't quite right. In invalid UTF8, a continuation byte can also emit a replacement char if it's the start of the byte sequence. Eg, `0b01100001 0b10000000 0b01100001` outputs 3 chars: a�a. Whether you're at the beginning of an output char depends on the last 1-3 bytes.
  • rockwotj 1y ago
    > outputs 3 chars You mean codepoints or maybe grapheme clusters? Anyways yeah it’s a little more complicated but the principle of being able to truncate a string without splitting a codepoint in O(1) is still useful
    • jridgewell 1y ago
      Yah, I was using char interchangeably with code point. I also used byte instead of code unit. > truncate a string without splitting a codepoint in O(1) is still useful Agreed!
• sparkie 1y ago
  VLQ/LEB128 are a bit better than the EBML's variable size integers. You test the MSB in the byte - `0` means it's the end of a sequence and the next byte is a new sequence. If the MSB is `1`, to find the start of the sequence you walk back until you find the first zero MSB at the end of the previous sequence (or the start of the stream). There are efficient SIMD-optimized implementations of this. The difference between VLQ and LEB128 is endianness, basically whether the zero MSB is the start or end of a sequence. 0xxxxxxx - ASCII 1xxxxxxx 0xxxxxxx - U+0080 .. U+3FFF 1xxxxxxx 1xxxxxxx 0xxxxxxx - U+4000 .. U+10FFFD 0xxxxxxx - ASCII 0xxxxxxx 1xxxxxxx - U+0080 .. U+3FFF 0xxxxxxx 1xxxxxxx 1xxxxxxx - U+4000 .. U+10FFFD It's not self-synchronizing like UTF-8, but it's more compact - any unicode codepoint can fit into 3 bytes (which can encode up to 0x1FFFFF), and ASCII characters remain 1 byte. Can grow to arbitrary sizes. It has a fixed overhead of 1/8, whereas UTF-8 only has overhead of 1/8 for ASCII and 1/3 thereafter. Could be useful compressing the size of code that uses non-ASCII, since most of the mathematical symbols/arrows are < U+3FFF. Also languages like Japanese, since Katakana and Hiragana are also < U+3FFF, and could be encoded in 2 bytes rather than 3.
  • kstenerud 1y ago
    Unfortunately, VLQ/LEB128 is slow to process due to all the rolling decision points (one decision point per byte, with no ability to branch predict reliably). It's why I used a right-to-left unary code in my stuff: https://github.com/kstenerud/bonjson/blob/main/bonjson.md#length-field-header https://github.com/kstenerud/bonjson/blob/main/bonjson.md#le... | Header | Total Bytes | Payload Bits | | ---------- | ----------- | ------------ | | `.......1` | 1 | 7 | | `......10` | 2 | 14 | | `.....100` | 3 | 21 | | `....1000` | 4 | 28 | | `...10000` | 5 | 35 | | `..100000` | 6 | 42 | | `.1000000` | 7 | 49 | | `10000000` | 8 | 56 | | `00000000` | 9 | 64 | The full value is stored little endian, so you simply read the first byte (low byte) in the stream to get the full length, and it has the exact same compactness of VLQ/LEB128 (7 bits per byte). Even better: modern chips have instructions that decode this field in one shot (callable via builtin): https://github.com/kstenerud/ksbonjson/blob/main/library/src/KSBONJSONDecoder.c#L116 https://github.com/kstenerud/ksbonjson/blob/main/library/src... static inline size_t decodeLengthFieldTotalByteCount(uint8_t header) { return (size_t)__builtin_ctz(header) + 1; } After running this builtin, you simply re-read the memory location for the specified number of bytes, then cast to a little-endian integer, then shift right by the same number of bits to get the final payload - with a special case for `00000000`, although numbers that big are rare. In fact, if you limit yourself to max 56 bit numbers, the algorithm becomes entirely branchless (even if your chip doesn't have the builtin). https://github.com/kstenerud/ksbonjson/blob/main/library/src/KSBONJSONDecoder.c#L142 https://github.com/kstenerud/ksbonjson/blob/main/library/src... It's one of the things I did to make BONJSON 35x faster to decode/encode compared to JSON. https://github.com/kstenerud/bonjson https://github.com/kstenerud/bonjson If you wanted to maintain ASCII compatibility, you could use a 0-based unary code going left-to-right, but you lose a number of the speed benefits of a little endian friendly encoding (as well as the self-synchronization of UTF-8 - which admittedly isn't so important in the modern world of everything being out-of-band enveloped and error-corrected). But it would still be a LOT faster than VLQ/LEB128.
• cryptonector 1y ago
  This is referred to as UTF-8 being "self-synchronizing". You can jump to the middle and find a codepoint boundary. You can read it backwards. You can read it forwards.