Что такое битмап

Что такое Битмапы (Bitmaps)?

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

Битмап, это графический объект, который содержит заголовок, необходимую информацию о картинке (такую как высота, ширина, цвета и т.д.) и, собственно, само изображение (большой массив, содержащий цвет каждой точки). В Delphi для этой цели уже предусмотрен класс TBitmap.

Битмапы можно рисовать не только на форме, но и по всему экрану. Может это и может показаться немного странным, но иногда это бывает полезно, особенно при создании скринсейвера. Однако, сначала нам необходимо разобраться с тем, как работать с битмапами. Вот небольшой пример:

procedure Form1.DrawBitmap(const Filename: String; const x,y: Integer);

// Сперва убедимся, что файл существует!

if not FileExists(Filename) then

ShowMessage(‘The bitmap ‘ + Filename + ‘ was not found!’);

Canvas.Draw(x, y, Bmp);

Эта функция пытается загрузить и показать картинку, (с именем Filename, например ‘myBitmap.bmp’) начиная с точки (x,y).

Сразу скажу, что эта функция довольно неэффективна. Она создаёт и уничтожает битмап каждый раз когда вызывается, а так же каждый раз проверяет существование файла. Лучше объявлять объект TBitmap как часть формы, создавать и загружать картинку в FormCreate, а освобождать её в FormDestroy.

Функции рисования в gdi

TCanvas имеет несколько полезных функций, которые работают с типом TGraphic. Тип TGraphic является базовым классом для графических объектов в Delphi, таких как: битмапы (TBitmap), иконки (TIcon), метафайлы (TMetafile) и JPEG-и (TJPEGImage). Все они используют одни и те же функции, которые приведены в таблице:

Все эти функции являются методами TCanvas.

Рисует TGraphic на канвасе так как он есть, не растягивая.

Рисует TGraphic на канвасе, подгоняя (растягивая) его под заданную область.

Canvas.StretchDraw( Bounds(0,0,32,32), MyGraphic);

Копирует часть TCanvas-а в другой, при необходимости растягивая его.

Canvas.CopyRect( Bounds(0,0,32,32), MyBmp.Canvas, Bounds(0, 0, 640, 480));

TCanvas.Draw является обёрткой для API функции BitBlt:

hdcDest: HDC; // дескриптор конечного контекста устройства

nXDest, // коорд. x верхнего левого угла конечного прямоугольника

nYDest, // коорд. y верхнего левого угла конечного прямоугольника

nWidth, // ширина конечного прямоугольника

nHeight: Integer; // высота конечного прямоугольника

hdcSrc: HDC; // дескриптор исходного контекста устройства

nXSrc, // коорд. x верхнего левого угла исходного прямоугольника

nYSrc: Integer; // коорд. y верхнего левого угла исходного прямоугольника

dwRop: DWORD // код растровой операции

Описанный выше способ позволяет рисовать битмап в run-time. Конечно, проще поместить на форму TImage и установить в ней картинку. Изображение будет постоянно оставаться на том месте, где Вы его поместили, но это скучно ;-). Куда интереснее сделать при помощи битмапов анимацию.

С другой стороны, поняв принципы работы с битмапами, Вам будет легче перейти к другим графическим библиотекам (например DirectX).

Bitmap-индексы в Go: поиск на дикой скорости

Я выступил с этим докладом на английском языке на конференции GopherCon Russia 2019 в Москве и на русском — на митапе в Нижнем Новгороде. Речь в нём идёт о bitmap-индексе — менее распространённом, чем B-tree, но не менее интересном. Делюсь записью выступления на конференции на английском и текстовой расшифровкой на русском.

Мы рассмотрим, как устроен bitmap-индекс, когда он лучше, когда — хуже других индексов и в каких случаях он значительно быстрее них; увидим, в каких популярных СУБД уже есть bitmap-индексы; попробуем написать свой на Go. А «на десерт» мы воспользуемся готовыми библиотеками, чтобы создать свою супербыструю специализированную базу данных.

Очень надеюсь, что мои труды окажутся для вас полезными и интересными. Поехали!

Введение

Привет всем! Сейчас шесть вечера, мы все суперуставшие. Замечательное время, чтобы поговорить о скучной теории индексов баз данных, да? Не волнуйтесь, у меня будет пара строчек исходного кода тут и там. 🙂

Если без шуток, то доклад переполнен информацией, а у нас не так много времени. Поэтому давайте начинать.

Сегодня я буду говорить о следующем:

• что такое индексы;
• что такое bitmap-индекс;
• где он используется и где он НЕ используется и почему;
• простая имплементация на Go и немного борьбы с компилятором;
• чуть менее простая, но гораздо более производительная имплементацию на Go-ассемблере;
• «проблемы» bitmap-индексов;
• существующие реализации.

Так что такое индексы?

Индекс — это отдельная структура данных, которую мы держим и обновляем в дополнение к основным данным. Она используется для ускорения поиска. Без индексов поиск требовал бы полного прохода по данным (процесс, называемый full scan), и этот процесс имеет линейную алгоритмическую сложность. Но базы данных обычно содержат огромное количество данных и линейная сложность — это слишком медленно. В идеале нам бы получить логарифмическую или константную.

