Performance comparison: counting words in Python, C/C++, Awk, Rust, and more

I even submitted a PR[0], but Ben decided he was tired of maintaining and decided to archive the project (which fair enough!).

[0]: https://github.com/benhoyt/countwords/pull/115

* It uses byte strings instead of UTF-8 strings. In my opinion, that’s not an optimization, that’s changing the problem. Depending on the question you’re asking, only one of the two can be correct.

* It uses a faster hash algorithm. It’s not the first time this came up in a benchmark article. Rust’s decision to use a DOS-safe hash by default (and not provide a fast algorithm in the std, like other languages do) really seems to hurt it in that kind of microbenchmark.

* It uses get_mut+insert instead of the more convenient HashMap::entry method, because the latter would require redundantly allocating the key even in the repeat case. I’ve hit this problem in the past as well. Maybe the upcoming HashMap::raw_entry_mut will make this kind of optimization cleaner.

I took the source code file size from the repository, and the runtime from the blog post.

Then I made an arbitrary overall "PAIN SCORE" (lower is better) by multiplying code size * runtime. I suggest this is a worthwhile metric simply because lower is better on both axes, but of course, in the "real world" there will be different economic costs to CPU time and developer time depending on the use case. Here's the sorted results, from least "pain" to most:

    LANGUAGE   FILENAME        CODE SIZE      RUNTIME     PAIN SCORE (LOWER IS BETTER)
    Shell      optimized.sh      75 bytes      1.83 s      137.25
    Crystal    simple.cr        240 bytes      1.29 s      309.6
    Nim        simple.nim       424 bytes      0.77 s      326.48
    Python     simple.py        208 bytes      2.21 s      459.68
    Ruby       simple.rb        175 bytes      3.17 s      554.75
    Go         optimized.go    1514 bytes      0.40 s      605.6
    Python     optimized.py     464 bytes      1.33 s      617.12
    Zig        optimized.zig   2688 bytes      0.24 s      645.12
    Go         simple.go        688 bytes      1.12 s      770.56
    Zig        simple.zig      1394 bytes      0.55 s      766.7
    Nim        optimized.nim   1683 bytes      0.49 s      824.67
    Shell      simple.sh         60 bytes     14.81 s      888.6
    Ruby       optimized.rb     401 bytes      2.47 s      990.47
    JavaScript simple.js        532 bytes      1.88 s     1000.16
    C          optimized.c     4360 bytes      0.23 s     1002.80
    Rust       optimized.rs    3065 bytes      0.43 s     1317.95
    Swift      simple.swift     317 bytes      4.23 s     1340.91
    JavaScript optimized.js    1501 bytes      1.10 s     1651.1
    C          simple.c        2735 bytes      0.96 s     2625.6
    Rust       simple.rs       2239 bytes      1.38 s     3089.82

I am definitely a Crystal fan, in fact this afternoon I'm continuing to implement suggestions from my recent Show HN https://news.ycombinator.com/item?id=32081943 comments. :)

1) The choice of libraries/datatypes used for strings and word->count map

2) How the source file is split into words - probably library function again, although in C/C++ one could choose to implement a super-optimized low level version that would blow the others away

IMO a performance comparison between languages is only meaningful if the runtime is not dominated by library functions, or if one admits it's really a standard library performance comparison, not a language comparison.

The programs are not comparable in the the following ways:

- Case: TFA requires (at least) ASCII lowercasing but the contest problem required no lowercasing.

- Ordering: TFA does not require sorting, but the contest problem required sorting.

- Memory: TFA imposes a requirement phrased as "don't read the whole file into memory" and this sounds like it's a resource-saving constraint, but it's usually a constraint that requires the program to spend additional resources. You could just mmap the file and store pointers into the mapped region. It costs extra to do copies instead of no copies.

- Text: TFA is unclear on what assumptions may be made about the lengths of words. For the contest problem, the Hungarian wikipedia input's longest word is around 80k.

- Safe, Hashing, Stdlib: TFA imposes some restrictions on what constructs may be used that are not imposed in the contest problem.

