Back to Basics: (Range) Algorithms in C++ - Klaus Iglberger - CppCon 2023

https://www.youtube.com/watch?v=eJCA2fynzME

Transcrição

[00:00]

00:00 a lot of interesting stuff happens in the hallway it happens uh you you know you get to walk out of of a session and there's a collective experience that you just went through and so there will be a

[00:12]

00:12 hallway conversation that Springs up discussing the [Music] material first of all a wonderful good morning and welcome to this installment

[00:31]

00:31 of the Back to Basics track which is about algorithms so um few words about myself I'm doing zos trainings Consulting Etc and actually algorithms is one of the

[00:42]

00:42 topics I really love to talk about because it is an example for just good softw design and so this is just a perfect fit for the Back to Basics track so it all started in 1994 with his

[00:55]

00:55 paper paper entitled thus then attempted Library proposed by Alexander stenov for standardization in the standard library and in his paper he proposed what we today all know as first

[01:09]

01:09 the containers perap the interesting detail about the containers is that the containers do not contain a lot of algorithm like

[01:18]

01:18 functions so algorithms the second component are actually free functions completely separate for the containers and it was a very specific reason to do that because this this entire library to

[01:31]

01:31 be extendable yeah from a design point of view this is nice yeah so imagine you have a container and you want to add another algorithm you could not add anything to standard Vector it needs to

[01:43]

01:43 be something outside and the algorithms on the other hand they should not be bound too strongly to the containers of course um uh they should work on all containers even if you add a

[01:53]

01:53 new one so these concerns are perfectly separate good but they need to work together and this is what we of course do by means of iterators iterators is the abstraction level in between and um

[02:07]

02:07 this is how they work together now um on this level already this looks a little bit like a toolbox so all of this stuff works like little things that you

[02:22]

02:22 could put together and this is one reason why I like to talk about this sdl stuff and the algorithms because this is just good software design this is how software should look like I don't know

#recommended

[02:32]

02:32 it looks like playful stuff touchy toy but it's actually really really useful now in this talk we're going to talk about algorithms only unfortunately this year there's nothing on containers

[02:44]

02:44 um but there's another talk on iterators so if you wait till 2 p.m on today Nik suus will talk about the other part the iterator part and and you get a little more of a complete

[02:57]

02:57 picture all right so let's have a little bit fun with algorithms and The Simpsons yay okay I see there not a lot of Simpsons fans in the room it's probably too early I know but um we'll have

[03:14]

03:14 little fun with the Simpsons so let me introduce the cast for this talk first we have Lisa the algorithm expert then of course on the other side we have Bart the totally algorithm

[03:24]

03:24 ignorant skeptic and of course we also have Maggie the always interested C+ ver Enthusiast so let's let's uh first introduce a little struct person um so persons have first names last names and

[03:39]

03:39 an AG super simple not really something to to go into and we introduce an entire Vector of persons The Simpsons so um we have of course um Homer March Bar Le and Maggie The Simpsons but we have also a

[03:53]

03:53 couple of other characters from the show so H mman Ralph wiam millton n Flanders Jeff Albert Burns and potentially many many more yeah imagine that this is a vector of

[04:04]

04:04 say 50 perhaps even more Simpsons characters good now let's do something with this Vector of persons Bart has a first idea let me

[04:15]

04:15 find the youngest person in the vector of persons all right so how uh how can you do with this well first officially we should check uh if there's actually a

[04:28]

04:28 single person so if this is an empty Vector there's nothing to to really do okay else we first pick the first element as the the youngest person why not it's a

[04:42]

04:42 first good guess but then of course we go through all the other persons and we note this one this little detail we go to the kind of second element and from there till the end in single steps and

[04:55]

04:55 we compare the age of all the persons yeah if um if the age of any person we are currently at is smaller than the age of the currently smallest person youngest

[05:07]

05:07 person then we found a new youngest person and you do this until the end and then we found the youngest person ah great who is the youngest person well in this Vector of persons it's of course

[05:25]

05:25 Maggie but megie totally disapproves part solution now she really doesn't like that for many very good reasons first this is hard to read now I don't know how which code you

[05:39]

05:39 usually read but um I I would definitely argue this is not easy you really have to scan through all of these little details until you really understand what's going on here so it's hard to

[05:50]

05:50 understand too and now this is one single slide of code okay it's not a lot but imagine this on a big scale yeah programmers developers scanning this kind of code

[06:03]

06:03 every single day how many hours of last you do that and how many Bucks are introduced when somebody wants to add a little other detail this is innumerable this is really really

[06:14]

06:14 bad it's also very verbos okay as I said it only fills a single slide but still it's a lot of code for this simple problem and it's easy to get something wrong really I I pointed out a couple of

[06:28]

06:28 little details like the Plus here um the the comparison the Plus+ little little details something could go wrong and last but not least in this form definitely is not

[06:40]

06:40 reusable Magie disapproves Magie is not happy now Magie actually would use ah okay last last comment here the comment itself basically shows us that there's something wrong yeah find the youngest

[06:54]

06:54 person if you have to explain to developers what the next piece of code is doing something is wrong now Magie would use an algorithm so she goes to CP

