Russian Qt Forum

Стоит задача обработки больших массивов данных, в которых каждый элемент может принимать одно из пяти значений. Длина массивов - до сотен миллионов элементов.
До этого я массивы задавал просто - с помощью char. Т.е. один байт на один элемент. При этом массивы могли занимать пару сотен мегабайт. Для ускорения работы хотелось бы загружать массив из файла в оперативку целиком. Но мне не нравится такая пустая трата ресурсов (да и не на любом компе такое получится загрузить, либо получится с тормозами) - ведь если элементов всего пять, то для их кодирования достаточно трех битов, а не байта.
Например:
A - 000
B - 001
C - 010
D - 011
E - 100
Так можно уменьшить размер занимаемой памяти почти в три раза.
Жалко, не существует в Qt готовых решений массивов, где можно задать количество бит на элемент :)
Так вот, хочу создать свой класс, который будет хранить данные внутри как QBitArray, но наружний интерфейс будет работать только тройками битов.
Так вот вопросов два - 1) может есть что-то подобное уже готовое, что я мог проглядеть (хотя и не обязательно Qtшное); 2) Если делать это с нуля с помощью битовых СИшных операций или с помощью QBitArray - разница в скоросте работы не будет существенной (в описании QBitArray мало что сказано о том, насколько он быстро работает)?
Да, и самый главный вопрос - а выгодно ли это делать с точки зрения скорости? Ведь если загружаю байты, то их будет больше, но читаются они быстрее. Если загружу битами (хотя это те же байты, конечно), то памяти займет меньше, но скорость? Как я понимаю, чтобы прочитывать все элементы, там в каждом байте сначала биты будут сдвигаться и сравниваться.

ну если ваши трёх-битные элементы реализовывать с помощью QBitArray, то на счёт скорости я незнаю как будет, а вот в памяти вы точно проиграете, ну это в том случае если каждый элемент будет реализован с помощью QBitArray.
Готовых решений нету, покрайней мере я про них незнаю...

ну я бы сделал так: с помощью QBitArray хранил массив элементов, ну например максимум на массив 192(64 * 3), это означает 64 элемента в массиве, каждый размером по 3 бита, ну или сами как хотите. Максимальный размер массива по количеству элементов должен быть кратным 3!!! Выбирать из массива элемент по индексу думаю не составит труда - обычная математика. Ну а в случае если индекс элемента принадлежит другому массиву - то это также простая математика... таким способом учтём проигрышь по памяти...


А вообще в С++ есть такое понятие как "Битовые поля"
int bits:4; //4 бита
int bits:3; //3 бита

Если речь про сотни мегабайт памяти, то вместо восьмеричной системы счисления есть смысл использовать пятеричную. Экономия при идеальном выборе слова для хранения данных - 37.5% ОЗУ.

Конечно нет, я собирался просто массив из QBitArray рассматривать не как массив отдельных битов, а как массив отдельных троек битов.

