Справка с оптимизацией C# функционирует через C и/или блок

У меня есть этот метод C#, который я пытаюсь оптимизировать:

// assume arrays are same dimensions
private void DoSomething(int[] bigArray1, int[] bigArray2)
{
    int data1;
    byte A1, B1, C1, D1;
    int data2;
    byte A2, B2, C2, D2;
    for (int i = 0; i < bigArray1.Length; i++)
    {
        data1 = bigArray1[i];
        data2 = bigArray2[i];

        A1 = (byte)(data1 >> 0);
        B1 = (byte)(data1 >> 8);
        C1 = (byte)(data1 >> 16);
        D1 = (byte)(data1 >> 24);

        A2 = (byte)(data2 >> 0);
        B2 = (byte)(data2 >> 8);
        C2 = (byte)(data2 >> 16);
        D2 = (byte)(data2 >> 24);

        A1 = A1 > A2 ? A1 : A2;
        B1 = B1 > B2 ? B1 : B2;
        C1 = C1 > C2 ? C1 : C2;
        D1 = D1 > D2 ? D1 : D2;

        bigArray1[i] = (A1 << 0) | (B1 << 8) | (C1 << 16) | (D1 << 24); 
    }
}

Функция в основном выдерживает сравнение два int массивы. Для каждой пары соответствия элементам метод сравнивает каждое отдельное значение байта и берет большие из двух. Элементу в первом массиве затем присваивают новое int значение создается из 4 самых больших значений байта (независимо от источника).

Я думаю, что оптимизировал этот метод как можно больше в C# (вероятно, я не имею, конечно - предложения в этом отношении приветствуются также). Мой вопрос, действительно ли это стоит того для меня для перемещения этого метода в неуправляемый DLL C? Был бы получающийся метод выполняться быстрее (и сколько быстрее), принимая во внимание издержки маршалинга моего управляемого int массивы, таким образом, они могут быть переданы методу?

При выполнении это получило бы меня, скажем, 10%-е улучшение скорости, затем это не будет стоить моего времени наверняка. Если бы это было в 2 или 3 раза быстрее, то я должен был бы, вероятно, сделать это.

Примечание: никакая "преждевременная оптимизация" комментарии, заранее спасибо. Это - просто "оптимизация".

Обновление: Я понял, что мой пример кода не получал все, что я пытаюсь сделать в этой функции, таким образом, вот обновленная версия:

private void DoSomethingElse(int[] dest, int[] src, double pos, 
    double srcMultiplier)
{
    int rdr;
    byte destA, destB, destC, destD;
    double rem = pos - Math.Floor(pos);
    double recipRem = 1.0 - rem;
    byte srcA1, srcA2, srcB1, srcB2, srcC1, srcC2, srcD1, srcD2;
    for (int i = 0; i < src.Length; i++)
    {
        // get destination values
        rdr = dest[(int)pos + i];
        destA = (byte)(rdr >> 0);
        destB = (byte)(rdr >> 8);
        destC = (byte)(rdr >> 16);
        destD = (byte)(rdr >> 24);
        // get bracketing source values
        rdr = src[i];
        srcA1 = (byte)(rdr >> 0);
        srcB1 = (byte)(rdr >> 8);
        srcC1 = (byte)(rdr >> 16);
        srcD1 = (byte)(rdr >> 24);
        rdr = src[i + 1];
        srcA2 = (byte)(rdr >> 0);
        srcB2 = (byte)(rdr >> 8);
        srcC2 = (byte)(rdr >> 16);
        srcD2 = (byte)(rdr >> 24);
        // interpolate (simple linear) and multiply
        srcA1 = (byte)(((double)srcA1 * recipRem) + 
            ((double)srcA2 * rem) * srcMultiplier);
        srcB1 = (byte)(((double)srcB1 * recipRem) +
            ((double)srcB2 * rem) * srcMultiplier);
        srcC1 = (byte)(((double)srcC1 * recipRem) +
            ((double)srcC2 * rem) * srcMultiplier);
        srcD1 = (byte)(((double)srcD1 * recipRem) +
            ((double)srcD2 * rem) * srcMultiplier);
        // bytewise best-of
        destA = srcA1 > destA ? srcA1 : destA;
        destB = srcB1 > destB ? srcB1 : destB;
        destC = srcC1 > destC ? srcC1 : destC;
        destD = srcD1 > destD ? srcD1 : destD;
        // convert bytes back to int
        dest[i] = (destA << 0) | (destB << 8) |
            (destC << 16) | (destD << 24);
    }
}

