Помогите оптимизировать целочисленную математику

Question

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

Этот код используется для преобразования данных пикселей после выполнения фильтрации NTSC. Я предоставил данные профилирования рядом со строками в виде% от общего времени выполнения, чтобы вы могли видеть, что нужно для работы. На эту функцию в целом приходится около половины моего бега (48% самостоятельно, 53% с детьми).

// byte[] ntscOutput;
// ushort[] filtered; - the pixels are ushort, because of the texture color depth

int f_i = 0;
int row = 0;
for (int i = 0; i < 269440; i++)                                  // 3.77 %
{
    int joined = (ntscOutput[f_i + 1] << 8) + ntscOutput[f_i];    // 6.6 %
    f_i += 2;                                                     // 1.88 %

    filtered[i] = (ushort)joined;                                 // 2.8 %

    ushort red = (ushort)(joined & 0xf800);                       // }
    ushort green = (ushort)(joined & 0x7e0);                      //  > 2.36 % each
    ushort blue = (ushort)(joined & 0x1f);                        // }

    red = (ushort)((red - (red >> 3)) & 0xf800);                  // }
    green = (ushort)((green - (green >> 3)) & 0x7e0);             //  > 4.24 % each
    blue = (ushort)((blue - (blue >> 3)) & 0x1f);                 // }

    filtered[i + 602] = (ushort)(red | green | blue);             // 5.65 %

    row++;
    if (row > 601)
    {
        row = 0;
        i += 602;
    }
}

Я открыт для любого метода оптимизации. Если на самом деле невозможно улучшить реальные математические операции, может быть, что-то с небезопасным кодом и указателями сработает в манипулировании массивами, чтобы предотвратить так много приведений? Может быть, как-то изменить типы моего массива, или, может быть, развернуть цикл? Я уверен, что это возможно, потому что сама операция фильтрации - это огромная функция библиотеки C с множеством циклов и математических операций, и все это составляет 1,35% моего времени выполнения.

Answer 1

Вы запрашиваете микрооптимизацию, но пытались ли вы сначала оптимизировать макрос?

269440 делится на любые 2 ^ n, это означает, что вы можете легко связать этот код с числом имеющихся у вас процессоров, иимеют в основном скорость n-tupled.

Просто убедитесь, что не объявляете потоки внутри этого кода.

Микрооптимизация с использованием ключевого слова unchecked может быть достигнутаблок rgb, окружая все непроверенным {}, но это, вероятно, мало поможет.

Реальная оптимизация будет такой:

Для всех возможных значений joined (ushort) storeвсе результирующие значения filtered[i + 602] в массив с индексом каждого существа (ushort) соединяются, и не используют вычисления, а получают значение непосредственно из массива.

Затем пропустите часть rgb и используйте в качестветело цикла:

filtered[i] = (ushort)joined;
filtered[i+602] = precalculatedValues[(ushort)joined];

Таким способом можно преобразовать объединенный в ushort (после удаления побитовых операций).

Answer 2

Мне интересно, так как вы зацикливаетесь 269440 раз (ну, реже с переменной строки), и есть только 2 ^ 16 возможностей для результата отфильтрованной переменной, вы рассматривали таблицу поиска ?Я не уверен, насколько хорошо массив 2 ^ 16 будет сидеть в C #, но, возможно, стоит попробовать.

Answer 3

Нет необходимости разбивать соединенный ushort и соединять результат обратно.Вы можете вычислить вывод напрямую, используя

 filtered[i + 602] = (ushort)(joined - ((joined >> 3) & 0x18e3));            

Позвольте мне объяснить это: в вашем примере синий использует биты 0-4, зеленый использует 5-10, а красный использует 11-15.Биты соединения (в порядке с прямым порядком байтов)

rrrr rggg gggb bbbb

join >> 3 сдвигают все компоненты (красный, зеленый, синий) на 3.Т.е. объединенный >> 3 имеет формат

000r rrrr gggg ggbb

Мы хотим замаскировать биты из одного компонента, которые перетекают в другой компонент.Это делается с помощью 0x18e3.Т.е. (объединено >> 3) & 0x18e3 имеет формат

000r r000 ggg0 00bb

Далее вы делаете вычитание

joined - ((joined >> 3) & 0x18e3)

Thisвычитает сдвинутые компоненты RGB из оригинала за один шаг.Тем не менее, вы должны учитывать недостатки.Т.е. вы не хотите, чтобы нижняя часть зеленого компонента распространялась на красный компонент.Небольшая мысль показывает, что это не проблема.Все сдвинутые компоненты меньше, чем их первоначальное значение, и, следовательно, не может быть недопущения.Другими словами, одно приведенное выше утверждение должно работать нормально.(Конечно, вам все равно придется тщательно проверять).

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

Answer 4

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

ushort redblue = (ushort)(joined & 0xf81f);
ushort green = (ushort)(joined & 0x7e0);

redblue = (ushort)((redblue - (redblue >> 3)) & 0xf81f);
green = (ushort)((green - (green >> 3)) & 0x7e0);

filtered[i + 602] = (ushort)(redblue | green);

Чтобы улучшить читаемость, вы должны определить константы для всех этих магических чисел.

Answer 5

Я следовал за некоторыми уловками на этой странице: http://developer.amd.com/documentation/articles/pages/7162004127.aspx

Может быть, кто-то еще найдет дополнительные пункты этой страницы? Добро пожаловать в комментарий ниже.

uint f_i = 0;
uint row = 0;
ushort red, green, blue;
ushort joined;
for (uint i = 0; i < 269440; i++)                                  // 3.77 %
{
    joined = (ntscOutput[f_i + 1] << 8) + ntscOutput[f_i];    // 6.6 %
    f_i += 2;                                                     // 1.88 %

    filtered[i] = joined;                                 // 2.8 %

    red = (joined & 0xf800);                       // }
    green = (joined & 0x7e0);                      //  > 2.36 % each
    blue = (joined & 0x1f);                        // }

    red = (ushort)((red - (red >> 3)) & 0xf800);                  // }
    green = (ushort)((green - (green >> 3)) & 0x7e0);             //  > 4.24 % each
    blue = (ushort)((blue - (blue >> 3)) & 0x1f);                 // }

    filtered[i + 602] = (ushort)(red | green | blue);             // 5.65 %

    row++;
    if (row > 601)
    {
        row = 0;
        i += 602;
    }
}

Answer 6

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

Да, вы можете добиться значительного ускорения, используя небезопасные. Нет никаких оснований для установки линии joined на 6%, и состояние петли также может быть улучшено. Попробуйте:

int row = 0;
int remaining = 269440/2;
fixed (ushort* p = (ushort*)&ntscOutput[0])
    do {
        int joined = *p;
        p++;

        // ...

    } while (--remaining > 0);