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

A great talk which gets you thinking in this mindset is "Data-Oriented Design and C++" by Mike Acton ▶ this video As an example, if you are checking a boolean flag (1 bit) on an object, and it ends up being a cache miss (and x86_64 cache line size is 64 bytes), then your computer just went through all the expense of pulling in 512 bits from RAM yet it only used 1 of them. You are achieving 0.2% of the machine's possible throughput.

in “Old box, dumb code, few thousand connections, no big deal” · View on HN

Just because it's asm doesn't mean it's fast, sure. Just because it's C doesn't mean it's faster than an implementation in your favourite scripting language. Having said that, compilers do pretty badly on C-to-simd optimisation. The best you get is loop vectorization if it's really simple logic. You can usually get some pretty good wins there. The fact you lay out your memory for simd usually is a win all of its own due to cache prefetching even if you don't actually use any simd instructions. Compilers need heuristics to manage cache when you know what you're trying to do, (eg when should it use non-temporal writes, for example?) Fast C code is written while having a really clear mental model of the underlying architecture and the assembly that the C will produce with -O3 (or whatever flag is relevant to your compiler) and then checked with -S or objdump -D, profiled with callgrind/cachegrind, perf, rdtsc etc... The compiler really can't "Do it for you" You /can/ use a compiler as one of your tools when /you/ do it. As Randy Hyde points out you can always beat the compiler because you can use its generated assembly language in every case you can't beat, so the absolute worst you get is a tie. So yeah, you can totally smoke clang, Intel, microsoft and gnu C compiler and get paid something for doing it in certain industries too. :-) Mike Acton being aggressively opinionated on the subject, but the lecture is really good (despite/because of) the bits you'll disagree with and th

in “Asmttpd – Web server for Linux written in amd64 assembly” · View on HN

I'm going to disagree with most of the comments here which say that you can't become faster, as I have become notably faster over the past couple of years (perhaps 1.5-2x faster!!). Basically, it was a fairly major coding style change that happened after working with others in my industry (game development) and seeing their prolific output of high quality code. My process for writing code used to be: - Identify problem. - Identify the abstractions that fit the problem - Implement those abstractions - Write code to solve problem using those abstractions. Now it is - Identify problem. - Write code to solve problem, pulling abstractions out if and only if they make sense and would actually be used . Honestly, I feel this leads to much better, cleaner and more understandable code, however, it tends not to mesh well with what some people consider best practices. The resulting code tends to not be particularly object oriented, tends to have large functions, and tends to perform very well due to having a very small distance from what the code says to what actually needs to be executed by the processor. For more on this approach, see [0]: [link] [1]: [link] [2]: ▶ this video

in “Ask HN: How do I become a faster programmer?” · View on HN

> cache-aware data structures and algorithms Maybe hardware- and access-aware more generally. One of Mike Acton's other talks has a "Is Data-Oriented Design even a thing?" section, which goes over what he means when he refers to DOD: ▶ this video

in “Introduction to Data-Oriented Design [pdf]” · View on HN

> Recently someone proposed this on LLVM Well, to be honest, it's not any extraordinary idea and it's not even mine. Mike Acton used this exact example in his CppCon video ( ▶ this video at 25:58). I just happened to know that LLVM's DenseMap has this problem. On the other comment, data locality is a property (well... it's not really a binary thing (i.e, an execution has it or it doesn't), but really a spectrum; but ok, it will do) of a program. For example, a simple definition which I like is in the paper "Improving Data Locality with Loop Transformations ( [link] ): > Data locality is the property that references to the same memory location or adjacent locations are reused within a short period of time. Changing the the layout is just a transformation to achieve this property. So, the two things are different in the sense that one is a property while the other is a transformation, but they're not different in the sense that data layout transformations are not relevant to data locality. Regarding cache locality, that is also a property that we could define let's based on this ( [link] ) say as: "The property that data brought into cache should be reused as much as possible before it is replaced". Data locality depends on the hardware on which the program is executed. Since we use caches in our hardware, to have data locality you usually need to need have cache locality so these two coincide. Finally, yes you're absolutely right (well, last time I checked...). LLVM has a bunch of

in “Common misconceptions about compilers” · View on HN

Casey Muratori is basically describing Data Oriented Programming. Perhaps the most famous talk about it was from CPPCON 2014 [1]. I come from an embedded background (microcontrollers and bare metal) so I'm pretty sympathetic to his argument. If you work in it long enough, it feels natural and "clean". Uncle bob's Clean Code probably feels natural to Java devs. Personally, my biggest gripe comes from experiencing people trying to introduce it to a team. Inevitably someone tries to enthusiastically implement some part of it and suddenly are writing 1 line functions everywhere. I think this is the type of thing Casey is also implicitly talking about when he's railing against the rules being brought up. [1] ▶ this video

in “Beyond Clean Code” · View on HN

dyingkneepad is talking about how the cpu actually works (x86-64 & cache hierarchy). It doesn't really matter what constructs a particular programming language does or doesn't have -- we can reason about performance in terms of what x86-64 instructions the cpu ends up executing. Suppose we want to compute the sum of n scalars, represented as n 32 bit floats, say, and we're weighing up if we should store these n scalars in a linked list or an array. The "introduction to algorithms" analysis might be that both approaches require O(n) storage and O(n) running time, so they're indistinguishable, up to some constants that get absorbed into the big-oh notation. The basic big-oh analysis is true as a first cut for some theoretical simplification of a machine, but with our performance hats on, maybe we're interested in the constants being small so our code actually runs fast on a real machine -- we need to understand how a real machine works in a little bit more detail, in particular we need to have some crude mental model of the memory hierarchy. On real hardware, if we use a linked list to store our data then each node in the list may end up in an unpredictable region of memory. The CPU will need to load these fragmented chunks of memory into L1 cache memory. Depending on the whims of the memory allocator, each time we read a node into cache we may get a single useful scalar value surrounded by a bunch of other junk -- our precious expensive L1 cache may be 90% filled with junk and

in “Ask HN: How come pass-by-reference is not the default in C++?” · View on HN

There's been a few talks: CppCon 2014: Mike Acton "Data-Oriented Design and C++": ▶ this video CppCon 2018: Stoyan Nikolov “OOP Is Dead, Long Live Data-oriented Design”: [link] Building a Data-Oriented Future - Mike Acton [2019]: [link] And a blog/book has been created: [link]

in “Data-oriented design or why you might shoot yourself in the foot with OOP (2009)” · View on HN

Something extremely popular in older games: Collection types with non-uniform elements. Imagine a kind of array or list where some elements are 4 bytes long and some are 6 bytes. There's this really funny reaction from the audience when Mike Acton suggests writing different types of scene graph nodes to a void* to avoid unnecessary padding which would pollute the data cache. One of the Q&A questions at the end utters its distaste for it cause it's using void instead of proper types. It's the objectively better solution in terms of performance, but it's just too yuck for many people. ▶ this video

in “How to Read Assembly Language” · View on HN

For numerical computing:yes. For games, dont you just use float (for non-integer values)? Found the video I was thinking about: ▶ this video from 1:24:00 onwards.

in “Best aspects of C” · View on HN

I'm reminded of Mike Acton's 3 Lies of Object Oriented Programming . Lie 2: Code should be designed around a model of the world . He makes the point that object-oriented models can never really model real-world objects, and shouldn't try to. A game engine may have several ways of representing a chair, for instance (a physics chair, a breakable chair, a static chair, a usable chair). These probably shouldn't share an interface, despite all relating to real-world chairs. ▶ this video

in “Examples of Incorrect Abstractions in Other Languages” · View on HN

It's nice to hear this kind of concerns; don't be afraid! At last, C++ committee members are just people like you, hopefully nicer than expectation. > I find reading C++ "standards" papers onerous and feel like they're written in a way that's deliberately inaccessible. Sadly, it's somehow true; standard wordings are typically not readable for laypeople because its primary purpose is unambiguous specification but not education. Generally, I find that it's a good idea to avoid "wording for ~~" proposals if I haven't followed that specific line of proposals from its beginning. But many proposals are still fairly readable technical papers; for instance, Herb Sutter's proposals are generally easy to follow. (ex. [link] ) > I feel like I'd be marginalized for not using template metaprogramming, not knowing the new hotness by heart, and generally being a proponent of C-with-classes. ▶ this video Don't worry. Mike Acton is not known to be a strong proponent of "Modern C++", but his session[1] is one of the most popular CppCon video on Youtube. Even if you don't like templates, people will generally respect you. > I just feel like so much of the C++ "standards" work feels like it's led by academics who think the concerns of working programmers like me are beneath them. [link] You can find the list of the participants for the last meeting. Most of them are just engineers and even Bjarne is now working for Morgan Stanley (I think most of "designed by Ivory Tower" concerns can be generally cr

in “Thoughts on Modern C++ and Game Dev” · View on HN

"'Premature optimization is the root of all evil' is the root of evil" [link] [link] [link] [link] It's basically an excuse to not think about the performance or implementation of your entire product until the end and then, when you use a profiler and chop away "10%" here and "20%" there, you still end up with a slow-as-piss program with every function taking less than 1% total time. Then what do you do? Oh yeah, what you should have done in the first place. _Think_ about how your program actually functions so you can remove all of the insane systemic, architecture decisions you made that all bleed a fixed amount of time every single function call. That's the difference between an engineer, and script kid. If you're not reasoning about _the entire platform_ (all the way down to the cache lines), you're not engineering. You can abstract all you want, but those abstractions don't magically prevent the underlying hardware and architectural decisions from affecting the product. Abstractions tools (read: approximations!) for high-level reasoning. They're not magic "you don't have to think [about low level implementation]" spells. Actual experts keep trying to warn you guys about abusing that quote, but nobody apparently ever listens. Stop quoting it like a bible verse, because just like bible verses, everyone forgets the entire context and just uses it like a bloody bumper-sticker slogan. In the words of Saul Williams: "You have wandered too far from the original source, and are e

in “Netflix: Removing client-side React.js improved performance by 50%” · View on HN

No, they're not cache friendly. The problem is row-based vs column-based. Array of structs vs Structure of arrays. With arrays of structs/objects you get row-based access patterns. Especially for cases where you only want to access one or two columns, you always pull in everything else. ▶ this video

in “In Defense of C++” · View on HN