По существу это делает то же самое как первый метод, кроме этого второй массив (src) всегда меньше, чем первое (dest), и второй массив расположен незначительно относительно первого (подразумевать, что вместо того, чтобы быть положением в, скажем, 10 относительно dest, он может быть расположен в 10,682791).

Для достижения этого я должен интерполировать между двумя значениями заключения в скобки в источнике (скажите, 10 и 11 в вышеупомянутом примере, для первого элемента), и затем сравните интерполированные байты с целевыми байтами.

Я подозреваю здесь, что умножение, вовлеченное в эту функцию, является существенно более дорогостоящим, чем сравнения байта, так, чтобы часть могла быть отвлекающим маневром (извините). Кроме того, даже если сравнения являются все еще несколько дорогими относительно умножения, у меня все еще есть проблема, что эта система может на самом деле быть многомерной, означая, что вместо того, чтобы сравнить 1-мерные массивы, массивы могли быть 2-, 5-или безотносительно - размерные, так, чтобы в конечном счете время, потраченное для вычисления интерполированных значений, затмило время, потраченное финалом bytewise сравнение 4 байтов (я предполагаю, что это имеет место).

Насколько дорогой умножение здесь относительно смещения бита, и действительно ли это - вид операции, которая могла быть ускорена, будучи разгруженным к DLL C (или даже блок DLL, хотя я должен буду нанять кого-то для создания этого для меня)?

9
задан MusiGenesis 31 May 2010 в 01:05
поделиться

6 ответов

Приведенная ниже функция использует небезопасный код для обработки целочисленных массивов как массивов байтов, так что нет необходимости в переключении битов.

    private static void DoOtherThing(int[] bigArray1, int[] bigArray2)
    {
        unsafe
        {
            fixed (int* p1 = bigArray1, p2=bigArray2)
            {
                byte* b1 = (byte*)p1;
                byte* b2 = (byte*)p2;
                byte* bend = (byte*)(&p1[bigArray1.Length]);
                while (b1 < bend)
                {
                    if (*b1 < *b2)
                    {
                        *b1 = *b2;
                    }
                    ++b1;
                    ++b2;
                }
            }
        }
    }

На моей машине, работающей под отладчиком в режиме Release с массивами из 25 миллионов целых чисел, этот код примерно на 29% быстрее, чем ваш оригинал. Однако при автономной работе разницы во времени выполнения почти нет. Иногда ваш оригинальный код быстрее, а иногда новый код быстрее.

Примерные цифры:

          Debugger  Standalone
Original  1,400 ms    700 ms
My code     975 ms    700 ms

И да, я сравнил результаты, чтобы убедиться, что функции делают одно и то же.

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

Учитывая эти результаты, я сомневаюсь, что вы сможете улучшить ситуацию, перейдя на нативный код. Как вы говорите, накладные расходы на маршалинг массивов, скорее всего, съедят любую экономию, которую вы могли бы получить при обработке.

Следующая модификация вашего исходного кода, однако, на 10%-20% быстрее.

    private static void DoSomething(int[] bigArray1, int[] bigArray2)
    {
        for (int i = 0; i < bigArray1.Length; i++)
        {
            var data1 = (uint)bigArray1[i];
            var data2 = (uint)bigArray2[i];

            var A1 = data1 & 0xff;
            var B1 = data1 & 0xff00;
            var C1 = data1 & 0xff0000;
            var D1 = data1 & 0xff000000;

            var A2 = data2 & 0xff;
            var B2 = data2 & 0xff00;
            var C2 = data2 & 0xff0000;
            var D2 = data2 & 0xff000000;

            if (A2 > A1) A1 = A2;
            if (B2 > B1) B1 = B2;
            if (C2 > C1) C1 = C2;
            if (D2 > D1) D1 = D2;

            bigArray1[i] = (int)(A1 | B1 | C1 | D1);
        }
    }
4
ответ дан 4 December 2019 в 12:59
поделиться

