Затраты на итерацию T [] приведения к IList <T> - PullRequest
Новая
       22

Затраты на итерацию T [] приведения к IList <T>

13 голосов
/ 26 ноября 2011

Я заметил, что производительность перебирает примитивную коллекцию (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();
    }

Ответы [ 3 ]

19 голосов
/ 26 ноября 2011

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

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

Редактировать: Если вам интересен фактический машинный код, генерируемый JIT из Release build без отладчик подключен, вот он.

Версия массива 

            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

IE Многочисленная версия 

            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]
3 голосов
/ 27 ноября 2011

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

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

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

0 голосов
/ 14 декабря 2016

В качестве альтернативы ответу @ MagnatLU выше, вы можете использовать for вместо foreach и кэшировать список Count. По сравнению с 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;
}
...