Форум программистов, компьютерный форум CyberForum.ru

оптимизация, медленный доступ к трехмерному массиву - C++

Восстановить пароль Регистрация
 
muaddib
0 / 0 / 0
Регистрация: 14.10.2011
Сообщений: 13
22.03.2013, 10:37     оптимизация, медленный доступ к трехмерному массиву #1
Здравствуйте, публикуюсь здесь потому что нет доступа к разделу экспертов.
Требуется перевести буфер из одного формата в другой по определенной формуле с плавающей точкой, а именно из формата yuyv в формат rgb24 (если это что-то кому то скажет).
Хотел сократить расчеты записав все значения в массив и просто беря оттуда нужные значения.
Но оказывается что каждый раз считать получается быстрее, вопрос почему?
Компилятор gcc.
Привожу тестовый код программы, непосредственный расчет ведется со скоростью 18 циклов/сек, если брать рассчитанные значения из массива - 6 циклов/сек.
Исходный буфер pbuffer заполняю случайными значения от 0 до 255. Если буфер заполнять константами, то скорость большая, но думаю это из-за оптимизации.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
#include <iostream>
#include <time.h>
#include <cstdlib>
 
using namespace std;
 
#define rgb_ptr unsigned char*
 
static const int BPP_YUY2 = 2;
static const int BPP_YUY2_PIXEL = 4;
static const int BPP_RGB24 = 3;
 
unsigned char tableR[256][256][256];
unsigned char tableG[256][256][256];
unsigned char tableB[256][256][256];
 
inline char clip(int x){
    if (x>255)
        return 255;
    if (x<0)
        return 0;
    return x;
}
 
void yuv2rgb(unsigned char y, unsigned char u, unsigned char v, unsigned char *r, unsigned char *g, unsigned char *b)
{
    float C = y - 16;
    float D = u - 128;
    float E = v - 128;
    *r = clip(C + ( 1.402 * E )) ;
    *g = clip(C - ( 0.344136 * D + 0.714136 * E )) ;
    *b = clip(C + ( 1.772 * D )) ;
}
 
void fillTables(void)
{
    int i,j,k;
 
    for (i=0;i<256;i++)
    {
        for (j=0;j<256;j++)
            for (k=0;k<256;k++)
                yuv2rgb(i,j,k,&tableR[i][j][k],&tableG[i][j][k],&tableB[i][j][k]);
    }
 
}
 
void getTables(unsigned char y, unsigned char u, unsigned char v, unsigned char *r, unsigned char *g, unsigned char *b)
{
    *r = tableR[y][u][v];
    *g = tableG[y][u][v];
    *b = tableB[y][u][v];
}
 
void yuyv_to_rgb(rgb_ptr buffer_yuyv, rgb_ptr buffer_rgb, int width, int height)
{
    rgb_ptr pixel_16;   // for YUYV
    rgb_ptr pixel_24;// for RGB
    int y0, u0, v0, y1;
    unsigned char r, g, b;
    unsigned char r1,g1,b1;
    if ( buffer_yuyv == NULL || buffer_rgb == NULL)
    return;
 
    pixel_16 = buffer_yuyv;//width * height * 2
    pixel_24 = buffer_rgb;//width * height * 3
 
    int i = 0, j = 0;
   // while ((i + 2) < height * width * 2)
    for (i=0;i < (height * width * 2 -2);i=i+BPP_YUY2_PIXEL)
    {
        y0 = pixel_16[i];
        u0 = pixel_16[i+1];
        y1 = pixel_16[i+2];
        v0 = pixel_16[i+3];
 
        //yuv2rgb(y0, u0, v0, &r, &g, &b);
        getTables(y0, u0, v0, &r, &g, &b);  // 1st pixel
 
        pixel_24[j] = r;
        pixel_24[j + 1] = g;
        pixel_24[j + 2] = b;
 
        //yuv2rgb(y1, u0, v0, &r1, &g1, &b1);
        getTables(y1, u0, v0, &r1, &g1, &b1);// 2nd pixel
 
        pixel_24[j+BPP_RGB24] = r1;
        pixel_24[j + 1 + BPP_RGB24] = g1;
        pixel_24[j + 2 + BPP_RGB24] = b1;
 
        j+=BPP_RGB24;
        j+=BPP_RGB24;
        //i += BPP_YUY2_PIXEL;
    }
 
}
 
