Hacker News Reader

Comment by stabbles | Hacker News Reader

The title I/O is _no longer_ the bottleneck seems to suggest disk speed has caught up, while in reality the slowness is due to poor implementation (slow Python or Go with lots of allocations).

The real problem to me is that languages are too high-level and hiding temporary allocations too much. If you had to write this in C, you would naturally avoid unnecessary allocations, cause alloc / free in the hot loop looks bad.

Presumably soon enough it's very unlikely you find any new word (actually it's 10 passes over the same text) and most keys exist in the hashmap, so it would be doing a lookup and incrementing a counter, which should not require allocations.

Edit: OK, I've ran OP's optimize C-version [1] and indeed, it only hits 270MB/s. So, OP's point remains valid. Perf tells me that 23% of all cache refs are misses, so I wonder if it can be optimized to group counters of common words together.

[1] https://benhoyt.com/writings/count-words/

View on HN

I don't know if I can agree. Python is certainly problematic for the reasons you outlined, but Go is much closer to C in terms of performance. Go is also compiled, and as such you have similar opportunity to optimize and measure allocs. In my experience it's much harder to tune Python, and Go is often easier to tune than C due to the great ergonomics of the compiler. You can also drop down to assembly!

But really, I disagree because I've frequently saturated massive IOPS. I/O is still the bottleneck. The article pretty much immediately excludes network I/O, which is in many cases more common than disk I/O. Even so, tiny single-threaded programs reading words one-at-a-time are obviously not going to be I/O constrained with modern disks. For these types of programs, I/O hasn't been a bottleneck in a long, long time, and I'd actually be surprised to hear candidates suggest otherwise.

Let’s call spades spades: C spanks Go in every measure. Go is nowhere near C speed.

It’s certainly more performant than any dynamically typed scripting language: JavaScript, Python, Ruby, etc but it’s probably closer to C#.

Go’s problem is that in practice there are interfaces (fat pointers) everywhere. I’m about to start optimizing one of the services my team owns and my first step is going to be looking for all the bad performance issues that comes out of this.

yeah, a friend of mine wrote a logfile parser in 01996 in c, and when i rewrote it in perl (also in 01996) it was about one tenth the size and ten times slower

whether i/o is the bottleneck depends on what you're doing and on which computer, and that's been true for at least 50 years

May I ask what's the rationale for writing 01996 rather than 1996? I've seen this before but I haven't seen an explanation of the advantage of it.

Y-10K awareness: https://longnow.org/ideas/long-now-years-five-digit-dates-an...

But it looks like an octal literal.

Haha, I thought it was some architecture I’ve never heard of.

I mean, Go is closer to C than Python is. But Go is still a garbage collected language with a runtime. It's not going to come close to the limits of performance that C offers

For a script like this your be surprised. If you don't do too much allocation, the garbage collector need not run. In fact it's common to disable it at the start. Now you can allocate much faster than C because you never clean up after yourself!

A real world example is esbuild, the author implemented it both Rust and Go initially. The Go version was faster and the code simpler. Which is why it's implemented in Go.

> A real world example is esbuild, the author implemented it both Rust and Go initially. The Go version was faster and the code simpler. Which is why it's implemented in Go.

But why is swc faster than esbuild then? The code isn't even considerably more complex.

Because different programs, implemented differently, run at different speeds...

I'm saying the performance of Go can sometimes be surprisingly fast. Not that it's magic.

So you're saying they wrote exactly the same program in Go and Rust for the comparison, changing the syntax only? Well then it's no surprise the Go version was faster.

Don't write Rust as if it was Go. That doesn't say anything meaningful about either Go or Rust.

Actually he wrote the Rust version first, so you're wrong jumping to conclusions.

I'm not trying to say Go is faster than Rust, it's usually slower. But there are always exceptions to the rule. The Go code, on the other hand, is usually simpler and quicker to write. For that reason I'd prefer Go if the problem lends itself to a garbage collected language.

So what did you mean by this?

> Because different programs, implemented differently, run at different speeds...

We're talking about two programs with exactly the same purpose - ingest TypeScript and output JavaScript. It's a pretty clear-cut comparison, IMHO.

> The Go code, on the other hand, is usually simpler and quicker to write

