Deep .NET  -  Iteration: for vs foreach
Published: 2023-09-02 14:46:53

I choose to start from one of the most common and basic things, Iteration.

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/ow2v7o5hjzrpb3903ajg.png)


We will explore how .NET iterates over `List<T>` and over an `Array<T>` and see what the differences are between iteration with a for and a foreach loop .

But before we will start, let’s go over `List<T>` and foreach and understand how each of them works

## `List<T>`


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/4l6pp5ikc855qkc8gan9.png)

The List class stores our items in an internal array named `_items`, when we are creating a new list without any parameter, `_items` is assigned to an empty array of T.


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/akw5yg301lj9uzsb4ow6.png)

By adding an item into the array

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/hiza61rylc72tu32do63.png)

.NET starts by updating the version of the array (the _version variable keeps changing by an increment of 1 every time the array is modified so it will be possible to keep track when the collection has been modified).

The `_size` variable acts as a virtual size for our list, while the physical size is actually the length of the `_items` array, called Capacity.
So every time that we are adding an item into the list it ensures that the capacity is big enough to store another item and if it is , then the new item will be assigned.

Every time the virtual size is bigger than the capacity, `AddWithResize` method is being called:

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/if95kbwv77bw1cjplky9.png)

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/gsol7ylbztmr4ks1wwti.png)

This ensures that the next minimum size will be bigger then the current one plus 1 since we wish to add a new item into the list.

Then the function calls to `EnsureCapacity`, which sets the new capacity into the default one (`DefaultCapacity=4`) in case `_items` is an empty array, or doubles `_items` size in case that `_items` is not empty.

That’s the most basic explanation to how List<T> was implemented and the goal is to cover 3 basic points

1. `List<T>` uses an internal array

2. The `Capacity(_items.Length)` of the List is different then the `Count(_size)` of the list

3. The list keeps an updated version variable that keeps track of changes.

## The foreach loop
Many different collections such as `List<T>` or `Dictionary<T>` can be iterated by a foreach loop, because their class implements one of the following interfaces: [System.Collections.IEnumerable ](https://docs.microsoft.com/en-us/dotnet/api/system.collections.ienumerable) or [System.Collections.Generic.IEnumerable<T>](https://docs.microsoft.com/en-us/dotnet/api/system.collections.generic.ienumerable-1) and satisfies the following conditions:

· has the public parameterless `GetEnumerator` method whose return type is either class, struct, or interface type,

· the return type of the `GetEnumerator` method has the public Current property and the public parameterless MoveNext method whose return type is [Boolean](https://docs.microsoft.com/en-us/dotnet/api/system.boolean).

Foreach loop works as **the following example: (the following example is not the real .NET implantation)**:


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/0pdhcva2r7iobadt5aha.png)
So every initialization starts by calling to the `GetEnumurator()`


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/jj3yi2ebxhqccj29mhkw.png)

Which creates a new Enumerator struct and passes the current list as an argument:


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/6tqh4piaw7l4a3rq22f4.png)

Important to mention that struct is not a reference type, and it’s important to understand the difference between the two - [you can read more about that here](https://docs.microsoft.com/en-us/dotnet/visual-basic/programming-guide/language-features/data-types/value-types-and-reference-types).

After initializing the Enumerator and assigning the value, the MoveNext() method is being called repeatedly n times:


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/a9e8h8axn6sl28r9fbhm.png)

The MoveNext method starts by assigning the list instance into a local variable, and then validates that the enumerable struct version matches the version of the list (to verify that the list was not modified)

```
((uint)_index < (uint)localList._size))
```
is equivalent to:

```
if (_index>0 || _index<localList._size)
```
worth to read about the sign bit and Two’s complement

https://en.wikipedia.org/wiki/Two%27s_complement.

And finally:

```
_current = localList._items[_index];

_index++;

return true;
```
it assigns the next value into _current and increments the index and return true.

## Warm up — Simple for loop

Just for warm up, let’s start from a basic for loop, and have a look at following C# program:


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/h42o3g1gp27ak2mrdjv4.png)

“some code” will be executed 333 times as long there is no break, return or throw involved. However, since we are talking about iteration , we will focus on the iteration itself which is highlighted in blue and not the first initialization part.

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/7ifjh6t47kf45wnwv8kq.png)

As we can see, in any iteration, the CPU executes 11 instructions to complete each iteration that is distributed in the following way:


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/uzlif3d2poc4sw3k80q2.png)

## Array iteration with for loop

Now, since we are all warmed up, let’s examine how exactly .NET iterates over an array with a for loop. We will examine the next example:


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/f6lqfqstlpmngpqzb8a8.png)

And the disassembly:

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/o4vwylubf68jmzt5ib85.png)

In that iteration, the CPU will have to execute 20 instructions- each iteration is distributed in the following way:


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/4bykwm4ddot4ad34781o.png)

## List Iteration With a foreach loop

Above, we saw how foreach iteration is implemented in .NET.
Now, let’s examine the next function:

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/fdldir5qywh8runqy9ve.png)

And the disassembly: (as before I highlighted only the part that occur n times, and ignored the initialization)


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/4r6zg1aqg0oeim8l1nkh.png)

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/np5htr1jn29otok3xvs4.png)

It’s easy to see that the current iteration was much longer. The CPU executes 34 instructions, with each iteration distributed in the following way:


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/uj4afhr8h7qgnt79y7am.png)

## List Iteration With a for loop

Before we dig in into the assembly, there is another thing that is worth mentioning. Any time we use[] on a list instance, we are invoking the following extension:


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/jz4szxuqdclu0b16j8rf.png)

Now, let’s take the following C# function:

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/s6vt0dh29cfet4pok692.png)

And the disassembly:


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/1yimbe1myql7cnpbctfz.png)

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/dn7s6xuqe59xvc4alv08.png)

In that iteration, the CPU executes 39 instructions n times just for the iteration which is distributed in the following way:


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/wc4c7i053h8vdpayhip9.png)

## Array Iteration with a foreach loop

And for our last example let’s have a look at the following C# code:


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/tcuelz7byx0klhqq23a1.png)

And let’s look even deeper:


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/vhu6u2kjny9tpb03irsc.png)

In that iteration, the CPU executes 16 instructions n times just for the iteration which is distributed in the following way:


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/vh1zeee5c6lwbwsezk5u.png)

## THE RESULTS

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/2qtfozm51u5pmnyxs6pq.png)

The results are displayed in the following tables: as seen in the first table above, the “total” column represents the number of assembly instructions. The“Estimated CPU cycles score” represents an estimated score that was calculated by the type of the instruction, the latency and the throughput.


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/92x3ivsfqy4nxado9y6g.png)


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/dm2n5kw11zsa96mu1i6v.png)

To test our conclusions, [I created the following TimeMesurment class, And initialized it with the value of 200000000](https://bitbucket.org/oryaacov/deep-.net/src/master/Iteration/Iteration/TimeMeasurment.cs)


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/rdhtfqp0aj2jooa42y3x.png)

In conclusion, it is nearly twice as efficient to iterate over an array then a list.

Of course, that List<T> creates a lot of necessary functionality such as adding and removing items from the collection, but sometimes developers use a List when those extra functionalities are unnecessary, as a form of a bad habit.

Thank you for reading.

Or Yaacov

## Sources:


- https://en.wikibooks.org/wiki/X86_Assembly/Control_Flow

- https://chadaustin.me/2009/02/latency-vs-throughput/

- http://www.cs.virginia.edu/~evans/cs216/guides/x86.html

- https://github.com/dotnet/core

- https://docs.microsoft.com/en-us/dotnet/csharp/index

- https://www.agner.org/