[07:06]

07:06 reference and so immediately on the start page she actually have link to all the algorithms yeah it's it's right there right column third from top and then she clicks on that she comes to the

https://en.cppreference.com/w/cpp/algorithm

[07:17]

07:17 algorithms library page a huge page really a huge page this page contains probably don't believe it more than 200 algorithms 200

[07:30]

07:30 but we don't have to go through all of them that definitely is not not really an option we now looking for the youngest person in a vector of course there's no algorithm called youngest

[07:42]

07:42 person but if we generaliz this a little bit you realize that we looking for a minimum and there is an entire category of minimum maximum algorithms what we now looking for is this particular

[07:54]

07:54 algorithm Min element it says so right away it Returns the smallest element in a Range so if you go to any of these algorithms you'll find a lot of details

[08:06]

08:06 now for beginners this is sometimes indeed a little scary because the first thing you see is uh pretty much all the overloads with all the details right away but let's do this slowly first of

[08:18]

08:18 all most of the algorithms not all of them will come to that are defined in the algorithm header and then indeed it looks a little scary but in total there are just four overloads which have

[08:29]

08:29 changed over the standards so um you uh you do see the first algorithm has a little difference since C plus 17 which is essentially con exper so it's just four

[08:41]

08:41 functions what you're going to do is just to naively use the first one to get a little warm warmed up so I know Ed main element that takes two parameters and that's what we what all the

[08:51]

08:51 algorithms very commonly do that take two iterators in this case forward iterators yeah what forward iterator is this is what n Su this will talk about at 2

[09:02]

09:02 p.m. so we call Min element and pass the range of elements so the beginning of the table and the end of table and it returns an iterator to the smallest elements or the youngest person in our

[09:17]

09:17 example good this is simple but unfortunately doesn't compile just yet there is a little more to that so if you now go back and scroll down to

[09:29]

09:29 almost the end of the page you'll actually find the a possible implementation I should say that this is not the implementation that uh is used everywhere but it's in in implementation

[09:42]

09:42 that is reasonable it definitely shows what's going on so this implementation pretty much looks like what BART has implemented before it does a comparison of um the

[09:53]

09:53 iterators by convention if there's nothing we return last it picks the first element as as a first good guess goes to the next one and then continues on and then and

[10:05]

10:05 that's the point here add as a comparison by means of less than less than this is a pretty reasonable default but not all types can or should be compared by less them in

[10:19]

10:19 particular uh persons probably are not good candidates for less than operation now if I would tell you um person a is less than person B I think you would not really know what I

[10:31]

10:31 have in mind doesn't really make sense it's not intuitive it's not a natural relation and so some types just cannot be compared with less than so this algorithm doesn't work for

[10:42]

10:42 all parameters for all types I should say but this is why we have overloads the third overload of these Min element actually takes three parameters takes two iterators again but

[10:55]

10:55 it also takes a compare operation so this compare is just anything yeah really this could be a function pointer it could be a function object it could L that could be anything and this compare

[11:09]

11:09 operation gives you the ability to deal with this comparison you define from outside how the comparison should work so the comp object is called the two persons are passed and if this comp

[11:22]

11:22 object returns true then you have found a new youngest person if it returns false should just go on to the next one that's simple that's nice and it

[11:34]

11:34 gives you a lot of power it gives you the power to configure this algorithm to your needs okay now as somebody who likes to talk about softw design I have to point this out this is an example for

[11:45]

11:45 what we call a strategy design pattern you also commonly call this policy based design but it basically is a design pattern right here so meaning we just have to pass one more parameter so we

Marcador

[11:57]

11:57 still pass begin and end but we not also pass for instance a Lambda that now looks a little more scary again but essentially it's pretty straightforward you have just to follow

[12:09]

12:09 the convention you pass something that takes two persons and does a comparison in our case we need a comparison of AG so we uh just compare the AG value of the two persons and that works and this

[12:24]

12:24 is good Magie likes that because it's definitely easier to read now of course Skeptics like bark at this point would say this is not easy to read however please do not confuse complex

[12:39]

12:39 with unfamiliar for many people who do not use algorithms this is unfamiliar but once you get into the habit of using them it becomes familiar and suddenly it's really easy to read

[12:49]

12:49 you know exactly where to look and and this is nice and so it's also easy to understand much more quickly it's also much shorter instead of an entire um slide we now have a

[13:00]

13:00 couple of lines because have formed it for the slide essentially it's one statement this is nice it's also super difficult to get something wrong so in other words it's

[13:10]

13:10 easy to get right so I wouldn't know how to mess this up it it really is pretty difficult and it's reusable so Min element is something that you can use for all kinds

[13:22]

13:22 of um minimum elements not just for youngest persons good a lot of good points however as Lisa now perfectly points out we can even do better so what I've just

[13:36]

13:36 shown you is the classic algorithm the C++ 98 form of the algorithm it is great but today actually what recommend and Lisa would do the same thing stood ranges Min

[13:49]

13:49 element now let's take a look at CP reference first in order to get a little bit of an idea so first from an include point of view you don't have to change anything you just uh include algorithm