I'm writing Go code at work, and Rust code mostly for fun (but used it at work too). I'd say this has changed significantly in the last 2 years. Now with rust-analyzer and much improved compiler output, writing Rust is very simple and quick too. I guess getting into Rust can be a little harder if you've only ever used GCed languages before, but it's not that hard to learn - and once you do it's super-effective. And the type inference of Rust is a huge reason why I'm using it - while Go has none.

Another thing to consider - usually the code in Go is much more about writing algorithms yourself instead of using library functionality (this is changing slowly thanks to the new support of generics but most code hasn't caught up yet and there aren't good libs using it so far). The resulting code in Go can be convoluted a lot and contain very hidden bugs. People also usually don't bother implementing a proper search/sorting algorithm for the sake of simplicity/speed of development - which you'd get automatically if you used a library function - so the code is less efficient. My Go code is usually 2-3x longer than the equivalent in TypeScript or Rust.

Go is great, I like it. Rust is great too. I recommend you to do what the esbuild author did - test it and choose for yourself, don't bother too much about others' opinion.

> We're talking about two programs with exactly the same purpose - ingest TypeScript and output JavaScript. It's a pretty clear-cut comparison, IMHO.

There are an infinite number of ways to design two programs for that task, with different trade-offs. You can't draw conclusions about which language is faster based on two different implementations by different people.

> Go is great, I like it. Rust is great too. I recommend you to do what the esbuild author did - test it and choose for yourself, don't bother too much about others' opinion.

I'm actually writing Rust code the last two years. It's been a while since I've used Go. But I'd rather use Go if the problem allows for a garbage collector. It's just simpler than managing it manually in Rust with the borrow checker and its rules. This is my opinion, nobody else's.

The GP didn't say that, maybe they wrote Go as if it were Rust, for all we know.

You can find the comments from the ESBuild author here on HN:

https://news.ycombinator.com/item?id=22336284

Rust compiler is much faster today than it was in 2020, btw.

> This is a side project and it has to be fun for me to work on it.

I respect this 100% - but then we shouldn't assume Go is better than Rust just based on that esbuild used it instead of Rust.

You could LD_PRELOAD a free that doesn't do anything in C too or a macro define to really make it no cost.

You'd need to change malloc too so it doesn't do extra work. You could do it. Go obviously isn't going to be faster than well written C. But sometimes you can be surprised.

Having played with this a previous time it was posted and looking at the profiler results, the main difference between the Go and C isn't due to any memory allocations but rather the lack of in-place update and slightly higher cost from being general-purpose in Go's hash table. (This is also probably why Rust, without the GC overhead, clusters with Go rather than C.)

I'm fairly certain that if one wrote C (or C++) programs with the same safety targets that Rust has out-of-the-box the performance is close, if not (for practical purposes) identical.

Of course, to do much useful (and performant) in Rust one often has to break out `unsafe`, which eliminates some of the out-of-the-box guarantees for safety--and in some cases makes one wonder if it's worth all the overhead instead of just using C or C++.

> the same safety targets

Rust's selling point is that the safety targets' costs are dev/compile-time ones. There should not be a difference unless the C/C++ code requires some IB or extremely manual memory management trickery, which it doesn't; and Go offers basically the same memory safety guarantees as Rust in this regard and is (slightly) faster.

In this case it's really almost entirely about the speed of the hash table.

I was referring to the overhead of development time. Rust is more complex than C, at least, and even after having gained proficiency coding in Rust still takes more time than writing an equivalent C program.

And "zero-cost" is misleading. There are definitely performance impacts from the implicit (and unadvertised explicit) bounds checking some of Rust's features come with. Writing a C program to an equivalent level of safety would have similar performance impacts. Hence, for as close to the same safety as possible, Rust and C should be almost identical in terms of performance.

That's probably the reason why Go got many people switching from their scripting languages and didn't end up as the C killer it was sold in the beginning.

That's exactly my reason to use it: fast prototyping and ability to replace bash scripts (as they become too unwieldy to maintain and expand from one point and on).

I've also successfully made an MVP with Golang which I then proceeded to rewrite in Rust in almost only one go and almost without blockers along the way.

Golang is pretty good but it still lacks important things like algebraic data types, and they're hugely important for fearless refactoring and correctness.

I never remember it being sold as a C killer maybe as a Java killer?

It was sold as C killer in the beginning.

And then a few years later there was an article that said, the Go engineers were surprised when they saw C/C++ coders weren't switching to Go rather Python/Ruby coders were "upgrading" to Go.

golang.org circa 2010:

> go is ... fast

> Go compilers produce fast code fast. Typical builds take a fraction of a second yet the resulting programs run nearly as quickly as comparable C or C++ code.

https://web.archive.org/web/20100217123645/http://golang.org...

That seems to me like they were trying to say "If you want C/C++ performance but nicer/easier syntax, you can use Go", which turned out to be not that true in the end.

Edit: the old "Language Design FAQ" also goes further in detail on how the envision (the first version of the) language: https://web.archive.org/web/20100211104313/http://golang.org...

I believe Go was created to replace python at Google.

It was more sold as a C++ killer than a C killer.

The Go code is reasonably efficient at avoiding allocations, though it's hard to avoid some. Without thinking too hard, it's also going to be hard to avoid those same ones in C, and some possible improvements would apply to both (e.g. defining a maximum word length).

"Lowercase word count" is a surprisingly difficult case in this regard, because you need to check and potentially transform each character individually, and also store a normalized form of each word. Probably some smart SIMD lowercase function could help here but I don't think any language is going to offer that out of the box. It's also defined in a way I think detaches a bit much from real-world issues - it's handling arbitrary bytes but also only ASCII. If it had to handle UTF-8 it would be very different; but also if it could make assumptions that only a few control characters were relevant.

> but I don't think any language is going to offer that out of the box.

That's what compilers are for. I tried to improve the C version to make it friendlier to the compiler. Clang does a decent job:

https://godbolt.org/z/o35edavPn

I'm getting 1.325s (321MB/s) instead of 1.506s (282MB/s) on a 100 concatenated bibles. That's still not a 10x improvement though; the problem is cache locality in the hash map.

Note: Just concatenating the bibles keeps your hash map artificially small (EDIT: relative to more organic natural language vocabulary statistics)...which matters because as you correctly note the big deal is if you can fit the histogram in the L2 cache as noted elsethread and this really matters if you go parallel where N CPUs*L2 caches can speed things up a lot -- until your histograms blow out CPU-private L2 cache sizes. https://github.com/c-blake/adix/blob/master/tests/wf.nim (or a port to your favorite lang instead of Nim) might make it easy to play with these ideas (and see at least one way to avoid almost all "allocation" - under some interpretations).

A better way to "scale up" is to concatenate various other things from Project Gutenberg: https://www.gutenberg.org/ At least then you have "organic" statistics on the hash.

> I don't think any language is going to offer that out of the box.

C# offers that out of the box, and the solution is much simpler there.

Pass StringComparer.OrdinalIgnoreCase or similar (InvariantCultureIgnoreCase, CurrentCultureIgnoreCase) to the constructor of the hash map, and the hash map will become case-agnostic. No need to transform strings.

The one possible issue is by not transforming the string you're going to run the possibly less efficient CI comparison a lot: because the corpus is text and duplicated, by my reckoning there are ~32000 unique "words" out of 82 million inout "words". That's a lot of conflicts.

Though the values should mostly be quite short, so a vectorised comparison might not even trigger as it wouldn't have the time to "stride": only one word of the top 10 even exceeds 4 letters ("shall", a hair under a million in my corpus).

The C# standard library will not run many case-insensitive comparisons. That comparison object doesn’t just compare two objects for equality, it also has another interface method which computes a hash of a single object.

Here’s implementation of the hash function used by that StringComparer.OrdinalIgnoreCase: https://source.dot.net/#System.Private.CoreLib/src/libraries... As you see, it has a fast path for ASCII-only input strings.

> The C# standard library will not run many case-insensitive comparisons. That comparison object doesn’t just compare two objects for equality, it also has another interface method which computes a hash of a single object.

Which doesn't matter because I'm talking about identical strings, so they will hash the same by definition, and they will have to be compared.

So the question is how fast the CI hash and equality operate compared to the CS ones.

And I asked about comparison because I assumed that would be the costlier of the two operations, relative to its CS brethren.

> how fast the CI hash and equality operate compared to the CS ones.

If the string is ASCII like in the OP’s use case, I think the difference is not huge.

CS comparison looks more optimized, they have an inner loop which compares 12 bytes as 3 64-bit values: https://source.dot.net/#System.Private.CoreLib/src/libraries...

