3 ms·

Do you have any recommendations on material to read on the subject of choosing optimal data structures / algorithms for a particular microarchitecture?

jandrewrogers 12y ago
Most of this follows from understanding (1) what kinds of things a modern core can do simultaneously and (2) how long it takes a core to do those things. On top of this, there are many additional rules regarding memory and cache access behavior. One of the most useful references for me is Agner Fog's instruction tables, which are updated regularly and you can download for free. They are genuinely an excellent resource. If you roughly understand how C or C++ is translated into machine instructions (not a big leap) then you can understand how bits of code will interact with the microarchitecture and what surrounding instructions can be executed concurrently in the same clock cycle. Basically you can have multiple 'threads' of execution running in a single core at the same time per clock cycle on a modern CPU. Good CPUs will try to do this for you but have limited ability to find this concurrency if you do not make it 'obvious' to the CPU with code idioms that make it impossible to miss. The amount of concurrency you can extract depends on the specific instructions your code is being translated into. Haswell has 4 ALUs per core but each ALU has different capabilities in terms of the subset of instructions it can execute; for example, some basic instructions can only be scheduled on two of the ALUs. http://agner.org/optimize/instruction_tables.pdf http://agner.org/optimize/instruction_tables.pdf Additionally, the architecture docs from CPU vendors is always insightful about the topology of the silicon, how everything is wired together, and the tradeoffs that are never mentioned in high-level marketing docs.

3 ms·

Do you have any recommendations on material to read on the subject of choosing optimal data structures / algorithms for a particular microarchitecture?

by hdevalence 12y ago

jandrewrogers 12y ago
Most of this follows from understanding (1) what kinds of things a modern core can do simultaneously and (2) how long it takes a core to do those things. On top of this, there are many additional rules regarding memory and cache access behavior. One of the most useful references for me is Agner Fog's instruction tables, which are updated regularly and you can download for free. They are genuinely an excellent resource. If you roughly understand how C or C++ is translated into machine instructions (not a big leap) then you can understand how bits of code will interact with the microarchitecture and what surrounding instructions can be executed concurrently in the same clock cycle. Basically you can have multiple 'threads' of execution running in a single core at the same time per clock cycle on a modern CPU. Good CPUs will try to do this for you but have limited ability to find this concurrency if you do not make it 'obvious' to the CPU with code idioms that make it impossible to miss. The amount of concurrency you can extract depends on the specific instructions your code is being translated into. Haswell has 4 ALUs per core but each ALU has different capabilities in terms of the subset of instructions it can execute; for example, some basic instructions can only be scheduled on two of the ALUs. http://agner.org/optimize/instruction_tables.pdf http://agner.org/optimize/instruction_tables.pdf Additionally, the architecture docs from CPU vendors is always insightful about the topology of the silicon, how everything is wired together, and the tradeoffs that are never mentioned in high-level marketing docs.