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

code::dive conference 2014 - Nokia Wrocław
codedive.pl/

[@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

[@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!

[@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.

[@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.

[@siwenzhang]

This talk is miraculous !

[@codeinclined]

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

[@smileysmile85]

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

[@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.

[@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

[@antonfernando8409]

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

[@neosapien247]

He really took that age joke to heart

[@probono2876]

Thank you for the outstanding presentation.

[@ante4933]

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

[@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.

[@emilflater5399]

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

[@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

[@malikaremu2344]

I love this video so much

[@PROMuffy]

That joke at the end... :o

[@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.

[@fkaanoz]

incredible talk!

[@nirmalyasengupta6883]

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

[@benk6192]

Amazing presentation

[@naknuknik]

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

[@pondlife9931]

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

[@ilovetobloved]

Amazing and brilliant lesson. thanks for wonderful session.

[@gat0tsu]

wow these lectures are really good

[@seopi]

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

[@FerhatErata]

Very good structured presentation

[@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

[@criticalposts3143]

I only traverse matrices in a Hilbert curve

[@alabamapilot244]

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

[@IndianNatiional]

Captivating and no doubt very informative

[@wessonwang5017]

great! got deeper understanding of cpu.

[@John-vk1ij]

Gosh. He's a born writer

[@berajpatel8081]

Thank you Scott Meyers

[@afterbunny257]

This guy is so fun

[@2005kpboy]

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

[@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..

[@wincentyzkielczy9162]

Great talk

[@ahsn]

Enlightenment! Love it.

[@mallydawg479]

woow I just went into trance

[@thormoz2550]

Great talk!

[@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.

[@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.

[@rostislavstelmach9168]

he is so genius

[@glizzdawiz]

fucking wizard.

[@DeusExAstra]

Very informative talk. Thank you!

[@parinda1980]

what a enlightenment!!!! thank you

[@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?

[@blazsovdat6433]

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

[@ekrem_dincel]

26:15 what the person said?

[@milahu]

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

[@bocckoka]

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

[@hvrjstn]

Zero cost abstraction is not as cheap as previously thought.

[@shadyabhi]

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

[@GeorgeTsiros]

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

[@utprem]

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

[@NOKIAWroclawTechnologyCenter]

you welcome!

[@headecas]

my brain hurts

[@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.

[@selvalooks]

thanks !! it was very clear !!

[@QuentinUK]

Dramatically improved performance.

[@danielphd5072]

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

[@solid8403]

The hardware ... THE HARDWARE

[@sobowaleolamide4177]

U dey here

[@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

[@mateusznowakowski1834]

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

[@jgvidotto]

great hair

[@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 😖

[@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

[@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.

[@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

[@malikaremu2344]

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

[@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.

[@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."

[@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?

[@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

[@chiku1987]

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

[@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

[@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.

[@reneschindhelm4482]

23:20 Hello Spectre & Meltdown!

[@tanveerhasan2382]

what do you mean?

[@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

[@chibula]

This guy fucks!

[@alinaqvi2638]

I thought L1 cache is 64 bytes not 64 kB.

[@OmarChida]

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

[@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.

[@georganatoly6646]

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

[@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

[@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 :)

[@tazeey]

21:33

[@lucienzhang]

mechanical sympathy matters

[@pabasararanasinghe]

😄

[@necrowizzard]

funny

[@higgins007]

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

[@kim15742]

lol, he made me laugh

[@HenriqueBucher]

Welcome to 1995 Scott

[@mahmutdikcizgi9773]

that db guy was a jerk.

[@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

[@cheopys]

Were I a dev lead I’d fire someone who wrote code as inconsiderably illegible as that. Gimmicks, fads, clutter

[@myverynow]

perfectly understandable why you used born crippled 8086* family. why i said crippled? simply, everything which is not risc / arm is born crippled. intel knows that and there are reasons for patching it with l1, l2, l3 cache. multiple cores on a die with distinct interface unit (separate from alu) is bad design!

[@simivb]

I hate speakers that are making a show out of their talk. 14:55. Everybody knows what a KB is. Thank you. I know you think you are funny and want people to be like "wow that's insane" but it is just annoying. I would rather have a calm person who simply states the facts give a talk than one of these celebrated tech-stars that make an entertainment product out of their talks. That Python guy is even worse.

[@codeinclined]

I don't think he was trying to be funny at all. He was just emphasizing how limited cache space is. People do this all the time in regular speech when they are trying to stress a point. It's not a matter of being calm or not. I suppose you could download the transcript and have a synthesized voice read it to you if human speech patterns are grating to your ears.

[@simivb]

I actually like human speech patterns, just not this particular one. There are tremendous speakers out there, who do a great job of conveying information and beeing entertaining. But when I listen to the kind of speaker that Scott Meyers belongs to (Raymond Hettinger is the king of those) I have the impression they are putting up an act. They are making a show. Seriously watch some Raymond Hettinger stuff, he did one talk where he asked the audience "do you dig it [python] now?" to get them to cheer after every bullet point. That is some manipulative stuff. That is ok at the E3 press conferences to heat up the crowd or if you are there to entertain people, but in a tech talk?? It's just manipulative. I am watching a tech talk to learn something while I am trying to figure out if the talk is actually any good (because 50% of tech talks are just rubbish), and a guy on a stage trying to entertain people is not aiding either of that. That said, Scott Meyers is way less extreme than Raymond Hettinger. He just does all the things that you get taught when learning to speak in front of people (intonation, dramatic pauses, accentuation), but the reason why they teach you this is because these are ways to manipulate people (Hitler was a tremendous speaker! (no, I do not want to imply that Scott Meyers is Hitler)). But when I watch a tech talk, I don't want to be persuaded by the way a person talks, but by the contents of their talk. That btw also happens in a lot of TED talks. I also have some experience in the field, which makes this ultra-beginner stressing stuff extra painful, but thats not his fault. Watch Andrei Alexandrescu for a better style. He is less manipulative and still entertaining. Ok watching 15:42 again. Are you seriously saying that he is not trying to be funny there?

[@Hopsonn]

Sounds like he just emphasizing that it is much greater in size really.

[@VestinVestin]

Different strokes for different folks, apparently... I thought the delivery was flawless and captivating.

[@gleventhal]

Totally subjective, you're of course entitled to your opinion, but it didn't bother me at all. The point he was emphasizing is that we rarely even bother thinking in terms of KB these days since space is generally so cheap, but in the context of CPU caches, we don't have much space to work with.