[14:00]

14:00 just as before then okay admittedly this looks scary it does that's from my perspective the one big disadvantage of the ranges forms unfortunately now you have to know

[14:14]

14:14 about Concepts and potentially forwarding references and about ah so many template related things the use is great yeah so stay with me so we have one form of M element that

[14:25]

14:25 takes to iterate this again the only thing that I now quickly point out that they don't have to be the same type anymore so we have an i and an S and this gives us more flexibility good then

[14:35]

14:35 we um take a comparator and something that is called a projection I'll show in a second how this works but then there's a second form which is really interesting yes I know that this is hard

[14:48]

14:48 to to understand and read but this R here that is some range something with begin and end and this is now what we're going to use

[14:59]

14:59 because this makes the code so much more pleasant to look at so Min element now just doesn't take begin and end it takes the vector itself the range the thing with begin and

[15:10]

15:10 end then as a comparator we now use less exactly the thing that didn't work before because I'm now also throwing in one of these projections I don't want to compare

[15:21]

15:21 persons as persons I actually want to compare the age value of a person and so all I'm now doing is I'm projecting persons onto their age value with this so you basically at this point provide a

[15:34]

15:34 pointer to member is this nice I think if you show this to somebody who has not seen this before this person might actually this

[15:43]

15:43 developer might actually guess what is is doing right away this is amazing absolutely amazing and so you can um can imagine that why why this is better there's even one more thing that we can

[15:56]

15:56 do because uh less is the default called anyway we can shortcut this to just an empty set of braces so it's even shorter and it's even harder to misuse there is no begin there's no end I

[16:11]

16:11 really would not know how to mess this up this is correct kind of by by Design good and now that that we have this the commment is totally Superfluous we can just remove that people can read

[16:24]

16:24 that and Magie is super happy all right so first impression but let's uh oh yeah of course the quote from the expert the

[16:37]

16:37 quote that everybody in the community knows and so should you should know it as well the quote from Sean pent from a talk in 2013 a talk is called C+ seasoning so this is what Johan had to

[16:47]

16:47 say in this talk if you want to improve code quality in your organization I would say take all your coding guidelines and replace them with

[16:58]

16:58 one goal no raw lips this will make the biggest change in code quality within your organization perhaps you have a little bit of an idea why that is we came from

[17:10]

17:10 a very complex code that was hard to understand to something that is hard to misuse in any way this is brilliant this is really better code quality all right but next little um

[17:23]

17:23 task right has a new idea because he's not convinced just yet uh no let me put all the children to the beginning of the vector okay Bart starts to code again first he just uh picks the begin and end

[17:37]

17:37 I calls them first and last why not then he does a y Loop but now wants to find the first adult in in a vector so we now Traverse the elements while we are not at the end

[17:53]

17:53 that's this part and while we have a children and you define yourself what child means and so we move on as long as this is true so inde we we continue until we hit the first

[18:07]

18:07 adult now if I explain it this way I think everybody nods and say yeah sure this is clear but if you would have to read this I'm not sure if you would immediately understand what this is

[18:18]

18:18 doing because it's kind of counterintuitive it says is child but actually we're trying to find the the opposite we're trying to find an adult it's kind of weird

[18:29]

18:29 Okay then if if you're not at the end we just continue with the remaining elements now first has been incremented to the first adult so we now continue with the next element the next person

[18:43]

18:43 till the end and check oh this is a typo so check is child of course is child so if this is a child then we swap so first currently is

[18:55]

18:55 at the first um um at adult we have found the next child so we swap and go on with the next element okay so this this works right does

[19:11]

19:11 it are we sure it's hard to say right again it's not a lot of code but it looks complex it looks difficult to understand so again of course Magie is a

[19:26]

19:26 little disappointed this is not really what she was looking for or hoping for but let's try to to to make this better yeah because again definitely there's something to improve there's

[19:36]

19:36 again a comment and and if there's a comment that tries to explain what is happening there is something wrong so let's look for patterns these three lines

[19:48]

19:48 here this is a very common pattern indeed pattern that we use all over the all over code base this is essentially a swap however it's a special swap because we

[20:00]

20:00 don't want to swap iterators we want to swap the thing behind the iterators the persons so that's an eer swap that's an algorithm nice so the code gets a little

[20:14]

20:14 shorter the Y loop I would say the Y Loop is again a very very common pattern we're trying to find a specific element we're trying to find an element that is not a child

[20:30]

20:30 find an element that is not that's a find if not so we tried to find the first element that is not a child nice again a lot of complexity has just vanished has

[20:42]

20:42 disappeared and it's readable so there a lot of little algorithms hidden in this piece of code but still there is the oh sorry yeah nice side remark we can pass the the the

[20:58]

20:58 function pointer here this is okay this will compile and work but without going into too much detail it is advisable to use some function object like a Lambda has to do with performance yeah this is

[21:11]

21:11 easier to inline for the compiler so it really is advisable to use Lambda although it essentially also just calls is child now for for more information please see corland

[21:23]

