Article explains why Unicode whitespace definition matters
1 Oct 30 6:25 PM · 13d ago · 3 posts · 2 sources · development 1 of 2
The piece notes that Unicode's White_Space property includes 25 characters, each serving distinct purposes—figure space for table digits, thin and hair space for variable gaps, no-break space for line-wrap control, and even OGHAM SPACE MARK that can render as a visible line in certain fonts.
“Yet the code looks a lot more complex than a simple c == ' ' check.”
Serce, Author · lobsters ↗Serce Developer and author
The whole story posts the bright band is this development · numbered dots are the others · click one to jump
What people said 14 voices · verbatim
-
Perfect hashing is ready cute! The implementation is very small and simple even though it's very fast: it's just the proof that it does actually work which is complicated. :D
-
> What adds more complexity is that Unicode is not frozen in time, and is constantly evolving. And this affects the definition of whitespace. For example, Unicode 6.3 had reclassified MONGOLIAN VOWEL SEPARATOR (U+180E) from a space separator to a format character, removing its White_Space property. The Unicode whitespace set had changed from 26…
-
I think it helps to have an intuition for how high-performance multipliers work to sanity check numbers like that. Here's my hand-wavy intuition for why the 3 logical stages map to roughly 3 cycles of latency in high performance implementations. If you look at industry papers on multipliers you'll see that it's not _too_ far from the truth…
-
A 64-bit integer multiply is 3 cycles of latency on a modern core, not 1 like an integer add. Integer multiply units have been fully pipelined for a long time, though, so each IMUL port can start a new multiply per cycle. That's the usual latency vs throughput thing. For a long time x86 cores only had 1 IMUL port, but both Intel and AMD released…
-
Some multiplications are faster than others, as compilers will try to use additions, shifts, and the special address-offset computation instructions to avoid using the general-purpose mulitplication circuits. But I didn't notice any regularities in 1682554634 that would enable fast multiplication.
-
> The magic 1682554634 number does look magical, and it's unclear to me how it was chosen (please do share if you know the answer). I think it’s usually just brute forced, right?
-
From memory (recollection of a university lecture about 18 years ago), the usual trick for picking hash functions for perfect hashing is: - pick a function at random from some family of hash functions - you need that function's outputs to be distinct for all of the elements you care about - which isn't a very strict property - so when the randomly…
-
If that was the case they'd have chosen the optimal (in hamming weight) value 0x51032000. Or the smallest value 0x8fd3817. 1682554634=0x6449bf0a was likely the result of a random search; the probability of a random 32-bit multiplier to generate a perfect hash is ~2^-14, so it wouldn't be out of place.
-
How is the proof complicated? They compare the ...charAt(HASH) == c. If only whitespace is in that table, then it can't possibly yield false positives. How do you check for false negatives? You just test that those couple dozen values in the table all hash correctly. Or am I missing something?
-
For some reason, I had it in my head that it was 1 clock cycle now, but apparently my memory is crap. It used to be 39 cycles back when I was doing assembly on the 386. And floating point was all done in software, unless you were lucky enough to have a 8087 (80387 or whatever) co-processor.
-
IIUC: On modern CPUs, integer multiplications are single-cycle operations. Intel double pumps them, so they're effectively a half cycle. (I'm sure that there are lots of clever cheats to get there.)
-
> I think it’s usually just brute forced, right? Quite possibly, but I'm not sure how and why they arrived at exactly this number since it's one of many options.
-
Just looked it up. 3-4 cycle latency. Still impressive. (Unless you interpret that as saying that the clock speed is too low.)
-
There's a bit of probability involved in the proof that you can find a suitable hash function.
All 2 developments of Serce explains why whitespace detection is deceptively… →
LobstersRedditHacker News