Как написать общий код, избегая при этом косвенных вызовов? - PullRequest
Новая
       63

Как написать общий код, избегая при этом косвенных вызовов?

6 голосов
/ 09 февраля 2012

Есть ли способ вызвать написание универсальных программ и алгоритмов на C #, в то время как избегает накладных расходов динамического решения?

Рассмотрим простой пример: 

static void QuickSort<T>(T[] arr, int left, int right, Comparison<T> compare)
{
    do
    {
        int i = left;
        int j = right;
        var x = arr[i + ((j - i) >> 1)];
        do
        {
            while (i < arr.Length && compare(x, arr[i]) > 0) i++;
            while (j >= 0 && compare(x, arr[j]) < 0) j--;
            if (i > j) { break; }
            if (i < j)
            {
                var temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
            i++;
            j--;
        } while (i <= j);
        if (j - left <= right - i)
        {
            if (left < j) QuickSort(arr, left, j, compare);
            left = i;
        }
        else
        {
            if (i < right) QuickSort(arr, i, right, compare);
            right = j;
        }
    } while (left < right);
}

Который вы могли бы назвать: 

QuickSort(buffer, 0, buffer.Length - 1, (a, b) => a.CompareTo(b))

Несмотря на кажущуюся эффективность, этот безобидный пример выполняет косвенный (то есть виртуальный) вызов для при каждом сравнении.

Очевидно, что процессор не может оптимизировать косвенные вызовы, и поэтому они работают плохо. На моем компьютере это приводит к снижению производительности на 25%, с примерно 3600 элементов / мс до 2700 элементов / мс.

Есть ли способ избежать таких косвенных вызовов при написании универсального кода?
Независимо от того, сколько я занимаюсь жонглированием с делегатами, DynamicMethod и т. П., Кажется, что всегда - это косвенный вызов между библиотечным кодом и кодом пользователя, который, очевидно, очень негативно влияет на производительность.

Ответы [ 5 ]

5 голосов
/ 09 февраля 2012

В случае сравнения элементов ответ отрицательный: вы не можете, скажем, указать > между x и arr[j] и ожидать, что компилятор выяснит, что вы хотите применить встроенный * Оператор 1004 * на объектах типа T.

Однако ваше решение может быть немного оптимизировано, потому что вы платите за косвенное обращение дважды. Поскольку вы уже объявили T и IComparable<T>, вы можете удалить параметр comparator и вызывать x.CompareTo(arr[j]), не проходя лямбду. Это сократило бы накладные расходы второго косвенного обращения. Конечно, это не позволит вам настроить способ сравнения ваших товаров, но это будет обычный случай оплаты гибкости за счет циклов ЦП.

2 голосов
/ 04 сентября 2013

Ваши результаты будут очень сильно зависеть от типа T и от того, насколько дорогими будут сравнения.

Я создал пользовательские версии ваших QuickSort методов: тот, который ожидает массив int, и тот, который ожидает массив string. Изменения ограничиваются удалением параметра сравнения и изменением двух сравнений в разделителе. Я изменил их для сортировки в обратном порядке, например: 

while (i < arr.Length && arr[i].CompareTo(x) > 0) i++;
while (j >= 0 && arr[j].CompareTo(x) < 0) j--;

Затем я проверил эти методы на вашем общем методе, используя массивы из 10 миллионов элементов. Мои результаты: 

Int: Generic QuickSort - 2,190 ms
Int: Custom QuickSort - 1,252 ms
String: Generic QuickSort - 32,902 ms
String: Custom QuickSort - 31,634 ms

Мой вывод таков: если сравнение очень недорогое (как с int и другими нативными типами), то вы заметите большую разницу в производительности. Если сравнение дорого (строки довольно дороги для сравнения), то затраты на виртуальный вызов теряются в стоимости сравнения.

Я знаю, что это не дает решения вашей проблемы; Я не думаю, что есть один. Гибкость часто приходит за деньги.

Люди, которые создавали библиотеки базовых классов, это понимали. Например, они создали особые случаи для примитивных типов, которые используют значение по умолчанию IComparer. Сравните разницу во времени выполнения при вызове Array.Sort этими двумя способами (используя int[10000000]): 

Array.Sort(a);  // 845 ms
Array.Sort(a, (a, b) => a.CompareTo(b)); // 2,339 ms

Оказывается, что Array.Sort имеет встроенные оптимизации для примитивных типов, которые используют их по умолчанию IComparer. См. Сравнения и IComparer для получения дополнительной информации об этом.

1 голос
/ 09 февраля 2012

Я думаю, что dasblinkenlight - это правильно, но я рискну догадаться, почему:

Когда вы передаете Comparer методу QuickSort, Framework создает общую реализацию делегата System.Comparison (System.Comparison 1` например).Вызовы любых универсальных делегатов являются виртуальными, что имеет смысл - как компилятор сможет статически генерировать вызов метода универсального типа, который создается только во время выполнения?

Рид Копси описывает это вздесь больше глубины: http://social.msdn.microsoft.com/Forums/en-US/csharplanguage/thread/b94c7506-e21f-43b1-be9a-bf88f8f72f36

Самым близким, что я мог получить, был фабричный шаблон, который возвращает не виртуальный вызов для известных типов: 

using System;
using System.Diagnostics;
using System.Linq;

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            const int size = 50000;
            var ra = RandomArray(size);
            var buffer = Enumerable.Range(0, size).OrderBy(i => ra[i]).ToArray();
            Debug.WriteLine(String.Join(",", buffer));
            new IntSorter().QuickSort(buffer);
            Debug.WriteLine(String.Join(",", buffer));

        }

        public IQuickSorter<T> GetSorter<T>() where T : IComparable<T>
        {
            if (typeof(T).Equals(typeof(Int32)))
                return (IQuickSorter<T>) new IntSorter();
            return new GenericSorter<T>();
        }

        public static Int32[] RandomArray(Int32 length)
        {
            var r = new Random();
            return Enumerable.Range(0, length).Select(i => r.Next(0, length + 1)).ToArray();
        }
    }

    public class IntSorter : IQuickSorter<int>
    {
        public void QuickSort(int[] arr)
        {
            QuickSortInner(arr, 0, arr.Length-1);
        }

        public void QuickSortInner(int[] arr, int left, int right)
        {
            do
            {
                int i = left;
                int j = right;
                var x = arr[i + ((j - i) >> 1)];
                do
                {
                    while (i < arr.Length && x.CompareTo(arr[i]) > 0) i++;
                    while (j >= 0 && x.CompareTo(arr[j]) < 0) j--;
                    if (i > j)
                    {
                        break;
                    }
                    if (i < j)
                    {
                        var temp = arr[i];
                        arr[i] = arr[j];
                        arr[j] = temp;
                    }
                    i++;
                    j--;
                } while (i <= j);
                if (j - left <= right - i)
                {
                    if (left < j) QuickSortInner(arr, left, j);
                    left = i;
                }
                else
                {
                    if (i < right) QuickSortInner(arr, i, right);
                    right = j;
                }
            } while (left < right);
        }
    }

    public class GenericSorter<T> : IQuickSorter<T> where T : IComparable<T>
    {
        public void QuickSort(T[] arr)
        {
            QuickSortInner(arr, 0, arr.Length - 1);
        }

        public void QuickSortInner(T[] arr, int left, int right)
        {
            do
            {
                int i = left;
                int j = right;
                var x = arr[i + ((j - i) >> 1)];
                do
                {
                    while (i < arr.Length && x.CompareTo(arr[i]) > 0) i++;
                    while (j >= 0 && x.CompareTo(arr[j]) < 0) j--;
                    if (i > j) { break; }
                    if (i < j)
                    {
                        var temp = arr[i];
                        arr[i] = arr[j];
                        arr[j] = temp;
                    }
                    i++;
                    j--;
                } while (i <= j);
                if (j - left <= right - i)
                {
                    if (left < j) QuickSortInner(arr, left, j);
                    left = i;
                }
                else
                {
                    if (i < right) QuickSortInner(arr, i, right);
                    right = j;
                }
            } while (left < right);
        }
    }

    public interface IQuickSorter<in T>
    {
        void QuickSort(T[] arr);
    }
}
0 голосов
/ 06 сентября 2013

На самом деле, я наконец понял, что решение очень простое:

Используйте обобщенные + интерфейсы вместо делегатов!

Пример: 

static void QuickSort<TCmp, T>(T[] arr, int left, int right, TCmp cmp)
    where TCmp : IComparer<T>
{
    do
    {
        int i = left;
        int j = right;
        var x = arr[i + ((j - i) >> 1)];
        do
        {
            while (i < arr.Length && cmp.Compare(x, arr[i]) > 0) i++;
            while (j >= 0 && cmp.Compare(x, arr[j]) < 0) j--;
            if (i > j) { break; }
            if (i < j)
            {
                var temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        } while (++i <= --j);
        if (j - left <= right - i)
        {
            if (left < j) QuickSort<TCmp, T>(arr, left, j, cmp);
            left = i;
        }
        else
        {
            if (i < right) QuickSort<TCmp, T>(arr, i, right, cmp);
            right = j;
        }
    } while (left < right);
}

На моем компьютере, когда я сравниваю старую версию, используя 

QuickSort(copy1, 0, copy1.Length - 1, (x, y) => x.CompareTo(y));

с новой версией, которая использует 

QuickSort(copy1, 0, copy1.Length - 1, comparer);

Я получаю хороший (~ 30%) прирост скорости.

0 голосов
/ 09 февраля 2012

Поместите метод быстрой сортировки в абстрактный тип и полностью избавьтесь от использования делегата.

Сначала создайте абстрактный тип. Обратите внимание на новый абстрактный метод сравнения и отсутствие делегата для метода QuickSort: 

public abstract class QuickSort<T>
{
    protected static abstract int compare(T x, T y);

    public static void QuickSort(T[] arr, int left, int right)
    {
        do
        {
            int i = left;
            int j = right;
            var x = arr[i + ((j - i) >> 1)];
            do
            {
                while (i  0) i++;
                while (j >= 0 && compare(x, arr[j]) < 0) j--;
                if (i > j) { break; }
                if (i < j)
                {
                    var temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                }
                i++;
                j--;
            } while (i <= j);
            if (j - left <= right - i)
            {
                if (left < j) QuickSort(arr, left, j);
                left = i;
            }
            else
            {
                if (i < right) QuickSort(arr, i, right);
                right = j;
            }
        } while (left < right);
    }
}

Затем создайте класс, который наследуется от QuickSort и реализует метод сравнения. Мы будем использовать целые числа для нашего примера: 

public class QuickSortInt : QuickSort<int>
{
    protected static override int compare(int x, int y)
    {
        if (x < y) return -1;
        if (x > y) return 1;
        return 0;
    }
}
...