4 ms·

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 thos

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.

dahfizz 4y ago
> 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.
- morelisp 4y ago
  > 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.
- throwaway894345 4y ago
  Typically you would just implement vectorization in assembly in the Go case.
stabbles 4y ago
> 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 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.
- cb321 4y ago
  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 elsethread 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 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/ https://www.gutenberg.org/ At least then you have "organic" statistics on the hash.
- deleted 4y ago
  [deleted]
Const-me 4y ago
> 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.
- deleted 4y ago
  [deleted]
- masklinn 4y ago
  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).
  - Const-me 4y ago
    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/System.Private.CoreLib/src/System/Marvin.OrdinalIgnoreCase.cs,00c02c3abefe449b https://source.dot.net/#System.Private.CoreLib/src/libraries... As you see, it has a fast path for ASCII-only input strings.
    - masklinn 4y ago
      > 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.

dahfizz 4y ago

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

morelisp 4y ago
> 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.
throwaway894345 4y ago
Typically you would just implement vectorization in assembly in the Go case.

stabbles 4y ago

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

cb321 4y ago
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 elsethread 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 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/ https://www.gutenberg.org/ At least then you have "organic" statistics on the hash.
deleted 4y ago
[deleted]

Const-me 4y ago

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

deleted 4y ago
[deleted]
masklinn 4y ago
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).
- Const-me 4y ago
  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/System.Private.CoreLib/src/System/Marvin.OrdinalIgnoreCase.cs,00c02c3abefe449b https://source.dot.net/#System.Private.CoreLib/src/libraries... As you see, it has a fast path for ASCII-only input strings.
  - masklinn 4y ago
    > 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.