Можно ли оптимизировать этот код? - PullRequest
Новая
       81

Можно ли оптимизировать этот код?

7 голосов
/ 31 марта 2009

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

int xSize = ResultImageData.GetLength(0);
int ySize = ResultImageData.GetLength(1);

for (int x = 0; x < xSize; x++)
{                
   for (int y = 0; y < ySize; y++) 
   {                                                
      ResultImageData[x, y] = (byte)((CurrentImageData[x, y] * AlphaValue) +
                                    (AlphaImageData[x, y] * OneMinusAlphaValue));
   }
}

Цикл в настоящее время занимает ~ 11 мс, что, как я полагаю, связано в основном с доступом к значениям байтовых массивов, так как вычисления довольно просты (2 умножения и 1 сложение).

Что я могу сделать, чтобы ускорить это? Это критичная ко времени часть моей программы, и этот код вызывается 80-100 раз в секунду, поэтому любое увеличение скорости, даже небольшое, будет иметь значение. Также в данный момент xSize = 768 и ySize = 576, но в будущем это увеличится.

Обновление : Благодаря Гуффа (см. Ответ ниже), следующий код экономит мне 4-5 мс на цикл. Хотя это небезопасный код. 

int size = ResultImageData.Length;
int counter = 0;
unsafe
{
    fixed (byte* r = ResultImageData, c = CurrentImageData, a = AlphaImageData)
    {
        while (size > 0)
        {
            *(r + counter) = (byte)(*(c + counter) * AlphaValue + 
                                    *(a + counter) * OneMinusAlphaValue);
            counter++;
            size--;
        }
    }
}

Ответы [ 14 ]

5 голосов
/ 31 марта 2009

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

int size = ResultImageData.Length;
unsafe 
{
   fixed(byte* rp = ResultImageData, cp = CurrentImageData, ap = AlphaImageData) 
   {
      byte* r = rp;
      byte* c = cp;
      byte* a = ap;
      while (size > 0) 
      {
         *r = (byte)(*c * AlphaValue + *a * OneMinusAlphaValue);
         r++;
         c++;
         a++;
         size--;
      }
   }
}

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

5 голосов
/ 31 марта 2009

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

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

4 голосов
/ 31 марта 2009

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

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

Пример (псевдокод) может быть таким: 

void process(int x, int y) {
    ResultImageData[x, y] = (byte)((CurrentImageData[x, y] * AlphaValue) +
        (AlphaImageData[x, y] * OneMinusAlphaValue));
}

ThreadPool pool(3); // 3 threads big

int xSize = ResultImageData.GetLength(0);
int ySize = ResultImageData.GetLength(1);

for (int x = 0; x < xSize; x++) {
     for (int y = 0; y < ySize; y++)  {
         pool.schedule(x, y);  // this will add all tasks to the pool's work queue
     }
}

pool.waitTilFinished(); // wait until all scheduled tasks are complete

РЕДАКТИРОВАТЬ: Майкл Медоус упоминается в комментарии, что plinq может быть подходящей альтернативой: http://msdn.microsoft.com/en-us/magazine/cc163329.aspx

4 голосов
/ 31 марта 2009

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

Одно замечание: как у вас время? Если вы используете DateTime, помните, что у этого класса плохое разрешение. Вы должны добавить внешний цикл и повторить операцию, скажем, десять раз - держу пари, результат меньше 110 мс. 

for (int outer = 0; outer < 10; ++outer)
{
    for (int x = 0; x < xSize; x++)
    {                
         for (int y = 0; y < ySize; y++) 
         {                                                
              ResultImageData[x, y] = (byte)((CurrentImageData[x, y] * AlphaValue) +
                                             (AlphaImageData[x, y] * OneMinusAlphaValue));
         }
    }
}
3 голосов
/ 31 марта 2009

Вы, вероятно, страдаете от проверки границ. Как утверждает Джон Скит, зубчатый массив вместо многомерного (то есть data[][] вместо data[,]) будет быстрее, как это ни странно.

Компилятор оптимизирует 

for (int i = 0; i < data.Length; i++)

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

По той же причине кэширование или поднятие свойства Length (помещение его в переменную, такую ​​как xSize) также было плохой вещью, хотя я не смог проверить это в Framework 3.5

3 голосов
/ 31 марта 2009

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

* 1003 Е.Г. * 

int xSize = ResultImageData.GetLength(0) -1;
int ySize = ResultImageData.GetLength(1) -1; //minor optimization suggested by commenter

for (int x = xSize; x >= 0; --x)
{                
     for (int y = ySize; y >=0; --y) 
     {                                                
          ResultImageData[x, y] = (byte)((CurrentImageData[x, y] * AlphaValue) +
                                         (AlphaImageData[x, y] * OneMinusAlphaValue));
     }
}

См. http://dotnetperls.com/Content/Decrement-Optimization.aspx

3 голосов
/ 31 марта 2009

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

2 голосов
/ 01 апреля 2009

Попробуйте поменять местами циклы x и y для получения более линейного шаблона доступа к памяти и (таким образом) уменьшения количества кешей, например, так. 

int xSize = ResultImageData.GetLength(0);
int ySize = ResultImageData.GetLength(1);

for (int y = 0; y < ySize; y++) 
{
    for (int x = 0; x < xSize; x++)
    {
        ResultImageData[x, y] = (byte)((CurrentImageData[x, y] * AlphaValue) +
            (AlphaImageData[x, y] * OneMinusAlphaValue));
    }
}
1 голос
/ 01 апреля 2009

Интересно, что данные изображений часто очень похожи, что означает, что вычисления, вероятно, очень повторяющиеся. Вы изучали возможность поиска таблицы для расчетов? Таким образом, в любое время, когда 0,8 умножалось на 128 - значение [80,128], которое вы предварительно рассчитали до 102,4, вы просто искали это? В основном вы тратите пространство памяти на скорость процессора, но это может сработать для вас.

Конечно, если ваши данные изображения имеют слишком высокое разрешение (и слишком большое значение), это может оказаться нецелесообразным.

1 голос
/ 01 апреля 2009

Вы также можете взглянуть на среду исполнения Mono и ее расширения Simd. Возможно, некоторые ваши расчеты могут использовать ускорение SSE, так как я понимаю, что вы в основном делаете векторные вычисления (я не знаю, до какого размера вектора есть ускорение для умножения, но есть для некоторых размеров)

(Сообщение в блоге, объявляющее Mono.Simd: http://tirania.org/blog/archive/2008/Nov-03.html)

Конечно, это не сработает в Microsoft .NET, но, возможно, вы заинтересованы в некоторых экспериментах.

Страница:
...