For the contest version of this problem, it seems like you can tokenize, hash, and count strings at around 1GB/s. Adapting a solution to solve TFA's problem (but not to conform to its Safe/Hashing/Stdlib requirements) would probably not carry too large of a penalty, since it's like 3 instructions to ASCII-lowercase 32 bytes and 1 string copy per unique string should take negligible time compared to the hash table lookups. So there is some room for the optimized solutions to go a little faster, if more optimizations are permitted.

[0]: https://easyperf.net/blog/2022/05/28/Performance-analysis-an...

[1]: https://www.youtube.com/watch?v=R_yX0XjdSBY

Edit:

Even if you ignore LLVM-libc, just slapping this into the optimized.cpp and replacing the critical `==` with `our_bcmp` makes it 10% faster. IFUNC calls to micro-optimized SIMD functions are counterproductive. It is far, far better that the compiler can see all the code at build time.

  int our_bcmp (const char* a, const char* b, size_t sz) {
    for (size_t i = 0; i < sz; i++) {
      if (a[i] != b[i]) return 1;
    }
    return 0;
  }

  CALL    runtime.mapaccess2_fast64(SB)

  CALL    runtime.mapassign_fast64(SB)

> 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, instead of for every increment

I just tried benchmarking this with a simple setup and I get zero allocations for both approaches, although the "pointer" approach is slightly faster

  package main
  
  import (
   "testing"
  )
  
  func BenchmarkIncrementMapRawInt(b *testing.B) {
   var data = make(map[int]int)
  
   b.ResetTimer()
   for i := 0; i < b.N; i++ {
    key := i % 1000
    data[key]++
   }
  }
  
  func BenchmarkIncrementMapPointerInt(b *testing.B) {
   var data = make(map[int]*int)
  
   b.ResetTimer()
   for i := 0; i < b.N; i++ {
    key := i % 1000
    increment(data, key)
   }
  }
  
  func increment(counts map[int]*int, value int) {
   if p, ok := counts[value]; ok {
    *p++
    return
   }

   n := 1
   counts[value] = &n
  }

  $ go test -bench=. -benchmem .
  goos: darwin
  goarch: arm64
  BenchmarkIncrementMapRawInt-8        112288002         10.57 ns/op        0 B/op        0 allocs/op
  BenchmarkIncrementMapPointerInt-8    139728302          8.586 ns/op        0 B/op        0 allocs/op

I also looked at the "simple" Zig version, which came out really well in the benchmark, and to me it didn't look simple at all. It seems you need to make a lot of low level details explicit.

But IMHO AWK takes the crown here. :)

[1] https://developer.apple.com/swift/

The code:

SELECT arrayJoin(splitByChar(' ', lower(line))) AS word, count() AS c FROM file('kjvbible.txt', LineAsString) WHERE notEmpty(word) GROUP BY word ORDER BY c DESC FORMAT Null

or:

clickhouse-local --query "SELECT arrayJoin(splitByChar(' ', lower(line))) AS word, count() AS c FROM file('kjvbible.txt', LineAsString) WHERE notEmpty(word) GROUP BY word ORDER BY c DESC" > /dev/null

It is using only a single thread.

However, in this case, the Python example is idiomatic.

Since the articles calls for better approaches, I would suggest to take the opportunity to use the walrus operator and rsplit() for the optimized version. Something like this:

    reminding = ""
    c=Counter( )
    while (chunk := sys.stdin.read(64 * 1024)):
        pre, post = chunk.lower().rsplit('\n', 1)
        c.update((reminding + pre ).split())
        reminding = post

However, the performances will be quite different depending of the python version you use. Interestingly, Python 3.11 beta, which comes with a lot performance tweaks, is slower for this exercice, while being reported to be faster on real life tasks.

Since this writing and other linked resources present only one side of the affair, I will mention: the presentation in Pearls was quite unfair to Knuth, and the conclusions commonly made of it somewhere between moderately and entirely unsound. (That is, as conclusions from the paper. I speak of unsoundness of logic only: these conclusions may be supportable from other sources.)

Knuth was challenged to demonstrate literate programming, and so that was what he demonstrated. He showed building something from the ground up assuming a very minimal environment, with problem analysis and all: of course that ended up more verbose than a Unix pipeline that glosses over problem analysis and starts with most of the tools you need to make a probably-acceptable solution!