Как насчет этого?

    private void DoSomething(int[] bigArray1, int[] bigArray2)
    {
        for (int i = 0; i < bigArray1.Length; i++)
        {
            var data1 = (uint)bigArray1[i];
            var data2 = (uint)bigArray2[i];

            bigArray1[i] = (int)(
                Math.Max(data1 & 0x000000FF, data2 & 0x000000FF) |
                Math.Max(data1 & 0x0000FF00, data2 & 0x0000FF00) |
                Math.Max(data1 & 0x00FF0000, data2 & 0x00FF0000) |
                Math.Max(data1 & 0xFF000000, data2 & 0xFF000000));
        }
    }

В нем гораздо меньше битового сдвига. При профилировании вы можете обнаружить, что вызовы Math.Max не инкрементируются. В этом случае вы просто сделаете метод более многословным.

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

Если это все еще не работает так, как вы ожидаете, вы можете попробовать использовать арифметику указателей в небезопасном блоке, но я сильно сомневаюсь, что вы увидите выигрыш. Код, подобный этому, вряд ли будет быстрее, если вы будете его экстернировать, из всего, что я читал. Но не верьте мне на слово. Измеряйте, измеряйте, измеряйте.

Удачи.

2
ответ дан 4 December 2019 в 12:59
поделиться

Вы можете взглянуть на класс BitConverter - не можете вспомнить, является ли это правильным порядком байтов для конкретного преобразования, которое вы пытаетесь выполнить, но о нем все равно стоит знать.

0
ответ дан 4 December 2019 в 12:59
поделиться

Да, встроенная функция _mm_max_epu8 () делает то, что вы хотите. Пережевывает 16 байт за раз. Проблема в массивах. Команды SSE2 требуют, чтобы их аргументы были выровнены по 16-байтовым адресам. Вы не можете получить это из кучи собранного мусора, это обещает только 4-байтовое выравнивание. Даже если вы обманете его, вычислив смещение в массиве, выровненном по 16 байт, вы проиграете, когда сборщик мусора сработает и переместит массив.

Вам нужно будет объявить массивы в коде C / C ++ с помощью декларатора __declspec (align (#)). Теперь вам нужно скопировать ваши управляемые массивы в эти неуправляемые. И результаты вернулись. Будете ли вы впереди, зависит от деталей, которые не так легко увидеть в вашем вопросе.

7
ответ дан 4 December 2019 в 12:59
поделиться

Я не вижу никакого способа ускорить этот код с помощью хитроумных битовых трюков.

Если вы действительно хотите, чтобы этот код был быстрее, единственный способ значительно (>2x или около того) ускорить его на платформе x86, который я вижу, это перейти к реализации на ассемблере/интринсике. В SSE есть инструкция PCMPGTB которая

"Выполняет SIMD сравнение для большего значения упакованных байтов, слов или двойных слов в операнде назначения (первый операнд) и операнде источника (второй операнд). Если элемент данных в операнде назначения больше, чем соответствующий элемент данных в операнде источника, то соответствующий элемент данных в операнде назначения устанавливается во все 1s; в противном случае он устанавливается во все 0s."

В регистр XMM поместится четыре 32-битных инта, и вы можете зациклиться на своих массивах, читая значения, получая маску и затем выполняя AND первого входа с маской, а второго - с инвертированной маской.

С другой стороны, возможно, вы можете переформулировать свой алгоритм так, чтобы вам не нужно было выбирать большие байты, а, например, взять AND из операндов? Просто мысль, трудно сказать, может ли это работать, не видя реального алгоритма.

2
ответ дан 4 December 2019 в 12:59
поделиться

Другой вариант, если вы можете запустить Mono, - это использовать пакет Mono.Simd . Это обеспечивает доступ к набору инструкций SIMD из .NET. К сожалению, вы не можете просто взять сборку и запустить ее в среде CLR MS, поскольку среда выполнения Mono обрабатывает особым образом во время JIT. Фактическая сборка содержит обычные IL (не-SIMD) «симуляции» операций SIMD в качестве запасного варианта на случай, если оборудование не поддерживает инструкции SIMD.

Насколько я могу понять, вам также необходимо уметь выразить свою проблему, используя типы, которые использует API.

Вот запись в блоге , в которой Мигель де Икаса объявил о возможностях еще в ноябре 2008 года. Довольно круто. Надеюсь, он будет добавлен в стандарт ECMA, и MS сможет добавить его в свою среду CLR.

1
ответ дан 4 December 2019 в 12:59
поделиться
Другие вопросы по тегам:

Похожие вопросы: