Russian Qt Forum

Имею дело с матрицами размером 20 x 1000000, по сути в этой матрице храню -1 или 1.(бинарные изображения).
Хотелось бы спросить, какую структуру выбрать для представления этой матрицы, чтобы работало быстрее.

Пока остановился на quint8[][]

Смотря как ты их будешь обрабатывать. Думаю лучше всего quint32 для 32 битных систем и quint64 для 64 битных.

почему бы не использовать тип bool для уменьшения потребления памяти?

Если ему надо делать тяжелые операции, то вытягивание одного бита может дорого стоить.

Это скользкое дело - bool может быть и 4 байта (замешан компилятор, за это получал когда переходили на Xcode)

Если хранятся бинарные данные - то и хранить их надо бинарно (в виде битов). А с матрицей надо подровняться на строку. Итого

C++ (Qt)
struct CBinMatrix {
 CBinMatrix (int row, int col )  // row = 100000, col = 20
 {
   mColBytes = (col + 7) / 8;
   mRow = row;
   mData = new unsigned char[mColBytes * mRow);
 }
 
 ~CBinMatrix( void ) 
  {
    delete [] mData;
  }
 
 bool Get( int row, int col ) const 
 {
   unsigned char src = *(mData + row * mColBytes + col / 8); 
   return (src & (1 << (col % 8))) != 0;
 }
 
 bool Set( int row, int col. bool val ) 
 {
// напишите по образцу Get
 }
 
// data 
 size_t mColBytes. mRow;
 unsigned char * mData;
};
 

Ой  :)

Edit: пропустил сдвиг, подправил

Да, это конечно же, будет быстрый доступ к элементу)

Опять смайлик забыл поставить..  :)

Хз что Вы хотели этим сказать - то ли действительно быстрый, то ли изображаете "сарказм знатока"  :)  На всякий случай поясню. Обращение к двумерному массиву примерно равно такому коду

C++ (Qt)
*(data + row * mColBytes + col);   // data[row][col]
 

Все равно умножение, сложение потом инкремент указателя. Сравнивая этот вариант с предыдущим - да, у того на неск действий больше, но каждое из них - практически одна машинная команда. Вес операций доступа не так уж велик, поэтому брать в 8(!) раз больше памяти чтобы ускориться на пару процентов - никак не правильно. Не то это место где выжимать скорость

Igors, спасибо. Сделаю замеры по времени работы вышей структуры и просто массива. Выложу результаты

Я вот тут сделал замеры(просто перебор всех значений):

Массив CBinMatrix bool to bool uint8 to bool quint32 to bool uint8 to uint8 uint32 to uint32

Затраченное время 0.055737 0.0408991 0.0408365 0.0408429 0.00579459 0.00578789

Отношение к самому быстрому 9.5 7 7 7 1 1

Как я и говорил приведение к биту довольно таки тяжелая операция, в данном случае замедлила все в 7 раз. Самодельная структура так вообще почти в 10 раз медленее тупого массива.
Странно что разницы между uint8 и uint32 нету.

Интересно, только выложите проект. Меня удивляет откуда "bool to bool" 7  ???

Ну там массив bool и результирующая переменная bool.
Можно попробовать еще какие-то варианты =).

Тест какой то неадекватный..

Согласен лишь с тем, что вариант Igors будет в любом случае самым медленным.

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

Во-первых нафига для этого прикручивать Qt гуй? К тому же всё равно прога работает только под виндос.. Обидно..
Во-вторых:
сравним вариант для binMatrix

C++ (Qt)
Timer timer;
    CBinMatrix binMatrix(ROWS, COLS);
    bool d = false;
    timer.Init();
    for (size_t i=0; i<ROWS; i++) {
        for (size_t k=0; k<COLS; k++) {
            d += binMatrix.Get(i, k);
        }
    }
    double delta = timer.GetDelta();
    qDebug() << d << "BinM " << delta;
 

с вариантом:

C++ (Qt)
Timer timer;
    bool **matrix = new bool*[ROWS];
    for (size_t i=0; i<ROWS; i++)
        matrix[ROWS] = new bool[COLS];
    bool d = false;
    timer.Init();
    for (size_t i=0; i<ROWS; i++) {
        for (size_t k=0; k<COLS; k++) {
            d += matrix[ROWS][COLS];
        }
    }
    for (size_t i=0; i<ROWS; i++)
        delete matrix[i];
    delete *matrix;
    double delta = timer.GetDelta();
    qDebug() << d << "bool " << delta;
 

В последним варианте учитывается ещё время на уничтожение массива, в то время, как в первом варианте, при замере времени, массив ещё был жив и разрушится уже после.

В-третьих..

Короче, лучше переписать это нормально, без всяких привлечений "windows.h" и вообще гуя...  

Да, и ещё:
Лучше удалять массив так:

C++ (Qt)
 for (size_t i=0; i<ROWS; i++)
        delete []matrix[i];
 delete []matrix;
 

   

Не могу откомпилить на своей платформе (не имею windows.h). Ладно, вот мой тест, у меня (icc release) печатает

Я оцениваю это дело так: когда идет "только (голое) обращение" - массив быстрее в 4 раза (хотя и не в 10). Но как только вмешивается др код - зффект быстро исчезает. Напр sumNear складывает всех соседей пикселя - вроде тоже обращение, добавлены лишь проверки на границы. Тем не менее выигрыш уже только в 2 раза. А вызов скромного qrand вообще убивает в ноль.

Также возможно что при бОльших размерах данных (сотни мегабайт) битовые данные будут "просто быстрее" за счет того что используемый диапазон адресов меньше (дела кэша)

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

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

Написал свой тест, где сравнивал скорость чтения/записи варианта 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> пока не сравнивал.. Может завтра.

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

Тут еще надо сравнивать компиляторы с разными ключами. 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.

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

Ключ O3 не изменяет результаты:
Щас попробу установить ICC 11 и на нем прогнать тесты.

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

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

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

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

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

Ясненько)

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

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

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


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

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

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

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

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

Немного магии меташаблонного программирования и 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 значительно проигрывает.

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

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

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

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

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

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

Как раз таки и означает) На холостом ходу, т.е. если ТС будет использовать, при работе с матрицей, конструкции вида 

C++ (Qt)
for(long i = o; i < mtx.rows(); ++i) {
    for (long j = 0; j < mtx.columns(); ++j) {
        someFunction( mtx(i, j) );
    }
}
 

то новый вариант с matrix будет вообще в 3-4 раза быстрей.

Вы же сами изменили изначальный мой вариант теста, введя RAIN, чтоб избавится от "холостого" хода...
Избавились. И всё равно matrix оказывается быстрей.

Но это.. Ещё не всё)
Сейчас CBinMatrix - написан не самым оптимальным образом.. Можно ещё ускорить..

Но пусть этим занимается ТС)
 

Не увлекайтесь - и не запутывайте начинающих :) В приведенном фрагменте скорость упрется в  someFunction, и если эта ф-ция "выше травы" то эффект "быстрого доступа" упадет до нуля. А вот если нагрузка манипулирует с битами, то битовое представление ой намного быстрее  :)

Ну и давайте закругляться - все ясно, начинаем "ходить по кругу". Умолкаю

Замеры интереснее было бы делать на реально работающем алгоритме.

Ну это и так понятно. Тут уже не нужно вытаскивать отдельный бит.
С этим я и не спорю)

А использование векторных массивов не подходит?