Про битовые поля почитал (http://www.informit.com/guides/content.aspx?g=cplusplus&seqNum=131) - вроде из них не получится массивы делать. Там же написано, что работать с битами все-таки медленнее, чем с байтами... Теперь думаю, какой выбор сделать в этой дилемме.

Что-то  я не совсем понял... Вроде бы система счисления в компах всегда олна - двоичная, речь идет о том, сколько разрядов юзать. И почему пять? Для кодирования пяти символов хватает и трех битов.

В вашей задаче нужна пятеричная система счисления, поскольку у вас 5 значений - 01234, а следовательно 567 никогда не используются. Видите, вы сами решили оперировать октетами, хотя процессор ничего об этом не знает, просто C предоставляет битовые операции для удобства, а для пятеричной математики в C ничего нет. Забудьте о том как думает процессор, думайте сами (-:

ересь какая-то. нет единицы меры - 3 бита. как минимум придется выделить 1 байт. а если выделять по одному байту динамически, то при выделении 1024 байт, реальной памяти будет съедено как минимум в 12 раз больше.
и что за компы такие, что на них нельзя загрузить гигабайт в оперативку? что, 92 год? ;)
а вообще, эта "задача" похожа на вымысел.

еще почитайте Memory mapping.

Ну почему, это наверно в случае если в 1 байте держать именно один элемент, но байт - 8 бит, туда максимум влезет 2 элемента, количество лишней памяти уже съедено, в 2 раза меньше...

конечно можно ещё и последнии биты задействовать, тогда получается так что один элемент будет лежать частями в разных байтах, такое тоже можно и не трудно написать, придётся писать ещё считывалку именно для такого случая... в этом случае вообще по памяти точно не проиграем и не будет тогда пустой не задействованной памяти

Не-а. В байт помещаются значения 0..255, значит в него можно записать 3(!), а не 2 значения, ибо как 5^3 == 125, что тоже влезает в байт (-: Я бы сделал на пятеричной системе счисления чтобы хотя бы замерить отношение размена ресурсов CPU на сэкономленую память.

Вот написал на колене рабочий пример. Конечно на идеальный код не претендует, но тем не менее.

C++ (Qt)
static const int MaxItems = 27;
 
inline int takeAt( quint64 blob, int i )
{
	Q_ASSERT( i >= 0 && i < MaxItems );
 
	for ( ; i != 0; --i )
		blob /= 5;
	return blob % 5;
}
 
inline void putAt( quint64 & blob, int i, int value )
{
	Q_ASSERT( i >= 0 && i < MaxItems );
	Q_ASSERT( value >= 0 && value < 5 );
 
	int values[ MaxItems ] = {0};
 
	int j;
	for ( j = 0; j < i; j++ )
	{
		values[ j ] = blob % 5;
		blob /= 5;
	}
 
	blob /= 5;
	blob *= 5;
	blob += value;
 
	for ( ; j != 0; j-- )
	{
		blob *= 5;
		blob += values[ j-1 ];
	}
}
 

В 64-битное число помещается 21 октет (21*3 == 63, что меньше 64) или 27 квинтетов. Экономия памяти - 22%

И даже если скорость чтения/записи упрётся в количество итераций умножения/деления - квинтеты можно хранить в 8 байтах, по 3 в каждом (3 операции умножения/деления вместо 14). Конечно тогда поместится только 24 значения, а не 27, но всё равно больше, чем 21 (-:

еще бы не плохо, подсчитать, во сколько раз упала производительность. ;)

у меня вот что получилось.

C++ (Qt)
#include <cctype>
#include <iostream>
 
int main() {
	const size_t sz = 1024*1024;
 
	for ( size_t i = 0; i < sz; ++i ) {
		new char;
	}
 
	std::cin.get();
 
	return 0;
}
 

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

C++ (Qt)
struct mem_block {
   struct mem_block* prev;
   struct mem_block* next;
   void* ptr;
   size_t size;
};
 

и того 16 байт.
страшно представить сколько памяти потребуется для 1024*1024 объектов QBitArray. :)
как мне кажется, оптимальный вариант, мемори-маппед файл и по байту для элемента.

Думаю функцию бизнес-логики легко можно зашаблонить и подставлять нужный инлайновый сеттер/геттер значения: чистый байт, два октета в байте, 21 октет в int64, 3 квинтета в байте, 27 квинтетов в int64. Запустить все вместе и сравнить (-;

Да, кстати, для каждого смещения квинтета можно делить/умножать сразу на константу, а не циклом, думаю прирост скорости будет существенный.

1) Да, битовый массив будет работать чуть медленнее байтового но падение скорости незначительно (особенно если не связываться с "использованием всех разрядов")

2) Да, это позволит сэкономить память значительно, но есть ли у Вас что экономить?  :) Паковать имеет смысл начиная примерно со 100 Mb

3) Есть ли это в Qt - не знаю. Но и своя реализация ничем не плоха, например простенько

Интересное решение! Вот только Вы чересчур увлеклись сокращением объема задействуемой оперативки, что с водой и ребенка выплеснули. Автор пишет:
Человек хочет ускорить работу своего алгоритма, и с этой целью рассматривает вариант помещения всего массива данных в память. Из предложенной вами реализации видно, что функция выборки элемента из массива будет задействовать в среднем 14(!) операций деления (исходя из предположения, что обращение к любому из 27 элементов равновероятно). Функция вставки и того сложнее - в среднем 28 операций деления, 14 - умножения, 14 - сложения. Умножение и деление - это довольно дорогие операции! Даже без тестирования понятно, что данная реализация будет работать в разы медленнее, чем работа с октетами. А значит весь выйгрыш от экономии памяти сожрется многократно.
А ничего, что в конечном итоге именно процессор будет это все делать? ;) Поэтому, если вы хотите что-то оптимизировать, то как раз об этом и стоит думать. Вовсе не случайно на практике используются системы счисления, основанием которых является степень двойки. Так уж устроены современные ЭВМ, что только такие системы счисления дают максимальную эффективность при вычислениях.
На мой взгляд, для данной задачи лучше всего подходит использование именно октетов. Это позволит существенно сократить объем используемой памяти, без заметного падения производительности. Вот как-то так (взял за основу функции Dendy, не сочтите за плагиат   :)):