int main()
{
    timespec t1;
    timespec t2;
    double t;
    const int ncycles=100;
    unsigned char *pdata = new unsigned char[1024*768*2]; //yuv
    unsigned char *data = new unsigned char[1024*768*3];  //rgb24
 
    int i;
    srand(time(NULL));
 
    fillTables();
 
    for (i=0;i<1024*768*2;i++)
        pdata[i] = rand() % 255;
 
    //for (i=0;i<1024*768*2;i++)
    //    pdata[i] = i%255;
 
    clock_gettime(1,&t1);
 
    for (i=0;i<ncycles;i++)
    {
       yuyv_to_rgb(pdata,data,1024,768);
       cout<<"#"<<i<<" ";
       cout.flush();
    }
 
    clock_gettime(1,&t2);
 
    t= (t2.tv_sec-t1.tv_sec)+(t2.tv_nsec-t1.tv_nsec)/1000000000.0; //складываем секунды и наносекунды
    cout<<"\nTime: "<<t<< "secs\n";
    cout<<"Cycles per sec: "<<ncycles/t<<"\n";
 
    delete pdata;
    delete data;
    return 0;
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
22.03.2013, 10:37     оптимизация, медленный доступ к трехмерному массиву
Посмотрите здесь:

Движение по массиву C++
C++ Поиск по массиву
C++ Вопрос по массиву.
фрагмент по массиву C++
C++ Поиск по массиву
Доступ к массиву из другой формы C++
C++ Проход по массиву
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Tulosba
:)
Эксперт С++
4382 / 3225 / 297
Регистрация: 19.02.2013
Сообщений: 9,044
22.03.2013, 12:47     оптимизация, медленный доступ к трехмерному массиву #2
Для оценки скорости выполнения следует убрать cout, и я не уверен, что clock_gettime() в этом случае уместен (почему кстати параметр 1, а не какой-нибудь CLOCK_PROCESS_CPUTIME_ID). Я бы использовал просто clock().
Цитата Сообщение от muaddib Посмотреть сообщение
Но оказывается что каждый раз считать получается быстрее
Двоякая фраза. Каждый раз вычислять или каждый раз считывать из таблицы?
muaddib
0 / 0 / 0
Регистрация: 14.10.2011
Сообщений: 13
22.03.2013, 14:28  [ТС]     оптимизация, медленный доступ к трехмерному массиву #3
Для оценки скорости выполнения следует убрать cout, и я не уверен, что clock_gettime() в этом случае уместен (почему кстати параметр 1, а не какой-нибудь CLOCK_PROCESS_CPUTIME_ID). Я бы использовал просто clock().
Скорость выполнения здесь заметна невооруженным глазом, так что можно использовать clock суть от этого не сильно меняется.

Двоякая фраза. Каждый раз вычислять или каждый раз считывать из таблицы?
Вычислять быстрее.
Tulosba
:)
Эксперт С++
4382 / 3225 / 297
Регистрация: 19.02.2013
Сообщений: 9,044
22.03.2013, 14:53     оптимизация, медленный доступ к трехмерному массиву #4
Могу предположить, что в силу того, что таблицы довольно большие (по 16 Мб каждая) в кэш всё это дело не поместится, в итоге - быстрее вычислять по-новой. Для более точных оценок могу предложить использовать профайлер.
muaddib
0 / 0 / 0
Регистрация: 14.10.2011
Сообщений: 13
22.03.2013, 15:55  [ТС]     оптимизация, медленный доступ к трехмерному массиву #5
Что значит в кэш?
Значит ли это что доступ к памяти медленней чем, операции с плавающей точкой?
Профайлер и говорит, что здесь самое узкое место.
Tulosba
:)
Эксперт С++
4382 / 3225 / 297
Регистрация: 19.02.2013
Сообщений: 9,044
22.03.2013, 17:30     оптимизация, медленный доступ к трехмерному массиву #6
Цитата Сообщение от muaddib Посмотреть сообщение
Значит ли это что доступ к памяти медленней чем, операции с плавающей точкой?
А кто-то может гарантировать обратное?
Цитата Сообщение от muaddib Посмотреть сообщение
Что значит в кэш?
У Вас в getTables() обращение к 3 разным массивам (по 16Мб каждый), следовательно извлеченные элементы находятся далеко друг от друга и каждый раз идет запрос к ОЗУ (если бы элементы были рядом, они могли лежать в кэше и считались бы на порядок быстрее, т.к. при чтении памяти в кэш попадает сразу блок смежных данных), а мог бы к быстрому кэшу.
muaddib
0 / 0 / 0
Регистрация: 14.10.2011
Сообщений: 13
25.03.2013, 11:24  [ТС]     оптимизация, медленный доступ к трехмерному массиву #7
Спасибо за ответ, похоже что так.
Процессору быстрее посчитать 3 многочлена с плавающей точкой, чем найти готовый результат в памяти размером 48 Мб.
diagon
Higher
 Аватар для diagon
