Skip to content
Hallway
0:00 / 0:00

#sortingalgorithms#quicksort#branchprediction

Sorting Algorithms: Speed Is Found In The Minds of People - Andrei Alexandrescu - CppCon 2019

CppCon

189K subscribers • 101 videos on Hallway • Conference channel

YouTube
  • Recommended by 8 people: 7 on Hacker News and 1 on Lobsters.
  • A classic. People kept recommending it from 2019 to 2023.
  • Presented by Andrei Alexandrescu, author and computer scientist
  • Linked in the descriptionCppCon/CppCon2019

Advanced. Deep dive for people who know the field.

184K views7 years ago8 recommendations

Computer scienceSystems programmingAlgorithmsPerformance and optimizationC++

Andrei Alexandrescu explores how to optimize classic sorting algorithms for modern hardware using branchless techniques and custom cost metrics.

CppCon.org Discussion & Comments: reddit.com/r/cpp/ Presentation Slides, PDFs, Source Code and other presenter materials are available at: github.com/CppCon/CppCon2019 Sorting Algorithms: Speed Is Found In The Minds of People In all likelihood, sorting is one of the most researched classes of algorithms. It is a fundamental task in Computer Science, both on its own and as a step in other algorithms. Efficient algorithms for sorting and searching are now taught in core undergraduate classes. Are they at their best, or is there more blood to squeeze from that stone? This talk will explore a few less known – but more allegro! – variants of classic sorting algorithms. And as they say, the road matters more than the destination. Along the way, we'll encounter many wondrous surprises and we'll learn how to cope with the puzzling behavior of modern complex architectures. — Andrei Alexandrescu Andrei Alexandrescu is a researcher, software engineer, and author. He wrote three best-selling books on programming (Modern C++ Design, C++ Coding Standards, and The D Programming Language) and numerous articles and papers on wide-ranging topics from programming to language design to Machine Learning to Natural Language Processing. Andrei holds a PhD in Computer Science from the University of Washington and a BSc in Electrical Engineering from University "Politehnica" Bucharest. He is the Vice President of the D Language Foundation. — Videos Filmed & Edited by Bash Films: BashFilms.com Work at Hudson River Trading (HRT): tinyurl.com/safxfctf

Why it's here

8 people recommend this

What people say. Highly recommended as an entertaining and deep exploration of optimizing sorting algorithms for modern CPU architectures.

jiggawattson Hacker News • Recommends

On “Ask HN: What's the best lecture series you've ever seen?”

Not exactly a lecture series, but Andrei Alexandrescu has had some fantastic keynote presentations at CppCon. I don't even program in C++ any more, but I've watched these more than once, they're entertaining, approachable, and inspiring: Speed Is Found In The Minds of People link to this video std::allocator Is to Allocation what std::vector Is to Vexation link An actual lecture series I've enjoyed watching is "The WE-Heraeus International Winter School on Gravity and Light", which covers General Relativity using modern mathematical approaches: link Again, I haven't done physics in 20 years, but I've found it surprisingly easy to follow because it is so clearly presented.
View on Hacker News

bborehamon Hacker News • Recommends

On “Ask HN: Programming Courses for Experienced Coders?”

I really enjoyed “Speed Is Found In The Minds Of People”, a talk by Andrei Alexandrescu. At first he is just showing simple stuff, but stay with it, he goes deep. link to this video
View on Hacker News

United857on Hacker News • Recommends

On “Engineering a Sort Function (1993) [pdf]”

If you're interested in these types of implementation/optimization details, Andrei Alexandrescu gave a great talk at this year's CppCon about practical sorting, e.g. when to break out of quicksort to something else: link to this video
View on Hacker News

planteenon Hacker News • Recommends

On “Mispredicted branches can multiply your running times”

The article is C++, so not sure why you are bringing up AOT/JIT since it doesn't apply here. And clearly there is a large gain possible by doing a calculation rather than a conditional with a high entropy result, otherwise, the article's mentioned speedup wouldn't have happened. A PGO feedback loop isn't going to do anything on a high entropy conditional. I saw a great talk at CppCon 2019 by Andrei Alexandrescu about speeding up std::sort. He does this same trick among others to speed up the C++ std library sort routine. link to this video
View on Hacker News

nestorDon Hacker News • Recommends

On “Infectious Executable Stacks”

In his talk "Speed Is Found In The Minds of People" 0, Andrei Alexandrescu tries to make a sort really fast for medium sized vector and then closes on thoughts on this precise distinction. If this question intress you, it is worth watching. 0: link to this video
View on Hacker News

jacoboluson Hacker News • Recommends

On “Why is quicksort better than other sorting algorithms in practice? (2013)”

I enjoyed Alexandrescu’s CppCon 2019 talk “Speed Is Found In The Minds of People” About optimizing generic sorting routines for modern hardware. link to this video
View on Hacker News

r_sreeramon Hacker News • Recommends

On “Airlines Are Just Banks Now”

Here's an excellent example of what GP said: link to this video (long video, skip to 26:00 if you are in a hurry) The key is that code isn't running in a vacuum. It's operating on data (or controlling systems, etc). A smaller amount of code may be operating on the data in an inefficient manner, whereas a larger amount may be doing it more efficiently. In the above talk, this contrast is very stark, because the "more code" version does some stuff and then does the exact thing the "less code" version does, yet is faster. This kind of thing is common enough (albeit less stark than in the above example), that "less code is faster" is not a great "default" assumption to make.
View on Hacker News

DeciusCaeciliusMetelluson Lobsters • Recommends

Improving std::sort
2View on Lobsters

jeffreygoestoon Hacker News • Mentions

On “Folly – Faceboook’s open source C++ library”

Well, this argument goes both ways, a generic implementation can never leverage special properties of your data. See i.e. Alexandrecu's talk 0 at about 1:05ff. If as a company you have special use cases or guidelines, you may easily benefit from libraries using these properties. 0 link to this video
View on Hacker News

lumberjackstianon Hacker News • Mentions

On “Hoare’s Rebuttal and Bubble Sort’s Comeback”

I'm not sure about much analysis and theory that explicitly captures branch prediction, but in last year's cppcon keynote Andrei offered a possible metric 0 where he takes into account the average "distance" between two subsequent array accesses. It's basically, (C(n) + M(n) + kD(n)) / n Where M is moves, C is comparisons, k is a some constant, and D is "distance". 0: link to this video
View on Hacker News

thomas43on Hacker News • Mentions

On “Ask HN: What do you recommend for optimization and profiling?”

Do you have some more detaile about your app? I use perf, sysprof, trace32, visual studio profiler for profiling, but this highly depends on your environment. These assorted links might be interesting to you: - link - link to this video - link - link
View on Hacker News

jiggawattson Hacker News • Mentions

On “Algorithms for Modern Hardware”

The FAANGS certainly have people doing this kind of work. For example, Andrei Alexandrescu has a bunch of keynote talks at CPPCon where he talks about 1-4% speed optimisations he makes to the std library at Facebook. link to this video I also like the talk by Nicholas Ormrod “The strange details of std::string at Facebook": link
View on Hacker News