code::dive conference 2014 - Scott Meyers: Cpu Caches and Why You Care

[@inunekonanita]

Here from Unity Learn understanding data oriented design. So glad they shared this link. Thank you for all the amazing things that I learned today!

[@TheLeontheking]

Really enjoyable to have a talk where one is not constantly reminded of "don't do premature optimization, focus on readability first, etc."

[@dagoberttrump9290]

Premature optimization might be bad but premature pessimization is worse..

[@ultranewbie]

@@dagoberttrump9290 very true, currently going through this

[@tah3460]

Kudos to camera man and editor for a presentation which has all slides and laser points in it! Finally someone who managed to do this properly!

[@SqueakyNeb]

Yeah this is brilliantly done.

[@ArthurSchoppenweghauer]

"That's what we like to see: 16 times as much CPU power and we're getting results 10% faster than before. Outstanding." LMAO

[@TheBlenderblob]

he has a c++ haircut

[@stephenkamenar]

lmao lololololololololololololololololololololololololololololololololololololololololololololololololololololololololololololololololololololololololololo

[@lilsteppawitda9]

real asf

[@atabac]

its a row traversal cut😂

[@robertvalentic4939]

xD!!

[@user-iz2cygh56]

I think this is a wig

[@andreitolkachev8295]

Absolutely fantastic presentation! I work on embedded satellite systems with very stringent requirements and we have managed to improve performance by a lot with just advice from this video. Brilliant

[@EngSamieh]

Thanks Nokia for your generous sharing.

[@smileysmile85]

this talk is amazing, I'm familiar with all these things but the way he explains is amazingly simple and clear

[@codeinclined]

Fantastic talk. It's really made a lot of things I've heard elsewhere make sense for the first time

[@dipavan]

Absolutely fascinating. Helped me to connect the dots and fill in the gaps. I understand the relationship between hardware and software much better now.

[@AaronOmary]

hehe, connect the DOTS

[@siwenzhang]

This talk is miraculous !

[@probono2876]

Thank you for the outstanding presentation.

[@1904home]

This was awesome. Every embedded systems developer needs to hear this. Yes you can have low level kernel guys enable cache on an SoC and get things setup for you but using the cache (best practices) to its fullest potential in the application space is a whole fun nother.

[@ante4933]

A lot covered , perfect point for directions on where to put your focus for optimization.

[@antonfernando8409]

Great talk and learned something new, and first time seen Scott, what a brilliant mind.

[@afterbunny257]

Anybody can cover the timestamps I lost befor 40:05? 40:05 False sharing on static and global data 41:15 False sharing on heap allocated data 41:43 False sharing on automatic variables and local variables 43:35 Summery 44:07 Performance gain on no-branching code 45:46 Data-oriented programming 49:47 Avoid iteration over heterogeneous sequences with virtual calls 52:58 Inlining 53:55 Take advantage of PGO and WPO 56:45 Strided access of matrix and cache associativity

[@emilflater5399]

Scott as always in shape. Thanks much for amazing presentation!

[@glizzdawiz]

Most developers know nothing about this. Spread this video.

[@captainzoltan7737]

It's because they GENERALLY don't need to. Sure if your writing an engine for the next triple a game , an operating system, the next Photoshop, or embedded systems yeah this stuff is pretty important . But the vast majority of developers work on stuff like websites and enterprise software that doesn't need low level expertise to run your machine to the wire. Sure certain parts of that often require optimisation, but the bulk of development work won't require it. Its why the most popular/used programming languages as of writing this are python, and JavaScript, and java . They are slow(java less so), resource inefficient languages compared to c, c++ and rust but they are good enough to get the job done alot of the time and are far easier to write in. Isn't a bash though, I just like learning this stuff because I find it interesting tbh

[@Ehal256]

​​@@captainzoltan7737 that's why software developers can't really call themselves engineers. Most of them want to ignore the physical reality of what they're doing, and users suffer for it.

[@neosapien247]

He really took that age joke to heart

[@pondlife9931]

Wonderful information! This man is so exacting that I pity any restaurant server who processes his order incorrectly.

[@PROMuffy]

That joke at the end... :o

[@benk6192]

Amazing presentation

[@naknuknik]

Very informative snd a good starting point ( with reference material for further learning included )

[@malikaremu2344]

I love this video so much

[@fkaanoz]

incredible talk!

[@nirmalyasengupta6883]

Always, some thing more to learn from Scott Meyers! Thanks!

[@ilovetobloved]

Amazing and brilliant lesson. thanks for wonderful session.

