What scientists must know about hardware to write fast code (2020) | Hacker News Reader

What scientists must know about hardware to write fast code (2020)

biojulia.net

109 pointsspekcular30 comments

That site now directs to malware, but the article is readable here:

http://web.archive.org/web/20221208105716/https://biojulia.n...

Good piece, goes into such depth that probably not all scientists must know all of this :)

That said, my own experience of noticing what people's machines are wasting time on around me is very different.

For scientists at firms (outside of academia) a major bottleneck is downloading, decompressing and shuffling data around. Unfortunately the lessons in the piece are in fact detrimental to this workload: 1. decompression is usually not faster than 500MB/s, which is much slower than SSD or network, but I still see compression everywhere with the idea that "cpu is faster". 2. Standard tools for downloading data, like awscli, are crazy slow compared to the actual ability of the network cards that are attached to the machines we (in big firms) use in the cloud. Specifically awscli caps at about 250MB/s no matter the configuration or network bandwidth, and people think it's normal because "network io is slow". (this of course doesn't apply to scientists who work out of the cloud, with much lower download speeds)

None of this contradicts anything in the piece. It's that the units of work for different sectors are different. Whereas a geoscientist working on modeling the ocean has bottlenecks in computation, scientists at firms often have them in data.

> 1. decompression is usually not faster than 500MB/s, which is much slower than SSD or network,

There are some, but you have to select the right one. https://github.com/inikep/lzbench#benchmarks

I think the distinction is in systems programming versus system programming.

Systems programming involves multiple systems with many components. It's not uncommon to find you simply can't make a solution work any better than it's designed, and you need to develop brand new solutions to problems (which makes the system even bigger).

System programming is simpler because it's one system and one or two codebases. It can still be quite complex, but you can often just optimize the one solution rather than having to come up with new ones.

If you’re working with time series data and using a vectorized algorithm implemented with SIMD instructions you can achieve decompression speeds approaching 15 GB/s [1].

Anecdotally when working with biological signals at my day job, compression is a massive win and an absolute no brainer tradeoff when shuffling data across the network or even just storing in memory.

That said, I think your first point is still reasonable for certain types of data and compression algorithms.

[1] https://github.com/lemire/SIMDCompressionAndIntersection

Hey all, author here. That link is to an older version of the post - an updated version can be found here: https://viralinstruction.com/posts/hardware/

@dang can it be replaced?

i can read >>that link<< -but, the updated version is inaccessable to me, you may want to fix that if you want everybody to be able to read what you have published.

Excellent write up, thank you!

It starts kind of slow, but then somehow morphs into effortlessly explaining advanced topics. I knew bits and pieces of this before, but I found information that was genuinely new to me, like this gem:

”Going back to the original example, that is why the perfectly predicted copy_odds_branches! performs better than code_odds_branchless!. Even though the latter has fewer instructions, it has a memory dependency: The index of dst where the odd number gets stored to depends on the last loop iteration. So fewer instructions can be executed at a time compared to the former function, where the branch predictor predicts several iterations ahead and allow for the parallel computation of multiple iterations.”

CSS/layout note: the floating table of contents to the right covers part of the main body column (in Safari, Firefox, and Chrome here), making this document illegible unless I use a narrow enough browser window that the table of contents goes away entirely.

Also, this document doesn’t load whatsoever when Javascript is disabled.

Thanks for the heads-up. I've filed a bug report for the table of content issue. Wrt. Javascript, I think the presentation style of the notebook is worth requiring Javascript.

Curious, looks like you're assuming that most scientists are using laptops rather than desktops ? Or are the researchers that I know atypical ?

Such a great and condensed write up... and then at the last moment it looks like one is finally going to learn about (dedicated) GPU programming, and... nope ! :P

Thanks! Well every one of my colleagues use laptops - but I think that detail should not matter for the content of the blog.

Seems like a good article, thank you! It's like a long sequel to the performance tips section of the Julia documentation. Only read a bit so far, found this error:

> 0.001321 seconds

> about 13 miliseconds

Uh no, that's about 1.3 milliseconds.

> Both your operating system and your programming language will make use of caches, however, sometimes it is necessary to manually buffer your files.

Hmmm? This part stands out. It sounds like the author is here. Can you help me understand this advice? It feels like it should have a million caveats and not be general advice. Often times memory mapping the file is going to be better. Unless you’re an expert you’re probably not going to do better than the page cache.

Using mmap() is popular because it is easy despite its many sharp edges, but outside a limited number of access patterns and hardware setups it is often quite slow because the page cache behavior is poor for many use cases. Manually buffering is often simpler, and with better performance, than trying to make the page cache perform well. Furthermore, mmap() doesn't work for large storage volumes generally, so you might find yourself doing your own buffering regardless.

If you have a relatively simple access pattern, and most applications do, then you don't need to be a database kernel engineer to design a trivial manual buffering system that can significantly outperform mmap(). It is a handful of lines of code in most languages.

