Автор Тема: Blur на разных ЯП.  (Прочитано 22815 раз)

valexey_u

  • Hero Member
  • *****
  • Сообщений: 3013
    • Просмотр профиля
Blur на разных ЯП.
« : Апрель 24, 2013, 04:34:26 pm »
Коль пошла такая пьянка, предлагаю погонять один и тот же алгоритм блюра на разных ЯП. Ну и попробовать, возмжно, оптимизировать производительность не изменяя самого алгоритма.

Начало темы, тут: 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.
« Последнее редактирование: Апрель 24, 2013, 04:36:10 pm от valexey_u »
Y = λf.(λx.f (x x)) (λx.f (x x))

Geniepro

  • Hero Member
  • *****
  • Сообщений: 1955
  • Знайте- истина в том, что повторено трижды подряд!
    • Просмотр профиля
Re: Blur на разных ЯП.
« Ответ #1 : Апрель 24, 2013, 04:47:02 pm »
Чем умножать целочисленную переменную на 0.25, а потом переводить результат в целочисленный же вид, не проще ли сдвиг на два бита использовать?
(int)(0.25 * x) == (x >> 2)
to iterate is human, to recurse, divine

Салат «рекурсия»: помидоры, огурцы, салат…

valexey_u

  • Hero Member
  • *****
  • Сообщений: 3013
    • Просмотр профиля
Re: Blur на разных ЯП.
« Ответ #2 : Апрель 24, 2013, 05:03:18 pm »
Чем умножать целочисленную переменную на 0.25, а потом переводить результат в целочисленный же вид, не проще ли сдвиг на два бита использовать?
(int)(0.25 * x) == (x >> 2)
А ты попробуй - исходники все есть :-)
Y = λf.(λx.f (x x)) (λx.f (x x))

Valery Solovey

  • Hero Member
  • *****
  • Сообщений: 509
    • Просмотр профиля
Re: Blur на разных ЯП.
« Ответ #3 : Апрель 24, 2013, 05:06:19 pm »
А от моих оптимизаций руками эффекта не было?

valexey_u

  • Hero Member
  • *****
  • Сообщений: 3013
    • Просмотр профиля
Re: Blur на разных ЯП.
« Ответ #4 : Апрель 24, 2013, 05:09:20 pm »
А от моих оптимизаций руками эффекта не было?
Я еще не пробовал. Народ, попробуйте - я просто не успеваю пробовать все идеи :-)
Y = λf.(λx.f (x x)) (λx.f (x x))

valexey_u

  • Hero Member
  • *****
  • Сообщений: 3013
    • Просмотр профиля
Re: Blur на разных ЯП.
« Ответ #5 : Апрель 24, 2013, 05:11:14 pm »
Чем умножать целочисленную переменную на 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
Y = λf.(λx.f (x x)) (λx.f (x x))

valexey_u

  • Hero Member
  • *****
  • Сообщений: 3013
    • Просмотр профиля
Re: Blur на разных ЯП.
« Ответ #6 : Апрель 24, 2013, 05:26:10 pm »
В 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;
Y = λf.(λx.f (x x)) (λx.f (x x))

ilovb

  • Hero Member
  • *****
  • Сообщений: 2538
  • just another nazi test
    • Просмотр профиля
    • Oberon systems
Re: Blur на разных ЯП.
« Ответ #7 : Апрель 24, 2013, 05:42:20 pm »
x*3+color

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

Да и вообще можно на одном прогоне эти значения в массив загнать.
« Последнее редактирование: Апрель 24, 2013, 05:44:44 pm от ilovb »

valexey_u

  • Hero Member
  • *****
  • Сообщений: 3013
    • Просмотр профиля
Re: Blur на разных ЯП.
« Ответ #8 : Апрель 24, 2013, 05:46:32 pm »
x*3+color

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

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

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

ilovb

  • Hero Member
  • *****
  • Сообщений: 2538
  • just another nazi test
    • Просмотр профиля
    • Oberon systems
Re: Blur на разных ЯП.
« Ответ #9 : Апрель 24, 2013, 06:51:25 pm »
Типа так:
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

  • Hero Member
  • *****
  • Сообщений: 2538
  • just another nazi test
    • Просмотр профиля
    • Oberon systems
Re: Blur на разных ЯП.
« Ответ #10 : Апрель 24, 2013, 07:01:56 pm »
FOR i := 1 TO W1*H1*3 DOКосяк  :) i := 0 конечно

valexey_u

  • Hero Member
  • *****
  • Сообщений: 3013
    • Просмотр профиля
Re: Blur на разных ЯП.
« Ответ #11 : Апрель 24, 2013, 07:06:54 pm »
FOR i := 1 TO W1*H1*3 DOКосяк  :) i := 0 конечно
Ну, это не может сказаться значительно ни на производительности, ни на корректности работы :-)
Y = λf.(λx.f (x x)) (λx.f (x x))

ilovb

  • Hero Member
  • *****
  • Сообщений: 2538
  • just another nazi test
    • Просмотр профиля
    • Oberon systems
Re: Blur на разных ЯП.
« Ответ #12 : Апрель 24, 2013, 07:08:26 pm »
Похоже таки гон. Сейчас еще раз прогнал твой код с DIV и получилось тоже ~440

valexey_u

  • Hero Member
  • *****
  • Сообщений: 3013
    • Просмотр профиля
Re: Blur на разных ЯП.
« Ответ #13 : Апрель 24, 2013, 07:11:17 pm »
Похоже таки гон. Сейчас еще раз прогнал твой код с DIV и получилось тоже ~440
Я прогнал твой вариант. Стало медленнее - было 303 (вариант с DIV), стало 378 секунд.

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

ilovb

  • Hero Member
  • *****
  • Сообщений: 2538
  • just another nazi test
    • Просмотр профиля
    • Oberon systems
Re: Blur на разных ЯП.
« Ответ #14 : Апрель 24, 2013, 07:21:55 pm »
Значит оптимизации тут роли особой не играют. Скорее всего поможет только отключение проверок.