Как сделать оптимизацию

[Igors]

Да и ещё, можно сравнить c std::vector<dool>. Для bool у вектора написана специализация, оптимизированная под все эти операции. Думаю с вектором получатся самые лучшие характеристики.
Но это нужно проверять... На нормальных тестах) 

Тест я подогнал, сделайте copy/paste и вставьте std::vector<dool>.
Ждем-с 

[m_ax]

Да и ещё, можно сравнить c std::vector<dool>. Для bool у вектора написана специализация, оптимизированная под все эти операции. Думаю с вектором получатся самые лучшие характеристики.
Но это нужно проверять... На нормальных тестах) 

Тест я подогнал, сделайте copy/paste и вставьте std::vector<dool>.
Ждем-с 

Сейчас пока времени нет.. Я лучше потом свой вариант теста приведу..

[m_ax]

Написал свой тест, где сравнивал скорость чтения/записи варианта CBinMatrix, предложенного товарищем Igors с вариантом обычного массива (matrix<T, Rows, Columns>), оформленного в виде шаблона (см. исходники).

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

Измерения были проведены для реализации CBinMatrix и шаблонной обёртки над обычным массивом (matrix<T, R, C>).
Ниже его реализация:

Код

C++ (Qt)
template <class T, unsigned long Rows, unsigned long Columns>
class matrix
{
public:
    typedef unsigned long size_type;
    matrix() {
        m_mtx = new T*[Rows];
        for (size_type i = 0; i < Rows; ++i)
            m_mtx[i] = new T[Columns];
    }
    ~matrix() {
        for (size_type i = 0; i < Rows; ++i)
            delete []m_mtx[i];
        delete []m_mtx;
    }
    const T& operator()(size_type row, size_type column) const { return m_mtx[row][column]; }
    T& operator()(size_type row, size_type column) { return m_mtx[row][column]; }
    static size_type rows() { return Rows; }
    static size_type columns() { return Columns; }
private:
    T **m_mtx;
};
 

 
Результаты
Число строк и столбцов в тесте было такое:

Код

C++ (Qt)
const unsigned long NUM_ROW = 1000000;
const unsigned long NUM_COL = 20;
 

В первом тесте сравнивались времена для CBinMatrix и matrix<bool, R, C>
Результаты трёх запусков (release) таковы:

Код

Bash
matrix<bool>:	        time (sec) = 0.09
CBinMatrix:		time (sec) = 0.22
 

CBinMatrix оказался в 2.44 раза медленнее.

Второй тест: CBinMatrix и matric<char>
При трёх запусках

Код

Bash
matrix<char>:	        time (sec) = 0.1
CBinMatrix:		time (sec) = 0.22
 
matrix<char>:	        time (sec) = 0.11
CBinMatrix:		time (sec) = 0.22
 
matrix<char>:	        time (sec) = 0.11
CBinMatrix:		time (sec) = 0.24
 

CBinMatrix оказался в 2.125 раза медленнее.

Третий тест: CBinMatrix и matric<int>
При трёх запусках

Код

Bash
matrix<int>:	        time (sec) = 0.23
CBinMatrix:		time (sec) = 0.22
 
matrix<int>:	        time (sec) = 0.25
CBinMatrix:		time (sec) = 0.23
 
matrix<int>:	        time (sec) = 0.24
CBinMatrix:		time (sec) = 0.23
 

Разница нивелируется.

С std::vector<bool> пока не сравнивал.. Может завтра.

Исходники теста прилагаются
 

[V1KT0P]

Разница нивелируется.

С std::vector<bool> пока не сравнивал.. Может завтра.

Исходники теста прилагаются
 

Тут еще надо сравнивать компиляторы с разными ключами. MSVS почему-то медленнее чем GCC на дефолтных настройках. И разница между двумя тестами Igors-а не такие большие, скорее дело в том что ICC лучше оптимизирует. Я конечно пробовал собрать с помощью GCC 4.7 но программа падает О_О. При чем узнать причину нельзя, ибо в дебаг версии отрабатывает на ура.
При чем там тест с подсчитыванием пикселей на int должен просто рвать любой другой, ибо CBinMatrix пока вытащит бит, пока проверит значение бита, пока перейдет по условному переходу, пока увеличит значение. В то время как для int надо всего-лишь достать значение и присвоить его. Как видно разница должна быть большая, но у меня ее почти нету.
Igors замени:

Код

C++ (Qt)
if (arr[x][y]) ++sum;

на:

Код

C++ (Qt)
sum += arr[x][y];

И скажи результаты, очень интересна разница с использованием ICC.

[m_ax]

Я тестил на gcc 4.4 (release) -O2
А этот мой тест на gcc 4.7 с ключом -O3  интересно что даёт?
И на MSVC?
 

[V1KT0P]

Я тестил на gcc 4.4 (release) -O2
А этот мой тест на gcc 4.7 с ключом -O3  интересно что даёт?
И на MSVC?
 

Ключ O3 не изменяет результаты:

GCC 4.63
matrix<int>:           time (sec) = 0.047
CBinMatrix:      time (sec) = 0.156

matrix<int>:           time (sec) = 0.032
CBinMatrix:      time (sec) = 0.171

GCC 4.7
matrix<int>:           time (sec) = 0.031
CBinMatrix:      time (sec) = 0.156

matrix<int>:           time (sec) = 0.047
CBinMatrix:      time (sec) = 0.141

MSVS2008
matrix<int>:           time (sec) = 0.063
CBinMatrix:      time (sec) = 0.110

