Porting UnoDB to ARM64

ARM is the most common non-Intel instruction set, and UnoDB has enough of Intel-specific code to make its port an interesting project. I started out on AWS Graviton 2 hardware (ARMv8.2+extensions instruction set) and finished on an Apple M1 (ARMv8.5+extensions). The latter became my daily development platform.

I believe any porting effort goes through similar steps: 1) make it build; 2) get it tested; 3) make it correct; 4) make it fast. Let's review them.

1) Make it build. While I had been trying to properly isolate Intel code with conditional compilation, some bits slipped through, which was to be expected while it was an Intel-only build. Some Intel code was missing preprocessor conditional compilation guards. Node16 search did not have a platform-independent fallback implementation. Both were easy to fix. Then, only three ARM-specific bits were required: cache line size constants, and the spinlock spin loop body. For the latter I went with the YIELD instruction. Optimistic lock spinlock implementation is probably the most underdeveloped feature of UnoDB anyway (it is a single PAUSE instruction on Intel), I didn't sweat it too much. The last ARM-specific bit was the platform-specific static_asserts to confirm the internal node sizes, which is entirely optional too.

2) Get it tested. I needed a free public CI/CD service. Internet said there are two options available: Travis-CI, and CircleCI. GitHub Actions, the one I was using already, supports ARM, but only if you provide your own runner VMs, so, nope. Now Travis-CI was something I used before, and then stopped, together with the rest of the OSS world. CircleCI was OK, thus I set up a simple job there at first, and added different compilers, tests, and sanitizers later.

3) Make it correct. Well, the tests passed on the first run attempt. All of them. With sanitizers. Under Valgrind. This includes the parallel tests for relaxed-atomics-heavy QSBR and Optimistic Lock Coupling ART. On ARM having a weaker memory model than Intel. I still haven't seen a crash since. Either I am lucky, or all that consistent testing over time on Intel using sanitizers, including ThreadSanitizer, pays off.

4) Make it fast. In this case this means porting the code that uses Intel vectorization intrinsics. There are libraries to write vectorized code at a slightly higher abstraction level (sse2neon, simde, and others), but I wanted to learn the actual architecture. That actual architecture has several vectorization instruction set extensions: NEON, SVE, SVE2. NEON very roughly corresponds to, say, SSE4, provides 128-bit vectors, and is the simplest one to use. Now SVE (and SVE2) is something else altogether. They provide means to write vector width-independent code, that is, the same code would run unmodified on a CPU with 128-bit vectors and on a CPU with 512-bit vectors. Naturally this comes with an overhead to query the runtime vector width and handling the data sizes not fitting evenly into vectors. This appears to be best suited for processing large amounts of data, which UnoDB internal nodes aren't. Thus I went with simpler NEON.

All the UnoDB vectorized code loop bodies follow the same pattern:

1. Load the next part of data
2. Compare it in some way against something, getting a result vector
3. Take the mask of the result vector and process it as needed.

That "take the mask of a vector" part is handled by PMOVMSKB/VPMOVSKB instructions (_mm_movemask_epi8 & _mm256_movemask_epi8 intrinsics), and so it happens that NEON does not have a direct replacement. I tried some emulating implementations from sse2neon and simde, getting slower than baseline results every time. Nevertheless, I managed to implement a faster Node4 search in NEON by observing that the useful part of the result vector is so small it can be copied to a general purpose register directly instead of movemask'ing it. This resulted in up to 14% higher throughput in the related microbenchmarks over the SWAR-in-a-general purpose register-optimized baseline.

At this point I had thought I was done because I couldn't overcome slow movemask fallback implementations for the rest of the code. Then, someone on Twitter (dead link–the account has been deleted since, I believe it's him) posted a new movemask replacement based on SHRN (shift right and narrow). This operation can be considered as a "halfway-movemask" which does not get down to a single bit per vector element, but it does not have to. Once we get something that fits in a GP register (or a pair of them, in the initial Node16 search implementation), we can work with that.

With this, a straightforward Node16 NEON search resulted in up to 50% higher throughput (and in up to 8% regression in the case of minimal-sized Node16, I took that trade-off). Node48 insert position search became up to 8% faster in the single-load-per-iteration implementation, and then I unrolled that loop to load four registers (8 elements per iteration). Unfortunately I misplaced the benchmark results of that, I recall it being something up to 10% faster on the top of baseline NEON.

Interestingly this code is unrolled exactly the same in all three (SSE4, AVX2, NEON) vector implementations to process four vector registers per iteration, corresponding to handling eight pointers per iteration for SSE4 & NEON, and 16 pointers for AVX2.

So, ARM64 is now a first-class platform for UnoDB, which is also convenient for me due to switching to Apple M1 as my main machine.

ART: how much faster AVX2 is than SSE4?

The original Adaptive Radix Tree paper, with vectorization as one of the main selling points, only requires SSE2 intrinsics, introduced with the first Pentium 4 in year 2000. And I developed UnoDB on an AVX-supporting Intel CPU, Sandy Bridge, 2nd Core generation, introduced in 2011. It might be considered a bit long in the tooth now, but still a bit newer than SSE2, and I have used SSE4.1 intrinsics too.

Then I upgraded the Sandy Bridge machine to Kaby Lake (7th generation, 2016), and started looking into an AVX2 port.

The vectorized ART algorithms were:

• Node4 search and insert position search (both regular and while expanding N4 to N16), all data fitting into a single XMM register
• Node16 search and insert position search, the original ART paper algorithm, again all data fitting into a single XMM register
• Node48 insert free child slot search, which is a first nullptr search in an array of 48 pointers

For the first two, I couldn't think of any ways to improve them. The data is already in a single XMM register. Maybe the compiler uses AVX2 VPBROADCAST* to do loads, stores, and, well, broadcasts, I am not sure, it's up to it.

The last one, however, is a textbook vectorization case, even if the amount of data is relatively small. The SSE4 implementation loads four XMM registers to process eight pointers per loop iteration. The array length being 48 easily permits unrolling the loop once more, to handle 16 pointers per iteration, but that implementation was slower for me.

For AVX2 I started with the simplest implementation and then tried to improve it step by step, using synthetic microbenchmarks for the N48 insert.

• The simplest implementation is to load and process a single YMM register (four pointers) per loop iteration. 2% to 5% speedup for N48 insert over the baseline which handled twice as much per iteration
• Then, unroll loop once for eight pointers per iteration. 1% to 8% speedup over the previous step
• Then, I experimented with prefetching the next loop iteration, but that was slower, I guess it's a trivial case for the hardware prefetcher.
• Then, unroll loop twice for 16 pointers per iteration. 2% to 10% speedup over the loop unrolled once.