[@gat0tsu]

wow these lectures are really good

[@ekrem_dincel]

26:15 what the person said?

[@FerhatErata]

Very good structured presentation

[@seopi]

크.. 배우고갑니다.. 운영체제와 하드웨어관련된 내용은 왜이리 재밌는지..

[@wessonwang5017]

great! got deeper understanding of cpu.

[@IndianNatiional]

Captivating and no doubt very informative

[@criticalposts3143]

I only traverse matrices in a Hilbert curve

[@PIX_BMS]

Love his serial killer hair.

[@remon95]

> What's the most you ever lost on a cache miss? > I dont understand... > printf("%d",num); //Call it. > Call it?? > Cache hit or miss. Call it.

[@2005kpboy]

Scott Myers of Myers Singleton, Hi Hello 👋...

[@jasonmarechal5501]

Summarizing a bit what I learned (a lot): - Hardware optimization is a thing and happen because of caches - Fetching a value for reading doesn't only fetch the value but the whole cache line (64 bytes) - Reading values from the same cache line is fast - Having to change cache line is costly: e.g. cache lien is full and new data is not in it - Arrays are the prefered data structure of cpu because contigus values can be read from the same cache line - For matix, row by row is faster than column by column (assuming columns are array of rows and rows array of values) for this reason - Writing a value invalidate the cache line, need to refetch it - False sharing occures when there is no logical dependency but hardware dependency. When multiple thread need to read/write (read only is not an issue) the same cache line. Better try to do a maximum of operation in the thread local storage and report to the global state only when necessary. Or copy the global state sub data set locally instead of trying to read it multiple times if there is a risque of it being invalidated.

[@felixkrivec8788]

Writing a value invalidate the cache line, need to refetch it. If I understood it correctly, this is only true if a cache line exists in multiple caches. If the cache line only exists in one cache, it remains valid.

[@John-vk1ij]

Gosh. He's a born writer

[@panteliskaramolegkos2693]

Why by doubling the threads (@ 8:01) no the performance drops? Context switching?

[@Barldon]

Increasing threads results in more false thread sharing (thus worse performance) if the algorithm doesn't take cache into consideration.

[@milahu]

1:15:25 with cpus faster than memory, it is more important to make good use of MEMORY (not cpus)

[@Fetrovsky]

"In particular, it's marked dirty in all the other caches." He surely meant invalid. It's marked dirty in the current cache, and invalid in all of the other caches. Later on he says "it's marked dirty" means "it's no longer valid." I'm sure he meant to say "it's no longer valid in all other caches," because the copy which was written (the dirty one) is the only valid copy of the cache line since it contains the most up-to-date values.

[@TheArakan94]

+Daniel Jesús Valencia Sánchez so what?? it's normal term - dirty bit :)

[@Fetrovsky]

+David Novák dirty != invalid

[@TheArakan94]

+Daniel Jesús Valencia Sánchez how so? dirty is normally used exactly in this meaning. In general it means that data has changed in one location and something have to be done about it - usually synchronization.

[@okuno54]

+David Novák I'm kinda guessing here, but: I think invalid means that the data in the cache line is just plain unusable. On the other hand, dirty means the data line will have to be written back up the hierarchy before the line can be used for other data; until that happens, the data can still be used by that core. The idea is: a write requires the data to be in exactly one cache line, so before writing to your cache, simply force the data out of all the other caches just to be sure. This invalidates all the other caches, but your cache is still valid.

[@sasjad]

That's correct, but only the dirty bit for the newly written data should be set to indicate that it holds the correct data. All other cache lines should not have their dirty bit set, and should instead be set to invalid because the data in those cache lines are "outdated". It is actually quite important to separate valid bit and dirty bit as they are not the same..

[@berajpatel8081]

Thank you Scott Meyers

[@minciNashu]

1:02:10 there's a programmer joke about 512. guy asks a programmer friend to lend him 500 dollars. the programmer says - i'll give you 512, so it's a whole number.

[@clodgozon3968]

012

[@shadyabhi]

Any books that complement this type of knowledge for an average programmer?

[@akashagarwal6390]

how abt the fact that an array needs a contiguous/continuous range or set of mem addresses only to fit in. So if i define an arr of size n, anything smaller than the n block in the mem is not being used to allocate space for the arr, leading to fragmentation of the mem. but i believe the runtime is more important than the mem fragmentation always right?

[@afterbunny257]

This guy is so fun

[@blazsovdat6433]

Could someone provide an URL to a copy of the Herb Sutter's article mentioned at the beginning of the talk? :-)