Hmmm… this does not match my experience at all. Some user space buffering helps but that’s just because it’s easier to write your application logic (ie read 4 bytes, read 17 bytes, read 46kb). I have not heard the advice to layer another layer of buffer on top of if that. The reason is that it lets you write such code efficiently without paying the syscall overhead. These buffers are very stupid and io_uring or mmap (with a read ahead option) will perform better for larger files because there’s either no extra memory copy or the cost is hidden better. I’ve seen people struggle and fail to outperform the page cache. The only time I’ve beaten it is when it was caching the wrong thing (it was caching compressed and uncompressed pages via fuse so telling it to forget about the compressed pages after decompression eased memory pressure).

I was assuming a zero-copy manual buffer for read-ahead/write-behind. There is really no way mmap() could be faster since it is required to do more. The tradeoff is that you don't have a linear address space (a non-issue for most apps) but you get much smarter scheduling and cache replacement behavior that results in higher effective throughput. You can't get there with madvise(); as the name suggests the kernel can and frequently does ignore very sensible requests to modify page cache behavior -- pathologically poor read-ahead behavior is what originally encouraged me to figure out kernel bypass. It is pretty easy to drive a gang of NVMe devices at their theoretical limits with a manual buffer if your access patterns are predictably simple, which is useful when slinging a lot of data around even if you aren't doing anything clever.

The caveat is that even though the code to do it is simple, you still have to understand how Linux storage and APIs work. As you correctly observe, naive attempts that don't understand the fundamentals can be significantly worse than just mmap()-ing things, like never actually removing the page cache from your I/O path (common mistake).

Sorry. I think I’m a little thick. How are you bypassing the page cache?

Most common operating systems provide a facility to directly DMA disk pages into a user space buffer (and vice versa) without involving the page cache. On Linux, for example, this is what the O_DIRECT flag is for. It is similar to mmap() but with different rules; you lose the page table magic but gain explicit control the I/O behavior. There is nothing faster if you know how to wield it. Operating systems add this feature to support database engines but it isn't the only use case.

Because a page cache is expected to support all possible processes, it can neither overfit simple access pattern cases, because then it would offer poor performance for common cases that are more complex, and it will never have enough context to offer excellent performance for complex access patterns because doing so would reduce performance for many common simple cases. Real page caches try to straddle both worlds; it is better to be mediocre for simple and complex cases than to be excellent at only simple or only complex cases. Bypassing the page cache allows processes to design their own page caches that are highly optimized for their specific requirements, should it be worthwhile to do so.

A reason people might not want to do this is that the APIs are operating system specific.

Following the GH issue clearly explains the reference to a specific Julia implementation that resulted in poor performance of byte-at-a-time I/O.

The advice is quite broad and simplified, but I think the one caveat of writing "sometimes" is enough.

What I mean is that, although the operating system caches files in RAM, and some (but not all) languages like Python and Julia implements a cache in its abstraction over file reading, these caches are not as fast as simply loading a bunch of bytes into an array and reading from the array, because they are hidden behind an abstracted IO, and the abstraction is not zero-overhead.

The difference is especially noticable when you read byte-by-byte, as in the issue I linked to in the text. For example, if you try to implement parsing with a finite state machine reading one byte at a time, you basically need to access memory directly without any overhead.

It's possible there are IO abstractions where reading from a "file" in RAM is just as fast as loading a byte from memory, but I don't know of any such abstractions.

If I'm reading the table under "fast instruction, slow instruction" correctly, float multiplication has half the reciprocal throughput of integer multiplication, which means float multiplication has twice the throughput.

So, if I want to multiply a bunch of integers together, does this mean it's faster for me to represent them as floats (even though I don't need the additional precision)?

It depends on the processor, but yes in some cases using floats would be faster for this reason. Please note that floats don't have "additional" precision, they have a different structure that means they can express a different set of numbers. Integers should in general always be preferred when the data you deal with is of integral nature.

Even if your CPU can do some instructions faster with floats it is generally not the kind of optimization you would want to make. You would end up making things more complicated for little practical benefit.

Funny thing by the way, integer arithmetic units are generally cheaper to make than float units, but most multiply/division heavy code is floating point, so CPU makers prioritise the floating point units.

Thank you for the detailed explanation.

This is a lot of words to essentially repeat the "Latency Numbers every developer should know" by Peter Norvig:

https://gist.github.com/jboner/2841832

EDIT: That was an uncharitable take and I apologize to the author.

What about the parts about SIMD, struct of arrays, the heap vs the stack, multithreading, the short introduction to assembly code, inlining and unrolling, and the actual explanations of what all those phrases in the doc you linked means?

You know, 80% of the content of my blog post?

Great article. Ignore the (if I may, arrogant) lossy compression attempted above.

I agree - this post is really useful, thanks for writing it!

What? That post has none of the information in this post. Did you even read it?

Reply on news.ycombinator.com