[HN Gopher] Performance comparison: counting words in Python, Go...
___________________________________________________________________
Performance comparison: counting words in Python, Go, C++, C, Awk,
Forth, Rust
Author : benhoyt
Score : 376 points
Date : 2021-03-15 09:27 UTC (13 hours ago)
(HTM) web link (benhoyt.com)
(TXT) w3m dump (benhoyt.com)
| lionkor wrote:
| 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 wrote:
| > 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 wrote:
| Depends on your point of view. Rust has more complexity
| hidden in layers underneath the one a developer is working
| with directly.
| super_mario wrote:
| Isn't grep really optimal C implementation?
| kevincox wrote:
| grep doesn't solve the problem.
| jonathanstrange wrote:
| 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 wrote:
| 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_ wrote:
| 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 wrote:
| I'm aware, but alas in my domain anything above 50us is
| "noticeable" if it happens regularly
| _ph_ wrote:
| 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.
| analognoise wrote:
| HFT?
| easytiger wrote:
| Something like that yes
| SimpleGoto1080 wrote:
| 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 wrote:
| You didn't ask for context.
| 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.
| rurban wrote:
| So this basically confirms Bentley's famous Programming Pearls
| book results from 1986. Nothing much changed.
| toppi wrote:
| 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
| pjmlp wrote:
| 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]
| Someone1234 wrote:
| You're micro-optimizing the wrong thing, most of the time taken
| in C# is in the .Split(' ',
| StringSplitOptions.RemoveEmptyEntries) (which is UNICODE
| instead of ASCII as in other languages by the way) and also
| Console.ReadLine().
|
| C# supports non-allocating splitting via the Span /
| ReadOnlySpan see this article about this very question:
|
| https://www.meziantou.net/split-a-string-into-lines-without-...
|
| You can also use the Win32 APIs to more efficiently hook the
| console input:
|
| https://stackoverflow.com/questions/33342340/fast-reading-of...
|
| You can change foreach to for or whatever, but after you deal
| with the major program's bottlenecks.
| pjmlp wrote:
| Surely, I haven't bothered to list everything.
| burntsushi wrote:
| 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.
| tester34 wrote:
| >there are better data structures than Dictionary
|
| What built in you'd use?
| andix wrote:
| 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]
| acdha wrote:
| 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 wrote:
| I give my skills as free beer when it is relevant for me,
| otherwise there are just advices.
| acdha wrote:
| Totally fair - my point was mostly that it seemed pretty
| clear that the author didn't have much C# experience and
| would gladly accept an expert's optimized version.
| pjmlp wrote:
| Which is why I mentioned some low hanging fruit of
| possible improvements.
| macgyverismo wrote:
| 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) {
| w-m wrote:
| Similar here, reading the file from stdin on a 2020 MBP on
| macOS 11.2.2 is incredibly slow. int main() {
| std::ios::sync_with_stdio(false); std::string
| str((std::istreambuf_iterator<char>(std::cin)),
| std::istreambuf_iterator<char>()); }
|
| takes around 8 seconds to run, no counting at all.
| int main() { std::ifstream f("kjvbible_x10.txt");
| std::string str((std::istreambuf_iterator<char>(f)),
| std::istreambuf_iterator<char>()); }
|
| runs in ~270 miliseconds. Factor 30x, yikes.
| c-cube wrote:
| 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 wrote:
| Try this maybe? https://codeforces.com/blog/entry/6251
| macgyverismo wrote:
| Asuming you mean 'std::ios::sync_with_stdio(false);', that
| was already present in the original code.
| nerdponx wrote:
| Is that due to something at the OS or filesystem driver level?
| usefulcat wrote:
| I tried that on Linux and got at best a 5% improvement.
| benhoyt wrote:
| Yeah, I'm on Linux too and tried that with no noticeable
| difference in results. There's something off about macOS's
| approach.
| cornstalks wrote:
| I dug into this once because reading from stdin on my Mac was
| so slow, but only when using std::cin. Using C APIs to read
| stdin was fast. Turns out libc++ on mac uses `getc` to read
| from stdin one character at a time. Madness.
| wmu wrote:
| 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).
| jpcooper wrote:
| Maybe due to stdio synchronisation? This can be turned off.
|
| https://en.cppreference.com/w/cpp/io/ios_base/sync_with_stdi...
| oefrha wrote:
| Text processing, without a single mention of Perl. How times have
| changed.
| asicsp wrote:
| And, Perl's hash implementation can perform better compared to
| Awk's associative arrays. The `SCOWL-wl.txt` file used below
| was created using http://app.aspell.net/create. `words.txt` is
| from `/usr/share/dict/words`. Mawk is usually faster, but GNU
| Awk does better in this particular case. $ wc
| -l words.txt SCOWL-wl.txt 99171 words.txt
| 662349 SCOWL-wl.txt 761520 total #
| finding common lines between two files # shorter file
| passed as the first argument here $ time gawk
| 'NR==FNR{a[$0]; next} $0 in a' words.txt SCOWL-wl.txt > t1
| real 0m0.376s $ time perl -ne 'if(!$#ARGV){$h{$_}=1;
| next} print if exists $h{$_}'
| words.txt SCOWL-wl.txt > t2 real 0m0.284s
| nerdponx wrote:
| Unfortunate, because for all the badness of Perl, it shines in
| exactly this case of "read a potentially-infinite stream of
| text from stdin, process it, and dump another stream to
| stdout".
| mfontani wrote:
| What would "all the badness of Perl" be?
| outside1234 wrote:
| See the unreadable unmaintainable code above.
| faizshah wrote:
| Honestly, when you don't know perl it looks really
| unreadable but if you spend some time learning it it's
| not that hard it's just many of the operators are not
| google-able. The harder part, from experience, is
| maintaining perl scripts. A lot of perl scripts from the
| early 2000s are written in extremely hacky ways without
| modern code style sensibilities. In 2021 I don't see any
| reason to use perl over python3 anymore, python3 is fast,
| widely used, easy to write, and easy to learn. Even the
| bioinformatics folks, some of the last perl holdouts,
| have been switching to python.
|
| Since learning perl a couple years ago I personally only
| use it for one liners to replace sed/awk. If I do use
| perl in a script it's usually in one liner form in a bash
| script to post process output from something like
| ripgrep.
| mfontani wrote:
| > In 2021 I don't see any reason to use perl over python3
| anymore
|
| Is there, in 2021, a "use strict" equivalent for Python,
| or can one still misspell variable names and not be
| warned about it?
| nerdponx wrote:
| You would get a NameError (or maybe an UnboundLocalError
| in some cases) if you use a nonexistent variable name in
| Python. At least, this has been true since 2013 when I
| started learning Python.
| jjav wrote:
| > In 2021 I don't see any reason to use perl over python3
| anymore
|
| Regex handling is still far nicer in perl than anywhere
| else, so for any script which is primarily about string
| parsing with regular expressions, perl is the right tool
| for the job.
| nerdponx wrote:
| For what it's worth, there's nothing in the Perl manual
| that says you have to write unreadable, unmaintainable
| code.
|
| Although maybe it's hard to judge a programming language
| separately from the culture around that programming
| language.
| mhd wrote:
| My version? That's a one-liner, one shouldn't maintain
| those. It was mainly intended to show that a lot of the
| logic for simple cases is so common that perl (and some
| other languages) have those as command line switches.
|
| That also makes it hard to win for total outsiders,
| though. This touches on core functionality, which often
| has quite a legacy behind it and thus its own vernacular.
| I can write `while (my $line = <STDIN>)` instead of
| `while(<>)`, but I can't get as easily rid of "chomp"
| being confusing to most people. A bit like car/cdr in
| Lisp.
|
| But that happens even if you have plain english functions
| and no special cased syntax. Looking at the simple python
| version, it took some effort for me to remember what
| `Count.update(lst)` does, or that `most_common` without
| arguments returns all elements.
| nerdponx wrote:
| Chaotic standard library with cute-but-difficult-to-search-
| for names like "chomp", messy and complicated rules around
| sigils and scalar() for arrays and tables, lots of magic
| convenience like "$_" being optional in loops, s/// being
| "destructive" by default, and the need for some ugly hacks
| around handling subroutine arguments.
|
| Perl has plenty of "good parts", too. But it is not an easy
| language to learn and even good idiomatic Perl code can be
| difficult to read. I don't blame people for favoring Python
| and Ruby.
| cgh wrote:
| I've always believed Perl has an alignment of chaotic
| good.
| mfontani wrote:
| I often see examples comparing one-liner worthy code
| written in one language with beautiful, linted, critique-
| passing indented code written in other languages, and on
| and on goes the Perl bashing based on examples of the
| former.
| keanebean86 wrote:
| My only complaint is the dollar sign. Same with PHP. It
| take time to build the muscle memory for that.
| mhd wrote:
| 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]
| jlg23 wrote:
| If you interviewed for a perl job, you'd probably be
| disqualified for writing code that is too readable ;)
| mhd wrote:
| I know this is meant as a joke, but I just use this to once
| again note that Perl actually had a very common
| linter/pretty printer way before it became all the rage
| (perltidy/perlcritic). I also wish other languages had a
| book like Perl Best Practices, that goes beyond just
| syntactical issues.
|
| To be fair, I once came across a sentiment that was pretty
| close to "readability is bad". Taken from both the (bourne)
| shell and awk, perl has lots of short variables that
| determine parsing input and other matters, like "$/". You
| can then `use English` to have alternative names for that,
| but those might not be as well known ("$/" would be
| "$INPUT_RECORD_SEPARATOR", or "$RS" as a tribute to awk).
| So the line noise might be more common and thus more
| understandable than the "readable" version.
|
| I don't quite buy that for e.g. "$INPUT_RECORD_SEPARATOR",
| but there's an argument to be made for "$RS" or "$ARG"
| being worse than the Asterix swear words.
| jlg23 wrote:
| > I know this is meant as a joke, but I just use this to
| once again note that Perl actually had a very common
| linter/pretty printer way before it became all the rage
| (perltidy/perlcritic).
|
| And all great perl hackers deliver readable code. But we
| still enjoy a round of perl golf once in a while. And
| honor demands, that, if you respond in perl golf style to
| an interview question, you make it count ;)
| anthk wrote:
| Perl is readable, just indent it.
| jlg23 wrote:
| I know, I still have my black belt in perl somewhere. The
| one-liner is readable, too.
|
| Throw in some needless array-referencing-and-
| dereferencing so people can rightfully consider perl a
| write-only language...
| nerdponx wrote:
| 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))}'
| faizshah wrote:
| I wrote that as a one liner it's not supposed to be
| readable. Here's a readable version of essentially the
| same program:
|
| https://perlmaven.com/count-words-in-text-using-perl
| faizshah wrote:
| Nice! I came up with:
|
| perl -nle '$w{lc s/[[:punct:]]//r}++ foreach split(/\s+/,$_);
| print map{"$w{$_} $_ \n"} (sort{$w{$a} <=> $w{$b}} keys(%w))
| if eof()' < kjvbible.txt
|
| If anyone's curious this takes .47 seconds on my local
| machine whereas the optimized shell solution takes about 3.5
| seconds.
|
| Edit: It looks like mhd's usage of autosplit -a and @F are
| faster than split($_) but calling print foreach key is slower
| than my print map strategy.
|
| So our solutions are combined to get:
|
| perl -anle '$w{lc s/[[:punct:]]//r}++ foreach @F; END{print
| map{"$w{$_} $_ \n"} (sort{$w{$a} <=> $w{$b}} keys(%w))}' <
| kjvbible.txt
|
| Which runs in .39 seconds. mhd's solution runs in .42
| seconds. For reference the optimized C version takes .059
| seconds (possibly cause of clang?), wc -w takes .023s and the
| optimized python version takes .288
| FireTrader wrote:
| I haven't written perl in 5 years. Reading this evokes a rare
| sense of joy / Stockholm syndrome.
| hu3 wrote:
| I expected Rust to be faster than trivial Go code.
|
| Any specifics on why it's not?
| burntsushi wrote:
| 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.htm...
| komuW wrote:
| > prevent HashDoS attacks[1] at the expense of slower
| hashing. I actually don't know whether Go's hashmap does the
| same.
|
| From looking at the code[1], it seems like it does. From[2]
| it looks like it is only for platforms that have AES.
|
| 1. https://github.com/golang/go/blob/7bfe32f39c59056c49f5776b
| 10...
|
| 2. https://github.com/golang/go/issues/9365
| praveenperera wrote:
| I had a specific question about the rust implementation.
| ordered.sort_by(|&(_, cnt1), &(_, cnt2)| cnt2.cmp(&cnt1));
|
| would produce the same result as what was in the blog post:
| ordered.sort_by(|&(_, cnt1), &(_, cnt2)|
| cnt1.cmp(&cnt2).reverse());
|
| But would avoiding the `reverse` call make it any faster, or
| is that a zero cost abstraction?
| burntsushi wrote:
| I didn't check the codegen or anything, but:
|
| 1) Yes, almost certainly zero-cost. 2) This isn't a hot
| part of the program.
|
| See also: https://old.reddit.com/r/rust/comments/m5ix0s/per
| formance_co...
| hu3 wrote:
| 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 wrote:
| 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.)
| hu3 wrote:
| To clarify my question, can Rust read files and split
| their strings without checking UTF8 correctness? That
| could speedup the algorithm.
|
| In Go I have used this [1] in the past when I had to
| validate UTF8 encoding but on hot paths where I'm sure
| UTF8 is valid (coming from sanitized database data for
| example) I skipped that part.
|
| [1] https://golang.org/pkg/unicode/utf8/#Valid
| burntsushi wrote:
| > To clarify my question, can Rust read files and split
| their strings without checking UTF8 correctness? That
| could speedup the algorithm.
|
| That's what every single Rust program in this benchmark
| does, _except_ for the simple variant.
| unionpivo wrote:
| yes, you can operate on raw byte strings (you write them
| like b'this is ASCI' ), and then it would look like go or
| c code.
| codeflo wrote:
| Don't downvote, it's a really good question. Naively, I'd also
| have expected Rust to be faster, given the same algorithm. My
| guess is that without a GC, the Rust solution can't delay
| deallocating all those temporary strings (both variants seem to
| allocate a string for each word, though I'm not sure if Go
| doesn't simply share string slices). GCs free memory in
| batches, which is often more efficient, and sometimes don't
| have to do it all on process exit. The Rust code meticulously
| deallocates each string individually.
| comeonseriously wrote:
| It is a good question, but the downvotes may be from "Rust
| Fatige" aka "Why not just rewrite everything in Rust".
| mikewarot wrote:
| 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.
| kzrdude wrote:
| (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.
| drran wrote:
| It's not so ugly when you use C on a computer with less than
| 64Kb of RAM.
| shakna wrote:
| > So ugly, and you'd hope anything as non-reusable as that is
| deprecated with a strong wording.
|
| It isn't. It was only added in POSIX 2001. Still there without
| major changes in 2018. [0] (There's actually a lot of similar
| libraries in POSIX, that don't include re-entrant forms.)
|
| Thankfully, re-entrant versions are supplied as extensions by
| GNU, which is significantly less horrifying.
|
| [0]
| https://pubs.opengroup.org/onlinepubs/9699919799/basedefs/se...
| bluetomcat wrote:
| 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 wrote:
| 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 wrote:
| > 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.
| burntsushi wrote:
| From the OP:
|
| > Memory: don't read whole file into memory. Buffering it
| line-by-line is okay, or in chunks with a maximum buffer
| size of 64KB. That said, it's okay to keep the whole
| word-count map in memory (we're assuming the input is
| text in a real language, not full of randomized unique
| words).
|
| A shorter but less precise way of saying that is, "make
| the program work on streams."
|
| > You can mmap stdin/fd 0 after an `fstat(0,..)` no
| problemo. Can it fail and should you check errors? Sure
| (as can accessing stdin in any way, actually).
|
| Of course. And when it fails, what do you do? You defer
| to something that can handle a stream! Which is exactly
| the problem in the OP.
| cb321 wrote:
| I disagree. mmap will demand page into memory - typically
| _read_ ing 4K at a time off storage (though really the
| buffer cache in all these timings). Much less than 64K.
| Were the file bigger than RAM/were there competition, it
| would also evict earlier pages. It's really just another
| way to "buffer" without worrying about all the fuss in
| user space, and I don't think you're going to convince me
| otherwise. I mean, MAP_POPULATE might violate the idea,
| but that is a very special case of mmap.
|
| Honestly, I think the author himself saying memory-mapped
| IO is a forward direction but "enough for now!" is pretty
| conclusive that he didn't think it was a forbidden
| optimization direction. I think you are over interpreting
| his early step-by-step style language explaining finite
| memory as a strict spec, or perhaps he shared an earlier
| draft of the article with you before he wrote that.
|
| It's fine to fail over to a stream, but often mmap is
| faster, as I know you know.
| burntsushi wrote:
| If you mmap'd a file, how do you keep its maximum memory
| usage to 64KB? I actually don't know the answer to that
| question. It's definitely not the default. You don't get
| to control it. The OS does.
|
| > It's fine to fail over to a stream, but often mmap is
| faster, as I know you know.
|
| But that's exactly the point. You literally cannot use
| mmap in all cases, either because you just can't or
| because it's actually slower. And in those cases, you
| need to fail over to a streaming implementation. And that
| streaming implementation needs to be fast too. And _that
| 's_ what this benchmark is.
|
| If you submitted a program that only used mmaps, and I
| sent a stream into that program, it would fail. So then
| you would need to modify the program to handle streams.
| And your strategy for dealing with mmaps couldn't be
| used. So then you'd need to optimize your handling of
| streams. Which is exactly what the programs in the OP are
| doing. So in the end, mmaps are a distraction for a
| benchmark like this, and I suspect that's why the OP
| didn't bother with them.
| cb321 wrote:
| You keep ignoring the author literally opening it up as
| an avenue in:
|
| >I'm sure there's further you could go with the C
| version: investigate memory-mapped I/O, avoid processing
| byte-at-a-time, use a fancier data structure for
| counting, etc. But this is quite enough for now!
|
| This subthread started with bluetomcat talking about the
| optimized C and what experienced C devs might do. That
| strikes me as fair game to open up discussion of
| alternative IO anyway _even if_ the author hadn 't
| already (which he clearly did, as quoted). So, that's two
| reasons it's worth bringing up, and I was never
| criticizing your program!
|
| If what you are on about is "Who wins what scorecard
| against what arbitrary constraints" or "My hands were
| tied, really!" or whatever, then, sorry, but this
| benchmark is too uncontrolled for great answers even on
| its own terms. Various stdio-using things would be "out
| of constraints" if a system was configured with bigger
| than 64K default buffers anyway which is certainly
| possible, if unlikely, today. None of the sample programs
| or the test harness "check" for that. Some of the
| languages may not be able to ensure it. Using that to
| leapfrog to "only streams" is a stretch. Is CPU freq
| scaling controlled? Min of N trials to filter background
| noise/get repeatability? Even simple mean+-sdev? No, no,
| and no. And probably four more things.
|
| Beyond all of that, I also don't think that's what _this
| subthread_ was ever about. bluetomcat 's opening was
| literally the opposite - equivalent to "real devs would
| do xyz _implicitly independent of the arbitrary
| constraints posed_ if performance is paramount
| "..seemingly a follow up on my quote from the author. He
| can of course chime in if I misread that. Presumably, the
| author would have had to relax that already problematic
| 64K constraint when moving on to mmap (which moving on he
| might have done if the article were fewer languages or if
| he had just done it that way first in his open coded C).
|
| The positions you seem dug into here seems to me "don't
| mention mmap to people questioning the posing of the
| contest even though the author did" or "you cannot
| default to mmap and fail over like
| fstat||mmap||do_streams||aiie_noStdInEven". Yes, which is
| faster varies by OS/situation. So? Maybe "experienced"
| C/whatever devs know their situation. (You use mmap in
| ripgrep...). Maybe these are all honest communication
| errors, but I don't think your positions are very
| tenable.
|
| As I mentioned in a few places, performance conclusions
| here are harder than they might look. As for
| "distractions", one might say that about literally all
| the optimized variants, including their numbers in the
| table since the numbers are likely to change more. The
| article might be stronger to focus on only the simple
| variants of all the rest, leaving the optimized ones for
| the github repo and weird "contest rule" debates on the
| github issues.
|
| Anyway, to add a little more actual information for
| passersby less dug in to defending some weird position
| like "", Nim's stdlib has a trie in critbits module. So,
| that test is "in bounds" and an easy experiment someone
| might enjoy.
|
| Have a nice day.
| burntsushi wrote:
| It's not about a scorecard. I didn't just dig my heels in
| and say, "language lawyering the OP says mmap isn't
| allowed so shut up." It's about what's a useful
| benchmark. I explained _why_ mmap 's are a distraction
| beyond just pointing to the OP's constraints. I don't
| think there's really much else to say and I disagree with
| your characterization of this thread.
| bluetomcat wrote:
| > As for "bad spatial and temporal locality," can you be
| more specific?
|
| One could use a lexicographic Btree-like structure with
| multiple characters per node, sharing consecutive cache-
| lines. For looking up the word "bar", you would traverse
| the "b" key from the root node, then its child "a" node,
| then the "r" child of the "a" node. Most of the nodes near
| the top would remain hot in the cache, and deeper less-
| visited nodes could be joined or compacted based on some
| criteria. Of course there are many subtleties, special
| cases and complications and the solution would be far more
| complex in terms of source code length.
|
| With a hash table, you effectively compute a hash for every
| word, and then jump at arbitrary locations throughout the
| whole table.
| burntsushi wrote:
| You've traded hashing for a memory access per byte. I did
| something similar in the 'optimized-trie' program for
| Rust: https://github.com/benhoyt/countwords/blob/master/r
| ust/optim... --- It ended up being slower. But, it is
| very much impacted by cache effects. So the next step
| here would indeed be to figure out how to reduce cache
| misses. But it's non-trivial.
|
| Like, maybe your idea works. _Maybe_. I don 't know.
| You'd have to try it. But it's not clear to me that it
| will. And it doesn't support "is far from what an
| experienced C programmer would write if performance was
| paramount" IMO.
| eisvogel wrote:
| 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 wrote:
| This comment is utter nonsense.
| andy_threos_io wrote:
| 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 wrote:
| Yeah, I noticed that too:
| 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. :-)
| gpderetta wrote:
| 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.
| usefulcat wrote:
| -O3 makes basically no difference for this code. I tried it.
| sesuximo wrote:
| Why copy the string at all? You have string in file. Mmap file
| and just store string view of it.
| gpderetta wrote:
| 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 wrote:
| 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 wrote:
| good point about the string being const! There are ways
| around that, but none pretty.
| Shorel wrote:
| 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...
| felixr wrote:
| If you want to read the " ten-page Knuthian masterpiece":
| https://homepages.cwi.nl/~storm/teaching/reader/BentleyEtAl8...
|
| I don't think it was linked from the article
| henrik_w wrote:
| Also interesting is that this problem is used as the example in
| the book "Exercises in Programming Style" by Cristina Videira
| Lopes. It shows this problem solved in 33 different programming
| styles, for example historical, function composition, data-
| centric etc.
|
| I have written more about it here:
| https://henrikwarne.com/2018/03/13/exercises-in-programming-...
| taeric wrote:
| There is a new version of that book. Thanks for bringing it
| to my attention, looks great!
| jerf wrote:
| 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.
| ngngngng wrote:
| Last summer I was looking for a program that would tell me
| which shell commands last used in a specific directory. Because
| I had been reading "The Unix Programming Environment" it
| quickly occurred to me that the program I was looking for could
| easily be made from several existing commands. Only after I
| wrote the small script did I find that the solution already
| existed except it was >1000 lines of code, 20 github
| contributors, and utilized a sqlite database.
|
| My one line has less features, but I'll take it.
| 35fbe7d3d5b9 wrote:
| 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 Faberge 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
| taeric wrote:
| Sorta. That incident is also famous for being easy to
| misrepresent.
|
| That said, if you are new to that, Programmer Pearls is a great
| series. And literate programming is neat to at least know of.
| chaostheory wrote:
| 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
| gibsonf1 wrote:
| 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 wrote:
| 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
| Frost1x wrote:
| Also not entirely sure how one plans to compare runtime
| performance when the original article didn't really describe
| the hardware it ran on that I could see skimming it over. If
| you can get better runtime performance results and run
| against ancient hardware of the same architecture, you may be
| able to assume you're below the lower bound of the benchmark
| system explored. If your runtimes are better in that case,
| you may be able to place high confidence that the LISP
| example in this case actually is more performent. Definitely
| would run it against the same inputs they used since they
| provide it and describe how you can easily get/derive the
| input (some Project Gutenberg ebook concatenated 10 times).
|
| I suppose you could also recreate all their examples to
| create your own baseline of runtime performance but that's a
| lot of work for what seems to be a not-very empirical
| benchmark (at least to me).
|
| Disclaimer: I did not check runtime complexity of any of the
| implementations because I didn't really care and skipped
| straight to the performance results table.
| woliveirajr wrote:
| On a 4.3MB file:
|
| https://github.com/benhoyt/countwords/blob/master/kjvbible.t.
| ..
| gibsonf1 wrote:
| Missed the sample set from the example. on the kjvbible.txt
| file with no optimization: ... WEB> (time (performance-
| count "/home/frederick/kjvbible.txt"))
|
| the 64015
|
| and 51313
|
| of 34634
|
| 26879
|
| to 13567
|
| that 12784
|
| in 12503
|
| he 10261
|
| shall 9838
|
| unto 8987
|
| for 8810
|
| i 8708
|
| ... Evaluation took: 0.365 seconds of real
| time 0.370322 seconds of total run time
| (0.338364 user, 0.031958 system) 101.37% CPU
| 1,060,005,621 processor cycles 106,297,040 bytes
| consed
|
| I had a bug in my original code which alphabetized rather
| than sorted by count, so the sort line should be:
|
| ((keys (sort (alexandria:hash-table-keys map) (lambda(x
| y)(> (gethash x map)(gethash y map))))))
| duckerude wrote:
| That file repeated 10 times, even:
| https://github.com/benhoyt/countwords/blob/master/test.sh
| Sekhmet wrote:
| It's just testing the output. For benchmark each variant
| is run 5 times with kjvbible.txt as input and then the
| lowest execution time is used as benchmark.
| gibsonf1 wrote:
| In that case, unoptimized lisp for kjvbible.txt at 0.365
| is 3rd fastest beating C
| coder543 wrote:
| Do you have the same exact hardware that the article is
| using? Otherwise, we can't say one way or another on that
| with the data you've provided.
|
| I'm also pretty certain the article is benchmarking
| against the 10x copy file for the actual benchmarks.
|
| See this example command in the article:
| time $PROGRAM <kjvbible_x10.txt >/dev/null
|
| So, even if you had the exact same hardware, I'm pretty
| sure your program would only be a bit faster than the
| unoptimized C# version. However, it's possible that your
| machine is a lot slower than what's used in the article,
| and your program is actually pretty fast -- but without
| more points of comparison, we just don't know. You
| haven't run the other benchmark programs on your hardware
| and posted the results.
| gibsonf1 wrote:
| It would be interesting to have the article author run
| the lisp code on their machine for a real comparison -
| would be very interested to see the results. My machine
| is a Linux (Ubuntu) laptop. I just sent an email to the
| author with the common lisp code - we'll se if he's
| interested enough to check.
| [deleted]
| gibsonf1 wrote:
| 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
| [deleted]
| coder543 wrote:
| Beyond the comments other people left here, for the results to
| be comparable, you need to provide the result for at least one
| (but ideally more than one) of the solutions in the article
| running on your hardware... otherwise you could just have a
| really fast (or slow) machine.
| [deleted]
| djhworld wrote:
| 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?
| cp9 wrote:
| https://github.com/golang/go/issues/45021
| [deleted]
| coder543 wrote:
| 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.
| benhoyt wrote:
| 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.)
| bjarneh wrote:
| > 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 wrote:
| 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 wrote:
| Link to the (great) CppCon talk:
| 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. :(
| andrepd wrote:
| 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.
| frankenst1 wrote:
| 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]
| typon wrote:
| The (unoptimized) Python version is fast enough and imo the most
| readable.
| [deleted]
| Shadonototro wrote:
| I don't like C#, but before "doing benchmark", you should
| probably learn to write efficient code, because your code is very
| naive, 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 wrote:
| I absolutely agree, and would like to add that the C example
| further reinforces this
| _old_dude_ wrote:
| 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 wrote:
| Maybe graalvm native version could be competitive
| svat wrote:
| There is a question on Stack Exchange about exactly this:
| 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 and in the
| discussion on a "Donald Knuth was framed" article:
| 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 wrote:
| Very interesting -- I hadn't seen that. Thanks for the link.
| platz wrote:
| 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)
| thefilmore wrote:
| The link to the repo is broken.
| benhoyt wrote:
| Thanks for that - fixed. Repo link is:
| https://github.com/benhoyt/countwords
| submeta wrote:
| Would love to see this for Common Lisp.
| gibsonf1 wrote:
| 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 wrote:
| Does that use the corpus from the article?
| fishmaster wrote:
| Me too. Alas, I can't do it myself.
| ncmncm wrote:
| 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 wrote:
| 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 wrote:
| 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 wrote:
| I'd be happy to be _shown_ that I 'm wrong.
| indweller wrote:
| Can someone explain why trie is not faster than hash table?
| burntsushi wrote:
| The source code of the trie program I wrote is here:
| 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
| throw_away wrote:
| 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.
| dietrologia wrote:
| I wonder why the C++ version didn't use a map, instead of doing
| unordered_map and then copying into a vector.
| ZeroGravitas wrote:
| 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.
| hamburglar wrote:
| 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.
| Veedrac wrote:
| It does irk me too. Being a programmer requires understanding
| the complexities hidden behind a task, and this brushes them
| all aside as if they don't matter.
|
| There are cases where your task is nice, simple, and well-
| defined, but word counting is not one of them. It's better to
| give a more realistic task that allows people to think about
| the premises.
| EvilEy3 wrote:
| This is litmus test to weed out people who pretend to be
| programmers. You assess complexities hidden behind the task
| in system design round.
| hamburglar wrote:
| Being a programmer involves a lot of things that are
| difficult to test for all at once in 45 minutes. Be irked
| all you want, but it seems counterproductive to pretend
| what's being asked is in anyway unclear or unreasonable
| when you're given a pure programming question with a clear
| spec. You're supposed to write the code. That's all.
| Veedrac wrote:
| My problem isn't that the spec is unclear, it's that the
| spec is silly. The task makes no sense, and selects for
| misusing tools. This makes it a bad interview question as
| given.
| hamburglar wrote:
| I'd argue that the problem does make perfect sense and
| isn't a "misuse of tools" if you manage to understand the
| goal of the interviewer, which is "watch this person
| write code for a solution to a well-specified but
| arbitrary (perhaps even silly) problem."
| hamburglar wrote:
| ... otherwise the proper answer is probably "I would
| recognize I'm sitting in a room with someone who has likely
| already put enough thought into this task that they could be
| considered an expert on the solution and I would consult them
| on the best solution rather than reinventing the wheel,"
| which would almost certainly not get you hired.
| superdimwit wrote:
| Who writes the third party library, though?
| lionkor wrote:
| SomeOtherGuyWhoCares(tm) in cooperation with
| ItWorksOnMyMachineSoYourMachineIsBroken Inc.
| jlg23 wrote:
| > 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".
| IshKebab wrote:
| > use some established third party library that does this exact
| task well
|
| I seriously doubt such a library exists for most languages
| (Javascript might be an exception because they seem to love
| writing one-line libraries). It's such a simple task!
| heavyset_go wrote:
| 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.
| nicholasjarr wrote:
| Really great stuff. Good job!
| dietrologia wrote:
| 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.
| cb321 wrote:
| 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
|
| [2] https://github.com/c-blake/adix/blob/master/tests/wf.nim
| chris_st wrote:
| 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/...
| cb321 wrote:
| 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 wrote:
| 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. }
| chris_st wrote:
| Thanks! That's a much cleaner implementation, and I
| learned some cool nim. I got a note on GitHub with a
| similar implementation, so I went with theirs.
|
| And, cool, "BS-scaling" is my new term of art :-)
| rtb wrote:
| 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 wrote:
| The grep version searches the input for "foobar" [1]. Hence, it
| doesn't solve the problem.
|
| [1]
| https://github.com/benhoyt/countwords/blob/eb2a8adf21c895907...
| rtb wrote:
| Thanks! I think he should make that a lot clearer in the
| "results" table.
| benhoyt wrote:
| 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".
| justbored123 wrote:
| 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 wrote:
| 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 wrote:
| TIL Mozilla, AWS, Google, Microsoft, and Huawei are "nobody"...
| https://foundation.rust-lang.org/
| throwaway4good wrote:
| 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 wrote:
| 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.
| Shorel wrote:
| 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 Malkiiat prints: kakvo 62 sa
| 61 ako 58 kogato 56 me 55 beshe 53
| a 51 planeta 51 li 49 chovek 43 edno
| 42 be 42 den 42 koito 40
| albertzeyer wrote:
| 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.)
| tadkar wrote:
| 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
| jeromeof wrote:
| Great, it would be nice if Java was included by the op
| ephaeton wrote:
| This shouldn't compare unicode-aware 'tolower' with ASCII-tolower
| ... sends false signals. "Optimizing" by setting LC_ to "C" .. oh
| my.
| 1f60c wrote:
| If you know something the author doesn't, I'm sure they'd
| appreciate a (constructive!) reaction blog post.
| ephaeton wrote:
| 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.
| jerf wrote:
| 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 wrote:
| 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".
| burntsushi wrote:
| 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.
| _wldu wrote:
| 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 wrote:
| 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.
| Ballas wrote:
| But both wc and grep are written in C...
| dcu wrote:
| https://lists.freebsd.org/pipermail/freebsd-current/2010-Aug...
| Simplicitas wrote:
| exactly .. this is the part I don't understand
| quietbritishjim wrote:
| 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.
| dgellow wrote:
| You can see them as a baseline
| bestinterest wrote:
| 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
| frankenst1 wrote:
| Could you update it so that you have "word count\n" on each
| line?
| bestinterest wrote:
| Like that?
| frankenst1 wrote:
| 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 wrote:
| Checkout Crystal lang one (Ruby but fast),
| https://github.com/benhoyt/countwords/pull/21/files seems
| to keep readability intact and committer is saying it
| outperforms Go which is interesting.
| frankenst1 wrote:
| Clocks in at 1.48s for me which is faster than Ruby but
| slower than JavaScript.
| [deleted]
| taeric wrote:
| 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.
| ZoomZoomZoom wrote:
| 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/
|
| 1. https://en.wikipedia.org/wiki/Stemming
| s9w wrote:
| I've never seen a multi-lang benchmark without glaring mistakes
| in a subset of them
| Shorel wrote:
| No Dlang included makes me sad.
| OskarS wrote:
| 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.
| josefx wrote:
| 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.
| haolez wrote:
| FORTH is the ideal language for a zombie apocalipse. Nothing
| comes close when you start with a CPU and nothing else :)
| anthk wrote:
| 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.
| maccam912 wrote:
| 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!
| MaxBarraclough wrote:
| 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#issuecommen...
| musingsole wrote:
| I often wonder how fast I'd run a race if I shot my foot too.
| oefrha wrote:
| > 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/2fe408497e6838b6fb761...
| MaxBarraclough wrote:
| 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 wrote:
| 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/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.
| benhoyt wrote:
| That link shows that yes, "_count_elements" is
| implemented in Python, but right after it pulls in the C
| version if available (which it presumably is in CPython):
| try: # Load C helper
| function if available from _collections import
| _count_elements except ImportError:
| pass
|
| Here is the C version (with a comment a little way down
| describing the "fast path advantages": https://github.com
| /python/cpython/blob/93d33b47af70ede473f82...
| MaxBarraclough wrote:
| Well spotted, thanks.
| MaxBarraclough wrote:
| Thanks for the link, interesting that __count_elements_
| is written in Python. At a glance it looks like the kind
| of thing that might benefit from being written in C, but
| presumably that 's not the case. Perhaps because of the
| dynamic typing of both arguments?
|
| > Python itself does not function at all without the dict
| implementation since it's the underpinning of the object
| model.
|
| Sure, but I don't see the point here.
|
| > Calling str.split() a standard library method is...
| okay.
|
| For our purposes there's no reason to draw a distinction
| between standard-library functionality closely integrated
| into the language, and standard-library functionality
| that isn't. The relevant point is that computational work
| is being handed off to optimised C code.
|
| Again, if you're optimising Python, the smart move is
| indeed to make maximal use of the optimised machinery in
| the standard-library (or for that matter some other
| dependable library). My point still stands: it would be
| interesting to look at a problem that isn't amenable to
| this approach, where the performance of the Python
| interpreter itself would be brought to the fore by
| necessity.
|
| How easy it is to find such a problem will be a function
| of how good a job Python does of providing applicable
| optimised functionality in its standard-library. Perhaps
| something like computing matrix determinants? I don't
| know enough Python to say.
| acdha wrote:
| It can be interesting - especially if you also compare it
| to something like the PyPy JIT - but it runs afoul of the
| idiomatic angle since Python has had decades of
| recommended practice being to write code in Python and
| optimize the hotspots in C, which has led to very popular
| libraries like NumPy, PIL/Pillow, etc. becoming almost
| universal in community recommendations.
| MaxBarraclough wrote:
| Right. They don't emphasise improving the performance of
| the Python interpreter precisely because they prefer to
| handle computational heavy-lifting in C instead. Python
| has been very successful with this approach. Java takes
| the opposite approach, promoting 'purity' and investing
| very heavily in JVM performance.
|
| It would still be interesting to see for benchmark
| purposes.
| acdha wrote:
| Agreed -- and especially so if you could see how common
| it is that CPython performance tanks but PyPy (or
| Jython?) does not after the JIT kicks in.
| MaxBarraclough wrote:
| (Too late to edit) benhoyt's comment points out that
| __count_elements_ has two implementations, one in Python
| and one in C. The Python version is used only if the C
| function is not found.
| heavyset_go wrote:
| > _Perhaps because of the dynamic typing of both
| arguments?_
|
| It wouldn't matter, you'd be dealing with PyObject
| pointers in C anyway.
| MaxBarraclough wrote:
| Right, that's what I meant. If the C code has to cope
| with dynamic typing anyway, there might be little scope
| to speed things up.
|
| The same isn't true for, say, string operations, where
| there might be plenty of opportunity to move tight loops
| from Python to C and speed things up considerably.
| heavyset_go wrote:
| Truthfully, I don't think optimization was a motivation
| for writing _count_elements() in Python or not. The
| CPython project doesn't prioritize optimization of the
| language or standard library unless there are clear
| performance gains to be made in the face of slow code.
| What most likely happened is someone wrote some code on a
| mailing list or bug report, and a maintainer included it
| as is.
|
| Reading the bug report that introduced Counter[1], the
| author states it is the simplest implementation they came
| up with, and Guido and other maintainers prioritized
| simplicity.
|
| [1] https://bugs.python.org/issue1696199
| MaxBarraclough wrote:
| Interesting, thanks.
| cies wrote:
| 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 wrote:
| 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 wrote:
| 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/eb2a8adf21c895907...
| unwind wrote:
| 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.
| benhoyt wrote:
| Yeah, I would have liked to avoid it too. But I think you have
| to allocate with the hcreate/hsearch API (for the "simple" C
| version). When I roll my own hash table with optimized.c I
| don't allocate for the integers.
| unwind wrote:
| No, you can just jam the integer into the "data" field in the
| structure and skip that allocation.
|
| As I said, and others have commented, it requires some
| complicated castery to avoid UB, but it's totally doable (and
| at least GCC does the right thing, while warning, with no
| advanced casts).
|
| Thanks for an interesting article!
| chaostheory wrote:
| It would be nice if the post went further as in using code that
| either uses concurrency or parallelism.
| burntsushi wrote:
| Someone on Lobsters suggested this too, and I don't think it
| would be particularly edifying. But maybe I'm wrong. Someone
| should go out and do that benchmark. Maybe we'll learn
| something. Here is what I wrote though:
|
| Coming up with a benchmark is hard. Benchmarks like these are
| models. _All models are wrong._ But. Some are useful.
|
| Follow you thinking to its logical conclusion. If you open up
| the parallel programming flood gates, now you need to do that
| for all of the programs. Now your effort to contribute a
| sample for each language goes up. Maybe enough where actually
| doing the benchmark isn't practical.
|
| So let's play the tape. If someone told me, "sure, have fun,
| throw threads at this!" I'd probably say, "can I use memory
| maps?" And let's say, "yes, sure, go for it!" I say okay,
| here's my first crack at it:
|
| 1. Hope stdin is a file and open it as a memory map.
|
| 2. Split the memory map slice into N chunks where N is the
| number of logical CPU cores on the system.
|
| 3. Run approximately the same algorithm devised in existing
| code submissions in N different threads, with one thread per
| chunk.
|
| 4. At the end, join the results and print.
|
| _If_ that ends up being the best strategy overall, then your
| model has become over-complicated because performance now
| likely depends on step (3). Which is exactly what the
| existing benchmark is. Now, maybe some languages have a
| harder time passing data over thread boundaries than others
| and maybe that impacts things. But that doesn 't apply to,
| say, C, Rust, C++ or Go.
|
| If that's not the best strategy, then maybe there is a
| cleverer approach that involves synchronizing on one shared
| data structure. I doubt it, but maybe. If so, your benchmark
| turns into one that is very different. It's no longer just
| about data transformation, but now you have to worry about
| synchronization trickiness. And now you're way outside of a
| standard goroutine pool that you might have used in Go.
|
| Building a good benchmark is an art. Sometimes the
| constraints look dumb and arbitrary. But you have to sit down
| and really look at it from a bunch of different angles:
|
| * Do the constraints approximate some real world conditions?
|
| * Do the constraints inhibit writing code that looks like
| real world code?
|
| * Do the constraints inhibit optimizing the crap out of the
| code?
|
| * Do the constraints make the benchmark difficult to create
| in the first place?
|
| * Do the constraints permit easy and clear measurement?
|
| There are probably more things that I didn't think about.
| chaostheory wrote:
| Yes, benchmarks are hard. However, single thread benchmarks
| don't reflect the real world unless you're a student.
| c-cube wrote:
| 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.
| beached_whale wrote:
| At least in C++, it's any integer type that is large enough.
| uintmax_t/intmax_t are guaranteed to be large enough
| scatters wrote:
| It just means that you need to cast _via_ intptr_t, i.e.
| double casts `(void*)(intptr_t)i` and `(int)(intptr_t)p`.
| GLib has macros for it if you feel that 's useful.
| fanf2 wrote:
| If you need to round-trip a pointer through an integer and
| back to the same pointer, you need to use intptr_t or
| uintptr_t. (Note that this is true for object pointers but
| not necessarily function pointers. There's no integer type
| guaranteed to be big enough for a function pointer.)
|
| If you want to round-trip an integer through a pointer and
| back to the same integer, you can use any integer type
| provided it is not bigger than intptr_t or uintptr_t.
| remexre wrote:
| 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 wrote:
| 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.
| c-cube wrote:
| I wonder if it's like insanities like SIGPIPE: it's kind
| of useful if you write IO tools in a few dozen/hundred
| lines of C. You don't need to carry around explicit
| context, or check if writes failed, or anything. Of
| course it sucks for anything else and we still have to
| deal with SIGPIPE .
| throwaway13337 wrote:
| For more language benchmarks of this sort, there is a pretty
| extensive list:
|
| 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_ wrote:
| 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 wrote:
| 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/...
| _ph_ wrote:
| 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 wrote:
| Again, for the benchmarks game, C is not free to
| implement an optimized hash table for the problem.
|
| Any of the programs are free to implement a "custom hash
| function" and many of them do.
|
| hash table != hash function
| techolic wrote:
| 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()
| MauranKilom wrote:
| 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.
| usefulcat wrote:
| 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&)
| jjnoakes wrote:
| 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.
| jeffbee wrote:
| 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.
___________________________________________________________________
(page generated 2021-03-15 23:02 UTC)