Blur на разных ЯП.

[valexey_u]

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

Начало темы, тут: http://oberspace.dyndns.org/index.php/topic,480.msg15786.html#msg15786

Рассматриваем только алгоритм Сергея. Краткое описание алгоритма (наивная реализация для одного цветового канала флоатов на C#):

Код: [Выделить]

const int N = 13;

for (int n = 0; n < N; n++)
{

  for (int y = 1; y < 479; y++)
  {
    for (int x = 1; x < 639; x++)
    {
      b[y, x] = 0.25 * (a[y - 1, x] + a[y + 1, x] + a[y, x - 1] + a[y, x + 1]);
    }
  }

  for (int y = 1; y < 479; y++)
  {
    for (int x = 1; x < 639; x++)
    {
      a[y, x] = 0.25 * (b[y - 1, x] + b[y + 1, x] + b[y, x - 1] + b[y, x + 1]);
    }
  }
}

Продублирую и дополню и вычищу то, что содержалось в том сообщении (из дополнительного - появилась реализация на КП/ББ):

Итак, вначале результаты. Напомню, что радиус размытия (N) = 13. Обрабатываются все три канала. Число обрабатываемых кадров = 1000.

Код: [Выделить]

C#:
   time: 107 seconds
   fps : 9.35
С++:
   time: 96 seconds
   fps : 10.42
BB/CP (2D массивы аналогично наивной реализации на C#):
   time: 439 seconds
   fps : 2.28
BB/CP (1D массивы, функция вычисления индекса - аналогично C++):
   time: 688 seconds
   fps : 1.45

Исходники:
C#:

Код: [Выделить]

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApplication5
{
    class Program
    {
        static unsafe void Main(string[] args)
        {
            const int H = 480;
            const int W = 640;
            byte[] a = new byte[H * W * 3];
            byte[] b = new byte[H * W * 3];

            System.Diagnostics.Stopwatch timer = new System.Diagnostics.Stopwatch();
            const int N = 13;
            timer.Reset();
            timer.Start();
            const int frames = 1000;
            for (int nn = 0; nn<frames; nn++)
            {
                fixed (byte* pa = &a[0])
                {
                    fixed (byte* pb = &b[0])
                    {
                        for (int n = 0; n < N; n++)
                        {
                            for (int y = 1; y < H - 1; y++)
                            {
                                for (int x = 1; x < W - 1; x++)
                                {
                                    for (int color_shift = 0; color_shift < 3; color_shift++)
                                    {
                                        *(pb + (H * y + x) * 3 + color_shift) = (byte)(0.25 * (*(pa + (H * (y - 1) + x) * 3 + color_shift)
                                        + *(pa + (H * (y + 1) + x) * 3 + color_shift)
                                        + *(pa + (H * y + x - 1) * 3 + color_shift)
                                        + *(pa + (H * y + x + 1) * 3 + color_shift)));
                                    }
                                }
                            }
                            for (int y = 1; y < H - 1; y++)
                            {
                                for (int x = 1; x < W - 1; x++)
                                {
                                    for (int color_shift = 0; color_shift < 3; color_shift++)
                                    {
                                        *(pa + (H * y + x) * 3 + color_shift) = (byte)(0.25 * (*(pb + (H * (y - 1) + x) * 3 + color_shift)
                                            + *(pb + (H * (y + 1) + x) * 3 + color_shift)
                                            + *(pb + (H * y + x - 1) * 3 + color_shift)
                                            + *(pb + (H * y + x + 1) * 3 + color_shift)));
                                    }
                                }
                            }
                        }
                    }
                }
            }

            timer.Stop();
            double dt = timer.Elapsed.TotalSeconds;
            System.Console.WriteLine("N = {0} (R = {1}), dt={2} seconds, FPS = {3}",
                N, 2 * N, dt, (frames / dt));

            System.Console.ReadLine();
        }
    }
}

C++:

Код: [Выделить]

#include <iostream>
#include <ctime>

const int width = 640;
const int height = 480;
const size_t blurRange = 13;

enum Color {
    RED = 0,
    GREEN,
    BLUE
};

int index(int x, int y, Color color) {
    return width*y*3+x*3+color;
}

int main()
{
    volatile unsigned char* volatile in  = new unsigned char[width*height*3];
    volatile unsigned char* volatile out = new unsigned char[width*height*3];

    time_t begin;
    time(&begin);

    const int frames = 1000;

    for (int nn=0; nn<frames; nn++) {
        for (int i=0; i<blurRange; i++) {

            for (int y=1; y<height-1; y++)
                for (int x=1; x<width-1; x++) {
                    out[index(x,y,RED)]= 0.25*(
                        (float)in[index(x,y-1,RED)]+
                               in[index(x,y+1,RED)]+
                               in[index(x-1,y,RED)]+
                               in[index(x+1,y,RED)]);
                    out[index(x,y,GREEN)]= 0.25*(
                        (float)in[index(x,y-1,GREEN)]+
                               in[index(x,y+1,GREEN)]+
                               in[index(x-1,y,GREEN)]+
                               in[index(x+1,y,GREEN)]);
                    out[index(x,y,BLUE)]= 0.25*(
                        (float)in[index(x,y-1,BLUE)]+
                               in[index(x,y+1,BLUE)]+
                               in[index(x-1,y,BLUE)]+
                               in[index(x+1,y,BLUE)]);
                }

            for (int y=1; y<height-1; y++)
                for (int x=1; x<width-1; x++) {
                    in[index(x,y,RED)]=0.25*(
                        (float)out[index(x,y-1,RED)]+
                               out[index(x,y+1,RED)]+
                               out[index(x-1,y,RED)]+
                               out[index(x+1,y,RED)]);
                    in[index(x,y,GREEN)]=0.25*(
                        (float)out[index(x,y-1,GREEN)]+
                               out[index(x,y+1,GREEN)]+
                               out[index(x-1,y,GREEN)]+
                               out[index(x+1,y,GREEN)]);
                    in[index(x,y,BLUE)]=0.25*(
                        (float)out[index(x,y-1,BLUE)]+
                               out[index(x,y+1,BLUE)]+
                               out[index(x-1,y,BLUE)]+
                               out[index(x+1,y,BLUE)]);
                }
        }
    }

    time_t end;
    time(&end);
    auto seconds = difftime(end, begin);
    std::cout << float(frames)/seconds << " " << seconds << std::endl;
}

Тестовый модуль на КП. Две функции:
Blur2DArray - реализация на 2D массивах
Blur1DArray - реализация на одномерных массивах.

Код: [Выделить]

MODULE Blur;
IMPORT Kernel, Out:=StdLog;

CONST
W = 640;
H = 480;
N = 13;
Frames = 1000;

TYPE
Plane = ARRAY W*3, H OF BYTE;
Plane1 = ARRAY W*H*3 OF BYTE;

PROCEDURE Blur2DArray*;
VAR
time : LONGINT;
f, n : INTEGER;
x, y : INTEGER;
color : INTEGER;
a, b : POINTER TO Plane;
BEGIN
NEW(a);
NEW(b);
time := Kernel.Time();

FOR f:=1 TO Frames DO
FOR n:=1 TO N DO

FOR y:=1 TO H-2 DO
FOR x:=1 TO W-2 DO
FOR color:=0 TO 2 DO
b[x*3+color,y] := SHORT(SHORT(SHORT(ENTIER(0.25*(a[x*3+color,y+1]+a[x*3+color,y-1]+a[(x-1)*3,y]+a[(x+1)*3,y])))));
END
END
END;

FOR y:=1 TO H-2 DO
FOR x:=1 TO W-2 DO
FOR color:=0 TO 2 DO
a[x*3+color,y] := SHORT(SHORT(SHORT(ENTIER(0.25*(b[x*3+color,y+1]+b[x*3+color,y-1]+b[(x-1)*3,y]+b[(x+1)*3,y])))));
END
END
END


END
END;

Out.Real((Kernel.Time() - time)/1000)
END Blur2DArray;

PROCEDURE Index(x,y,color : INTEGER) : INTEGER;
BEGIN
RETURN ((x+y*W)*3+color)
END Index;

PROCEDURE Blur1DArray*;
VAR
time : LONGINT;
f, n : INTEGER;
x, y : INTEGER;
color : INTEGER;
a, b : POINTER TO Plane1;
BEGIN
NEW(a);
NEW(b);
time := Kernel.Time();

FOR f:=1 TO Frames DO
FOR n:=1 TO N DO

FOR y:=1 TO H-2 DO
FOR x:=1 TO W-2 DO
FOR color:=0 TO 2 DO
b[Index(x,y,color)] := SHORT(SHORT(SHORT(ENTIER(0.25*(a[Index(x,y+1,color)]+a[Index(x,y-1,color)]+a[Index(x-1,y,color)]+a[Index(x+1,y,color)])))));
END
END
END;

FOR y:=1 TO H-2 DO
FOR x:=1 TO W-2 DO
FOR color:=0 TO 2 DO
a[Index(x,y,color)] := SHORT(SHORT(SHORT(ENTIER(0.25*(b[Index(x,y+1,color)]+b[Index(x,y-1,color)]+b[Index(x-1,y,color)]+b[Index(x+1,y,color)])))));
END
END
END;

END
END;

Out.Real((Kernel.Time() - time)/1000)
END Blur1DArray;
BEGIN
END Blur.


[Geniepro]

Чем умножать целочисленную переменную на 0.25, а потом переводить результат в целочисленный же вид, не проще ли сдвиг на два бита использовать?
(int)(0.25 * x) == (x >> 2)

[valexey_u]

Чем умножать целочисленную переменную на 0.25, а потом переводить результат в целочисленный же вид, не проще ли сдвиг на два бита использовать?
(int)(0.25 * x) == (x >> 2)

А ты попробуй - исходники все есть :-)

[Valery Solovey]

А от моих оптимизаций руками эффекта не было?

[valexey_u]

А от моих оптимизаций руками эффекта не было?

Я еще не пробовал. Народ, попробуйте - я просто не успеваю пробовать все идеи :-)

