Давеча довелось применить sparsetable из Google-овского sparsehash для представления разреженного вектора значений. Разреженный вектор в моем случае -- это вектор с обычной индексацией от 0 до N, где части элементов нет физически. Обращения к элементам идут именно по целочисленным индексам (к тому же индексы в моём случае были представлены std::uint32_t).
В принципе, здесь можно было бы воспользоваться каким-то ассоциативным контейнером на базе деревьев или хэш-таблиц, но все эксперименты показывали, что когда в разреженном векторе хранятся небольшие значения (например, указатели), то любые ассоциативные контейнеры потребляют значительно больше памяти чем обычный std::vector вектор, в котором незанятые ячейки заполнены специальными "мусорными" значениями.
Тогда как sparsetable показал себя здесь очень и очень хорошо.
Причем речь идет именно о классе sparsetable, который хоть и публичный в библиотеке sparsehash, но все-таки выглядит как вспомогательный внутренний класс, использующийся в реализации sparse_hash_map и dense_hash_map. Т.е. это именно что специальная структура данных для представления разреженного вектора, а не какой-то из вариантов хэш-таблицы.
При том, что класс sparsetable отлично зарекомендовал себя именно как специализированная структура данных, не могу не отметить несколько неприятных особенностей реализации sparsetable, обусловленных как старым C++ стандартом, в рамках которого написан sparsetable (а это C++03), так и подходом к разработке софта в Google.
Зафиксирую здесь те из них, которые я нахожу принципиально важными. Очень надеюсь, что найду время и силы сделать форк реализации sparsetable, в котором постараюсь от этих проблем избавится. Но, к сожалению, не уверен получится ли.
Итак, поехали.
Поскольку sparsetable написан для C++03, то он не поддерживает move semantic. Вообще. Причем как для самого sparsetable -- там нет ни конструктора, ни оператора перемещения, хотя swap для sparsetable есть. Но, самое плохое, sparsetable не поддерживает movable-only типы, вроде std::unique_ptr. Т.е. из коробки не получится хранить в sparsetable экземпляры std::unique_ptr 🙁
Еще sparsetable не поддерживает strong exception safety. Там прямо в комментариях в коде написано, что следовало бы реализовать обработку ситуации, когда конструктор копирования для помещаемого в контейнер объекта бросает исключение. Если такое произойдет, то контейнер останется в хз каком состоянии.
И с exception safety там есть еще один прикольный момент: дело в том, что sparsetable выполняет переаллокацию памяти даже при удалении элемента. Т.е. да, вы вызываете erase, внутри erase sparsetable решает заменить блок из которого элемент изъят блоком меньшего размера, для чего обращается к аллокатору... А аллокатор, в принципе, может бросить исключение. Т.е. из erase может вылететь bad_alloc 🙁 Что неприятно, т.к. время от времени я пишу код, в котором для выполнения отката ранее внесенных изменений при исключении делаются erase для возврата модифицированных контейнеров к исходному виду. Представьте себе что в блоке catch или даже в деструкторе объекта вы вызываете erase для sparsetable, а он бросает bad_alloc 🥴
Ну и работа с памятью там имеет одну важную особенность. По умолчанию sparsetable использует собственный аллокатор под названием libc_allocator_with_realloc. Этот аллокатор, как следует из его названия, полагается на Си-шный realloc при переаллокации блоков данных. Но вот если std::realloc возвращает NULL, то sparsetable просто... прерывает работу программы через вызов std::exit. Понятно, что это особенности Google-овского софта, под нужды которого sparsetable и писался, но блин, представьте себе, что у вас сервер, который держит в ОП информацию о десятках тысяч текущий сессий. И вдруг весь этот сервер одномоментно падает из-за того, что при обработке запроса в рамках одной из сессий не удалось переаллоцировать блок в одном sparsetable. Как-то печально, как по мне 🙁
Плюс к тому исходный sparsetable содержит методы для какой-то странной сериализации/десериализации. Полагаю, что в Google от sparsetable это требовалось. Но зачем это всем остальным -- хз.
И совсем отдельная история -- это отношение sparsetable к несуществующим элементам. Так, константная версия operator[] возвращает константную ссылку. В том числе и на несуществующие элементы! Если значения по индексу i нет, то operator[] вернет константную ссылку на статический объект типа T. Что, помимо прочего, означает, что тип T должен быть default-constructible.
Из-за того, что sparsetable выдает несуществующие элементы за существующие, но с общим дефолтным значением, проистекает и то, что у sparsetable есть два типа итераторов. Обычный итератор, который возвращается посредством begin/end, и который итерируется, в том числе, и по несуществующим элементам. И специальный nonempty-итератор + специальные методы nonempty_begin/nonempty_end, которые следует использовать, если хочется пробежаться только по существующим элементам.
Могу предположить, что подобные заморочки с имитацией несуществующих элементов через общее дефолтное значение были полезны для реализации хэш-таблиц на базе sparsetable. Но если использовать sparsetable отдельно, то выглядит это несколько странно (мягко говоря 🤨)
В общем, под нужды заказчика sparsetable из sparsehash был вытащен, избавлен от части ненужного хлама, слегка доработан напильником для устранения проблем с компиляцией под C++20 и использования std::allocator. Но до глубокой модернизации sparsetable руки так и не дошли. Однако желание сделать это осталось. Буду надеятся, что это получится сделать.
Если кто-то из читателей никогда не слышал про sparsetable, то впечатление можно составить вот из этого описания: Implementation of sparse_hash_map, dense_hash_map, and sparsetable. Там первая часть как раз sparsetable и посвящена. Описание лаконичное, но толковое.