C++ (Qt)
typedef unsigned char uchar;
typedef unsigned qint64 uint64;
static const int MaxItems = 21;
static const uchar mask = 7;
 
inline uchar takeAt( uint64 blob, int i )
{
	Q_ASSERT( i >= 0 && i < MaxItems );
        return (uchar)(blob >> i*3)&mask;
}
 
inline void putAt( uint64 & blob, int i, uchar value )
{
	Q_ASSERT( i >= 0 && i < MaxItems );
	Q_ASSERT( value >= 0 && value < 5 );
        blob |= ((uint64)value << i*3);
}
 

Код не тестировал (возможны недочеты и опечатки), но общая идея должна быть ясна. Приведеные побитовые операции будут выполняться очень быстро.

И еще, по поводу inline-функций: функции, приведенные Dendy, слишком сложны, чтобы компилятор смог бы сделать их подставляемыми, а значит ко всему прочему добавятся накладные расходы на их вызов  ;)

P.S. по сравнению с вариантом от Igors, в котором в 64 бита можно поместить 16 элементов, здесь можно сохранить 21 элемент. При этом накладные расходы будут не больше.

Октетами... Это же банально и скучно. Снова эти степени двойки, да их уже все наизусть знают. А вот вы посчитайте степени пятёрки хотя бы до 7-го порядка, слабо? ((-:

Вообще вы не подумайте, я с вами полностью согласен. Просто хотел предложить нестандартное решение, напомнить, что кроме двоичного счисления существуют и другие (надо же!). А то того и гляди хохма про 1024 метра в километре станет правдой.

Кстати, я там дальше утонил, что можно для умножения/деления использовать константы. И если логика обработки значения гораздо тяжелее логики выборки, а память важна - таки можно разменять ресурсы RAM на ресурсы CPU (-;

:D Что поделать, довольно часто работа программиста банальная и скучна, даже рутинна. Но судя по вопросу автора работа с битами для него нова, а значит скучно быть не должно ;). Да и стоит ли заморачивать голову человеку нестандартными подходами, если он еще с классикой разобраться не успел? Так кроме каши в голове ничего не получиться.

Не слабо. Степени пятерки в уме как раз очень хорошо считаются :).

До кучи: 5 бит на значение встречается не так уж редко (напр. некоторые форматы QuickTime). Реализация скромная, на базе unsigned short (используются 15 бит из 16)

Я правильно понимаю, что если мне не нужно изменять содержимое файла, то memory mapping не даст преимущества перед простой загрузкой данных целиком из файла, например, в QList?

Ну это уж Вы сами смотрите по обстановке. "Паковка" дает хорошую экономию по памяти и незначительное увеличение вычислений. Другое дело с ней заботы - стандартный контейнер не попользовать, адрес от этого "3-битового чудика" не получить, надо работать по индексу и.т.п. Все это не смертельно и пережить можно, но, как правило, имеет смысл только если "есть что паковать".

Нет, в последнем вопросе я имел ввиду работу с байтами, без паковки. Тут просто предложили вариант Memory Mapped File, я с ним не знаком, но по названию догадываюсь, что это отображение файла в память, при этом наверняка изменения данных в памяти потом запишутся в файл. Я и поинтересовался - если мне не нужно сохранять эти изменения в файл, то какое преимущество дает Memory Mapping перед простой загрузкой данных в любой контейнер?

А насчет паковки я решил сделать оба варианта :) Будет проверяться кол-во свободной памяти. Если хватает - загрузим байтами, если маловато - то битами. Компромис разрешен :)

Memory Mapped File - это своя песня и к битовой паковке прямого отношения не имеет. А вот когда надо наладить обмен данными между 2-мя процессами - без Memory Mapped не обойтись.

Программист должен быть ленивым и никогда не делать 2 варианта  :)