Почему я вижу увеличение скорости на 20% с помощью собственного кода?

Любая идея, почему этот код:

extern "C" __declspec(dllexport) void Transform(double x[], double y[], int iterations, bool forward)
{
    long n, i, i1, j, k, i2, l, l1, l2;
    double c1, c2, tx, ty, t1, t2, u1, u2, z;

    /* Calculate the number of points */
    n = (long)pow((double)2, (double)iterations);

    /* Do the bit reversal */
    i2 = n >> 1;
    j = 0;
    for (i = 0; i < n - 1; ++i)
    {
        if (i < j)
        {
            tx = x[i];
            ty = y[i];
            x[i] = x[j];
            y[i] = y[j];
            x[j] = tx;
            y[j] = ty;
        }
        k = i2;
        while (k <= j)
        {
            j -= k;
            k >>= 1;
        }
        j += k;
    }

    /* Compute the FFT */
    c1 = -1.0; 
    c2 = 0.0;
    l2 = 1;
    for (l = 0; l < iterations; ++l)
    {
        l1 = l2;
        l2 <<= 1;
        u1 = 1; 
        u2 = 0;
        for (j = 0; j < l1; j++) 
        {
            for (i = j; i < n; i += l2) 
            {
                i1 = i + l1;
                t1 = u1 * x[i1] - u2 * y[i1];
                t2 = u1 * y[i1] + u2 * x[i1];
                x[i1] = x[i] - t1; 
                y[i1] = y[i] - t2;
                x[i] += t1;
                y[i] += t2;
            }
            z = u1 * c1 - u2 * c2;
            u2 = u1 * c2 + u2 * c1;
            u1 = z;
        }
        c2 = sqrt((1.0 - c1) / 2.0);
        if (forward) 
            c2 = -c2;
        c1 = sqrt((1.0 + c1) / 2.0);
    }

    /* Scaling for forward transform */
    if (forward)
    {
        for (i = 0; i < n; ++i)
        {
            x[i] /= n;
            y[i] /= n;
        }
    }
}

работает на 20% быстрее, чем этот код?

public static void Transform(DataSet data, Direction direction)
{
    double[] x = data.Real;
    double[] y = data.Imag;
    data.Direction = direction;
    data.ExtremeImag = 0.0;
    data.ExtremeReal = 0.0;
    data.IndexExtremeImag = 0;
    data.IndexExtremeReal = 0;

    long n, i, i1, j, k, i2, l, l1, l2;
    double c1, c2, tx, ty, t1, t2, u1, u2, z;

    /* Calculate the number of points */
    n = (long)Math.Pow(2, data.Iterations);

    /* Do the bit reversal */
    i2 = n >> 1;
    j = 0;
    for (i = 0; i < n - 1; ++i)
    {
        if (i < j)
        {
            tx = x[i];
            ty = y[i];
            x[i] = x[j];
            y[i] = y[j];
            x[j] = tx;
            y[j] = ty;
        }
        k = i2;
        while (k <= j)
        {
            j -= k;
            k >>= 1;
        }
        j += k;
    }

    /* Compute the FFT */
    c1 = -1.0; 
    c2 = 0.0;
    l2 = 1;
    for (l = 0; l < data.Iterations; ++l)
    {
        l1 = l2;
        l2 <<= 1;
        u1 = 1; 
        u2 = 0;
        for (j = 0; j < l1; j++) 
        {
            for (i = j; i < n; i += l2) 
            {
                i1 = i + l1;
                t1 = u1 * x[i1] - u2 * y[i1];
                t2 = u1 * y[i1] + u2 * x[i1];
                x[i1] = x[i] - t1; 
                y[i1] = y[i] - t2;
                x[i] += t1;
                y[i] += t2;
            }
            z = u1 * c1 - u2 * c2;
            u2 = u1 * c2 + u2 * c1;
            u1 = z;
        }
        c2 = Math.Sqrt((1.0 - c1) / 2.0);
        if (direction == Direction.Forward) 
            c2 = -c2;
        c1 = Math.Sqrt((1.0 + c1) / 2.0);
    }

    /* Scaling for forward transform */
    if (direction == Direction.Forward)
    {
        for (i = 0; i < n; ++i)
        {
            x[i] /= n;
            y[i] /= n;
            if (Math.Abs(x[i]) > data.ExtremeReal)
            {
                data.ExtremeReal = x[i];
                data.IndexExtremeReal = (int)i;
            }
            if (Math.Abs(y[i]) > data.ExtremeImag)
            {
                data.ExtremeImag = y[i];
                data.IndexExtremeImag = (int)i;
            }
        }
    }
}

FFT http://www.rghware.com/fft.png

Я создал падение в CPU, увиденное в середине графика, выбрав "Native DLL FFT" в моем приложении:

http://www.rghware.com/InstrumentTuner.zip (исходный код)

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