21:23 t40 but essentially we're not there yet it still is quite a block of code uh and a common still indicates that it can do better this entire construct here is just to put all the children to the

[21:36]

21:36 beginning and all the other persons to the end yes that's another algorithm that's that looks like a partition and it really is so instead of

[21:49]

21:49 doing all of this stuff mentally we just call partition from first to last again and then we call uh we pass Al that just tells the um the the partition algorithm

[22:01]

22:01 what do we consider to be the the interesting kind of person so we are looking for children so partition takes a look at all the

[22:12]

22:12 elements and all the elements that ader to this given predicate or is child Lambda all of these elements are put to the front and all the other elements are just put to the back very simple so it's

[22:25]

22:25 not a sword or anything this is what we call a partition and I would claim I think other people would too that this is just common knowledge common terminology for all C++

[22:36]

22:36 delivers probably even Beyond C++ everybody should know what a partition is and so if you now see this code you should immediately know what this is doing this is just putting all the

[22:47]

22:47 children first but you also realize that algorithms are just using algorithms so it's it's a building block yeah little algorithms are used in big algorithms

[22:58]

22:58 that are used in even bigger algorithms that's good software design and so you can use your the standard algorithms in your algorithms in order to just create bigger more complex

[23:10]

23:10 things great again though we can do better we can use the C++ 20 form so ranges partition and of course the the the difference seems to be a little small

[23:24]

23:24 but again we don't have to pass begin and end we pass the vector right way and we don't have to fiddle with uh begin and end anymore pretty cool and again oops Yeah it's easy to read it's easy to

[23:38]

23:38 understand as soon as you know what a partition is this is kind of trivial code this is great it's definitely not verbose it's again one statement just to De formating four lines of code only

[23:50]

23:50 it's super easy to get right and it's perfectly reusable perfectly reusable let's let's imagine that we do not want the children first but say the

[24:01]

24:01 the senior citizens all we have to do is to just to make a change in one little place amazing that's usually the hardest thing with that we do in code yeah changing things and if you can do it

[24:14]

24:14 this simply I would say this is a really really amazing Improvement yeah to the complex form that b implemented first that's perfect reuse indeed however but is always the

[24:30]

24:30 critic what if I wanted to keep the previous order of the senior citizens could I do this as is simply well

[24:40]

24:40 um we don't have to reinvent anything we don't have to reimplement everything that's the perfect opportunity for another kind of partition something that we call stable

[24:51]

24:51 partition because there's not just one partition algorithm actually there's quite a lot of them so if you um go to CP reference again you'll find that partitioning operations is well quite a

[25:04]

25:04 sequence of algorithms partition is one of them so it's ranges partition but there also something called Partition copy and stable partition and partition point is partitioned also many of them

[25:16]

25:16 many of them they always carry the name partition in the in the name and this is good because it is terminology that everybody will understand it is something that we can

[25:27]

25:27 used to communicate in code this is great it's consistent and all of these different partitions are just are separated by means of different uh prefixes or

[25:39]

25:39 suffixes so the stable prefix tells you I'm going to keep the previous order of the first group and and the second group and again this is something that is very recurring in the algorithms you will

[25:51]

25:51 find that there is at least one other stable algorithm stable sort that has the same property the stable promises you that the previous um um order of in the case of

[26:02]

26:02 Sword equal elements uh is is kept good so all of these prefix and suffixes have fixed meaning so we have a very consistent naming very very good although I should admit it's not perfect

[26:15]

26:15 a few algorithms that are not perfectly named yeah we should rename them or provide something else but it's pretty good yeah it's it's there's more uh reason to be happy than than not

[26:28]

26:28 even Barre this is pretty cool however B kind of has a new challenge what if I now wanted to put the senior citizens last without changing their order based on on the

[26:42]

26:42 stable partition we have called before now that that is a rotate okay and this is now again a quote from this talk you have to

[26:52]

26:52 understand that I have to put this in this talk too that's a rotate is is something that that you have to say in every algorithm talk but it really is a rotate so we now take the return value

[27:05]

27:05 of stable partition gives us the so-called partition point and so this is the beginning of the second group or of course um also the end of the first group and we put this into the next

[27:17]

27:17 algorithm so we rotate from everything from begin to end such that this pass is the new first element nice it's a single function it's super

[27:32]

27:32 clear and it works however although it's simple and El of course what would happen if we would pass pass last what if we would do

[27:50]

27:50 this that would be UB undefined behavior all these algorith have some preconditions rotate for instance expects that you pass begin and end so

[28:03]

28:03 the complete range is the first and the third parameter this the the iterator in the middle is supposed to be something valid in the range from begin to end now in

[28:14]

28:14 this case it's kind of simple to mess this up because most algorithms take begin and end first and if you pass pass last unfortunately you have no specified that the range is from begin to pass an

[28:25]

28:25 end is not inside the range from begin to PA at least not likely yeah very it's very unlikely so this is a bug so in another words there are a

[28:36]

28:36 couple of small pitfalls that you have to remember this particular Pitfall though does not happen if you st C+ 20 form again ranges rotate so you just pass the table and pass and everything's

[28:48]

