45 ms·

Performance comparison: counting words in Python, Go, C++, C, Awk, Forth, Rust

• alexeiz 6y ago
  It's amazing how clean and small the simple C++ implementation is. It's smaller than Go and Rust. With C++20 features it can be even terser.
• deleted 6y ago
  [deleted]
• ephaeton 6y ago
  This shouldn't compare unicode-aware 'tolower' with ASCII-tolower ... sends false signals. "Optimizing" by setting LC_ to "C" .. oh my.
  • 1f60c 6y ago
    If you know something the author doesn't, I'm sure they'd appreciate a (constructive!) reaction blog post.
    • ephaeton 6y ago
      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.
      • burntsushi 6y ago
        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.
      • jerf 6y ago
        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.
      • benhoyt 6y ago
        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".
• s9w 6y ago
  I've never seen a multi-lang benchmark without glaring mistakes in a subset of them
• thefilmore 6y ago
  The link to the repo is broken.
  • benhoyt 6y ago
    Thanks for that - fixed. Repo link is: https://github.com/benhoyt/countwords https://github.com/benhoyt/countwords
• pjmlp 6y ago
  The C# is clearly not optimized, if the goal is to win micro-benchmarks. - foreach has hidden allocations - there are better data structures than Dictionary - GetValueOrDefault has higher cost than a plain if
  • deleted 6y ago
    [deleted]
  • tester34 6y ago
    >there are better data structures than Dictionary What built in you'd use?
    • andix 6y ago
      Some structure, where you don't have to do a keynlookup twice, for incementing the number. I would try it with a dictonary, that links to an array list with the counts.
      • deleted 6y ago
        [deleted]
  • burntsushi 6y ago
    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.
  • acdha 6y ago
    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.
    • pjmlp 6y ago
• oefrha 6y ago
  Text processing, without a single mention of Perl. How times have changed.
  • asicsp 6y ago
    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 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
  • mhd 6y ago
    Would perl -lane '$c{lc $_}++ for @F;END{print "$_ $c{$_}" for sort {$c{$b}<=>$c{$a}||$a cmp $b} keys %c}' < input.txt work?
    • deleted 6y ago
      [deleted]
    • jlg23 6y ago
      If you interviewed for a perl job, you'd probably be disqualified for writing code that is too readable ;)
      • anthk 6y ago
        Perl is readable, just indent it.
        • nerdponx 6y ago
          What is the readable indented version of this? perl -anle '$w{lc s/[[:punct:]]//r}++ foreach @F; END{print map{"$w{$_} $_ \n"} (sort{$w{$a} <=> $w{$b}} keys(%w))}'
• nicholasjarr 6y ago
  Really great stuff. Good job!
• tadkar 6y ago
  There is a similar great project here [1] with the Hungarian Wikipedia corpus. Great workout for non English and maybe non-ascii operations. The performance of Java there is super impressive. It should port relatively quickly to this file too... [1] https://github.com/juditacs/wordcount https://github.com/juditacs/wordcount
  • jeromeof 6y ago
    Great, it would be nice if Java was included by the op
• hu3 6y ago
  I expected Rust to be faster than trivial Go code. Any specifics on why it's not?
  • burntsushi 6y ago
    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. [1] - https://doc.rust-lang.org/std/collections/struct.HashMap.html https://doc.rust-lang.org/std/collections/struct.HashMap.htm...
    • hu3 6y ago
      Hey! The great burntsushi himself answering me. 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?
      • burntsushi 6y ago
        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.)
• kzrdude 6y ago
  (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.
  • bluetomcat 6y ago
    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.
    • burntsushi 6y ago
      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.
      • cb321 6y ago
        > 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.
• gpderetta 6y ago
  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.
  • sesuximo 6y ago
    Why copy the string at all? You have string in file. Mmap file and just store string view of it.
    • gpderetta 6y ago
      you can't mmap a pipe unfortunately and that's a very valid use case. At the very least you would need two distinct code paths.
  • thestoicattack 6y ago
    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.
    • gpderetta 6y ago
      good point about the string being const! There are ways around that, but none pretty.
  • usefulcat 6y ago
    -O3 makes basically no difference for this code. I tried it.
• Ballas 6y ago
  But both wc and grep are written in C...
  • Simplicitas 6y ago
    exactly .. this is the part I don't understand
  • dgellow 6y ago
    You can see them as a baseline
  • dcu 6y ago
    https://lists.freebsd.org/pipermail/freebsd-current/2010-August/019310.html https://lists.freebsd.org/pipermail/freebsd-current/2010-Aug...
  • quietbritishjim 6y ago
    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.
• deleted 6y ago
  [deleted]
• MaxBarraclough 6y ago
  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). [0] https://github.com/ForthHub/discussion/issues/88#issuecomment-796955928 https://github.com/ForthHub/discussion/issues/88#issuecommen...
  • oefrha 6y ago
    > 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. https://github.com/python/cpython/blob/2fe408497e6838b6fb761e42e8f8ffc70bd6f3b1/Lib/collections/__init__.py#L649-L681 https://github.com/python/cpython/blob/2fe408497e6838b6fb761...
    • MaxBarraclough 6y ago
      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.
      • oefrha 6y ago
        I practically linked to _collections._count_elements already (linked Counter.update instead because I thought linking to the call site is clearer), but here it is: https://github.com/python/cpython/blob/2fe408497e6838b6fb761e42e8f8ffc70bd6f3b1/Lib/collections/__init__.py#L519-L523 https://github.com/python/cpython/blob/2fe408497e6838b6fb761... 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.
