CppCon 2014: Chandler Carruth "Efficiency with Algorithms, Performance with Data Structures"
847 13 70655
Presentation Slides, PDFs, Source Code and other presenter materials are available at: https://github.com/CppCon/CppCon2014
Why do you write C++ code? There is a good chance it is in part because of concerns about the performance of your software. Whether they stem from needing to run on every smaller mobile devices, squeezing the last few effects into video game, or because every watt of power in your data center costs too much, C++ programmers throughout the industry have an insatiable desire for writing high performance code.
Unfortunately, even with C++, this can be really challenging. Over the past twenty years processors, memory, software libraries, and even compilers have radically changed what makes C++ code fast. Even measuring the performance of your code can be a daunting task. This talk will dig into how modern processors work, what makes them fast, and how to exploit them effectively with modern C++ code. It will teach you how modern C++ optimizers see your code today, and how that is likely to change in the coming years. It will teach you how to reason better about the performance of your code, and how to write your code so that it performs better. You will even learn some tricks about how to measure the performance of your code.
Chandler Carruth leads the Clang team at Google, building better diagnostics, tools, and more. Previously, he worked on several pieces of Google’s distributed build system. He makes guest appearances helping to maintain a few core C++ libraries across Google’s codebase, and is active in the LLVM and Clang open source communities. He received his M.S. and B.S. in Computer Science from Wake Forest University, but disavows all knowledge of the contents of his Master’s thesis. He is regularly found drinking Cherry Coke Zero in the daytime and pontificating over a single malt scotch in the evening.
Videos Filmed & Edited by Bash Films: http://www.BashFilms.com
By tjalfi 2017-09-20
Chandler Carruth talks about unordered_map performance in his CppCon 2014 talk "Efficiency with Algorithms, Performance with Data Structures". He endorses most of the other alternatives you mentioned.
By adrianN 2017-09-20
Yes, if you write performance sensitive code you have to be very careful with dictionaries. See for example this nice talk by Chandler Carruth https://www.youtube.com/watch?v=fHNmRkzxHWs
By dgquintas 2017-11-27
"Just say no to linked lists!" https://youtu.be/fHNmRkzxHWs?t=2099
By anonymous 2017-09-20
The standard library's maps are, indeed, inherently slow (
std::map especially but
std::unoredered_map as well). Google's Chandler Carruth explains this in his CppCon 2014 talk; in a nutshell:
std::unordered_map is cache-unfriendly because it uses linked lists as buckets.
This SO question mentioned some efficient hash map implementations - use one of those instead.
By anonymous 2017-09-20
I suggest watching this talk by Chandler Carruth: "Efficiency with Algorithms, Performance with Data Structures" He addresses the idea of "Power efficient instructions" at 4m 49s in the video. I agree with him, thinking about how much watt particular code consumes is useless. As he put it
Q: "How to save battery life?"
A: "Finish ruining the program".
Also, in Python you do not have low level control to be even thinking about low level problems like this. Use appropriate data structures and algorithms, and pray that Python interpreter will give you well optimized byte-code.