4 ms·
If you use the naive algorithm at the top of the page but iterate over UTF-8 code points rather than bytes -- which is straightforward, BTW -- you will get some
by pjscott 10y ago
If you use the naive algorithm at the top of the page but iterate over UTF-8 code points rather than bytes -- which is straightforward, BTW -- you will get some cleverness automatically in the compiler's implementation of the switch statement. I wrote a switch to handle the Unicode "is it space?" function, with the values from the table you linked, and compiled with "clang -Os". You know what it did?
It generated a friggin' binary search tree! Some of the leaves were a sequence of straight-line comparisons, because that's more compact, but the higher levels were all a bunch of "if (c > 0x167F) { ... }" sort of code. At one point it subtracts 8192 from something and then compares with 12, and I think this is because the x86 instruction encoding is shorter and the compiler knows that the register won't be needed again along either of the code paths from that point.
Compilers are amazing sometimes.
- userbinator 10y agoCompiling switches into binary (and even sometimes trinary) trees is an old technique that's been around since at least the days of 16-bit DOS... they will usually choose between a single-level lookup, double-level lookup, or tree depending on sparsity and options used. Subtraction and addition implicitly sets the flags, so you can generate very small code with inc/dec (1-byte instructions), like this: dec ax jz ax_was_zero dec ax jz ax_was_one ...