Стоимость встроенных методов в С#

Недавно я реализовал алгоритм QuickSort на С#. Сортировка по целочисленному массиву, содержащему миллионы элементов, производительность кода составляет примерно 10% от реализации .NET.

private static void QS(int[] arr, int left, int right)
{
    if (left >= right) return;

    var pIndex = Partition(arr, left, right);
    QS( arr, left, pIndex);
    QS( arr, pIndex + 1, right);
}

В массиве из 5 миллионов элементов этот код примерно на 60 мс медленнее, чем .NET.

Впоследствии я создал другой метод, который имеет метод Partition(), заключенный в QS() (исключая вызов метода и оператор return). Это, однако, привело к снижению производительности примерно до 250 мс медленнее, чем метод сортировки .NET.

Почему это происходит?

Изменить: это код метода Partition(). В встроенной версии QS() все содержимое этого метода, за исключением оператора return, заменяет строку var pIndex = Partition(arr, left, right);.

private static int Partition(int[] arr, int left, int right)
{
    int pivot = arr[left];
    int leftPoint = left - 1;
    int pIndex = right + 1;
    int temp = 0;

    while (true)
    {
        do { pIndex--; } while (arr[pIndex] > pivot);
        do { leftPoint++; } while (arr[leftPoint] < pivot);

        if (leftPoint < pIndex)
        {
            temp = arr[leftPoint];
            arr[leftPoint] = arr[pIndex];
            arr[pIndex] = temp;
        }
        else { break; }
    }
    return pIndex;
}

Изменить №2: В случае, если кто-то заинтересован в компиляции, вот код, который вызывает алгоритмы:

Изменить №3: Новый тестовый код из предложения Haymo.

private static void Main(string[] args)
{
    const int globalRuns = 10;
    const int localRuns = 1000;

    var source = Enumerable.Range(1, 200000).OrderBy(n => Guid.NewGuid()).ToArray();
    var a = new int[source.Length];

    int start, end, total;

    for (int z = 0; z < globalRuns; z++)
    {
        Console.WriteLine("Run #{0}", z+1);

        total = 0;
        for (int i = 0; i < localRuns; i++)
        {
            Array.Copy(source, a, source.Length);
            start = Environment.TickCount;
            Array.Sort(a);
            end = Environment.TickCount;
            total += end - start;
        }
        Console.WriteLine("{0}\t\tTtl: {1}ms\tAvg: {2}ms", ".NET", total, total / localRuns);

        total = 0;
        for (int i = 0; i < localRuns; i++)
        {
            Array.Copy(source, a, source.Length);
            start = Environment.TickCount;
            Quicksort.SortInline(a);
            end = Environment.TickCount;
            total += end - start;
        }
        Console.WriteLine("{0}\t\tTtl: {1}ms\tAvg: {2}ms", "Inlined", total, total / localRuns);

        total = 0;
        for (int i = 0; i < localRuns; i++)
        {
            Array.Copy(source, a, source.Length);
            start = Environment.TickCount;
            Quicksort.SortNonInline(a);
            end = Environment.TickCount;
            total += end - start;
        }
        Console.WriteLine("{0}\tTtl: {1}ms\tAvg: {2}ms\n", "Not inlined", total, total / localRuns);
    }
}

Ответы

Ответ 1

На основании информации, заданной в вопросе, можно только догадываться и называть некоторые идеи.

Вы правильно оценили? Имейте в виду, чтобы получить надежные результаты работы, нужно (по крайней мере)

  • Запустить выпуск сборок без прикрепленного отладчика
  • Повторите тест достаточно часто и усредните результаты
  • Сделайте тест честным, т.е. дать всем испытуемым ту же "конфигурацию ressource"

Чтобы убедиться, что источник (предполагаемого) снижения производительности действительно подключен к встроенной функции, можно исследовать сгенерированный код IL. Или еще лучше: машинные инструкции, сгенерированные компилятором JIT.

Для ILNumerics мы внедрили пользовательскую быструю сортировку и сделали много показателей производительности. Окончательный алгоритм в несколько раз быстрее, чем версия CLR. Ручная вставка - это только одно усовершенствование, которое необходимо для повышения производительности. Другие:

  • Не использовать рекурсию
  • Использование небезопасного сравнения/замены
  • Использование сортировки вставки для небольших разделов
  • Оптимизация для ограниченного размера временного массива замены стека

Очень часто источник странных результатов производительности найден в способе, память (неверно) используется алгоритмом. Другой может заключаться в различном потоке команд, который в конечном итоге более или менее преуспевает в оптимизации любого компилятора/процессора. Общая производительность исполнения - очень сложный зверь, трудно угадать детерминистически и, следовательно, профилировщик - ваш лучший друг!

@Edit:. Посмотрев на основную тестовую процедуру, вы, в основном, измеряете пропускную способность памяти вашего процессора/основной памяти. Массив int [] длиной 5 * 10e6 имеет размер около 19 МБ. Это, скорее всего, вне диапазона ваших кешей. Таким образом, процессор будет ждать памяти из-за обязательных кэш-пропусков больше всего времени. Это мешает влиянию любой переформулировки кода, которую трудно угадать. Я предлагаю попытаться измерить этот способ вместо этого: (псевдокод)

  • генерировать тестовые данные
  • выделить массив для копий

  • повторить число глобальных повторений (скажем, 10)

    • внутренние повторения для Array.Sort(например, 1000)
      • скопировать (несортированные) тестовые данные
      • Сортируйте копию с помощью Array.Sort
      • добавить время

    • среднее время для Array.Sort

    • внутренние повторения для Quicksort.Sort(например, 1000)

      • скопировать (несортированные) тестовые данные
      • сортируйте копию с помощью команды Quicksort.Sort
      • добавить время

    • среднее время для Quicksort.Sort

    • внутренние повторения для Quicksort.Sort2 (например, 1000)

      • скопировать (несортированные) тестовые данные
      • Сортируйте копию по Quicksort.Sort2
      • добавить время
    • среднее время для Quicksort.Sort2

Цель состоит в том, чтобы использовать quicksort только данные из кешей. Поэтому не заново создавайте копии из новой памяти, а имеете только два глобальных экземпляра: оригинал и копию для сортировки. Оба должны одновременно входить в кеш (последнего уровня)! С некоторым запасом прочности (для других процессов в системе) следует учесть только половину доступного размера кэша последнего уровня для обоих массивов. В зависимости от вашего истинного размера кеша тестовая длина 250 000 кажется более разумной.

@Edit2: Я запустил ваш код, получил те же результаты и просмотрел (оптимизированные) машинные инструкции в отладчике VS. Здесь идет соответствующая часть из обеих версий:

Not inlined: 
    69:                 do { pIndex--; } while (arr[pIndex] > pivot);
00000017  dec         ebx 
00000018  cmp         ebx,esi 
0000001a  jae         00000053 
0000001c  cmp         dword ptr [ecx+ebx*4+8],edi 
00000020  jg          00000017 
    70:                 do { leftPoint++; } while (arr[leftPoint] < pivot);
00000022  inc         edx 
00000023  cmp         edx,esi 
00000025  jae         00000053 
00000027  cmp         dword ptr [ecx+edx*4+8],edi 
0000002b  jl          00000022 


Inlined: 
    97:                 do { pIndex--; } while (arr[pIndex] > pivot);
00000038  dec         dword ptr [ebp-14h] 
0000003b  mov         eax,dword ptr [ebp-14h] 
0000003e  cmp         eax,edi 
00000040  jae         00000097 
00000042  cmp         dword ptr [esi+eax*4+8],ebx 
00000046  jg          00000038 
    98:                 do { leftPoint++; } while (arr[leftPoint] < pivot);
00000048  inc         ecx 
00000049  cmp         ecx,edi 
0000004b  jae         00000097 
0000004d  cmp         dword ptr [esi+ecx*4+8],ebx 
00000051  jl          00000048

Как видно, версия "Не встроенная" лучше использует регистры для уменьшения индексов работы (строка 69/97). Очевидно, что JIT решил не нажимать и не вставлять соответствующий регистр в стек, поскольку другой код в той же функции использует один и тот же регистр. Поскольку это горячий цикл (и CLR не распознает это), страдает общая скорость выполнения. Таким образом, в этом конкретном случае ручная установка функции разделения не выгодна.

Однако, как вы знаете, нет гарантии, что другие версии CLR сделают то же самое. Различия могут даже возникнуть для 64-битного.