New project: IntMap implementation in C

So I’ve been hacking on a new project recently. It’s an implementation of “Fast Mergeable Integer Maps” (known to Haskell and Scala programmers as IntMap) in C. The implementation is available on Github under a 2-clause BSD license. I’ve not done any work on packaging it yet, mostly because I’ve no idea how to package a C library (I suspect the answer is something like sacrifice a goat to acquire knowledge of how autotools works).

It’s currently pretty minimal. The core of the API is there with support for lookup, insert, union and enumeration, but I’ve put some thought into how it looks and what’s there should be pretty stable in terms of keeping the same API around.

Developing it has been… interesting. It’s rather shaken my confidence in my ability to write non-trivial C programs, truth be told. I’ve made pretty much every mistake I possibly could have – it’s mostly been trivial stuff (using the wrong variable, getting checks the wrong way around, etc) with a few interesting things (getting pointer addition wrong due to incorrect pointer types), but my testing process has been full of segfaults.

In the end I’m pretty confident I’ve caught most of the bugs in it, due to the testing process I’ve adopted (more on that later), but I’m a little worried about the error density – C isn’t a language that is forgiving of programmer error and apparently I rely a lot more on that in my normal programming than I’d previously been aware. I think clearly if I want to be writing C code on a regular basis I’m going to have to up my testing game if nothing else.

Part of the problem here is that this library ends up emulating both garbage collection (through reference counting) and pattern matching (through unions and a type tag) in C, both of which are fiddly and error prone to do, and even in Haskell the algorithms used are conceptually clear but a little tricky to implement correctly. All this adds up to a pile of edge cases that are easy to get wrong, and apparently I wasn’t so good at not getting them wrong.

So I turned to my standard tool for getting data-structures correct when there are lots of fiddly edge cases: QuickCheck style testing. Initially I did this using python bindings to intmap and hypothesis. The problem with doing so I found was that  the result is really quite slow so it was difficult to get thorough enough coverage. This was especially so under valgrind (python it turns out does not run well under valgrind). I could have solved this the same way I did in pyjq by generating a C program for each test case, but it wasn’t going to interact well with hypothesis and doesn’t solve the slowness problem.

So what do? Well I thought about using quickcheck style testing in C – there is an existing C quickcheck implementation but frankly that sounds pretty hellish.

So I ended up with a different approach. Rather than generating random data I generate random programs which should all be valid uses of the library. The essential idea of it is to generate a collection of intmaps, with a parallel implementation in python that allows to determine what should be in them. This then allows us to test a wide variety of assertions based on what we know should be in there.

The generated programs aren’t pretty. Here’s an example. However even an individual one produces pretty good coverage, and randomly generating 1000 of them should be more than enough to find most bugs. I’m sure there are bits it misses (for example it’s not currently very good at testing all the branches of equality – it in principle can do so, but I think some of the edge cases are too low probability), and it’s not impossible that there are still some subtle ones lurking in there, but since writing this I’m an awful lot more confident about the quality of this code than I was before I wrote this program generator.

It’s currently still quite slow, but that’s because it’s doing a thousand runs of compiling 4000 line C programs (twice – one in debug, the other not) and running each of those programs (twice – once in valgrind, the other not). With all that work, it should hopefully be reasonably good at making up for my failings as a C programmer.

This entry was posted in Uncategorized on by .

One thought on “New project: IntMap implementation in C

  1. Pingback: Updates to intmap | David R. MacIver

Comments are closed.