7 ms·
The choice to use UTF-32 (ie Unicode code points as integers, which might as well be 32-bit since your CPU definitely doesn't have a suitably sized integer type
by tialaramex 4y ago
The choice to use UTF-32 (ie Unicode code points as integers, which might as well be 32-bit since your CPU definitely doesn't have a suitably sized integer type) is unexpected, as I had seen so many other systems just choose to work entirely in UTF-8 for this problem.
Now, Brian obviously has much better instincts about performance than I do and may even have tried some things and benchmarked them, but my guess would have been that you should stay in UTF-8 because it's always faster for the typical cases.
- bombcar 4y agoIs UTF-32 fixed size per char? Because then it allows simple math that you can’t do on UTF-8.
- moomin 4y agoA “character” can be of fairly arbitrary length in Unicode, so no.
- fooster 4y agoNot to be contradictory, but unicode is not a specific encoding. ufc-8 is an encoding (with a non specific length) and utf-32 is an encoding of a Unicode code point with a specific length.
- happytoexplain 4y agoMost people talking about characters in Unicode are referring to grapheme clusters, and I assume the parent is too, since they are in fact defined by Unicode and vary in length in all encodings, hence their answer of "no" to the GP.
- valleyer 4y agoIt's a fixed size per codepoint. Many clusters that appear atomic in a text editor are made up of multiple codepoints. The flag emojis are among the many examples.
- thrown_22 4y agoUTF-8 is this magic ball of mud that somehow managed to convince people overstrikes were stupid and then implemented them so exuberantly that you can have a single glyph represented by half a dozen of them.
- ekimekim 4y agoTo nitpick: Overstrikes/other combining characters and the multiple possible ways to represent the same glyph are aspects of Unicode, the character set which deals with code points from 0 to 0x10ffff. Whereas UTF-8 is a way of encoding that character set into a sequence of bytes. The things you describe are present in all unicode encodings.
- simias 4y agoIt's always the tradeoff, some operations are simpler on UTF-32 but they have additional memory (and therefore cache) footprint and since you typically don't want to use UTF-32 externally you have to convert back and forth which is not free. I think these days people don't bother with UTF-32 too much because it's not even like you have a clean "one 32bit int, one character" relation anyway since some characters can be built from multiple codepoints. Since generally most code manipulating character strings are interested in characters and not codepoints, UTF-32 is effectively a variable-length encoding too...
- tialaramex 4y agoRight, somebody else might have actual metrics but I'd have guessed actual regular expression patterns are split something like: 90% Only care about ASCII, thus individual bytes in UTF-8, and so UTF-32 just wastes memory 1% Care about individual code points, but spread over multiple bytes (e.g. the double dagger ‡), UTF-32 is perfect 9% Care about multiple code points (to form e.g. a Flag, or é written in combining form, or two women kissing) and so UTF-32 doesn't really help again
- bmn__ 4y agoApplications and text-processing libraries are free use an internal text encoding or data structure, if you will, which does not suffer from the drawbacks. Conversions to encodings suitable for data exchange (e.g. UTF-8) are performed at the I/O boundaries.
- tialaramex 4y agoSure, and if stuff lives inside your "application and text-processing library" for long enough and performs enough of the thusly optimised actions without leaving, you might even amortize the cost of the work you did at the edges. But probably not.
- layer8 4y agoAnother factor is that nowadays machine code execution is much faster than memory accesses, so the trade-off of requiring more program logic to process a more compact format makes a lot of sense.
- happytoexplain 4y agoIt is fixed size per code point, which are what developers (and programming languages) sometimes casually call a character, but in practice a character is a grapheme, which can be multiple code points once you're outside the ASCII range. But it can still be useful to count code points, which would be faster in UTF-32. Edit: Mixed up code units and code points.
- thayne 4y agoAnd even then, in some languages at least, what constitutes a grapheme isn't always well defined.
- happytoexplain 4y agoTrue - I was thinking of Unicode's definition ("[extended] grapheme clusters").
- a1369209993 4y ago> in some languages at least, what constitutes a grapheme isn't always well defined. Can you provide some examples? People say this a lot, but the cases I've been able to find tend to be things like U+01F1 LATIN CAPITAL LETTER DZ, which is only not well defined in the sense that Unicode defines it wrong (as one character rather than two) presumably-on-purpose, for compatibility with one or more older character encodings.
- happytoexplain 4y agoIs DZ "wrong" because it's not considered a digraph by professionals, or because people don't agree that digraphs should be considered single characters?
- a1369209993 4y ago"DZ" isn't 'wrong', it's a perfectly valid two-character string consisting of "D" followed by "Z". Assigning to a multi-character string a encoded representation that isn't the concatenation of representations of each character in the string (especially while insisting that that makes it a distinct character in its own right) is what's wrong.
- masklinn 4y ago> Because then it allows simple math that you can’t do on UTF-8. That's not actually useful, because unicode itself is a variable length encoding. So it mostly blows up the size of your data. Though it might have been selected for implementation simplicity and / or backwards compatibility (e.g. same reason why Python did it, then had to invent "flexible string representation" because strings had become way too big to be acceptable).
- dotancohen 4y agoUnicode is not an encoding, despite MS Notepad calling some encoding "Unicode".
- formerly_proven 4y ago> Q: What is Unicode? > A: Unicode is the universal character encoding, maintained by the Unicode Consortium. This encoding standard provides the basis for processing, storage and interchange of text data in any language in all modern software and information technology protocols. https://home.unicode.org/basic-info/faq/ https://home.unicode.org/basic-info/faq/
- layer8 4y agoUnicode uses the term “character encoding form” or “character encoding scheme” for what is normally referred to or abbreviated as “character encoding” or “charset” (see e.g. RFC 8187), and uses “character encoding” or “coded character set” for the abstract assignment of natural numbers to the abstract characters in a character repertoire, which is more usually referred to as just “[coded] character set” (cf. also UCS = Unicode Character Set). This different use of terminology can cause confusion. The GP is correct that Unicode as a whole is not what is colloquially meant by “encoding”.
- brewmarche 4y agoIn your quote encoding refers to assigning numbers (code points in Unicode parlance) to characters (I am simplifying here, I know the definition of character in Unicode is not that easy). It’s like a catalogue of scripts. We have to extend it when we encounter new scripts that are not catalogued yet (or when we create new emojis) Converting a byte sequence to a Unicode code point sequence and vice-versa is called transformation format (or more generally an encoding form, but then might not be deterministic) by Unicode (see <https://www.unicode.org/faq/utf_bom.html#gen2 https://www.unicode.org/faq/utf_bom.html#gen2>). Unicode specifies UTF-8, -16 and -32. We do not have to change these formats unless the catalogue hit the limits of 32 bits (not a big problem for UTF-8 but for the other two formats). These formats are already able to encode code points that are not assigned yet. And the confusion now is that a lot of people call what Unicode calls transformation format (i.e. the byte to code point mapping) encoding as well. The term charset is also used sometimes. PS: Note that a goal of Unicode is to be able to accommodate legacy encoding/charsets by having a broad enough catalogue. This is so that these legacy encoding which may come with their own catalogue can be mapped to the Unicode catalogue. So we have control codes (even though not part of any “proper” human script), precomposed letters (there is a code point for à although it could be represented by a + combining `), things like the Greek terminal form of sigma separately encoded, although that could be done in font-rendering (like generally done for Arabic), and a lot more to aid with mapping and roundtrips.
- alganet 4y agoYou 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 agoTake 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).
- rustqt6 4y ago
- jamiek88 4y agoThis adds nothing to an interesting discussion. Can you leave this Facebook nonsense there please?
- Ericson2314 4y agoIt is fixed size...for now ;)
- sargstuff 4y agoBut what order are the bytes being chomped?
- simias 4y agoHe mentions that "The amount of actual change isn't too great, so I think this might be ok" so I wonder if part of the equation has more to do with avoiding messing with legacy code rather than raw performance. If the current code expects all codepoints to have a constant-width representation, it may be complicated to add UTF-8 into the mix. A complete guess on my part though, I never looked into AWK's source code.
- xonix 4y agoThis sounds reasonable. When the GoAWK creator tried to add Unicode support through UTF-8 he discovered that this had drastic performance implications (rendering some algorithms to be O(N^2) instead of O(N)), if done naive https://github.com/benhoyt/goawk/issues/35 https://github.com/benhoyt/goawk/issues/35. Therefore the change was reverted till the more efficient implementation can be found.
- benhoyt 4y agoYes, that's right. With my simplistic UTF-8-based implementation it turned length() -- for example -- from O(1) to O(N), turning O(N) algorithms which use length() into O(N^2). See this issue: https://github.com/benhoyt/goawk/issues/93 https://github.com/benhoyt/goawk/issues/93 Similar with substr() and other string functions, which when operating as bytes are O(1), but become O(N) when trying to count the number of codepoints as UTF-8. GNU Gawk has a fancier approach, which stores strings as UTF-8 as long as it can, but converts to UTF-32 if it needs to (eg: the string is non-ASCII and you call substr). It looks like Brian Kernighan's code has the same issue with length() and substr(). I'm going to try to email him about this, as I think it's kind of a performance blocker.
- benhoyt 4y agoBrian sent me a lovely (and surprisingly lengthy) reply. He noted that length() was already O(N), as onetrueawk just represents strings as NUL-terminated C strings and uses strlen() (though strlen is a lot faster than decoding UTF-8). However, he said that substr() and index() have indeed gone from O(1) to O(N), as it used to be possible to just index by number of bytes. The most challenging part, he said, was updating the regex engine, which "was written by Al Aho in 1977 and hasn't really been touched much since".
- _0w8t 4y agoThe code only uses UTF-32 in regular expressions where I suppose it was much simpler to adopt the older code. The rest uses UTF-8.
- jaxrtech 4y agoIt's also the case that `char` in Rust is a 32-bit primitive. Though, `String` being UTF-8 is convenient until you need to do Unicode operations on actual chars... It is surely better than dealing with UTF-16 "surrogate pairs"[2] in most pre-UTF-8 tech where a `char` is 16-bits but can't fit all Unicode codepoints without another 16-bit `char`. [1]: https://doc.rust-lang.org/std/primitive.char.html#representation https://doc.rust-lang.org/std/primitive.char.html#representa... [2]: https://stackoverflow.com/a/54922477/809572 https://stackoverflow.com/a/54922477/809572
- kqr 4y agoWell, it's not like we don't have plenty of combining marks in Unicode itself, so I suspect this is something you have to deal with either way.
- hgs3 4y agoUTF-32 performance woes are exaggerated. UTF-8 decoding requires branching whereas UTF-32 does not and in terms of storage real world text does not consume much space.
- kzrdude 4y agoUtf32 has the BOM which adds complexity and at least a top level branch. Maybe it's not so bad in practice, just duplicated generated code. But as an internal representation, some of it can be ignored by choice.