Контейнерная библиотека на C без затей (часть 1)

В Our Machinery мы свято верим в минимализм – всегда стараемся сделать все проще и меньше. Чем больше кода у вас в проекте, тем больше вам приходится переживать. Надо больше разбираться, оптимизировать, отлаживать, рефакторить, портировать, модернизировать, документировать и т.д. и т.п. Больше кода – больше проблем!

Мы также стараемся уменьшить использование внешних библиотек. Это, наверно, самый спорный момент. Много кто посоветовал бы вам не изобретать велосипед. И в некоторых сообществах разработчиков (мы судим по node.js) программисты ни на минуту не задумаются о том, стоит или не стоит вводить пакетную зависимость для функции длиною в три строчки.

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

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

В нашем случае конечными пользователями являются разработчики. Мы не можем предсказать, каким образом они будут использовать код, и не хотим ограничивать их. Это означает, что они могут столкнуться с проблемами производительности или ошибками, о которых мы никогда не задумывались. Так что «это просто работает» для нас недостаточно. Код должен вести себя приемлемо в самых разных сценариях. Мы не только не можем полностью предсказать, что сделают пользователи – мы также не можем знать, что для них будет важно: размер приложения, производительность, время компиляции, работа на узкоспециализированной платформе и что-то еще? Давать такие гарантии со сторонними библиотеками сложно.

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

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

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

Типы контейнеров

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

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

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

Руководствуясь в Our Machinery духом минимализма, мы решили пойти дальше и определить в библиотеке только два типа контейнеров:

• Массивы (или «растяжимые буферы»)
• Хэш-таблицы

Никаких списков, деревьев, строк, очередей, множеств и т.п.

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

Важно отметить, что в качестве основного языка программирования мы используем C, а не C ++. Это означает, что у нас нет контейнеров обобщенного типа, таких как vector<T>.

Я не большой поклонник шаблонов C ++ вообще. Они делают заголовочные файлы раздутыми. Зачастую сильно увеличивают время компоновки и размер кода. Сообщения об ошибках непонятны. Абстракции часто не являются нулевыми (даже если так обещают). Шаблоны порождают монстров сверхабстракции, таких как vector<T, allocation_policy, storage_policy, threading_policy, ...>. И при написании шаблона сложный код нужен даже чтобы скомпилировать оператор if.

Но для обобщенных функций типа vector<T> шаблоны, конечно же, великолепны!

Варианты реализации контейнеров собственными силами, безусловно, невелики:

• Мы могли бы реализовать отдельные типы для сбора всего, что хотим сохранить: char_array, int_array, float_array  и т. д. – фуу!
• Мы могли бы взять большой union  как вариант контейнера и хранить такой массив – фуу!
• Мы могли бы сделать qsort() и bsearch(), уничтожить всю информацию о типе и заставить пользователя вызывать void * для правильных – фуу!

К счастью, кроме C у нас есть еще магия препроцессор!

Массивы ( «растяжимые буферы»)

Наша реализация массива основана на методе «растяжимого буфера», популяризированном Шоном Барретом.

Основная идея метода – представить массив с помощью регулярного указателя на элементы:

my_type_t *a = NULL;

Указатель NULL  представляет пустой массив. Если массив не пуст,  a  укажет на элементы массива. Но вот в чем трюк: непосредственно перед элементами мы размещаем небольшой заголовок с данными, которые отслеживает  std::vector:

Структура памяти в растяжимом буфере

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

struct array_header_t
{
uint32_t size;
uint32_t capacity;
};

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

#define array_header(a) \
((array_header_t *)((char *)(a) - sizeof(array_header_t)))

Макрос для вычисления размера массива, соответственно:

#define array_size(a) ((a) ? array_header(a)->size : 0)

Обратите внимание, что о случае a == NULL надо позаботиться отдельно.

Добавление элементов в массив будет выглядеть примерно так (скобки убрали, чтобы было удобнее читать):

#define array_push(a, item) \
array_full(a) ? a = array_grow(a, sizeof(*a)) : 0, \
a[array_header(a)->size++] = item

Здесь array_full() это макрос для проверки  size == capacity, а  void * array_grow(void *, uint32_t) является регулярной функцией C, выделяющей для массива новую память. Обратите внимание, что ей необходимо передать размер элементов, поскольку нет информации об их типах. Чтобы объединить несколько выражений в одной строке, мы пользуемся запятой, в этом тоже заключено преимущество С. Подробности можно посмотреть в реализации растяжимого буфера.

Самое приятное в этом подходе то, что мы получаем правильный тип переменных (my_type_t *a) абсолютно не нуждаясь в обобщенных функциях. Еще весьма приятно, что указатель NULL представляет собой допустимый (пустой) массив. Это означает, что для получения структуры с массивами достаточно по умолчанию инициализировать x = {0}.

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

Еще одним недостатком является то, что указатели на растяжимые буферы неотличимы от обычных указателей. Т.е. мы не можем сказать, указывает ли  char *x именно на растяжимый буфер. Поэтому указатели на буферы я помечаю комментарием:

/* array */ char *x;

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

Хэши

В STL хэш-таблицы реализуются при помощи std::unordered_map<K, T>. Чтобы сделать нечто подобное в С, мы можем воспользоваться подходом растяжимого буфера и определить нашу хэш-таблицу как:

key_t *keys;
value_t *values;

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

Но я не думаю, что этот подход лучший. На самом деле, можно поступить проще.

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

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

Мы можем избавиться от проблем, если хэшировать ключи до того как помещать в хеш-таблицу. То есть мы просто применяем хеш-функцию hash (key) → k, а затем используем k вместо key в качестве ключа хэш-таблицы.

Единственное предостережение заключается в том, что хешировать ключи надо в достаточно большом пространстве, чтобы быть (статистически) уверенным в отсутствии коллизий. Если hash (key_1) = hash (key_2), мы не сможем сохранить оба key_1 и key_2 в хеш-таблице. Мы выделяем большой объем для своих хэш-таблиц. 64 бит достаточно, но при необходимости вы можете устанавливать и 128.

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

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

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

struct hash_t
{
uint32_t num_buckets;
uint64_t *keys;
uint64_t *values;
};

Затем мы определяем функции для управления этим:

uint64_t hash_lookup(const struct hash_t *hash, uint64_t k, uint64_t default_value);

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

(На самом деле в нашем коде есть две версии хэш-таблицы:  hash64_t для 64-битных данных и  hash32_t  для 32-битных).

Добавление значений в хэш-таблицу выглядит примерно так:

hash_t info_lookup;
/* array */ info_t *info;
array_push(info, my_info);
hash_add(&info_lookup, hash_string("my name"), array_size(info) - 1);

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

Далее…

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

Источник: http://ourmachinery.com/post/minimalist-container-library-in-c-part-1/