Tuesday, June 29, 2021

art_map: Adaptive Radix Tree implemented as a std::set/std::map container

TL;DR: https://github.com/justinasvd/art_map, 10x faster searches than std::map, patches welcome!

I was happily hacking away at my ART implementation UnoDB when Justinas V. Daugmaudis noticed it and decided to implement a C++ container-style data structure using it. This thought had crossed my mind previously too, but the project looked definitely not-fun to me due to the level of C++ knowledge required, which I, a finger-tracking reader of "Effective Modern C++" do not possess. Now Justinas, a Boost contributor, knows his C++ at the language lawyer level, in fact I don't know anyone better suited to pull off a proper C++ container implementation.

There are significant differences between C++ container needs and what UnoDB provides with its in-memory-DB-ish interface and whole Optimistic Lock Coupling business, so Justinas could not just wrap my implementation. He ended up taking my source code, removing OLC and leaf node code, and writing some actual proper C++ in its place, with my surviving code being mostly internal node algorithms. He also replaced the node type bytes with tagged pointers, reducing node sizes, something I also plan to do. In other words, UnoDB now has all the attributes of a successful open source project-it was forked! /s

We exchanged ideas in the process, with me implementing several performance-related suggestions of his (I lost one bet), him following my development too, all for the better.

I also provided a fuzzing service for Justinas-by wrapping art_map into UnoDB-compatible interface and plugging it into my fuzzers. The API surface tested this is too narrow for my liking but still getting the important insert/delete/search code paths. And the fuzzers, the same ones I praised in my previous blog post, came up with absolutely nothing, to my shock. That tells something about writing code in a, uhm, mathematical way. Yet, he claims it's alpha and could kill your cat.

Besides collaborating with art_map I also added several OLC-specific optimizations, did major internal cleanups from Justinas code review, and changed the license to Apache 2.0 because someone asked me to.