The fastest way to iterate a List in C# is NOT what you think

hello everybody i'm nick and in this video i'm going to show you the fastest and also the most memory efficient way to iterate lists in c sharp working with lists in c sharp is extremely common they're everywhere just because of how easy they are to work with to add data and remove data just because they are a verbal length as opposed to arrays which are fixed and they're very tricky to copy and change and the lists are great however one of the most common things we do with lists are iterating them now you might think you know what's the fastest way to iterate a list but i can guarantee you it is not that just for looping a list is not the fastest way to do it so in this video we're gonna see all the ways we can iterate a list and then by the end of it you will know the fastest and most memory efficient way to do it if you like them of content and you want to see more make sure you subscribe during the summer notification bell and for more training check out nickchopsters.com all right so let me show you what i have here i have a simple console application it has nothing in here and the first thing i'm going to do is add benchmark.net because this will be very benchmark heavy this video actually i have added benchmark.net already and i'm going to go ahead and add my benchmarks class i'm going to say benchmarks over here and i'm going to put all the ways you can basically iterate a list here now i'm going to slap a memory diagnosis on those benchmarks because i'm very interested to see how much memory these tests will allocate now because i want this benchmarks to be as objective and realistic as possible i'm going to add a randomizer for this benchmarks to generate different sets of data every single time and i'm going to add also a seed which will help this data be the exact same on every iteration even though it is random and then what i'm going to need is a size that i want to run for so a list of a specific size we're going to default this to 100 and we're going to change as we go and then i need a private read-only list of integers that's what we're gonna run this against items here we go and then we're gonna have a global setup method which will initialize the array so public void setup goes here and then since this is not the constructor i need to remove the read only and then it looks like this we have items and we set that to an enumerable.range and we select a random number random integer and we to list that and this is the list we're going to iterate now we're going to start with the two most common approaches to iterate a list one is the for loop and one is the for each loop so the follow would look something like this i'm just iterating on the count and i'm getting an item from that for loop i'm not really doing anything with the item but it will still be there if i build this in release mode and i show you the il code you will see that the item is actually retrieved with the get item method so it's not actually removed and then we're gonna have the for each method over here and again this is very straightforward we iterate with a four inch loop and we get the item back now what i want to do is go in the program.cs and say benchmark runner dot run and i'm going to run the benchmarks for 100 items all right so results are back and let's see what we have here so as you can see 4 is slightly faster than for each however what i also want to show you is how this scales as the size of the collection also scales because this doesn't actually tell the whole story so i'm going to remove 100 from here and add the params attribute and say i want this for 100 also for 100 000 and also for 1 million and now let's see how based on the size the performance actually changes so this will run two tests three times with different sizes let's go ahead and see that again all right so results are back and let's see what we have here so for the for loop 100 items 45 nanoseconds for the forage 47 nanoseconds then the difference kind of fades away in the 100 000 items and then we slightly see it again in a few microseconds actually half microsecond for 1 million items so there is a small difference as you can see but it's not really visible here but i want to show you why this difference exists so we're going to go ahead and see how the code is lowered in shoplab.io so what i have here is shoplab.io it will allow me to see how my code from the left the high level c sharp will be lowered to low level c sharp so if i go ahead and i create a for each loop and i save our item in items and i see what code this converts into you can see that it creates an enumerator over here using the get enumerator method and then it uses a while loop with the move next to get the current item and then it also adds a final block to dispose of that numerator now if i go ahead and add a for loop over here then as you can see that for loop is actually lowered converted into a while loop with the items.count and then we're getting the item with a lookup directly over here so as you can see it's generating different code and this version of the code is slightly more efficient now in terms of memory they are the same now if we go back here these are obviously two of the most basic ways and common ways to iterate a list however we have a few more exotic ways to do the same thing and let's take a look at those so the first thing i'd like to take a look at is the for each link method because if i go and say for each link then i can have items dot for each which is a list method and say item and then have the lambda and do something with the item so that's one of the things i can have i also have access to parallel methods so this adds multi-threading into the mix you can say benchmark and you can have public void parallel for each which you probably are aware of you can say parallel dot for each and then you pass down the items and then you have a delegate that can use the item and do whatever you want in this block and you can even customize the way this is parallelized and you can also have parallel link what you can do is say public void error link you can say items as parallel for all which is the for each alternative in the parallelized workflow and you can get the item and do something with it here so these are the three exotic ways you can use to do the same thing so what i'm going to do is just run the exact same benchmark but now also have these things into the mix and see how they perform compared to the for each and the for loop all right so results are back and let's see what we have here so let's start with 100 items and the four each link so compared to the row versions the for each and the for loop this is now three times slower it doesn't allocate any memory but it is three times slower which is pretty slow for gaining really nothing i mean you might think it is more readable to do that and you might be able to chain methods but then you'd have to have a list to begin with so in my opinion just go for it for each loop into the for each list method but you should know how it performs then we have the parallel for each which is five microseconds so we left the nanosecond world and also we have 4.1 kilobytes of memory allocated on the heap and then you go to the parallel link and then for 100 items you have 13 microseconds and 11.5 kilobytes of memory that's a lot but here is where this becomes interesting as you can see the 100 and then 100 000 and then the 1 million data the bytes allocated for them this is a double for 100 000 but also stays the same basically in fact it's a bit less for 1 million and then you have 11.6 and 11.5 full of these sizes so it looks like the allocated memory is the same for a different size of data what changes is the speed now in both cases both in the four and four each loops we see a linear scale in the speed so it was 45 and 47 nanoseconds in the beginning then you go to basically 42 for both and then 418 microseconds for both so half a millisecond almost this is also effectively what you see with the for each link 156 148 microseconds and then uh 1.4 milliseconds you're nothing surprising here i was kind of expecting for each to be the worst performing one anyway where this becomes very very interesting is in the parallel versions so polar forage and parallel link as you can see actually decrease in the delta because the overhead to actually have them and having the more threads actually decreases and it crosses the threshold at some point where they're actually faster with more data as opposed to the sequential version of the iteration and in fact if you were to do more work in those loops and not just have or give me an item they would be significantly faster in most cases depending on the course you have at your disposal compared to the sequential evasion so you should be aware of it in the memory location for using them as you can see remains static as the data grows so they're relatively safe in terms of scaling their memory for bigger data sets now what does that mean does it mean that four and four each is the best way to go for smaller lists and then parallel dot for each is the best way to go for bigger lists well no let's take a look at the technique you've never actually seen before so what i'm going to add is a benchmark again and i'm going to call that public void for each span of course it would be a spam what you expect but how would you get a span out of the list because to get a span you kind of need the array to get a span from so how do you get a span from a list because you can't access the array in a list if i go and search for list actually if i go here you will see that the list is backed up by an items array but that is internal i cannot access it so what i can do is say for each collections marshall as span and i can pass my list in there and then i can say item and as you can see this var this item here it is an integer it is the item from that list the way this is possible is because this method actually has access to the items directly and creates as you can see here a span from the items which is the array of the list and how does it perform well i'm going to show you how this performs but i'm also going to add the four version of this test and that's it now all i want to do is run this test which for me will take eight minutes or something but for you it's just going to be one of the alright results are back and let's really have here and i'm going to focus only on four for each and then the two new span methods so we have the same 45 and 47 nanoseconds for the one-handed size but then as you can see both the four each and the for loop on the span 24 almost half the speed and again no memory allocations then as we grow the data set as you can see similar thing half the speed 20 microseconds for both of them they're effectively the same and then as we grow even further they're still faster and more more efficient there is no memory than both the parallel versions and fall and forage and everything however even though they are the fastest and most memory efficient way to iterate a list you have to be very careful because as you can see over here if we read the summary it says get a view over the list data items should not be added or removed from the list while the span is in use so this is only safe if and only if you are not mutating the list you're working with because you're getting a span on that array and if that array changes then that can cause problems so you have to be careful and it is marked on the class it is an unsafe class that provides set of methods blah blah blah but these are not unsafe marked methods you can use them and in fact their runtime is using them extensively and you can as well as long as you can guarantee that the data won't be mutated while you're iterating it and that's it i've personally used it with great success but it was only scenarios where nothing could actually mutate the data when i have that span and i'm iterating over it and that's it that is the fastest and most memory efficient to iterate a list in c sharp with a small caveat well that's all i have for you forever thank you very much for watching special thanks to my patreons for making this possible if you want to support us we're going to find a link in the description down below leave a like if you like this video subscribe more than like this ring the bell as well and i'll see you in the next video keep coding

Channel: Nick Chapsas

Views: 151,324

Keywords: Elfocrash, elfo, coding, .netcore, dot net, core, C#, how to code, tutorial, development, software engineering, microsoft, microsoft mvp, .net core, nick chapsas, chapsas, dotnet, .net, C# list, list, ilist, ienumerable, list iteration, fast list iteration, fast list enumeration, span, list span, .net span, .net 7 list, fast list c#, The fastest way to iterate a List in C# is NOT what you think

Id: jUZ3VKFyB-A

Length: 13min 42sec (822 seconds)

Published: Thu Sep 15 2022