* Rough latency timings
* Caching
* Prefetching
* Sequential vs. random access
* N-dimensional layouts (row/column major and arbitrarily strided)
* Design of cache-oblivious algorithms
* SIMD-able access patterns
* False sharing
* Instruction cache & code size
* Branch prediction and speculative execution
I'd be curious to hear what else folks would put on (or remove from) this list.
Let's say someone is building a micro-service in C#.Net. Why would any of this stuff matter to them? The company cares about features and moving forward quickly.
It's rather like forcing all your developers to be able to code every type of different sorting algorithm when they are only ever going to call "mylist.Sort()" in reality.
This seems like another of those occasions when HN misjudges what the vast reality of practical day to day software creation looks like. Most engineers are not writing low-level code, they are not working on hardware directly, and they don't need to know exactly how RAM works at the transistor level.
I'm not saying it's not interesting, but it's not going to change how I write my for-loops and if statements or make calls to BigTable, etc.
You might be surprised at how much changing your for loops can be when accessing matrix data.
for(int i=0; i<10000; i++){
for(int j=0; j<10000; j++){
blah[j][i] = whatever(); // Column oriented is very slow.
}
}
for(int j=0; j<10000; j++){
for(int i=0; i<10000; i++){ // Very fast: We move row-wise now. With luck, this is SIMD-vectorized by your compiler.
blah[j][i] = whatever();
}
}
-----------
If someone is writing high performance code, the #1 goal is to be able to read your profiler's output. If you can't read what the profiler says (cache hits, TLB hits, memory stalls, etc. etc.) then you can't make sense of the data.
The PDF goes deeper than I'd personally go, but there's some concepts here that are absolutely necessary if you actually want to understand what a decent profiler gives you these days.
Also, you have to understand that saving 1 or 2 milliseconds isn't important when compared to getting software built faster. For the typical use case, optimizing a for-loop like this for in-memory data isn't going to change the total performance of your program by even 0.5%. This is what so many people just don't understand. For modern web based applications, 99.9% of the time spent is doing IO, either hard-drive, data storage, or across the network. Optimizing those calls is FAR more important, than wasting time trying to save 1 millisecond in a for-loop which is iterating over 100 in-memory objects.
This is where the understanding that the practical reality of building software for a real business is very different to theoretical examples drummed up by computer scientists on discussion boards.
I see so many engineers trying to make their in-memory code faster by parallizing it, saving (if they're lucky) 1 or 2 milliseconds, but making their code far less maintainable and potentially introducing bugs, while the users wouldn't notice any practical difference in the app. Meanwhile, the app really does feel slow, because some numb-nuts made a call to some api and blocked the ui thread.
Our hadoop cluster is relatively small at 5PB right now, but I would be impressed indeed if you were processing PB of data on a smallish AWS instance.
If you were considering using Hadoop for work that can be processed on a "smallish instance" then I'd suggest you maybe don't really understand big-data or the normal workloads for which Hadoop is intended. For example, we run ML models on our Hadoop cluster which take hours to run distributed over around 100 nodes. Let me know when this can be done on a "smallish instance."
In general, you optimize software by starting from the slowest things first, and then working your way to the faster things when you run out of things to optimize. It seems like your problems are I/O bound, and therefore the bulk of optimizations can be made by simply optimizing your I/O (either through async calls, or better understanding of what the frameworks are actually doing, etc. etc.).
And that makes sense for sure.
The thing is: the next level of optimization is not CPU-optimization, but instead memory optimization. In fact, all CPU-based optimization starts at the Main-memory level. Why?
Because memory is slower than virtually everything inside of the main CPU Core.
Which means, memory-level optimization is a far more important skill than any other CPU-based optimization technique. Modern CPU Cores operate at 4GHz easily, but RAM only responds every 100ns on server systems (that's 400 CPU-cycles of RAM Latency!)
-----------
In effect, if there's one low-level optimization any higher-level programmer should know about, it is RAM optimization. Sure, there are CPU-optimizations (SIMD registers, L1 vs L2 cache, and more), but RAM access itself is hundreds of times slower than CPU-speeds and needs to be optimized before lower-level optimizations are sought.
Once RAM access are fully optimized, then you can finally reach for the CPU-core optimizations. Instruction-level parallelism, or SIMD Registers, or what-not.
RAM is the next slowest part of your system after I/O. As such, optimizing RAM access is the most logical next step forward when your programs are running poorly.
Why not? I work with the scripting languages only and regularly hit this scenario so I won't say this is completely useless.
When you analyze a few hundred 50GB files for specific patterns, you have to go line by line in those cases shaving off milliseconds, optimizing how data should be accessed and optimized becomes valuable.
There are tens of thousands teams and thousands of tournaments and his code was taking two days to precalculate the results for every team.
Written with minimal understanding of how slow the memory is, the new code takes less than a minute. There was no point of optimizing it further, the algorithmic changes were enough.
1. L1 cache lines are 64-bytes long. By fetching column-wise, you are wasting the bandwidth between L1 and main-memory. L1 cache will always fetch 64-bytes. By moving "with" the cache, you allow the L1 --> Main Memory data-transfers to be far more efficient.
2. Virtual Memory is translated by the TLB before it returns the actual value. Moving within a 4kB page is more efficient than moving across pages.
The non-reason:
* Hardware prefetcher probably works, even on column-oriented data.
All of these reasons hold even if the SIMD-optimizer fails. If the SIMD-optimizer is actually working, you'll more efficiently load/store to L1 cache. But this is likely a memory-bound problem and optimizing the core isn't as important.
% cat t.c
#include <sys/time.h>
#include <sys/resource.h>
#include <stdio.h>
double get_time()
{
struct timeval t;
struct timezone tzp;
gettimeofday(&t, &tzp);
return t.tv_sec + t.tv_usec*1e-6;
}
int blah[SIZE][SIZE];
int whatever() { static int i=0; return ++i; }
int main()
{
double t0 = get_time();
for(int i=0; i<SIZE; i++){
for(int j=0; j<SIZE; j++){
blah[j][i] = whatever(); // Column oriented is very slow.
}
}
double t1 = get_time();
for(int j=0; j<SIZE; j++){
for(int i=0; i<SIZE; i++){ // Very fast: We move row-wise now. With luck, this is SIMD-vectorized by your compiler.
blah[j][i] = whatever();
}
}
double t2 = get_time();
printf("SIZE=%5d dt1=%4.3e dt2=%4.3e\n",SIZE,t1-t0,t2-t1);
return 0;
}
% for (( i=1; i<100000 ; i*=10 )) do gcc -DSIZE=$i -O t.c; ./a.out; done
SIZE= 1 dt1=4.179e-04 dt2=0.000e+00
SIZE= 10 dt1=5.190e-04 dt2=0.000e+00
SIZE= 100 dt1=5.062e-04 dt2=9.537e-07
SIZE= 1000 dt1=4.014e-03 dt2=1.490e-04
SIZE=10000 dt1=1.347e+00 dt2=4.349e-02
SIMD only really makes a difference at the L1 or L2 cache levels. Its a fancy micro-optimization that compilers do and can improve code speed in those cases...
But the "big" change, going from column-wise traversal into row-wise traversal, is the huge memory optimization that programmers should know about. It just so happens that SIMD-optimizations are also easier for compilers to figure out on row-wise traversal, so you get SIMD-optimization "for free" in many cases.
My list presupposes you've hit a wall and need the best performance you can get. That's not always the case, but I certainly wouldn't say that these optimizations don't make a difference in the "real world of softare."
False sharing alone can be the difference between a 16x parallelization speedup and a 1000x+ slowdown over the naive serial algorithm. 16x can be the difference between actionable results tomorrow or three weeks from today... and if you didn't know about it, the 1000x+ slowdown would be otherwise inscrutable.
I don't know exactly what that number is going to be, but I do know it is going to be a lot less than 100%.
For example, an O(n^2) algorithm can often beat an O(n) one when n is "small". How do you get that "experienced" feel for which to choose when you're designing your program?
This is even important for people doing REST APIs, Web Services and Microservices. Milliseconds matter when the load gets beyond a certain point and your system ends up full of stragglers. How do you get that "experienced" feel for where that point might be and how far you can push a particular architecture without investing in a major rework?
The effect of tail latency on most web servers might surprise you:
http://latencytipoftheday.blogspot.com/
http://latencytipoftheday.blogspot.com/2014/06/latencytipoft...
TL;DR: most of your visitors will experience the bottom 1% of your performance curve on every page load.
Back when I started, both the BASIC and Common Lisp camps had heuristics on helping the compiler generate more efficient code. The reasons are similar to today: increase throughput for scaling or customer experience while simultaneously reducing what you spend on hardware and/or electricity. Lean, easy-to-manage setups can also sometimes let you afford extra personnel to build stuff faster.
There's definitely a cut-off where micro-optimizations wouldn't be necessary. A lot of efficiency gains are simple, though. Just gotta consistently use what you learn.
"web applications/web sites/microservices"
The world is bigger than you think it is. There could be more code in making a single AAA videogame than in the entire Amazon infrastructure.
I'd add "Virtual Memory" to that list. In particular, the TLB cache, memory pages (4kB, 2MB "Large Pages", 2GB "Huge Pages).
Although x86 specific, I'd also add x86-64 has 48-bit physical pointers: the top 16-bits are basically ignored by the current virtual memory system. I dunno if the whole Page Directory / Directory Tables / etc. etc. needs to be fully explained, but programmers should have an overall good idea what they are.
There's lots of things to do with Virtual Memory. And anyone who actually reads profiler data needs to understand what the heck that TLB Cache Hits performance counter means.
> * False sharing
More specifically the MESI Protocol (although that's an abstraction), and cache lines should be taught. False Sharing comes as an understanding after you understand those other two concepts.
A CPU Core holds a cache line in Exclusive state so that it can write to it. A 2nd CPU Core attempts to gain access, but it cannot until the 1st core releases control (by writing data back to memory and setting the line to the Invalid state).
The knowledge of the 64-byte cache line is more general than just false sharing: it helps understand why alignment can be an issue (a load/store across a 64-byte cache line would require 2-reads by the memory controller), etc. etc.
and "the top 16-bits are basically ignored" is a funny way to spell "general protection exception on linear memory reference in non-canonical space" but sure, guess we're just handwaving here
Because no CPU actually implements MESI. All CPUs implement more complicated stuff, like MESIF / MOESI. Instead of going into MESIF (which only Intel CPUs implement) or MOESI (only older AMD CPUs implement), lets just stick with the textbook MESI.
Which is "wrong", but its "correct enough" to explain the concept. That's what I mean by an abstraction, no CPU today actually does MESI, its simply a concept to introduce to solidify the student's understanding of cache coherency. Its close enough to reality without getting into the tricky CPU-specific details of the real world.
> guess we're just handwaving
I mean, you have to set those bits back to 0 before using them as a pointer.
But the system will literally never use those top 16-bits for anything. So some highly optimized code stores data in those top 16-bits and then zeros them out before using. IIRC, Lisp machines and various interpreters.
I think its easier to explain cache-coherence through MESI, rather than to abstractly just say "Caches are coherent". At least personally, I didn't understand cache coherence until I sat down and really tried to understand MESI.
I guess other people learn differently than I do, but I always view cache-coherence through the MESI lens.
Could you elaborate on this? Which pointers exactly?
There's an extension to use 55-bits or 56-bits... I forget exactly. But I don't think its actually been implemented yet on any CPU yet.
EDIT: It was Intel's 57-bit memory: https://en.wikipedia.org/wiki/Intel_5-level_paging . Yeah, I knew it was a weird number. But I guessed wrong earlier.
With 48 bits you can still address 256TB of memory. I guessing that from a practical and financial point of view it probably made little sense for vendors to build a CPU that enabled addressing the full 64 bits. At least for now.