Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

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

benhoyt.com

Post reply on HN
Print view View original

221–230 of 234 posts

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

#221

Post by mustache_kimono »

burntsushi wrote: post #220
mustache_kimono wrote: post #20

Re: the Rust optimized implementation, I was able to get ~20-25% better performance by rewriting the for loops as iterators, using Rust's byte range pattern matching, and a buffered writer, which seems crazy, but it's true. I chalked it up to some crazy ILP/SIMD tricks the compiler is doing. I even submitted a PR[0], but Ben decided he was tired of maintaining and decided to archive the project (which fair enough!).…

From my measurements, your optimized version runs at about the same speed as mine: $ cd /tmp/ $ git clone -b ag/test-kimono https://github.com/BurntSushi/countwords $ cd countwords/rust/ $ ./bench Summary './optimized-trie/target/release/countwords You mentioned in another comment that you were benchmarking on an M1. Maybe there's some interesting differences there in the codegen, how the CPU executes or both. Your '…

> Kudos!

Thanks!

> I don't think I ever would have broken out of my local optima to discover that program.

It really is the answer to what is the most knuckle-headed thing one could try, but I was curious what Rust-with-the-guardrails could do.

> My 'trie' variant is now the fastest Rust submission

Cool. Very interested why this is the case.

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

#222

Post by nerdponx »

anonymoushn wrote: post #186
nerdponx wrote: post #182

Earlier quoted context omitted.

The issue is that this is a weird requirement. I have seen real world data sets that had all manner of exotic whitespace like nonbreaking spaces and vertical tabs peppered throughout, so I am sympathetic. But this situation isn't common. That said, for a CLI program like this, usually approximate results are good enough anyway. And realistically, most text should use ASCII whitespace for pretty much all text.

It is a context-specific requirement, but "fully general lowercasing" would be an impossible requirement. For e.g. Japanese text, I think you'd only have to add 1 or 2 characters to the set of whitespace characters. You also have to solve Japanese text segmentation, which is hard-to-impossible. If you want to canonicalize the words by transforming half-width katakana to full-width, transforming full-width romaji to a…

Great write up! However I should've clarified, I wasn't talking about word segmentation in general, only about expanding the universe of valid "whitespace" grapheme clusters (or even just codepoints) to include the various uncommon, exotic, and non-Western items.

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

#223

Post by claytongulick »

igouy wrote: post #52
claytongulick wrote: post #34

My takeaway is that unoptimized c++ is pretty close to the same performance as JavaScript. Wild.

fwiw https://benchmarksgame-team.pages.debian.net/benchmarksgame/...

Yep, I don't have the energy tonight to inspect the source code, but how you write js matters a lot.

Little things like hoisting local variables out of the prototype and closure chains can make a massive difference.

I did some experiments with hot path js optimization several years ago and was pretty surprised at the performance you can squeeze out of the jitter.

Js is notorious for being difficult to do good perf analysis on because of the warming and hot path analysis. From my experiments it can sometimes take many seconds from startup for the jitter to kick in on a tight loop.

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

#224

Post by burntsushi »

mustache_kimono wrote: post #221
burntsushi wrote: post #220

Earlier quoted context omitted.

From my measurements, your optimized version runs at about the same speed as mine: $ cd /tmp/ $ git clone -b ag/test-kimono https://github.com/BurntSushi/countwords $ cd countwords/rust/ $ ./bench Summary './optimized-trie/target/release/countwords You mentioned in another comment that you were benchmarking on an M1. Maybe there's some interesting differences there in the codegen, how the CPU executes or both. Your '…

> Kudos! Thanks! > I don't think I ever would have broken out of my local optima to discover that program. It really is the answer to what is the most knuckle-headed thing one could try, but I was curious what Rust-with-the-guardrails could do. > My 'trie' variant is now the fastest Rust submission Cool. Very interested why this is the case.

The "why" behind the trie is explained in the comments in the code. :-) The core of my hypothesis was to avoid hashing and hash table lookups at all.

The problem with the trie, though, is that it does a memory access per byte.

Whether and when this trade is beneficial is not totally clear to me, but clearly, it can vary.

Whether my hypothesis is actually correct is also not something I'm certain of. Verifying this would take some time with: 1) looking at the codegen and 2) some use of `perf` to extract CPU counters for things like branch and cache misses, and see if a correlation can be established.

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

#225

Post by dvhh »

FpUser wrote: post #12

I would not call it performance comparison at all. When Python call functions written in C it is not Python's performance. Write those functions using plain Python and then see the results. Sure for this basic example in the article it does not matter from a practical standpoint. But when you need to step away from canned cases suddenly Python's performance sucks big time.

Are you implying that node.js is pure ecmascript ?

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

#226

Post by mustache_kimono »

burntsushi wrote: post #220
mustache_kimono wrote: post #20

Re: the Rust optimized implementation, I was able to get ~20-25% better performance by rewriting the for loops as iterators, using Rust's byte range pattern matching, and a buffered writer, which seems crazy, but it's true. I chalked it up to some crazy ILP/SIMD tricks the compiler is doing. I even submitted a PR[0], but Ben decided he was tired of maintaining and decided to archive the project (which fair enough!).…

From my measurements, your optimized version runs at about the same speed as mine: $ cd /tmp/ $ git clone -b ag/test-kimono https://github.com/BurntSushi/countwords $ cd countwords/rust/ $ ./bench Summary './optimized-trie/target/release/countwords You mentioned in another comment that you were benchmarking on an M1. Maybe there's some interesting differences there in the codegen, how the CPU executes or both. Your '…

