Почему Enumerable.Single() выполняет итерацию всех элементов, даже если более одного элемента уже найдено?

При профилировании одного из наших приложений мы обнаружили загадочное замедление в некотором коде, когда мы Enumerable.Single(source, predicate) для большой коллекции, в которой было несколько элементов, которые соответствовали предикату в начале коллекции.

Расследование показало, что реализация Enumerable.Single() выглядит следующим образом:

public static TSource Single<TSource>(this IEnumerable<TSource> source, Func<TSource, bool> predicate) 
{
        TSource result = default(TSource);
        long count = 0;
        // Note how this always iterates through ALL the elements:
        foreach (TSource element in source) { 
            if (predicate(element)) {
                result = element;
                checked { count++; }
            }
        }
        switch (count) {
            case 0: throw Error.NoMatch();
            case 1: return result;
        }
        throw Error.MoreThanOneMatch();
    }

Эта реализация будет проходить через каждый элемент последовательности, даже если более одного элемента уже соответствует предикату.

Следующая реализация, похоже, даст те же результаты:

public static TSource Single<TSource>(this IEnumerable<TSource> source, Func<TSource, bool> predicate)
{
    TSource result = default(TSource);
    long count = 0;
    foreach (TSource element in source) {
        if (predicate(element)) {
            if (count == 1) // Exit loop immediately if more than one match found.
                throw Error.MoreThanOneMatch();

            result = element;
            count++; // "checked" is no longer needed.
        }
    }

    if (count == 0)
        throw Error.NoMatch();

    return result;
}

Кто-нибудь знает, почему фактическая реализация не использует эту очевидную оптимизацию? Я что-то упускаю? (Я не могу себе представить, что такая очевидная оптимизация будет упущена из виду, и поэтому должна быть какая-то конкретная причина для этого.)

(Примечание: я понимаю, что этот вопрос может привлечь ответы, которые являются мнениями; я надеюсь на ответы, которые дают конкретные причины для повторения всех элементов. Если ответ на самом деле "потому что дизайнеры не думали, что такая оптимизация была необходима", тогда этот вопрос не подлежит обсуждению, и я думаю, я должен просто удалить его...)

Для сравнения посмотрите на реализацию Single() которая не принимает предикат:

public static TSource Single<TSource>(this IEnumerable<TSource> source) 
{
    IList<TSource> list = source as IList<TSource>;
    if (list != null) {
        switch (list.Count) {
            case 0: throw Error.NoElements();
            case 1: return list[0];
        }
    }
    else {
        using (IEnumerator<TSource> e = source.GetEnumerator()) {
            if (!e.MoveNext()) throw Error.NoElements();
            TSource result = e.Current;
            if (!e.MoveNext()) return result;
        }
    }
    throw Error.MoreThanOneElement();
}

В этом случае они приложили усилия для добавления оптимизации для IList.

Ответ 1

Вы, кажется, не единственный, кто так думал. Реализация .NET Core имеет оптимизированную версию:

using (IEnumerator<TSource> e = source.GetEnumerator())
{
    while (e.MoveNext())
    {
        TSource result = e.Current;
        if (predicate(result))
        {
            while (e.MoveNext())
            {
                if (predicate(e.Current))
                {
                    throw Error.MoreThanOneMatch();
                }
            }

            return result;
        }
    }
}

Таким образом, чтобы ответить на ваш вопрос: кажется, что нет "хорошей" причины, кроме просто разработчика, не думающего об оптимизации этого варианта использования.

Ответ 2

Оптимизация была применена в .NET Core

Код сейчас:

public static TSource Single<TSource>(this IEnumerable<TSource> source, Func<TSource, bool> predicate)
{
    if (source == null)
    {
        throw Error.ArgumentNull(nameof(source));
    }

    if (predicate == null)
    {
        throw Error.ArgumentNull(nameof(predicate));
    }

    using (IEnumerator<TSource> e = source.GetEnumerator())
    {
        while (e.MoveNext())
        {
            TSource result = e.Current;
            if (predicate(result))
            {
                while (e.MoveNext())
                {
                    if (predicate(e.Current))
                    {
                        throw Error.MoreThanOneMatch();
                    }
                }

                return result;
            }
        }
    }

    throw Error.NoMatch();
}

Везде, где возможно, код даже проверяет, является ли целью IList<T> поэтому он может избежать итерации:

public static TSource Single<TSource>(this IEnumerable<TSource> source)
{
    if (source == null)
    {
        throw Error.ArgumentNull(nameof(source));
    }

    if (source is IList<TSource> list)
    {
        switch (list.Count)
        {
            case 0:
                throw Error.NoElements();
            case 1:
                return list[0];
        }
    }
    else
    {
        using (IEnumerator<TSource> e = source.GetEnumerator())
        {
            if (!e.MoveNext())
            {
                throw Error.NoElements();
            }

            TSource result = e.Current;
            if (!e.MoveNext())
            {
                return result;
            }
        }
    }

    throw Error.MoreThanOneElement();
}

ОБНОВИТЬ

Проверка вывода git blame показывает, что оптимизация итераций была применена еще в 2016 году!

Оптимизация IList<> была добавлена 1 год назад, вероятно, в рамках оптимизации Core 2.1

Ответ 3

Как указывалось в других ответах, оптимизация была применена, но я просто хотел бы высказать гипотезу, что они сделали это таким образом, изначально думая о том, что у них нет способа гарантировать, что функция предиката не имеет стороны последствия.

Я не уверен, что действительно был бы случай, когда такое поведение было бы использовано/полезно, но об этом следует помнить.