perf-ninja VS platform

Another good course with exercises: https://github.com/dendibakh/perf-ninja

Not DOD, but the Performance Ninja Course teaches about optimization, from which you can get better understanding why DOD is fast https://github.com/dendibakh/perf-ninja

For performance information, I like https://github.com/dendibakh/perf-ninja it is a free set of performance tuning exercises and he also has a free book on x86 which is very informative. and https://github.com/fenbf/AwesomePerfCpp in addition to this list, I also like "The Art of Writing Efficient Programs: An advanced programmer's guide to efficient hardware utilization and compiler optimizations using C++ examples" by Fedor Pikus (and also his other book on design patterns.)

There are a lot of issues here, so I can share some stuff about some of them and hope that some helpful internet commenters come along and point out where I have neglected important things.

A single modern CPU core is superscalar and has a deep instruction pipeline. With your help, it will decode and reorder many instructions and execute many instructions concurrently. Each of those instructions can operate on a lot of data.

As famous online controversial opinion haver Casey Muratori tells us, most software just sucks, like really really bad (e.g. commonly people will post hash table benchmarks of high-performance hash tables that do bulk inserts in ~100ns/op, but you can do <10ns/op easily if you try), and using SIMD instructions is table stakes for making good use of the machinery inside of a single CPU core. SIMD instructions are not just for math! They are tools for general purpose programming, and when your program has unpredictable branches in it, it is often a lot cheaper to compute both branches and have a data dependency than to have a branch. Instructions like pshufb or blendv or just using a dang lookup table can replace branches. Wojciech Muła's web site[0] is the best collection of notes about using SIMD instructions for general-purpose programming, but I have found many of the articles to be incomplete or incorrect, and I have not yet done anything to fix the issue. "Using SIMD" ends up meaning that you choose the low-level layout of your data to be more suitable to processing using the instructions available, not just replacing the "glue code" and leaving the data the same as it was.

Inside your single CPU core there is hardware for handling virtual -> physical address translation. This is a special cache called the translation lookaside buffer (TLB). Normally, chips other than recent Apple chips have a couple hundred entries of 1 4KiB page each in the TLB, and recent Apple chips have a couple hundred entries of 1 16KiB page each. Normal programs deal with a bit more than 1 meg of RAM today, and as a result they spend a huge portion of their execution time on TLB misses. You can fix this by using explicit huge pages on Linux. This feature nominally exists on Windows but is basically unusable for most programs because it requires the application to run as administrator and because the OS will never compact memory once it is fragmented (so the huge pages must be obtained at startup and never released, or they will disappear until you reboot). I have not tried it on Mac. As an example of a normal non-crazy program that is helped by larger pages, one person noted[1] that Linux builds 16% faster on 16K vs on 4K pages.

Inside your single CPU core is a small hierarchy of set-associative caches. With your help, it will have the data it needs in cache almost all the time! An obvious aspect of this is that when you need to work on some data repeatedly, if you have a choice, you should do it before you have worked on a bunch of other data and caused that earlier data to be evicted (that is, you can rearrange your work to avoid "capacity misses"). A less obvious aspect of this is that if you operate on data that is too-aligned, you will greatly reduce the effective size of your cache, because all the data you are using will go into the same tiny subset of your cache! Famous online good opinion haver Dan Luu wrote about this here[2]. The links included in that post are also good resources for the topics you've asked about.

When coordinating between multiple CPU cores, as noted in TFA, it is helpful to avoid false sharing[3]. People in industry have mostly found that it is helpful to avoid sharing *at all*, which is why they have work explicitly divided among cores and communicate over queues rather than dumping things into a concurrent hash map and hoping things work out. In general this is not a popular practice, and if you go online and post stuff like "Well, just don't allocate any memory after startup and don't pass any data between threads other than by using queues" you will lose imaginary internet points.

There are some incantations you may want to apply if you would like Linux to prioritize running your program, which are documented in the Red Hat Low Latency Performance Tuning guide[4] and Erik Rigtorp's web site[5].

Some other various resources are highload.fun[6], a web site where you can practice this sort of thing, a list of links associated with highload.fun[7], Sergey Slotin's excellent online book[8], and Dendi Bakh's online course[9] and blog[10].

> Off topic: What level of sophistication about modern CPUs is _good_ to have?

Probably none? These skills are basically unemployable as far as I can tell.

[0]: http://0x80.pl/articles/index.html

[1]: https://twitter.com/AtTheHackOfDawn/status/13338951151741870...

[2]: https://danluu.com/3c-conflict/

[3]: https://rigtorp.se/ringbuffer/

[4]: https://access.redhat.com/sites/default/files/attachments/20...

[5]: https://rigtorp.se/low-latency-guide/

[6]: https://highload.fun/

[7]: https://github.com/Highload-fun/platform/wiki

[8]: https://en.algorithmica.org/hpc/

[9]: https://github.com/dendibakh/perf-ninja

[10]: https://easyperf.net/notes/

