Упаковка чисел с нестандартной разрядностью бит в массив
Задача: экономно упаковать числа в массив, весь диапазон значений которых умещается в число бит, отличное от стандартных 8, 16, 32, 64.
Вопрос: Как подобное правильно реализовать и есть ли уже готовые реализации на C или C++? Ну т.е. понятно что если допустим у нас число из 7 бит и в качестве типа, через который вытаскиваем битики из массива используем 8-битный тип и какое-то число попадает прямо на границу 8-бит, например
Первое что приходит в голову - составить структуру, кратную 8 по длине.Второе - читать побайтово и сдвигать каждый раз, чтобы получать отдельное число.
Задача: экономно упаковать числа в массив
hint: если неважна последовательность битов, то по кватрам 8 семибитных чисел очень быстро помещаются в 7 восьмибитных. 8 9-битных в 9 восьмибитных. ну и так далее
экономно упаковать числа в массив
Не там ты экономишь. Сэкономив доли копейки на памяти, ты сильно усложняешь код. То, что ты ищешь называется LEB128.
А оно точно тебе надо? Выигрыш по памяти может оказаться ничтожным и ненужным, зато по скорости будет значительное проседание.
как такой массив инициализировать на этапе компиляции
Через constexpr, например.
Какую структуру? Может union? Взять например такую фигню:
Только не забывай, что ты сэкономишь всего 1/8 памяти, а код усложнится сильно. Тебе оно надо? Ладно бы там были булевы значения или нибблы.
Дык я не говорю конкретно о записи 7-битных, меня интересует общий случай, ну чтобы и 4-битные, и 3-битные, и 5-битные так упаковывать. 7-битные просто для примера
Упаковывать их все в 8-и битные.
А если у меня числа 11-битные например? А если мне в микроконтроллер с ограниченной ПЗУ нужно это втулить? Не, так не годится
Еще раз — на каждый сэкономленный бит данных ты добавляешь 100 байт лишнего кода на encoder/decoder.
У тебя терабайты данных, которые ты пихаешь в пзу?
Классический trade-off: memory vs. cpu. Серебрянной пули нет.
PS: грануляция пзу не редко dword (16bit) — от этого тогда и надо исходить. И что бы прочесть тоже 11-и битное упакованное число, тебе надо обратится в худшем случае уже к двум ячейкам. А это медленно. Разумнее (проще и быстрее) будет паковать 11 бит в 16 бит и не экономить на спичках.
Еще раз — на каждый сэкономленный бит данных ты добавляешь 100 байт лишнего кода на encoder/decoder.
В контроллерах/процессорах с гарвардской архитектуой данные и код хранятся в разных местах вообще-то, так что если много свободного места в секции кода и мало в секции данных, то подобный «размен» может оказаться вполне полезен. Да и не думаю я, что там наберется 100 байт на encoder/decoder. На ассемблере можно очень компактно это сделать
а потом у них текстовые редакторы тормозят на 16G памяти и 4ядрах 4GHz
Завести специальный тип для таких N-битных представлений вроде тех, что используются в Boost.Endian, сделать специализацию std::vector наподобии std::vector<bool>. Простой она, конечно, не будет, но пользоваться будет можно удобно.
Я другое имел в виду. Ну да, обвернуть в union.
Кстати, зря ты считаешь что такой подход с упаковкой чисел не нужен. Я нашел ему очень хорошее применение. Речь идет о сжатии изображений и видео. Тут только надо как следует подумать над алгоритмом. Взять например какое-нибудь примитивное greyscale изображение 8 бит на один пиксель. Плавное изменение так легко закодировать в меньше чем 8 бит, если считать разность значений пикселей с соседними по определенным правилам. Например простенький градиентик:
В том примере используется такое правило
хотя можно сделать нечто вроде
я велосипедирую битовые потоки в таких случаях обычно
есть ли уже готовые реализации на C или C++?
посмотри в zlib, там что-то такое должно быть, наверное
Экономней всего будет сжать поток бит имея обычные границы для чисел.
Serializing the data for a compressed file format . The chain code can be represented as a sequence of directions for each step. There are 8 directions, so this requires 3 bits of information. Pack 2 steps into each byte. You can do better, putting 8 steps into 3 bytes, but gzip, which works on bytes, will be less successful at compressing such data, and we use gzip on the sequential step data.
Да, по стандарту в vector<bool> оно значение в битах хранит. Зачем кстати так сделали? Из-за этого с этим vector<bool> нельзя работать как с нормальным vector. sizeof(bool) равен 1, и следуя логике этот vector<bool> должен по одному байту на элемент выделять, но разработчики стандарта плюсов похоже с логикой не очень дружат. Вот даже ссылка нагуглилась http://alenacpp.blogspot.com/2005/06/vector.html
Ладно, фиг с ней с логикой. В любом случае надо поверх этих битиков городить что-то, что могло бы из этих битиков читать в нормальный тип, и писать в них из нормального типа. Как мне кажется, тут с плюсовым вектором лучше вообще не связываться, функции чтения-записи в этот массив-с-нестандартной битности просто сделать на C через сдвиги и битовые маски, сделав это поверх нормального массива из uint8_t uint16_t uint32_t или uint64_t. Надо только понять, какой тип для массива лучше всего подходит тут
поверх нормального массива из uint8_t uint16_t uint32_t или uint64_t
а чем это будет лучше vector<bool>, в котором уже сделаны более-менее удобные методы обращения к n-му биту?
Я бы массив из bool сделал для хранения. Сдвигать, складывать для получения. Ну если хранить только однородные: семибитные, шестибитные и т.д.
Можешь и в 64-битных числах хранить, потом их кастовать в тот же массив.
Тем, что эффективнее брать некий непрерывный кусок битов из одного или двух соседних(если число попало на границу) элементов массива, чем дергать по битику. Например если надо
Если это делать масками и сдвигами через чтение соседних , у компилятора больше шансов заоптимизировать это, чем если получать по одному битику и из них уже собирать
Массив из bool (в отличии от плюсового вектора из bool) будет по байту на элемент тратить, а это не то что я хочу. А про вектор из bool и неэффективности считывания числа побитово я уже свои возражения высказал
ну так зафигачь таким образом. лучший вариант, очевидно, — uint64_t, и доставать числа сдвигом.
а готовых решений я не помню для такого. на всякий случай посмотрел в бусте, там не нашёл. возможно есть на какой-нибудь помойке либа от васяна.
Разве? С последними стандартами он также будет в 1 бит. sizeof, по крайней мере, всё верно показывает.
Немного не в тему, но я бы лучше продумал интерфейс работы с этим массивом: «положить число», «достать», «вырезать кусок» и выполнил бы любую реализацию, а оптимизациями по памяти занимался бы в случае крайней необходимости. К примеру, если понадобится удалить число из такого упакованного массива, это ж сколько сдвигов надо будет делать.
тут вроде говорилось не про динамический массив.
А, ну тогда всё-равно сначала интерфейс с DEFINE-ами или шаблонами(C++), а потом 4 алгоритма - для 1,2,3,4-битных чисел и один алгоритм для 1,2,3,4,8-байтных чисел. Выбор алгоритма - DEFINE-ами или if-ами (для известного на этапе сборки sizeof(MY_TYPE) компилятор должен оптимизировать переходы).
Выигрыш в памяти менее, чем в 2 раза для не кратных 8-ми >5битных чисел кажется сомнительным.
Разве? С последними стандартами он также будет в 1 бит.
Эээ. Не понял. Массив из bool (если речь идет об обычном сишном массиве, без этой плюсовой магии) не может по одному биту на элемент держать т.к. к такому элементу никак нельзя получить нормальный указатель
Ну, если совсем делать нечего, то вот:
Непортабельно, зависит от порядка байт и все такое. Если сделать макросом и передавать в качестве b константу, то компилятор даже что-то тут соптимизирует.
Ты хоть как-то бы отреагировал на код =(
Ну раз анонимус хочет, чтобы я на этот код как-то отреагировал.
Не совсем понятно, зачем тут нужны сдвиги на 3 :
И не совсем понятно, почему я не вижу операции деления / и нахождения остатка от деления % . Например если взять массив из 8-битных char и упаковывать в него 3-битные числа, то чтобы получить десятое 3-битное число, надо было бы сделать следующее: умножить 3 на 10 (получим 30), разделить 30 на 8 нацело (получим 3) и найти остаток от деления 30 на 8 (получим 6). Это значит что десятое по счету 3-битное число в 3 байте, со сдвигом 6. Если ничего не напутал.
Вот эта вот часть ((*(int64_t*)(a+o))&mask)>>d и (*(int64_t*)(a+o))&=
mask; наводит меня на мысль, что тут чтение-запись uint64_t может производиться не по выравненным под 8 байт адресам. Для некоторых архитектур (в частности ARM) необходимо, чтобы обращения к памяти имели естественное выравнивание, т.е. адрес памяти должен быть кратен размеру данных (2 для short, 4 для int, 8 для uint64_t и double).
Для некоторых архитектур (в частности ARM) необходимо, чтобы обращения к памяти имели естественное выравнивание, т.е. адрес памяти должен быть кратен размеру данных (2 для short, 4 для int, 8 для uint64_t и double).
Для актуальных процессоров ARM вроде уже не важно, не?
Не проверял. Но точно знаю что существуют процессоры, где это важно. В любом случае подобный каст является UB http://spin.atomicobject.com/2014/05/19/c-undefined-behaviors/ см второй пункт
И не совсем понятно, почему я не вижу операции деления / и нахождения остатка от деления %.
Сдвиг на 3 и есть деление на 8.
Учитывая что там используются uint64_t я ожидал увидеть деление на 64 а не на 8. Да и современные компиляторы умеют оптимизировать подобные деления и нахождения остатоков, так что нет смысла запутывать код этими сдвигами вместо деления и нахождения остатка
Учитывая что там используются uint64_t я ожидал увидеть деление на 64 а не на 8.
Как ты справедливо заметил, там есть плохой каст. Можно было бы и догадаться, почему я делю на 8 =) Я ищу кусок из 64 бит, который содержит интересующий нас элемент массива.
Да и современные компиляторы умеют оптимизировать подобные деления и нахождения остатоков, так что нет смысла запутывать код этими сдвигами вместо деления и нахождения остатка
Ну, не очень-то и запутывать. Это ты видишь сдвиг, а я вижу деление на 8 =)
А про оптимизацию. Я часто видел, что (a<<1)+a работает быстрее, чем 3*a.
Кстати, если разрядность бит, которые нужно упаковать, небольшая, то предлагаю паковать сколько влезет в 64 бит.
Например, если нужно упаковать 90 чисел по 7 бит, то запаковать их по 9 штук в 10 uint64_t.
А про оптимизацию. Я часто видел, что (a<<1)+a работает быстрее, чем 3*a.
Не смеши, ты ни черта не понимаешь в оптимизации. Хорошо хоть, твой компилятор исправляет подобные потуги. Начать хотя бы с того, что самое быстрое целочисленное умножение на 3, 5 и 9 под x86(_64) будет не сдвигом со сложением, а единственной lea с косвенной адресацией.
Не смеши, ты ни черта не понимаешь в оптимизации.
Хорошо хоть, твой компилятор исправляет подобные потуги.
Я лишь говорю о том, что видел. В том конкретном случае (a<<1)+a работало быстрее.
В том конкретном случае (a<<1)+a работало быстрее.
Ты код c -O0 что ли собирал? И как мерил, главное?
Пробовал с -O2 и -O3.
Там был достаточно большой код, который обрабатывал изображение пару секунд.
Любой человеческий компилятор уже с -O1 знает лучше школо-оптимизаторов.
Не спорю. Могу попробовать поискать тот код на работе.
https://github.com/openssl/openssl/blob/6218a1f57e7e25a6b9a798f00cf5f0e56a02f. разработчики openssl тоже нифига в оптимизации не понимают, раз зачем-то втулили ассемблерную вставку для циклического сдвига. Компилятор такое отлично оптимизирует, к тому же в GCC вродекак builtin есть для этого
Молодец. Отдавай свой код компилятору на оптимизацию, иначе дико тупить будет.
Компилятор такое отлично оптимизирует
к тому же в GCC вродекак builtin есть для этого