Это огромная сложная тема, переполненная тонкостями и компромиссами, но, посмотрев на десятки лет разработки и исследования различных баз данных, я готов утверждать, что существует всего несколько широко используемых подходов к созданию индексов БД.

Первый подход заключается в иерархичном уменьшении области поиска, разделении области поиска на более мелкие части.

Обычно мы делаем это, используя разного рода деревья. Примером может служить большая коробка с материалами в вашем шкафу, в которой находятся более мелкие коробки с материалами, разделёнными по различным тематикам. Если вам нужны материалы, то вы наверняка будете искать их в коробке с надписью «Материалы», а не в той, на которой написано «Печеньки», так ведь?

Второй подход заключается в том, чтобы сразу выделить нужный элемент или группу элементов. Мы делаем это в hash maps или в обратных индексах. Использование hash maps очень похоже на предыдущий пример, только вместо коробки с коробками у вас в шкафу куча маленьких коробок с финальными предметами.

Третий подход — избавиться от необходимости поиска. Это мы делаем с помощью Bloom-фильтров или cuckoo-фильтров. Первые дают ответ мгновенно, избавляя вас от необходимости осуществлять поиск.

Последний подход заключается в полноценном использовании всех мощностей, которые даёт нам современное железо. Именно это мы делаем в bitmap-индексах. Да, при их использовании нам иногда требуется пройти по всему индексу, но делаем мы это суперэффективно.

Как я уже сказал, тема индексов БД обширна и переполнена компромиссами. Это значит, что иногда мы можем использовать несколько подходов одновременно: если нам нужно ещё сильнее ускорить поиск или если необходимо покрыть все возможные типы поиска.

Сегодня я расскажу о наименее известном подходе из названных — о bitmap-индексах.

Кто я такой, чтобы говорить на эту тему?

Я работаю тимлидом в Badoo (возможно, вы лучше знаете другой наш продукт — Bumble). У нас уже более 400 млн пользователей по всему миру и много фич, которые занимаются тем, что подбирают для них лучшую пару. Делаем мы это с помощью кастомных сервисов, использующих в том числе и bitmap-индексы.

Так что же такое bitmap-индекс?

Bitmap-индексы, как подсказывает нам название, используют битмапы или битсеты для того, чтобы заимплементить поисковый индекс. С высоты птичьего полета этот индекс состоит из одного или нескольких таких битмапов, представляющих какие-либо сущности (типа людей) и их свойства или параметры (возраст, цвет глаз и т. д.), и из алгоритма, использующего битовые операции (AND, OR, NOT) для ответа на поисковый запрос.

Нам говорят что bitmap-индексы лучше всего подходят и очень производительны для случаев, когда есть поиск, объединяющий запросы по многим столбцам, имеющим малую кардинальность (представьте «цвет глаз» или «семейное положение» против чего-то типа «расстояние от центра города»). Но позже я покажу, что они прекрасно работают и в случае со столбцами с высокой кардинальностью.

Рассмотрим простейший пример bitmap-индекса.

Представьте, что у нас есть список московских ресторанов с бинарными свойствами вроде этих:

• рядом с метро (near metro);
• есть частная парковка (has private parking);
• есть веранда (has terrace);
• можно забронировать столик (accepts reservations);
• подходит для вегетарианцев (vegan friendly);
• дорогой (expensive).

• «Покажи мне рестораны, подходящие для вегетарианцев»;
• «Покажи мне недорогие рестораны с верандой, где можно забронировать столик».

Как? Давайте посмотрим. Первый запрос очень простой. Всё, что нам нужно, — это взять битмап «подходит для вегетарианцев» и превратить его в список ресторанов, чьи биты выставлены.


Второй запрос немного сложнее. Нам необходимо использовать битовую операцию NOT на битмапе «дорогой», чтобы получить список недорогих ресторанов, затем за-AND-ить его с битмапом «можно забронировать столик» и за-AND-ить результат с битмапом «есть веранда». Результирующий битмап будет содержать список заведений, которые соответствуют всем нашим критериям. В данном примере это только ресторан «Юность».


Тут очень много теории, но не волнуйтесь, мы увидим код очень скоро.

Где используются bitmap-индексы?

Если вы «загуглите» bitmap-индексы, 90% ответов будут так или иначе связаны с Oracle DB. Но остальные СУБД тоже наверняка поддерживают такую крутую штуку, правда? Не совсем.

Пройдёмся по списку основных подозреваемых.