28:48 perfect and so this is why I would definitely argue prefer to use the new forms they're a little more flexible they can do more and they also protect you from the few uh problems that um

[29:01]

29:01 that we may have with the old algorithms okay third problem now B wants to sum up the age of all

[29:15]

29:15 persons that's simple right that's that's just a for Loop so we start with a total H and H was int so we have an total h of int and then there's a for Loop of course a range based full loop

[29:28]

29:28 we Travers all the persons in the table and we just add the the H value oh total age sorry total age here and we print the total age cool that was simple and even Lisa is not

[29:45]

29:45 entirely against that it's not entirely bad it's short it's clear but yeah we could also use an algorithm here we could use accumulate accumulate so now this is one of the

[30:01]

30:01 first algorithms that is not in the algorithm header it's in the numeric header so there something to keep in mind there are a couple of special algorithms that yeah a little more

[30:09]

30:09 numerical there in a in a special place and then accumulate itself takes two iterators and an initial value in it so essentially we we have to tell accumulate where where it starts this in

[30:26]

30:26 it is the the thing that it uses to accumulate there's a second form however that allows us to also additionally provide a binary operation so why is that well let's

[30:39]

30:39 again take a look at the possible implementation so the first accumulate is is really nothing but a full loop a simple full loop that goes through all the

[30:49]

30:49 elements and adds onto this init value ignore the move not so important all the the elements of this range all right but again this does not work for our purpose because we don't want to

[31:03]

31:03 add persons to integers doesn't really work now we could add an addition operator yeah that did the default we could say int plus person uh write an operator for in plus

[31:15]

31:15 per this is not really natural again it's not really intuitive that's why accumulate also comes in the second form so we provide a binary operation that allows us to reduce these two elements

[31:28]

31:28 so we pass unit value and the next person to this operation and this operation gives us the next uh value and so we do this for all the persons until we have a final value so we accumulate

[31:42]

31:42 reduce all of these these values the one thing that you now have to kind of remember is that op doesn't change any of these inputs it returns in new value it really is like an addition

[31:54]

31:54 operator but once you kind of understand that it's not so difficult to do the right thing so we call accumulate we pass begin and end we pass

[32:08]

32:08 the initial value for some the value zero is not not entirely bad so this is pretty reasonable of course and then we passed this addition operator again comely done by means of a Lambda so the

[32:22]

32:22 order is important you first pass the um the uh you have a parameter of the type of the accumulator so INT in our case second is of the type of the parameter of the of

[32:35]

32:35 the values in the in Vector person and inside you just do the according addition h plus p. H great and this is what we could print of

[32:49]

32:49 course so this works but now of course the skeptic um part is like exactly is this better the F was simpler right it was less code and this is definitely something

[33:04]

33:04 that you will hear a lot when you when you start to use algorithm why is this really better however there is a pretty strong argument in this case look at the con indeed before with a followup we

[33:16]

33:16 couldn't make this cons because that the H value was changed but now we can actually make this Con and as AO it's a very common anti pattern the so-called itm anti pattern it team standing for

[33:28]

33:28 initialize then modify initialize and modify is this usual and so this is this is the anti pattern that Kor hstar talked about a couple of years ago very very uh often

[33:40]

33:40 so it really is an anti pattern it's the anti pattern that you first have some local variable and change it throughout the function and then eventually you do something with it most of the time

[33:51]

33:51 however we can implement this by sitting it once and then reading it only this is good it again makes the code easier to understand it communicates and it is a safety mechanism of course so prefer to

[34:06]

34:06 keep things immutable and the algorithm kind of gives you that for free this helps definitely this is good B is not convinced yet and he asked the one question that

[34:20]

34:20 you also hear a lot when you start use algorithms what about performance ah performance of course S Plus is deler this is something that many people care

[34:32]

34:32 about and of course the the usual argument is isn't the full loop faster it's simpler right so it should be faster okay challenge accepted let's take let's compare the two solutions the

[34:44]

34:44 full loop with the accumulate and I don't do a benchmark it's actually something far simpler in this context we can just um take a look at godbolt

[34:58]

34:58 so this is now um uh perhaps a little small I apologize but this is was the only way to make this work so on the left hand side we have the sum function that takes a vector of values and we use

[35:10]

35:10 a for Loop to to sum up all the values yeah in the end we return the final result okay simple little function on the right you see the quing assembly code I'm using clang 16 which does mean

[35:23]

35:23 that this is the one is just an example and it worked out well for me and of course I use optimization and that that's a little bit the point here we want it to be

[35:34]

35:34 fast all right now next slide I'm kind of doing the same for accumulate so I kind of um have the same function signature again I have a value oh I could have gotten rid of this and I

[35:50]

35:50 return the um the result of accumulate okay but watch the right hand side I now go back and forth between the two versions um couple of times watch the right hand

[36:04]

36:04 side so I go back and forth and back and forth and once more and there's no difference right there is no difference it's the same code okay if little less colors I I I know but it's

[36:22]

36:22 the same code so it really does make a difference for the compiler where they use the gthm or the full loop so basically you can choose whatever is more expressive what whatever is better

[36:32]

36:32 from a um coding point of view amazing so there's no performance argument in this case absolutely not wow they are fast and elegant I'm deeply

[36:46]

36:46 impressed I'm still wondering why accumulate is a complex and indeed accumulate perhaps is a little special it feels a little complex for what it actually

[36:57]

36:57 does it could be simpler absolutely however um this is now again perhaps a little reminder where it comes from so the or STL paper from 1994 actually proposed something that was a

[37:09]

37:09 research library at that time a research library for generic programming and the goal was to make things generic General as much as possible accumulate actually turns out

[37:21]

37:21 to be the most generic perhaps the most General algorithm that we have in the entire sdl and really you can do amazing things not necessarily useful or good things but amazing things with that and

[37:32]

37:32 as has been demonstrated by bendine in 2016 so he has spent 60 Minutes on just talking about what accumulate can do so you can actually use accumulate to find things even to sort things and no no no

[37:44]

37:44 I would not advise to do it but it is possible because of the way it is uh it is implemented so okay it may not be as simple as it can be but it is amazingly

[37:55]

37:55 comp um powerful cool and it's perfectly reusable again of course so let's use this on a vector of floating Point values and indeed we now have a vector of

[38:07]

38:07 doubles and we we just want to sum up all the doubles yeah begin of the values and values zero and it is another bug it it really happens

[38:23]

38:23 easily the initial value the zero there is a little Oddity about accumulate that you please should remember I glanced over this before a

[38:37]

38:37 little bit um so now let's take a look a closer look at this this initial value is deduced so this is some T can be int can be double can be something in other words the thing that you pass the value

[38:48]

38:48 that you provide that defines the type of this T but this is not just it this T is now used as a return type so whatever you pass to accumulate will be the return type that's actually part of why

[39:04]

39:04 it's a powerful you can pretty much decide how it works but unfortunately this also means that you have to pay a little bit of attention which value you provide so

[39:15]

39:15 zero is definitely not the right choice for accumulating double values so what you should definitely do is to provide something like 0. Z or if you're lazy do Z or zero dot only but

[39:28]

39:28 you have to provide a double value now since this is a common trap common Pitfall perhaps there is one one more thing that we can do to um to improve on that I would propose that

[39:42]

39:42 well not just me even Lisa would propose that you explicitly mention the type at this point so instead of passing literal you pass for instance double empty set of um uh braces and it does the same

[39:55]

39:55 thing but it makes the type that you provide more visible and so if somebody comes along and does a copy and paste and unfortunately this is still done a lot um then it's not the zero that is

[40:07]

40:07 copied along and forgotten it's the type and because it's more visible perhaps the other person will adapt this accordingly slightly safer all

[40:20]

40:20 right what if I wanted to speed this up with many threats another perform argument of course well then unfortunately you're out of luck with accumulate accumulate

[40:33]

40:33 promises and this really is a guarantee that everything is summed up or reduced from left to right this is a strong guarantee which actually you can of course also utilize to your advantage so

[40:45]

40:45 if you have double values you can could sort them from small to large and you could sum this up from the small to the large and this would be more accurate of course this is

[40:54]

40:54 good but you can still paralyze you would use C+ 17 to reduce instead so reduce reduce is super similar to accumulate it's also first of all in the

[41:10]

41:10 numeric of course but then it it really looks the same it has the same interface yeah two iterators and an initial value of type t or which also makes the return type but reduce does not promise

[41:25]

41:25 anything it doesn't promise um that anything is wrong it doesn't promise that it sums up from left to right any order is possible there's another overload that

[41:37]

41:37 actually will come in handy in just a bit you see that we only passed first and last and that the def the the init value is kind of chosen automatically nice but the thing that I'm now after is

[41:50]

41:50 the second overload we pass first and last but before before that we pass an execution policy and that's a pretty amazing detail execution policy you'll find find

[42:05]

42:05 out about the execution policy at the very top of the uh algorithm page um and that explains what what possibilities you have so today in C 20 we have four different execution

[42:17]

42:17 policies first seek sequential okay that's the default it's nothing special nothing uh different would happen we have par parallel threat parallel to be precise we have par and

[42:31]

42:31 seek parallel by threats and by means of instructions so simd operations and since C+ is 20 um we also have un seek so you could paralyze by means of sim instructions per

[42:44]

42:44 se and all you now have to do in order to make this parallel is to just provide an execution policy so we would call reduce with for instance do execution par

[42:57]

42:57 that's it and then we would provide begin and end and potentially if you want to also an initial value that's it that's all you have to do in order to make this accumulation

[43:09]

43:09 this reduction operation parallel so simple it's so again you cannot do anything wrong of course the HPC uh Enthusiast is a little disappointed because there is

[43:23]

43:23 very little that very few knobs to do something you cannot explicitly pin the threats you cannot explicitly deal um deal with the details but this is good enough to just make it

[43:34]

43:34 parallel to just speed it up just works out of the box pretty cool indeed of course I said this before for reduce you can also just drop the initial value which makes it even

[43:47]

43:47 simpler yeah you cannot um accidentally do use the wrong um uh initial value here that's pretty cool indeed now so even Barett loves this quite a lot now going back to this this