1921 / 1187 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
25.03.2013, 11:40     оптимизация, медленный доступ к трехмерному массиву #8
Цитата Сообщение от muaddib Посмотреть сообщение
Процессору быстрее посчитать 3 многочлена с плавающей точкой, чем найти готовый результат в памяти размером 48 Мб.
Логично, обращение к внешней памяти занимает сотни процессорных тактов. Можно еще попробовать поиграться с упреждающей выборкой... Но если есть возможность за десяток-другой тактов посчитать значение заново, то, разумеется, надо считать заново.

Цитата Сообщение от muaddib Посмотреть сообщение
Значит ли это что доступ к памяти медленней чем, операции с плавающей точкой?
Намного.
Tulosba
:)
Эксперт С++
4382 / 3225 / 297
Регистрация: 19.02.2013
Сообщений: 9,044
25.03.2013, 12:08     оптимизация, медленный доступ к трехмерному массиву #9
Цитата Сообщение от diagon Посмотреть сообщение
Цитата Сообщение от muaddib Посмотреть сообщение
Значит ли это что доступ к памяти медленней чем, операции с плавающей точкой?
Намного.
Есть какие-то пруфы на этот счет?
taras atavin
Ушёл с форума.
 Аватар для taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
25.03.2013, 12:16     оптимизация, медленный доступ к трехмерному массиву #10
Цитата Сообщение от muaddib Посмотреть сообщение
Что значит в кэш?
Значит ли это что доступ к памяти медленней чем, операции с плавающей точкой?
Профайлер и говорит, что здесь самое узкое место.
Смотря к какой памяти. Если к кешу, то такта 2, а к основной оперативе запросто 18 и больше + только одно ядр0о в каждый момент имеет доступ к шине. Масивы же ещё трёхмерные в кеш редко влазят.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
25.03.2013, 12:46     оптимизация, медленный доступ к трехмерному массиву
Еще ссылки по теме:

По массиву Y сформировать массив Z C++
C++ Как получить доступ к массиву из другого класса?
Доступ к динамическому массиву C++
Возможность получать доступ к массиву, объявленному в другом файле C++
Перемещение по массиву C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
diagon
Higher
 Аватар для diagon
1921 / 1187 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
25.03.2013, 12:46     оптимизация, медленный доступ к трехмерному массиву #11
Цитата Сообщение от Tulosba Посмотреть сообщение
Есть какие-то пруфы на этот счет?
Ну, например, отсюда
Время отклика для оперативной памяти > 100
При этом среднее колво тактов для операций с вещественными числами примерно равно 2.
Ну и вот, оттуда же
С ростом производительности процессоров возникла проблема, связанная с тем, что скорость доступа к внешней памяти стала ниже скорости вычислений.

UPD:
Цитата Сообщение от diagon Посмотреть сообщение
При этом среднее колво тактов для операций с вещественными числами примерно равно 2
Тут немного наврал, так как учитывал суперскалярность(и смотрел на throughput, а не на latency).
Вот еще
integer from main memory ~200
Floating Point multiply-and-add (fma) 5
Floating Point convert integer to fixed-point floating point (setf) 9
Floating Point convert fixed-point floating-point to integer (getf) 2
Floating Point fixed-point to/from floating-point conversion (fcvt) 7
Floating Point fixed-point floating point multiply-and-add (xma) 7
Yandex
Объявления
25.03.2013, 12:46     оптимизация, медленный доступ к трехмерному массиву
Ответ Создать тему
Опции темы

Текущее время: 01:01. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru