foreach loop could behave like for loops for IList values

[VGib]

Hello,

This is the continuation of this issue

What is my problem
I get big performance increase when dealing with calculating code with lot of arrays, which such a method (I just check that the IEnumerable is IList, since this has been lot done in Linq code)

 public static void ForEach<T>(this IEnumerable<T> values, Action<T> doOnValue)
        {
            var valuesAsList = values as IList<T>;
            if (valuesAsList is null)
            {
                foreach (var value in values)
                {
                    doOnValue?.Invoke(value);
                }
            }
            else
            {
                for (int position = 0; position < valuesAsList.Count; position++)
                {
                    doOnValue?.Invoke(valuesAsList[position]);
                }
            }
        }

the foreach is a good way for code lisibility. And I have the advantage of for boost , with foreach lisibility.

What I would like
I'd like the foreach to behave like for loop, i.e not using IEnumerable, when dealing with IList.

Is it possible ?

Regards,

VGib

[YairHalberstadt]

This isn't always the case that for is faster than foreach.

For example looping over an ImmutableList is O(n) when using foreach but O(n * log(n)) when using for.

[VGib]

OK, I didn't do benchmark with ImmutableList, just my own use case.

Is it possible to do this when the for loop is known to be faster.

For my purpos, this is typically the case when the compilator should choose to change your code, without having to guess which is faster of for and foreach.

This may be to complicated for common developpers.

If this seems too complicated let's close it.

[YairHalberstadt]

How would the compiler know which is faster?

[VGib]

I've take a look to ImmutableList.

This is obviously not a good idea, to use for loop. (But without knowing, I'll may use the for loop).

Maybe a #something before the class. This should be present on List and array. As they are lot used, this may be a good idea.

Any way: this need to have to be able to have information read at compile time. I don't know if this can be done.

If too complicated let's close this. But this seems to me great.

[YairHalberstadt]

But the type isn't known at compile time. At compile time all we have is an IEnumerable

[VGib]

OK, so false good idea.
Let's close it.

[benaadams]

In you example it would go faster if you also only evaulated .Count via the interface once

int count = valuesAsList.Count;
for (int position = 0; position < count; position++)
{
    doOnValue?.Invoke(valuesAsList[position]);
}

Sprinkle in some pattern matching to combine the cast and null check

public static void ForEach<T>(this IEnumerable<T> values, Action<T> doOnValue)
{
    if (values is IList<T> list)
    {
        int count = list.Count;
        for (int position = 0; position < count; position++)
        {
            doOnValue?.Invoke(list[position]);
        }
    }
    else
    {
        foreach (var value in values)
        {
            doOnValue?.Invoke(value);
        }
    }
}

[VGib]

yes, you're right. I'll fix it.
Thanks

[HaloFour]

In Java they used a marker interface RandomAccess to indicate that the collection was efficient to navigate by index. ArrayList<T> implements it, but LinkedList<T> does not. It's kind of a shame .NET didn't have similar.

https://docs.oracle.com/javase/8/docs/api/java/util/RandomAccess.html

[YairHalberstadt]

@HaloFour

But ImmutableList does have efficient random access. It's just slower than sequential access.

[VGib]

So if it's slower, it just don't have the interface (could be rename in IsFasterWithRandomAccess).

[HaloFour]

@YairHalberstadt

Per the Java docs I linked the general rule of thumb is to apply that marker interface if it is expected that a for loop would be faster than using an iterator (or a foreach loop). But it also explicitly calls out how fuzzy this can be.

[YairHalberstadt]

@HaloFour

But you also have to evaluate whether the cost of checking for that interface is greater than the benefits it gets you. Note that Java doesn't change the behaviour of a foreach loop to check for this interface.

[VGib]

I know that Linq is doing lot of check optimization to check if there is a IList or just a IEnumerable.
For sample, the first method :

    public static TSource First<TSource>(this IEnumerable<TSource> source) {
            if (source == null) throw Error.ArgumentNull("source");
            IList<TSource> list = source as IList<TSource>;
            if (list != null) {
                if (list.Count > 0) return list[0];
            }
            else {
                using (IEnumerator<TSource> e = source.GetEnumerator()) {
                    if (e.MoveNext()) return e.Current;
                }
            }
            throw Error.NoElements();
        }

The question is: is the average performance boost better ?

[YairHalberstadt]

@VGib

Linq doesn't do those checks when it's just planning to enumerate. It only does the checks if it can use them more effectively in some way. For example it can make first allocation free by checking for IList.

[john-h-k]

This is a breaking change, and they are inherently different things

public class OhNo<T> : IList<T>, IEnumerable<T> where T : new() // implicit
{
    public IEnumerator<T> GetEnumerator() => null;
    public T this[int index] => new T();
    public int Count => int.MinValue;
}

Evaluating this using Count and the indexer is completely different behaviour to the enumerable. Sure, this is absolutely horrific code, but it is still a breaking change.

[VGib]

OK

[VGib]

Hello,

I was wondering something, excuse-me if I post my idea, when you have already answer.

Is it possible to make an optimisation on the Enumerable class, to prefer the for loop instead.

Because the List and Array have a special Enumerator ( from [https://github.com/microsoft/referencesource/blob/master/mscorlib/system/collections/generic/list.cs](List repositoryl) )

 [Serializable]
        public struct Enumerator : IEnumerator<T>, System.Collections.IEnumerator
        {
            private List<T> list;
            private int index;
            private int version;
            private T current;

            internal Enumerator(List<T> list) {
                this.list = list;
                index = 0;
                version = list._version;
                current = default(T);
            }

            public void Dispose() {
            }

            public bool MoveNext() {

                List<T> localList = list;

                if (version == localList._version && ((uint)index < (uint)localList._size)) 
                {                                                     
                    current = localList._items[index];                    
                    index++;
                    return true;
                }
                return MoveNextRare();
            }

            private bool MoveNextRare()
            {                
                if (version != list._version) {
                    ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumFailedVersion);
                }

                index = list._size + 1;
                current = default(T);
                return false;                
            }

            public T Current {
                get {
                    return current;
                }
            }

            Object System.Collections.IEnumerator.Current {
                get {
                    if( index == 0 || index == list._size + 1) {
                         ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumOpCantHappen);
                    }
                    return Current;
                }
            }
    
            void System.Collections.IEnumerator.Reset() {
                if (version != list._version) {
                    ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumFailedVersion);
                }
                
                index = 0;
                current = default(T);
            }

        }
    }
}

This would be nice to have the roslyn warning on the Enumerator type, with maybe an interface IEnumerablePreferForLoop.

What do-you think ?

[HaloFour]

@VGib

If that's what you want you can write an analyzer which warns on foreach over any specific implementation of IEnumerable<T> or IList<T>, and offer a fix to convert to a for loop instead. But that doesn't sound like something that the compiler should enforce.

[VGib]

Yes I'd like (maybe I would I like the CLR to optimize the loop with something like:
Get the enumerator, if Enumerator prefer the for loop, optimize with a for loop, but this may seems dreaming :) ).

But any way, this seems me much more easier to implement, than what we speek about. Since this is just an interface you put on Enumerator, and not on upper class.

[yaakov-h]

Using a for loop would lose version-safety, i.e. throwing an exception if the collection was modified whilst enumerating.

This is not something the compiler can just swap out for you.

[VGib]

OK so bad idea (once more).

[tannergooding]

It's not that it is a bad idea.

It's just that there are a lot of subtleties to any language proposal and unless you have previous experience with that, it is very easy to miss the various reasons why something might not work.

Everyone has pain points with every language and so everyone has ideas on how to fix those pain points. Putting up issues for those ideas is completely fine and the appropriate people (sometimes just other members from the community) will comment on why 'x' will or won't work, various edge cases that need to be considered, or link to existing/related proposals.

If people don't log an issue for the pain points they have, they language team may never know that some people consider it a pain point and so it or some feature to address it, may never come into existence (as it then requires someone from the language team to consider it a pain point, which they may not).

[avin-kavish]

@benaadams Isn't this a compiler optimizaton?

int count = list.Count;
for (int position = 0; position < count; position++)
{
}

[benaadams]

@benaadams Isn't this a compiler optimizaton?

No, the compiler can't make that optimization.

What the interface call IList.Count does is unknown to the compiler; its also unknown to the Jit so it can't be hoisted out of the loop and must be called each time; as it could do anything,

You can make the choice to assume its well behaved and will return the same value each time so manually hoist it out of the loop; but neither compiler can make that assumption.

If its a direct call rather than a interface, or virtual call (like on an array, span or List); then the Jit will likely inline it an then hoist it out of the loop automatically; but it cannot do that with an interface dispatch as it cannot "see" what the method does.

[HaloFour]

@avin-kavish

For a LinkedList<T> it becomes an accidentally quadratic "optimization", in that instead of walking the nodes once as it would with foreach using an Enumerator<T> it will walk all of the nodes up until the index for each iteration of the loop.

[CyrusNajmabadi]

For a LinkedList it becomes an accidentally quadratic "optimization", in that instead of walking the nodes once as it would with foreach using an Enumerator it will walk all of the nodes up until the index for each iteration of the loop.

Note: a smart linked list coudl keep track of the last node/index that was looked up to make striding like this fast. It's something i've seen in a lot of interesting datastructures (for example, string-apis with non-fixed-width-char lengths).

[HaloFour]

@CyrusNajmabadi

Sure, theoretically an implementation could, but the one in .NET doesn't and it's not wise to assume that any implementation would do that. And ultimately something like that would just be more complicated than just using an enumerator since now the list has to track mutable state which would need to be synchronized across threads, etc.

[CyrusNajmabadi]

Sure, theoretically an implementation could, but the one in .NET doesn't and it's not wise to assume that any implementation would do that. And ultimately something like that would just be more complicated than just using an enumerator since now the list has to track mutable state which would need to be synchronized across threads, etc.

Sure :) Just throwing it out there for completeness :D

[avin-kavish]

@benaadams Thanks, yeah runtime optimization is what I meant. I was thinking of C++ compiler optimizations and forgot that C# needed a run-time for a second there.

but it cannot do that with an interface dispatch as it cannot "see" what the method does.

Doesn't it "see" after the first dispatch? Once the procedure that it invoked does it's task it must be able to infer and optimize following calls to it?

@HaloFour wow, that's gonna give me a nightmare. xD