MySQL ещё не поддерживает bitmap-индексы, но есть Proposal с предложением добавить эту опцию (https://dev.mysql.com/worklog/task/?id=1524).

PostgreSQL не поддерживает bitmap-индексы, но использует простые битмапы и битовые операции для объединения результатов поиска по нескольким другим индексам.

У Tarantool есть bitset-индексы, он поддерживает простой поиск по ним.

У Redis есть простые битовые поля (https://redis.io/commands/bitfield) без возможности поиска по ним.

MongoDB ещё не поддерживает bitmap-индексы, но также есть Proposal с предложением добавить эту опцию https://jira.mongodb.org/browse/SERVER-1723

• Но в нашем доме появился новый сосед: Pilosa. Это новая нереляционная база данных, написанная на Go. Она содержит только bitmap-индексы и базирует всё на них. Мы поговорим о ней чуть позже.

Имплементация на Go

Но почему bitmap-индексы так редко используются? Прежде чем ответить на этот вопрос, я хотел бы продемонстрировать вам имплементацию очень простого bitmap-индекса на Go.

Битмапы, по сути, представлены просто кусками данных. В Go давайте для этого воспользуемся слайсами байтов.

У нас есть один битмап на одну ресторанную характеристику, и каждый бит в битмапе говорит о том, есть у конкретного ресторана данное свойство или нет.

Нам понадобятся две вспомогательные функции. Одна будет использоваться для заполнения наших битмапов рандомными данными. Рандомными, но с определённой вероятностью того, что ресторан обладает каждым свойством. Например, я считаю, что в Москве очень мало ресторанов, в которых нельзя забронировать столик, и мне кажется, что примерно 20% заведений подходят для вегетарианцев.

Вторая функция будет преобразовывать битмап в список ресторанов.


Чтобы ответить на запрос «Покажи мне недорогие рестораны, у которых есть веранда и в которых можно забронировать столик», нам понадобятся две битовые операции: NOT и AND.

Мы можем немного упростить наш код, воспользовавшись более сложной операцией AND NOT.

У нас есть функции для каждой из этих операций. Обе они идут по слайсам, берут соответствующие элементы из каждого, объединяют их битовой операцией и кладут результат в результирующий слайс.

И вот теперь мы можем воспользоваться нашими битмапами и функциями для ответа на поисковый запрос.

Производительность не такая высокая, даже несмотря на то, что функции очень простые и мы прилично сэкономили на том, что не возвращали новый результирующий слайс при каждом вызове функции.

Попрофилировав немного с pprof, я заметил, что компилятор Go пропустил одну очень простую, но очень важную оптимизацию: function inlining.

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

Но я-то не боюсь и могу обмануть компилятор, воспользовавшись goto вместо цикла, как в старые добрые времена.

И, как видите, теперь компилятор с радостью инлайнит нашу функцию! В итоге нам удаётся сэкономить около 2 микросекунд. Неплохо!

Второе узкое место несложно увидеть, если внимательно посмотреть на ассемблерный вывод. Компилятор добавил проверку на границы слайса прямо внутрь нашего самого горячего цикла. Дело в том, что Go — безопасный язык, компилятор опасается, что три моих аргумента (три слайса) имеют разный размер. Ведь тогда будет теоретическая возможность возникновения так называемого переполнения буфера (buffer overflow).

Давайте же успокоим компилятор, показав ему, что у всех слайсов одинаковый размер. Мы можем это сделать, добавив простую проверку в начале нашей функции.

Видя это, компилятор с радостью пропускает проверку, а мы в итоге экономим ещё 500 наносекунд.

Большие батчи

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

Всё, что мы делаем, — это базовые битовые операции, и наши процессоры очень эффективно их выполняют. Но, к сожалению, мы «кормим» наш процессор очень маленькими кусками работы. Наши функции выполняют операции побайтово. Мы можем очень просто подтюнить наш код, чтобы он работал с 8-байтовыми кусками, используя слайсы UInt64.

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

Имплементация на ассемблере

Но это ещё не конец. Наши процессоры могут работать с кусками по 16, 32 и даже 64 байта. Такие «широкие» операции называются single instruction multiple data (SIMD; одна инструкция, много данных), а процесс преобразования кода таким образом, чтобы он использовал такие операции, называется векторизация.

К сожалению, компилятор Go — далеко не отличник в векторизации. На текущий момент единственный способ векторизации кода на Go — это взять и положить данные операции вручную с использованием ассемблера Go.

Ассемблер Go — странный зверь. Вы наверняка знаете, что ассемблер — это что-то, что сильно привязано к архитектуре компьютера, для которого вы пишете, но в Go это не так. Ассемблер Go больше похож на IRL (intermediate representation language) или промежуточный язык: он практически платформонезависимый. Роб Пайк выступил с отличным докладом на эту тему несколько лет назад на GopherCon в Денвере.

В дополнение к этому Go использует необычный формат Plan 9, отличающийся от общепризнанных форматов AT&T и Intel.

Можно с уверенностью сказать, что писать ассемблер Go вручную — это не самое весёлое занятие.

Но, к счастью, уже есть две высокоуровневые тулзы, которые помогают нам в написании Go ассемблера: PeachPy и avo. Обе утилиты генерируют Go-ассемблер из более высокоуровневого кода, написанного на Python и Go соответственно.

Эти утилиты упрощают такие вещи, как register allocation (выбор процессорного регистра), написание циклов, и в целом упрощают процесс входа в мир ассемблерного программирования в Go.

Мы будем использовать avo, так что наши программы будут почти обычными программами на Go.

Вот так выглядит самый простой пример avo-программы. У нас есть функция main(), которая определяет внутри себя функцию Add(), смысл которой заключается в сложении двух чисел. Здесь присутствуют вспомогательные функции для получения параметров по имени и получения одного из свободных и подходящих процессорных регистров. У каждой процессорной операции есть соответствующая функция на avo, как видно по ADDQ. И наконец, мы видим вспомогательную функцию для сохранения результирующего значения.

Вызвав go generate, мы выполним программу на avo и в итоге будут сгенерированы два файла:

• add.s с результирующим кодом на Go-ассемблере;
• stub.go с заголовками функций для связи двух миров: Go и ассемблера.

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

Ранее мы использовали лейблы и goto (или прыжки) для повышения производительности и для того чтобы обмануть компилятор Go, но сейчас мы делаем это с самого начала. Дело в том, что циклы — это более высокоуровневое понятие. В ассемблере же у нас есть только лейблы и прыжки.

Оставшийся код должен быть уже знаком и понятен. Мы эмулируем цикл лейблами и прыжками, берём маленькую часть данных из двух наших слайсов, объединяем их битовой операцией (AND NOT в данном случае) и затем кладём результат в результирующий слайс. Всё.

Вот так выглядит окончательный код на ассемблере. Нам не нужно было высчитывать смещения и размеры (выделено зелёным) или следить за используемыми регистрами (выделено красным).

Если сравнить производительность имплементации на ассемблере с производительностью лучшей имплементации на Go, то мы увидим, что она одинакова. И это ожидаемо. Ведь мы не делали ничего особенного — мы лишь воспроизвели то, что делал бы компилятор Go.

К сожалению, мы не можем заставить компилятор заинлайнить наши функции, написанные на ассемблере. У Go-компилятора на сегодняшний день такая возможность отсутствует, хотя просьба добавить её существует уже довольно длительное время.

Именно поэтому невозможно получить какие-либо преимущества от мелких функций на ассемблере. Нам надо либо писать большие функции, либо использовать новый пакет math/bits, либо обходить ассемблер стороной.

Давайте теперь посмотрим на векторные версии наших функций.

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

Одно из новшеств связано с тем, что более широкие векторные операции используют специальные широкие регистры. В случае с 32-байтными кусками это регистры с префиксом Y. Именно поэтому вы видите функцию YMM() в коде. Если бы я использовал AVX-512 с 64-битными кусками, то префикс был бы Z.

Второе новшество связано с тем, что я решил использовать оптимизацию, которая называется разворачивание цикла (loop unrolling), то есть сделать восемь операций цикла вручную, прежде чем прыгнуть в начало цикла. Данная оптимизация уменьшает количество бранчей (ветвлений) в коде, и она ограничена количеством свободных регистров, имеющихся в наличии.

Ну а что насчёт производительности? Она прекрасна! Мы получили ускорение примерно в семь раз по сравнению с лучшим решением на Go. Впечатляет, да?

Но даже эту имплементацию потенциально можно было бы ускорить, воспользовавшись AVX-512, префетчингом или JIT (just-in-time compiler) для планировщика запросов. Но это уж точно тема для отдельного доклада.

Проблемы bitmap-индексов

Сейчас, когда мы уже рассмотрели простую реализацию bitmap-индекса на Go и гораздо более производительную на ассемблере, давайте, наконец, поговорим о том, почему же bitmap-индексы так редко используются.

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

Проблема большой кардинальности

Итак, нам говорят, что bitmap-индексы подходят только для полей с малой кардинальностью, то есть таких, у которых мало значений (например, пол или цвет глаз), и причина в том, что обычное представление таких полей (один бит на значение) в случае большой кардинальности будет занимать слишком много места и, более того, эти bitmap-индексы будут слабо (редко) заполнены.


Иногда мы можем использовать другое представление, например стандартное, которое мы используем для представления чисел. Но именно появление алгоритмов сжатия всё изменило. За последние десятилетия учёные и исследователи придумали большое количество алгоритмов сжатия для битмапов. Основное их преимущество в том, что не нужно расжимать битмапы для проведения битовых операций — мы можем совершать битовые операции прямо над сжатыми битмапами.

В последнее время стали появляться и гибридные подходы, как, например, roaring битмапы. Они используют одновременно три разных представления для битмапов — собственно битмапы, массивы и так называемые bit runs — и балансируют между ними, чтобы максимизировать производительность и минимизировать потребление памяти.

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

Ещё один подход, который может нам помочь справиться с большой кардинальностью, называется группировка (binning). Представьте, что у вас есть поле, представляющее рост человека. Рост — это число с плавающей запятой, но мы, люди, не думаем о нём в таком ключе. Для нас нет разницы между ростом 185,2 см и 185,3 см.

Получается, мы можем сгруппировать похожие значения в группы в пределах 1 см.

А если мы ещё и знаем, что очень мало людей имеют рост меньше 50 см и больше 250 см, то мы можем, по сути, превратить поле с бесконечной кардинальностью в поле с кардинальностью примерно в 200 значений.

Конечно, при необходимости мы можем сделать дополнительную фильтрацию уже после.

Проблема большой пропускной способности

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

Базы данных должны давать возможность обновлять данные в тот момент, когда потенциально сотни других запросов осуществляют поиск по этим данным. Нам нужны локи, чтобы избежать проблем с одновременным доступом к данным или иных проблем совместного доступа. А там, где есть один большой лок, там есть проблема — lock contention, когда этот лок становится узким местом.

Эту проблему можно решить или обойти с помощью шардинга или использования версионированных индексов.

Шардинг — штука простая и общеизвестная. Вы можете шардировать bitmap-индекс так, как вы шардировали бы любые другие данные. Вместо одного большого лока вы получите кучу мелких локов и таким образом избавитесь от lock contention.

Второй способ решения проблемы — это использование версионированных индексов. У вас может быть одна копия индекса, которую вы используете для поиска или чтения, и одна — для записи или обновления. И раз в какой-то промежуток времени (например, раз в 100 мс или 500 мс) вы их дублируете и меняете местами. Конечно, этот подход применим только в тех случаях, когда ваше приложение может работать с чуть отстающим поисковым индексом.

Эти два подхода можно использовать одновременно: у вас может быть шардированный версионированный индекс.

Более сложные запросы

Последняя проблема bitmap-индексов заключается в том, что, как нам говорят, они плохо подходят для более сложных типов запросов, например запросов «по промежутку».

И правда, если подумать, битовые операции типа AND, OR и т. д. не очень подходят для запросов а-ля «Покажи мне отели со стоимостью номера от 200 до 300 долларов за ночь».

Наивным и очень неразумным решением было бы взять результаты для каждого долларового значения и объединить их битовой операцией OR.

Чуть более правильным решением было бы использовать группировку. Например, в группы по 50 долларов. Это ускорило бы наш процесс в 50 раз.

Но проблема также легко решается использованием представления, созданного специально для такого типа запросов. В научных работах оно называется range-encoded bitmaps.

В таком представлении мы не просто выставляем один бит для какого-либо значения (например, 200), а выставляем это значение и всё, что выше. 200 и выше. То же самое для 300: 300 и выше. И так далее.

Используя это представление, мы можем ответить на такого рода поисковый запрос, пройдя по индексу всего два раза. Сначала мы получим список отелей, где номер стоит меньше или 300 долларов, а затем выкинем из него те, где стоимость номера меньше или 199 долларов. Готово.

Вы удивитесь, но даже геозапросы возможны с использованием bitmap-индексов. Хитрость в том, чтобы использовать геопредставление, которое окружает вашу координату геометрической фигурой. Например, S2 от Google. Фигуру должно быть возможно представить в виде трёх или более пересекающихся прямых, которые можно пронумеровать. Таким образом мы сможем превратить наш геозапрос в несколько запросов «по промежутку» (по этим пронумерованным линиям).

Готовые решения

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

Однако не у всех есть время, терпение и ресурсы, чтобы создать bitmap-индексы с нуля. Особенно более продвинутые, с использованием SIMD, например.

К счастью, есть несколько готовых решений, которые вам помогут.

Roaring битмапы

Во-первых, есть та самая roaring bitmaps-библиотека, о которой я уже говорил. Она содержит все необходимые контейнеры и битовые операции, которые вам понадобятся для того, чтобы сделать полноценный bitmap-индекс.

К сожалению, на данный момент ни одна из Go-реализаций не использует SIMD, а значит, Go-реализации менее производительны, чем реализации на C, например.

Pilosa

Другой продукт, который может вам помочь, — СУБД Pilosa, у которой, по сути, только bitmap-индексы и есть. Это относительно новое решение, но оно завоёвывает сердца с огромной скоростью.
/>
Pilosa использует roaring битмапы внутри себя и даёт вам возможность использовать их, упрощает и объясняет все те вещи, о которых я говорил выше: группировка, range-encoded bitmaps, понятие поля и т. п.

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

Пример очень похож на то, что вы видели раньше. Мы создаём клиент к серверу Pilosa, создаём индекс и необходимые поля, затем заполняем наши поля рандомными данными с вероятностями и, наконец, выполняем знакомый запрос.

После этого мы используем NOT на поле «expensive», затем пересекаем результат (или AND-им) с полем «terrace» и с полем «reservations». И наконец, получаем финальный результат.

Я очень надеюсь, что в обозримом будущем в СУБД вроде MySQL и PostgreSQL тоже появится этот новый тип индексов — bitmap-индексы.

Заключение

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

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

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

What is Bitmap and How to Use Bitmap Effectively into Your Design

We come across bitmap images every day without even realizing it. It’s all around us because it’s used in so many visual designs that we can hardly avoid it. It even goes by another name, but let’s first understand the bitmap, what is a bitmap image, what is a BMP file, and other basic concepts that are very important when it comes to design.

What is a Bitmap?

A bitmap is essentially a group of squares on a screen, with each square being assigned a particular color. This square is not the same as a pixel, which is essentially a display unit on electronic screens. Pixels cannot be stretched or shrunk, obviously, because they are physical units; on the other hand, bits or squares that make up a bitmap can be enlarged or shrunken, which makes the image larger or smaller, as the case may be. However, it can get confusing because the bits in a bitmap are sometimes called pixels!

What is a Bitmap File?

When a group of these squares or bits is given a coordinated color according to a fixed reference ‘map’, it displayed a color image, which we call a bitmap or a bitmap image. This image is stored in the form of the BMP file format, which has the extension .bmp. This bitmap file can be inserted into a document or a design when required. Of note is the fact that a bitmap image is sometimes also called a raster image, but it is not exactly the same. In turn, these two image file formats are different from vector images. This is an important difference for designers to be aware of.

Now that we’ve covered the basics of what’s a bitmap and how it is stored and used, let’s go a little deeper.

More Introduction about Bitmaps

The problem with bitmaps or even raster images is that they cannot be enlarged to a great degree. If they are, you will see an effect called pixelation, which is basically the phenomenon where you can see the individual squares rather than a smooth finish. Despite this drawback, bitmap images are extremely useful when designing interfaces and print materials.

How are Bitmaps Created and Saved?

We saw the concept of a map representing the color of each individual square in a bitmap image. The color is defined by the data for that square on the bitmap. The map is sometimes referred to as a key that tells you which color is assigned to each of the thousands of squares on a typical bitmap image. That’s essentially what is stored in a .bmp file — the data that tells the rendering part of the software how many squares there are and the color of each individual square.

How are Bitmap Images different from Raster Graphics?

Although a lot of designers use the term raster to refer to bitmap images, it’s not always the same thing. A raster image can either be a pixelmap or a bitmap. When it’s a bitmap, then using either term is correct. However, a pixelmap is a map of how individual pixels should be assigned their colors. This can cause a lot of confusion but, for the most part, raster graphics are usually referred to as bitmaps and vice-versa.

What are some Common Formats for Bitmap Images?

The BMP file format is just one of many file formats for bitmaps or raster graphics. The most common and widely used formats are JPG, GIF, TIFF, PSD, PNG, etc. that are primarily used for web transfers. Other popular formats are RAW and EXIF, which contain not only the information about the image and how to render it but also tells us about the capture device (usually a camera), what settings were used, etc. This metadata is very important in many use cases.

Of all these types, the BMP file format is the only one that cannot be compressed, and it is exclusive to Windows systems. All other image file formats use some kind of compression algorithm to reduce the file size so they can be sent via the Internet. This makes them easy to upload and download, so they’re very suitable for design projects.

The Drawbacks of using Bitmap Images in your Design

The compressibility issue is one of the major problems with bitmap images. Since you can’t reduce the file size, you’ll need to transfer it as it is. This is sometimes not possible unless you have FTP access or a file transfer service with adequate capacity. Remember, you generally won’t send one image at a time, which is what makes this an inconvenient format.

The second problem, as we saw, is pixelation. This is where the image becomes visible as individual color-squares rather than a smooth image. It can cause an image to get blurred, which looks bad on an otherwise slick design.

That being said, if you’re aware of these limitations, there are no significant roadblocks for you to use bitmap images to good effect in your designs.

How to Use Bitmaps Effectively in your Designs

One of the advantages of using bitmap images in your designs is that bitmap files can hold a lot of color information. This is especially useful when working with photographs or when you want to create images are look very real. This also gives you access to a wider range of colors for rich color transitions and more. That gives us three scenarios where bitmap trumps vector.

1. When using photographs in your design — A bitmap or raster is the natural choice when your design has photos in it. That’s because photos are essentially made up of pixels, which makes it easier to convert them into another analog version, the bitmap. Edits are easier to make and the transition from one color to another is much smoother. The only thing to watch out for is. you got it — pixelation!

2. When you need to do extensive edits and need more detail — Since you can alter the color profile of individual pixels, your edits can be much more granular. It’s also easier to add effects like drop shadows, change the contrast, make lines look smoother, etc. A significant amount of such detailing is only possible when you use raster or bitmap images in your design.

3. When you want your images to look like photos — i.e. realistic — Raster images look far more real than vector images, so if you’re using natural objects such as flowers, etc., a bitmap is the better choice. You also have much more control over the color profile of the bits or pixels making up the image, giving you a better end result that is as close to natural as possible.

Conclusion: Bitmap images certainly have their drawbacks, but they make your designs look richer and more realistic. As long as you know how to work within the limitations of pixelation and image transfers, you can use bitmap images in a very powerful way.

What is Bitmap? Features, Types & More

A bitmap refers to the particular graphic file format. It uses the extensions .bmp (bitmap) or .dib (device-independent bitmap) and is used mainly in Microsoft Windows and OS/2. It also refers to a raster or bitmapped image format.

Technically, this is an image file format that allows creating and storing computer graphics. The file actually contains a lot of tiny dots in a specific pattern that creates an image when viewed from a distance.

• A bitmap refers to the network made of rows and columns or a domain of bits that displays a rectangular image made up of pixels.
• Every cell in it has a value to either fill it in or leave it blank, which creates an image.
• A bitmap can be created by breaking an image into the smallest possible pieces, called pixels, and storing the color depth or info of each in bits.
• The number of rows and columns or the color intensity of each specific dot can be increased but this will also increase the density of the bitmap image.
• Magnifying a bitmap image too much will make it pixelated because the dots will then become small color squares on the grid.

Understanding Bitmap

A bitmap simply refers to a file format or a memory organization that consists of rows and columns of bits, called pixels. These pixels are usually squares created by bits.

The primary purpose of developing the bitmap format by Microsoft in the 1980s was to provide the users with images that are application or device-independent.

It also offers the users a useful and easy way to use a small amount of memory to keep track of it for a bitmap table.

• A bit array
• A bitmap index
• A raster image
• A pixmap

Usually, the bitmap files are larger in size. That is why it is not used commonly outside of the Microsoft Windows setting.

There are different types of bitmaps, as you will come to know about them in the later section, but apart from BMP, every other format implements a compression algorithm to ensure that the bitmaps are smaller and it is easier to transfer them across the internet.

Pixels

• 8 bits for Black and White
• 24 bits for color

There are often tens of thousands of these bits, which collectively display the image.

• There are 800 pixels for 600 lines on the computer screen.
• Collectively, there are 480,000 pixels in the image.

When the number of pixels is higher, the image will be more realistic and clearer.

Saving

• In 4-bit (16 colors)
• In 9-bit (256 colors)
• In 16-bit (65,536 colors)
• In 24-bit (16.7 million colors)
• As uncompressed images

Compression

Typically, for making changes in the files to store and transfer, data compression is used in bitmaps.

• The pixels are more prominent.
• They are not close to each other.
• They have themselves changed into small squares.

On the other hand, if the compression is lower, the bitmap will be more intact and will look pretty much the same as the original.

Requisites

• If the size of the unit is smaller, the bitmap will be bigger. This is because it will store the value 1 or 0 for every individual unit.
• If the unit size is bigger, on the other hand, the bitmap will be smaller.

There is no need to select a large size for the units because, even with a small unit size of, say, 3 bytes, a single bit of the bitmap can denote 24 bits.

This is because the size of the bitmap depends entirely on the size of the memory unit as well as the memory.

However, the problem arises when an ‘n’ size memory block in the bitmap is required to be engaged by a process.

In such a situation, a ‘n’ size vacancy with all zero values will be required in the bitmap.

What are the Features of Bitmap?

Ideally, there are two specific features of a bitmap namely, the resolution or number of pixels, and the color depth for each pixel.

However, there are also a few other notable features of a bitmap, such as:

• They can be edited easily because a bitmap image is typically created pixel-by-pixel.
• It allows users to add or remove pixels and change the color of each of them by zooming in on an image irrespective of the graphics program.
• It is one of the several different forms of storing images in a computer. It typically has the .bmp extension.
• Every pixel in a bitmap is allotted a bit, at least. It indicates whether or not it should reflect in the background, foreground, or any other color.
• It uses different shades of lighting and gradations of color while displaying a color image.
• The larger the number of bits, the larger is the file and greater is the bitmap resolution.
• The size of a bitmap file is reduced by using a compression technique, but the necessary data is retained to display a good image.
• The use of lossless compression techniques can resize smaller files with satisfactory results.
• A bitmap image cannot be greatly rescaled. Excessive rescaling will make the image blurry and pixelated and reducing it too much will result in the loss of image clarity.
• It cannot reproduce images with more than 256 colors.
• Photos saved in this format can be reduced for the internet by converting into the JPEG format, which is a lossy compression arrangement but can display photos with more than 256 colors.
• Bitmaps can produce any 2D rectangular image and also allow copying and pasting it repetitively to cover a large area quickly and easily with the same repeating pattern. This is referred to as a tile map.

How Many Types of Bitmap Images are There?

There are five major types of bitmap images. However, there are also a few others that are used in specific types of systems.

These are Bitmap or BMP, Graphics Interchange Format or GIF, Joint Photographic Experts Group or JPEG, Portable Network Graphics or PNG, Tag Image File Format or TIFF, Exchangeable Image File or EXIF, X BitMap or XBM used in X Window systems, and PiCture eXchange or PCX.

Each of these types can be distinguished by their respective features, as explained below.

• Usually used by Windows
• Used to store application-independent and device-independent images
• The number of bits per pixel is specified in the file header
• Usually, BMP files have 24 bits per pixel
• These files are usually not compressed
• Not suitable for transfer over the internet

• Usually used for images on web pages
• Suitable for line drawings
• Works well with pictures with sharp boundaries between blocks of solid colors
• Used for internet-enabled projects
• These files are usually compressed
• Uses a compression algorithm
• One color can be selected as transparent
• One single file can store a set of images to create an animated GIF
• Can store 8 bits per pixel at most
• They are restricted to 256 colors

• It is a compression scheme
• Suitable for scanned photos and natural scenes
• May result in negligible loss during the compression process
• It can store 24 bits per pixel
• Suitable for web transfer
• Can display more than 16 million colors
• Do not support animation or transparency
• Used for internet-enabled projects
• It supports a configurable level of compression
• Uses a compression algorithm
• It is not suitable for blocks of solid color, line drawings, and sharp boundaries
• JPEG is not a file format but JPEG File Interchange Format (JFIF) is, which stores the images
• These JFIF files use .jpg extension

• Used for pictures taken by a digital camera
• The images are compressed based on the JPEG specification
• No loss of information
• Uses a compression algorithm
• Files can use 1, 2, 4, or 8 bits per pixel
• In addition to the images, the files also contain information about its such as date, shutter speed, and exposure time
• The file stores information about the manufacturer of the camera, its model, and others as well

• Files are compressed
• No loss of information
• Uses a compression algorithm
• Stores colors with 8, 24, or 48 bits per pixel
• Stores grayscales with 1, 2, 4, 8, or 16 bits per pixel
• Can store an alpha value per pixel to specify the degree of color blending with the background
• Displays a better image progressively
• It contains gamma correction information
• It can store color correction information

• More flexible and extendable format
• Supported by a wide range of image processing apps and platforms
• Images are stored with a random number of bits per pixel
• Uses a range of compression algorithms
• Can store multiple images in one single multiple-page file
• Stores information of the image, host computer, scanner make, orientation, compression type, samples per pixel, and more
• Properly arranged by means of tags

Bitmap Vs Vector

• A bitmap is a block of colors represented in a grid format, but in comparison, vectors represent colors and shapes created by using mathematical formulas.
• Bitmap is suitable for working on photographs, but in comparison, vector is best suited for logos and several other illustrations.
• The common types of bitmap image files include .jpg, .png, .gif, .bmp and more, but in comparison, the common types of vector files are .svg, .eps, .pdf and more.
• Bitmap is also referred to as raster graphics, but in comparison, vector is also referred to as object-oriented graphics.
• A bitmap graphic is much larger in size in comparison to a vector graphic of similar nature.
• Changes in resolution will affect a bitmap image but the vector graphics will not be affected by the changes in resolution.
• Altering a bitmap image is not as easy as modifying vector graphics.
• It is easy to convert one type of bitmap file to another, but it is not easy to convert one type of vector file to another.
• It is very hard to convert a bitmap graphic into a vector graphic, but in comparison, converting a vector graphic into a bitmap graphic is relatively simple.
• The bitmap graphics take up larger memory and storage space, but in comparison, the vector graphics do not.
• A bitmap graphic is not scalable, but in comparison, a vector graphic is.
• Bitmaps usually have a much wider color capability in comparison to the vector graphics.
• Bitmap uses comparatively less processing power than the vector graphics.
• Bitmap images cannot be resized without sacrificing pixels, but in comparison, vector images can be resized without any adverse effect on their quality.
• Bitmap images are not as easy to use as the vector images since the latter is resolution-independent.

Questions & Answers:

Why is Bitmap Used?

One of the main reasons to use bitmaps in your image design is that the file will contain loads of color information in the form of uncompressed data. This is ideal for storing and displaying digital images of high quality.

This will be very helpful when working with images or photographs that need to look real since you will be able to access a much wider range of rich colors to use for transitions and more.

How Many Bits are There in a Bitmap?

Usually, the number of bits in a bitmap file is detailed in the file header. It can be varied, such as 1, 4, 8, 15, 24, 32, or 64 bit per pixel, but a bitmap with 24 bits per pixel is used most commonly.

What is the Size of a Bitmap File?

The size of the bitmap file would typically depend on the way the individual pixels are handled. Usually there are a few dimensional restraints to a bitmap file, which may max out at 4 GB.

What are Bitmap Images Made Up of?

Typically, the bitmap images are made up of pixels instead of lines. This means that when you zoom a bitmap image it will be grainy, instead of being sharp or smooth.

Where are Bitmap Images Stored?

In a computer, the bitmap images are stored where every other thing is stored, that is, in a file system on the hard disk as a file.

It may be stored as an entire image in a file, or sometimes it may be stored as a part of the content in a file. The image is stored in a compressed format as a quadrangular grid of pixels.

Conclusion

Bitmap or raster images are typically made up of pixels or small dots of diverse colors, set in a proper manner to create an image.

Ideally, it is the arrangement of the pixels in a bitmap image that makes it easy to use. It is highly dependent on the resolution and therefore changes in it may result in a loss of image quality.

About Puja Chatterjee

Puja Chatterjee is a technical writer with extensive knowledge about computers. She graduated from BIMS. Her expertise includes technology writing and client relationship management gained through over 12 years of experience. Follow Her at Linkedin.