[44:06]

44:06 quote you remember that John perin explicit said no raw Loops this is something that you will hear a lot in the community for good reasons I just now realize it's simple

[44:17]

44:17 it's it's correct it's efficient It's a Wonderful all-in-one package but I thought we now agree that this is good does this mean that we should not use four and Y Loops anymore is it bad

[44:31]

44:31 from today's perspective to use a full loop well this is what many people kind of claim and of course there are good reasons to use them but even in the in the talk of Jean um there are some

[44:42]

44:42 answers so okay examples so let's assume that we want to just print the persons now let's assume we have some output operator for persons okay we could actually do this

[44:55]

44:55 with a copy stood copy an algorithm would provide begin and end but now copy needs another range that it copies to want to print this so we now have to a little artificially uh

[45:09]

45:09 pretend that we have a range with an O stream iterator that we pass see out and perhaps something as a delimiter okay it works it's not particularly beautiful we could Al

[45:22]

45:22 alternatively use a for each so we could use uh begin and end again as the first two parameters and then provide a Lambda that well prints the given person also okay definitely much more

[45:34]

45:34 Cod than a range based fall Loop this is simple this is short so so why not just use that however as Lisa now tells us it

[45:50]

45:50 definitely helps to know the algorithms but it's not forbidden to use fups no no no no no and this is um um kind of the definition so if there's simple and short everything's

[46:01]

46:01 fine this is what um you'll find in the C+ a seasoning talk in the first half hour there there's more in this talk but there is actually a slide that defines what a raw loop is and not every Loop is

[46:12]

46:12 a for Loop a raw Loop you can definitely use for Loops if that's right here if it is short and simple if people can take a look at this and understand immediately what's going

[46:28]

46:28 on so if for instance you have just a single statement perhaps two function calls perhaps also successive function calls if you combine them this is okay this is fine so this does not mean that

[46:42]

46:42 four y Loops also are bad but they should be simple they should be understandable they should be maintainable and perhaps to give another expert a chance to also have a say turn

[46:53]

46:53 Earth defined it this way 9 times out of 10 a full loop should either be the only code in a function or the only code in the loop should be a function or even both so simple for Loops are perfectly

[47:08]

47:08 fine perfectly okay right now I just love these algorithms but there's so many more than 200 in C+ 20 how how can I learn more about

[47:22]

47:22 them well this is an excellent question indeed and there are a couple of great talks to watch to continue the journey so first of all I mentioned it a couple of times but now I would recommend C+

[47:33]

47:33 seasoning the first half hour there's actually more in this talk uh it's kind of three topics that I addressed but the first half hour has become probably the most um um well well known this is a

[47:44]

47:44 fantastic example for why algorithms help that's kind of the I would say the initial talk that showed the community why they're just great there's another talk though that I

[47:55]

47:55 really recommend 105 sdl algorithms in less than an hour by Jonathan bukara very famous talk indeed but for very good reasons this is not a talk so don't be don't be um

[48:07]

48:07 afraid to to watch this yeah 60 Minutes 105 s algorithms he does not do um um an algorithm in 40 seconds each no no no no what he's doing is he gives you the overview now which algorithms are

[48:20]

48:20 available and this is prior to C 20 so it's half of them C 20 kind of doubl the number this gives you the overview which algorithms are available how they're connected how they

[48:31]

48:31 interact and after this overview I believe you you kind of have an idea what you can use what is available if you're a little more into um how to use them how to apply

[48:44]

48:44 them then I would recommend algorithm intuition from Connor HRA actually this is two talks this is part one of two and that's of course the second part but he tries to actually use

[48:55]

48:55 them for well problems this is a great way to see how they also interact yeah sometimes you have to use several algorithms sometimes you have to combine them but

[49:06]

49:06 the resulting code is really really nice really readable and intuitive here also this is the specialty of Conor uh Compares this with other program languages and the nice

[49:17]

49:17 thing is C++ is not bad indeed he concludes that what we have is pretty a really wonderful tool so the guidelines and takeaways don't be like Bart and write

[49:31]

49:31 all of your four wi Loops manually prefer to use algorithms ouch this hurts a little but I see that you're right algorithms are simple elegant fast and removes so much

[49:45]

49:45 potential for errors which is the last Point alone uh definitely a reason to to take a close look at this then please prefer to use the C+ 20 ranges algorithms they're even simpler

[49:58]

49:58 they also give you a couple more options um it just requires C plus 20 um compiler and to what I've heard uh still a lot of people cannot use C+ 20 yet so do use algorithms and as soon as you

[50:12]

50:12 upgrade your compiler c+2 just take a look around um an upgrade to c+2 ranges algorithms then remember conventions and a few pitfalls there definitely conventions I

[50:25]

50:25 mention most of them or few of them definitely but they unfortunately also a few pitfalls especially in the old version please just remember them and uh yeah

[50:36]

50:36 then then everything should be great and so learn more about algorithms it really is from a strategic Point View one of the best things that it can do to improve the quality of your

[50:50]

