Почему этот код List‹›.IndexOf намного быстрее, чем List[i] и ручное сравнение?

Я сделал следующие предположения:

• PointD это структура
• IndexOf действительно медленнее, чем перебор списка вручную

Вы можете ускорить IndexOf, реализовав интерфейс IEquatable<T>:

struct PointD : IEquatable<PointD>
{
    public int X;
    public int Y;
    public int Z;

    public bool Equals(PointD other)
    {
        return (this.X == other.X) &&
                (this.Y == other.Y) &&
                (this.Z == other.Z);
    }
}

Без реализации интерфейса IEquatable<T> IndexOf будет сравнивать два элемента PointD, используя ValueType.Equals(object other), который требует дорогостоящих операций упаковки.

В документации по интерфейсу IEquatable<T> указано:

Интерфейс IEquatable<T> используется универсальными объектами коллекций, такими как Dictionary<TKey, TValue>, List<T> и LinkedList<T>, при проверке на равенство в таких методах, как Contains, IndexOf, LastIndexOf и Remove. Его следует реализовать для любого объекта, который может храниться в универсальной коллекции.

Вот мой полный код теста:

using System;
using System.Collections.Generic;
using System.Diagnostics;

struct PointD 
{
    public int X;
    public int Y;
    public int Z;
}

class PerfTest
{
    List<PointD> _pCoord3Points = new List<PointD>();

    int checkPointIndexOf(PointD pt)
    {
        return _pCoord3Points.IndexOf(pt);  
    }

    int checkPointForBreak(PointD pt)
    {
        int retIndex = -1;
        for (int i = 0; i < _pCoord3Points.Count; i++)
        {
            PointD otherPt = _pCoord3Points[i];
            if ((pt.X == otherPt.X) &&
                (pt.Y == otherPt.Y) &&
                (pt.Z == otherPt.Z))
                retIndex = i;
            break;
        }
        return retIndex;
    }

    void init()
    {
        for (int x = 0; x < 100; x++)
        {
            for (int y = 0; y < 10; y++)
            {
                for (int z = 0; z < 10; z++)
                {
                    PointD pt = new PointD() { X = x, Y = y, Z = z };
                    _pCoord3Points.Add(pt);
                }
            }
        }
    }

    static void Main(string[] args)
    {
        PerfTest test = new PerfTest();
        test.init();
        Stopwatch sw = Stopwatch.StartNew();
        for (int x = 0; x < 100; x++)
        {
            for (int y = 0; y < 10; y++)
            {
                for (int z = 0; z < 10; z++)
                {
                    PointD pt = new PointD() { X = x, Y = y, Z = z };
                    test.checkPointIndexOf(pt);
                }
            }
        }
        sw.Stop();
        Console.WriteLine(sw.Elapsed);
        sw = Stopwatch.StartNew();
        for (int x = 0; x < 100; x++)
        {
            for (int y = 0; y < 10; y++)
            {
                for (int z = 0; z < 10; z++)
                {
                    PointD pt = new PointD() { X = x, Y = y, Z = z };
                    test.checkPointForBreak(pt);
                }
            }
        }
        sw.Stop();
        Console.WriteLine(sw.Elapsed);
    }
}

В сборке Windows 7, x64, .NET 4.0 x64 я получаю следующие тайминги (приблизительно):

IndexOf:  00:00:04.8096623
For Loop: 00:00:00.0014203

При превращении PointD в class тайминги меняются на

IndexOf:  00:00:01.0703627
For Loop: 00:00:00.0014190

При использовании struct PointD, реализующего IEquatable<PointD>, я получаю более "похожие" результаты, но IndexOf все еще медленнее (теперь нет существенной разницы при использовании class):

IndexOf:  00:00:00.3904615
For Loop: 00:00:00.0015218

Обычно, прежде чем вы получите доступ к элементу массива, он проверяет, что индекс >= 0 и длина ‹, чтобы вы не читали и не перезаписывали память, которая вам не принадлежит. Помимо прочего, он устраняет множество серьезных недостатков безопасности, называемых переполнением буфера.

Излишне говорить, что это снижает производительность, если в вашем цикле очень мало кода. Чтобы уменьшить эту проблему, JIT-компилятор оптимизирует циклы for формы for (i = 0; i < array.Length; i++) { array[i]; }, то есть любой цикл, который обращается ко всем индексам массива от 0 до длины - 1. В этом случае он опускает проверку границ. (Оптимизация терпит неудачу, если вы обращаетесь к таким вещам, как массив [i + 1], по той причине, что вы можете выйти за границы.)

К сожалению, это работает только с массивами, а не со списками. Таким образом, ваш последний код не будет оптимизирован.

Но поскольку List‹> внутри содержит массив, а List.IndexOf() использует цикл для прямого доступа к каждому значению в массиве, его можно оптимизировать.

Кстати, лучше сказать for (int i = 0; i < array.Length; i++) { }, чем int length = array.Length; for(int i = 0; i < length; i++) { }, потому что нельзя быть уверенным, что length действительно является длиной массива.

Изменить: глядя на код IndexOf с использованием Reflector, цикл действительно оптимизируется, но, как уже упоминали другие люди, он вызывает Equals(), для чего требуется поиск vtable и различные проверки работоспособности. Так что в этом случае IndexOf может работать медленнее, если вы не запускаете его с профилировщиком.

Дизассемблированный код:

internal virtual int IndexOf(T[] array, T value, int startIndex, int count)
{
    int num = startIndex + count;
    for (int i = startIndex; i < num; i++)
    {
        if (this.Equals(array[i], value))
        {
            return i;
        }
    }
    return -1;
}

Какой тип _pCoord3Points? Если тип элемента является типом значения, который переопределяет только Equals(object), то возможно, что IndexOf многократно упаковывает значения для проверки на равенство. Это может объяснить. Однако на данный момент это просто догадки... если бы вы могли предоставить короткую, но полную программу, демонстрирующую проблему, вам было бы намного легче помочь.