• cies 6y ago
  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.
  • burntsushi 6y ago
    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.
    • rtb 6y ago
      The "grep" and "wc" commands that are included in that table don't attempt to solve the problem. That wasn't clear to me on first reading. 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/eb2a8adf21c895907a7abd14a66650eb1f83c1a4/benchmark.py#L23 https://github.com/benhoyt/countwords/blob/eb2a8adf21c895907...
• toppi 6y ago
  Here is a similar excercise. Ad-hoc programs in different languages generate a long list of random numbers. How long does it take? https://github.com/posch/generate-random-numbers https://github.com/posch/generate-random-numbers
• bjarneh 6y ago
  > 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...
  • wirthjason 6y ago
    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.
    • s3cur3 6y ago
      Link to the (great) CppCon talk: https://www.youtube.com/watch?v=bSkpMdDe4g4 https://www.youtube.com/watch?v=bSkpMdDe4g4 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. :(
• deleted 6y ago
  [deleted]
• albertzeyer 6y ago
  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.)
• josefx 6y ago
  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. 0.00 0.00 32187/32187 std::vector<std::pair<std::string,int> >::vector<std::__detail::_Node_iterator<std::pair<std::string const, int>, false, true>,void> ( std::__detail::_Node_iterator<std::pair<std::string const, int>, false, true>, std::__detail::_Node_iterator<std::pair<std::string const, int>, false, true> > const& ) [11] 0.0 0.00 0.00 32187 void std::string::_M_construct<char*>(char*, char\*, std::forward_iterator_tag) [8] 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.
• unwind 6y ago
  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.
  • c-cube 6y ago
    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.
    • remexre 6y ago
      hcreate is POSIX, hcreate_r (which allows having multiple hashmaps per process) is the GNU extension, iirc. I thought POSIX added a bunch more safe pointer casts, but I don't know off the top of my head...
      • therealcamino 6y ago
        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.
• throwaway13337 6y ago
  For more language benchmarks of this sort, there is a pretty extensive list: https://benchmarksgame-team.pages.debian.net/benchmarksgame/index.html 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.
  • _ph_ 6y ago
    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.
    • igouy 6y ago
      You are very sceptical of which benchnmarks ? 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/program/knucleotide-gcc-1.html https://benchmarksgame-team.pages.debian.net/benchmarksgame/...
      • _ph_ 6y ago
        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. quite contradicting your statement.
        • igouy 6y ago
• wmu 6y ago
  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. 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 http://0x80.pl/notesen/2019-01-07-cpp-read-file.html).
  • jpcooper 6y ago
    Maybe due to stdio synchronisation? This can be turned off. https://en.cppreference.com/w/cpp/io/ios_base/sync_with_stdio https://en.cppreference.com/w/cpp/io/ios_base/sync_with_stdi...
    • usefulcat 6y ago
      He did that: "This line makes it run almost twice as fast: ios::sync_with_stdio(false);"
