Algorithms for Modern Hardware
en.algorithmica.org
en.algorithmica.org
I'm starting a new chapter in my life and find it impossible to find a position that matches the collection of abilities, and the rare ones available responded with excuses ranging from too old to too mediocre. It is so bad that I'm now looking into switching to education, specifically gifted youngster where my knowledge and insights might rub off, guide, inspire and motivate. But even that is proving to be difficult.
Background: I'm an 70ies wizz-kid, Europe (NL), have an ATW-800, 9 years computer science education including hardware and software, through bad college advice was dis-advised to take the academic path, OS-design (linux, medical, HPC) in 90ies, small single-board computers in 00ies, fractal logic and calculating with structures in 10ies. My handicap: I'm too shy to stand in a spotlight or in front of a camera.
Located in .nl, the oil and gas industry surely has some work that benefits from these kinds of optimizations. ASML probably does enough simulation as well. I'd guess there are probably a handful of financial firms operating on these time scales. Outside of those, the various universities will have groups in this space. I doubt that's an inclusive list, just some areas where I'd expect to find heavily optimized code for specific hardware.
I used to learn clarinet for several years when I was yong. And I learned to code a simple CPU core with VHDL and FPGA when I was in college. And now I’m writing C# in healthcare industry. I may never write such kind of experience in my resume. But that helps me when I write projects on waveform editing, or to understand what is “parallel”.
So I separate my knowledge for two part. One is something I need to get a job, the other is something I interest in. Which may helps you in future or not. But you enjoy the time in it.
As for this book, it is useless especially when you are writing some stupid web server in a programming language like Java or C#. But just my interest about optimization.
I like the libraries that ship with toolchains for using this stuff. Anyone shipping silicon will have toolchain(s), either built in house or via consultancies.
Cutting cycles off integer divide is a waste of time for one application and a serious win if it's the integer divide the compiler injects into all applications.
Further from the machine you get language runtimes (e.g. libc, libm) then application libraries (blas, lapack, mpi) where it starts to merge with ML or HPC tooling.
So for instance, JavaScript interpreter in a browser is meh unless the person doing the work is hired by someone who needs their SPA to run faster.
So a mega corp looking for someone with a lot of experience making their software more efficient (think a large operator like MS Azure , Google, AWS), especially if there are supply chain issues making it hard or expensive to scale up their existing hardware. Also high frequency trading where nano seconds matter.
Or older legacy systems (folks still using mainframes?) where the costs of switching to a new system in compliance and interoperability mean they’re trying to wring ever cycle out of the existing system.
It's a _very_ wild guess but there might be opportunities in that general area for a software engineer that has deep practical knowledge around performance.
If you like this, you might also enjoy reading about optimisation tips by Mike Acton (data oriented programming,https://dataorientedprogramming.wordpress.com/tag/mike-acton... ) and Pierre Terdiman (on collision detection and physics optimizations, for example http://www.codercorner.com/blog/?p=1978)
We wrote some book (and SIGGRAPH courses) a few years ago, Multithreading for Visual Effects (http://www.multithreadingandvfx.org). The audience for this kind of books turned out to be pretty small.
[1] https://www.fevrierdorian.com/blog/post/2014/08/24/Multithre...
[2] https://www.fevrierdorian.com/blog/post/2014/08/24/Le-livre-...
His work stands at one extreme of how to architect a program, and is an extremely valuable reference, but he states his opinions as facts and that can be detrimental for the beginners he markets some of this material to.
Massive inefficiencies that could all be cut down to a unikernel running on the hypervisor directly. Whether that's a good idea or not in practice is a different story, but the performance improvements and energy savings are real.
That said, his issue is less on the strength of his convictions (which, as far as performance goes, are at least on-point), but rather his delivery. He has very little patience and is not looking to debate even when it might be beneficial to himself or to others.
And yet this is not the only lens through which to view software development. Correctness, expressiveness, portability, developer hours. There are many possible things to optimize for, and Casey barely gives these an ounce of weight compared to performance. The reason to target a program towards a platform with an operating system and a file system is because writing these things takes time, using them affords flexibility, and minimizes bugs from you're bespoke code. Casey does not view these as problems.
Casey writes near-C for bare metal, or when not using bare metal directly against the platform API and if you only learned from him that's the only approach you would view as valid. When talking about his approach to writing code he constantly derides, sometimes very harshly, those who would think about program architecture any other way.
I don't think the Rustacean evangelists' obsession with memory safety is the last word is software development, or Linus's assessment of languages other than C, or Jonathon Blow's and Casey's orientation with performance above all else. These are ideas, opinions, and there's some value in representing them as such.
But beyond that, IMO, it's fine to use higher-level constructs and target higher-level "platforms" (i.e. electron) to improve portability, developer productivity, etc. Even within that setting you can avoid doing things that pessimize your performance, and that's often enough for a massive improvement.
Dogma is the bane of software-development, be it abstraction at all cost, immutability at all cost, or performance at all cost, etc.
You seem very sure of that.
If I recall correctly, his statement can be more charitably summarised as noting that many of the functions of an OS or FS are not useful in the specific use case he had, which was running a single program serving a website. He would therefore prefer to not have the additional complexity, attack surface and performance overhead. I do not think that this is very controversial? There are of course trade-offs involved, and he did mention that he was planning on running Linux as a way to get device drivers and something booting with reasonable effort, at least initially.
edit: the Linux direct I/O feature that sort of obsoletes this use of raw devices was apparently developed in part by Oracle, which I guess might be interesting
The noise source described is that changes to the code typically alter alignments of code and/or data and that is often the cause of the performance difference measured, not the change to the algorithm. The reason this is noise is because unrelated changes to the code might make it change again.
IIRC, the speaker suggests improving compiler/profiler tools to randomise these alignments and benchmark many times.
Run it once, spot small speedup, call yourself a genius. Repeat.
I don't follow my own advice in much of the rest of the book, though (because I mostly focus on at least double-digit performance improvements).
At the same time, resetting the branch predictor AFAIK can only be done by powering the CPU off and on again.
I've also enjoyed your blog over the past few months, especially your post on the Eytzinger Layout [1], which we've implemented for TigerBeetle's new deterministic LSM-forest [2].
I can also understand your decision to write the examples in C++ given all the legacy code that's out there and given the easy access to std lib examples which are often not optimal. However, if I may make one suggestion it would be to take the extra time now to rewrite the examples in Zig — it's a clearer, simpler, newer language that makes sense for high performance coding for the next 10-20 years. It has a great approach to SIMD intrinsics and shares many of the same performance values as your book. For example, the std lib ships with SoA that can be used to generate SoA layouts at comptime.
As an orthogonal language, it's also brilliant for book examples, notably very readable, and also guaranteed to compile on the first attempt—it will make the examples more engaging and accessible, to bring the cool performance ideas across cleanly to your readers, without abstraction overhead, unnecessary complexity or usability issues.
From a community point of view, I think that this change would also find you a very engaged, supportive and concentrated systems community right from the get go.
On the other hand: How do you teach performance engineering? I learned it in the Demoscene, which was simply a competition. "I can do this effect in 2 cycles less". Not everybody will be a good performance engineer. Or should be! I feel like the people who do good in performance engineering will be competitive and find their win in whatever environment. Maybe that is a good context for the book: That's what people did to win!
However, for most business applications, it doesn’t bring much value. Modern hardware allows a lot of inneficiencies, and having some step few seconds faster or slower won’t matter much. In the last decade I spent maybe a day per year improving performance.
However, when I worked on some mini games recently performance was important since day 1. And I got a lot of joy from that process, programming was fun again!
Even the performance people can argue with me on here when I give them correct advice like that you might not want to try and use all CPU and memory just because they're there.
(For instance because your process is lower priority and so is only scheduled on E-cores and so the # CPUs number you see doesn't actually apply to you.)
Writing a type that automatically becomes SOA vs. AOS is relatively easy in D, almost impossible in C i.e. please stop writing "fast" code in C.
Several people have done the entity component system (ECS) thing.
There's a library (which I haven't tried out) for doing this in C++20: https://github.com/celtera/ahsohtoa
(The author is an HN regular, jcelerier.)
People who are going to be good at it are the kind of people who work that kind of stuff out themselves.
One note: You've got a few sections on B-Trees. BTrees may work well for on-disk data structures (eg databases, filesystems) but in my experience, skip lists work better in-memory; not to mention they're several times simpler to implement.
Eg: I got up to twice the performance moving from a b-tree to a skip list for a Rope structure, at half the code size. (And another 2x from embedding a gap buffer in each leaf):
[1] https://chromium.googlesource.com/v8/v8/+/refs/heads/chromiu...
I wish I had this text when I took my intro to computer hardware course!
I found one or two copy editing errors (missing words, a broken link) but those are easily fixed and I'll make an issue for them.
Great work overall.
How would you compare this to The Art of Writing Efficient Programs by Fedor Pikus? I am looking for a comprehensive guide.
The book I took was Tanenbaum's Structured Computer Organization. It was fantastic, as was Operating Systems. This class was indeed the "light comes on" as you go from gates to logic to CPU to signals to microcode to assembly and so on and so forth.
What Tanenbaums and this lack is a bit of history. We can learn a lot by the examples of the older computers, and what each generational "innovations" brought us.
I will get out of Russia in a few months and then figure out the best way to deliver a hard copy.
> So, don’t bother. If you want to support this book, just share the articles you like on link aggregators and social media and help fix typos — that would be enough.
This breaks my heart. Supporting justified sanctions is one thing. Witnessing how sanctions are affecting a civilian as an individual is another.
I hope those sanctions keep piling up (as they’re among the very few things that are actually capable of ending the war) so people like Sergey can once again live a normal life.