CI comparer doesn’t do that, it loads individual UTF-16 elements: https://source.dot.net/#System.Private.CoreLib/src/libraries... But still, it’s very simple code which does sequential memory access.

> And I asked about comparison because I assumed that would be the costlier of the two operations, relative to its CS brethren.

I think the bottleneck is random memory loads from the hash table.

Hashing and comparison do sequential RAM access. The prefetcher in the CPU will do its job, you’ll get 2 memory loads every cycle, for short strings going to be extremely fast. If that hashtable doesn’t fit in L3 cache, the main memory latency is much slower than comparing strings of 10-20 characters, no matter case sensitive or not.

But all of those optimizations can also be done, and more efficiently, by transforming while reading. Even if they're as fast as they can be, they're not as fast as a memcmp. The C# approach isn't buying you any performance here.

Yeah, it’s possible to change case while loading, but I’m not sure that’s gonna be much faster.

But I’m sure it gonna be much harder.

For non-ASCII strings, converting case may change their length in bytes. You don’t even know in advance how much memory you need to transform 2GB of input text (or 1MB buffer if streaming). And if streaming, you need to be careful to keep code points together: with a naïve approach you gonna crash with a runtime exception when you split a single codepoint between chunks.

English words are 99.9% ASCII, but that remaining 0.1% like “naïve” is not. The C# standard library is doing the right thing for this use case. Specifically, for 99.9% of words the CI comparer will use the faster ASCII-only code to compare or hash, and only do the expensive shenanigans for small count of non-ASCII words.

Note how C# makes the implementation much simpler. A single parameter passed to the constructor of the Dictionary<string,Something> makes it implement case-insensitivity automagically.

> Probably some smart SIMD lowercase function could help here but I don't think any language is going to offer that out of the box.

No, but at least you have direct access to the intrinsics in C. To get vectorization in Go, you have to implement it in C and link that into your Go program.

> To get vectorization in Go, you have to implement it in C and link that into your Go program.

Go has an assembler which does not require implementing anything in C (though the assembler uses a more C-style syntax), nor critically does it require using CGo linkage. It's used to implement many hot paths in the stdlib.

Typically you would just implement vectorization in assembly in the Go case.

The file is only being read once according to the blog and then it is in memory. This isn't an I/O intensive application at all.

I have written a small script in python that does something similar. I have a word list with 1000 words and I check the presence of the words. Here is the thing. For every word I go through the entire file. So lets say I scan the file one thousand times. In fact I did something more complicated and ended up going 6000 times over the original file and yet it still took only three seconds. If all these scans had to reread the file it would take forever.

This sounds like a very inefficient method. The Python stdlib module 'collections' includes a Counter class which can do this for you. Then all you need to do is copy the dict key/item pair to a new one that match your word list.

he has figures for both cached and uncached performance

if all your scans had to reread the file from nvme it would take five times as long if we extrapolate from those figures

not forever

the optimized version does it byte by byte

Of course disk speed has caught up. Single core clock speed hasn't changed in over 10 years now? Disk now uses SSD and has been chugging along with improvements.

I'm curious what a multi thread(multi process for python due to GIL?) comparison would be. Obviously people aren't doing this by default though, so the author's point still stands.

> Single core clock speed hasn't changed in over 10 years now?

This is not true. I thought the same thing and you are right in regards to base line clock speed. But the performance is still increasing. I just got a new PC at work with a 2021 high-end CPU and it has 200% single core performance of the 2015 mid-range CPU in my private PC:

https://www.cpubenchmark.net/compare/4597vs2599/Intel-i9-129...

Well, CPU got a lot better at benchmarks, that is true. Caches got bigger, predictions got better. Specialized instructions were added. IPC improvement kinda slowed down after Sandy Bridge, at least for Intel.

Also, the comment you're quoting is talking about clock speed, and the link you provided literally shows the same base clock speed - 3.2 GHz. Intel progressively pushed turbo speed higher, but that the speed you could have achieved yourself by overclocking.

Does the CPU constantly hold the turbo speed under a single threaded workload?

Depends. The cpu attempts to hold the maximum possible speed on any cores that are in use.

On my water cooled and specifically tweaked desktop- yes. It’ll hold max boost indefinitely, even with all threads. (getting to about 80c after 10 mins). Single-thread max is faster, and it’ll hold that as well.

