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
@@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.
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
Absolutely fascinating. Helped me to connect the dots and fill in the gaps. I understand the relationship between hardware and software much better now.
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.
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
"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.
+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.
+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.
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..
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.
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.
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).
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 😖
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?
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
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."
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.
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.
+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.
+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.
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.
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.
+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
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? :|
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?
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 :)
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.
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 :)
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.
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
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.
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!
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.
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.
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?
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.
it should be illegal to do so many camera cuts from the slides all the time like this... shame keep the focus on the slides, and make a picture-in-picture if you really want to show the speaker