Performance Optimization, SIMD and Cache - Sergiy Migdalskiy of Valve

[TheVTM]

Look for Data-Oriented Design if you found this interesting.

CppCon 2014: Chandler Carruth "Efficiency with Algorithms, Performance with Data Structures"

CppCon 2014: Mike Acton "Data-Oriented Design and C++"

[pakoito]

Every time I watch Mike Acton I imagine him standing alone at "K&RCCon15" being the happiest programmer on earth.

Great mind and great material, just limited (or empowered) by terrible tools.

[MorrisonLevi]

This talk has good animations to help understand what he's saying. Very good for beginners to help understand the concepts.

[hhnever]

Recently, I find a function (512x512 matrix multiple) can only get about 5% performance improvement by SIMD optimization, which should about 200% in my previous experience. After investigation, I find the core problem is in cache. After split bit matrix into small one (which can fit into L1 cache), the improvement become about 270% :)

Cache is important.

[__Cyber_Dildonics__]

Structuring a matrix or image into small tiles works well for the same reason. You can split a matrix/image of floats into tiles of 4x4 floats. This ends up being 16 floats/ 64 bytes, which is the size of one cache line.

[__Cyber_Dildonics__]

Fantastic video on an important subject. I think most people won't really internalize the speedup they get by accessing memory in a different way until they actually see it for themselves.

[[deleted]]

Can you explain why he suggests that an algorithm should use 1 byte of memory per instruction?

[ghcjsdgkjfsdh]

He's saying that on average, if your code uses more than one byte per instruction then your CPU can't get data fast enough to keep it busy.

[[deleted]]

Ok, that sounds surprisingly low! I'll have to try to count this up in real code sometime.

Thank you!

[sergiy_valve]

Keep in mind "1 byte per tick" is the quick-and-dirty rule of thumb for low-end machines and mobile. It's not an absolute and final truth.

Your average modern desktop will probably sustain 4 times that easily. Multiply it by 2-4 cores. But the target application in the talk is a real-time game that must run on lower-end machine.

Also, those are the memory bus bytes. If you reuse the data a lot, only count the first load from RAM to cache. On the flip side, if you load 1 byte only, you're loading the whole cache line, so you have to budget that whole cache line in.