[@pretzelboi64]

People seem to hate his haircut but I think it suits him really well.

[@wincentyzkielczy9162]

Great talk

[@i_am_acai]

by heap based binary search tree at 25:53 is this the heap data structure or heap memory?

[@akashagarwal6390]

does it matter? a heap DS is also an object residing in the Heap mem space of the RAM (fast/primary/main mem) right?

[@GeorgeTsiros]

37:20 not only that, it's likely going to be kept in a register

[@DrakosKai]

Scott gets his hair done at Castle Greyskull! Seriously though, release some more books so I can buy them!

[@gleventhal]

lol, that's funny. I was thinking Emo Phillips.

[@alabamapilot244]

"What's the most you ever lost on a cache miss?"

[@ahsn]

Enlightenment! Love it.

[@totheknee]

1:08:15 - In fact, OO design is almost invariably harder to read and maintain than _any_ other paradigm I've come across. It would be nice if people would actually think about what readability means instead of just assuming the Object-is-God dogma is true without it ever being demonstrated.

[@ekrem_dincel]

34:00 is this apply even when you don't use any synchronization? Does it resets caches anyway? (note 38:50)

[@ekrem_dincel]

Note 1:00:01

[@DeusExAstra]

Very informative talk. Thank you!

[@hvrjstn]

Zero cost abstraction is not as cheap as previously thought.

[@mallydawg479]

woow I just went into trance

[@rostislavstelmach9168]

he is so genius

[@glizzdawiz]

fucking wizard.

[@utprem]

Watching this video with a beer in hand makes my understand good. Thanks #Nokia

[@NOKIAWroclawTechnologyCenter]

you welcome!

[@danielphd5072]

Thank you for this video #cpp #cplusplus #caches #CPU #memory

[@thormoz2550]

Great talk!

[@parinda1980]

what a enlightenment!!!! thank you

[@snarkyboojum]

Why can't the compiler work out how to avoid false sharing automatically? Seems like it'd be worth fixing when the compiler generates machine code.... His comment at 1:13:00 on the subject seems to be plain wrong - from software.intel.com/en-us/articles/avoiding-and-identifying-false-sharing-among-threads "Since compilers are aware of false sharing, they do a good job of eliminating instances where it could occur. For example, when the above code is compiled with optimization options, the compiler eliminates false sharing using thread-private temporal variables. Run-time false sharing from the above code will be only an issue if the code is compiled with optimization disabled."

[@ba0cbmft]

How did MS miss the boat on some of this stuff? They had Abrash working for them for years and his book on graphics programming covers these topics. Optimizing for tricky caching architecture has been a thing since at least the Pentium.

[@codeinclined]

Well, one of the examples was them commenting on beta code. While ideally they would have designed around this ahead of time, at least they caught on to their performance issue on that while it was still in beta. The rest of it might range anywhere from human error to assigning junior programmers to essential systems and not having good code review or mentorship happening (tight deadlines and too many cooks in the kitchen may exacerbate that too).

[@GeorgeTsiros]

abrash may be good but ms is not the best at using the capability of their tools. No, I'm not saying Abrash is a tool, that's not what I'm getting at 😖

[@paulsaulpaul]

Who can maintain their peace listening to this guy? Why is he so wound up? I will have to find some kind of written version of this lesson.

[@hunterxvov4ik]

fax.

[@chiku1987]

Here's the link to the slides - cdn2-ecros.pl/event/codedive/files/presentations/2014/CPUCachesHandouts.pdf

[@antiHUMANDesigns]

So, when parallelizing code over multiple cores, we should make sure that no writes are ever performed within 64bytes of where some other core is reading, then? I mean, to try to state it as a "rule". If I understand it correctly, that should prevent the possibility of false sharing of the same cache line. If what I'm saying is true, then would this conclude that the potentially fastest way (ignoring other forms of possible overhead) to parallelize processing an array would be to split the array into sections of multiples of 64 bytes, and give one such section to each core? Or is there a problem of not knowing where a cache line will start and end? Any input is appreciated.

[@jonaskoelker]