matrix<int>:           time (sec) = 0.062
CBinMatrix:      time (sec) = 0.125

Щас попробу установить ICC 11 и на нем прогнать тесты.

[m_ax]

Да, кстатии, заметил сейчас один косяк в CBinMatrix из-за которого программа падает.

Если в тесте поменять значения NUM_ROW и NUM_COL на следующие:

Код

C++ (Qt)
const unsigned long NUM_ROW = 20;
const unsigned long NUM_COL = 1000000;
 

то усё.. приехали.. out of range

[V1KT0P]

Щас попробу установить ICC 11 и на нем прогнать тесты.

ICC 11 у меня не дал никакого прироста, наверно из-за того что проц не интел =).

ICC11
matrix<bool>:   time (sec) = 0.047
CBinMatrix:             time (sec) = 0.172

matrix<bool>:   time (sec) = 0.062
CBinMatrix:             time (sec) = 0.157

[m_ax]

Ясненько)

Короче, пока igors не залатает свой CBinMatrix, сравнивать что-то особого смысла нет(( 

[Igors]

Избегаю цитат чтобы было короче. Обращение (x, y) соответствует "столбец, строка" (как оно на экране), конечно упадет если звать "строка, столбец". Ладно, изменил на (row, col) чтобы было однообразно.

Главное - тесты показывают эффективность процессорного кэша (а совсем не эффективность кода). В аттаче немного измененный пример m_ax, где адреса выбираются подряд (rain = 0), или вперемешку (rain = 1). Теперь уже битовые данные заметно быстрее

---- ICC rain = 0 -------
sum = 10001120
matrix<bool>:   time (sec) = 0.54
sum = 10001120
CBinMatrix:   time (sec) = 0.39

---- ICC rain = 1 -------
sum = 9987800
matrix<bool>:   time (sec) = 4.86
sum = 9987800
CBinMatrix:   time (sec) = 1.53


---- GCC (4.2) rain = 0 -------
sum = 10001120
matrix<bool>:   time (sec) = 0.51
sum = 10001120
CBinMatrix:   time (sec) = 0.53

---- GCC (4.2) rain = 1 -------
sum = 9987800
matrix<bool>:   time (sec) = 5.65
sum = 9987800
CBinMatrix:   time (sec) = 2.07

Мораль: никогда не рыпайся с оптимизацией "просто так" до тех пор пока она не будет действительно узким местом 

[V1KT0P]

Мораль: никогда не рыпайся с оптимизацией "просто так" до тех пор пока она не будет действительно узким местом 

А чего не добавил для наглядности unsigned char?

[Igors]

А чего не добавил для наглядности unsigned char?

И так достаточно . Меняя char/int/bool можно чего-то получить в разы - но только на "очень холостом" ходу, тогда оно как-то удачно ляжет в кэш. Но как только будет добавлен код обработки (пусть простейший) - эффект сразу "растворится".

Если расход памяти в полтора-два раза больше - уже надо репу чесать, может ну его нафиг. А тут так резво сразу в 8 раз. Или вообще в 32, мол int быстрее 

[m_ax]

И так достаточно . Меняя char/int/bool можно чего-то получить в разы - но только на "очень холостом" ходу, тогда оно как-то удачно ляжет в кэш. Но как только будет добавлен код обработки (пусть простейший) - эффект сразу "растворится".

Не спешите... Здесь дело не в кэше, а кое в чём другом)

Немного магии меташаблонного программирования и matrix становится быстрее почти в полтора раза (при rain = 1)
RAIN = 1

Код

Bash
matrix<bool>:	        time (sec) = 3.5
CBinMatrix:		time (sec) = 4.89
 
matrix<bool>:	        time (sec) = 3.53
CBinMatrix:		time (sec) = 4.97
 
matrix<bool>:	        time (sec) = 3.55
CBinMatrix:		time (sec) = 4.91
 

RAIN = 0

Код

Bash
matrix<bool>:	        time (sec) = 1.21
CBinMatrix:		time (sec) = 1.86
 
matrix<bool>:	        time (sec) = 1.2
CBinMatrix:		time (sec) = 1.85
 
matrix<bool>:	        time (sec) = 1.21
CBinMatrix:		time (sec) = 1.87
 

И это при том, что физически matrix содержит в 8 раз больше элементов. Так что скорость доступа и записи в CBinMatrix значительно проигрывает.

[m_ax]

Забыл сказать..
 
В принципе, CBinMatrix, используя подход применённый выше, тоже можно не хило ускорить)
А если потом ещё использовать его в качестве специализации matrix для типа bool, то TC получит удобную шаблонную матрицу, которая в случае bool будет просто летать).

Интересно, а что в итоге сам ТС наваял?

[Igors]

Немного магии меташаблонного программирования и matrix становится быстрее почти в полтора раза

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

Однако достигнутые "полтора" совсем не означают "общее ускорение" - это всего лишь "ускорение доступа" или "холостой ход". Подключите нагрузку (т.е. не просто читать/писать а делать что-то полезное) - и очень быстро от того полтора останется кот наплакал.

Также прикинем - а какие разумные действия будут производиться с данными которые (по своей природе) битовые? Да наверное и операции битовые, напр OR. AND. XOR двух матриц. Очевидно здесь битовые данные будут "просто в неск раз быстрее".

И это при том, что физически matrix содержит в 8 раз больше элементов.

Вот-вот. Если мне нужно будет 100 Mb, то Вам - 800 Mb. Такое разбазаривание ресурсов может квалифицироваться как (а) полное лоховство или (б) умышленное вредительство