50:50 code all right now this there's only one last question one last question because um yeah else you you hang out the entire day and you don't know what to do okay I know you

[51:04]

51:04 would use Google but um we can clarify this right away and I think then then you can sleep well also so who is Jeff Albertson I know this is what you have

[51:16]

51:16 been asking yourself the entire talk yeah this is why you looked so so confused a little bit everyone is known except for this one okay who's Jeff Albertson

[51:26]

51:26 okay I knew it h I'll help you the comic book guy all right thank [Applause] you so we have a couple of minutes for

[51:46]

51:46 questions if you have any please feel free so hello great um back to the SL

[52:00]

52:00 partition okay perhaps this is quicker oh my I did not practice where exactly my my slides are so this okay partition range is partition right no not yet no

[52:22]

52:22 noine this one what what should it not be director I didn't get it sorry the I could just write that's correct you could pass anything that is callable that takes a

[52:44]

52:44 person of course or something that's convertible to that takes a person you have persons something that it could convert to um but it must be callable that's the convention this is what the

[52:54]

52:54 algorithm uses inside I said that you should prefer Lambda though because really this makes it easier for the compiler to inline the call so a the calling is child directly

[53:05]

53:05 might end up with really function calls the Lambda here will be inlined definitely so it's it's a performance argument not what you can do yes

[53:19]

53:19 yeah hi I've noticed a convention uh both in your books and here that you use begin my table and my table as opposed to my table table is there a specific reason why you prer that over the other

[53:32]

53:32 one there is a reason um if you use do begin then you always assume this is a container with beginning and member functions which is great I think this is what we use most

[53:45]

53:45 of the time but now let's assume this perhaps a little weird reason that we have to use a build-in array a buildin array would not have member functions doesn't have any members with be so the

[53:56]

53:56 free function begin and end this would still work so this is a little more generic it kind of shows that free functions are I would say the backbone of generic programming this is how it

[54:06]

54:06 just works better yeah thank you all right um El yes it does in R is notor

[54:26]

54:26 yeah absolutely you have you correct I could do that too but very strong reason I had to show rotate yeah that's a rotate I I worked hard to make this happen so hi I want to know I

[54:46]

54:46 have reason contain and then automatically get begin and to say out every time so yeah exactly this is why one reasons one of many reasons why I propose said

[55:02]

55:02 that the C 20 forms are better now this is less fuss for you but if for some reason people have to use the old versions want to use them perhaps sometimes you just want to uh sort half

[55:13]

55:13 of the range not not the entire range then um I would prefer the free functions for for the reason I just explained yeah all right right thank you for

[55:26]

55:26 the question to call from lamb directly so um it is a performance argument if you pass so if you use his

[55:40]

55:40 child directly I didn't show it I admit but let's assume it's a function plane function then you would pass a function pointer any kind of pointer for the compiler is a an obstacle it cannot

[55:53]

55:53 inline as easily I do not claim that it never in lines that that is wrong sometimes it definitely happens but it's harder for the compiler and so this it definitely helps

[56:03]

56:03 if you just wrap this in a Lambda then it will be inlined with 100% guarantee as soon as you go to one this is inlined It's so [Music]

[56:18]

56:18 simple it's not very for me to read element so it's not I think because it's like this form oh the for example I think here it's not

[56:45]

56:45 very intive that it adds the H okay I agree it's it's names generally addition multiplication is we call them reduction operations it's kind of a computer

[56:59]

56:59 science term so from that perspective reduce is a nice term but it's not clear that the default is addition yeah exactly yeah um I agree perhaps this is just one thing that you know have to

[57:11]

57:11 remember keep in the back of your mind if accumulate is not wrong you can use accumulate too just remember that it's not paralyzable absolutely it definitely

[57:23]

57:23 would work yeah thank you all right so hi that's true as good as it's better than the code and any that I should be aware so I

[57:49]

57:49 would assume yes it is as good but if you truly are worried about performance the one thing that you you have to do is to Benchmark yeah this is the one and only guideline that I can give you um so

[57:59]

57:59 if you're worried Benchmark and if you do find that the algorithm is not as efficient if your full loop whatever is better then first thing about whether you perhaps can exploit a special case

[58:12]

58:12 and of course use your for Loop but please do not um just leave the for Loop in some other code block now make it a separate function perhaps implement it in algorith like fashion to enable reuse

[58:24]

58:24 and give it a good name of course um but if you feel like this is the general case I have a better solution and you're convinced that everything's correct then why not file a bug report with your

[58:35]

58:35 compiler vendor to say actually this is not as good as I want it to be I think there's a perfect legitimate reason to to to do that yeah all right

[58:48]

58:48 hi oh this is something I missed very good question thank you there's not there is not not um the in C+ 20 the numeric algorithm so everything in stood numeric was not um

[59:01]

59:01 upgraded the reason is uh to my best knowledge this time they didn't have the time to do that um so no unfortunately not yeah all right this is s 23 yeah but okay I

[59:18]

59:18 should mention this too thank you in C 23 add-on we have them but they have different names F left fault right correct thank you all right with that have a great day

[59:29]

59:29 enjoy the [Applause] conference