3 ms·
FWIW, the Nim version is (no deps besides stdlib): import os, strutils, tables, heapqueue iterator topByVal*[K, V](c: Table[K, V], n = 10, min = V.low): (
by cb321 6y ago
FWIW, the Nim version is (no deps besides stdlib):
import os, strutils, tables, heapqueue
iterator topByVal*[K, V](c: Table[K, V], n = 10, min = V.low): (K, V) =
var q = initHeapQueue[(V, K)]()
for key, val in c:
if val >= min:
let elem = (val, key)
if q.len < n: q.push(elem)
elif elem > q[0]: discard q.replace(elem)
var y: (K, V) # yielded tuple
while q.len > 0: # q now has top n entries
let r = q.pop
y[0] = r[1]
y[1] = r[0]
yield y # yield in ASCENDING order
template maybeCount(count, word: untyped) =
if word.len > 1: count.mgetOrPut(word, 0).inc
proc main() =
var count = initTable[string, uint]()
for path in ".".walkDirRec:
if not path.endsWith(".txt"):
continue
for line in path.lines:
var word = ""
for c in line.toLower:
if c in {'a'..'z'}:
word.add c
else:
count.maybeCount word
if word.len > 0: word.setLen 0
count.maybeCount word # line ends in a word
for word, cnt in count.topByVal:
echo cnt, " ", word
main()
Doing a gcc-10 profile-guided-optimization build on this, I get the min time of 5 trials running on Charles Dickens' Tale Of Two Cities { opening paragraph is very optimization claims relevant! :-) } available here: http://www.textfiles.com/etext/AUTHORS/DICKENS/dickens-tale-126.txt http://www.textfiles.com/etext/AUTHORS/DICKENS/dickens-tale-...
7.3 ms EDIT- tptacek's C version (w/bug-fix & new tokenization)
15.8 ms Above Nim 1.4 PGO --gc:arc
24.8 ms Above Nim 1.4 --gc:arc
27.3 ms Original C++ PGO
30.2 ms Original C++ -O3 only
42.6 ms dga's Rust with rustc-1.47.0 build --release
This is on a i7-6700k. So, Skylake core and probably more importantly 8 MiB L3. So, also FWIW, I could not reproduce the Rust/C++ timing ratios with the above mentioned input file. I would also point out that not only is globwalk unnecessary as @burntsushi points out, neither are regexes nor even sorting. A heap is a better way to do "top N", but you may need to reverse the answer if you care. I mean, maybe the point of the original C++ is to also bench/exhibit use of regex engines and part of the Rust point is utf8 or some such, but to me that seems more like a distraction.
Anyway, maybe my rust build environment is screwy. Hence, my inclusion of an exact input .txt file for others to try out if they care. I had to add some extern crates and [dependencies] of anyhow, lazysort, regex, globwalk. I've never done a PGO build with rust, either. So, that may help.
- dgacmu 6y agoInteresting. I've used this same file for a test on: - I7-7920HQ, MacOS Rust version: 90ms (rustc 1.47.0 (18bf6b4f0 2020-10-07)) C++ version: 340ms (Apple clang version 12.0.0 (clang-1200.0.32.2)) - Xeon(R) Gold 6130 (skylake, Ubuntu 20.04) Rust: 76ms (rustc-1.47.0) C++: 60ms (gcc version 9.3.0 (Ubuntu 9.3.0-10ubuntu2)), -O3, no PGO Seems quite CPU and compiler-dependent. Odd that the results on MacOS were so horrible for C++. And thanks - I've updated the post to include this more-reproducible benchmark, and included both macOS and linux results. One note: I modified the single threaded one to use walkdir, but that shouldn't affect time in a major way. The macos timings were about the same. And yes, I agree about the top N part. I deliberately tried to remain "algorithm-compatible" with the C++ example; there are lots of tricks to use to speed this up more. Getting rid of the line-at-a-time processing would be a good start, for example - it results in an unnecessary double-scan of the input.
- cb321 6y agoCool. And, yeah..mmap()ing the whole file would also auto-reject non-regular files at the OS layer fixing that TOCTTOU issue..I almost did that, but I'm sure there are various other tricks, too. I mostly thought Nim deserved to be seen and then it happened to also be faster..perhaps giving folks a slight Bayesian update on presumptions of performance. :-)
- Measter 6y agoWould you be willing to test my implementation[0] also? It'd be interesting to see the overhead of the (overkill) string normalization I do, along with the much reduced pressure on the allocator compared to yours. [0] https://gist.github.com/Measter/e2e287ee21311d34ea8eb8cd9d5783be https://gist.github.com/Measter/e2e287ee21311d34ea8eb8cd9d57...
- cb321 6y agoWell, I got 93 ms on the same Tale Of Two Cities file, 2x slower than dga's version and 18x slower than my last 5.0 ms Nim version (done to properly avoid hanging forever if someone does a "mknod foo.txt p") mentioned elsewhere in this thread ( https://news.ycombinator.com/item?id=24822429 https://news.ycombinator.com/item?id=24822429). Really, though, all the code for all 6 versions (two Nim, one C, two Rust, one C++) as well as the input file is available to all. So, you should/could double check yourself. As dga mentions in his updated blog there is a lot of compiler/CPU sensitivity.