Во всяком случае, почему я вижу 20% -ное увеличение скорости с использованием собственного кода? Это, кажется, летит перед некоторыми предположениями, которые я ранее имел.

UPDATE

После преобразования функции в небезопасный метод и фиксации проблемы long/int. Новый небезопасный метод работает быстрее, чем собственный метод (довольно круто).

Профиль http://www.rghware.com/profile.png

Очевидно, что проверка привязки массива является причиной замедления на 20% в этом методе БПФ. Из-за этого природа, методы for-loops в этом методе не могут быть оптимизированы.

Спасибо всем за помощь.

Ответы

Ответ 1

Просто глядя на этот код, я подозреваю, что по моему опыту довольно значительное замедление происходит от С++ → С#.

Одна из основных проблем, с которой вы столкнетесь в наивном порту такой процедуры, как это делает С#, - это то, что С# будет добавлять проверку границ на каждый массив. Поскольку вы никогда не перебираете массивы таким образом, чтобы оптимизировать (см. Этот вопрос для деталей), почти каждый доступ к массиву будет получать проверку границ.

Кроме того, этот порт довольно близок к отображению 1- > 1 из C. Если вы запустите это через хороший профилировщик .NET, вы, вероятно, найдете некоторые интересные места, которые можно оптимизировать, чтобы вернуть их обратно С++ с одной или двумя настройками (что почти всегда было моим опытом в таких процедурах портирования).

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

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

Отметьте эту страницу о С# по сравнению с С++, в частности:

"Длинный тип: в С# длинный тип - 64 бита, а в С++ - 32 бита."

Вы должны преобразовать версию С# для использования int, а не долго. В С# длинный 64-битный тип. Это может фактически оказать глубокое влияние на манипуляции с указателем, потому что я считаю, что вы случайно добавляете long- > int-преобразование (с проверкой переполнения) при каждом вызове указателя.

Кроме того, пока вы на нем, вы можете попробовать обернуть всю функцию в unchecked block. С++ не выполняет проверку переполнения, которую вы получаете на С#.

Ответ 2

Это, скорее всего, связано с кодом генерации компилятора JIT, который не так эффективен, как код, сгенерированный собственным компилятором.

Профилирование кода, вероятно, должно быть вашим следующим шагом, если вы заботитесь о 20% -ном снижении производительности или можете использовать библиотеку с оптимизированной полкой.

Ответ 3

Собственный компилятор может делать гораздо более глубокие и более тяжелые оптимизации, чем JIT-компилятор, такие как векторизация, межпроцедурный анализ и т.д. И БПФ могут получить большие ускорения с векторизации.

Ответ 4

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

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

Ответ 5

Я только что запустил код, который он отправил с помощью int вместо long, и это действительно не помогло. Я знаю, что другим людям повезло с FFT в .NET, показывая, что .NET может достигать или превосходить проформы С++ даже с математикой FFT,

Таким образом, мой ответ, либо код плаката более оптимизирован (для C), то тот, который указан в ссылке, или он менее оптимизирован для С#, чем тот, который я связал в статье.

Я выполнил два набора тестов на двух машинах с .NET 2.0. Одна машина имела XPSP2 и имела один процессор, Pentium III с тактовой частотой 850 МГц и 512 Мб ОЗУ. Другая машина построила 5321 Vista и имела один процессор, 2 ГГц Mobile Pentium 4 с 1 ГБ ОЗУ. В каждом случае я вычислил среднее значение из 100 отдельных вычислений БПФ по 217 (131072) значениям данных. Из этих значений я вычислил стандартную ошибку от стандартного отклонения.

Результаты показаны в ms. Результаты для машины Pentium III:

  Not Optimized   Optimized For Space Optimized For Speed
Unmanaged   92.88 ± 0.09    88.23 ± 0.09    68.48 ± 0.03
Managed C++ 72.89 ± 0.03    72.26 ± 0.04    71.35 ± 0.06
C++/CLI 73.00 ± 0.05    72.32 ± 0.03    71.44 ± 0.04
C# Managed  72.21 ± 0.04    69.97 ± 0.08

Результаты для Mobile Pentium 4:

          Not Optimized   Optimized For Space Optimized For Speed
Unmanaged   45.2 ± 0.1  30.04 ± 0.04    23.06 ± 0.04
Managed C++ 23.5 ± 0.1  23.17 ± 0.08    23.36 ± 0.07
C++/CLI 23.5 ± 0.1  23.11 ± 0.07    23.80 ± 0.05
C# Managed  23.7 ± 0.1  22.78 ± 0.03

Ответ 6

Вы использовали профайлер, например AQTime, чтобы узнать, где находится горло бутылки? Иногда при переводе native на управляемый код возникает тривиальная вещь. С другой стороны, поскольку управляемый код в некоторых сценариях медленнее, чем собственный код, вы можете попробовать вместо этого использовать небезопасный код.