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

My take away: cache locality is everything.

I watch nearly all talks on cppcon + meeting. This is my favourite subject. This talk encapsulates 70% of what it is to write efficient code. to cover 70% is incredible for an hour. Best talk to date on the subject.

26:16 Very good chandler, "Why do I bring up these simple examples, I bring up these simple examples because it is critical that you always do these things, ok. Not some of the time, not after a profile discovers a problem, you wont find a profile that points to these problems, that's part of what makes them really tricky, ok. The key here is that you want to always do these things because they don't actually make your code worse." Essentially we're talking about efficiency death by a thousand performance hits, microoptimiziation zealotry called to battle, I like it.

Excellent talk and even more accessible than Mike Acton's Data-Driven design talk (also good) without being so low-level oriented.

Great talk as usual by Chandler!

Absolutely a wizard.

Thanks! This talk is still very useful in 2023, though it could be 2 times shorter. The gist is: be cache-friendly, keep your data locality high, use contiguous containers. Instead of std::map you can often use std::vector + housekeeping, and sort when necessary. Lists are evil. Earlier, I saw that, in synthetic examples, when not much else is going on, the performance of std::vector and std::map is essentially the same when the sizes of the containers are below ~500. The tricky part here is the "when not much is going on". So I decided to carry out a real life experiment. Recently I wrote a lightweight node profiler for a tree of CPU-heavy nodes of a size ~400. I used maps to sort measurements by two distinct properties. It was ok, but in debug builds the performance hit due to profiling was noticeable, similar to 1-2 heavy nodes. I spent 2 hours rewriting the code to std:vector plus some additional housekeeping.The gathering and sorting of data in debug builds became ~3.5x faster, and filtering of data became ~8-10 times faster. Surprizingly, the code became 1.5x smaller. Now it is entirely possible that the first version of my code was simply shit. But anyway, now my profiler is really a lightweight one.

Awesome talk.

I love the table of memory latency at 37:15

gotta love this guy.

interesting talk!

Very informative talk, thanks !

"Performant" is very much a valid word in marketing pidgin.

Great talk

he was talking about sorted vectors and in that case you can use std::lower_bound which will be faster then map::find

No, he didn't say to simply replace map with vector. He said that a sorted vector (where find() would become a binary search) has the same functionality as map but much higher performance.

Good talk.

good talks don't age! e: reflecting more about the LL/maps points, I found myself tending towards making basically 3D arrays and providing the API as if it were a map/graph/deque w/e just because I'm lazy and it was quicker/simpler to implement but then testing it runs faster as well

The real sentence is "Rush to idle", Copyright Mooly Eden ... ;)

This speech is sooo cool

It is pity that too much constraints in the C++ specification forces std libraries to specific implementations. It seems that we miss already out out on sbo vector (like Boost's small_vector) and a hash map with faster lookup. Perhaps that one also solves the creation cost of unordered containers which can be pretty heavy due to allocations.

Very interesting but I'm confused... why don't the CPP committee give us a range of useful vector-based data structures that we know will be faster in practice (given some bounds)?

great talk : )

