Hacker News Comments on
Sorting Algorithms: Speed Is Found In The Minds of People - Andrei Alexandrescu - CppCon 2019
CppCon
·
Youtube
·
25
HN points
·
9
HN comments
- This course is unranked · view top recommended courses
Hacker News Stories and Comments
All the comments and stories posted to Hacker News that reference this video.This is a thing, see https://www.youtube.com/watch?v=FJJTYQYB1JQ (talk by Andrei Alexandrescu at CppCon 2019 about this exact idea)
⬐ jiggawattsUpvoted because this is a fantastic talk all by itself, and also highly topical.⬐ ncmncmAs I recall, this was the talk that triggered me to begin the experiments that led to the article.
Andrei has a pretty amazing CppCon talk similar to this: https://youtu.be/FJJTYQYB1JQ
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:
- https://github.com/Kobzol/hardware-effects
- https://www.youtube.com/watch?v=FJJTYQYB1JQ
- http://igoro.com/archive/gallery-of-processor-cache-effects/
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".
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.
I enjoyed Alexandrescu’s CppCon 2019 talk “Speed Is Found In The Minds of People”About optimizing generic sorting routines for modern hardware.
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.
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.
⬐ pjmlpBecause implementation and programming language are not the same thing?Speaking of which, better catch up on the C++ interpreters and JIT related talks from CppCon 2019.
⬐ planteenI can't tell if you are trying to troll here. So you reject the notion of branchless coding as a premature optimization because you think it is going to be made irrelevant by a potential future microcode update? Or are you saying that a C++ interpreter/JIT would have made this branchless at run-time, but that optimization isn't made at compile time?⬐ pjmlpThe first one naturally.The tone of my previous remark is that optimization algorithms are orthogonal to programming languages, an language agnostic backend optimizer working on AST and SSA passes doesn't care what the input language was all about.
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: https://www.youtube.com/watch?v=FJJTYQYB1JQ
⬐ drudru11Thanks for this recommendation. It pushed me to finally watch it and I found it to be a really nice talk.