C# offers that out of the box, and the solution is much simpler there.
Pass StringComparer.OrdinalIgnoreCase or similar (InvariantCultureIgnoreCase, CurrentCultureIgnoreCase) to the constructor of the hash map, and the hash map will become case-agnostic. No need to transform strings.
Though the values should mostly be quite short, so a vectorised comparison might not even trigger as it wouldn't have the time to "stride": only one word of the top 10 even exceeds 4 letters ("shall", a hair under a million in my corpus).
Here’s implementation of the hash function used by that StringComparer.OrdinalIgnoreCase: https://source.dot.net/#System.Private.CoreLib/src/libraries... As you see, it has a fast path for ASCII-only input strings.
Which doesn't matter because I'm talking about identical strings, so they will hash the same by definition, and they will have to be compared.
So the question is how fast the CI hash and equality operate compared to the CS ones.
And I asked about comparison because I assumed that would be the costlier of the two operations, relative to its CS brethren.
If the string is ASCII like in the OP’s use case, I think the difference is not huge.
CS comparison looks more optimized, they have an inner loop which compares 12 bytes as 3 64-bit values: https://source.dot.net/#System.Private.CoreLib/src/libraries...
CI comparer doesn’t do that, it loads individual UTF-16 elements: https://source.dot.net/#System.Private.CoreLib/src/libraries... But still, it’s very simple code which does sequential memory access.
> And I asked about comparison because I assumed that would be the costlier of the two operations, relative to its CS brethren.
I think the bottleneck is random memory loads from the hash table.
Hashing and comparison do sequential RAM access. The prefetcher in the CPU will do its job, you’ll get 2 memory loads every cycle, for short strings going to be extremely fast. If that hashtable doesn’t fit in L3 cache, the main memory latency is much slower than comparing strings of 10-20 characters, no matter case sensitive or not.
But I’m sure it gonna be much harder.
For non-ASCII strings, converting case may change their length in bytes. You don’t even know in advance how much memory you need to transform 2GB of input text (or 1MB buffer if streaming). And if streaming, you need to be careful to keep code points together: with a naïve approach you gonna crash with a runtime exception when you split a single codepoint between chunks.
English words are 99.9% ASCII, but that remaining 0.1% like “naïve” is not. The C# standard library is doing the right thing for this use case. Specifically, for 99.9% of words the CI comparer will use the faster ASCII-only code to compare or hash, and only do the expensive shenanigans for small count of non-ASCII words.
Note how C# makes the implementation much simpler. A single parameter passed to the constructor of the Dictionary<string,Something> makes it implement case-insensitivity automagically.
That's what compilers are for. I tried to improve the C version to make it friendlier to the compiler. Clang does a decent job:
https://godbolt.org/z/o35edavPn
I'm getting 1.325s (321MB/s) instead of 1.506s (282MB/s) on a 100 concatenated bibles. That's still not a 10x improvement though; the problem is cache locality in the hash map.
A better way to "scale up" is to concatenate various other things from Project Gutenberg: https://www.gutenberg.org/ At least then you have "organic" statistics on the hash.
No, but at least you have direct access to the intrinsics in C. To get vectorization in Go, you have to implement it in C and link that into your Go program.
Go has an assembler which does not require implementing anything in C (though the assembler uses a more C-style syntax), nor critically does it require using CGo linkage. It's used to implement many hot paths in the stdlib.
"Lowercase word count" is a surprisingly difficult case in this regard, because you need to check and potentially transform each character individually, and also store a normalized form of each word. Probably some smart SIMD lowercase function could help here but I don't think any language is going to offer that out of the box. It's also defined in a way I think detaches a bit much from real-world issues - it's handling arbitrary bytes but also only ASCII. If it had to handle UTF-8 it would be very different; but also if it could make assumptions that only a few control characters were relevant.