There are a few funny points about this: Caches - at the time of the talk intel Haswell was already released and they had one of the best experimental changes Intel did in that long 4-core time: They added an L4 cache. For some applications (my work included) that was a huge speedup (~20% in many instances). Sadly they did not further pursue that. Java - i mostly had the opposite experience: People claiming it to be oh so slow. Kinda funny when you can then show them that it is one of the most used languages for programs running on supercomputers. Sure, Java was extremely slow in the first version where is was basically an interpreted language. And even nowadays there are scenarios were it is crawling along like a sloth but that is in specific scenarios only as it has a rather long startup-time for the JVM so starting a small program thousands of times from commandline-arguments will be really slow. On the other hand writing java is easy and when putting the same amount of work into writing a program in C++ and Java then the Java-Version is very likely to perform better as it tends to be easier to write java and harder to write high performance C++. And performance: Well yeah, sadly programs are objectively becoming less and less efficient and slower at completing the same objectives - generally speaking. More time and resources is focused on other aspects and performance is treated like "Speed? We got faster hardware" very often. Specially with smaller games that is very noticeable. When 2D side-scrollers with maybe a few docent objects on screen will not run smoothly on a 10 year old CPU while looking worse than the games that came out 15 years ago.... I have seen extremes like Sim-City clones that have less functionality and less going on would fully utilise 1 core of a current CPU and still only compute about 10 timesteps a second. And at my work it is also rather strange. Yes, i do use std::unordered_map for a few things as it made the algorithm easier. Funnily enough i initially used a normal std::map and during code-review it was mandated that i'd switch to unordered-map for better performance..... just that the change gave me exactly 0 improvement in execution-time cause for our software most of the time is wasted on an incredible archaic and inefficient tracing-tool. Changing the format in which i traced the data (constructing and formatting the string on my own) gave me a 3x speedup. The whole base-system has so many problems that the execution-time of the actual businesslogic is not even 1/10th the total. Best thing ever was the request to improve the interface i had written for communicating with a particular hardware-system. It was a block of ~2500 bytes, with the first couple bytes being some base-information that was always required and some control-info telling us which fields were filled. Reading everything in one go took about 1 second. The initial request was for me to read those few marking-bytes and then only read the individual fields that were actually useful - and that increased the time to over 2 seconds cause that hardware only polled incoming requests like 50 times a second. Changing it to read it opportunistic with a large initial block reduced it to 500 ms on average. And of those 500 ms i checked that my code was only running for ~10 ms, 9ms were for the slow tracing,

i dislike camera work where they jump away from the diagrams, like the cpu one, cause I like to look longer and study (obviously I can pause though, so its kinda moot anyhow)

My definition of "performant" would be reaching the point at which continuing to improve the performance of a program does not justify the cost it would require to improve it.

idk I tested using output pointer vs return value and in my simple case they were about the same speed with the output pointer being slightly faster.

The compiler can do return-value optimization if you return by value. But a move, which is not exactly free, cannot be elided.

The compulsion to return return a vector by value is very suspect. Returning by value in this case forces the user to always re-allocate a new vector, even though it's often cheaper to re-use a vector you already had, especially if the new vector will have the same size or be smaller than the old vector. But return by value prevents that, because RVO doesn't work for re-assignment.

The comparison of java and c++ prformance he does is good but i think the problem is his conclusion that it is hard to get java to perfoem better than c++ but in reality it is a bit difficult to make a c++ program run in an optimized way. So if you are not super skilld it is a bit of a dice roll. So if you simplify the situation you could say C++ is like rolling a die with the numbers 1-20 on it and using java is like rolling a die with the numbers.. lets say 5-15 because higher amount of control also means higher risk of messing up.

This is a great talk !! Do we have something similar for Python as well ? Because Python does really need performant approaches. Any talk that covers some basics and /or advanced stuff?

40:39 Why is one cycle of a 3Ghz 1ns? Shouldnt it be 0.33333ns? How many CPU clock cycles are needed to access the L1 cache? Half a cycle? Is this correct?

The twist is that transistor density has become so high that lighting up all the transistors at once will cause the silicon to melt in a very short time. (seconds?)

24:39. That code is NOT linear. Yes, you hash the key 4 times, but you always hash it 4 times regardless of how many entries are in the cache. If it was linear you would do more work with bigger caches. That code may not be efficient, but it is still O(1)

Imagine if the data centers sold the cooling water as heating water that we're regularly spending in the northern hemisphere.

The missing frames are driving me nuts

Well you can compare the perfrmance of your code to the theoretical peak performance of your CPU. Nothing crazy about that. TPP will tell you how many operstions your CPU is able to do per second. Linear algebra libraries will be the programs that come closest to TPP

what a diverse crowd! :D

52:36 "...we are subject to some worse is better problems in the real world. There are going to be cases where the exact opposite of everything you know or want to believe will be true. For example, bubble sort is the fastest sort algorithm, for small data sets. Despite being quadratic algorithmically and being a terrible idea most of the time." I think Chandler would do well to abstract this divergence from the ideal processor/system where the algorithmic constraints are unhindered vs the real world cache hierarchy memory locality constraints. What properties would that ideal computer have to present for the algorithmic concerns to dominate in isolation? Is it just a matter of instant random access to any physical memory? Is that the bottom line of why "everything we want to believe is true" is actually only conditionally true? At the university we were definitely taught in a theoretical space about complexity, and these extra notions would have obscured the theoretical points being made. It's good to have a reality check though, thanks so much Chandler.

