Стоимость методов встраивания в C #

Question

Я недавно реализовал алгоритм быстрой сортировки в C #.Сортировка по целочисленному массиву, содержащему миллионы элементов, производительность кода примерно на 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;
}

Edit # 2: Если кто-то заинтересован в компиляции, вот код, который вызывает алгоритмы:

Редактировать # 3: Новый тестовый код по предложению Хеймо.

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);
    }
}

Answer 1

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  • среднее время для быстрой сортировки. Сортировка

  • внутренних повторений для быстрой сортировки. Сорт2 (например, 1000)

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

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

@ 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 не распознает это), общая скорость выполнения страдает.Таким образом, в данном конкретном случае ручное встраивание функции Partition невыгодно.

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