News for hackers. Stuff that matters.
Re:I/O is no longer the bottleneck by morelisp on Saturday November 26, 2022 @08:03AM (#33752294)
The Go code is reasonably efficient at avoiding allocations, though it's hard to avoid some. Without thinking too hard, it's also going to be hard to avoid those same ones in C, and some possible improvements would apply to both (e.g. defining a maximum word length).

"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.

Re:I/O is no longer the bottleneck by Const-me on Saturday November 26, 2022 @08:33AM (#33752501)
> I don't think any language is going to offer that out of the box.

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.

Re:I/O is no longer the bottleneck by masklinn on Saturday November 26, 2022 @09:06AM (#33752728)
The one possible issue is by not transforming the string you're going to run the possibly less efficient CI comparison a lot: because the corpus is text and duplicated, by my reckoning there are ~32000 unique "words" out of 82 million inout "words". That's a lot of conflicts.

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).

Re:I/O is no longer the bottleneck by Const-me on Saturday November 26, 2022 @09:19AM (#33752821)
The C# standard library will not run many case-insensitive comparisons. That comparison object doesn’t just compare two objects for equality, it also has another interface method which computes a hash of a single object.

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.

Re:I/O is no longer the bottleneck by masklinn on Saturday November 26, 2022 @10:34AM (#33753448)
> The C# standard library will not run many case-insensitive comparisons. That comparison object doesn’t just compare two objects for equality, it also has another interface method which computes a hash of a single object.

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.

Re:I/O is no longer the bottleneck by Const-me on Saturday November 26, 2022 @12:40PM (#33754768)
> how fast the CI hash and equality operate compared to the CS ones.

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.

Re:I/O is no longer the bottleneck by morelisp on Saturday November 26, 2022 @01:18PM (#33755142)
But all of those optimizations can also be done, and more efficiently, by transforming while reading. Even if they're as fast as they can be, they're not as fast as a memcmp. The C# approach isn't buying you any performance here.
Re:I/O is no longer the bottleneck by Const-me on Saturday November 26, 2022 @01:48PM (#33755390)
Yeah, it’s possible to change case while loading, but I’m not sure that’s gonna be much faster.

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.

Re:I/O is no longer the bottleneck by stabbles on Saturday November 26, 2022 @08:25AM (#33752434)
> but I don't think any language is going to offer that out of the box.

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.

Re:I/O is no longer the bottleneck by cb321 on Saturday November 26, 2022 @08:30AM (#33752478)
Note: Just concatenating the bibles keeps your hash map artificially small (EDIT: relative to more organic natural language vocabulary statistics)...which matters because as you correctly note the big deal is if you can fit the histogram in the L2 cache as noted elsewhere and this really matters if you go parallel where N CPUs*L2 caches can speed things up a lot -- until your histograms blow out CPU-private L2 cache sizes. https://github.com/c-blake/adix/blob/master/tests/wf.nim (or a port to your favorite lang instead of Nim) might make it easy to play with these ideas (and see at least one way to avoid almost all "allocation" - under some interpretations).

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.

Re:I/O is no longer the bottleneck by dahfizz on Saturday November 26, 2022 @08:16AM (#33752367)
> 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.

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.

Re:I/O is no longer the bottleneck by throwaway894345 on Saturday November 26, 2022 @08:27AM (#33752448)
Typically you would just implement vectorization in assembly in the Go case.
Re:I/O is no longer the bottleneck by morelisp on Saturday November 26, 2022 @08:22AM (#33752413)
> 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.