Performance Engineering - [Performance Analysis and Tuning on Modern CPUs](https://www.amazon.co.uk/Performance-Analysis-Tuning-Modern-CPUs/dp/B08R6MTM7K) This book also has labs - https://github.com/dendibakh/perf-ninja

Denis Bakhvalov is in the process of making various labs you can benchmark and try to fix here: https://github.com/dendibakh/perf-ninja

The highload.fun wiki[0] links some resources. The intel optimization manual[1] is also useful.

These resources are mostly aimed at solving problems for which compilers are not very useful, so there are probably other resources that are a better fit.

[0]: https://github.com/Highload-fun/platform/wiki

[1]: https://www.intel.com/content/www/us/en/content-details/6714...

The web site containing the article has a collection of other articles about this sort of thing. You can also read about this in some parts of Algorithms for Modern Hardware[0]. highload.fun includes some other links about this stuff[1]. In general there isn't a great guide and it's best to get your hands dirty. highload.fun happens to be a good place to do that :)

[0]: https://en.algorithmica.org/hpc/algorithms/prefix/

[1]: https://github.com/Highload-fun/platform/wiki

There are a lot of issues here, so I can share some stuff about some of them and hope that some helpful internet commenters come along and point out where I have neglected important things.

A single modern CPU core is superscalar and has a deep instruction pipeline. With your help, it will decode and reorder many instructions and execute many instructions concurrently. Each of those instructions can operate on a lot of data.

As famous online controversial opinion haver Casey Muratori tells us, most software just sucks, like really really bad (e.g. commonly people will post hash table benchmarks of high-performance hash tables that do bulk inserts in ~100ns/op, but you can do <10ns/op easily if you try), and using SIMD instructions is table stakes for making good use of the machinery inside of a single CPU core. SIMD instructions are not just for math! They are tools for general purpose programming, and when your program has unpredictable branches in it, it is often a lot cheaper to compute both branches and have a data dependency than to have a branch. Instructions like pshufb or blendv or just using a dang lookup table can replace branches. Wojciech Muła's web site[0] is the best collection of notes about using SIMD instructions for general-purpose programming, but I have found many of the articles to be incomplete or incorrect, and I have not yet done anything to fix the issue. "Using SIMD" ends up meaning that you choose the low-level layout of your data to be more suitable to processing using the instructions available, not just replacing the "glue code" and leaving the data the same as it was.

Inside your single CPU core there is hardware for handling virtual -> physical address translation. This is a special cache called the translation lookaside buffer (TLB). Normally, chips other than recent Apple chips have a couple hundred entries of 1 4KiB page each in the TLB, and recent Apple chips have a couple hundred entries of 1 16KiB page each. Normal programs deal with a bit more than 1 meg of RAM today, and as a result they spend a huge portion of their execution time on TLB misses. You can fix this by using explicit huge pages on Linux. This feature nominally exists on Windows but is basically unusable for most programs because it requires the application to run as administrator and because the OS will never compact memory once it is fragmented (so the huge pages must be obtained at startup and never released, or they will disappear until you reboot). I have not tried it on Mac. As an example of a normal non-crazy program that is helped by larger pages, one person noted[1] that Linux builds 16% faster on 16K vs on 4K pages.

Inside your single CPU core is a small hierarchy of set-associative caches. With your help, it will have the data it needs in cache almost all the time! An obvious aspect of this is that when you need to work on some data repeatedly, if you have a choice, you should do it before you have worked on a bunch of other data and caused that earlier data to be evicted (that is, you can rearrange your work to avoid "capacity misses"). A less obvious aspect of this is that if you operate on data that is too-aligned, you will greatly reduce the effective size of your cache, because all the data you are using will go into the same tiny subset of your cache! Famous online good opinion haver Dan Luu wrote about this here[2]. The links included in that post are also good resources for the topics you've asked about.

When coordinating between multiple CPU cores, as noted in TFA, it is helpful to avoid false sharing[3]. People in industry have mostly found that it is helpful to avoid sharing *at all*, which is why they have work explicitly divided among cores and communicate over queues rather than dumping things into a concurrent hash map and hoping things work out. In general this is not a popular practice, and if you go online and post stuff like "Well, just don't allocate any memory after startup and don't pass any data between threads other than by using queues" you will lose imaginary internet points.

There are some incantations you may want to apply if you would like Linux to prioritize running your program, which are documented in the Red Hat Low Latency Performance Tuning guide[4] and Erik Rigtorp's web site[5].

Some other various resources are highload.fun[6], a web site where you can practice this sort of thing, a list of links associated with highload.fun[7], Sergey Slotin's excellent online book[8], and Dendi Bakh's online course[9] and blog[10].

> Off topic: What level of sophistication about modern CPUs is _good_ to have?

Probably none? These skills are basically unemployable as far as I can tell.

[0]: http://0x80.pl/articles/index.html

[1]: https://twitter.com/AtTheHackOfDawn/status/13338951151741870...

[2]: https://danluu.com/3c-conflict/

[3]: https://rigtorp.se/ringbuffer/

[4]: https://access.redhat.com/sites/default/files/attachments/20...

[5]: https://rigtorp.se/low-latency-guide/

[6]: https://highload.fun/

[7]: https://github.com/Highload-fun/platform/wiki

[8]: https://en.algorithmica.org/hpc/

[9]: https://github.com/dendibakh/perf-ninja

[10]: https://easyperf.net/notes/