> In particular, your approach appears to do 3 (and some change) passes over each buffer: 1) read up to '\n' (just the first line), 2) UTF-8 validation, 3) make lowercase and 4) split on whitespace.

I really should have waited until I had more time to respond, but it really only should be 2, 3, and 4.

I tried unsafe/unchecked for UTF8, and, yes, it is a modest bump, but I wanted to do it without unsafe. And 3 and 4 are really pretty fast for what they are. They both work on bytes and the str as_bytes transmute is virtually cost free from what I can tell.

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

#227

Post by Bogdanp »

kortex wrote: post #200
Bogdanp wrote: post #190

Earlier quoted context omitted.

I have no dog in this fight, but I do want to point out that’s it’s not exactly true that Counter is implemented in pure Python: * it’s a subclass of dict * its update method (used by the code in the post) dispatches to a C implementation on its fast path

Yes, that's exactly what I said. dict.update is in C, because it's a core feature of the python vm . It's pure CPython. What do you think "pure python" is? There's no python hardware ISA (afaik). All cpython is manipulating data structures in C via Python VM opcodes. It just so happens that whatever opcodes that are dispatched in the course of solving this problem are quite efficient. If you say "it does not count as…

“Pure Python” commonly means implemented using only the Python language. Something written in pure Python ought to be portable across Python implementations. I was merely pointing out that this line

https://github.com/python/cpython/blob/4395ff1e6a18fb26c7a66...

isn’t exactly pure Python, because, under a different runtime (eg PyPy), the code would take a different path (the “pure Python” implementation of _count_elements[1] instead of the C implementation[2][3]). Yes, it's hard to draw exact lines when it comes to Python, especially as the language is so tied to its implementation. However, I think in this case it's relatively clear that the code that specific line is calling is an optimization in CPython, specifically intended to get around some of the VM overhead. Said optimization comes into play in the OP.

[1]: https://github.com/python/cpython/blob/4395ff1e6a18fb26c7a66...

[2]: https://github.com/python/cpython/blob/4395ff1e6a18fb26c7a66...

[3]: https://github.com/python/cpython/blob/4395ff1e6a18fb26c7a66...

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

#228

Post by benibela »

gary17the wrote: post #183
benibela wrote: post #180

Earlier quoted context omitted.

>even Pascal and Forth. Even? Pascal is touted as being as fast as C

Perhaps bad phrasing on my part. I meant that in the are-they-still-even-maintaining-modern-optimizing-compilers-for-Pascal-and-Forth sense.

FreePascal maintains their own optimizer. It is one of the few languages that still have their own optimizer rather than using LLVM. Although they would probably better of using LLVM. They introduce a new optimization every month, and I usually notice the new optimization when my code starts crashing with the nightly compiler.´

But they have a bunch of reasons why they cannot use LLVM like "LLVM will almost certainly never support all targets that FPC supports (Gameboy Advance, OS/2, WinCE, ...), or at some point drop support for targets that FPC still supports (as already happened with Mac OS X for PowerPC/PowerPC64)." [1]

Or "FPC's native code generators are much faster than LLVM's (even if you would neglect the overhead of FPC generating bitcode and the LLVM tool chain reading it back in), so especially while developing it may be more interesting to use FPC's own code generators"

But the test of this thread mostly benchmarks the hashmap implementation. I got my own Pascal hash map, it is twice as fast than the one in their standard library.

And, looking at the test code, it does a double hashing, first a get, then an insert. If it did a find entry and update it in-place, it would be twice as fast, too.

Together that would be four times faster and as fast as the C version and still be simple

[1] https://wiki.freepascal.org/LLVM#Frequently_Asked_Questions

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

#229

Post by mustache_kimono »

burntsushi wrote: post #220
mustache_kimono wrote: post #20

Re: the Rust optimized implementation, I was able to get ~20-25% better performance by rewriting the for loops as iterators, using Rust's byte range pattern matching, and a buffered writer, which seems crazy, but it's true. I chalked it up to some crazy ILP/SIMD tricks the compiler is doing. I even submitted a PR[0], but Ben decided he was tired of maintaining and decided to archive the project (which fair enough!).…

From my measurements, your optimized version runs at about the same speed as mine: $ cd /tmp/ $ git clone -b ag/test-kimono https://github.com/BurntSushi/countwords $ cd countwords/rust/ $ ./bench Summary './optimized-trie/target/release/countwords You mentioned in another comment that you were benchmarking on an M1. Maybe there's some interesting differences there in the codegen, how the CPU executes or both. Your '…

> It is IMO very much not the first program someone would write for this.

True.

> Bringing in 'hashbrown' and futzing with the hash table lookup/insert is definitely a perf tweak that you probably wouldn't want to do unless you had to, because it makes the code more complex. The 'Box' cements it as an 'optimized' variant.

I would say, both these items, I added much later, and contribute substantially less to the bottom line performance than you might think. Bulk of the performance is elsewhere.

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

#230

Post by ppeetteerr »

saagarjha wrote: post #153
ppeetteerr wrote: post #104

Curious if anyone knows why the swift version is slow? Is it the casting from subsequence to a string?

Here's a very rough breakdown of the operations it does: 1.33 s 56.7% specialized Collection .split(separator:maxSplits:omittingEmptySubsequences:) 263.00 ms 11.2% Substring.lowercased() 226.00 ms 9.6% specialized Dictionary.subscript.modify 189.00 ms 8.0% readLine(strippingNewline:) As you can see, calling split on the string is really slow. The reason it is slow is that it's using the generic implementation from Co…

Thank you for this response!

It's sad to see that Swift is so slow in this particular case given that it has the potential to be such an optimized language (strong typing, compilation, backing from Apple).

Post reply on HN