New Algorithms in C++23 - Conor Hoekstra - C++ on Sea 2023
Vložit
- čas přidán 14. 05. 2024
- cpponsea.uk/
---
New Algorithms in C++23 - Conor Hoekstra - C++ on Sea 2023
C++23 has made a number of very important additions to the Ranges library that was introduced in C++20. This talk will be an overview everything new in the C++23 Ranges library as well as a high level overview of all the different "types" of algorithms in C++ (from C++98 to C++23).
---
Slides: github.com/philsquared/cppons...
Sponsored By think-cell: www.think-cell.com/en/
---
Conor Hoekstra
Conor (he/him) is a Research Scientist at NVIDIA working on array programming models and languages. He is extremely passionate about programming languages, algorithms and beautiful code. He is the founder and organizer of the Programming Languages Virtual Meetup, he has a CZcams channel and is the host of two podcasts: ADSP and ArrayCast. Conor is also an avid conference speaker.
---
C++ on Sea is an annual C++ and coding conference, in Folkestone, in the UK.
- Annual C++ on Sea, C++ conference: cpponsea.uk/
- 2023 Program: cpponsea.uk/2023/schedule/
- Twitter: / cpponsea
---
CZcams Videos Filmed, Edited & Optimised by Digital Medium: events.digital-medium.co.uk
#cpp #cpponsea #programminglanguage - Věda a technologie
That the standard forgot to include "join_with" in C++20 was nearly criminal. You could split a string but you could not re-concatinate it anymore -.-
Bruh, C++ has been criminal for nearly 40 years at this point.
Thank you for the great talk! One thing not discussed is the quality of the generated code. In a benchmark for me the ranges version is 70% slower then the loop version posted by @tylovset. In GCC 13.1 -O3 I get 605ns vs 354ns. Also the generated assembly is 9x longer, 312 vs 35 lines in O3.
See on godbold /z/Ej8Eaco1d
This is not an argument against range based algorithms. They are more readable and less bug-prone. I just have some doubts about the hugely templated implementation of views in ranges-v3 and std::ranges that seem to be very hard for compilers to understand. In contrast std::algorithm don't have this problem.
That was something I was wondering about too. In many situations, one wouldn't want to give up the performance. It would be interesting to know if it was easy to fix the performance problem but still stay mostly in the ranges space.
Thank you, this matches my experience with similar code. To add to it: C++ compilers can often autovectorize your simple 0..N-1 for loop, no such luck if you're programming like this.
It's not always true. I observed an opposite effect in my experience. I had an acceleration when I rewrote a complicated 2D point traverse in an NFP algorithm with ranges. It was amazing, especially considering it was production code, not a toy example.
Excellent talk, grat subject, and really well presented!
40:09 I looked into it, and the inner-range of chunk_by is a std::ranges::subrange - which is typically a sized_range when its iterators are random-access - which is the case in this example (std::vector is random access) - so std::ranges::size will work here, but wouldn’t work if the input was (for example) a std::list or if (for example) a filter_view had been applied before the chunk_by. Interestingly enough, the constructor of std::ranges::subrange has an optional argument of type subrange_kind which can be used to make it sized - but chunk_by (as well as split, chunk) doesn’t have a mechanism to control the ‘kind’ of its subrange. I think it might’ve be worth adding such control to chunk_by.
GREAT TALK!!
cpp is becoming a functional lang, and I'm here for it.
Awesome talk, very well presented
1:08:19 the claim about ‘single-pass’ for the ranges solution relies on the fact that std::ranges::distance of each chunk_by subrange is O(1), I believe. I think this true in this case because the range is random access. If we used std::ranges::size instead, I think it would have caused the compiler to verify/enforce single-pass.
Amazing
42:10, cpp developers discovering pipe syntax going nuts, Elixir devs been chillin'
Nice Talk.
I love how each of his videos makes me understand the algorithms and standard library tools just a bit better. Like you really don't want to do this kind of data manipulation by hand, no matter how much someone who started at assembly tries to convince you iterating loops is more readable. This sushi example also made me read more of the documentation, discovering valarray from slice that I noticed when trying to find out about views::elements and the example ended up demonstrating to me how you can handle matrices as linear arrays and do operations like trace. Which is another step towards figuring out how to play with matrix algebra in C++.
One of the greatest horrors of criticizing someone in the professional field on youtube is that your nickname is forever immortalized on a lecture example of having errors and non-working code. I suppose it kinda reflects real life situations where you start thinking "should I say this out loud in public?" Personally the moment I learned range iteration, I tried to drop the int i = 0; i < size; i++ everywhere possible, because the times I haven't been paying enough attention when thinking of how to get the idea into a code and made those indexing mistakes that 1. should be obvious 2. aren't obvious at all. When you say "iterate through all of them" and maybe "while performing an operation on them" I choose that 100 times out of 100, just because I don't trust myself as a human to be perfect every time. And what do I hate more than getting the idea wrong? Getting the idea right but believing it's wrong because the code doesn't compile or gives wrong results because of some stupid detail and it takes hours to troubleshoot that I had i = 0 instead of i = 1 or the end of the container instead of end - 1 or something like that. It's so much time wasted on something that shouldn't have happened to begin with. Humans just aren't that good at tediously envisioning every single step in practice while remembering all the previous operations that may have altered what you're dealing with. What is good at that? Computer for sure. So why not let the computer do the work when you say "I want to process every value in this box". Someone has for sure written a better algorithm to do that than I could come up with. Or most others, because most people's job and life goal is not to optimize every detail in something that is supposed to actually do something useful, the focus is on getting that useful thing to work and do the thing, probably to let you focus on other thinking surrounding that basic tool, where you want to solve a dirty real life scenario.
I'm not sure if it's the engineering thinking versus someone else thinking, but I feel like it's rather common for engineers to think "I have a problem, I don't want to spend all of my time with the problem on finding the perfect pencil to get the markings on the paper looking just right. Instead I want to solve the problem and see if it's a good solution, if it's not I want to have time to come up with another". The goal is not to write the best nested for loop, it's to count those numbers for whatever you're doing. I always hated the loops for arithmetic operations especially because they are the opposite of easily readable. You would never in real life describe calculating a matrix by quoting the names of all the elements one by one, you'd just say that you want to sum them up in a specific way or whatever.
As a last comment I would make the point that obviously the length of scrutiny is in what your application is. Maybe it is the code that is the bottleneck in your massive project and you need to optimize it and write it in really fundamental way. But maybe your target is to get the code running without bugs, without noticeable memory issues and just continuing to implement features. Ready and tested solutions far outweigh your manual work in that case. And might actually still achieve the better performance in two minutes than your deep dive into fundamentals without hours of working it bug free and optimizing it.
1:05:04 I would have fixed the error by initializing `int max_run` to zero. (Often I'd use INT_MIN for such things, but run length is effectively unsigned). That way, all the logic (the min-operation in this case) stays unduplicated. The iteration start index would remain unchanged from the original. That said, it's a pretty immaterial difference between the two fixes.
Hi, thanks for the talk! I think the slides are still missing at the link (I was trying to find the godbolt links without copying them manually)
Thank you for your comment and bringing this to our attention. We shall rectify this asap.
Interesting talk! So has the author written a Q-to-C++23 converter? And could one embed such a convertor into Circle? (I know next to nothing about Circle so that may not be a well-formed or smart question.)
Great talk, thank you.
When you compare the different solutions at 1:11:00 - I remember someone telling me that using algorithms from the STL, compilers in general are much better in optimizing the code since they kind of "know" it much better than if you write your own for loops. Do you (or anyone else) know if this is actually true?
If it is, that would be another argument towards using stl ranges.
In general, yes. The algorithms represent a canonical form the compiler will encounter, while other forms will have to be mapped onto that; even if there exists a form that is correctly mapped, that just means the library will produce the same form. OpenMP uses a bunch of these patterns, and the compiler's inability to alert you when your logic doesn't match the pragmas demonstrates that it can't reliably recognize them.
I agree with @ChristianBrugger, the perf in that particular case is really bad.
Conor Hooekstra claims that the range version is bug free by design but if the list of sushi is of size 0 or 1 then adjacent_transform will return an empty range and ranges::max on empty ranges is Undefined Behavior.
I'm really surprised no one noticed this bug so far!
Conor Hooekstra addresses that 1:07:19 also the problem itself is undefined for sushi lists of size 0 or 1
Benchmarking would've been very useful and interesting to see in the presentation. Also, quite confused by some of the justifications; one moment saying it's parallelisable then at the end saying it isn't. Similarly the seemingly throwaway comment about violating the lambda, presumably meaning that this is incorrect code with UB?? So, "we can do this now," just doesn't seem true?
Syntactically i like it a lot though, and your combinators library looks excellent!
- There is nothing wrong with comparing solutions with other languages, but everything has its limits. If I was interested in Circle/Haskell/q syntax, I would watch videos about these languages.
- It's not fair to claim that a raw loop is poorly readable while also claiming that `transform($, _c(_sub_))` is well readable.
There is a place for both ranges and loops in C++. It would be nice if the advocates of functional programming would change their tone a bit and stop dictating what is cool and what is not.
Despite this, the presentation was interesting.
pairwise_transform is sometimes called scan in other programming languages
Scan and pairwise_transform are 2 different things. Look at haskell's map2 (pairwise_transform) and scan. It is not the same
I think scan() is typically referring to what C++ calls accumulate().
@@Roibarkan that's usually called fold
@@kilianvounckx9904 Which map2? Futhark has one, but Haskell calls that zipWith. They can do adjacent pairwise operations when combined with drop 1.
Folds are general enough to build scans with, but they are indeed different. That approach could easily go quadratic time.
I still don't understand why everyone is making such a fuss about this. All this functionality has existed in Boost and in ranges_v3 sicne a long time ago. The standard always takes 10/15 extra years to finally put stuff in the libary.
This moves a lot of complexity from the code into the language. There are tradeoffs in doing so but personally I don't think they're favorable. Complexity moved into the language effectively means into the compiler where generating tight simple code becomes a lot harder than compiling primitive C code that plays well with existing debuggers and any old compiler. Also that code doesn't even look like C++ anymore. All these combinator libraries and compiler extensions make it look like Haskell. Obviously this talk is by a Haskell programmer so they don't see it as a problem, but those of us who drank the FP kool-aid before realizing it is kool-aid don't see that as a good thing.
Agree. I learnt BASIC, (self taught in the early1980s), as an engineer was taught PASCAL at university first year (1987) then a crash course in FORTRAN because that's what industry actually uses, and I did use software written in FORTRAN and did do a bit of FORTRAN programming as part of my career. In early 2000s did some C++ programming to create applications to help out with my work. In 2018 went to open evenings for the Computer Science dept at a nearby university and the students were talking about Haskell and showing examples of how to implement some academic problem in the smallest number of lines, and I was thinking there is no way anyone is going to understand this a few days later, and this is not going to scale to an actual application. Honestly I don't understand the point of the problem here, (the 2 items of sushi) and the final C++ code makes no sense; I could probably work out what is happening with the original C++ code, (the for loop based version).
all_of was introduced in C++11, not 98.
I'm sure people have already pointed it out but the for loop version in sushi for two could be made way better
int sushi_for_two(const vector& fishes) {
int r = 0;
int last = -1;
int counts[2] = {0, 0};
for (int f : fishes) {
if (f != last) {
counts[f] = 1;
last = f;
} else {
counts[f]++;
}
r = max(r, min(counts[0], counts[1]));
}
return 2*r;
}
The ranges version is still way more readable
The hell is this piping nonsense!? I would understand chaining the functions with "." by having them as member functions of the range. But why pipes?? And why don't they work for all functions?? All the variadic functions could have been pipable by having the thing to the left of the pipe act as the first of the variadic parameters in the non-piped function, e.g.:
"nums | zip_transform(std::plus{}, nums);"
How would that be more confusing than the current implementation?? And let me finally get to my main point: *Why is everything one statement*?!?!?!? Did we forget what the blocks of statements are for? You know... the main part of the syntax of these languages... I thought we were supposed to write a block of statements in {} that indicates things that should happen in order. And let's not forget that when chaining the last operation (return, assignment, etc) is still at the top! I understand that people were confused when creating this language and didn't realise there should be a difference between code that says what things need to happen and code that says how the memory should be structured. So to use the intended way of ordering the operations you are forced to explicitly tell the compiler to allocate variables on the stack and even give them names. But then you also expect the compiler to optimise them all out. And there is no way to explicitly control this. Which to me is completely insane design.
So here is my quick fix: add a way to use the result of the last statement in the next (let's say we use $ as in Circle). Maybe there are some things that need to be considered in more complicated cases, but in this simple example:
auto sushi_for_two(std::vector sushi) {
chunk_by(sushi, _eq_);
transform($, distance);
pairwise_transform($, _min_);
return max($) * 2;
}
It's basically the Circle implementation but without the pipes and with the benefit of having a waaaaay broader and more useful functionality. And since those are separate statements you can easily add some code in the middle for debugging and stuff like that. As long as you remember to pass down the $ (maybe an actual use case for "," operator. Or a case where a named thing makes sense). No pointless named locals. No need to worry about whether those locals should be auto, const auto, auto &, auto &&, etc... And this is actually what you are trying to say with your syntax. But in a more convoluted way that doesn't order operations in a consistent way. You just want to take the last result and do something with it. But without nesting function calls. And with the ability to use the last result multiple times in the next operation.
That example with Sushi for Two using loops is really not that great, because for that particular problem, it can be done in half the lines you presented. First of, you do not need min temporary, just do max(max_so_far, min(a, b)). Use shorter variables. Two this nested if inside for loop is not needed. You can clearly see that these two if and else statements have same two last instruction. Then what remains is max of mins, or not changing max of mins. But if you do max(max_of_mins, min(whatever, 0)), it exactly the same as not changing it. I wrote it blindly optimally (single pass, no extra allocations), in 17 lines of code (ok in D, but it would be the same in C++) using loops, and it is readable.
I am guessing you are going to use chunk_by(equal{}), then do count, and do pairwise. Yeah, maybe.
Sure, with a bit of comment the ranges adaptor version is kind of nicer and optimal (no need to repeat stuff after the loop) and cute, but as any tool there is a tradeoff in readability and flexibility. (I.e. what if you want to debug code, things get messy).
I have been using Ranges in D for years, and you had this stuff in other languages (like Python, Haskell, Erlang, Elixir, Bash) for years or decades. And, not it is not necessarily easier or better or more readable. Still waiting for smart compilers to actually parallelize things.
int sushi4two(int[] fish) {
int prev_count = 0;
int current_type = -1;
int current_count = 0;
int max_found = 0;
foreach (i, f; fish) {
if (f == current_type) {
current_count++;
} else {
max_count = max(max_count, min(current_count, prev_count));
prev_count = current_count;
current_count = 1;
current_type = f;
}
}
max_count = max(max_count, min(current_count, prev_count));
return max_count * 2;
}
no need to duplicate the code for max_count at the end of the loop, just put that outside of the if statement
Great talk. Although, I like my C solution better.... The example is still a very good showcase for ranges and Circle.
int sushi_for_two(int sushi[], int N) {
int result = 0, n1 = 0, n2 = 0;
for (int i = 1; i
Yes! C gang > c++ gang
Exactly, I would write C code like that too for this problem. Easier to debug, easier for the compiler to generate good code, works on any old C compiler.
Here's a criticism that wasn't mentioned in the talk: How on Earth do you use gdb to see how your code executes step by step? The loop solution with 4 state variables is about a gazillion times easier to debug.
If you like Haskell, by all means program in Haskell. But I'm not going to incorporate this nonsense into my C++ code.
Good point, but I think that the typical way to debug this kind of code is not by stepping through it, but by interactively running variations of the algorithm on inputs that yield suspicious/incorrect results. For this methodology, the debugger should have interactive execution capabilities (e.g. godbolt like) and I hope such debuggers are on their way.
@@Roibarkan Interactively running on some inputs might be okay for this toy problem, but when our trading system crashes in the middle of the night and we are losing money, I need my debugger to just work. C++ programming is not [always] an amateur activity.
@@alonamaloh If instead of fusing all operations into a single chain of pipes, have intermediate views of what you have done over your range, then you can debug.
C++ Consortium: Let's take some of this half-assed functional kool-aid from other languages because we need some of our own.
There need to be more ways for people to write unmaintainable, hard to understand code. Gotta show em who's boss.
Loops are easier to understand, more flexible, and we know exactly what they do. EDIT: Also notice that the code below doesn't need to store the input anywhere, so it truly is O(1) in memory.
First try, about 5 minutes:
#include
int main() {
int n;
std::cin >> n;
int last = 0;
int length_previous = 0;
int length_current = 0;
int most = 0;
for (int i = 0; i < n; ++i) {
int fish_type;
std::cin >> fish_type;
if (fish_type == last)
length_current++;
else {
length_previous = length_current;
last = type;
length_current = 1;
}
int most_ending_here = std::min(length_previous, length_current);
if (most_ending_here > most)
most = most_cutting_here;
}
std::cout
You solved a different problem, the whole setup was a function with the signature "size_t sushi_for_two(std::vector sushi)" which is not matched in your code (this also means your "actual O(1)" is pointless, but I digress)
To your other claims, "easier to understand" is a matter of personal opinion but general opinion is against you here, and "we know exactly what they do" is just projecting your own lack of understanding. We do know exactly what ranges do, you just seem not to (perhaps watch the video). And finally, "more flexible" is just false. Your solution only accepts input from standard input and only outputs to standard output, in what universe is that flexible or easy to use?
But I do agree I think the solution is the video is perhaps a little overdone, and to your point it does not lend itself well to reading from standard input. But use ranges differently and you can get something like this.
template
size_t sushi_for_two(R&& sushi){
std::optional previous;
size_t current = 0, last = 0, most = 0;
for(const auto& fish : sushi){
if(previous == fish){
++current;
} else {
most = std::max(most, std::min(last, current));
last = current;
current = 1;
}
previous = fish;
}
return 2 * std::max(most, std::min(last, current));
}
In terms of readability it is about equivalent to your solution, but it is far more flexible. You can use any comparable type with any standard container or any input source with no additional overhead for modern compilers.
For example:
int main(){
// reading from standard input
size_t length;
std::cin >> length;
auto a = std::views::istream(std::cin) | std::views::take(length);
// using a vector
std::vector b = {2, 2, 1, 1, 1, 2, 2, 2, 2};
std::cout
This is insanity written by programmers who have probably never shipped a performant product in their lives, nor worked with commercial codebase before. What if you want to step through the algorithm in the debugger? You can't. A for loop version is far more readable, you can see the data being transformed in every step and a programmer not familiar with the problem solution can easily see what is happening.
Don't let people who code like this anywhere near your codebase. If you wan't to prototype features or get something working quickly, go nuts.
This style of programming (operations on ranges) is more expressive, since these operations have exact meanings known to all who use them (so you don't have to read the code to understand what it does). You don't need to verify the actual operations (you can assume "filter" works, "chunk_by" works, etc), only the high level business logic.
In the for-loop you have to make sure you don't off-by-one the loop counter, you have to read to the code to understand what it is trying to do (because you have directions on "how to do" something, not a simple description of "what to do") and you have to possibly manage allocations / copies / state yourself.
Do you think it's a coinsidence that APL / Q / etc are used by stock exchange companies and C++ is used by them and gets more of the same kind of features? It's because they are proven to work and produce correct, maintainable code. There is a slight overhead when onboarding new programmers, but the final productivity is obviously worth it.
Could argue your response is from someone who has never had to work on a complex enough system to make it worth the over head. Even high frequency trading firms will favor correctness over performance and while FP is often not more performant it can be less error prone and easier to conceptualize.
Do people really think for loops are better?, theyre ugly and verbose.
They are superior in every way. Easier to read, easier to debug and more performant on msvc compilers.
Pretty sure these algorithms are abstractions to keep you from having to rewrite the same loops anytime you need to repeat something. A very welcome abstraction, I might add. Plus with most algorithms they are composable. Another thing about algorithms is the compilers can design around them, which in turn can make them more performant in the long run.
@@GankablePlayer I don't know about you but I rarely write "the same loops anytime I need to repeat something". Often a loop starts out very simple but over time it grows. This is where a for-loop is more flexible in my opinion since it's trivial to add another step to it, or break out early, or adding an if-statement or nesting a for loop inside another. Often times you need to completely rewrite these pipelines to accomodate anything it was not initially written for. Or maybe you just decide to rewrite it as a for loop when you need to modify it. If I find myself typing (close to) the same loop logic multiple places I can extract it to a function.
template
int sushi_for_two(T fishes) {
if (fishes.empty())
return 0;
int result = 0;
int last_count = 0;
T::value_type last_fish = fishes[0];
int this_count = 0;
for (auto fish : fishes) {
if (fish == last_fish)
++this_count;
else {
result = std::min({result, last_count, this_count});
last_count = this_count;
this_count = 0;
last_fish = fish;
}
}
return std::min({result, last_count, this_count});
}