The three steps together amount to 2% to 40% speedups (and there's a 2% regression in a single hopefully rare case) over SSE4, and that's the benefit of AVX2 I was able to get.

If that loop were unrolled once more, it would disappear: the first "iteration" would handle 32 pointers, and then separate code would optionally handle the remaining 16. I did not go down this road.

The next project would be to add AVX-512 support, but I don't have the hardware nor I am really motivated to get my hands on it. A fun fact: did you know that "512" in AVX-512 refers to the total number of different instruction sets all calling themselves AVX-512? But then again, the base AVX-512F set should be enough for me.

(edit: replaced GitHub line links with line range links)

UnoDB and exception safety

Nobody uses exceptions in C++, which makes C++ an exceptional (sorry) language. Everybody uses exceptions in Java, for example. I cannot think of any other language whose practitioners ignore the main prescribed error handling method so thoroughly, to the point of standardization work now adding alternate (not replacement! merely alternate) error handling mechanisms, which then don't cover all use cases, resulting in a fine mess IMHO.

I find the main accepted C++ way of handling errors by checking every return value at every call site for every possible error incredibly verbose, ugly, error prone, and I actually like C++ exceptions. Maybe that's because I did not have to use them for embedded development, did not care about error messages having full stacktraces, nesting them, their performance, and dealing with catching "..." in a useful way. In other words, maybe I find them to be OK because I never actually had to use them in production.

Since I am developing UnoDB as a library which could be used in an exception-using or exception ignoring codebase, I have to make it exception-safe. Now ever since reading Effective C++ series, I got the vague idea of being exception-safe as

• noexcept all the things that can be noexcept'ed
• RAII all the things
• for any non-trivial state, build it in a local variable and std::swap into place
• never throw from a destructor (I know it's technically not true, you just have to compare std::uncaught_exceptions values in the constructor and the destructor, if equal, fail away!)
• ???
• Profit!

See, the levels of exception safety guarantees (nothrow, basic, strong) do not even really enter the picture. Just try to do things in a safe way, and the result will be safe-ish.

And then this "safe-ish" code will break in subtle or not-subtle ways on the first actual exception thrown. I was ignoring this until Justinas casually mentioned while discussing something else: "to test exceptions, run a test in a loop with injecting std::bad_alloc on the 1st, 2nd, ... allocation, until the test succeeds." I noted this and some time later set off to work:

• Created an allocation_failure_injector class that maintains an allocation counter and throws std::bad_alloc on reaching a preset value, call it from the global operator new 
• Easy tests first: for non-memory allocating operations, wrap their tests in a must_not_allocate helper method that sets the failure injector to fail on the very first allocation, observe that it never happens
• Have a helper to do Justinas' loop
• In the state-changing potentially-failing test harness operations (such as ART test insert), catch any exception and assert that nothing in the observable state changed (i.e. node counter values). Look, we are going for the strong exception safety guarantee here!
• Make fuzzer tests inject and handle OOM too.

Both ART and QSBR were treated this way, and it did not take long for the "safe-ish" code to show serious bugs:

• QSBR would leak memory, bump counters prematurely, and generally end up in inconsistent states (one, two, three), including a fuzzer-found bug that was non-deterministic due to unpredictable C++ standard library allocation count
• In the case of growing/shrinking an ART tree node, if the allocation of the new node failed, the old existing node would still get reclaimed. Yikes.

As a result, the code is no longer exception "safe-ish", but actually safe to some actual level with respect to std::bad_alloc. There are other exceptions that might be thrown, but I couldn't think of any reasonable not-immediately-fatal way to handle std::mutex::lock throwing std::system_error.

As I was writing above I noticed that half of the commit messages say "crash safety" instead of "exception safety." At least I haven't found "exception isolation levels" or the rest of ACID in my commit messages yet.

UnoDB ported to MSVC

I have ported UnoDB to Microsoft Visual Studio, the third major C++ compiler. The other two, GCC and clang, are reasonably close to each other, while MSVC likes to do its own thing, not only due to different runtime platform, but also because of a different C++ standard interpretation in the compiler and library. MSVC 6.0 (the Internet Explorer 6.0 of C++ compilers, don't try to use the C++98 standard library there) was the first compiler I used in my professional C++ work two decades ago. Luckily 6.0 is not the current version, and Microsoft tried to clean up its act with respect to standard C++ since (not fully – why std::exception::what() is not noexcept?) So, the port forced to write more, uhm, portable code. Most GCC and clang-specific compiler extensions and builtins mapped straightforwardly to MSVC ones, and a few that didn't could be #ifdef'ed away trivially. There was only one incompatible API call – posix_memalign – which mapped to _aligned_malloc trivially too. Then the port pointed out actual bugs in my assumptions, mostly in the standard library use:

• Do not assume that std::array::iterator is a raw pointer - it can be anything that satisfies C++ iterator requirements.
• Do not instantiate std::uniform_int_distribution with std::uint8_t - the distribution only supports integral types while uint8_t is of course a character type!
• Do not assume that different compilers will lay out the same structs the same in memory, even if architecture and field alignment requirements do not differ.

Besides the actual source code, I was most worried about CMake script compatibility. Turns out, MSVC and CMake work quite nicely together if one uses CMake presets, and porting the build scripts was relatively easy. 

At this point the basic port was completed with tests and benchmarks passing. Even though my main development platform is macOS and test/benchmark one is Linux, I wanted to do a first-class port that matches the existing platforms as much as possible and makes the most of MSVC features. For that, I did more work:

• CI. Github Actions has good Windows runner support. It was a bit alien to learn and write PowerShell script bits and not to revert to UNIX'isms, otherwise it works and runs great.
• Clean compiler diagnostics. I have enabled /W4 warning level and fixed a few unremarkable issues. I did have to add some CMake kludge to remove the default /W3. I am using CMake 3.12 and this issue has been fixed in 3.15.
• AddressSanitizer. It's very nice that MSVC has it, and it mostly works as expected. There are two open MSVC bugs though, so I am unable to fully test it in CI yet.
• clang/LLVM in MSVC. Now that's interesting – a clang compiler integrated with the rest of MSVC toolchain. For code, that required adding #ifdefs in the style of defined(_MSC_VER) && !defined (__clang__), which takes some time to get used to. For build system, things got even more interesting. There is a clang-cl.exe compiler driver that translates MSVC cl.exe command line options to clang ones internally. Which is great, except that there are a few cl.exe flags that do not have translations and cause errors, and that there are a few clang-style flags that have to passed together with cl.exe-style flags too. And then this whole one-toolchain-two-compilers business took CMake by surprise – I had to use incorrect-if-ever-ported-to-native-LLVM-on-windows CMake workarounds. CMake 3.14 introduces CMAKE_CXX_COMPILER_FRONTEND to address this. Anyway, this is also tested in CI.
• clang/LLVM in MSVC with AddressSanitizer. Yep, that's also a thing, but here I hit the wall of incompatible runtime libs and stopped.

But by far the biggest payoff in doing the port were the MSVC static analyzer fixes. The analyzer was a honorable mention in my static analyzer post and now that I can run it on my code, the results exceeded my expectations. It started innocently enough, a few trivial changes (and some more), a few new asserts added to help out data flow analysis. Similar to asserts, I added some assumptions – which are facts provided to compiler about variable values in release build too. (One of my previous experimental branches did the same - lock-free 128-bit atomic stats used assumptions to limit double values to 2^63 for integer conversion to avoid branching to the highest-bit-set case handling). Some code was de-duplicated, dead code was removed. Then it caused me to discover a typo, which invalidated many months of runs of Node48 and Node256 random get benchmarks. Luckily there were no code changes dependent on the affected benchmarks.

The static analyzer also checks for C++ Core Guidelines violations, and there is a slightly sad story there, of the "why we can't have nice things in C++" kind. To suppress violation diagnostics, MSVC provides a well-meaning gsl::suppress(x.1) attribute. To make suppressions portable, LLVM well-meaningly ported it but made the argument a string literal – gsl::suppress("x.1") – because that's what portability means! To make both compilers work, the Core Guidelines introduces a well-meaning GSL_SUPPRESS(x.1) macro. If it is present in the code, clang-format will insert a space after dot – GSL_SUPPRESS(x. 1) – breaking the compilation. There is no .clang-format option to stop this behavior, and so all the actual uses of this macro in the actual portable codebases look like this:

// clang-format off

GSL_SUPPRESS(f.4) // NO-FORMAT: attribute

// clang-format on

Where NO-FORMAT: attribute seems to be a thing to handle MSVC own formatter (?). Luckily, I could replace GSL suppressions with direct MSVC compiler suppressions, and that's a minor inconvenience in the big picture. 

All in all, I learned a lot by doing an MSVC port, working with Windows was a bit of a change of regular programming environment, and improved the code more than expected – not too bad.

Optimistic lock coupling overhead for single thread Adaptive Radix Tree

UnoDB has two Adaptive Radix Tree implementations: a regular one, which is not safe for concurrent use, and optimistic lock coupling one (OLC ART), which enables concurrency and, hopefully, scalability for reads, by having per-node seqlocks. When I set out to implement them both, one interesting question for me was how much overhead does OLC add in single-thread workloads, in other words - can OLC ART be used instead of ART even if concurrency is not needed?

To try to make the answer more meaningful I did a round of optimizations for the latter, with the biggest one being a rewrite of try_read_lock implementation to do a single comparison in the fast path instead of two. Two comparisons is what the pseudocode in the OLC ART paper does. I have also logged my first missed-optimization compiler bug. The changes did not result in dramatic improvements (the try_read_lock one reduced branch mispredictions by 25%) but every little bit helps.

So the current answer is - OLC makes things slower 2x-3x compared to the regular one, in my implementation. This is a rough mean/average of various benchmarks, which vary from ~10% overhead on random gets to 200%-300%-400% (even 600% once) for everything else. Drilling down into these numbers a bit, it's somewhat easy to explain the relatively good numbers for random gets - memory-bound execution, least changes in the OLC algorithm compared to the baseline one. The update algorithms, especially the delete one, are relatively heavy in locking operations. The delete might lock three nodes at once, with restart logic if any one of the three write locks fail. This, however, does not explain, why scans have as much overhead as updates, sharing the same algorithm as random gets.

Another elephant in the room in this comparison is direct heap allocation/deallocation for the regular case vs. Quiescent State-Based Reclamation (QSBR) for OLC. I see a lot of QSBR in the single-thread profiles and I cannot really optimize it, at this point, due to the implementation needing a full rewrite as it does not scale due to a Big QSBR Lock.

And that is the next fun thing to do. I did not find any lock-free QSBR implementation on the internet, so I guess I'll see about writing one.

C++ linters and static analysis tools I tried for UnoDB

I love C++ static analysis. I also like linters, and so will happily try away and integrate any reasonable tool out there into CI/CD for UnoDB. So, in the last three years I got to play with quite a few of them.

Let's start with the simplest of them all, the linters. While the simplest, they still vary in complexity, from regex check collections (cpplint) to LLVM-infrastructure-based ones (clang-tidy).

• cpplint. Good for having unified header guard style, "// namespace" comments at their ends, wrapping lines at 80 chars. It also tries to enforce Google C++ guidelines of 2012 (?) vintage, with less than impressive results: '<mutex> is an unapproved C++11 header'. OTOH, it integrates with Emacs through flycheck-google-cpplint, making it easy to keep the code compliant while it's being written.
• include-what-you-use. Cleans up #include directives. A great tool, must-have for C++ until modules take over, but some of the diagnostics suggest to include some internal header for a C++ standard symbol. As a result, it's somewhat labor-intensive to go through results and apply fixes.
• clang-tidy. A source-code linter with local code analysis. Enforced the Rule of 0-3-5 for me many times, helped with Almost Always Auto declarations (sorry Justinai), replaced v.size() == 0 with v.empty() etc. Overall, does not catch bugs, but helps to write better C++ idioms. Integrates with Emacs through clangd for instant feedback.

Next up, compiler warnings, GCC & clang. I went through the docs of both and enabled every reasonable non-default warning, but did not use clang's -Weverything, which is apparently not very reasonable. The warnings made me do several non-default-for-me things:

• All the small constants have U suffixes if used with unsigned variables. You don't do unsigned y = 1U, x = y << 3; you do y = 1U, x = y << 3U;
• GCC function attributes cold, pure, etc. were suggested and applied. But also there are in-line warning suppressions for false positives.
• GCC made me write a class template deduction guide once. I have looked into them before and am happy user of them when somebody else writes them, but as for actually writing one, I had thought hell will freeze over first. Yet, here we are.

Honorable omission: MSVC /W4.

Finally, the actual static analysis tools:

• Coverity. I couldn't get the damn thing ("Coverity Build Tool") to run, and believe me, I tried. Guess will check again in six months.
• cppcheck. (Hey, an actual project still hosted on SourceForge!) This one punches above its weight in that it's implements its own C++ parser, but has better diagnostics than one would expect from that. Sadly, "better" is not always "good enough." I added a tweak here & there in my code, but most of the time I add suppressions. I also managed to crash it once, unfortunately this means I found more bugs in cppcheck than it did in my code. I tried to report this bug, but the procedure is unfriendly for new reporters, to put it mildly. On the bright side, it is being actively developed and it recently got an LLVM-based parser, so I expect more good things out of it in the future.
• Compiler static analysis, GCC & clang. GCC static analyzer is very new, the clang one is a bit older but still not very complete, and so at this point it was more of integrating them into the pipeline, suppressing false positives, and waiting for the new versions to come out. Honorable omission: MSVC /ANALYZE.
• Sonatype Lift, called muse.dev originally and then acquired. Its developers were extremely helpful, popping up in my project to comment on false positives and "oh yeah we will fix this ASAP" remarks before I could even review my own run results. As for the actual checks, for C++ code the main backend is FBInfer. It produced several non-obvious-at-first diagnostics which were not false positives nonetheless and required thinking and refactoring to address, resulting in better code structure.
• Sonarcloud. This one tries to become the JIRA of everything by including test results, coverage results, and converting diagnostics to tasks. For the actual diagnostics, it has an opinion about everything ("never use std::unique_lock, always use std::lock_guard"), all that done in a web portal. I applied a lot of minor fixes to make this one happy - adding missing 'const', removing redundant template args, tightening class access specifiers, etc, etc, etc.

Omissions: PVS-Studio. Their licence for OSS used to be a rather strange one–requiring to add source code comments "This project is checked by PVS-Studio for free!", but I see it has changed since, and so I might try it next.

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.

Optimizing Adaptive Radix Tree Implementation for CPU

For a long time in my career I wanted to learn how to better optimize for the CPU. I was lucky enough to work in places where performance matters, however it was almost exclusively I/O performance, scalability, big-O, maybe an occasional memory access pattern issue-not quite the CPU itself.

So I took my Adaptive Radix Tree implementation, and wrote a bunch of isolating microbenchmarks for all the interesting code paths. Then I tried to see how can I make things faster, on a bare metal Sandy Bridge server (AVX instruction set, state of the art, I know). Some random things I learned (or re-confirmed for myself) in the process:

• ART, as a node-jumping tree structure, is cache miss-bound as sizes increase. Yet it is possible to do CPU work with L3/L2/L1D-fitting tree sizes.
• An "obviously faster" code change is not such frequently enough so that not re-measuring will bite you. The more "obvious", the more discipline is required to rerun the numbers. This point is beaten to death and yet never goes away.
• I couldn't really figure out the restrict keyword. I understand the theory behind it, yet when I put it in the code, surprises happen. Most of the time it perturbs code generation in a random insignificant direction. Including the cases when it should have been a no-op. It is not helping that it is absent from the C++ language, existing as a compiler extension only.
• Compiler generates different code for, say, unsigned vs uint8_t local variables whose all allowed values fit into uint8_t. It should be able to pick the optimal width itself, but it does not appear to do that.
• Well-predicted branching code appears to be faster than branchless code, which appears to be faster than poorly-predicted branching code. It might be easier to tell if some code is poorly-predicted than if some code is well-predicted.
• Some branchless code will trade conditional jumps for conditional data dependency chains (e.g. Intel CMOVcc), which is still an improvement, but less so.
• Looping is faster than recursing
• Sprinkling SIMD intrinsics in the code for not-quite-vector data is a thing, it is also a thing that the compiler is not likely to do for you. The smallest data amount which I saw to be processed faster in SIMD was four bytes (Node4 search in ART - exact same algorithm that the paper proposed for Node16 search, just narrower). It helps to view SIMD instructions not as something exclusively reserved for long vector loops, but as specific tools in the general purpose instruction set.
• Conversely, putting a bunch of bytes in a general-purpose register and treating them as a vector of independent bytes is also a thing, it even has a name: SWAR (SIMD within a register).