[valexey_u]

Чем умножать целочисленную переменную на 0.25, а потом переводить результат в целочисленный же вид, не проще ли сдвиг на два бита использовать?
(int)(0.25 * x) == (x >> 2)

Замена на целочисленное деление на 4 в варианте C++ дало прирост в скорости в 1.5 раза:

Код: [Выделить]

C++ (умножение на 0.25):
   time: 92
   fps : 10.87
C++ (деление на 4):
   time: 66
   fps : 15.15


[valexey_u]

В 2D массивном варианте ББ/КП также при переходе не целочисленку быстродействие поднялось в полтора раза:

Код: [Выделить]

BB/CP (2D массивы аналогично наивной реализации на C#, "*0.25"):
   time: 439 seconds
   fps : 2.28
BB/CP (2D массивы аналогично наивной реализации на C#, "/4"):
   time: 303 seconds
   fps : 3.3

Исходник функции (модуль тот же):

Код: [Выделить]

PROCEDURE Blur2DArray*;
VAR
time : LONGINT;
f, n : INTEGER;
x, y : INTEGER;
color : INTEGER;
a, b : POINTER TO Plane;
BEGIN
NEW(a);
NEW(b);
time := Kernel.Time();

FOR f:=1 TO Frames DO
FOR n:=1 TO N DO

FOR y:=1 TO H-2 DO
FOR x:=1 TO W-2 DO
FOR color:=0 TO 2 DO
b[x*3+color,y] := SHORT(SHORT((a[x*3+color,y+1]+a[x*3+color,y-1]+a[(x-1)*3,y]+a[(x+1)*3,y]) DIV 4));
END
END
END;

FOR y:=1 TO H-2 DO
FOR x:=1 TO W-2 DO
FOR color:=0 TO 2 DO
a[x*3+color,y] := SHORT(SHORT((b[x*3+color,y+1]+b[x*3+color,y-1]+b[(x-1)*3,y]+b[(x+1)*3,y]) DIV 4));
END
END
END


END
END;

Out.Real((Kernel.Time() - time)/1000)
END Blur2DArray;


[ilovb]

x*3+color

Зачем так много раз вычислять это? Компилер ведь не оптимизирующий.

Да и вообще можно на одном прогоне эти значения в массив загнать.

[valexey_u]

x*3+color

Зачем так много раз вычислять это? Компилер ведь не оптимизирующий.

Да и вообще можно на одном прогоне эти значения в массив загнать.

You are welcome!
В смысле, перепиши ББшную процедуру так, как тебе кажется правильным, кинь сюда, также кинь сравнительный замер того что было и что стало на твоей машине, и я тоже прогоню тест на своей.

[ilovb]

Типа так:

Код: [Выделить]

MODULE Blur;
    IMPORT Kernel, Out:=StdLog;
   
    CONST
        W = 640; W1 = 640 - 3;
        H = 480; H1 = 480 - 3;
        N = 13;
        Frames = 1000;
       
    TYPE
        Plane = ARRAY W*3, H OF BYTE;
        Plane1 = ARRAY W*H*3 OF INTEGER;
       
    PROCEDURE Blur2DArray*;
    VAR
        time : LONGINT;
        f, n : INTEGER;
        x, y : INTEGER;
        color : INTEGER;
        a, b : POINTER TO Plane;
        c1, c2, c3, c4: POINTER TO Plane1;
        i: INTEGER;
    BEGIN
        NEW(a);
        NEW(b);
        NEW(c1); NEW(c2); NEW(c3); NEW(c4); i := 0;
        time := Kernel.Time();
       
                FOR y:=1 TO H-2 DO               
                    FOR x:=1 TO W-2 DO
                        FOR color:=0 TO 2 DO
                            c1[i] := x*3+color;
                            c2[i] := (x-1)*3;
                            c3[i] := (x+1)*3;
                            c4[i] := y;
                            INC(i);
                        END
                    END
                END;
       
        FOR f:=1 TO Frames DO
            FOR n:=1 TO N DO
           
                (*FOR y:=1 TO H-2 DO               
                    FOR x:=1 TO W-2 DO
                        FOR color:=0 TO 2 DO
                            b[x*3+color,y] :=
                                (a[x*3+color,y+1] +
                                a[x*3+color,y-1] +
                                a[(x-1)*3,y] +
                                a[(x+1)*3,y]) DIV 4;
                        END
                    END
                END;*)
               
                FOR i := 0 TO W1*H1*3 DO
                    x := c1[i];
                    y := c4[i];
                    b[x, y] := SHORT(SHORT((a[x, y+1] + a[x, y-1] + a[c2[i], y] + a[c3[i], y]) DIV 4));
                END;

                (*FOR y:=1 TO H-2 DO               
                    FOR x:=1 TO W-2 DO
                        FOR color:=0 TO 2 DO
                            a[x*3+color,y] :=
                                (b[x*3+color,y+1] +
                                b[x*3+color,y-1] +
                                b[(x-1)*3,y] +
                                b[(x+1)*3,y]) DIV 4;
                        END
                    END
                END*)
               
                FOR i := 1 TO W1*H1*3 DO
                    x := c1[i];
                    y := c4[i];
                    a[x, y] := SHORT(SHORT((b[x, y+1] + b[x, y-1] + b[c2[i], y] + b[c3[i], y]) DIV 4));
                END;
               
            END
        END;
       
        Out.Real((Kernel.Time() - time)/1000)
    END Blur2DArray;
(*Blur1DArray*)
END Blur.

было ~750 (версия с DIV 4)
стало ~440

Но у меня может быть гон. Ибо антивирус мелкомягкий работает.

[ilovb]

Код: [Выделить]

FOR i := 1 TO W1*H1*3 DOКосяк  i := 0 конечно

[valexey_u]

Код: [Выделить]

FOR i := 1 TO W1*H1*3 DOКосяк  i := 0 конечно

Ну, это не может сказаться значительно ни на производительности, ни на корректности работы :-)

[ilovb]

Похоже таки гон. Сейчас еще раз прогнал твой код с DIV и получилось тоже ~440

[valexey_u]

Похоже таки гон. Сейчас еще раз прогнал твой код с DIV и получилось тоже ~440

Я прогнал твой вариант. Стало медленнее - было 303 (вариант с DIV), стало 378 секунд.

Что в общем то и следовало ожидать - вместо пересылки из регистра в регистр мы получили пересылку из ОЗУ (пусть даже это кэш первого или второго уровня).

[ilovb]

Значит оптимизации тут роли особой не играют. Скорее всего поможет только отключение проверок.