Go small structs and interfaces

The normal rule of thumb is that if you have small structs, you should pass them by value, rather than by pointer.

So in gSuneido (the Go implementation of Suneido I'm working on) that's what I'm doing.

But I was thinking about the way interfaces work in Go. An interface can only hold a pointer. So if you do:

var i interface{} = x

and x is not a pointer, then x will be copied to the heap so that i can point to it.

Some simple cases avoid the allocation. For example, true, false, and empty string ("") can be assigned to an interface without causing allocation. Presumably because the runtime has a shared value it can point to.

Suneido is dynamically typed, so values are stored and passed around as Value interfaces. (The equivalent of an abstract base class in C++ or Java.)

Given this, does it still make sense to "pass" small structs by value? Or is that just going to cause heap allocation?

I made a quick benchmark.


And the results were:

BenchmarkSmallByValue     20.7 ns/op    16 B/op    1 allocs/op
BenchmarkSmallByPointer    2.09 ns/op    0 B/op    0 allocs/op

As expected, when we pass by value, we get a heap allocation every time, making it about 10 times slower. That's a bit misleading because the benchmark doesn't do any real work. e.g. if it was doing 500ns of work, then the comparison would be 520ns versus 502ns which is much less significant.

However, the allocation is more of a concern. Heap allocation has bigger, more widespread affects like garbage collection and cache pressure and memory bandwidth. These aren't always evident from a benchmark.

With these kinds of micro-benchmarks I'm always afraid the compiler has optimized away key parts of the code. But I used Compiler Explorer to look at the code generated, and it all seems to be there.

Somewhat surprisingly, I got the same results for a simple string rather than a struct - it's faster to pass a pointer to a string. Coming from C++ or Java, you think of a string as already being a pointer. But in Go it's more like a slice, i.e. it's actually a small struct containing a pointer and a length. Because it's a small struct, you normally pass it by value. But when you use interfaces, that means heap allocation (of the slice struct as well as the actual bytes of the content).

Unless I'm missing something, it seems like I should change gSuneido to use pointers for all values, even strings.

Partial Incremental Encoding

I have been thinking about how to improve Suneido's Btree implementation.

Btree's were initially designed for disk storage. But Suneido memory maps the indexes and generally Suneido database servers have enough memory that the indexes are resident. Would it make sense to use a different Btree design for in memory?

One possibility is to not store the keys in the Btree, since there's no extra disk access to access the data if it's in memory. That's more like how you'd design a normal in-memory data structure. And it makes the Btree nodes much smaller.
But memory is not flat these days, we have multiple levels of caches. And in relative terms, cache misses are almost as bad as disk accesses. So what we really want is to minimize cache misses.

So we have a design continuum. No keys makes the index small but will mean a lot of indirection and therefore cache misses. Entire keys means no indirection, but indexes are big.

My first thought was to compromise and store a small fixed portion of each key in the index. This keeps the index small, makes nodes fixed size, and reduces indirection.

bill	bi
billy	bi
erika	er
erin	er
erma	er

But ordered keys usually have common prefixes, so storing the first few bytes does not discriminate very well.

To handle that we can use prefix compression (aka incremental encoding or front compression)

bill	0, bill
billy	4, y
erika	0, erika
erin	3, n
erma	2, ma

Prefix compression means we have to linear scan each node (i.e. you can't do a binary search). But Btree nodes are reasonably small and linear is actually the optimal access pattern for memory caches.

We can combine these techniques by only including the minimum information to differentiate each key from its predecessor.

bill	0, b
billy	4, y
erika	0, e
erin	3, n
erma	2, m

Interestingly, this looks a lot like a radix tree, branching on a single character.

This nicely handles both dense (e.g. sequential values) and sparse (widely separated) distributions of keys. However, it does have a worst case - when we go from a sparse key (small common prefix) to a dense key (large common prefix) (e.g. bill to billy or erika to erin) we need more information than we have in the index. One option is indirection to look at the actual data. That's ok if it's rare, but not so good if it's common.

If we give up the fixed length idea (which is not as important for linear scan anyway) then we can store the extra information necessary for this case (the missing prefix information)

bill	0, b
billy	4, illy
erika	0, e
erin	3, rin
erma	2, m

With this, only one indirection is required at the end of each search to compare the key to the actual data.

In my test data I averaged less than 1.1 bytes per entry. (Although obviously it can be more, as in this example.)

To search, we iterate sequentially, maintaining the known prefix after each entry, and comparing that to what you're looking for. Because we only have partial information, we may search one entry too far. e.g. if we're looking for "earl" we should stop at "erika", but since all we have for "erika" is "e", we'll look one past.

key	entry	known
bill	0, b	b
billy	4, illy	billy
erika	0, e	e
erin	3, rin	erin
erma	2, m	erm

Inserting and deleting affect the encoding of the following values so you need to re-encode entries until you're back in sync. (e.g. hit a 0 entry) This requires looking at the actual data, but it's only for updates, and typically not that many entries.

I've prototyped the design and it seems to perform reasonably but I haven't implemented enough to actually benchmark it against Suneido's current implementation (which stores entire uncompressed keys).

Part of what triggered this was Design continuums and the path toward self-designing key-value stores that know and learn 

Scala Native & More

I recently discovered Scala Native, a version of Scala that compiles to a native executable rather than running on the JVM like the original Scala. (via Modern Systems Programming with Scala Native)

Scala is an attractive language. Scala is to Java as C++ is to C. Meaning it's much more complex. (Scala promotes its simple syntax, but that doesn't mean it's a simple language.)

In some ways I like Kotlin better than Scala. It seems to give a lot of the advantages of Scala, without Scala's complexity. And there are non-JVM versions of Kotlin. But the problem is that Kotlin relies on the Java libraries, which is a portability problem for the non-JVM versions. Whereas, one of the strengths of Scala is its libraries (e.g. collections).

Libraries bring up an interesting issue. To write good libraries seems to require more features and complexity than application code. A lot of the complexity of C++ is to enable writing good libraries, and I suspect the same is true of Scala. The other alternative is the Go approach. Go has a built in "map" collection. You can't write map in the Go language. If you want a slightly different style of map, what you can write in Go is nothing like the built in one. This is at the heart of the Go generics struggle. On one hand, you want to be able to write your own map in Go. On the other hand, you want to keep Go's simplicity and not end up with another C++.

Another factor is that people seem to like complexity, regardless of whether it's counter-productive, myself included, sadly. Languages like C++ are fascinating. There's always something more you can learn. Whereas simpler languages like Go are vaguely disappointing in that respect. I love how the C++ folks gleefully pile complexity on top of glittering complexity. But when it comes time to actually get some work done ... then maybe you want something simpler. (Especially when the wondrous pyramid is built on unsafe ground.)

Complexity also tends to affect build times. C++ and Scala are both known for slow compiles, whereas Go is extremely fast.

Unfortunately, from what I can see of Scala Native it's not very mature. It's currently using the a conservative Boehm garbage collector. That's what I use in cSuneido and from experience I know the weaknesses of conservative garbage collection. It's definitely not as strong as the JVM garbage collector. But they are working on a new garbage collector. Go (and Mono) also started out weak in this area but improved greatly. I can't tell whether Scala Native has the same libraries (e.g. collections) as regular Scala. The libraries are (mostly?) written in Scala so I would hope they would be portable.

Scala Native also appears to be weak in the concurrency area, which seems like a fatal flaw in today's multi-core world.

One feature mentioned on the web site is that Scala Native provides access to malloc and realloc. While this might appear attractive to C programmers, it seems a little odd in a garbage collected language. It also allows you to explicitly allocate data on the stack (like alloca). I'd much rather have escape analysis (like Go) that does that automatically. (I did see a mention that they are working on escape analysis.)

I'm not sure if it's indicative of the project as a whole, but the PragProg book seems focused on writing unsafe C code in Scala syntax. Personally, I have no desire to go back to the days of buffer overflows and mysterious crashes from dangling pointers and memory access violations. It might give higher performance, but I suspect you'd get similar performance from writing it in safe Go.

It's an interesting project that I plan to keep an eye on, but I don't think it's ready for my use yet.

Dependencies

I've always been reluctant to take on third party dependencies in my projects. I do it, but not lightly, and preferably not often. I could justifiably be criticized for regularly reinventing the wheel. On the other hand, I've seen and experienced things like DLL version hell on Windows.

The web arena goes to the other extreme of embracing dependencies. You seemingly can't write a web page without multiple frameworks and libraries du jour.  I'm always horrified when I install a Node package and it installs hundreds of dependencies. It seems like asking for problems, although somehow it seems to work almost all of the time.

Dependencies also tend to add to bloat. Code intended for reuse has to satisfy many people's needs. Which means it has a lot of features that you don't need. Compilers and other tools can often strip out some of the unused code. But features that are interwoven into the code (e.g. extra fields in a data structure) are not easily stripped out. Often, the 80-20 rule applies and you can get what you need with a small fraction of the code of a general purpose library.

Complexity is the other side of bloat. Do you really understand that third party library? What are its performance characteristics? How does it handle errors? What algorithms is it using? What are the weaknesses? The documentation may cover some of that, but it's more likely to just tell you how to use it. None of that may be relevant at first, but eventually it probably will.

Longevity is another big factor. A dependency that isn't maintained over the long term sooner or later becomes a liability. Yet major long term projects don't seem to be worried about taking on dependencies that are maintained by one person in their spare time.

Errors are another issue. I can fix errors in my own code. Errors in third party code are not so simple. You can submit a bug report and wait, hoping that it might get fixed eventually. Or you can try to figure out the code, and if you can comprehend it, do your own patch or fork. But if it's a big complex code base, that's usually not feasible.

You can't escape dependencies - operating systems, languages, databases, etc. are all dependencies. But you can think about the costs and risks as well as the benefits

Here's a good discussion of dependencies from Russ Cox, one of the core Go language team. (the post is not Go specific) Fairly long, but worth reading.

https://research.swtch.com/deps

Precedence Climbing Expression Parsing

Both cSuneido (original C++ implementation) and jSuneido (newer Java implementation) use classic recursive descent parsers. And that's what I implemented once again with gSuneido (in progress Go implementation).

But classic recursive descent is ugly for expressions, especially when you have lots of levels of precedence (because Suneido followed the C/C++ pattern). The code is verbose because there is a function for every level of precedence. And it's slow because during parsing you have to call through all those functions. For example, an expression consisting of a single identifier requires passing through 15 levels of precedence.

I've been aware of top down operator parsing (TDOP) aka Pratt parsing for a while (see my previous blog post). And more recently I came across precedence climbing which is basically a simplified version of TDOP.  I started and one of my programmers finished (thanks Hao!) a TDOP parser for the Suneido language, written in the Suneido language. We use it, for example, for search and replace by expression.

But I had always found TDOP somewhat hard to follow. The original Pratt paper is not the clearest. Crockford's version is better but still uses Pratt's cryptic "nud" (null denotation) and "led" (left denotation) terminology.

Recently I read Writing An Interpreter In Go and Writing A Compiler In Go by Thorsten Ball. (recommended, although I found myself skipping over the masses of test code) They use a TDOP parser, with the less opaque terminology of "prefix" instead of "nud" and "infix" instead of "led".

The main advantage of TDOP is that it is modular and easily extendible. But I had a more or less fixed target. So I decided to try rewriting the gSuneido expression parser using precedence climbing instead. (gSuneido is a good place to try out ideas because it's not in production and I don't have to worry about breaking anything.)

The basics are easy. It took a bit of experimentation to get things like assignment operators and ?: working but it wasn't too bad.

One thing that puzzles me is that assignment is normally thought of as the lowest precedence. But I had to make it the highest precedence in order to get things like "false is x = f()" to work. In my old classic recursive descent implementation assignment was high precedence as well.

With my classic recursive descent, it was hard coded into the parser that only certain expressions (lvalues e.g. x or v[0] or a.b.c) were allowed on the left of an assignment (or ++ or --). But that wasn't the case with this version so I had to add checking for that.

The end result (initial version or latest) is smaller than the old code, and runs quite a bit faster. In some ways it's not as clear, for example, figuring out how the minimum precedence argument works. But in other ways it's clearer, for example, there's an explicit precedence table (instead of the order of recursive calls). However, I'm not sure if it's enough better to warrant going back and changing the cSuneido or jSuneido versions.

The parallels between precedence climbing and TDOP are easy to see in the code. The pcExpr method has a switch with the led/infix handling, and the atom method has a switch with the nud/prefix handling. It would be easy to refactor to a table driven style (like Pratt) or an object oriented style (like Crockford). I didn't do this because it would have made the code slower (due to the indirect function calls) and larger.

References:
Top Down Operator Precedence, Vaughan Pratt
Top Down Operator Precedence, Douglas Crockford
Parsing Expressions by Recursive Descent, Theodore Norvell
From Precedence Climbing to Pratt Parsing, Theodore Norvell
Parsing expressions by precedence climbing, Eli Bendersky
Pratt Parsers: Expression Parsing Made Easy, Bob Nystrom

A Better Hash Table

Reading A new fast hash table in response to Google’s new fast hash table got me thinking about hash tables again. I wrote an implementation of his last hash table design back in January. It worked well, but memory usage was higher than I would like, and this new design promised to improve that.

However, this time he didn't explain the design, just shared the code. So it took me a little bit to figure out exactly how it worked. The basics are straightforward but there are a few tricky parts.

The data layout is the same as my last version - a flat array of blocks, each holding separate small arrays (e.g. 8 entries) for keys, data, and control information. The advantage of this layout is that it prevents wasting space for padding, while still maintaining locality. It can also be allocated with a single request.

This hash table is chained (i.e. collisions are handled with a linked list) but using empty slots rather than separate allocations. And the chains are not linked with a pointer or an index, but with an index into a set of jump sizes. So we can't link to an arbitrary slot, but only to a particular set of slots relative to the origin. In practice this seems sufficient.

Simple open addressing (e.g. linear probing) ends up with "chains" (probe sequences) containing different hash indexes. This leads to longer searches. We could do something similar, but it's better if we ensure that the chain starting at a certain index only contains entries with that same hash index. That means if you want to insert and the slot is part of another chain then you have to move the other chain from that point on. (If the chains were actual linked lists, you could just move the one element and then link to the rest of the chain. But since we only support certain specific jumps, we can't do that in the general case. And so we need to move the entire rest of the chain.)

I also used Fibonacci hashing which adds an additional hashing step to spread out values more than mod would.

Here's an illustration of how it works. For simplicity I'll use numeric keys and use of hash index of the first (tens) digit (without the additional Fibonacci hashing).

Inserting non-colliding elements is simple.

If we insert a colliding element, we "chain" it.

The chaining might have to skip occupied slots. If we insert 11, 12, and 31 we'd get:

Note: Chaining starts out looking like linear probing but when the chain gets longer the jumps get larger. 

Note: 10 and 30 are "direct hits", whereas 11, 12, and 31 are "chain" slots. We use one bit of the meta data to record this.

When we insert 20 we find its slot is used for a chain so we move the chain from that point on (11,12) so we can insert 20 where it "belongs".

This allows lookups to take advantage of the direct/chain distinction. If we look for 60 we find a chain slot (11) and we know immediately that it's not in the table. Whereas, if we look for 15 (same hash as 10,11,12), we find a direct slot so then we need to follow the chain to determine if the value is present.

When we delete an item from anywhere but the end of the chain, we move the end of the chain into the deleted item's slot, shortening the chain by one without moving all the elements. So if we delete 10 we get:

Note: Deleting 20 would not undo the chain move that was done when we inserted 20. 

I started with a Go implementation, although I'll probably port it to C++ as well. The initial version of the code is on Github.

After some tweaking, the performance is about 10% faster than the previous version, which is not huge, but considering the previous version was very fast, that's not bad. The best part is that it used about half as much memory - exactly the benefit that was promised.

Bit Twiddling

A while ago I wrote a new decimal floating point implementation when I was looking into a Go implementation of Suneido. The original cSuneido (C++) implementation is ok, but it definitely could be better. I ported the Go implementation to jSuneido (Java) but never got around to porting it to cSuneido, and never ended up putting it into production. I did port it to suneido.js (JavaScript) although that was harder because JavaScript doesn't have integers, let alone 64 bit ones. All it has are floating point numbers which you can use as integers but you only get 53 bits of precision. And the bitwise operations are only 32 bit.

Anyway, I decided to port the implementation to C++. Go and C++ aren't that different for this kind of code so it should have been a simple project. But, of course, I couldn't get into the code without thinking of improvements.

One thing I discovered was that although C++ has 64 bit integers, and CPU's are 64 bit, 32 bit programs (like cSuneido) don't have access to 64 bit instructions :-( On Visual C++ most of the operations turn into calls to runtime routines. (Comparison is inline but still multiple instructions.) One of the drawbacks to going 64 bit is that pointers double in size which can make programs larger and slower. (Even Knuth complained about this) Linux has an x32 mode which uses 32 bit pointers but runs with the 64 bit instruction set. But as far as I know there's nothing comparable on Windows or OS X. (If you're an old timer like me, you may remember the variety of memory models available related to the transition from 16 bit to 32 bit and breaking the 640k limit.)

The first area where I could see room for improvement was "shifting". Sometimes you want the 64 bit coefficient minimized / shifted to the right, so there are no trailing (decimal) zeroes. Other times you want it maximized / shifted to the left so there is a digit in the most significant position. In the Go version I had simple iterative routines that multiplied or divided by 10 repeatedly (up to 20 times).

My first thought was that you could use the number of leading or trailing zero bits to at least estimate how much you had to multiply/divide. When dividing you can use the factor of 2 in 10. i.e. if you have no trailing zero bits, then you know it's not evenly divisible by 10. And if you have 3 trailing zero bits then you might be able to divide evenly by up to 1000. I combined that with a kind of a binary search to take larger steps initially.

I had a harder time with the leading bits. 3 leading zero bits means you can multiply by 8. 4 leading zero bits meaning you can multiply by 16. From that I drew the incorrect conclusion that 4 leading zeroes were required to allow multiplying by 10. It took me way too long to discover my mistake. For example, with 8 bit values, 16 only has three leading zero bits, but 16 * 10 = 160 which safely fits within the maximum 8 bit value of 255.

Eventually I realized what I needed was integer log 10. That can be calculated efficiently using the number of leading zero bits (see Hacker's Delight). Which in turn can be calculated efficiently using compiler intrinsics like _BitScanReverse (Visual C++) or __builtin_clzll (GCC).

I was also wrong in assuming I could improve the division implementation. I thought maybe I could use double floats to do the division but converting back and forth isn't easy. I looked into division by reciprocals calculated by Newton Raphson. And I looked into Goldschmidt. But none of them seemed better than simple long division. Long division is normally slow because you only calculate one digit of the quotient per iteration. But if the divisor is less than the full 64 bit precision (the normal case), then you can get a bunch of digits per iteration. For example, the first iteration of 1/3 calculates 1e19 / 3 which gives 19 digits of precision in one iteration. Another trick I found, was that even if the divisor has full precision, after a few iterations you can reduce the precision (and therefore the iterations) without losing precision in the result. (although I have no formal proof of that)

In comparison, multiplication should be easy - just split the numbers into "halves" and calculate partial products and add them up. But, as the saying goes, the devil is in the details. The first problem is that 19 digits doesn't divide evenly into halves. One approach is to drop one digit and split 9 - 9, but then you lose precision. You could split into three parts, but that adds a bunch of extra multiplies and adds. Unfortunately, 10 digits * 10 digits can overflow 64 bits. But 10 digits * 9 digits is safe, so I realized I could split one of the numbers 10-9 and the other 9-9. The asymmetry complicates the code a little, but gives a bit more precision. Then I realized I could split one 10-9 and the other 9-10. That does lead to one of the partial products being 10 digits * 10 digits, but you only need the most significant digits of the result so you can reduce it to 9 * 9 without losing precision.

The other trick to getting as much precision as possible is that if high * high is less than full precision, then you can use an additional digit of precision from the middle partial products. And then you can use the high digit from low * low.

Getting this all working was way more of a struggle than it should have been. I spent a lot of time staring at 19 digit numbers and trying to figure out why the results were wrong in the last few digits.

Along the way I discovered there were several bugs in the Go implementation. Which isn't surprising considering it was never used. But I obviously need better test cases.

One option I haven't explored is using "magic" numbers to replace division (e.g. by 10) with multiplication and shifting. GCC and Clang compilers do this automatically, Visual C++ does not. However they don't appear to do it in 32 bit code for 64 bit values. (Tip - you can use Compiler Explorer to see/get the magic numbers.)

When I'm debugging this kind of code, I often end up writing it with each sub-expression computed separately and assigned to a separate variable. (reminiscent of SSA) This makes it clearer in the debugger what all the intermediate values are. Unfortunately, it makes the code harder to read so I usually remove it once the code is working. Of course, then I find a new bug and wish I had it back. It would be nice if there were refactoring tools to easily switch between the two forms. Or if the debugger would automatically capture and display the intermediate results.

I also tend to add a bunch of debugging output to print all these intermediate results, which I also usually end up wishing I had soon after removing it. It would be nice if IDE's could toggle showing or hiding this debugging code.

Some tools I find useful for this kind of work:

Hacker's Delight - a great resource. Most of the material can be found on-line these days, but you have to search through a lot of junk to find it.

WolframAlpha - great for things like 2^64 - 1 or multiplying two 20 digit numbers, or converting between number bases. There are other ways to do this stuff, but I find Alpha the easiest. I've often wished I was a Mathematica whiz, but other than bit twiddling I'm not really into math these days.

Compiler Explorer - handy for getting an idea how different compilers translate your code

Big Integer Calculator - not as powerful as WolframAlpha but simpler for e.g. truncating integer division

Small Size Data Structure Optimization

The usual approach for a expandable "vector" data structure is to use a dynamically allocated array that doubles in size as necessary. That's how C++ std::vector and Java ArrayList and Go slice/append work.

But that means the time and space overhead of a heap allocation. And it means indirection and poor locality for CPU caches. (The array itself is contiguous, but you have to chase a pointer to get to it.)

If you have a lot of small lists, one possible optimization is to "embed" a small array inside the list structure. That's not really feasible in Java, but easily done in C++ or Go. One example of this is the small string optimization (SSO) in C++.

But what happens when you grow beyond that small embedded array? The simplest solution is to just stop using it. But that seems wasteful, both in space and in locality.

Another option is to treat the embedded array as the start of the larger overall array, at the cost of complicating the indexing a little. That fixes the space wastage, but we still don't get much benefit from locality since the additions to a vector go at the end.

What if we treat the embedded array as following the used elements of the larger dynamically allocated array? Additions go into the embedded array until it fills up, and then we spill the contents into the larger dynamically allocated array.

If the embedded array holds e.g. 4 elements, then 3/4 of the adds only access the embedded array with good locality. Every 4th addition will block move the entire contents of the embedded array (4 elements) into the larger dynamic array (which will occasionally double in size). So the embedded array acts as a "buffer".

Merge trees and buffered Btrees have a somewhat similar pattern in that most of the activity takes place in a small area which periodically spills into the rest of the data structure.

I did some quick benchmarking using Go. My initial result was that it was slightly slower, but did about half as many allocations (because of the embedded small array). The speed was a little disappointing, but I was comparing against a simple Go slice append so my code was admittedly more complex.

Of course, the locality part of it is harder to measure. A small test that fits entirely in cache will not benefit much from locality. Sure enough, if I made the test create many more vectors, then the new version beat a simple Go slice append by about 30%.

The allocation advantage is entirely dependent on how big the vectors are. If they are small enough to fit in the embedded array, then there are zero allocations. If the vectors are very large then the number of allocations approaches the same as the slice append. Of course, the whole reason for the embedded array is that you have a lot of little objects.

One drawback of the embedded array is that it makes the data structure larger. A vector can be as small as a pointer and two integers or pointers which is reasonable to pass by value. Once you add an embedded array, you probably don't want to pass it by value or store it by value in other vectors or maps. If that means you have to allocate it on the heap, then you won't get as much advantage. However, it you're using it locally or embedding it in a larger data structure then it's fine.

A Tale of Two Hash Tables

For some reason I started thinking about hash tables again. I realize only a geek would think so, but I find them pretty cool. How can you not like a data structure whose lookup time is O(1) i.e. independent of size. The other fascinating part is that there are a huge number of different designs for hash tables, each with its own set of tradeoffs.

To beat the critics to the punch ... Did I have a pressing problem that I needed to solve? Nope. Did I benchmark the old code or the new code? Nope. Would it make more sense to just use std::unordered_map and quit reinventing the wheel? Probably. Was it a fun challenge that would give incremental improvements? I think so. I could say it's because I'm semi-retired and can afford to mess around. But I've been doing it all along. What's Suneido but the biggest example of reinventing the wheel. Right or wrong, it’s what I enjoy and the way I roll, and I think it’s worked out pretty well. I try not to take it too far . Originally I wrote my own garbage collectors for cSuneido. I'm not talking about yet-another-reference-counting-class, this was a full blown conservative bit mapped garbage collector. A fun challenge and probably some of my best work. But when the obviously better Boehm collector came along I switched over and threw out my own version.

cSuneido uses a pretty standard traditional hash table design - an array of pointers to nodes with separate chaining for collisions. It has worked fine for 20 years. But it has some drawbacks - every insert requires an allocation, there's considerable space overhead (pointers, separately allocated blocks, padding), and all the indirection means it's not cache friendly.

The design of the Go hash table is quite interesting. It uses an array of buckets, each holding e.g. 8 entries. Within a bucket there are separate arrays for keys and values to eliminate padding. Although the initial buckets are allocated in one large array, overflow buckets are chained. It also caches the high byte of hashes to speed up searches.

I reimplemented the Go hash table when I was working on gSuneido. (I couldn't just use the built-in one because it doesn't allow arbitrary types for keys like Suneido needs.) At that point the Go one was written in C, nowadays it's written in Go (albeit unsafe).

So I thought I'd rewrite cSuneido's hash table using the Go design. It took me a day or two to code and debug and it worked well.

But I remembered an article I'd read with the provocative title of "I Wrote the Fastest Hashtable". It uses open addressing, linear probing, robin hood hashing, prime sizing, and a probe limit. One drawback was that it was using a traditional array-of-structs model, which means wasted space for padding, especially since it includes a one byte value per slot which is pretty much guaranteed to get padded. But that issue is easy to overcome with an approach similar to the Go design, by storing the table in "blocks", and within each block using separate arrays for the keys and values (and the one byte "distance"). However, unlike the Go design, the table is still treated as a single large flat array. The tradeoff is that it slows down indexing slightly.

So I took another day or two and implemented this design. I love the simplicity of the lookup code:

int i = index_for_key(k);
for (int d = 0; d <= distance(i); ++d, ++i)
    if (HE::keyeq(k, key(i)))
        return i;
return -1;

You can't get much simpler than that. (Another nice feature of this design is that bounds checks are eliminated by adding extra slots on the end, which is feasible because of the probe limit.)

This design trades off slightly more expensive inserts and deletes for faster lookups. For the usual case of more lookups than updates, that's a good tradeoff. One negative aspect is that resizing the hash table will be slightly more expensive. But that's probably not a large factor because when you're growing a hash table, the new table is sparse and therefore collisions are less frequent.

One feature that makes me a little nervous is that the table grows if an insert exceeds the probe limit, with the probe limit set to log2(n). In most hash tables if all the keys hash to the same value you end up with a linear search. In this design the table would grow until you ran out of memory or hit a size limit. (hash table denial of service vulnerability). But in practice, the prime table sizes make it almost impossible for this to happen.

It took me a bit longer to debug than I expected with the simple code. The insert and delete are a little trickier with robin hood hashing because elements get moved around. C++ templates also gave me a bit of grief, as usual.

Testing with (pseudo) random values I got the expected good results:
- average probes for lookup was 1.3
- average load at resize was .75
- average swaps per insert was 1.3 (although max was 55!)

An average load at resize of .75 means the overall average load is .56 (half full). That's fairly typical for hash tables. It's the cost you pay for the performance. On the positive side, this design has only 1 byte of overhead per slot, and no overhead for pointers or padding or separate allocation, so it's better than many hash tables.

Here's a snapshot of the code. It'll end up in the cSuneido repo at some point. Note - it's not a full STL container since that requires a lot of extra code that I don't need. It also assumes that keys and values are simple objects (like integers or pointers) that are fast to assign and copy. See the article linked above for a more general purpose implementation.

A Bittersweet Triumph

I've been fascinated with the game of Go since I was young. As a kid I played a fair bit of chess, never seriously, but I could usually beat my peers. That was balanced by regularly getting thrashed by a 90 year old in my neighborhood that I was conscripted to play with. After I discovered Go I pretty much gave up on Chess. My business partner and I used to play a lot of Go in the early days of our company. It was a good way to occupy our time on business trips. We were never very good, and almost never played with anyone else, but it was a fun mental challenge. I still play regularly on my iPad against SmartGo Kifu and Crazy Stone (which claims to use deep learning), but only small 9x9 games. (and I'm still not any good!)

One of the things that attracted me to Go was that it wasn't amenable to the same techniques that were used in software to conquer Chess. Of course, I don't believe there is any magic in human brains, so presumably there was a way for computers to handle it. Until AlphaGo, most people believed it would be a long time, perhaps a decade, before computers could beat the best human players. So it was a bit of a shock to everyone when AlphaGo recently beat the worlds best human players.

I highly recommend the full length (90 min) documentary about AlphaGo - a Go playing computer program developed by DeepMind, a company owned by Google. (Don't be scared off by "AI". The documentary isn't technical, it's more about the people.) It's available on Netflix, iTunes, Google Play, and Amazon.



For more of the technical details, see the Nature articles. They're behind a paywall on the Nature web site, but they seem to be available on Scribd - Mastering the game of Go with deep neural networks and tree search and Mastering the game of Go without human knowledge

I've never been involved in AI, but it's always fascinated me. It was one of the original reasons I got into computers. In the early days there was a lot of hype about neural networks. But they didn't live up to their hype and there was a backlash that meant they were downplayed for many years. Recently they've seen a huge comeback and are now living up to much of those original hopes. Partly that's because of advances in hardware like GPU's.

The first AlphaGo was trained partly on human games. Its successor, AlphaGo Zero, learned completely on its own, by playing itself. It surpassed the earlier version in a matter of days. Not long after, the AlphaGo project was ended and the team was disbanded. I guess it's a done deal.

Concurrency Again

It started with long update transactions. Mostly we ignored them - some of our customers have slow servers, and sometimes they try to do transactions that are too large.

jSuneido aborts long update transactions as a defense mechanism. Its optimistic concurrency control has to track overlapping transactions, so if a transaction takes a long time, it can lead to a lot of overlaps.

But some of these long update transactions didn't make much sense. They appeared to be slow in the final commit stage. This stage just writes to the memory mapped files and normally is very fast, nowhere near the 20 second transaction limit.

I started going through the code, trying to see what might explain this. I wondered if it might have something to do with the background (once a minute) task that calls force on the MappedByteBuffers to flush them to external storage. Trying to ensure that files are durably written is tricky these days with so many levels of caching etc. but it seems worth trying.

I would have thought that force itself would be fast since most of the work would be done at the operating system level. But the documentation says that it doesn't return till it finishes writing to storage. I added some logging and found that force is usually fast (a millisecond) but occasionally slow (10's of seconds). There didn't seem to be a particular reason for the slow ones. I assume Windows is doing something that blocks.

The slow force would be enough to cause long update transactions, but force was supposed to be happening in a background thread so it shouldn't have blocked anything.

Crap! The force method was synchronized. And so was a method that transactions needed to use to commit. So the force would block the commit and could cause the problem. The problem was relatively rare because the force was only once a minute and usually fast, and it would have to hit exactly when a transaction was committing.

Did force really need to be synchronized? Did the other methods? Back to the age old problems of concurrency with shared memory and locking.

I removed the synchronized. But then I worried about accessing the array of MappedByteBuffers without any locking. I could make the array reference volatile but not the array elements. So I changed it to use AtomicReferenceArray.

At first I thought it was working ok. I ran tests with a bunch of threads hammering on the database and it seemed to work ok. But then my database got corrupted. Was my change failing? I ran the tests again and everything was fine. Hmmm. I changed the force to run every 10 seconds instead of every minute. Sure enough, now the database would get corrupted every time I ran the test.

It still didn't make sense to me that removing synchronized from force would corrupt the data. I noticed that my force method was also writing a few zeros to the end of the file to force the last modified date of the file to get updated. I could see that having concurrency issues. I changed it to rewrite the first few bytes of the file header instead. That fixed it, no more corruption. Hopefully it's smart enough to see that nothing has actually changed and not physically write to storage.

Everything looked good according to my tests, but that's generally not sufficient when it comes to concurrency. I also feel like I should convince myself that it is "safe", even if only informally.

Writing to the database (the final stage of an update transaction) was protected by a lock. So there could only be a single writer at a time. (Yes, that's a bottleneck, but it's a small part of the overall process so it doesn't reduce concurrency too much.)

But there are multiple reader threads. So the question is visibility, not exclusion. The Java Memory Model makes no guarantees of visibility without either volatile or locking. To ensure visibility I needed writers to release a lock when they were finished, and readers to acquire that same lock when they were starting.

For database transactions, that seemed to be covered. Transactions called synchronized methods (on the same object) at the beginning and end.

But there were other readers besides database transactions. The database checking process was one. It also turned out to be ok because it acquired the commit lock briefly at the start. (And writers released it at the end.)

That left the force process. Part of the problem was that it's low level code. It doesn't (and shouldn't) "know" about transactions or commit locks etc. I needed something at the same level. Luckily, writers called a particular low level method when they ended so I could synchronize that method along with the force method. Oops! Just about repeated the original mistake of force holding a lock while it was working. It didn't need to hold it since the goal wasn't exclusion. I just needed to acquire (and then release) the lock (to ensure visibility). So I made a dummy "sync" method that was synchronized and called that at the start of the force method.

I think I've convinced myself that it is "safe". I wouldn't say I'm one hundred percent sure, but reasonably confident.

Another question is fragility. Would future changes be likely to break this? Minor changes seem pretty safe. The things I'm depending on are reasonably fundamental. If I made bigger changes it could be dangerous, but presumably if I'm making bigger changes I would reconsider concurrency. And I did document it.

So if visibility and exclusion are covered, do I need to use an AtomicReferenceArray? Presumably not, so I reverted those changes and went back to a plain old array.

I did another round of testing on both OS X and Windows and didn't encounter any problems.

The problem with this kind of concurrency issue is that you can't just throw locks at it. The problems are just as likely to come from too many locks as from not enough. I wish you could just lock everything and be done with it. But if you do that, you'll probably have deadlocks, and you'll be back to single threaded performance.

Suneido Bind

In functional programming you have the idea of "partial application" of functions, where you supply some of the arguments to a function and the result is a new function that takes the remaining arguments. This is also referred to as "binding" some of the arguments, for example C++ std::bind.

We've had a version of this in Suneido for a long time, called "Curry". This is actually not the correct name, although it's related. Technically, currying f(a,b) would give you a function you could call as g(a)(b), where g(a) would give you a function you could call as h(b).

Suneido's Curry similarly allows you to supply some of the leading arguments, creating something you can call later with the remaining arguments. For example:

f = Curry(Print, 'hello')
f('world')
    => hello world

The code is fairly simple, using Suneido's variable number of argument facilities (similar to Javascript's spread and rest)

Recently, I was thinking that it would be nice if you could simply write: (like Scala)

f = Print('hello', _)

That would require compiler changes, but I realized I could do something similar to try out the idea:

f = Bind(Print, 'hello', Bind)

I needed something to stand for unsupplied arguments and using Bind itself seemed suitable.

To make it fast, I had the idea that I could generate a custom class. That sounds expensive, but you only need a class per "shape" of bind, not the particular values. And the classes could be cached. The code is a bit more complicated but not bad.



As hoped, the functions returned by Bind were faster than the ones from Curry, about four times faster. That was nice. And although Bind didn't handle variable numbers of arguments like Curry, it didn't require the supplied arguments to be at the beginning.

Of course, the other way to do this is using Suneido blocks (like closures or lambdas in other languages but with a syntax that came from Smalltalk):

f = {|b| Print('hello', b) }

It turned out that was slightly faster than my fancy new Bind. Which means we shouldn't be using Curry either since it's even slower. (jSuneido is even smart enough to see that's not actually a closure and optimize it to just be a normal function, avoiding the overhead of capturing the environment.)

It would still be nicer to write: Print('hello', _) but that could simply be syntactic sugar for the equivalent block. That wouldn't be too hard to implement in jSuneido since it compiles via an AST but it would be harder in cSuneido which compiles in a single pass directly from source to byte code.

Of course, if you had that, then it would also be nice to be able to write e.g. Map(2 * _) as a shorthand for: Map({|x| 2 * x })

Go Interfaces and Immediate Integers

One of the unique things about the Go language is how it handles "dynamic" references compared to a language like Java.

In Java we have:

Whereas in Go we have:

In Go an interface is a "fat pointer". Your first thought might be, six of one, half a dozen of the other. What difference does it make where you put the type. However, there are significant tradeoffs.

Next, you might think, I could have multiple references to the same value, in which case Go will use more space because it will duplicate the type. But if we have a large array of values (in which case we're unlikely to have references to all of them), then Go would save space because it wouldn't need the type on each value.

The other big saving is if you have statically (compile time) typed references in Go they will look like:

And again, you save space because there's no need to store the type at runtime.

Given that background, the problem I was thinking about was how to handle integers in a Go version of Suneido. In Java you have to used boxed (on the heap) integers for generic references.

Older versions of Go were perfect for this purpose since they stored integers right in the interface in the same place as the pointer.

But sadly (for me) when they improved the garbage collector they removed immediate values:

The implementation of interface values has been modified. In earlier releases, the interface contained a word that was either a pointer or a one-word scalar value, depending on the type of the concrete object stored. This implementation was problematical for the garbage collector, so as of 1.4 interface values always hold a pointer. In running programs, most interface values were pointers anyway, so the effect is minimal, but programs that store integers (for example) in interfaces will see more allocations.

So now if you store an integer in an interface it gets allocated on the heap, effectively "boxing" it like Java does, although with less overhead.

For something like implementing Suneido, this really sucks. It adds a huge amount of overhead (relatively) on simple integer operations.

You could make an "extra fat" value that had an interface and an integer, but that's ugly too.

In C++ you can use a union to handle immediate integers and that's what cSuneido does. But Go doesn't have unions in the C/C++ sense.

But the union in cSuneido basically reserves a portion of the address space for use by immediate integers. i.e. a pointer falling in that range of addresses is assumed to be and is treated as an integer.

So why not do something similar in Go. Here's my proof of concept:

var space [1024 * 1024 * 1024]int8
var base = uintptr(unsafe.Pointer(&space[0]))

func ExampleSmi() {
   n := 123456789   

   x := &space[n]
   i := uintptr(unsafe.Pointer(x)) - base
   fmt.Println(i)
   // Output:   

   // 123456789

}

It does use the unsafe package, but only in a read-only, relatively safe way. (IMO) Pointers will always point into valid memory so the garbage collector will be happy. And it should be fast since the unsafe functions are primarily a compile time feature, they don't do much at runtime.

This example handles 30 bit integers (1 gb). (Unsigned here, but easily modified to handle signed.) I tried to allocate a 4 gb array to handle 32 bit integers but the compiler appears to have a limit of 2 gb. (Note: 4gb is an insignificant portion of a 64 bit address space.) That's too bad because I could probably ignore overflow from math on 32 bit integers, but not 30 bit integers.

We want to declare the "space" statically so that "base" is a constant. One question I had was whether this would add 1gb to the executable. With Go 1.9 on OS X it doesn't. (It appears to go in SNOPTRBSS which I translate as "no pointer uninitialized/zero memory") My other question is whether it's smart enough to allocate zeroed virtual memory and avoid actually zeroing the memory. I'm not sure how to check this, but there doesn't seem to be any lag in startup. Also, looking at the process in the OS X Activity Monitor is shows real memory usage under 2mb.  Presumably if the virtual memory is never modified it will never use any real memory. Also, importantly, the array is of type int8 so it won't need to be scanned by the garbage collector.

Even better, we can make our own type based on int8 (e.g, type Smi int8) and then define methods on this type. As long as we don't make the Smi type public and are careful to only make instances within the array then it will work like any other type. We basically have the old behavior of Go, albeit with a smaller range of integers.

It's a bit of kludge but it should work quite well and it's all standard (albeit "unsafe") Go. And it's no worse than tagged pointers  or nan boxing.

[[nodiscard]]

I was reviewing some of my cSuneido C++ code and I noticed that I was ignoring the return value from a function, which meant that a variable might not be set. The function looked like:

bool int_if_num(int* pi);

I recalled reading about the new (C++17) [[nodiscard]] attribute which should catch this kind of error. I added the attribute to the function:

[[nodiscard]] bool int_if_num(int* pi);

I thought it was supported in Visual Studio but it turned out that it's "coming soon" in the next release.

But I also had Clang which does support it, and sure enough it caught the error:

error: ignoring return value of function declared with 'nodiscard' attribute

(I thought there might be more instances, but this was the only one.)

The nice thing about this kind of feature is that it's fine if it doesn't have universal support. I commonly compile with GCC and Clang in addition to Visual Studio because they each catch different issues.

[Afterward - reading the code more carefully, I found that I was initializing the variable prior to the call so it wasn't a problem after all. But that relied on the function not modifying the value unless it succeeded, which could change, and then there would be a problem. So it was still worth fixing the code.]

Eclipse Tip

I have become accustomed to seeing "change bars" in Visual Studio i.e. being able to see which lines have been changed but not committed to version control.

It seemed odd that Eclipse wouldn't have this feature so I went searching for it and sure enough it does, but strangely, it's disabled by default. It's also a little hard to find. It's not under Annotations or Team (version control). It's under Editor > Text Editors > Quick Diff, which makes sense, and you can get there easily by searching for "diff", as long as you know what to search for.

You want to check "Enable quick diff" and "Show differences in overview ruler" and "Git Revision" under "Use this reference source". (assuming you're using Git)

See also: stack overflow: Highlighting modified lines in Eclipse

Streaming Functional

Suneido has functional aspects like map and filter. They're not a major part of the language but they're definitely useful. However, it has always bothered me that they aren't "streaming". An operation like Map or Filter always generated a new collection. For small collections and many usages that works ok. Obviously it doesn't allow you to work with infinite streams but that's not a common requirement for our applications. But it's annoyingly inefficient if the desired result isn't a collection. e.g. If you end up joining the results into a string or writing them to a file.

I've thought about how I could change Suneido's functional methods to be streaming but it alway seemed like it would be a big change. When Java 8 introduced its streaming methods (for similar reasons) it was another reminder. However I didn't really like their approach - having to start by calling .stream and end by with some kind of collector. It makes sense and works well but it's verbose. One of the things I like about functional style is that it tends to be quite succinct.

The other day I was thinking about it again and I realized I might be closer than I thought, that Suneido might already have most of what I needed.

Early on in Suneido's development I'd face a similar problem with iterating over the members of an object. The Members method returned a new collection but that was wasteful if you just wanted to iterate. So I'd introduced "sequences" which could be iterated over without instantiating a new collection. Basically they just wrapped an iterator. However, they could also be treated as collections. If you called a collection method on them, they would instantiate the collection automatically. This meant a single method like Members could be used both to iterate lazily, and to generate a new collection, automatically and invisibly.

Later I added a Sequence function so that you could write these kinds of lazy sequences in user code. For example, we used it for a string lines method. But it never got used extensively.

My insight (as usual, obvious in hindsight) was that Sequence provided almost everything I needed to make the functional methods streaming. I simply rewrote Map and Filter as iterators and wrapped them in Sequence.

I wrote them as standalone functions, but also made them methods on collections. I prefer to write list.Filter(...).Map(...) than Map(Filter(list))

But I immediately ran into a problem. list.Filter(...).Map(...) worked, but it wasn't streaming. i.e. The result of Filter was still getting instantiated. The reason was that the sequence/iterator didn't have a Map method so it would instantiate the collection which did.

That was easy to fix, although it required a change to the runtime implementation of Sequence. There was no reason that you couldn't call user defined collection methods on sequences. It was only the built-in collection methods that required instantiation.

The next problem I ran into was that people were misusing Map purely for side effects. They should have been using Each instead. That was easy to fix, but somewhat tedious to examine every use of Map.

Then I found that Join would trigger an instantiation because it was a built-in collection method. So I added a built-in Join method on sequences.

I also found that laziness (as with these streams) and mutability don't play well together. I ended up needing to explicitly instantiate sequences in a few places because otherwise things would change out from under them. This is ugly and I'm not really happy with it, although thankfully it seems quite rare. But I could see it stumping someone who wasn't aware of how sequences work.

Being explicit about when to transition between collections and streams (like Java 8) avoids many of these issues, but doing it automatically fits better with Suneido's philosophy.

This project was a bit of a roller coaster (aren't they all?) alternating between thinking it was easy and I was done, with finding "fundamental" flaws without obvious solutions.  Unusually, even quite flawed implementations would handle most (simple) scenarios. It was the corner cases that gave me grief.

After hanging Suneido a few times I ended up adding a way to mark infinite sequences and refusing to instantiate them or display their contents. For fun I wrote a Primes infinite sequence.

Overall I'm pretty happy with how it turned out. I haven't done many benchmarks. I'm sure I can come up with scenarios where it will be a big win, but I doubt it'll make much difference in the larger picture.

One weakness is that Suneido doesn't have any easy way to write sequence operations. Currently they have to be written as iterators, which is ok for simple stuff but not very nice for things like tree traversals. Ideally you'd have some kind of "generators" with "yield". A project for another time!

Concurrency is Hard episode n+1

For almost a year a bug has been haunting me. Once every few thousand server startups, the server would hang. It wasn't totally frozen - the server monitor web page was still running and the server would still accept connections (but not service them). Simply restarting would fix it. There was no discernible pattern, customers got it at random and there didn't seem to be anything in common between them.

At first we wrote it off to bad hardware or server glitches. But it continued to happen a little too consistently for that to be the cause.

It was hard to pinpoint exactly when it started since we didn't pick up on it right away. But we knew the rough time frame. So I could look at version control and see what changes I'd made. But nothing seemed like it could cause it. I could have rolled back changes, but most of them were bug fixes so I wasn't keen to do that. And for all we knew it could have been a Windows update or a Java update or changes to the application code that triggered it.

Once we recognized we had a problem, my first thought was that it was some kind of deadlock during the startup sequence. No problem, Java has ThreadMXBean findDeadlockedThreads. It worked great when I forced deadlocks. I scheduled it to run five minutes after startup. It didn't find anything. I scheduled it to run every five minutes. Still didn't find anything. So either it wasn't a deadlock, or the deadlock detection wasn't working. In other words, no progress.

It seems terrible that we had this bug for almost a year. I did work on it, and many hours in total, but it was never really urgent. An individual customer might get it once every six months and they simply had to restart. So there wasn't a lot of external pressure to fix it. It certainly "bugged" me but with no clues it was hard to even know what to try.

I studied the code. I rewrote large sections. I ran the ThreadSafe static analysis tool on it. We added logging in numerous places.

We did stress testing to try and make it happen, although it's hard to "stress test" server startup. All we could do is repeatedly start and stop the server. Of course, it never happened when we did this.

What I really needed was to examine a hung system with a debugger (e.g. jvisualvm). But we only install a JRE on our customers servers, not the full JDK. If it happened consistently on one customer we could have installed the JDK on their server but it didn't. Towards the end I was starting to think about installing the JDK on all our customers. I would have been happy even to make the bug worse so it happened more frequently. At least then I'd have a chance of getting it under the microscope.

Looking at the Java documentation I found you could debug core dumps. So next time we got a chance to access a hung server, we forced a core dump. But we're using a launcher to run as a Windows service, and the launcher meant the debugging tools didn't recognize the core dump. So much for that idea.

One of the problems with Java's "synchronized" keyword is that you can't put any timeouts on it. So towards the end I was considering replacing all my uses of synchronized with explicit locks with timeouts. At least then deadlocks would time out and give me a clue where they were happening. In retrospect, this would have worked to locate where the problem was.

One of the problems was the slow turnaround. After making a change to jSuneido we would run it internally for at least a week. Then we'd roll it out to beta customers, and then finally to the rest of the customers. Then we had to wait for several days to see if the problem reoccured. So after each change I'd have to wait several weeks to see if it made a difference. Of course, there was nothing stopping me from continuing to work on the problem during this time, but the natural inclination was to want to wait and see if the change had worked.

One pattern we noticed was that it seemed to be related to requests to the HTTP server during startup. We weren't aware of that last time we stress tested so I thought it might be something to try. So I set up a server to restart every minute and arranged for a constant stream of HTTP requests. It ran all day without a hiccup. I normally shut down my computer at night. But that was only about 500 restarts, not really enough to have a good chance of detecting something that only happens every few thousand times. What the heck, I left it running overnight.

When I went to check it in the morning I had no expectation of finding anything other than it happily running. So it took me a minute of staring at the screen to realize it had hung! Eureka! Funny to be so excited about managing to hang your software!

I was almost afraid to touch it, for fear of disturbing the hung process. I fired up jvisualvm and did a thread dump. As I'd expected from the beginning, it was a deadlock. Two threads each owning a lock that the other wants.

And still the deadlock detection didn't show anything. I realized the reason was that one of the threads was not waiting on a lock, it was "parked" in Guava cache code. The code it was in was documented as "thread safe". As Inigo says in The Princess Bride, "You keep using that word. I do not think it means what you think it means."

I briefly entertained the (attractive) thought that the deadlock was in the Guava code and not my fault. That would have been nice, although harder to get fixed. But unfortunately it was quite obvious from the thread dump that it was my code that was at fault, despite the one thread being parked in Guava code.

The problem, and one of the lessons from this bug, is that code that calls a user supplied function is never truly thread safe because you can't control what that function does. That's also one of the problems with "functional" code, it is not amenable to static analysis.

In hindsight I realize that ThreadMXBean also has dumpAllThreads. I might have been able to write code to detect when the server hung and dumped the threads automatically. That would have given me the information I needed to solve this. Of course, I had no way to know that before now.

When I started rewriting Suneido from C++ to Java one of the big reasons was that we needed a multi-threaded server, and I thought Java had good concurrency support. But what it has is locks and shared state, which we've come to realize is not a great way to handle concurrency. Even back then I knew that, and I tried hard to minimize locking (which also helps performance) by keeping state thread contained and using immutable data. But I still used a certain amount of locking and concurrent data structures (which commonly use locking). And it's mostly worked out pretty well - jSuneido hasn't had a lot of concurrency problems. However, it's a bit like the lack of safety and garbage collection in C++, if you're careful you can get away with it, but sooner or later it's going to catch you.

Bug Tale

Yesterday, towards the end of the day, one of my staff came to me with a bug in cSuneido. Actually it was the second time he'd brought it to me. The first time I sent him away with a request for more details. This time he brought me a printed screen shot of the error. Perhaps that seemed more tangible.

Sometimes I get the impression that my staff gets a certain amount of secret enjoyment out of pointing out my bugs. Some of that's probably just my imagination and frustration. But even if it's true, it's understandable. They have to put up with me critiquing their code all the time.

I wasn't happy about it. It had been a busy day with the usual parade of interruptions. I didn't feel like I'd accomplished anything, and now this steaming turd had been deposited on my desk. I started to work on the bug, although I was pretty sure there wouldn't be enough time left in the day to get anywhere on it. The only advantage of starting late was that the interruptions had died out now that most people had left for the day.

On the positive side, the bug was repeatable. On the negative side it wasn't simple to reproduce - you had to run client-server, open our application, and then run a bunch of queries for over a minute. After thinking I'd fixed it several times I realized that it also only happened the first time you did this after starting the client. Subsequent runs worked fine.

The error itself was an access violation. The more I work in "safe" languages like Java or JavaScript or Go, the more I hate unsafe languages like C++. An access violation could be anything - a dangling pointer, a garbage collection issue, an uninitialized variable, an invalidated reference ...

On top of this, the error occurred inside a background fiber. Even better, it didn't occur when I ran the debug version of cSuneido.

As I expected, I didn't get anywhere before I headed home for the day, pissed off.

After supper I debated whether to work on it some more. If I could make a little progress, even just get a clue or narrow it down, then I'd end the day feeling a lot better. On the other hand, if I just ended up banging my head on the wall, I'd probably feel even worse.

I took the gamble, of course. Programmers are nothing if not eternal optimists. They have to be. But I hedged my bet by not "getting serious" and firing up the big iMac. I just sat in the living room with my laptop. That way if I failed I could tell myself it was because I'd just been poking around.

I didn't find the bug, but I did narrow it down enough that I felt I was hot on the trail. I could recreate the problem with a much simpler test case, and I'd found that I could recreate it in the debugger as long as I used the release build. It's harder to debug in the optimized version but being able to use the debugger at all was a big help.

It turned out the only significance of the queries running for over a minute was that during that minute several timer tasks got queued and ran concurrently when the queries ended. I could get the same result by just starting two fibers "at the same time".

Thankfully, the next day I was working at home and could focus on the problem. It was quite puzzling at first. I could see (in the debugger) exactly where the problem was, but the code looked correct, and almost all the time it worked correctly. I even resorted to looking at the assembly language and register contents, something I haven't done for a long time.

Stepping through the code I found there was a fiber context switch in the middle of the problem lines. And from looking at the assembler it was pretty obvious the compiler was caching the results of some common subexpressions, which it probably wasn't doing in the debug version. But I couldn't see how that caused a problem.

With fibers being cooperative and not pre-emptive, you don't really need to worry about concurrency issues. But this turned out to be a concurrency issue after all.

The problem lines were:

tls().thedbms = dbms_remote_async(server_ip);
tls().thedbms->auth(tok); 

tls() was getting evaluated and cached. But if dbms_remote_async "blocked" waiting to connect, then another fiber would run, and if that other fiber created a new fiber, and this caused the fibers vector to grow (reallocate), then the cached value of tls() would be invalid, causing the access violation.

Sure enough, if I called reserve on the vector to pre-grow it, then the problem went away.

It only happened the first time because after that the vector wouldn't need to grow and the tls() reference would stay valid.

I was grateful that the problem was so repeatable. If this had been real threads it would have been much more erratic. One of the advantages of fibers is that they are deterministic.

One local fix was to rewrite it as:

auto dbms = dbms_remote_async(server_ip);
tls().thedbms = dbms;
dbms->auth(tok); 

But where else in the code did I have this potential problem? And what would stop me from reintroducing the problem in future code.

My next thought was that I needed to tell the compiler that tls() was "volatile", i.e. it could change concurrently. But that wasn't really the problem. Even in single threaded code inserting into a vector invalidates any references, that's part of its contract.

One option was to use Windows fiber local storage. This didn't exist back when I rolled my own.

Another option was to dynamically allocate the tls structure so it didn't reside inside the vector.

However, there could potentially be other reference into the vector. I'd had problems with this in the past and "solved" them by using indexes into the vector rather than pointers. But it was still something I had to continually be on the lookout for.

Instead, I decided to switch from a vector to a simple fixed size static array. cSuneido isn't designed for huge numbers of fibers anyway. References into a fixed size static array were safe, nothing can invalidate them.

Problem solved (fingers crossed) and my mood has distinctly improved :-)

If you're interested in the nitty gritty, the change is on Github