еще оптимизация я могу сделать для этой функции? - PullRequest
1 голос
/ 15 марта 2011

У меня есть простая функция размытия рамки в графической библиотеке (для JavaScript / canvas, с использованием ImageData), которую я пишу.

Я сделал несколько оптимизаций, чтобы избежать скоплений избыточного кода, таких как циклычерез [0..3] для каналов вместо копирования кода и реализации каждого окружающего пикселя с помощью одной не скопированной строки кода с усреднением значений в конце.

Это были оптимизации для сокращения избыточных строккод.Могу ли я выполнить какие-либо дальнейшие оптимизации такого рода или, что еще лучше, изменить что-либо, что может улучшить производительность самой функции?

Запуск этой функции в области изображения 200x150 с Core 2Duo занимает около 450 мс на Firefox 3.6, 45 мс на Firefox 4 и около 55 мс на Chromium 10.

Различные заметки

  • expressive.data.get возвращает ImageData object
  • expressive.data.put записывает содержимое ImageData обратно на холст
  • , а ImageData - это объект с:
    • unsigned long width
    • unsigned long height
    • Array data, одномерные данные в формате r, g, b, a, r, g, b, a ...

код

expressive.boxBlur = function(canvas, x, y, w, h) {
    // averaging r, g, b, a for now
    var data = expressive.data.get(canvas, x, y, w, h);
    for (var i = 0; i < w; i++)
        for (var j = 0; j < h; j++)
            for (var k = 0; k < 4; k++) {
                var total = 0, values = 0, temp = 0;
                if (!(i == 0 && j == 0)) {
                    temp = data.data[4 * w * (j - 1) + 4 * (i - 1) + k];
                    if (temp !== undefined) values++, total += temp;
                }
                if (!(i == w - 1 && j == 0)) {
                    temp = data.data[4 * w * (j - 1) + 4 * (i + 1) + k];
                    if (temp !== undefined) values++, total += temp;
                }
                if (!(i == 0 && j == h - 1)) {
                    temp = data.data[4 * w * (j + 1) + 4 * (i - 1) + k];
                    if (temp !== undefined) values++, total += temp;
                }
                if (!(i == w - 1 && j == h - 1)) {
                    temp = data.data[4 * w * (j + 1) + 4 * (i + 1) + k];
                    if (temp !== undefined) values++, total += temp;
                }
                if (!(j == 0)) {
                    temp = data.data[4 * w * (j - 1) + 4 * (i + 0) + k];
                    if (temp !== undefined) values++, total += temp;
                }
                if (!(j == h - 1)) {
                    temp = data.data[4 * w * (j + 1) + 4 * (i + 0) + k];
                    if (temp !== undefined) values++, total += temp;
                }
                if (!(i == 0)) {
                    temp = data.data[4 * w * (j + 0) + 4 * (i - 1) + k];
                    if (temp !== undefined) values++, total += temp;
                }
                if (!(i == w - 1)) {
                    temp = data.data[4 * w * (j + 0) + 4 * (i + 1) + k];
                    if (temp !== undefined) values++, total += temp;
                }
                values++, total += data.data[4 * w * j + 4 * i + k];
                total /= values;
                data.data[4 * w * j + 4 * i + k] = total;
            }
    expressive.data.put(canvas, data, x, y);
};

Ответы [ 5 ]

1 голос
/ 15 марта 2011

Возможно (просто возможно) перемещение if проверок в максимально возможной степени было бы преимуществом. Позвольте мне представить псевдокод:

Я просто назову код зацикливания на k «внутренний цикл» для простоты

// do a specialized version of "inner loop" that assumes i==0
for (var i = 1; i < (w-1); i++)
     // do a specialized version of "inner loop" that assumes j==0 && i != 0 && i != (w-1)
     for (var j = 1; j < (h-1); j++)
        // do a general version of "inner loop" that can assume i != 0 && j != 0 && i != (w-1) && j != (h-1)
     }
     // do a specialized version of "inner loop" that assumes j == (h - 1) && i != 0 && i != (w-1)
}
// do a specialized version of "inner loop" that assumes i == (w - 1)

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

1 голос
/ 15 марта 2011

Если вы используете только данные var как data.data, вы можете изменить:

var data = expressive.data.get(canvas, x, y, w, h);

до:

var data = expressive.data.get(canvas, x, y, w, h).data;

и измените каждую строку как:

temp = data.data[4 * w * (j - 1) + 4 * (i - 1) + k];

до:

temp = data[4 * w * (j - 1) + 4 * (i - 1) + k];

, и вы сохраните некоторые имена поиска.

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

Обновление:

Кроме того, if (i != 0 || j != 0) может быть быстрее, чем if (!(i == 0 && j == 0)) не только из-за отрицания, но и из-за короткого замыкания.

(Проведите собственные эксперименты с == против === и != против !==, потому что мои быстрые тесты показали результаты, которые кажутся мне нелогичными.)

А также некоторые из тестов проводятся много раз, и некоторые из них взаимоисключающие, но в любом случае проверяются без другого. Вы можете попытаться изменить его, добавив больше вложенных ifs и больше ifs.

0 голосов
/ 15 марта 2011

объявление temp = 0 не обязательно, просто напишите var total = 0, values = 0, temp;.

Следующим шагом является возврат в обратном направлении.

var length = 100,
    i;

for (i = 0; i < length; i++) {}

медленнее, чем

var length = 100;

for (; length != 0; length--) {}

Третий совет - использовать Устройство Даффи для огромных петель.

0 голосов
/ 15 марта 2011

Вы можете вытащить некоторые общие выражения:

for (var i = 0; i < w; i++) {
    for (var j = 0; j < h; j++) {
        var t = 4*w*j+4*i;
        var dt = 4*j;
        for (var k = 0; k < 4; k++) {
            var total = 0, values = 0, temp = 0;
            if (!(i == 0 && j == 0)) {
                temp = data.data[t-dt-4+k];
                if (temp !== undefined) values++, total += temp;
            }
            if (!(i == w - 1 && j == 0)) {
                temp = data.data[t-dt+4+k];
                if (temp !== undefined) values++, total += temp;
            }
            if (!(i == 0 && j == h - 1)) {
                temp = data.data[t+dt-4+k];
                if (temp !== undefined) values++, total += temp;
            }
            if (!(i == w - 1 && j == h - 1)) {
                temp = data.data[t+dt+4+k];
                if (temp !== undefined) values++, total += temp;
            }
            if (!(j == 0)) {
                temp = data.data[t-dt+k];
                if (temp !== undefined) values++, total += temp;
            }
            if (!(j == h - 1)) {
                temp = data.data[t+dt+k];
                if (temp !== undefined) values++, total += temp;
            }
            if (!(i == 0)) {
                temp = data.data[t-4+k];
                if (temp !== undefined) values++, total += temp;
            }
            if (!(i == w - 1)) {
                temp = data.data[t+4+k];
                if (temp !== undefined) values++, total += temp;
            }
            values++, total += data.data[t+k];
            total /= values;
            data.data[t+k] = total;
        }
    }
}

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

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

Довольно болезненно, но, возможно, очень эффективно: вы можете потерять множество условных операций, разбив свои циклы на {0,1..w-2, w-1} и {0,1..h-2, h- 1}.

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

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

0 голосов
/ 15 марта 2011

Незначительная оптимизация:

var imgData = expressive.data.get(canvas, x, y, w, h);
var data = imgData.data;

// in your if statements
temp = data[4 * w * (j - 1) + 4 * (i - 1) + k];

expressive.data.put(canvas, imgData, x, y) 

Вы также можете выполнить некоторые незначительные оптимизации в своих индексах, например:

4 * w * (j - 1) + 4 * (i - 1) + k // is equal to
4 * ((w * (j-1) + (i-1)) + k

var jmin1 = (w * (j-1))
var imin1 = (i-1)
//etc, and then use those indices at the right place

Также ставьте {} после каждого оператора forесть в вашем коде.2 дополнительных персонажа не будут иметь большого значения.Потенциальные ошибки будут.

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...