There is no C# optimized variant because nobody wrote one. There is no claim that the C# program is optimized. Look at the table: there are "simple" and "optimized" variants for each language (except C#). The "simple" variants are intentionally not supposed to be optimized, and instead, use something approximating idiomatic code for the given language.
The author named it “simple.cs” for presumably that reason and the “though not being a C# developer, there may be obvious things I’m missing” part makes me think they’d be happy to get your optimized contribution.
Totally fair - my point was mostly that it seemed pretty clear that the author didn’t have much C# experience and would gladly accept an expert’s optimized version.
You're micro-optimizing the wrong thing, most of the time taken in C# is in the .Split(' ', StringSplitOptions.RemoveEmptyEntries) (which is UNICODE instead of ASCII as in other languages by the way) and also Console.ReadLine().
C# supports non-allocating splitting via the Span / ReadOnlySpan see this article about this very question:
And, Perl's hash implementation can perform better compared to Awk's associative arrays. The `SCOWL-wl.txt` file used below was created using http://app.aspell.net/create. `words.txt` is from `/usr/share/dict/words`. Mawk is usually faster, but GNU Awk does better in this particular case.
$ wc -l words.txt SCOWL-wl.txt
99171 words.txt
662349 SCOWL-wl.txt
761520 total
# finding common lines between two files
# shorter file passed as the first argument here
$ time gawk 'NR==FNR{a[$0]; next} $0 in a' words.txt SCOWL-wl.txt > t1
real 0m0.376s
$ time perl -ne 'if(!$#ARGV){$h{$_}=1; next}
print if exists $h{$_}' words.txt SCOWL-wl.txt > t2
real 0m0.284s
I know this is meant as a joke, but I just use this to once again note that Perl actually had a very common linter/pretty printer way before it became all the rage (perltidy/perlcritic). I also wish other languages had a book like Perl Best Practices, that goes beyond just syntactical issues.
To be fair, I once came across a sentiment that was pretty close to "readability is bad". Taken from both the (bourne) shell and awk, perl has lots of short variables that determine parsing input and other matters, like "$/". You can then `use English` to have alternative names for that, but those might not be as well known ("$/" would be "$INPUT_RECORD_SEPARATOR", or "$RS" as a tribute to awk). So the line noise might be more common and thus more understandable than the "readable" version.
I don't quite buy that for e.g. "$INPUT_RECORD_SEPARATOR", but there's an argument to be made for "$RS" or "$ARG" being worse than the Asterix swear words.
> I know this is meant as a joke, but I just use this to once again note that Perl actually had a very common linter/pretty printer way before it became all the rage (perltidy/perlcritic).
And all great perl hackers deliver readable code. But we still enjoy a round of perl golf once in a while. And honor demands, that, if you respond in perl golf style to an interview question, you make it count ;)
Which runs in .39 seconds. mhd's solution runs in .42 seconds. For reference the optimized C version takes .059 seconds (possibly cause of clang?), wc -w takes .023s and the optimized python version takes .288
Unfortunate, because for all the badness of Perl, it shines in exactly this case of "read a potentially-infinite stream of text from stdin, process it, and dump another stream to stdout".
Honestly, when you don’t know perl it looks really unreadable but if you spend some time learning it it’s not that hard it’s just many of the operators are not google-able. The harder part, from experience, is maintaining perl scripts. A lot of perl scripts from the early 2000s are written in extremely hacky ways without modern code style sensibilities. In 2021 I don’t see any reason to use perl over python3 anymore, python3 is fast, widely used, easy to write, and easy to learn. Even the bioinformatics folks, some of the last perl holdouts, have been switching to python.
Since learning perl a couple years ago I personally only use it for one liners to replace sed/awk. If I do use perl in a script it’s usually in one liner form in a bash script to post process output from something like ripgrep.
You would get a NameError (or maybe an UnboundLocalError in some cases) if you use a nonexistent variable name in Python. At least, this has been true since 2013 when I started learning Python.
> In 2021 I don’t see any reason to use perl over python3 anymore
Regex handling is still far nicer in perl than anywhere else, so for any script which is primarily about string parsing with regular expressions, perl is the right tool for the job.
My version? That's a one-liner, one shouldn't maintain those. It was mainly intended to show that a lot of the logic for simple cases is so common that perl (and some other languages) have those as command line switches.
That also makes it hard to win for total outsiders, though. This touches on core functionality, which often has quite a legacy behind it and thus its own vernacular. I can write `while (my $line = <STDIN>)` instead of `while(<>)`, but I can't get as easily rid of "chomp" being confusing to most people. A bit like car/cdr in Lisp.
But that happens even if you have plain english functions and no special cased syntax. Looking at the simple python version, it took some effort for me to remember what `Count.update(lst)` does, or that `most_common` without arguments returns all elements.
Chaotic standard library with cute-but-difficult-to-search-for names like "chomp", messy and complicated rules around sigils and scalar() for arrays and tables, lots of magic convenience like "$_" being optional in loops, s/// being "destructive" by default, and the need for some ugly hacks around handling subroutine arguments.
Perl has plenty of "good parts", too. But it is not an easy language to learn and even good idiomatic Perl code can be difficult to read. I don't blame people for favoring Python and Ruby.
I often see examples comparing one-liner worthy code written in one language with beautiful, linted, critique-passing indented code written in other languages, and on and on goes the Perl bashing based on examples of the former.
I assume you're asking why the "simple" Rust version is slower than the "simple" Go version?
I wrote the simple Rust program. I've also been writing Go for a long time. It's tough to say precisely why, but here are some guesses:
* The simple variants, by virtue of being simple, do a lot of extra allocation. Go, because of its GC, might be able to do a bit better here. (I believe the Rust program also does more allocations than the Go program.)
* In Rust, all strings are UTF-8 validated. In Go, they are not. In Go, strings are only conventionally UTF-8.
* A good portion of these programs is spent interacting with a hashmap. Rust's default hashing algorithm is chosen to prevent HashDoS attacks[1] at the expense of slower hashing. I actually don't know whether Go's hashmap does the same. So I'm highlighting it here as a potential difference that perhaps someone else can elaborate on.
Strings are just slices of bytes in Rust too. Both languages use UTF-8 as their internal representation. The difference is that Rust requires its strings to be valid UTF-8. Go does not. Either choice is reasonable. The downside of requiring valid UTF-8 is that in order to read bytes from a file, you have to do a validation check on them to ensure they are UTF-8 before returning a string back. This is an additional cost.
But this is not the only additional cost in the Rust program. I outlined a few others.
> Isn't it possible to do the same with Rust for this benchmark?
This benchmark has two programs for each language. The "simple" and "optimized" variant. The "simple" version is supposed to be written in an idiomatic style for that language. Taking extra steps to make tweaks and optimize the code is, I think, against the spirit of the challenge. Obviously, this is a very fuzzy concept, and everyone can make up their own mind on the extent to which this framing is useful. (I think it is, personally, especially when you also allow for a second submission that tries to make the program fast.)
To clarify my question, can Rust read files and split their strings without checking UTF8 correctness? That could speedup the algorithm.
In Go I have used this [1] in the past when I had to validate UTF8 encoding but on hot paths where I'm sure UTF8 is valid (coming from sanitized database data for example) I skipped that part.
Don’t downvote, it’s a really good question. Naively, I’d also have expected Rust to be faster, given the same algorithm. My guess is that without a GC, the Rust solution can’t delay deallocating all those temporary strings (both variants seem to allocate a string for each word, though I’m not sure if Go doesn’t simply share string slices). GCs free memory in batches, which is often more efficient, and sometimes don’t have to do it all on process exit. The Rust code meticulously deallocates each string individually.
(The C code.) Using hcreate and the fact that posix describes this interface which uses a hash table singleton, is just mind boggling. :) So ugly, and you'd hope anything as non-reusable as that is deprecated with a strong wording.
Even the "optimized" C version is far from what an experienced C programmer would write if performance was paramount. General-purpose memory allocation, using hash tables with inherently bad spatial and temporal locality, using buffered I/O instead of mapping the file to memory.
You can't map an arbitrary stream into memory. That's one of the constraints of the challenge: it has to be able to work on a stream.
And even then, you can't memory map all kinds of files. This is what happens when you assume that you can:
$ ag MHz /proc/cpuinfo
$ grep MHz /proc/cpuinfo
cpu MHz : 2300.000
cpu MHz : 988.934
cpu MHz : 2300.000
cpu MHz : 800.044
cpu MHz : 2300.000
cpu MHz : 2300.000
cpu MHz : 2300.000
cpu MHz : 1100.949
In the optimized C program, allocation is not a bottleneck. Pretty much all allocation is done upfront and that's all you need. There is an allocation for writing a new word to the table, but that's also amortized and isn't a big factor in the performance of the program in this particular benchmark.
As for "bad spatial and temporal locality," can you be more specific? I guess the only thing I can see is perhaps inlining words smaller than some size into the same allocation as the hash table. But the hash table is otherwise one contiguous allocation.
> That's one of the constraints of the challenge: it has to be able to work on a stream.
I cannot find any stream constraint in either the article or the countwords repo. He just says "standard input" and his "test.sh" uses "<kjvbible_x10.txt".
You can mmap stdin/fd 0 after an `fstat(0,..)` no problemo. Can it fail and should you check errors? Sure (as can accessing stdin in any way, actually).
He even mentions memory-mapped IO as a further way to go in the article in the C part.
> Memory: don’t read whole file into memory. Buffering it line-by-line is okay, or in chunks with a maximum buffer size of 64KB. That said, it’s okay to keep the whole word-count map in memory (we’re assuming the input is text in a real language, not full of randomized unique words).
A shorter but less precise way of saying that is, "make the program work on streams."
> You can mmap stdin/fd 0 after an `fstat(0,..)` no problemo. Can it fail and should you check errors? Sure (as can accessing stdin in any way, actually).
Of course. And when it fails, what do you do? You defer to something that can handle a stream! Which is exactly the problem in the OP.
I disagree. mmap will demand page into memory - typically reading 4K at a time off storage (though really the buffer cache in all these timings). Much less than 64K. Were the file bigger than RAM/were there competition, it would also evict earlier pages. It's really just another way to "buffer" without worrying about all the fuss in user space, and I don't think you're going to convince me otherwise. I mean, MAP_POPULATE might violate the idea, but that is a very special case of mmap.
Honestly, I think the author himself saying memory-mapped IO is a forward direction but "enough for now!" is pretty conclusive that he didn't think it was a forbidden optimization direction. I think you are over interpreting his early step-by-step style language explaining finite memory as a strict spec, or perhaps he shared an earlier draft of the article with you before he wrote that.
It's fine to fail over to a stream, but often mmap is faster, as I know you know.
If you mmap'd a file, how do you keep its maximum memory usage to 64KB? I actually don't know the answer to that question. It's definitely not the default. You don't get to control it. The OS does.
> It's fine to fail over to a stream, but often mmap is faster, as I know you know.
But that's exactly the point. You literally cannot use mmap in all cases, either because you just can't or because it's actually slower. And in those cases, you need to fail over to a streaming implementation. And that streaming implementation needs to be fast too. And that's what this benchmark is.
If you submitted a program that only used mmaps, and I sent a stream into that program, it would fail. So then you would need to modify the program to handle streams. And your strategy for dealing with mmaps couldn't be used. So then you'd need to optimize your handling of streams. Which is exactly what the programs in the OP are doing. So in the end, mmaps are a distraction for a benchmark like this, and I suspect that's why the OP didn't bother with them.
You keep ignoring the author literally opening it up as an avenue in:
>I’m sure there’s further you could go with the C version: investigate memory-mapped I/O, avoid processing byte-at-a-time, use a fancier data structure for counting, etc. But this is quite enough for now!
This subthread started with bluetomcat talking about the optimized C and what experienced C devs might do. That strikes me as fair game to open up discussion of alternative IO anyway even if the author hadn't already (which he clearly did, as quoted). So, that's two reasons it's worth bringing up, and I was never criticizing your program!
If what you are on about is "Who wins what scorecard against what arbitrary constraints" or "My hands were tied, really!" or whatever, then, sorry, but this benchmark is too uncontrolled for great answers even on its own terms. Various stdio-using things would be "out of constraints" if a system was configured with bigger than 64K default buffers anyway which is certainly possible, if unlikely, today. None of the sample programs or the test harness "check" for that. Some of the languages may not be able to ensure it. Using that to leapfrog to "only streams" is a stretch. Is CPU freq scaling controlled? Min of N trials to filter background noise/get repeatability? Even simple mean+-sdev? No, no, and no. And probably four more things.
Beyond all of that, I also don't think that's what this subthread was ever about. bluetomcat's opening was literally the opposite - equivalent to "real devs would do xyz implicitly independent of the arbitrary constraints posed if performance is paramount"..seemingly a follow up on my quote from the author. He can of course chime in if I misread that. Presumably, the author would have had to relax that already problematic 64K constraint when moving on to mmap (which moving on he might have done if the article were fewer languages or if he had just done it that way first in his open coded C).
The positions you seem dug into here seems to me "don't mention mmap to people questioning the posing of the contest even though the author did" or "you cannot default to mmap and fail over like fstat||mmap||do_streams||aiie_noStdInEven". Yes, which is faster varies by OS/situation. So? Maybe "experienced" C/whatever devs know their situation. (You use mmap in ripgrep...). Maybe these are all honest communication errors, but I don't think your positions are very tenable.
As I mentioned in a few places, performance conclusions here are harder than they might look. As for "distractions", one might say that about literally all the optimized variants, including their numbers in the table since the numbers are likely to change more. The article might be stronger to focus on only the simple variants of all the rest, leaving the optimized ones for the github repo and weird "contest rule" debates on the github issues.
Anyway, to add a little more actual information for passersby less dug in to defending some weird position like "", Nim's stdlib has a trie in critbits module. So, that test is "in bounds" and an easy experiment someone might enjoy.
It's not about a scorecard. I didn't just dig my heels in and say, "language lawyering the OP says mmap isn't allowed so shut up." It's about what's a useful benchmark. I explained why mmap's are a distraction beyond just pointing to the OP's constraints. I don't think there's really much else to say and I disagree with your characterization of this thread.
> As for "bad spatial and temporal locality," can you be more specific?
One could use a lexicographic Btree-like structure with multiple characters per node, sharing consecutive cache-lines. For looking up the word "bar", you would traverse the "b" key from the root node, then its child "a" node, then the "r" child of the "a" node. Most of the nodes near the top would remain hot in the cache, and deeper less-visited nodes could be joined or compacted based on some criteria. Of course there are many subtleties, special cases and complications and the solution would be far more complex in terms of source code length.
With a hash table, you effectively compute a hash for every word, and then jump at arbitrary locations throughout the whole table.
You've traded hashing for a memory access per byte. I did something similar in the 'optimized-trie' program for Rust: https://github.com/benhoyt/countwords/blob/master/rust/optim... --- It ended up being slower. But, it is very much impacted by cache effects. So the next step here would indeed be to figure out how to reduce cache misses. But it's non-trivial.
Like, maybe your idea works. Maybe. I don't know. You'd have to try it. But it's not clear to me that it will. And it doesn't support "is far from what an experienced C programmer would write if performance was paramount" IMO.
> So ugly, and you'd hope anything as non-reusable as that is deprecated with a strong wording.
It isn't. It was only added in POSIX 2001. Still there without major changes in 2018. [0] (There's actually a lot of similar libraries in POSIX, that don't include re-entrant forms.)
Thankfully, re-entrant versions are supplied as extensions by GNU, which is significantly less horrifying.
std::iostream is going to be hopelessly slow, but I would like to point out that -O3 is more appropriate for templated C++ code.
It seems that the two hot spots are the std::string constructor (unsurprisingly) and the vector constructor.
Making string faster is not easy. I would check that gcc is configured to use C++11 strings with the small string optimization and not the older C++03 compatible refcounted string. Writing your own string or a custom allocator are options, but probably overkill for the problem.
The vector constructor is more surprising. It is possible that -O3 could help a bit there. Wrapping the map iterators with std::move_iterator would also avoid a lot of string copies.
std::move_iterator was my first thought too, but I'm not sure if it works, since the key type for std::unordered_map is defined to be const, so you may have to make a copy anyway.
Maybe use a vector-of-pointer-to-pair, since we're leaving the map around and we don't really need the vector to own anything.
I think the point was to compare the reasonably simplest idiomatic examples in the various languages. For example, the C++ example used `std::unordered_map` even though that isn't necessarily the fastest possible hash table for C++ for even general purpose jobs, let alone specific ones.
Of course you could write significantly faster implementations in C (and probably in the other languages) by writing data structures from scratch especially for the job (and memory allocation strategies and maybe other stuff), and if you're the author of wc or grep then that is well worth doing because it will be used so many times relative to the amount of time for you to write that code. The comparison of the idiomatic C program vs grep is basically proof of that. But the article seemed to be targetting more typical developers than just want to plug together some common existing components.
Would be interested to see a similar comparison for a problem where the Python solution is unable to offload a significant amount of the computation onto its standard-library.
Also, nice to see Forth included. I strongly suspect that if the Python solution were unable to leverage its rich and well optimised standard-library, it would be easily outpaced by Forth.
Also, the Forth solution used Gforth, which is far from the fastest Forth engine around. [0] It would likely have performed close to C if they had used a native-code-compiling Forth engine (SwiftForth, VFX Forth, or iForth, all of which unfortunately are proprietary payware).
> if the Python solution were unable to leverage its rich and well optimised standard-library
collections.Counter is a very straightforward collection backed by dict. The code isn't specially optimized, you can write the same code yourself with dict and even avoid (probably a negligible amount of) overhead.
Now, dict is optimized, but that's a builtin type. You don't need PSL.
The article provides profiling data of the optimised Python solution. If I'm reading it right, 90% of the time (1148 milliseconds out of a total of 1280) is spent executing the _collections._count_elements and str.split methods, both of which are Python standard-library methods presumably implemented in optimized C.
Of course, they're right to optimize this way, and it's to Python's credit that it's possible to leverage this approach so successfully using only the standard-library, but I think my earlier point stands.
Again, very straightforward, based on dict. Python itself does not function at all without the dict implementation since it's the underpinning of the object model.
str is a builtin type. Calling str.split() a standard library method is... okay.
Thanks for the link, interesting that _count_elements is written in Python. At a glance it looks like the kind of thing that might benefit from being written in C, but presumably that's not the case. Perhaps because of the dynamic typing of both arguments?
> Python itself does not function at all without the dict implementation since it's the underpinning of the object model.
Sure, but I don't see the point here.
> Calling str.split() a standard library method is... okay.
For our purposes there's no reason to draw a distinction between standard-library functionality closely integrated into the language, and standard-library functionality that isn't. The relevant point is that computational work is being handed off to optimised C code.
Again, if you're optimising Python, the smart move is indeed to make maximal use of the optimised machinery in the standard-library (or for that matter some other dependable library). My point still stands: it would be interesting to look at a problem that isn't amenable to this approach, where the performance of the Python interpreter itself would be brought to the fore by necessity.
How easy it is to find such a problem will be a function of how good a job Python does of providing applicable optimised functionality in its standard-library. Perhaps something like computing matrix determinants? I don't know enough Python to say.
Right, that's what I meant. If the C code has to cope with dynamic typing anyway, there might be little scope to speed things up.
The same isn't true for, say, string operations, where there might be plenty of opportunity to move tight loops from Python to C and speed things up considerably.
Truthfully, I don't think optimization was a motivation for writing _count_elements() in Python or not. The CPython project doesn't prioritize optimization of the language or standard library unless there are clear performance gains to be made in the face of slow code. What most likely happened is someone wrote some code on a mailing list or bug report, and a maintainer included it as is.
Reading the bug report that introduced Counter[1], the author states it is the simplest implementation they came up with, and Guido and other maintainers prioritized simplicity.
It can be interesting – especially if you also compare it to something like the PyPy JIT – but it runs afoul of the idiomatic angle since Python has had decades of recommended practice being to write code in Python and optimize the hotspots in C, which has led to very popular libraries like NumPy, PIL/Pillow, etc. becoming almost universal in community recommendations.
Right. They don't emphasise improving the performance of the Python interpreter precisely because they prefer to handle computational heavy-lifting in C instead. Python has been very successful with this approach. Java takes the opposite approach, promoting 'purity' and investing very heavily in JVM performance.
It would still be interesting to see for benchmark purposes.
(Too late to edit) benhoyt's comment points out that _count_elements has two implementations, one in Python and one in C. The Python version is used only if the C function is not found.
That link shows that yes, "_count_elements" is implemented in Python, but right after it pulls in the C version if available (which it presumably is in CPython):
try: # Load C helper function if available
from _collections import _count_elements
except ImportError:
pass
Optimized grep is as fast as the non optimized grep. Seems odd.
I've seen ripgrep (in Rust, also by article contributor Andrew Gallant aka burntsushi) outperform grep in almost every way possible, both in benchmarks and in my experience.
I think grep (and wc) are included in that table as a sort of baseline. Like, "roughly speaking, what can we expect?" Or maybe, "what can we hope for?" grep (or ripgrep) isn't otherwise particularly relevant here.
In the case of grep and wc, the "optimized" variant is running with LC_ALL=C, which sets the locale to C. Presumably, the non-optimized variant is using the OP's default locale, which is maybe something like en_US.UTF-8. (Apologies for the US assumption, but what matters is that it's not the C locale.)
This is a common trick for speeding up GNU utilities when you're only working with ASCII data. It also works for things like `sort`.
In the case of grep, sometimes running with and without the locale will be about as fast, particularly if you're only searching for a simple ASCII literal pattern.
> I still like it, because (unlike C++) I can understand it
No article like that is complete without a little C++ critique :-)
> I think it’s the simple, idiomatic versions that are the most telling. This is the code programmers are likely to write in real life.
I very much agree with him on this statement. If people started writing "optimized" versions of algorithms (on that level); who would ever be able to read others peoples code...
I saw a talk by Matt Godbolt demoing the compiler explorer showing showing the assembly between idiomatic C++ vs someone trying to outsmart the compiler. In all cases the idiomatic version was superior in performance and readability / maintainability.
The one thing I would say is: as you dig more into C++ perf, you can develop an intuition for the kinds of things the compiler can and can't optimize. For instance, the C++ example from the article uses `std::unordered_map`, which is just an absolute mess from a cache locality perspective—the best compilers today (or of the foreseeable future) can't do a thing to fix that. Improving the programmer's choice of data structure is just not on the radar. :(
The optimized Python code seems to have a number of bugs:
The loop ending condition might miss non-handled `remaining` (when there is no new-line at the end of the file). (The fix should be simple. Just move the check one line below.)
When there is no newline in some chunk, it would handle the word incorrectly at the chunk boundaries. (But ok, with the constraint that lines cannot be longer than the chunk size, this should not happen. But this could have been fixed easily anyway. Just `remaining = chunk; continue` + the other fix.)
Setting LC_* to 'C' nukes locale awareness by saying "we're only caring about ASCII-en-us" and thus goes back to the 'cheap' tolower that's also present in the C and C++ version, and most likely in the awk as well - in contrast to, say, the python version.
Finding the "lower case of a character" is immensely harder in face of unicode, because the table is way larger and there's no nice speed hacks by manipulating an index into the ASCII table. JFGI: "tolower performance unicode".
If you notice setting LC_ALL makes a difference in performance for you, you ought to be aware that now you're no longer comparing same capabilities.
I'm not sure how to constructively state that except for: One shouldn't compare ASCII and unicode "tolower" in performance comparisons, as you end up comparing apples and oranges (at best. More like apples and snails) - which I did.
If the author uses code that uses "tolower" in job interviews, i.e., evaluates candidates based on their input WRT case normalization - and he even writes ("This is Unicode-aware ...") - he should know that Unicode awareness is not ubiquitous, and comes at quite a cost. Knowing about unicode awareness, one would assume he'd be aware of not making a fair comparison.
Can you state the specific comparison that is not apples-to-apples in the OP?
The only one I see is the comparison between 'simple' and 'optimized'. But that's more about "what does a simple idiomatic solution look like" and what does an "optimized and possibly less simple" solution look like. That comparison isn't designed to be apples-to-apples in the way you're saying. The simple variant will use Unicode-aware casing in environments where that's the simple and natural thing to do.
IIRC, most of the 'optimized' programs are using ASCII casing. Python doesn't, but casing isn't even close to the bottleneck in that program.
I believe the author is fully aware of this, and just chose the ASCII version for all languages precisely so that we don't get into Unicode efficiency issues. Doing that wouldn't be objectively bad or anything, it just isn't the question the author is asking. It is still a fine question on its own terms.
Yes, I'm definitely aware of this, thanks -- and as a result, you can't really compare the "simple" and "optimized" versions. Most of the "simple" versions (except C) are Unicode-aware, most of the optimized versions not -- though I acknowledge I haven't stuck to that always, e.g., in the C case, when it's just "too hard".
I think most of the uglynes in the c++ template case comes from the tool not resolving the standard types. Just replacing the std::string boilerplate reduces it by roughly half.
So that looks like a std::vector<pair<string,int> > constructor taking two map iterators as input and an internal string member taking char pointer based iterators as input.
Very interesting, these kinds of articles are (to me) some of the best content we get on here.
I'm no expert in any of the languages used except maybe C, at least I'm quick to form opinions about C code. In C, I'm not so sure that there is a well-established "idiomatic" concept, since C is not so tightly bound to a community as more modern languages. At least that's my feeling.
That said, I was shocked to see that the example code did heap-allocations to store integers. Single integers, one per allocation, per "counting bucket". I would store the count in the data pointer without a second thought, I just "can't" make 4/8-byte heap allocations and still sleep at night. Especially after all the concern about processing the input in large blocks for performance! Casting an integer to/from a void pointer should be pretty safe according to my gut feel. If that turns out to be false, I would dump the libc's hash API altogether, since it makes me do heap allocations to store single integers.
I tried making the change locally, and the time taken (as measured with the OP's benchmarking program) dropped from 0.11 to 0.10 on my system (a Dell laptop running an Intel i5-7300). That's at least something.
Afaik the only integer type it's safe to cast from and to pointers is intptr_t. Not exactly the type people reach to when writing the first "simple" version. Another comment also points out that hcreate (which is not posix, only GNU?) and the likes use a global hashmap? I can't see a lot of use cases for such a singleton datastructure.
I've been programming in C for decades and I'd never heard of hcreate. I'm sitting here wondering how the heck did that ever get standardized, allowing single hash table per process. What a bizarre feature.
I wonder if it's like insanities like SIGPIPE: it's kind of useful if you write IO tools in a few dozen/hundred lines of C. You don't need to carry around explicit context, or check if writes failed, or anything. Of course it sucks for anything else and we still have to deal with SIGPIPE .
It just means that you need to cast via intptr_t, i.e. double casts `(void*)(intptr_t)i` and `(int)(intptr_t)p`. GLib has macros for it if you feel that's useful.
If you need to round-trip a pointer through an integer and back to the same pointer, you need to use intptr_t or uintptr_t. (Note that this is true for object pointers but not necessarily function pointers. There’s no integer type guaranteed to be big enough for a function pointer.)
If you want to round-trip an integer through a pointer and back to the same integer, you can use any integer type provided it is not bigger than intptr_t or uintptr_t.
Yeah, I would have liked to avoid it too. But I think you have to allocate with the hcreate/hsearch API (for the "simple" C version). When I roll my own hash table with optimized.c I don't allocate for the integers.
No, you can just jam the integer into the "data" field in the structure and skip that allocation.
As I said, and others have commented, it requires some complicated castery to avoid UB, but it's totally doable (and at least GCC does the right thing, while warning, with no advanced casts).
Someone on Lobsters suggested this too, and I don't think it would be particularly edifying. But maybe I'm wrong. Someone should go out and do that benchmark. Maybe we'll learn something. Here is what I wrote though:
Coming up with a benchmark is hard. Benchmarks like these are models. All models are wrong. But. Some are useful.
Follow you thinking to its logical conclusion. If you open up the parallel programming flood gates, now you need to do that for all of the programs. Now your effort to contribute a sample for each language goes up. Maybe enough where actually doing the benchmark isn't practical.
So let's play the tape. If someone told me, "sure, have fun, throw threads at this!" I'd probably say, "can I use memory maps?" And let's say, "yes, sure, go for it!" I say okay, here's my first crack at it:
1. Hope stdin is a file and open it as a memory map.
2. Split the memory map slice into N chunks where N is the number of logical CPU cores on the system.
3. Run approximately the same algorithm devised in existing code submissions in N different threads, with one thread per chunk.
4. At the end, join the results and print.
If that ends up being the best strategy overall, then your model has become over-complicated because performance now likely depends on step (3). Which is exactly what the existing benchmark is. Now, maybe some languages have a harder time passing data over thread boundaries than others and maybe that impacts things. But that doesn't apply to, say, C, Rust, C++ or Go.
If that's not the best strategy, then maybe there is a cleverer approach that involves synchronizing on one shared data structure. I doubt it, but maybe. If so, your benchmark turns into one that is very different. It's no longer just about data transformation, but now you have to worry about synchronization trickiness. And now you're way outside of a standard goroutine pool that you might have used in Go.
Building a good benchmark is an art. Sometimes the constraints look dumb and arbitrary. But you have to sit down and really look at it from a bunch of different angles:
* Do the constraints approximate some real world conditions?
* Do the constraints inhibit writing code that looks like real world code?
* Do the constraints inhibit optimizing the crap out of the code?
* Do the constraints make the benchmark difficult to create in the first place?
* Do the constraints permit easy and clear measurement?
There are probably more things that I didn't think about.
Yes, you've basically gone over the details of why doing parallelized / concurrent performance comparisons between different programming languages is very difficult. I agree with most of what you have written. However, this doesn't change the fact that any comparison of performance between different languages, that ignores relevant concurrent and / or parallelization features, isn't very useful. This is especially true when the selling point for a few languages in this list is concurrency and / or parallization related features.
No, what I'm saying is that it is useful. Because in a concurrent program, you'll almost certainly being using the single threaded techniques developed here. And that the fastest program will be the one that uses the fastest single threaded techniques. So it makes sense to simplify the model and just look at the thing that is going to dominate the runtime of the program.
If a "dumb" thread pool is indeed what ends up being the best concurrent solution, then Rust, Go, C and C++ (and probably most of the other languages) are going to have almost no problems implementing it. It's just Not That Interesting.
Now, maybe I'm wrong. Maybe there is something clever here to exploit in a concurrent program, and that some languages let you do that easier than others. I doubt it. It would be interesting if it turned out to be the case, but it would be a different benchmark. It wouldn't just be about how well a language can deal with simple data transformation tasks, but also about how it deals with tricky concurrency problems. But this doesn't seem like the kind of problem that needs such things. It complicates the model.
Like honestly, just saying that any benchmark that ignores parallelism "isn't very useful" is just totally ridiculous.
> No, what I'm saying is that it is useful. Because in a concurrent program, you'll almost certainly being using the single threaded techniques developed here. And that the fastest program will be the one that uses the fastest single threaded techniques.
You have a point. Maybe I am wrong in saying that it's near useless.
> If a "dumb" thread pool is indeed what ends up being the best concurrent solution, then Rust, Go, C and C++ (and probably most of the other languages) are going to have almost no problems implementing it. It's just Not That Interesting.
Your argument makes sense if every language used the same form of concurrency or parallelism. Unfortunately, that isn't the case. Wouldn't the type of concurrency or parallelism affect performance?
> Now, maybe I'm wrong. Maybe there is something clever here to exploit in a concurrent program, and that some languages let you do that easier than others.
but concurrency / parallelism IS much easier in some languages vs others (did I misunderstand what you wrote?).
> Wouldn't the type of concurrency or parallelism affect performance?
That's what I'm saying: almost certainly not IF the best concurrent solution to this problem is to chunk of the work and feed it off to a bog standard thread pool. Pretty much every language---even C---has tools that make this pretty easy to do.
And I don't see any reason why a dumb thread pool wouldn't be the best answer to this if parallelism were allowed. Like, the fact that Go has goroutines is just not going to help with anything for this kind of work-load. Goroutines help in more complex concurrent situations.
> but concurrency / parallelism IS much easier in some languages vs others (did I misunderstand what you wrote?).
When the extent of the parallelism is a dumb thread pool with no synchronization between them, then it's pretty easy to do that in just about any language.
> That's what I'm saying: almost certainly not IF the best concurrent solution to this problem is to chunk of the work and feed it off to a bog standard thread pool.
That's the thing. This is not the case for all programming languages, even for some of the ones included this performance test. Python has a GIL. Distributing work via threads isn't going to do much unless it's something I/O intensive. Consequently, testing performance via a programming language's available methods to distribute work does matter. Special features like Goroutines also matter.
> When the extent of the parallelism is a dumb thread pool with no synchronization between them, then it's pretty easy to do that in just about any language.
The specific implementations of work distribution still matters for performance doesn't it? Different implementations yield varying levels of performance right?
Python has a `multiprocessing` module that sidesteps the GIL.
You can question me all day. Go build the benchmark. Publish it. Have people scrutinize it. I have my prior based on building this sort of tooling for years and actually publishing benchmarks.
And you still continue to miss my point. Instead, we're in a hypothetical pissing match about code that doesn't exist. Either the parallelism problem is uninteresting, or your benchmark becomes about complex synchronization. The former complicates the benchmark for no good reason. The latter results in a different benchmark entirely.
> Python has a `multiprocessing` module that sidesteps the GIL.
Yes and distributing work with multiple processes is not the same as distributing it via threads. There is a difference in performance in different implementations and variations of concurrency and parallelism.
> we're in a hypothetical pissing match about code that doesn't exist. Either the parallelism problem is uninteresting, or your benchmark becomes about complex synchronization.
Yes, the code doesn't exist because it's difficult to do, and that's what makes it interesting.
> Yes and distributing work with multiple processes is not the same as distributing it via threads. There is a difference in performance in different implementations and variations of concurrency and parallelism.
I literally addressed that in my first comment: "Now, maybe some languages have a harder time passing data over thread boundaries than others and maybe that impacts things. But that doesn't apply to, say, C, Rust, C++ or Go."
> Yes, the code doesn't exist because it's difficult to do, and that's what makes it interesting.
Well, I mean, I haven't done it not because it's hard, but because it appears pointless to me. That's my prior. Show me I'm wrong. I'm happy to learn something new.
> Well, I mean, I haven't done it not because it's hard, but because it appears pointless to me.
That's just your opinion and you haven't convinced me otherwise. Likewise, I don't think I'm going to convince you either.
> I literally addressed that in my first comment
Yes, but that doesn't mean that it's not an important point. Even if we were just comparing "C, Rust, C++ or Go.", different work distribution implementations have different sets of performance. It's hard, but it's still useful to capture that data because the real world doesn't run on a single thread or even a single core. If you're going to continue glossing over this, there's no point in continuing our discussion. We're just going in circles.
I didn't say it wasn't useful to capture the data. Indeed, I've been saying, "happy to see it done and happy to learn something if I'm wrong." Look at what I said above:
> Now, maybe I'm wrong. Maybe there is something clever here to exploit in a concurrent program, and that some languages let you do that easier than others. I doubt it. It would be interesting if it turned out to be the case, but it would be a different benchmark.
So the fact that you keep trying to niggle at the specifics of parallelism tells me that you're completely and totally missing my point. You're missing the forest for the trees.
Looking back at the convo, it started by you saying, "it would be nice to see parallelism considered." Fine. I responded by saying why that particular rabbit hole is probably not be so useful, or would be measuring something totally different than the OP. To which, you kind of flipped the script and said, "However, single thread benchmarks don't reflect the real world unless you're a student." It would have been a lot better to just say, "I disagree, but I don't have time to do the benchmark myself, so we'll have to leave it at that."
There's a lot of goalpost shifting going on. Like, are we arguing whether a parallel benchmark could be useful? Or are we arguing about whether a single threaded benchmark is useless? They are two different arguments. The former gets my response above, navel gazing at why that model probably isn't particularly useful. But the latter is just crazytown.
Amusingly, I've done a multi-threaded version of the word counting program in order to test a shm kv store. I needed benchmark that created a lot of cross thread concurrent accesses to keys and I found a blog about this test. My version has serious constraints though, you have to create a shared memory map with enough space to hold all of the keys beforehand, as it doesn't resize the shm kv map as it runs.
The speedup of the multi-threaded version vs the single-threaded version is about linear. The single threaded version uses 2 threads, one to read stdin and one to hash the keys, the 16 threaded version uses one thread to read, 16 to hash.
Here, they have code samples and multiple implementations of each task in each language.
It's a great resource for, at a glance, how performant a language is at basic cpu and memory intensive tasks and how simple the related code is.
It still has the issue that some code is unrealistically optimized for the language. And also that many solutions use standard libraries written in other languages. It's worth looking at the source, therefore.
I am very sceptical of these benchmarks for the reasons you listed. The individual implementations are often too different to give a comparable score. And sometimes this is because of the rules. Like the requirement to use the language-provided hash tables, while C is free to implement an optimized hash table for the problem.
Just looking at the first lines of the linked code, I see the following:
// Define a custom hash function to use instead of khash's default hash
// function. This custom hash function uses a simpler bit shift and XOR which
// results in several percent faster performance compared to when khash's
// default hash function is used.
That is picking terms. Many languages don't allow to specify custom hash functions, so you can't specify the hash functions until you do write a custom hash table. A fair benchmark would allow for this, if it is allowed in C.
The OP "Performance comparison: counting words in Python, Go, C++, C, Awk, Forth, Rust" does not allow external libraries BUT then makes an exception for C, and then makes a further exception -- In the optimized version we’ll roll our own hash table.
Wikipedia is your friend -- "A hash table uses a hash function to compute an index, also called a hash code …"
I was not talking about the article but the benchmark site linked. Not sure what you want to say with the wikipedia citation.
I have not made a comprehensive list, but the topic has come up when discussing one of the Go benchmarks. The Go language has a build-in hashtable, called a map, and this does not allow to specify custom hash functions. Of course rolling out a hashtable implementation which does allow this is prohibited by the benchmark rules. Probably intentionally, also like your distraction attempts are hinting to.
Please share the widely agreed criteria to identify code we would all call "unrealistically optimized" ;-)
2 tasks — pidigits & regex-redux — explicitly allow use of standard libraries (GMP, PCRE2, RE2) written in other languages.
8 tasks do not.
(Those standard libraries were allowed because some language implementations provided arbitrary precision arithmetic or regex by wrapping those standard libraries.)
Of course, realistic use of some languages relies on calling standard libraries written in other languages.
Regarding the C++ version: instead of copying data to a vector and then sorting the vector, it might be more profitable to use std::multimap<size_t, string>. This is a sorted container (likely rb-tree based) that handles duplicated keys.
I can't really wrap my head around these types of question.
Surely the correct answer is "use some established third party library that does this exact task well". Probably faster, better battle tested against weird input, localised etc etc than anything you can come up with by yourself.
Though obviously that is then useless if the interview is actually for someone who can actually write something like this for some super secret internal thing that is nothing like the problem solved by the standard solutions available. But is that really the case? I have doubts.
If I was hiring though, I'd be more worried about hiring people who would write standard elements from scratch (mostly because that's more fun) than re-use standard building blocks to get a task done correctly.
e.g. for this specific question I'd be most impressed with someone who could talk about Spacy or some other standard library that can do a lot of things in this area very quickly but also be repurposed to do interesting new things. Do I need someone who can write Spacy from scratch or someone who can use Spacy?
Immediately optimising by ignoring non-ASCII and punctuation seems mor elike a red flag than a positive.
> Surely the correct answer is "use some established third party library that does this exact task well". Probably faster, better battle tested against weird input, localised etc etc than anything you can come up with by yourself.
The point of questions like this is to test basic understanding, not the ability to search on SO or similar.
> If I was hiring though, I'd be more worried about hiring people who would write standard elements from scratch (mostly because that's more fun) than re-use standard building blocks to get a task done correctly.
As long as the hire is able to fix/extend the 3rd party library on their own... this is exactly what you figure out with "these types of questions".
It seems almost disingenuous to me to miss the point of this type of interview question, because it is so obvious that the intention is “imagine a scenario where you need to do a high performance implementation of some very well-defined task, for which you don’t have a super fast utility function. Let’s use word frequency counting as an example and ignore the fact that such a problem is almost certainly already solved.” It’s implicit in the asking of the question that they aren’t actually in need of word counts on arbitrary bodies of text and need your help solving that problem. It’s a programming interview. Accept the premise and show them that you can program.
... otherwise the proper answer is probably “I would recognize I’m sitting in a room with someone who has likely already put enough thought into this task that they could be considered an expert on the solution and I would consult them on the best solution rather than reinventing the wheel,” which would almost certainly not get you hired.
It does irk me too. Being a programmer requires understanding the complexities hidden behind a task, and this brushes them all aside as if they don't matter.
There are cases where your task is nice, simple, and well-defined, but word counting is not one of them. It's better to give a more realistic task that allows people to think about the premises.
Being a programmer involves a lot of things that are difficult to test for all at once in 45 minutes. Be irked all you want, but it seems counterproductive to pretend what’s being asked is in anyway unclear or unreasonable when you’re given a pure programming question with a clear spec. You’re supposed to write the code. That’s all.
My problem isn't that the spec is unclear, it's that the spec is silly. The task makes no sense, and selects for misusing tools. This makes it a bad interview question as given.
I’d argue that the problem does make perfect sense and isn’t a “misuse of tools” if you manage to understand the goal of the interviewer, which is “watch this person write code for a solution to a well-specified but arbitrary (perhaps even silly) problem.”
I was more viewing this in context of the article, which goes on to micro-optimize a version with an IMO unreasonable set of assumptions.
If it's instead explicitly given that this is a quick litmus test, the choices of the first pass implementation don't really matter, and you'll talk about complexities after, then sure.
> use some established third party library that does this exact task well
I seriously doubt such a library exists for most languages (Javascript might be an exception because they seem to love writing one-line libraries). It's such a simple task!
Knuth-McIlroy comes up a lot. Previous discussion [1]. For this example I can make a very similar Nim program [2] run almost exactly the same speed as `wc -w`, yet the optimized C program runs 1.2x faster not 1.15x slower than `wc -w` - a 1.4x discrepancy - bigger than many ratios in the table. So, people should be very cautious about conclusions from any of this.
Thanks for doing a nim version! I've been learning nim, and am very much a beginner, so I thought I'd tackle a simple version [0]. I'd appreciate any critiques... I don't know how idiomatic it is.
Honestly, the optimized version you created is kind of opaque; I don't want people to think that that's what "typical" nim looks like.
I'll do a pull request on the project for mine as simple (I'd have added your version as an optimized version, but I couldn't get it to compile).
On my machine, the simple-c version runs in 0.70 seconds, my simple nim runs in 0.73 seconds (and they produce the same output, which is nice :-), the nim executable is 95k.
Sure. Feel free. I agree it's probably a bit advanced, and it breaks a rule or two of the "constraints" some people seem passionate about and needs to include punctuation to match results.
Feedback-wise, yours isn't so bad, though I haven't tested it. There is definitely a simpler one that looks roughly like the Python and probably runs a bit slower than yours. That would probably be a better/more fair candidate for the "simple" category, but it probably still has ok-ish performance.
This may be more fair for the "simple" case in Nim.
import tables, strutils
var counts = initCountTable[string](16384)
for line in stdin.lines:
for word in line.toLowerASCII.split:
counts.inc word
counts.sort # SortOrder.Ascending to reverse
for word, count in counts:
echo word, " ", count
I compiled with `nim c -d:danger --gc:orc --panics:on` with gcc-10.2 on Linux-5.11 with nim-devel and file in /dev/shm. Runs in about 1.97x the time of "wc -w" for me (.454s vs .2309).
If we apply "BS-scaling" to the article table that would be 2.27*.2 = 0.454 sec on the author's machine which would make it twice as fast as the "simple C". Yet, if I actually run the simple C, I get 0.651 seconds, so only 651/454=1.43x "simple C" speed. This mismatch is, again, bigger than Go vs. RustB (0.38/0.28 = 1.35x). My only point is that you cannot just apply BS scaling and these results may very well fail to generalize across environments.
For what it's worth, literally every time I re-do anything in Rust in Nim, the Nim is faster. But benchmarks are like opinions...everyone has them and you should very much form your own, not delegate to "reputation". The best benchmark is actual application code. I make no positive general claims, but say this only because Rust people so often do. { EDIT: I think it is generally a big mistake to make many assumptions about prog.lang performance, especially if the assuming is on the "must be fast" side. }
Thanks! That's a much cleaner implementation, and I learned some cool nim. I got a note on GitHub with a similar implementation, so I went with theirs.
316 comments
[ 7.1 ms ] story [ 264 ms ] thread- foreach has hidden allocations
- there are better data structures than Dictionary
- GetValueOrDefault has higher cost than a plain if
What built in you'd use?
I would try it with a dictonary, that links to an array list with the counts.
C# supports non-allocating splitting via the Span / ReadOnlySpan see this article about this very question:
https://www.meziantou.net/split-a-string-into-lines-without-...
You can also use the Win32 APIs to more efficiently hook the console input:
https://stackoverflow.com/questions/33342340/fast-reading-of...
You can change foreach to for or whatever, but after you deal with the major program's bottlenecks.
https://perlmaven.com/count-words-in-text-using-perl
Throw in some needless array-referencing-and-dereferencing so people can rightfully consider perl a write-only language...
To be fair, I once came across a sentiment that was pretty close to "readability is bad". Taken from both the (bourne) shell and awk, perl has lots of short variables that determine parsing input and other matters, like "$/". You can then `use English` to have alternative names for that, but those might not be as well known ("$/" would be "$INPUT_RECORD_SEPARATOR", or "$RS" as a tribute to awk). So the line noise might be more common and thus more understandable than the "readable" version.
I don't quite buy that for e.g. "$INPUT_RECORD_SEPARATOR", but there's an argument to be made for "$RS" or "$ARG" being worse than the Asterix swear words.
And all great perl hackers deliver readable code. But we still enjoy a round of perl golf once in a while. And honor demands, that, if you respond in perl golf style to an interview question, you make it count ;)
perl -nle '$w{lc s/[[:punct:]]//r}++ foreach split(/\s+/,$_); print map{"$w{$_} $_ \n"} (sort{$w{$a} <=> $w{$b}} keys(%w)) if eof()' < kjvbible.txt
If anyone's curious this takes .47 seconds on my local machine whereas the optimized shell solution takes about 3.5 seconds.
Edit: It looks like mhd's usage of autosplit -a and @F are faster than split($_) but calling print foreach key is slower than my print map strategy.
So our solutions are combined to get:
perl -anle '$w{lc s/[[:punct:]]//r}++ foreach @F; END{print map{"$w{$_} $_ \n"} (sort{$w{$a} <=> $w{$b}} keys(%w))}' < kjvbible.txt
Which runs in .39 seconds. mhd's solution runs in .42 seconds. For reference the optimized C version takes .059 seconds (possibly cause of clang?), wc -w takes .023s and the optimized python version takes .288
Although maybe it's hard to judge a programming language separately from the culture around that programming language.
Since learning perl a couple years ago I personally only use it for one liners to replace sed/awk. If I do use perl in a script it’s usually in one liner form in a bash script to post process output from something like ripgrep.
Is there, in 2021, a "use strict" equivalent for Python, or can one still misspell variable names and not be warned about it?
Regex handling is still far nicer in perl than anywhere else, so for any script which is primarily about string parsing with regular expressions, perl is the right tool for the job.
That also makes it hard to win for total outsiders, though. This touches on core functionality, which often has quite a legacy behind it and thus its own vernacular. I can write `while (my $line = <STDIN>)` instead of `while(<>)`, but I can't get as easily rid of "chomp" being confusing to most people. A bit like car/cdr in Lisp.
But that happens even if you have plain english functions and no special cased syntax. Looking at the simple python version, it took some effort for me to remember what `Count.update(lst)` does, or that `most_common` without arguments returns all elements.
Perl has plenty of "good parts", too. But it is not an easy language to learn and even good idiomatic Perl code can be difficult to read. I don't blame people for favoring Python and Ruby.
The performance of Java there is super impressive. It should port relatively quickly to this file too...
[1] https://github.com/juditacs/wordcount
Any specifics on why it's not?
I wrote the simple Rust program. I've also been writing Go for a long time. It's tough to say precisely why, but here are some guesses:
* The simple variants, by virtue of being simple, do a lot of extra allocation. Go, because of its GC, might be able to do a bit better here. (I believe the Rust program also does more allocations than the Go program.)
* In Rust, all strings are UTF-8 validated. In Go, they are not. In Go, strings are only conventionally UTF-8.
* A good portion of these programs is spent interacting with a hashmap. Rust's default hashing algorithm is chosen to prevent HashDoS attacks[1] at the expense of slower hashing. I actually don't know whether Go's hashmap does the same. So I'm highlighting it here as a potential difference that perhaps someone else can elaborate on.
[1] - https://doc.rust-lang.org/std/collections/struct.HashMap.htm...
Thanks for taking the time to clarify specifics. I appreciate your attention.
I guess in Go strings are just a slice of bytes?
Isn't it possible to do the same with Rust for this benchmark?
But this is not the only additional cost in the Rust program. I outlined a few others.
> Isn't it possible to do the same with Rust for this benchmark?
This benchmark has two programs for each language. The "simple" and "optimized" variant. The "simple" version is supposed to be written in an idiomatic style for that language. Taking extra steps to make tweaks and optimize the code is, I think, against the spirit of the challenge. Obviously, this is a very fuzzy concept, and everyone can make up their own mind on the extent to which this framing is useful. (I think it is, personally, especially when you also allow for a second submission that tries to make the program fast.)
In Go I have used this [1] in the past when I had to validate UTF8 encoding but on hot paths where I'm sure UTF8 is valid (coming from sanitized database data for example) I skipped that part.
[1] https://golang.org/pkg/unicode/utf8/#Valid
That's what every single Rust program in this benchmark does, except for the simple variant.
1) Yes, almost certainly zero-cost. 2) This isn't a hot part of the program.
See also: https://old.reddit.com/r/rust/comments/m5ix0s/performance_co...
From looking at the code[1], it seems like it does. From[2] it looks like it is only for platforms that have AES.
1. https://github.com/golang/go/blob/7bfe32f39c59056c49f5776b10...
2. https://github.com/golang/go/issues/9365
And even then, you can't memory map all kinds of files. This is what happens when you assume that you can:
In the optimized C program, allocation is not a bottleneck. Pretty much all allocation is done upfront and that's all you need. There is an allocation for writing a new word to the table, but that's also amortized and isn't a big factor in the performance of the program in this particular benchmark.As for "bad spatial and temporal locality," can you be more specific? I guess the only thing I can see is perhaps inlining words smaller than some size into the same allocation as the hash table. But the hash table is otherwise one contiguous allocation.
I cannot find any stream constraint in either the article or the countwords repo. He just says "standard input" and his "test.sh" uses "<kjvbible_x10.txt".
You can mmap stdin/fd 0 after an `fstat(0,..)` no problemo. Can it fail and should you check errors? Sure (as can accessing stdin in any way, actually).
He even mentions memory-mapped IO as a further way to go in the article in the C part.
> Memory: don’t read whole file into memory. Buffering it line-by-line is okay, or in chunks with a maximum buffer size of 64KB. That said, it’s okay to keep the whole word-count map in memory (we’re assuming the input is text in a real language, not full of randomized unique words).
A shorter but less precise way of saying that is, "make the program work on streams."
> You can mmap stdin/fd 0 after an `fstat(0,..)` no problemo. Can it fail and should you check errors? Sure (as can accessing stdin in any way, actually).
Of course. And when it fails, what do you do? You defer to something that can handle a stream! Which is exactly the problem in the OP.
Honestly, I think the author himself saying memory-mapped IO is a forward direction but "enough for now!" is pretty conclusive that he didn't think it was a forbidden optimization direction. I think you are over interpreting his early step-by-step style language explaining finite memory as a strict spec, or perhaps he shared an earlier draft of the article with you before he wrote that.
It's fine to fail over to a stream, but often mmap is faster, as I know you know.
> It's fine to fail over to a stream, but often mmap is faster, as I know you know.
But that's exactly the point. You literally cannot use mmap in all cases, either because you just can't or because it's actually slower. And in those cases, you need to fail over to a streaming implementation. And that streaming implementation needs to be fast too. And that's what this benchmark is.
If you submitted a program that only used mmaps, and I sent a stream into that program, it would fail. So then you would need to modify the program to handle streams. And your strategy for dealing with mmaps couldn't be used. So then you'd need to optimize your handling of streams. Which is exactly what the programs in the OP are doing. So in the end, mmaps are a distraction for a benchmark like this, and I suspect that's why the OP didn't bother with them.
>I’m sure there’s further you could go with the C version: investigate memory-mapped I/O, avoid processing byte-at-a-time, use a fancier data structure for counting, etc. But this is quite enough for now!
This subthread started with bluetomcat talking about the optimized C and what experienced C devs might do. That strikes me as fair game to open up discussion of alternative IO anyway even if the author hadn't already (which he clearly did, as quoted). So, that's two reasons it's worth bringing up, and I was never criticizing your program!
If what you are on about is "Who wins what scorecard against what arbitrary constraints" or "My hands were tied, really!" or whatever, then, sorry, but this benchmark is too uncontrolled for great answers even on its own terms. Various stdio-using things would be "out of constraints" if a system was configured with bigger than 64K default buffers anyway which is certainly possible, if unlikely, today. None of the sample programs or the test harness "check" for that. Some of the languages may not be able to ensure it. Using that to leapfrog to "only streams" is a stretch. Is CPU freq scaling controlled? Min of N trials to filter background noise/get repeatability? Even simple mean+-sdev? No, no, and no. And probably four more things.
Beyond all of that, I also don't think that's what this subthread was ever about. bluetomcat's opening was literally the opposite - equivalent to "real devs would do xyz implicitly independent of the arbitrary constraints posed if performance is paramount"..seemingly a follow up on my quote from the author. He can of course chime in if I misread that. Presumably, the author would have had to relax that already problematic 64K constraint when moving on to mmap (which moving on he might have done if the article were fewer languages or if he had just done it that way first in his open coded C).
The positions you seem dug into here seems to me "don't mention mmap to people questioning the posing of the contest even though the author did" or "you cannot default to mmap and fail over like fstat||mmap||do_streams||aiie_noStdInEven". Yes, which is faster varies by OS/situation. So? Maybe "experienced" C/whatever devs know their situation. (You use mmap in ripgrep...). Maybe these are all honest communication errors, but I don't think your positions are very tenable.
As I mentioned in a few places, performance conclusions here are harder than they might look. As for "distractions", one might say that about literally all the optimized variants, including their numbers in the table since the numbers are likely to change more. The article might be stronger to focus on only the simple variants of all the rest, leaving the optimized ones for the github repo and weird "contest rule" debates on the github issues.
Anyway, to add a little more actual information for passersby less dug in to defending some weird position like "", Nim's stdlib has a trie in critbits module. So, that test is "in bounds" and an easy experiment someone might enjoy.
Have a nice day.
One could use a lexicographic Btree-like structure with multiple characters per node, sharing consecutive cache-lines. For looking up the word "bar", you would traverse the "b" key from the root node, then its child "a" node, then the "r" child of the "a" node. Most of the nodes near the top would remain hot in the cache, and deeper less-visited nodes could be joined or compacted based on some criteria. Of course there are many subtleties, special cases and complications and the solution would be far more complex in terms of source code length.
With a hash table, you effectively compute a hash for every word, and then jump at arbitrary locations throughout the whole table.
Like, maybe your idea works. Maybe. I don't know. You'd have to try it. But it's not clear to me that it will. And it doesn't support "is far from what an experienced C programmer would write if performance was paramount" IMO.
It isn't. It was only added in POSIX 2001. Still there without major changes in 2018. [0] (There's actually a lot of similar libraries in POSIX, that don't include re-entrant forms.)
Thankfully, re-entrant versions are supplied as extensions by GNU, which is significantly less horrifying.
[0] https://pubs.opengroup.org/onlinepubs/9699919799/basedefs/se...
It seems that the two hot spots are the std::string constructor (unsurprisingly) and the vector constructor.
Making string faster is not easy. I would check that gcc is configured to use C++11 strings with the small string optimization and not the older C++03 compatible refcounted string. Writing your own string or a custom allocator are options, but probably overkill for the problem.
The vector constructor is more surprising. It is possible that -O3 could help a bit there. Wrapping the map iterators with std::move_iterator would also avoid a lot of string copies.
Maybe use a vector-of-pointer-to-pair, since we're leaving the map around and we don't really need the vector to own anything.
Of course you could write significantly faster implementations in C (and probably in the other languages) by writing data structures from scratch especially for the job (and memory allocation strategies and maybe other stuff), and if you're the author of wc or grep then that is well worth doing because it will be used so many times relative to the amount of time for you to write that code. The comparison of the idiomatic C program vs grep is basically proof of that. But the article seemed to be targetting more typical developers than just want to plug together some common existing components.
Also, nice to see Forth included. I strongly suspect that if the Python solution were unable to leverage its rich and well optimised standard-library, it would be easily outpaced by Forth.
Also, the Forth solution used Gforth, which is far from the fastest Forth engine around. [0] It would likely have performed close to C if they had used a native-code-compiling Forth engine (SwiftForth, VFX Forth, or iForth, all of which unfortunately are proprietary payware).
[0] https://github.com/ForthHub/discussion/issues/88#issuecommen...
collections.Counter is a very straightforward collection backed by dict. The code isn't specially optimized, you can write the same code yourself with dict and even avoid (probably a negligible amount of) overhead.
Now, dict is optimized, but that's a builtin type. You don't need PSL.
https://github.com/python/cpython/blob/2fe408497e6838b6fb761...
Of course, they're right to optimize this way, and it's to Python's credit that it's possible to leverage this approach so successfully using only the standard-library, but I think my earlier point stands.
Again, very straightforward, based on dict. Python itself does not function at all without the dict implementation since it's the underpinning of the object model.
str is a builtin type. Calling str.split() a standard library method is... okay.
> Python itself does not function at all without the dict implementation since it's the underpinning of the object model.
Sure, but I don't see the point here.
> Calling str.split() a standard library method is... okay.
For our purposes there's no reason to draw a distinction between standard-library functionality closely integrated into the language, and standard-library functionality that isn't. The relevant point is that computational work is being handed off to optimised C code.
Again, if you're optimising Python, the smart move is indeed to make maximal use of the optimised machinery in the standard-library (or for that matter some other dependable library). My point still stands: it would be interesting to look at a problem that isn't amenable to this approach, where the performance of the Python interpreter itself would be brought to the fore by necessity.
How easy it is to find such a problem will be a function of how good a job Python does of providing applicable optimised functionality in its standard-library. Perhaps something like computing matrix determinants? I don't know enough Python to say.
It wouldn't matter, you'd be dealing with PyObject pointers in C anyway.
The same isn't true for, say, string operations, where there might be plenty of opportunity to move tight loops from Python to C and speed things up considerably.
Reading the bug report that introduced Counter[1], the author states it is the simplest implementation they came up with, and Guido and other maintainers prioritized simplicity.
[1] https://bugs.python.org/issue1696199
It would still be interesting to see for benchmark purposes.
I've seen ripgrep (in Rust, also by article contributor Andrew Gallant aka burntsushi) outperform grep in almost every way possible, both in benchmarks and in my experience.
In the case of grep and wc, the "optimized" variant is running with LC_ALL=C, which sets the locale to C. Presumably, the non-optimized variant is using the OP's default locale, which is maybe something like en_US.UTF-8. (Apologies for the US assumption, but what matters is that it's not the C locale.)
This is a common trick for speeding up GNU utilities when you're only working with ASCII data. It also works for things like `sort`.
In the case of grep, sometimes running with and without the locale will be about as fast, particularly if you're only searching for a simple ASCII literal pattern.
I suppose they are included as a baseline for reading a file and for tokenising strings into words. See https://github.com/benhoyt/countwords/blob/eb2a8adf21c895907...
No article like that is complete without a little C++ critique :-)
> I think it’s the simple, idiomatic versions that are the most telling. This is the code programmers are likely to write in real life.
I very much agree with him on this statement. If people started writing "optimized" versions of algorithms (on that level); who would ever be able to read others peoples code...
The one thing I would say is: as you dig more into C++ perf, you can develop an intuition for the kinds of things the compiler can and can't optimize. For instance, the C++ example from the article uses `std::unordered_map`, which is just an absolute mess from a cache locality perspective—the best compilers today (or of the foreseeable future) can't do a thing to fix that. Improving the programmer's choice of data structure is just not on the radar. :(
The loop ending condition might miss non-handled `remaining` (when there is no new-line at the end of the file). (The fix should be simple. Just move the check one line below.)
When there is no newline in some chunk, it would handle the word incorrectly at the chunk boundaries. (But ok, with the constraint that lines cannot be longer than the chunk size, this should not happen. But this could have been fixed easily anyway. Just `remaining = chunk; continue` + the other fix.)
Finding the "lower case of a character" is immensely harder in face of unicode, because the table is way larger and there's no nice speed hacks by manipulating an index into the ASCII table. JFGI: "tolower performance unicode".
If you notice setting LC_ALL makes a difference in performance for you, you ought to be aware that now you're no longer comparing same capabilities.
I'm not sure how to constructively state that except for: One shouldn't compare ASCII and unicode "tolower" in performance comparisons, as you end up comparing apples and oranges (at best. More like apples and snails) - which I did.
If the author uses code that uses "tolower" in job interviews, i.e., evaluates candidates based on their input WRT case normalization - and he even writes ("This is Unicode-aware ...") - he should know that Unicode awareness is not ubiquitous, and comes at quite a cost. Knowing about unicode awareness, one would assume he'd be aware of not making a fair comparison.
The only one I see is the comparison between 'simple' and 'optimized'. But that's more about "what does a simple idiomatic solution look like" and what does an "optimized and possibly less simple" solution look like. That comparison isn't designed to be apples-to-apples in the way you're saying. The simple variant will use Unicode-aware casing in environments where that's the simple and natural thing to do.
IIRC, most of the 'optimized' programs are using ASCII casing. Python doesn't, but casing isn't even close to the bottleneck in that program.
I'm no expert in any of the languages used except maybe C, at least I'm quick to form opinions about C code. In C, I'm not so sure that there is a well-established "idiomatic" concept, since C is not so tightly bound to a community as more modern languages. At least that's my feeling.
That said, I was shocked to see that the example code did heap-allocations to store integers. Single integers, one per allocation, per "counting bucket". I would store the count in the data pointer without a second thought, I just "can't" make 4/8-byte heap allocations and still sleep at night. Especially after all the concern about processing the input in large blocks for performance! Casting an integer to/from a void pointer should be pretty safe according to my gut feel. If that turns out to be false, I would dump the libc's hash API altogether, since it makes me do heap allocations to store single integers.
I tried making the change locally, and the time taken (as measured with the OP's benchmarking program) dropped from 0.11 to 0.10 on my system (a Dell laptop running an Intel i5-7300). That's at least something.
I thought POSIX added a bunch more safe pointer casts, but I don't know off the top of my head...
If you want to round-trip an integer through a pointer and back to the same integer, you can use any integer type provided it is not bigger than intptr_t or uintptr_t.
As I said, and others have commented, it requires some complicated castery to avoid UB, but it's totally doable (and at least GCC does the right thing, while warning, with no advanced casts).
Thanks for an interesting article!
Coming up with a benchmark is hard. Benchmarks like these are models. All models are wrong. But. Some are useful.
Follow you thinking to its logical conclusion. If you open up the parallel programming flood gates, now you need to do that for all of the programs. Now your effort to contribute a sample for each language goes up. Maybe enough where actually doing the benchmark isn't practical.
So let's play the tape. If someone told me, "sure, have fun, throw threads at this!" I'd probably say, "can I use memory maps?" And let's say, "yes, sure, go for it!" I say okay, here's my first crack at it:
1. Hope stdin is a file and open it as a memory map.
2. Split the memory map slice into N chunks where N is the number of logical CPU cores on the system.
3. Run approximately the same algorithm devised in existing code submissions in N different threads, with one thread per chunk.
4. At the end, join the results and print.
If that ends up being the best strategy overall, then your model has become over-complicated because performance now likely depends on step (3). Which is exactly what the existing benchmark is. Now, maybe some languages have a harder time passing data over thread boundaries than others and maybe that impacts things. But that doesn't apply to, say, C, Rust, C++ or Go.
If that's not the best strategy, then maybe there is a cleverer approach that involves synchronizing on one shared data structure. I doubt it, but maybe. If so, your benchmark turns into one that is very different. It's no longer just about data transformation, but now you have to worry about synchronization trickiness. And now you're way outside of a standard goroutine pool that you might have used in Go.
Building a good benchmark is an art. Sometimes the constraints look dumb and arbitrary. But you have to sit down and really look at it from a bunch of different angles:
* Do the constraints approximate some real world conditions?
* Do the constraints inhibit writing code that looks like real world code?
* Do the constraints inhibit optimizing the crap out of the code?
* Do the constraints make the benchmark difficult to create in the first place?
* Do the constraints permit easy and clear measurement?
There are probably more things that I didn't think about.
Consider re-reading my comment. It anticipated your criticism and responded directly to it.
If a "dumb" thread pool is indeed what ends up being the best concurrent solution, then Rust, Go, C and C++ (and probably most of the other languages) are going to have almost no problems implementing it. It's just Not That Interesting.
Now, maybe I'm wrong. Maybe there is something clever here to exploit in a concurrent program, and that some languages let you do that easier than others. I doubt it. It would be interesting if it turned out to be the case, but it would be a different benchmark. It wouldn't just be about how well a language can deal with simple data transformation tasks, but also about how it deals with tricky concurrency problems. But this doesn't seem like the kind of problem that needs such things. It complicates the model.
Like honestly, just saying that any benchmark that ignores parallelism "isn't very useful" is just totally ridiculous.
You have a point. Maybe I am wrong in saying that it's near useless.
> If a "dumb" thread pool is indeed what ends up being the best concurrent solution, then Rust, Go, C and C++ (and probably most of the other languages) are going to have almost no problems implementing it. It's just Not That Interesting.
Your argument makes sense if every language used the same form of concurrency or parallelism. Unfortunately, that isn't the case. Wouldn't the type of concurrency or parallelism affect performance?
> Now, maybe I'm wrong. Maybe there is something clever here to exploit in a concurrent program, and that some languages let you do that easier than others.
but concurrency / parallelism IS much easier in some languages vs others (did I misunderstand what you wrote?).
That's what I'm saying: almost certainly not IF the best concurrent solution to this problem is to chunk of the work and feed it off to a bog standard thread pool. Pretty much every language---even C---has tools that make this pretty easy to do.
And I don't see any reason why a dumb thread pool wouldn't be the best answer to this if parallelism were allowed. Like, the fact that Go has goroutines is just not going to help with anything for this kind of work-load. Goroutines help in more complex concurrent situations.
> but concurrency / parallelism IS much easier in some languages vs others (did I misunderstand what you wrote?).
When the extent of the parallelism is a dumb thread pool with no synchronization between them, then it's pretty easy to do that in just about any language.
That's the thing. This is not the case for all programming languages, even for some of the ones included this performance test. Python has a GIL. Distributing work via threads isn't going to do much unless it's something I/O intensive. Consequently, testing performance via a programming language's available methods to distribute work does matter. Special features like Goroutines also matter.
> When the extent of the parallelism is a dumb thread pool with no synchronization between them, then it's pretty easy to do that in just about any language.
The specific implementations of work distribution still matters for performance doesn't it? Different implementations yield varying levels of performance right?
You can question me all day. Go build the benchmark. Publish it. Have people scrutinize it. I have my prior based on building this sort of tooling for years and actually publishing benchmarks.
And you still continue to miss my point. Instead, we're in a hypothetical pissing match about code that doesn't exist. Either the parallelism problem is uninteresting, or your benchmark becomes about complex synchronization. The former complicates the benchmark for no good reason. The latter results in a different benchmark entirely.
Yes and distributing work with multiple processes is not the same as distributing it via threads. There is a difference in performance in different implementations and variations of concurrency and parallelism.
> we're in a hypothetical pissing match about code that doesn't exist. Either the parallelism problem is uninteresting, or your benchmark becomes about complex synchronization.
Yes, the code doesn't exist because it's difficult to do, and that's what makes it interesting.
I literally addressed that in my first comment: "Now, maybe some languages have a harder time passing data over thread boundaries than others and maybe that impacts things. But that doesn't apply to, say, C, Rust, C++ or Go."
> Yes, the code doesn't exist because it's difficult to do, and that's what makes it interesting.
Well, I mean, I haven't done it not because it's hard, but because it appears pointless to me. That's my prior. Show me I'm wrong. I'm happy to learn something new.
That's just your opinion and you haven't convinced me otherwise. Likewise, I don't think I'm going to convince you either.
> I literally addressed that in my first comment
Yes, but that doesn't mean that it's not an important point. Even if we were just comparing "C, Rust, C++ or Go.", different work distribution implementations have different sets of performance. It's hard, but it's still useful to capture that data because the real world doesn't run on a single thread or even a single core. If you're going to continue glossing over this, there's no point in continuing our discussion. We're just going in circles.
> Now, maybe I'm wrong. Maybe there is something clever here to exploit in a concurrent program, and that some languages let you do that easier than others. I doubt it. It would be interesting if it turned out to be the case, but it would be a different benchmark.
So the fact that you keep trying to niggle at the specifics of parallelism tells me that you're completely and totally missing my point. You're missing the forest for the trees.
Looking back at the convo, it started by you saying, "it would be nice to see parallelism considered." Fine. I responded by saying why that particular rabbit hole is probably not be so useful, or would be measuring something totally different than the OP. To which, you kind of flipped the script and said, "However, single thread benchmarks don't reflect the real world unless you're a student." It would have been a lot better to just say, "I disagree, but I don't have time to do the benchmark myself, so we'll have to leave it at that."
There's a lot of goalpost shifting going on. Like, are we arguing whether a parallel benchmark could be useful? Or are we arguing about whether a single threaded benchmark is useless? They are two different arguments. The former gets my response above, navel gazing at why that model probably isn't particularly useful. But the latter is just crazytown.
This is the source for it:
https://github.com/raitechnology/raikv/blob/master/test/ctes...
The speedup of the multi-threaded version vs the single-threaded version is about linear. The single threaded version uses 2 threads, one to read stdin and one to hash the keys, the 16 threaded version uses one thread to read, 16 to hash.
$ time ctest -t 1 < ~/data/enwiki-p10p30303 18.88user 0.25system 0:09.58elapsed 199%CPU
$ time ctest -t 16 < ~/data/enwiki-p10p30303 8.08user 0.25system 0:00.49elapsed 1680%CPU
https://benchmarksgame-team.pages.debian.net/benchmarksgame/...
Here, they have code samples and multiple implementations of each task in each language.
It's a great resource for, at a glance, how performant a language is at basic cpu and memory intensive tasks and how simple the related code is.
It still has the issue that some code is unrealistically optimized for the language. And also that many solutions use standard libraries written in other languages. It's worth looking at the source, therefore.
For the benchmarks game, C is not free to implement an optimized hash table for the problem.
The hash table used is from "Klib: a Generic Library in C".
https://benchmarksgame-team.pages.debian.net/benchmarksgame/...
Any of the programs are free to implement a "custom hash function" and many of them do.
hash table != hash function
Wikipedia is your friend -- "A hash table uses a hash function to compute an index, also called a hash code …"
Which languages shown on the benchmarks game website 'don't allow to specify custom hash functions …" ? https://en.wikipedia.org/wiki/Hash_function
> Probably intentionally
Wow.
2 tasks — pidigits & regex-redux — explicitly allow use of standard libraries (GMP, PCRE2, RE2) written in other languages.
8 tasks do not.
(Those standard libraries were allowed because some language implementations provided arbitrary precision arithmetic or regex by wrapping those standard libraries.)
Of course, realistic use of some languages relies on calling standard libraries written in other languages.
Also, as somebody else mentioned, iostreams are slow. Even simple reading of file can be several times slower than plain C (http://0x80.pl/notesen/2019-01-07-cpp-read-file.html).
https://en.cppreference.com/w/cpp/io/ios_base/sync_with_stdi...
(defmethod performance-count ((path-file string))
WEB> (time (performance-count "/home/frederick/performance-comparison.txt"))the 4
foo 2
defenestration 1
Evaluation took:
NIL WEB>Surely the correct answer is "use some established third party library that does this exact task well". Probably faster, better battle tested against weird input, localised etc etc than anything you can come up with by yourself.
Though obviously that is then useless if the interview is actually for someone who can actually write something like this for some super secret internal thing that is nothing like the problem solved by the standard solutions available. But is that really the case? I have doubts.
If I was hiring though, I'd be more worried about hiring people who would write standard elements from scratch (mostly because that's more fun) than re-use standard building blocks to get a task done correctly.
e.g. for this specific question I'd be most impressed with someone who could talk about Spacy or some other standard library that can do a lot of things in this area very quickly but also be repurposed to do interesting new things. Do I need someone who can write Spacy from scratch or someone who can use Spacy?
Immediately optimising by ignoring non-ASCII and punctuation seems mor elike a red flag than a positive.
The point of questions like this is to test basic understanding, not the ability to search on SO or similar.
> If I was hiring though, I'd be more worried about hiring people who would write standard elements from scratch (mostly because that's more fun) than re-use standard building blocks to get a task done correctly.
As long as the hire is able to fix/extend the 3rd party library on their own... this is exactly what you figure out with "these types of questions".
There are cases where your task is nice, simple, and well-defined, but word counting is not one of them. It's better to give a more realistic task that allows people to think about the premises.
If it's instead explicitly given that this is a quick litmus test, the choices of the first pass implementation don't really matter, and you'll talk about complexities after, then sure.
I seriously doubt such a library exists for most languages (Javascript might be an exception because they seem to love writing one-line libraries). It's such a simple task!
[1] https://news.ycombinator.com/item?id=24817594
[2] https://github.com/c-blake/adix/blob/master/tests/wf.nim
Honestly, the optimized version you created is kind of opaque; I don't want people to think that that's what "typical" nim looks like.
I'll do a pull request on the project for mine as simple (I'd have added your version as an optimized version, but I couldn't get it to compile).
On my machine, the simple-c version runs in 0.70 seconds, my simple nim runs in 0.73 seconds (and they produce the same output, which is nice :-), the nim executable is 95k.
[0]: https://github.com/csterritt/word_frequency_nim/blob/master/...
Feedback-wise, yours isn't so bad, though I haven't tested it. There is definitely a simpler one that looks roughly like the Python and probably runs a bit slower than yours. That would probably be a better/more fair candidate for the "simple" category, but it probably still has ok-ish performance.
If we apply "BS-scaling" to the article table that would be 2.27*.2 = 0.454 sec on the author's machine which would make it twice as fast as the "simple C". Yet, if I actually run the simple C, I get 0.651 seconds, so only 651/454=1.43x "simple C" speed. This mismatch is, again, bigger than Go vs. RustB (0.38/0.28 = 1.35x). My only point is that you cannot just apply BS scaling and these results may very well fail to generalize across environments.
For what it's worth, literally every time I re-do anything in Rust in Nim, the Nim is faster. But benchmarks are like opinions...everyone has them and you should very much form your own, not delegate to "reputation". The best benchmark is actual application code. I make no positive general claims, but say this only because Rust people so often do. { EDIT: I think it is generally a big mistake to make many assumptions about prog.lang performance, especially if the assuming is on the "must be fast" side. }
And, cool, "BS-scaling" is my new term of art :-)