Накладные расходы Iterating T [], переданные в IList <T>

Я заметил хитовую производительность итерации над примитивной коллекцией (T []), которая была передана в общий набор интерфейсов (IList или IEnumberable).

Например:

    private static int Sum(int[] array)
    {
        int sum = 0;

        foreach (int i in array)
            sum += i;

        return sum;
    }

Вышеуказанный код выполняется значительно быстрее, чем код ниже, где параметр изменяется на тип IList (или IEnumerable):

    private static int Sum(IList<int> array)
    {
        int sum = 0;

        foreach (int i in array)
            sum += i;

        return sum;
    }

Достижение производительности все равно происходит, если переданный объект является примитивным массивом, и если я попытаюсь изменить цикл на цикл for вместо цикла foreach.

Я могу обойти хит производительности, закодировав его так:

    private static int Sum(IList<int> array)
    {
        int sum = 0;

        if( array is int[] )
            foreach (int i in (int[])array)
                sum += i;
        else
            foreach (int i in array)
                sum += i;

        return sum;
    }

Есть ли более элегантный способ решения этой проблемы? Спасибо за ваше время.

Изменить: Мой контрольный код:

    static void Main(string[] args)
    {
        int[] values = Enumerable.Range(0, 10000000).ToArray<int>();
        Stopwatch sw = new Stopwatch();

        sw.Start();
        Sum(values);
        //Sum((IList<int>)values);
        sw.Stop();

        Console.WriteLine("Elasped: {0} ms", sw.ElapsedMilliseconds);
        Console.Read();
    }

Ответы

Ответ 1

Лучше всего создать перегрузку для Sum с int[] как аргумент, если этот метод критичен по производительности. CLR JIT может обнаруживать итерацию в стиле foreach по массиву и может пропускать проверку диапазона и напрямую обращаться к каждому элементу. Каждая итерация цикла занимает 3-5 инструкций на x86, причем только один поиск в памяти.

При использовании IList JIT не имеет знаний о базовой структуре коллекции и заканчивается использованием IEnumerator<int>. Каждая итерация цикла использует два вызова интерфейса: один для Current, один для MoveNext (2-3 поиска в памяти и вызов для каждого из них). Это, скорее всего, заканчивается ~ 20 довольно дорогостоящими инструкциями, и вы не можете с этим поделать.

Изменить: Если вам интересно, какой фактический машинный код выдается JIT из сборки Release без отладчика, вот оно.

Массив версии

            int s = 0;
00000000  push        ebp  
00000001  mov         ebp,esp 
00000003  push        edi  
00000004  push        esi  
00000005  xor         esi,esi 
            foreach (int i in arg)
00000007  xor         edx,edx 
00000009  mov         edi,dword ptr [ecx+4] 
0000000c  test        edi,edi 
0000000e  jle         0000001B 
00000010  mov         eax,dword ptr [ecx+edx*4+8] 
                s += i;
00000014  add         esi,eax 
00000016  inc         edx  
            foreach (int i in arg)
00000017  cmp         edi,edx 
00000019  jg          00000010

версия IEnumerable

            int s = 0;
00000000  push        ebp  
00000001  mov         ebp,esp 
00000003  push        edi  
00000004  push        esi  
00000005  push        ebx  
00000006  sub         esp,1Ch 
00000009  mov         esi,ecx 
0000000b  lea         edi,[ebp-28h] 
0000000e  mov         ecx,6 
00000013  xor         eax,eax 
00000015  rep stos    dword ptr es:[edi] 
00000017  mov         ecx,esi 
00000019  xor         eax,eax 
0000001b  mov         dword ptr [ebp-18h],eax 
0000001e  xor         edx,edx 
00000020  mov         dword ptr [ebp-24h],edx 
            foreach (int i in arg)
00000023  call        dword ptr ds:[009E0010h] 
00000029  mov         dword ptr [ebp-28h],eax 
0000002c  mov         ecx,dword ptr [ebp-28h] 
0000002f  call        dword ptr ds:[009E0090h] 
00000035  test        eax,eax 
00000037  je          00000052 
00000039  mov         ecx,dword ptr [ebp-28h] 
0000003c  call        dword ptr ds:[009E0110h] 
                s += i;
00000042  add         dword ptr [ebp-24h],eax 
            foreach (int i in arg)
00000045  mov         ecx,dword ptr [ebp-28h] 
00000048  call        dword ptr ds:[009E0090h] 
0000004e  test        eax,eax 
00000050  jne         00000039 
00000052  mov         dword ptr [ebp-1Ch],0 
00000059  mov         dword ptr [ebp-18h],0FCh 
00000060  push        0F403BCh 
00000065  jmp         00000067 
00000067  cmp         dword ptr [ebp-28h],0 
0000006b  je          00000076 
0000006d  mov         ecx,dword ptr [ebp-28h] 
00000070  call        dword ptr ds:[009E0190h]

Ответ 2

Добро пожаловать в оптимизацию. Здесь не всегда очевидно!

В принципе, как вы обнаружили, когда компилятор обнаруживает, что определенные типы ограничений безопасности доказаны, он может выдавать чрезвычайно эффективный код при полной оптимизации. Здесь (как показывает MagnatLU) мы видим, что знание того, что у вас есть массив, позволяет делать всевозможные предположения относительно фиксированного размера и позволяет напрямую обращаться к памяти (что также максимально эффективно в том, как она интегрируется с CPU prefetch, для бонусной скорости). Когда у компилятора нет доказательства того, что он может генерировать сверхбыстрый код, он безопасен. (Это правильная вещь.)

Как общий комментарий, ваш код обходного пути довольно прост, когда дело доходит до кодирования для оптимизации (когда сделать код сверх читабельным и поддерживаемым не всегда является первым соображением). Я действительно не понимаю, как вы могли бы улучшить это, не делая свой API класса более сложным (а не выигрывать!). Более того, просто добавив комментарий внутри тела, чтобы сказать, почему вы это сделали, это решило проблему обслуживания; это на самом деле одно из лучших применений для (не-doc) комментариев в коде в первую очередь. Учитывая, что прецедент - это большие массивы (т.е. Разумно оптимизировать вообще), я бы сказал, что у вас есть отличное решение.

Ответ 3

В качестве альтернативы вышеприведенному ответу @MagnatLU вы можете использовать for вместо foreach и кешировать список Count. По сравнению с int[] все еще накладные расходы по сравнению с int[], но не так много: продолжительность перегрузки IList<int> снизилась на ~ 50%, используя ваш тестовый код на моей машине.

private static int Sum(IList<int> array)
{
    int sum = 0;

    int count = array.Count;
    for (int i = 0; i < count; i++)
        sum += array[i];

    return sum;
}