• submeta 6y ago
  Would love to see this for Common Lisp.
  • fishmaster 6y ago
    Me too. Alas, I can't do it myself.
  • gibsonf1 6y ago
    Common Lisp (sbcl.org): (non-optimized - needs to remove need for consing) (defmethod performance-count ((path-file string)) (let ((map (make-hash-table :test 'equal))) (with-open-file (stream path-file :direction :input :if-does-not-exist nil) (when stream (loop for line = (read-line stream nil 'end) until (eq line 'end) do (let ((split (split-string #\space (string-downcase line)))) (dolist (word split) (let ((index (gethash word map))) (if index (setf (gethash word map) (incf index)) (setf (gethash word map) 1)))))) (let ((keys (sort (alexandria:hash-table-keys map) (lambda(x y)(> (gethash x map)(gethash y map)))))) (dolist (key keys) (format t "~A ~A~%" key (gethash key map)))))))) WEB> (time (performance-count "/home/frederick/performance-comparison.txt")) the 4 foo 2 defenestration 1 Evaluation took: 0.000 seconds of real time 0.000294 seconds of total run time (0.000000 user, 0.000294 system) 100.00% CPU 757,077 processor cycles 0 bytes consed NIL WEB>
    • fishmaster 6y ago
      Does that use the corpus from the article?
• ZeroGravitas 6y ago
  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.
  • jlg23 6y ago
    > 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".
  • hamburglar 6y ago
    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.
• cb321 6y ago
  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. [1] https://news.ycombinator.com/item?id=24817594 https://news.ycombinator.com/item?id=24817594 [2] https://github.com/c-blake/adix/blob/master/tests/wf.nim https://github.com/c-blake/adix/blob/master/tests/wf.nim
  • chris_st 6y ago
    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. [0]: https://github.com/csterritt/word_frequency_nim/blob/master/wf.nim https://github.com/csterritt/word_frequency_nim/blob/master/...
    • cb321 6y ago
      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.
      • cb321 6y ago
        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. }
• jonathanstrange 6y ago
  I've got to say I'm rather happy with Go's performance and verbosity of the unoptimized version in this micro-benchmark. For me it's just the right trade-off. Go was the right choice for my current project. I don't need it faster but wouldn't want my garbage-collected language to be substantially slower. I suppose SBCL would be in a similar ballpark for this task, though, and would love to see an unoptimized SBCL version.
  • easytiger 6y ago
    This test also doesn't take into account if this was a long runing process continually churning whats the effect on GC/RC pauses etc.
    • _ph_ 6y ago
      The nice thing about the Go GC is, it runs completely in parallel to your program, so that there are no significant GC pauses any more (typically far below the millisecond range, rather microseconds).
      • easytiger 6y ago
        I'm aware, but alas in my domain anything above 50us is "noticeable" if it happens regularly
        • analognoise 6y ago
          HFT?
          • easytiger 6y ago
            Something like that yes
        • _ph_ 6y ago
          It might be a noticeable delay if you require quick response by the program, but won't have a significant impact on the total run time of the program.
• throwaway4good 6y ago
  Here is my solution in JS: "The foo the foo the defenestration the" .split(/\s/) .map(w => w.toLowerCase()) .reduce((m, w) => { m[w] = m[w] ? m[w] + 1 : 1; return m }, {}) I haven't checked the performance, though ...
  • frankenst1 6y ago
    One of the specs is to not read the file in full but to parse it in chunks from stdin. You also need to sort the output by count.
• MauranKilom 6y ago
  Regarding speed of the C++ version: The fundamental mistake is to use std::unordered_map. The standard library map and set implementations (both ordered -> tree-based and unordered -> hash-based) are almost never the correct choice if you care about performance. That's definitely a flaw in the language, but like with C you would just use a different implementation for this purpose.
  • jjnoakes 6y ago
    To expand on this a bit, the C++ unordered map (hash table) uses basically a linked list to track the entries in each bucket (separate chaining for collisions) because the standard requires that operations that may resize the map don't invalidate iterators. You pay for this with extra memory allocations and non-contiguous memory access. In most low level benchmarks, other collision mechanisms (probing, etc) perform much better.
  • usefulcat 6y ago
    Although std::unordered_map is definitely not nearly as fast as a hash map can be in c++, that's probably not the main problem here. I would bet on iostreams and/or tolower being bigger problems. Note that tolower is called for every /character/. I don't know everything it does, but I know it's doing some semi-esoteric locale stuff, and in general it's doing a lot more than a naive ascii implementation would. I seem to recall it's even doing a dynamic_cast in there somewhere. For each character of input. I was curious, so I ran callgrind on it. Here are the top 10 offenders (by Ir, 'instructions retired'). For clarity I have elided many details. Total Ir is 5,647,099,795, so the stuff below accounts for greater than 50% of all Ir. 1,079,594,033 std::istream& operator>>(std::istream&, std::string&) 553,657,533 std::istream::sentry::sentry(std::istream&, bool) 550,159,646 __cxxabiv1::__vmi_class_type_info::__do_dyncast(...) 426,992,280 __dynamic_cast 413,240,330 std::_Hash_bytes(void const*, unsigned long, unsigned long) 383,294,340 tolower 230,374,111 std::string::_M_append(char const*, unsigned long) 223,653,549 /usr/include/c++/9/bits/stl_algo.h:main 172,438,098 __strcmp_avx2 164,226,680 std::ctype const& std::use_facet(std::locale const&)
• super_mario 6y ago
  Isn't grep really optimal C implementation?
  • kevincox 6y ago
    grep doesn't solve the problem.
• macgyverismo 6y ago
  I was suprised at the C++ outcome, so I started testing myself. I was very amazed to find a 4~5x speedup when reading directly from file (std::ifstream) instead of reading stdin. This was on a 10.5.7 MBP 2014 [edit] more like 9~10x actually... time { ./build/Release/countwords_ifstream; } | tail ... real 0m1.337s user 0m1.332s sys 0m0.022s time { ./build/Release/countwords_original < kjvbible_x10.txt; } | tail ... real 0m12.184s user 0m12.138s sys 0m0.044s changes between these two: 6a7 > #include <fstream> 8a10 > std::ifstream inp( "/Users/macgyverismo/Desktop/test/kjvbible_x10.txt" ); 13c15 < while (std::cin >> word) { --- > while (inp >> word) {
  • nerdponx 6y ago
    Is that due to something at the OS or filesystem driver level?
  • c-cube 6y ago
    Could be a lock on stdin that is acquired in a loop? Rust has such a lock and typically one should lock stdin at the beginning and read from within the critical section.
  • FAANG_dream 6y ago
    Try this maybe? https://codeforces.com/blog/entry/6251 https://codeforces.com/blog/entry/6251
    • macgyverismo 6y ago
      Asuming you mean 'std::ios::sync_with_stdio(false);', that was already present in the original code.
  • usefulcat 6y ago
    I tried that on Linux and got at best a 5% improvement.
    • benhoyt 6y ago
      Yeah, I'm on Linux too and tried that with no noticeable difference in results. There's something off about macOS's approach.
• mikewarot 6y ago
  I read it as counting source code words, in which case Linux Shell scripts really won this contest. I'm not a linux/shell expert, but I really, really thought the shell script was the most performant answer... it was quite legible even to this Windows user, and only had one line of text.
• gibsonf1 6y ago
  Unoptimzed version in Common Lisp (so has consing) (see performance against bible and bible x 10 later in this thread) For kjvbible.txt at (unoptimized) 0.365 is 3rd fastest beating C, and 4th faststest beating optimized Go (would be interesting to see how fast the optimized Lisp would be) Common Lisp (sbcl.org): (defmethod performance-count ((path-file string)) (let ((map (make-hash-table :test 'equal))) (with-open-file (stream path-file :direction :input :if-does-not-exist nil) (when stream (loop for line = (read-line stream nil 'end) until (eq line 'end) do (let ((split (split-string #\space (string-downcase line)))) (dolist (word split) (let ((index (gethash word map))) (if index (setf (gethash word map) (incf index)) (setf (gethash word map) 1)))))) (let ((keys (sort (alexandria:hash-table-keys map) (lambda(x y)(> (gethash x map)(gethash y map)))))) (dolist (key keys) (format t "~A ~A~%" key (gethash key map)))))))) WEB> (time (performance-count "/home/frederick/performance-comparison.txt")) the 4 foo 2 defenestration 1
  • paulgdp 6y ago
    Your result is very surprising probably because you benchmarked on the very small example corpus whereas other languages were benchmarked on a much much bigger corpus
    • woliveirajr 6y ago
      On a 4.3MB file: https://github.com/benhoyt/countwords/blob/master/kjvbible.txt https://github.com/benhoyt/countwords/blob/master/kjvbible.t...
      • duckerude 6y ago
        That file repeated 10 times, even: https://github.com/benhoyt/countwords/blob/master/test.sh https://github.com/benhoyt/countwords/blob/master/test.sh
        • gibsonf1 6y ago
          On x10 (no optimization yet so consing is killing performance): firmament: 10 firmament, 10 genesis 10 version 10 Evaluation took: 2.798 seconds of real time 2.813069 seconds of total run time (2.677126 user, 0.135943 system) 100.54% CPU 8,125,595,437 processor cycles 934,110,048 bytes consed
• maccam912 6y ago
  I don't trust myself to write a decent version, but if someone here wants to do some marketing for Nim I'm sure the code would be compact and easy to read, but could still end up quite fast here!
• rurban 6y ago
  So this basically confirms Bentley's famous Programming Pearls book results from 1986. Nothing much changed.
• OskarS 6y ago
  I would have loved to see the Knuth version (which was literate Pascal with WEB, I think) compared as well, but I imagine that is a nightmare to build. I wonder if the source code is available anywhere, I can't recall ever seeing it. I think Knuth used a custom-made trie, and it would be interesting to see that compared to these hash table based solutions. Also: this comparison honestly just makes me love AWK more and more. So little code needed! So concise, and pretty ok performance as well! AWK really is an underrated little language.
• haolez 6y ago
  FORTH is the ideal language for a zombie apocalipse. Nothing comes close when you start with a CPU and nothing else :)
  • anthk 6y ago
    I like it (and collapseos), but scheme would be more amazing for that projec; because well, once I saw some Spaniard doing vector algebra in Forth exercises and my head nearly exploded. Forth is ideal to compose new words, but sometimes playing with the stack look like juggling.
• jeffbee 6y ago
  If the author doesn’t know how to use C++ they should not have included it. It just leads to everyone commenting on that defective aspect of the article, instead of the rest of it.
• djhworld 6y ago
  Can someone explain this bit (re: Go implementation) > To reduce the allocations, we’ll use a map[string]*int instead of map[string]int so we only have to allocate once per unique word Does the `map[string]int` approach allocate a new integer each time it is incremented?
  • deleted 6y ago
    [deleted]
  • coder543 6y ago
    Yeah. I want to check that locally... I don't feel like that's doing anything useful here. For starters, ints aren't normally "allocated" (in the heap sense). Go is value oriented, not reference oriented. I feel like the bigger change in the code was avoiding the allocation of the string for each word in the source text, and instead passing the byte slice directly to the point where it was used as the map key. Since strings are immutable, when you convert a byte slice to a string, it must be copied into a new immutable backing slice so that no one else can touch it. The exception is that the compiler optimizes map accesses where the key is a string type, but the code is converting a byte slice into a string at the point of using it as a map key. The compiler elides that conversion, making it a no-op, and instead just passes the byte slice in, since the hash map can make a copy of the string if it needs to, but it will otherwise avoid the unnecessary allocation and copying that converting this would otherwise require. I feel like that's where the big difference is. Heap allocating the integers and storing references in the map doesn't feel like it's actually doing anything here, although storing pointer values in maps can be useful in certain scenarios.
  • cp9 6y ago
    https://github.com/golang/go/issues/45021 https://github.com/golang/go/issues/45021
  • benhoyt 6y ago
    No, map[string]int doesn't allocate ints. Why the map[string]*int version is faster is because it avoids a "write" to the map when you're not adding new words -- it can just look up the pointer and increment what it points to. The Go compiler is not smart enough (yet) to optimize the former to avoid a map write. (That's my understanding, anyway.)
• typon 6y ago
  The (unoptimized) Python version is fast enough and imo the most readable.
• Shadonototro 6y ago
  I don't like C#, but before "doing benchmark", you should probably learn to write efficient code, because your code is very naïve, and i'm being polite split creates a new array and you do it each lines, that's not what you want Javascript scripters shouldn't program, they shouldn't write benchmark neither And that's just for C#, the C++ code you wrote is worse than we a 1st day junior would spit
  • lionkor 6y ago
    I absolutely agree, and would like to add that the C example further reinforces this
• platz 6y ago
  Would love to see this for Haskell as well for comparison (both a simple, idiomatic solution as well as a more optimized approach via profiling)
  • sullyj3 6y ago
    Luckily, that very article exists! https://chrispenner.ca/posts/wc https://chrispenner.ca/posts/wc Edit: upon reading the article it seems like the'yre different kinds of word counting. Still interesting and worth reading nevertheless!
• rtb 6y ago
  What are the "grep" and "wc" lines doing in the results? I can't find them in his git repos. Does he have a solution for the problem using grep, or is he just including "grep x <input" as a reference point for how fast you can read a file?
  • fmos 6y ago
    The grep version searches the input for "foobar" [1]. Hence, it doesn't solve the problem. [1] https://github.com/benhoyt/countwords/blob/eb2a8adf21c895907a7abd14a66650eb1f83c1a4/benchmark.py#L23 https://github.com/benhoyt/countwords/blob/eb2a8adf21c895907...
    • rtb 6y ago
      Thanks! I think he should make that a lot clearer in the "results" table.
      • benhoyt 6y ago
        Thanks for the feedback. I was trying to make that clear with "grep reference", but you're right, it's still ambiguous. I'll add a note to clear it up. Both "wc" and "grep" don't solve the problem, they're just comparisons to see how fast other programs can read the input (and in wc's case, tokenize into words). For grep, I'm using "grep foobar".
• Shorel 6y ago
  No Dlang included makes me sad.
• lionkor 6y ago
  seriously, scanf in a loop, strdup, etc.? the reason C can be so fast is because a SKILLED developer can write very optimized code. The C and C++ examples are not written well by any means. All this article does is demonstrate that a less complex language is easier to write "good enough" code in.
  • methyl 6y ago
    > All this article does is demonstrate that a less complex language is easier to write "good enough" code in. Is Rust less complex than C?
    • ZoomZoomZoom 6y ago
      Depends on your point of view. Rust has more complexity hidden in layers underneath the one a developer is working with directly.
  • mymatsubara 6y ago
    The scanf and strdup are used in the unoptimized version, which I think is completely fair.
• Shorel 6y ago
  This is definitely the most interesting part of the article for me: Incidentally, this problem set the scene for a wizard duel between two computer scientists several decades ago. In 1986, Jon Bentley asked Donald Knuth to show off “literate programming” with a solution to this problem, and he came up with an exquisite, ten-page Knuthian masterpiece. Then Doug McIlroy (the inventor of Unix pipelines) replied with a one-liner Unix shell version using tr, sort, and uniq. http://www.leancrew.com/all-this/2011/12/more-shell-less-egg/ http://www.leancrew.com/all-this/2011/12/more-shell-less-egg...
  • felixr 6y ago
    If you want to read the " ten-page Knuthian masterpiece": https://homepages.cwi.nl/~storm/teaching/reader/BentleyEtAl86.pdf https://homepages.cwi.nl/~storm/teaching/reader/BentleyEtAl8... I don't think it was linked from the article
  • jerf 6y ago
    I have seen it observed that while the tr/sort/uniq approach has practical value, that if the question is how would you implement the features that tr/sort/uniq provide simply invoking them is not much of an answer. I don't think Knuth was unaware that there were existing tools that could solve the problem, the whole point was to demonstrate his literate programming approach at some semi-reasonable scale on a problem everyone could recognize. It's kinda like how pretty much every interview-sized question has some sort of off-the-shelf solution somewhere, because anything that fits into an interview has been solved thousands of times over... but that's not the point of interviews. In modern terms, it would be something like complaining that $LANGUAGE's web server implementation is a grotesque bloated mess (and therefore $LANGUAGE isn't very good) because in shell all I have to do is run "nginx". There is a true and useful sense in which that is true, but there is also a true and useful sense in which that is utterly missing the point.
  • 35fbe7d3d5b9 6y ago
    I've always personally disliked McIlroy's oft-quoted conclusion (emph. mine): > Knuth has shown us here how to program intelligibly, but not wisely. I buy the discipline. I do not buy the result. He has fashioned a sort of industrial-strength Fabergé egg—intricate, wonderfully worked, refined beyond all ordinary desires, a museum piece from the start. Well, yes – absolutely. If you read the initial column[1] pre-McIlroy's response, you'll see that Knuth is not presenting a word-counting solution, but instead the concept of literate programming and how intertwining code and prose can be better for the programmer. Knuth isn't trying to count words, he's trying to teach you a different way to develop, and he's doing it by showing an example that has been simplified so the average person can chew on it. I'm not sure if the popular interpretation of "ivory tower Knuth versus tactical genius McIlroy" is a modern take or if that was how it was received when the column was published, but it feels very unfair to present it as such today. [1]: https://doi.org/10.1145/5689.315644 https://doi.org/10.1145/5689.315644
• frankenst1 6y ago
  Here are my results with JavaScript (node.js v14.15.4) added: Language | Simple | Optimized | Notes ------------- | ------ | --------- | ----- `wc -w` | 0.17 | 0.16 | `wc` reference; optimized sets `LC_ALL=C` `grep` | 0.53 | 0.54 | `grep` reference; optimized sets `LC_ALL=C` Go | 0.82 | 0.29 | C | 0.83 | 0.20 | Rust B | 1.10 | 0.28 | also by Andrew: bonus and custom hash JavaScript | 1.29 | | no readline JavaScript | 1.81 | | with readline Rust A | 1.55 | 0.30 | by Andrew Gallant Python | 2.14 | 1.17 | Ruby | 3.59 | | AWK | 4.28 | 1.22 | optimized uses `mawk` C++ | 6.68 | 0.83 | "optimized" isn't very optimized Shell | 42.60 | 9.50 | optimized does `LC_ALL=C sort -S 2G` Btw: is there something wrong with my shell? //with readline const rl = require('readline').createInterface(process.stdin); const wordCounter = {}; rl.on('line', (line) => { let words = line.toLowerCase().split(/\s+/).forEach(word => { wordCounter[word] = (wordCounter[word] || 0) + 1; }); }).on('close',() => { let output = Object.entries(wordCounter) .sort(([,countA],[,countB]) => countB - countA) .map(wc => wc.join(" ")) .join("\n"); console.log(output); }); -------------------------------------------- //without readline const wordCounter = {}; let lastChunk = ''; process.stdin.on('data', chunk => { let words = (lastChunk + chunk.toString().toLowerCase()).split(/\s+/); if (!words.length) return; lastChunk = words.pop(); for (let word of words) { if (word) wordCounter[word] = (wordCounter[word] || 0)+1; } }).on('end',() => { if (lastChunk) wordCounter[lastChunk] = (wordCounter[lastChunk] || 0)+1; let output = Object.entries(wordCounter) .sort(([,countA],[,countB]) => countB - countA) .map(wc => wc.join(" ")) .join("\n"); console.log(output); });
  • deleted 6y ago
    [deleted]
• ncmncm 6y ago
  These things invariably report misleading results just because the author can't be bothered to learn to write idiomatic code in most of the languages. Nobody is obliged to learn that many languages well, but truth demands scruples. If you are not interested in truth, what is the point of publishing one of these? The result is predictable: whichever language the author already knows best wins. In this one, for example, we get: "There’s obviously a lot more pushing you could do with C++. However, I suspect it would end up getting more and more low-level and more C-like" which is just wholly false. There are reasons why the people who are the most serious about performance use C++: you can get C++ code as fast as the machine can physically do without giving up any abstraction or readability, and without avoiding powerful features. That is the core value proposition of the language: abstraction without penalty. It delivers, and not by accident. To get top performance does require awareness of what operations are inherently slow for machines, and not writing code to require such operations. But that doesn't mean giving anything up. Code that looks like C is no faster than C. Hence, to make code faster than C, you must make it look less like C. Really, we don't expect an article like this to reveal all about how to write the best code in all languages. Just don't report lazy falsehoods.
  • burntsushi 6y ago
    Why not write the C++ program? It's not like the OP presented the C++ program as the shining example of what the best looks like. They inserted plenty of caveats. And FWIW, I ported the optimized C program to Rust. They look very similar even though Rust is all about zero cost abstractions as well. So the OP's claim really isn't that ridiculous.
    • ncmncm 6y ago
      In the old days we said, "You can write Fortran in any language", meaning you can write bad code in any language. But that is not a reason to write bad code. Idiomatic Rust, like idiomatic C++, is faster than C. So, your C-in-Rust runs like C, slow, not like good Rust or good C++, fast.
      • burntsushi 6y ago
• Shorel 6y ago
  Real life application for this exercise (I use a python version from time to time): Count the frequency of words in a book, then get the most frequent words you don't know in Anki, so you can learn the words that will help you understand more of the text. This is of course taken from the Fluent Forever book. Example from Малкият принц: какво 62 са 61 ако 58 когато 56 ме 55 беше 53 а 51 планета 51 ли 49 човек 43 едно 42 бе 42 ден 42 който 40
  • machiaweliczny 6y ago
    I have python script that takes on the book, does what you said and translates everything also. Very helpful, with this + list od 2K most popular words learned english in 2 books when in middle school.
    • Shorel 6y ago
      Care to share it?
      • machiaweliczny 6y ago
        Sure here it is[0]. This one is for parsing Kindle clippings but it's quite similar (except no sorting of all words, I was usually using some service for mobi to txt switch before feeding script). I should probably clean it up and switch implementation to english (but don't use it anymore). [0] https://github.com/Machiaweliczny/KindleClippingsTranslator/blob/master/czytaj.py https://github.com/Machiaweliczny/KindleClippingsTranslator/...
        • Shorel 6y ago
          Dziękuję bardzo!
• bestinterest 6y ago
  Simple Ruby implementation counts = Hash.new(0) STDIN.each_line do |line| words = line.downcase.split words.each do |word| counts[word] += 1 end end counts.sort_by { |_k, v| -v }.each do |word, count| p "#{word} #{count}" end
  • petercooper 6y ago
    Alternative approach depending on preferred readability: STDIN.each .map(&:downcase) .map(&:split) .flatten .tally .sort_by { _2 } .reverse .each { |word, count| puts "#{word} #{count}" } (It has a slightly different performance profile and is slightly slower than the other implementation. 477ms vs 418ms on the KJV dataset for me.)
  • frankenst1 6y ago
    Could you update it so that you have "word count\n" on each line?
    • bestinterest 6y ago
      Like that?
      • frankenst1 6y ago
        Yep, this is probably the most readable implementation of all languages so far. I ran it and got 3.59s (Go 0.82s, Rust 1.55s, Shell 42.6s(?)) For accurate diff results, one would need `puts` instead of `p` to get rid of the additional quotes.
        • bestinterest 6y ago
          Checkout Crystal lang one (Ruby but fast), https://github.com/benhoyt/countwords/pull/21/files https://github.com/benhoyt/countwords/pull/21/files seems to keep readability intact and committer is saying it outperforms Go which is interesting.
• taeric 6y ago
  I do get a wry grin from the trie not being faster. Feels like that is always a data structure that feels like it will speed things up, but really needs very specific settings to do so.
• andrepd 6y ago
  Gprof is as good as deprecated nowadays. Perf is an amazing tool: convenient for simple call-graph profiling, and with a huge slew of features if you want to dig deeper.
• justbored123 6y ago
  Very interesting, but why would you omit the two most used languages, Java and JavaScript in favor of obscure ones such as Rust and Forth that nobody uses?
  • klibertp 6y ago
    Because they bring absolutely nothing new to the comparison. These languages are uninteresting in their feature set, and plain boring compared to Forth. Python and C++ already represent the "most used" languages category. Also, not knowing Forth is a Bad Thing(tm) if you want to be a Real Programmer(tm). Same goes for Lisp and Prolog. They all have a place in the history and practice of programming, and dismissing them as "obscure languages that no one uses" misses the point.
  • carols10cents 6y ago
    TIL Mozilla, AWS, Google, Microsoft, and Huawei are "nobody"... https://foundation.rust-lang.org/ https://foundation.rust-lang.org/
• andy_threos_io 6y ago
  Most of the implementations are unable to handle larger words than the read (64k) buffer. The C is for sure. edit: Also the C implementation will get in infinite loop with more than 64k words
  • burntsushi 6y ago
    Yeah, I noticed that too: https://github.com/benhoyt/countwords/blob/9d81d13711e56c25068893880a648ac96d0fa92e/rust/optimized-customhashmap/main.rs#L113-L115 https://github.com/benhoyt/countwords/blob/9d81d13711e56c250... The constraints do say that it is okay to assume lines are reasonable length. But yes, if you were making GNU wordfreq, that might not be something you want to assume. But at that point, it just depends on what you want your failure mode to be I suppose. greps for example will happily just gobble up as much memory as they can to fit a line into memory. :-)
• _wldu 6y ago
  I don't think Go gets the credit it deserves (from a performance aspect). I've had to rewrite a good deal of C++ code in Go and most of the time, the Go code runs faster.
  • debug-desperado 6y ago
    Been true of Java for decades. Most application programmers aren't churning out highly tuned C++, and their design is easily outperformed with a bump allocator and generational GC.
• svat 6y ago
  There is a question on Stack Exchange about exactly this: https://codegolf.stackexchange.com/questions/188133/bentleys-coding-challenge-k-most-frequent-words https://codegolf.stackexchange.com/questions/188133/bentleys... I haven't looked into it yet (whether the benchmarks are comparable) but it would be interesting to check the programs there against the ones in this post, and either update the benchmarks here or add new submissions to that question. For a while the fastest program there was one in Rust, then out of curiosity I translated Knuth's program from 1986 into C++ and a simplified version based on it was even faster; currently a Rust translation of the idea (a custom trie using not too much memory) is the fastest one there. (In fact, the current fastest two Rust submissions there came after I linked to the question from HN in Feb 2020, in a couple of comments at https://news.ycombinator.com/item?id=22221592 https://news.ycombinator.com/item?id=22221592 and in the discussion on a "Donald Knuth was framed" article: https://news.ycombinator.com/item?id=22406070 https://news.ycombinator.com/item?id=22406070.) Edit: I tried to do the comparison myself but one issue I ran into (apart from minor things like taking input from filename vs stdin, and printing top N words versus all, which are easily handled) is that the benchmark on the StackExchange question considers "words" to be made of alphabetic characters (a–z), and the trie solutions make use of that fact (a trie node has 26 children etc), while the benchmark from this post includes punctuation (e.g. it has "words" like "him," and "him." i.e. "him" followed by a comma or period are counted as separate words). I gave up at this point, but maybe someone with more energy could modify the benchmark here and try comparing them.
  • benhoyt 6y ago
    Very interesting -- I hadn't seen that. Thanks for the link.
• heavyset_go 6y ago
  In the Python examples, you should iterate over sys.stdin.buffer, which wraps sys.stdin with an io.BufferReader, to make it equivalent to the examples in other languages.
• indweller 6y ago
  Can someone explain why trie is not faster than hash table?
  • throw_away 6y ago
    What advantage would a trie's prefix searching give you in a word count task? Worse, you're following word.length() pointers, potentially all over your memory. You could collapse with Patricia or Merkle or whatever, but they'll all be worse than the one pointer lookup of a hash table (modulo collision chasing if you pick a bad hash/size) & all in the service of giving you a feature (prefix lookup) you don't need.
  • burntsushi 6y ago
    The source code of the trie program I wrote is here: https://github.com/benhoyt/countwords/blob/master/rust/optimized-trie/main.rs https://github.com/benhoyt/countwords/blob/master/rust/optim... The comments explain why I think it's slower. The TL;DR is that using a trie requires more memory accesses than a hash table (per byte of input), and those memory accesses slow the whole enterprise down. But, not all memory accesses are created equal. So perhaps a more clever representation that exploits locality better would do better. "Obvious" techniques for shrinking memory usage made a big difference and brought the performance of the trie program closer to C: https://github.com/benhoyt/countwords/pull/2 https://github.com/benhoyt/countwords/pull/2
    • indweller 6y ago
      Yeah, I get it now. Thanks!
• ZoomZoomZoom 6y ago
  I basically solved the same problem about a year ago. I was reading Gormenghast trilogy and for a considerable part of the book I stumbled upon rare English words of unknown or hazy meaning for me. I decided I need a tool to prepare Anki decks with those words, bu as I'm too lazy to manually log them, I thought I just use the same algorithm, take the top most infrequently occurring words and generate a CSV with definitions from GCIDE[0] to load into Anki. I used Rust and thought it's the textbook case for a trie, but what I found is that crates.io had quite a few tries but not all of them working or ergonomic enough. Only one of the libraries I tried (huh) gave me a slight advantage over a HashMap, although statistically insignificant, which is rather disappointing, considering the program outputted sorted frequency groups. I'm pretty pleased with the results. I considered adding stemming[1], silly me. Too hard of a problem to bother. 0. https://gcide.gnu.org.ua/ https://gcide.gnu.org.ua/ 1. https://en.wikipedia.org/wiki/Stemming https://en.wikipedia.org/wiki/Stemming
• SimpleGoto1080 6y ago
  The other day someone posted rust was faster than C and I asked for context because the article had no proof. My post was flagged This article shows exactly why C is nearly twice as fast as C++ and why rust is in between. This is a good article, the other thread was a bad article and bad thread
  • steveklabnik 6y ago
    You didn't ask for context. https://news.ycombinator.com/item?id=26448432 https://news.ycombinator.com/item?id=26448432 You asserted there was no context, and so you believed it to be wrong. Hacker News tends to frown on very short, negative posts from new accounts.
    • SimpleGoto1080 6y ago
      Correct. I misspoke. I wanted to edit but the site was down and it looks like I can't any longer
    • SimpleGoto1080 6y ago
      Maybe it was negative but how else would you talk about a problem with an article? Every benchmark I seen with actual numbers and code had C++ faster except for one and we were able to check the source to why
      • steveklabnik 6y ago
        Even this comment, while short, is much better! "doesn't have context" is, ironically, kind of context-free. What context did you want? Given what you just said, the answer is apparently "benchmarks." You don't even need to make your comment all that much longer to be much, much better (imho, I'm not dang, I don't own this place, heh) > With the lack of context in this article I'm willing to bet rust isn't actually faster than C into something like > Without benchmarks, I'm willing to bet rust isn't actually faster than C. Now that I write that out, it's even shorter! But it's way better. You've made a specific criticism of the article, rather than making a very abstract one. I'd still say that something this short isn't likely to be upvoted, but it isn't likely to be downvoted like you were. Compare your comment to this one: https://news.ycombinator.com/item?id=26446830 https://news.ycombinator.com/item?id=26446830 While it does start with some "I like Rust," imho that wasn't even necessary. It's also more aggressive than you were, but even got some replies. Even though it contained the same sentiment.
• chaostheory 6y ago
  If you're not using multiple CPU cores with either multiple processes or threads for all the languages being compared, this blog post is not as useful as it good be
• eisvogel 6y ago
  The table at the end of the article, and most of the article, are meaningless. They are comparing the performance of grep and wc, programs written in C, with their own program, written in C. Python is also in the mix, and is also a program written in C. Most C programs are also valid C++ programs, so the top entry for grep should really be labelled "C/C++". I'm tired of this kind of comparison.
  • anthk 6y ago
    This comment is utter nonsense.
• _old_dude_ 6y ago
  No java ! here is my code golf version var map = new BufferedReader(new InputStreamReader(in, UTF_8)) .lines() .flatMap(compile(" ")::splitAsStream) .collect(groupingBy(w -> w, () -> new TreeMap<>(reverseOrder()), counting())); It obviously doesn't work without the imports import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.TreeMap; import static java.lang.System.in; import static java.nio.charset.StandardCharsets.UTF_8; import static java.util.Collections.reverseOrder; import static java.util.regex.Pattern.compile; import static java.util.stream.Collectors.counting; import static java.util.stream.Collectors.groupingBy;
  • killingtime74 6y ago
    Maybe graalvm native version could be competitive
• dietrologia 6y ago
  I wonder why the C++ version didn't use a map, instead of doing unordered_map and then copying into a vector.
• dietrologia 6y ago
  I wonder why the C++ version opted for an unordered_map, copied into a vector and then sorted. I'd be curious to see if using an std::map would work better.
• techolic 6y ago
  There're more string copies that can be optimized away for the C++ solution: 1. When filling the map with `word`, can use emplace with std::move of the `word` instead of operator[] because `word` is no longer needed after that, after checking that it's not already in the map 2. Constructing the vector (for sorting) with all pairs from the map ends up copying the whole map's worth of data! Can use iterator of the map instead of the key of the map in the pair. This may also make sort() faster because it may be cheaper to move an iterator than a string during sort()
• raymondh 6y ago
  > Let me know if you find a better approach. Except for the printing, this runs at about C speed because it has very little interpreter overhead: c = Counter(sys.stdin.read().casefold().split()) for word, count in c.most_common(): print(word, count) P.S. Thanks for the kind shout-out in your article.
  • benhoyt 6y ago
    No problem -- defaultdict is one of my favourite Python tools! Note that the code you posted is nice for a one-liner, however, it goes against my constraint of not reading the entire file into memory (important for very large files).
• julienpalard 6y ago
  Reminds me of logtop: $ apt install logtop $ printf "%s\n" the foo the foo the defenestration the | logtop 7 elements 1 4 the 2 2 foo 3 1 defenestration It's implemented using an AVL tree (because it aimed to work on continuous streams like logs, so it's limited in size).
• artem247 6y ago
  I love the simple Ruby version (it was added to Github) #!/usr/bin/env ruby counts = Hash.new(0) STDIN.each_line { |line| line.downcase.split.each { |w| counts[w] += 1 }} counts.sort_by { |k,v| -v }.each { |k,v| puts "#{k} #{v}" }