+antiHUMANDesigns - I think you are correct on the first part: if you can make cache-line reads always be disjoint from cache-line writes (for the duration the cache line stays in cache, I think) you should have no false sharing. It's my understanding, though I'm very unsure about this, data of any kind can start at any byte-that is, elements 0 through (64 / (sizeof element)) of an array may reside in two adjacent cache lines if element 0 doesn't lie at a cache line boundary. Maybe your specific compiler has ways of letting you tell something about memory layouts; if you can align your important data structures on cache line boundaries, then your method will probably at least provide a non-trivial benefit. For large _arrays_ specifically, my guess is that if you split it in (roughly) even chunks and traverse them in row-major order, that will scale near-perfectly and be *very* hard to beat. I think giving the first half to thread A and the second half to thread B will be better than giving all the even-numbered cache lines to thread A and all the odd-numbered cache lines to thread B, but this is based on gut feelings and non-articulated heuristics rather than data. YMMV.

[@rmay9001]

+antiHUMANDesigns well I think that fastest way would be having each thread having a cache aligned array to itself, not just splitting an array into blocks of 64-bytes, that way you could also get prefetching per per thread, I doubt the prefetching will happen if a core is say reading a block then moving to the N + 4 cache line, but your way will at least avoid false sharing.

[@antiHUMANDesigns]

Jonas Kölker Yes, that is how it seems to me, aswell, that while a cache line may be 64 bytes long, your current data may not be at the start of it. So keeping them 64 bytes apart may not be necessary, but it guarantees that there is no false sharing. I'm writing a 2D game engine in C++, and it gathers the information about how many cpu cores there are, and how long a cache line is, so that I could dynamically take advantage of the cache to the max. Of couse, being a 2D engine, it hardly requires as much performance. Yes, if you traverse an array, then pre-fetching will probably be fast enough to make maximal use of the cache. In reality, this is really hard to do, because it's really hard to make sure you have the data you need, with no need for "getters", in an array. Updating the position of things, for example, wroks perfectly fine. But other things usually requires that you gather data from different things as you process. In practice, it's reall hard to figure this out in an optimal way.

[@antiHUMANDesigns]

rmay9001 My point is that imagine you have an "unlimited" number of cpu cores, and you want to split an array to do work on them. There would be no gain in splitting it so many times that each piece is smaller than 64 bytes. In fact, it may slow you down. So, the minimum size of each piece should be 64bytes.

[@rmay9001]

+antiHUMANDesigns well only if you wrote back into the array, if you had one array that you read from, and had another array you wrote into, and in that array you guaranteed no cache conflicts, you could still gain some performance

[@sai-codes]

at 20:19 what is a well localized code?

[@_capu]

your different variables of a structure should be adjacent if they are used at the same time in your code something like this

[@QuentinUK]

Dramatically improved performance.

[@gleventhal]

@3:20 He said Microsoft's compiler 3 times for two datasets and never mentioned GCC XD Luckily, based on context we can infer the faster one is GCC

[@selvalooks]

thanks !! it was very clear !!

[@mohamedtarek8899]

I try the first program using python results to show no difference between col or row ordering. However, when I use NumPy array in C order, not Fortran, there is a huge difference. Does anybody have an explanation why this is not true using python?

[@jonatanlind5408]

C is compiled to cpu instructions while python is interpreted. The interpreter used to run python effects the hardware in such a way that cpu cache effects no longer matter. C meanwhile is "closer to the metal" and as such details of how the cpu works is more visible to the program. The reason NumPy is affected by col vs. row ordering is because NumPy is implemented in C so the calls in python simply forwards to C. I'm however not sure I understand your question so feel free to ask a follow-up question in case I misunderstood something. Cheers :)

[@RobBCactive]

AFAIK Numpy is using a C shim to interface to a Fortran library. Fortran lays out multi dimensional arrays in first subscript varies fastest order, C uses a natural array of arrays, where last subscript varies fastest. That means strings in most languages are lain out naturally in memory where Fortan would slice them in the columns. So the surprising effects you see might be due to Fortran favouring column major scan. Numpy may be converting arrays back and forth for processing by Fortran.

[@solid8403]

The hardware ... THE HARDWARE

[@sobowaleolamide4177]

U dey here

[@mateusznowakowski1834]

amazing talk, sad that probably I will never use this knowledge in my job :|

[@brod515]

I didn't really understand the idea that the matrices can vary in shape. A Matrix can vary in shape conceptually but in memory isn't it all lined up linearly

[@pawanadhikari110]

MrBrN197 yes but here we talk about fetching the value row or column ,,,and he is saying it to visualise conceptually

[@headecas]

my brain hurts

[@sobowaleolamide4177]

I legit had this problem on a matrix algorithm I wrote about 4 years ago, until now I didn’t understand why the algorithm ran so slow with concurrency and faster with a single thread. I

[@GeorgeTsiros]