26:13 accessing a map 4 times is O(n) but accessing a map once and storing the result suddenly makes it O(1)? What? If you're going to count the hashing and pointer chasing as O(n), whether you do it 4 times or 1 time is not going to change the fact that it is O(n). Correct me if I'm wrong.

Although I agree on the cache locality affect on performance, I don't really buy the argument using vectors against map and lists. The problem is that you normally need to traverse (almost) random locations in the memory in order to do anything with the objects you reference in your collection, unless these objects are actually contained in the vector itself. In every other case that you put (smart or otherwise) pointers in the vector, and you want for example to locate an object (e.g. with binary search) then cache misses will be frequent.

@ +aziz as ---- Linked lists aren't bad (in general). Traversing lists on modern hardware is slow because of the way the caching mechanism works. Because it isn't generally stored contiguously in memory, the processor will keep requiring lookups in slower memory rather than loading a contiguous block into the cache.

at 23:00 isnt it a way bigger optimization (if X is expensive to copy) to move the X's into the vector or emplace back with constructor arguments? Isnt that going to speed up the code a lot more than reserve would? I understand that reserve will make the code more efficient, but Im confused why he chose to talk about that and not this other optimization that seems more obvious to me.

It's not amortized but expected 54:11

Dropped

I for one am guilty of using linked lists excessively in the past.

It's bad in all languages because each node is allocated separately by definition.

One thing was not clear. If I am not supposed to use std::map, then making a std::find on a std::vector is faster than std::map find method?

allocation in loop hole allotcation in loop hole

39:10 What about L3 cache?

23:00 Doesn't that make like 2 copies of every single thing in the vector? I thought things like this ran a copy constructor...

"99.9999% you want to run programs faster, to save battery life" the games industry does NOT - I repeat - does NOT exist

Making code fast.

It seems to be a French word.

Why not use move instead of returning by value?

what he said

I love when people say ignorant things like "[word which is indeed a word] isn't a word" and are being serious, it just shows they don't understand how language works. Dictionaries describe the usage of words by the speaker of a language, they do not determine what is and is not a word and they do not determine the objective meaning of words.

but I liked unordered_map.. goddamnit..

- So, is it always better to do all the work locally, and return a copy? - If a f() has more than 1 return way, it tends to be slower? - Never use 'std::move()'? - If an array/vector must have 64 bytes to fit in the L1 cache, does that mean that the array should be divided into several ones, 64 bytes each?

I really don't see his rant against map. Maybe it is not useful to the apps that he's seen at Google. But to think he's seen them all at Google is no less than sheer hubris. Also his rant against std::unordered_map seems only on its implementation, not the data structure itself.

26:09 example says: X* getX(std::string key, std::unordered_map& cache) { std::unique_ptr& entry = cache[key]; if(entry) { return entry.get(); } entry = make_unique(); // cache[key] = entry; //

RVO and NRVO have too many caveats to be trusted. Sometimes it's required, and sometimes it's not. Sometimes you get the optimization anyway, abut sometimes you don't. Even if the compiler optimized it away today, nothing guarantees it still will tomorrow. Nobody has time to constantly check the assembly output and there is no way to assert your got RVO. It's much simpler and more reliable to just use an out parameter.

I wish I could marry him.

I think that this wouldn't apply for interpreted languages like Python, because Python under the hood is working with buckets of memory, and every data type is an object(int, str, list, tuple, true or false, etc.)

it feels a bit underwhelming. The whole talk could be condensed to 20 minutes, saying: memory access is the main bottleneck, hence cache is important and data access pattern must have the locality, use std::vector and nothing else, and call reserve when you know the size ahead. In fact, the most useful part of it is all those bits in the discussion, about the return value optimization (which "we are not supposed to focus on in this talk"!) and that std::map is actually a linked list, and that there is google's "dense hash map" floating somewhere in open source projects on the internet. Which is ironic, because everything important is implicit, like always in C++.

The overall message of this talk seems to be that STD data structures are in general pretty terrible.

In summary: linked lists and red-black trees, although fundamental data structures in computer science, are terrible and should never be used for anything because "caches"... got it.

these c++ dudes are really passive-salty

Im looking for hot girls, is this a good place to find them?

This is ridiculous, and insulting to generations of computer scientists.