McIlroy himself admitted a few years later that he had been “a little unfair” to criticise on engineering grounds what had only been an illustration of technique. Even in the paper, Bentley did admit a degree of culpability for this mismatch in his “criticism of programs” paragraph. (“He admires the execution of the solution, but faults the problem on engineering grounds. (That is, of course, my responsibility as problem assigner; Knuth solved the problem he was given on grounds that are important to most engineers-the paychecks provided by their problem assigners.)”)

But I do wish that Knuth had been given the opportunity to write a review of McIlroy’s review, for simultaneous publication.

[0]: https://news.ycombinator.com/item?id=26463967

(Copying from my comment the last time this was posted: https://news.ycombinator.com/item?id=26467684)

There's also a nice book "Exercises in Programming Style" about just this problem.

When I've been asked this in programming interviews, I've almost always been expected to produce something like the code in the article (and do), but usually I'd point to something like the NLTK library as a better approach. It's polished and highly capable, and handles probably just about every edge case there is.

Not that it doesn't happen, it's just not something I've run into.

Just today I was testing out the performance difference hashing some Scylla queries and got nearly 2x faster hashing moving to fxhash.

readLines(file) |> strsplit(“ +”) |> unlist() |> table() |> sort(desc = TRUE)

    $ g++ -I robin-hood-hashing/src/include -O2 -flto -std=c++20 -fno-exceptions -fno-unwind-tables -fno-asynchronous-unwind-tables -lfmt

    $ time ./a.out < kjvbible_x10.txt > /dev/null
    0,19s user 0,01s system 99% cpu 0,197 total

    0,22s user 0,01s system 99% cpu 0,233 total

               if (!counts.TryGetValue(word, out var wordCountRef))
                {
                    counts.Add(word, new Ref<int>(1));
                }

Or should the "threading" constraint really have been stated as "you can use multiple threads, but only if they all have their own address space"?

Alternatively, given the multi-core capabilities of even budget/mobile/small systems these days (even the Rasberry Pi 4 has a quad-core CPU), isn't restricting the implementation to a single thread a weird artificial limitation in 2022? Also, a GPU-based implementation would be interesting, and GPUs most of their power from their massively parallel core architecture.

I think it is more fair to say that in Go optimizations are always OFF.

  from collections import Counter
  from re import finditer

  word_counts = Counter()
  with open(PATH, encoding = 'utf-8') as file:
      doc = file.read()
  word_counts.update(match.group().lower() for match in finditer(r'\w+', doc))

A solution to every aspect of this problem but the line-by-line bit took just over a minute to write. Adding that took another minute.

The trade-off is that LC is slower than almost any of the languages listed, and optimization is almost impossible -- the idiomatic way is the fastest (almost). And if you don't like the way LC parses words, there is almost no way to change it without going into the source code (a big pain).

  \t desc count each group `$lower " " vs raze read0 `:kjvbible_x10.txt

I am sure q pros or k purists can optimize this even more...

EDIT: Moving the lower earlier brings this down to 1.9s

  desc count each group `$ " " vs lower raze read0 `:kjvbible_x10.txt

https://github.com/samuell/gccontent-benchmark#readme

Really hard - or impossible - to arrive at a definitive single number for one language, but the whole exercise is a lot of fun and quite informative IMO :)

Start with something not too far north of FizzBuzz but with a ton of scope to progressively enrich the problem until the clock runs out.

At $BIG_CO du jour people tend to talk about how much “signal” an interview produces, and starting somewhere that a meaningful number of candidates can’t do anything with offers very little “signal”, likewise very little Shannon information.

Great article!

Or maybe the difference is just noise? It's hard to tell without more details on how the benchmarks were run.

Interesting. This is something I'll have to keep in mind.

Best practice is always been to consider I/O the slowest.

But, it's true... times have changed.

Maybe we shouldn't make this assumption anymore.

Om the other hand the article is gold mine for learning performance analysis in different languages.

I've been asking different versions of that question since I started interviewing and it is a surprisingly good filter.

But with articles like this, now I need new questions..

Anyone has an explanation ?

I know the swift string type is really complex, but i always assumed it was at least performing well..

I wonder why that is?

Wild.

Other comments here reveal how, exactly.