even without caches, row major traversal is faster, because Random Access Memory does not really like to be accessed randomly xD It has lower latency when accessing nearby locations to the ones previously accessed. Of course, if the entire array fits in one page (block? section? bank? easter bunny?) of memory it wouldn't matter. So it's a staggered issue: the process's memory accesses are as fast as the _slowest_ memory that it demands. If it fits in L1, then it's as fast as L1. If it touches ram, then its _memory accesses_ will be as fast as ram. Did i get it right? :|

[@moobanposrisuk1736]

easter bunny - ha ha ha ha ! Good point tho' really

[@bocckoka]

when you are introduced, you say these words, in this order: 'thank you for the lovely introduction'

[@jgvidotto]

great hair

[@tazeey]

21:33

[@chibula]

This guy fucks!

[@mycollegeshirt]

why the hell am I sharing the cache with the os if my program has the users attention

[@absurdengineering]

mycollegeshirt If you’re coding bare metal, there’s no OS, and your process will be the only thing running. You’ll end up writing the OS yourself and will face the same problem right away, except you won’t have the advantage of man-millenia of effort that went into making that OS work well (yes, mainstream OSes are way better than you give them credit for; Windows Explorer is not what makes an OS tick). You’re not talking to the USB host that talks to the keyboard and mouse yourself, and you’re not talking to the graphics card command queue to draw stuff on screen either. The OS is that piece of software that does it. Once you do these things yourself (e.g. by putting all your code into a driver that then processes all interrupts and doesn’t let any other OS code run - possible even on Windows, no biggie), you won’t have to share with the OS. And this assumes that there’s nothing else running on that computer. The OS has to reply to pings on the network, it has to process broadcast network packets, it has to react to various hardware indicating that the data requested is available (disk commands finishing up, network requests arriving and leaving, etc). Even on bare metal, “you” don’t have users attention. Some code written by the platform vendor is talking to the peripherals so that you don’t have to spend a man-year getting a rudimentary USB stack going. Poorly. And also, on any CPU that has to do thermal and power management (even mid-size microcontrollers have to do this, mind you!), you either have to do that too, lest the chip shut down on you, or there’ll be system management code either running behind your back on the same execution platform (and preempting your code without you even knowing without taking measurements), or running on a dedicated embedded CPU within… Modern platforms are quite a bit more complex than that equivalent of a Z80 system they show in intro computer architecture classes.

[@reneschindhelm4482]

23:20 Hello Spectre & Meltdown!

[@tanveerhasan2382]

what do you mean?

[@alinaqvi2638]

I thought L1 cache is 64 bytes not 64 kB.

[@OmarChida]

64 bytes is the cache line. 64kb is the whole thing

[@malikaremu2344]

No boolean in struct got ya, a boolean is a bit though

[@todorsamardzhiev144]

If your principal engineer looks like Scott Meyers, your company is definitely gonna make it. Just saying.

[@anandkulkarni2111]

Things arent simple as some times we assume them to be at higher level of abstraction :) this makes life of lot of application developers more difficult that easy as most organizations aim on shipping more frquently and faster than doing deep dive analysis and optimization :)

[@milahu]

5:00 the lowercasePee uppercasePee code is not optimized for magazines ... its optimized for idiots (by trolls). but its equally idiotic to still use this hard-to-read code in a presentation

[@georganatoly6646]

surprised there's not a bunch of assembly programmers in the comments looking down their noses at the high-level programmers lol

[@lucienzhang]

mechanical sympathy matters

[@pabasararanasinghe]

😄

[@mahmutdikcizgi9773]

that db guy was a jerk.

[@necrowizzard]

funny

[@higgins007]

And the industry as a whole is still making excuses to stick with OO. Shame.

[@saniancreations]

I can't help but think, Scott, are you angry? There's this sort of... 'bitterness' emanating from his facial expressions and tone of voice. Like he's just incredibly pissed off at the whole industry and everything it stands for. Which he might be for all I know, but still. (also word choice? that "pathetic" remark towards the audience was a little much 20:40) This talk is important, informative and it doesn't beat around the bush. It gets to the point, which I like. But man, I feel like it could have been so much better if he just spoke in a more positive tone. It's almost like he's berating all of us rather than teaching. The first half of the talk is definitely the worst in this regard, it gets better near the end and especially the questions segment is actually fine, so I'm not really sure why he speaks in this way.

[@the32bitguy]

I guess he is passionate, it makes it gripping to listen to

[@kim15742]

lol, he made me laugh

[@HenriqueBucher]

Welcome to 1995 Scott