My laptop will pull power within 15 seconds and be down to base clocks in a couple mins. Unless I set it down outside and it’s very cold.

Most un-tweaked chips are going to be below 25 watts with a single core loaded, and lots of laptops can cool that without any problems.

It depends on motherboard and cooling. 6700K, for example, is constantly running at 4.2Ghz or 4.5Ghz (winter clocks). Constantly while thermals allow it... Non-overclocking motherboards allow it to boost for 2 minutes, after that, it's iffy.

Are you simply glossing over the fact that CPU 1 has a turbo of 5.2 Ghz and the other 3.6 Ghz ?

Yes, I did not go into details where the differences are coming from. The base clockspeeds are the same, which is obviously the number that GP noticed not changing over the last 10 years.

Other things changed. The turbo clockspeed is one of them.

Also, the the old one is 65W TDP and the new one is 241W TDP.

> Single core clock speed hasn't changed in over 10 years now?

Technically we have gone from 3.3gz- 3.9gz base frequency, 4.1-4.2 single core boosts, 4.7ghz heavy OC in Haswell to

4.3 and 3.0 base clock for efficiency/perf cores, with boosts to 5.4 ish, stable 5.8ghz all core frequency with heavy OC, and even pushing 6.something GHz single core with a good setup.

But then again, this is on the more extreme ends. Mainstream laptops have remained relatively stable.

re Python MP:

On my 12700k, I saw almost linear scaling (per core, not thread) with multiprocessing when loading stuff from the disk for ML applications and processing. This was with the datasets library.

It's not just about clock speed. CPI has been steadily improving across processor generations, even when the clock speed doesn't meaningfully change.

Sorry do you mean IPC (instructions per clock) or is there another term that I’m not aware of?

Cycles per instruction.

"Cycles per instruction" sounds more like a measurement of instruction latency rather than instruction throughput, and I don't think instruction latency has improved as much in the past decade as instruction throughput: the most significant microarchitecture trend has been toward wider CPUs with more execution ports, wider instruction decoders, and larger reorder buffers.

Yah, that was my thought exactly. Its probably not just the language choice, but the chosen algorithm. I expect a word frequency counting algorithm to run at close to the speed of sequential main memory read speeds. So the bottleneck in real situations is likely how fast the I/O subsystem can get it into RAM.

(a quick glance at the C version tells me all I need to know with the scanf, strdup, etc. This is sorta like those C vs Java benchmarks which boil down to the fact that the default (glibc/etc) C malloc() isn't really optimized for perf, and what your really bench marking is how terrible it is for frequent tiny allocations. I think there _IS_ a diffrence between the code written by someone who lives C in a system programming context, and people who dabble in it from a higher level language.).

PS: Say using a hash to track a words frequency, likely works OKish but the need to keep it small, while still avoiding collisions would cause problems if the algorithm were parallelized in a long running system (rather than batching, where you would just run each thread against its own copy of the frequency tables, and then merge them at the end). But I'm still fairly certain that "your doing it wrong" if the overall algorithm can't run at a significant fraction of main memory bandwidth.

Don't forget about naive implementations in languages like C++ where using cin/cout can cause your program to run slower than Python when doing file IO

Yeah I’ve worked on non trivial javascript codebases where allocations and gc mattered.

I’d like to hear more about this.

Not your OP, but I've got stories!

PhotoStructure is a non-trivial app written in TypeScript for both frontend and backend tasks.

Coming from Scala, I initially used a lot of Array.map, Array.foreach, and, to handle things like Some/None/Either:

function map<T,U>( maybe: <T|undefined>, f: (t:T) => U )

According to the V8 memory inspector, all those tiny fat-arrow functions can hammer the GC (presumably due to stack allocations and pulling in local context). Replacing large array iteration with for loops was a big win.

Also, handling large files with a streaming parser when possible, instead of reading them entirely into memory, another win.

Buffer concatenation may be faster by pushing read chunks onto an array, and joining the lot at the end, rather than incrementally appending with .concat.

When memoizing functions, if they themselves return functions, watch out for fat-arrows if you didn't need the caller's context (which may prevent gc from unexpectedly retained variables).

But the first step should always be to profile your app. You can't assert improvement without a baseline.

Reply on news.ycombinator.com