Super Instructions

The overhead of an interpreter depends on the size of the instructions compared to the dispatching. So one of the ways to reduce the overhead is to increase the size of the instructions. One way to do that is “super instructions” - combining several instructions into one. This caught my interest and I decided to see whether it would help with Suneido. The Suneido byte code instructions themselves are mostly simple, which means a higher overhead, but most of the time is spent in built-in functions like database queries, which means a lower overhead.

The first step was to determine if there were combinations of instructions that were common enough to justify optimizing them. I added some quick temporary instrumentation to the interpreter. First I looked at sequences of two instructions. The most common accounted for roughly 7% of the instructions. The top 10 made up 40% of the instructions. That was actually higher than I expected. I also looked at sequences of 3 and 4 instructions. The most common was 3% so I decided to keep it simple and stick to 2 instruction sequences.

%	op1	op2
7.0	Load	Value
6.7	Value	CallMethNoNil
5.2	Value	Get
4.8	Load	Load
4.5	This	Value
2.7	Store	Pop
2.5	This	Load
2.3	Get	Value
2.2	Pop	Load
2.2	Global	CallFuncNoNil
40.1	Total

The compiler code generator funnels through a single emit function so it was easy to modify that to detect the sequences and replace them with combined instructions. And it was easy to add the new instructions to the interpreter itself. If I’d stopped there it would have been a quick and easy one day project. But, of course, I had to benchmark it. At first that went well. Micro benchmarks showed clear improvement as I expected. But running our application test suite showed a slight slowdown of 1 or 2%. That puzzled me.

One possibility was that it slowed down the compiler. Running the test suite requires compiling all the code. The changes did slow down the compiling slightly but compiling is fast enough that it doesn’t even show up in profiling. I optimized the code slightly but that wasn’t the problem.

That left the interpreter. gSuneido uses a giant switch to dispatch instructions. Go doesn’t allow some of the other dispatching methods you could use in e.g. C(++). I had added 10 cases to the switch. Did that slow it down? How did Go implement switches? Searches didn’t turn up a lot, but it sounded like it used a binary search. Running the code in the debugger confirmed this. Maybe adding more cases had added another level to the binary search? I tried rewriting the switch as a hand written binary search using if-else, optimized for the most frequent instructions. That quickly turned into an ugly mess. More searching found Go issue 5496 to implement switches with jump tables. The issue appeared to be completed. I used Compiler Explorer to test and sure enough, Go compiled dense integer switches as jump tables. But not my interpreter switch??? I tried simplifying the switch, ordering the cases, removing fallthrough, etc. But the debugger still showed a binary search. I found the implementation in the Go compiler source code. It seemed straightforward; there were no special requirements. I tried one of my simple examples from Compiler Explorer inside my gSuneido project. That didn't show as a jump table in the debugger either. What the heck!

Back to the Go compiler source code. There was a condition on base.Flag.N, what was that? Oh crap. That's the -N command line option that disables optimization, which is used by the debugger. So whenever I was using the debugger to look at the assembly language code, I was seeing the unoptimized version. A little digging and I figured out how to use gdb to disassemble the production code and found it had been using a jump table all along. Argh!

Back to the original question - why was it slower? Maybe the extra code in the interpreter was affecting inlining? I looked at the compiler inlining logging but everything still seemed to be getting inlined correctly.

Looking at the cpu profile, the interpreter time decreased as I'd expect. The only noticeable increase was in garbage collector time. But the changes don't do any allocation. They would actually decrease the size of compiled code slightly. The allocation from the test suite was slightly higher. But the memory profile didn't show anything.

In the end, I gave up. I can't figure out why the overall test suite seems slightly slower. There doesn't seem to be any evidence that it's a result of the changes. Everything else shows an improvement so I'm going to keep it. I can only guess that the slowdown is a result of perturbing the code, affecting layout, or caching, or branch prediction, or timing. Modern cpu's are so complex that they are somewhat non-deterministic.

Code is in Github as usual.

String Allocation Optimization

This post follows on from the previous one. (Go Interface Allocation) After realizing the allocation from assigning strings to interfaces (common in gSuneido) I started thinking about how this could be improved. I had a few ideas:

• predefine all 256 one byte strings (common when looping over a string by character)
• implement a "small string" type (i.e. a one byte size and 15 byte array in 16 bytes, the same space as a Go string pointer + size)
• intern certain strings with the new Go unique package (unique.Make returns a Handle which is a pointer so it could be stored in an interface without allocation)

Unfortunately, the last two require introducing new string types. That's feasible (gSuneido already has an additional SuConcat string type to optimize concatenation) but it would take some work.

Luckily the first idea was easy and didn't require a new string type.

func SuStr1(s string) Value {
    if len(s) == 1 {
        return SuStr1s[s[0]]
    }
    return SuStr(s)
}

var SuStr1s = [256]Value{
    SuStr("\x00"), SuStr("\x01"), SuStr("\x02"), SuStr("\x03"),
    ...
    SuStr("\xfc"), SuStr("\xfd"), SuStr("\xfe"), SuStr("\xff"),
}

It didn't make much difference overall but it was easy to see the improvements on specific types of code. For a simple change I think it was worth it. (Thanks to "AI" for auto-completing most of that 256 element array.)

See the commit on GitHub

Go Interface Allocation

I was running some benchmarks recently and I noticed the memory allocation was higher than I expected. After some investigation, I found it was an issue I was aware of, but that was easily overlooked.

The simplest Go "interface" is "any" aka "interface { }". This is a bit like void* in C or C++, except it has a runtime type. An interface is a fat pointer consisting of a pointer plus the runtime type (another pointer). You can store a pointer in an interface without any allocation. But if you store a value that isn't a pointer e.g. a struct, then it has to be on the heap, which usually means allocation.

The catch is that in Go there are quite a few fat pointers. It is a distinctive feature of Go. For example, a string value consists of a pointer and a length, and a slice consists of a pointer, a length, and a capacity. So even though mentally you might think of strings and slices as pointers, they don't fit in an interface. So storing a string in an interface allocates a copy of the string value (16 bytes) which in turn points to the actual data. (Also not ideal for locality.)

For example:

Even though this benchmark doesn't create any new values, it still allocates. If the type of X is changed from any to string, then there is no allocation.

There's not much you can do about this. In some cases you can use generics to avoid interfaces. But interfaces are a basic feature of Go, it's hard to avoid them totally. My point is just that if you're trying to write high performance code that minimizes allocation, watch out for interfaces.

See also: Go Interfaces and Immediate Integers

Keyword Recognition

Daniel Lemire's recent blog post Recognizing string prefixes with SIMD instructions and one he linked to Modern perfect hashing for strings prompted me to revisit how I was recognizing keywords in gSuneido. Although I find it interesting how you can use advanced processor instructions, I didn't really want to get into that. But like most things, even without looking at my code, I figured it could probably be improved.

I found that I was recognizing language keywords (28) with a linear search, sorted by frequency of occurrence. For query keywords I was using a Go map. Both were quite fast, certainly not a bottleneck.

The reason I hadn't used a Go map for language keywords was that I wanted to "intern" the strings. And there's no way to retrieve the key of a Go map (unless you loop through all of them). Normally it doesn't matter since you need the key to do a lookup in the first place. But the key I'm doing a lookup with is a slice from the source code. If I hold onto that key, it will keep the entire source code in memory (because the reference prevents garbage collection).

One of the first things I tried (Compile-time switches from the Modern article) was one of the fastest (4x faster than the old linear search) - switch on the length, and then switch on the i'th character (chosen for each length). For example:

switch len(s) {
case 2:
    switch s[1] {
    case 'f':
        if s == "if" {
            return tok.If, "if"
        }
    case 's':
        if s == "is" {
            return tok.Is, "is"
        }

I find it a little surprising that this turned out to be the fastest since it has quite a few branches - two switches plus a string comparison. Using Compiler Explorer to look at the assembler, I found the code was quite good. I was expecting a call to a string comparison function, but it is unrolled inline. It may actually be beneficial that the switches are explicit so each branch can get its own prediction.

Based on the assembler, I simplified the code. This was just as fast, smaller source code, and smaller machine code.

switch len(s) {
case 2:
    if s == "if" {
        return tok.If, "if"
    }
    if s == "is" {
        return tok.Is, "is"
    }

Because it was comparing constant strings and it knew the length matched, it compared them as multi-byte integers instead of strings. 2, 4, and 8 bytes matched int16, int32, and int64. For lengths of 3, 5, 6, and 7 it used a combination e.g. 6 characters was an int32 and an int16.

I did try various other approaches.

I tried finding "perfect" hash functions and table sizes, which turned out to be trickier than I thought. It was almost as fast as the switch version.

I tried another hash table implementation, but it was slower than the Go map.

I tried switching on the length and then doing a linear search.

In the end I went with the switch version since it was fastest. It was a little more verbose, but Tabnine handled most of the code generation.

Did this micro-optimization make any difference to the overall speed? No, not that I saw from a quick test. But it was an interesting investigation. And yes, premature optimization can be a mistake. But ignoring speed is also a mistake.

Regular Expression Implementation

This detour started with an out-of-memory error, which I tracked down to a runaway regular expression, which was a result of old C++ code expecting a nul terminated string, even though it was taking a pointer and a length.

It was easy enough to fix, but it got me looking at my regular expression implementation. Suneido has its own regular expression implementation both for historical reasons, and for portability. When I wrote jSuneido I tried to use Java regular expressions, but it proved too hard to make it compatible with cSuneido. And by now we have a lot of application code that depends on the particular flavor of regular expressions that I originally implemented.

Although it's a fairly clean object-oriented design, there was one part where it was switching on types rather than calling a virtual method. That was because it needed to update some state. No big deal, I’d just put the state on an object and pass it around.

I decided to work on this on the Go version, and Go made it very easy to write a quick benchmark to make sure my changes didn’t slow it down too much.

What I found was that it was already quite slow, and even slower with the changes. Suneido applications don’t tend to use a lot of regular expressions, so the speed wasn’t a huge issue, but it bothered me nonetheless.

The implementation compiles regular expressions to an intermediate form which is then interpreted. The speed of an interpreter depends primarily on how “large” the instructions are. In this case the instruction are very small, e.g. matching a single character. And my fancy object-oriented design added even more overhead in terms of indirection and virtual (interface in Go) calls.

What if I took a different approach and used the classic big-switch-in-a-loop style of interpreter with all the code inlined? 

I made a quick prototype and benchmarked it as 300 times faster. I was a skeptical of that result, but it seemed worth investigating. As the code grew from a trivial prototype, the results came down to earth, ending up about 3 or 4 times faster. That was more believable, and still a good improvement. I suspect my first prototype was a little too simple and the compiler optimization eliminated most of it. That’s a common problem with micro-benchmarks.

Without all the object-oriented wrapping overhead, the inline interpreter wasn’t even that big, around a hundred lines of code.

Of course, while I was in there I couldn’t resist a few other optimizations. Suneido’s regular expression implementation uses fairly naive backtracking, which has some ugly worst cases. It’s a bit ad hoc, but I added specific handling for some of those bad cases. That’s where I saw up to 1000 times speed improvement, although only for those specific cases.

So I was happy with the speed improvement from this rewrite, but was the code harder to follow? I’m not sure. The interpreter is more monolithic, but it’s still reasonably small. And a whole bunch of interconnected small objects is not always easy to follow either. For me, it was a reasonable trade off.

Code in Github as usual

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.

Optimizing Tr

Suneido has a string.Tr function, similar to the Unix tr command. Recently, I was looking at the stdlib Base64 code. Decode was using string.Tr to strip any newlines. However, there may not be any newlines. Which made me wonder what Tr did in this case - did it still make a copy of the string? Sure enough, it did.

My first reaction was to add a guard:

if s.Has?('\n')
    s = s.Tr('\n')

Then I started to wonder where else we should be doing this. But that was ugly. It made more sense to build it into Tr.

But implementing it as above would mean doing an extra scan of the source string. Since the code was already scanning, it would be more efficient to just defer copying until found somewhere where you needed to make a change.

I implemented this in the C++ code. It complicated it a little, but not too bad.

Then I tried to implement the same thing in the Java code. Not being able to "cheat" with macros like in the C++ version meant I had to create an instance to share the variables. This defeated part of the purpose (to avoid allocation) and seemed ugly.

Instead I decided to do an initial scan to find the first character to be changed, and then either return or continue from that point. This still avoided redundant scanning, without complicating the main part of the code.

In the process, I discovered there were a few other cases I could short circuit - if the source string is empty, or if the "from" character set is empty then you can just return the source string unchanged. Also, if there are no ranges in the from set or the to set, then you don't need to expand the sets, avoiding more allocation and copying, albeit only on the sets. I also simplified the code a little. (It was a good thing I had tests since I "simplified" a little too aggressively a few times!) See the code.

I also decided to add a cache for expanding sets with ranges. I'm not sure that's justified, but it's similar to what I do with regular expressions. The regular expression code had been using a home-brew LruCache, but I switched to Google Guava's caching facilities. That also allowed time based expiry so I could make the cache bigger without wasting space if it wasn't needed.

Then I went back and revised the C++ tr code using the same approach as the Java code.  For some reason I had originally use std::vector for the sets. I switched to making them gcstring's to avoid making a new set if there are no ranges to expand. I also added a cache, using the existing CacheMap that was being used for regular expressions.

Although it sometimes bugs me to have to update two implementations of Suneido, it does have its benefits. It means if I want to use the same approach I can't take too much advantage of specific language features (e.g. macros). This might mean I can't use some fancy feature, but in many cases that's not the wisest anyway. By the time I've written the code in two different languages, I think the end result is usually better than if I'd just written it once.

Again, I'm guilty of optimizing without real proof of whether it's justified. Tr is fairly heavily used in some areas, and the changes will probably speed up those areas. But whether that makes much difference in the bigger picture is questionable.

An amusing historical aside - I originally ported this code from Software Tools by Kernighan and Plauger, which uses Ratfor (rational Fortran). The code's origins are still visible in some of the names and structure. This book was an inspiration in my early programming days. I still have my original copy, although it's falling apart. It's pretty cool that it's still in print 37 years later.

See also previous posts: String Building Internals and An Amusing Bug

String Building Internals

Recently we ran into a problem where a service using cSuneido was running out of memory. I confidently switched the service to use jSuneido, and got stack overflows. So much for my confidence!

We tracked it down to calling Base64.Encode on big strings (e.g. 1mb) (This came from sending email with large attachments.)

Base64.Encode was building the result string a character at a time by concatenating. In many languages this would be a bad idea for big strings. (e.g. In Java you would use StringBuilder instead.) But Suneido does not require you to switch to a different approach for big strings, the implementation is intended to handle it automatically.

Up till now, Suneido has handled this by deferring concatenation of larger strings. If the length of the result is greater than a threshold (64 bytes in cSuneido, 256 bytes in jSuneido) then the result is a "Concat" that simply points to the two pieces. This defers allocating a large result string and copying into it until some operation requires the value of the result. Basically, Suneido makes a linked list of the pieces.

For example, if you built a 1000 character string by adding one character at a time, Suneido would only allocate and copy the result once, not 1000 times. (It still has to create 1000 Concat instances but these are small.)

In practice, this has worked well for many years.

I thought I had implemented the same string handling in jSuneido, but actually I'd taken a shortcut, and that was what caused the stack overflows.

The obvious way to convert the tree of Concat's to a regular string is a recursive approach, first copying the left side of each concat, and then copying the right side, each of which could be either a simple string or another Concat. The problem is that the tree is not balanced. The most common case is appending on the end, which leads to a tree that looks like:

But with many more levels. If your tree has a million levels, then recursing on each side (in particular the left side) will cause stack overflow. In cSuneido I had carefully iterated on the left side and recursed on the right. (Basically doing manual tail-call elimination.) But when I ported the code to Java I had unknowingly simplified to recurse on both sides.

Once I knew what the problem was, it was easy enough to fix, although a little trickier due to using StringBuilder.

Thinking about the problem I realized in this case, there was a better way to write Base64.Encode. I could use the form of string.Replace that takes a function to apply to each match, and simply replace every three characters with the corresponding four characters in Base64. Since string.Replace uses a buffer that doubles in size as required (via StringBuilder in jSuneido), this is quite efficient. (In the process I discovered string.Replace in cSuneido choked on nul's due to remnants of nul terminated string handling. Easy enough to fix.)

But that left the problem of why cSuneido ran out of memory. I soon realized that the whole Concat approach was hugely wasteful of memory, especially when concatenating very small  strings. Each added piece requires one memory block for the string, and another for the Concat. Most heaps have a minimum size for a heap block e.g. 32 bytes. So in the case of appending a single character, it was using 64 bytes. So building a 1 mb string a character at a time would use something like 64 mb. Ouch!

In theory, cSuneido could still handle that, but because it uses conservative garbage collection, spurious references into the tree could end up with large amounts of garbage accumulating.

Maybe my whole Concat scheme wasn't ideal. To be fair, it has worked well up till now, and still works well for moderate string sizes. It just wasn't designed for working with strings that are millions of characters long.

I dreamed up various complicated alternative approaches but I wasn't excited about implementing them. It seemed like there had to be a simpler solution.

Finally, I realized that if you only worried about the most common case of appending on the end, you could use a doubling buffer approach (like StringBuilder). The result of a larger concatenation would be a StrBuf (instead of a concat). Because strings are immutable, when you appended a string onto a StrBuf, it would add to the existing buffer (sharing it) if there was room, or else allocate a new buffer (twice as big).

Theoretically, this is slightly slower than the Concat approach because it has to copy the right hand string. But in the common case of repeatedly appending small strings, it's not bad.

This approach doesn't appear to  be noticeably faster or slower, either in large scale (our entire application test suite) or in micro-benchmarks (creating a large string by repeatedly appending one character). But, as expected, it does appear to use significantly less memory (roughly half as much heap space).

One disadvantage of this approach is that it doesn't help with building strings in reverse order. (i.e. by repeatedly adding to the beginning of a string) That's unfortunate, but in practice I don't think it's too common.

A nice side benefit is that this approach is actually simpler to implement than the old approach. There is no tree, no recursion, and no need for manual tail-call elimination.

Unfortunately, in Java (where I've been working on this) you still have to convert the StringBuilder to a string when required, which makes yet another copy. In cSuneido I should be able to simply create a string wrapping the existing buffer.

Thinking about it some more, I wasn't happy with the extra copying - a lot more than the previous approach. I realized I could combine the two approaches - use a doubling array, but storing references to the pieces rather than the actual characters. This eliminates the copying while still reducing memory usage.

Note: Concats and Pieces cannot be combined because Pieces is shared - appending to a Concats will result in a new Concats that (usually) shares the same Pieces. Concats is effectively immutable, Pieces is mutable and synchronized. (It would be nice if Java let you combine a class and an array to make variable sized objects, but it doesn't.)

However, in the worst case of building a large string one character at a time, this would still end up requiring a huge array, plus all the one character strings. But given the array of strings, it's relatively easy to merge small strings and "compact" the array, reducing the size of the array and the overhead of small strings.

I didn't want to compact too often as this would add more processing overhead. I realized that the obvious time to compact was when the array was full. If there were contiguous small strings that could be merged, then you could avoid growing the array.

I was disappointed to discover that this new approach was about 1/2 as fast as the old approach (when building a 1mb string one character at a time). On the positive side, it resulted in a heap about 1/4 the size (~200mb versus ~800mb). It was a classic space/time tradeoff - I could make it faster by doing less merging, but then it used more memory.

Interestingly, the test suite (a more typical workload) ran about 10% faster. I can't explain that, but I'm not complaining!

It still nagged me that the new approach was slower building huge strings. I tried running it longer (more repetitions) to see if garbage collection would have more of an effect, but that didn't make much difference. Nor did building a 100kb string instead of 1mb (and again doing more repetitions). Then I thought that since my new approach was specifically aimed at building huge strings, maybe I should try increasing the size. Sure enough, building a 10mb string was 4 times faster with the new approach. Finally, the results I was hoping for! Of course, in practice, it's rare to build strings that big.

I initially wrote special code for adding to the beginning of a concatenation and for joining two concatenations. But then I added some instrumentation and discovered that (at least in our test suite) these cases are rare enough (~1%) that they're not worth optimizing. So I removed the extra code - simpler is better.

There are a number of "thresholds" in the code. I played around a bit with different settings but performance was not particularly sensitive to their values.

I probably spent more time on this than was really justified. But it was an interesting problem!

As usual, the code is in Mercurial on SourceForge. Or go directly to this version of Concats.

Optimizing Java Memory Usage

One of the things I've been meaning to work on for a while is the memory usage for temporary indexes in Suneido's database.

I started by measuring the current memory usage. I used two test cases, first a single table with 400,000 records sorting by a non-indexed field, and second the same table but joined with another one. I used Visual VM to watch the heap and force garbage collections to get an idea of memory usage. The first case used about 200mb and the second about 400mb. For the simple case, that's about 500 bytes per record. I was pretty sure I could improve this usage.

My assumption was that a lot of the usage was Java's per-object overhead.

For each record, the temporary index code created a new sort key record, plus an Object[] array that stored references to each of the source data records (more than one in the case of joins). These sort key arrays are then added to a MergeTree.

My first step was to switch from allocating a separate small array for each sort key, to putting them into a big array and referencing them by offset.

I could have used a standard ArrayList, but it works by doubling the size of it's internal array each time it needs to grow. At very large sizes, this is not the best strategy. For example, to grow from 100mb to 200mb you need to allocate a new 200mb array, copy the old 100mb array into it, and then the old array has to be garbage collected. On top of this, if the data is long lived, it will probably end up being moved to older generations by the garbage collector, where it won't get garbage collected as easily.

Instead, I wrote an ArraysList which uses a bunch of medium sized arrays rather than one big array. To grow it simply allocates another medium size array, without any copying or garbage collecting. This is not necessarily better in every situation, but for my usage it is.

The next problem was that now I was storing an int offset (into the ArraysList) instead of an array. My MergeTree is generic, which means to use if for int's they'd have to be boxed into Integers. Then I'd be back to too much per-object overhead. So I had to make a specialized IntMergeTree. It's too bad that Java makes such a big distinction between primitives and references, and that generics only work with references. (Scala tries to reduce the distinction, and it even lets you specialize a generic class for a primitive type, but it still ends up boxing and unboxing most of the time.)

In the common case where you're just sorting a single table, there's no need for the array at all, and instead of storing the ArraysList offset, you can just store the integer "address" of the record.

The next step was to store the sort key record in larger blocks of memory rather than individually, and again reference them by offset rather than a Java reference. For this I could use the MemStorage class I had already written to create in-memory databases for tests. It inherits from the same Storage base class as my MmapFile memory mapped file access. These are based on ByteBuffers. Each sort key record used at least three memory objects (the record, its ByteBuffer, and the ByteBuffer's array) so this was a significant saving. (This doesn't require much serialization because the sort key records are already in a serialized form.)

The end result was that the memory usage was less than 1/4 of what it was before. My first case now took about 40mb instead of 200mb, and my second case took about 90mb instead of 400mb. Not bad for a couple of days work.

I wouldn't normally recommend this kind of messing around - the overhead is seldom a big issue. But in the case of a server, with large numbers of users competing for memory, I think it was worth it.

Benchmark Surprises

We recently ran into a minor bug in Suneido - tracing temporary indexes in database queries would sometimes report queries that didn't actually have temporary indexes.

I found the problem right away. The query optimization looks at multiple different "strategies", some involve temporary indexes and some don't. The flag that indicated whether a temporary index was needed wasn't getting reset between trying different strategies. This flag wasn't used for much, so the problem hadn't been noticed.

The problem was, when I fixed the bug, a bunch of query optimization tests started failing. That surprised me because the flag wasn't used much, and on top of that, the change fixed the flag - why would that break things?

It turned out the one other place where the flag was used was in join optimization. And unintentionally, the code had ended up dependent on the incorrect flag. Ouch. It turned out surprisingly hard to figure out what was going on. The query optimization is complex and because it explores many different strategies (to find the least cost) any debugging output is large and hard to follow.

Eventually I tracked it down to the relative estimated costs of temporary indexes versus look-ups by joins (which was tied indirectly to the flag).

I'm embarrassed to say that I have never really done good benchmarking to check that the "cost" estimates in the code matched the real execution times. Most of the estimates are seat of the pants guesses, adjusted to work reasonably. It's not as bad as it sounds because there's usually one strategy that is much better than the rest, so you don't really need to be exact.

I "fixed" it (so the tests passed) by greatly reducing the cost estimate for look-ups, but I wasn't sure if that just happened to fix it, or if the cost of look-ups was actually a lot lower than I originally thought. (Actually, one test still "failed" but the new strategy looked better than the old one so I "fixed" the test.)

I took a few hours and did some quick benchmarks. The results were surprising. The optimization "cost" takes into account index key size and record size but it turned out these had very little affect on the execution time. The only significant factor (in the tests I ran) was the number of records processed. A temporary index roughly doubled the time. Joins took roughly the sum of the time of reading the two sides separately, the number of look-ups had little affect.

Note: These results are very specific to Suneido, I would not expect them to applicable elsewhere. They are also working with data that fits comfortably in memory so disk access is not a factor. That might seem unrealistic, but that's actually the normal case with our systems.

One good thing about the results is that (I think) it validates part of the database implementation. The code is careful to not copy data - the database file is mapped into memory, and that "raw" memory becomes (within a wrapper object) the in-memory record with no copying or conversion. This is likely the reason that record size (and maybe index key size) had little effect on speed. (Since I assume copying and conversion would take time proportional to record size.)

I ended up refactoring the join optimization to not use the flag at all. That left only the tracing using it, and it was easy to rewrite that to work another way. So I ended up removing the problematic flag entirely. Nice.

I'm left with the realization that my query optimization code is likely a lot more complicated than it needs to be. It looks like it would work just as well if I ignored record size and index key size and just based costs on the estimated number of records to be processed at each stage. But I think I'll leave that for another  time.

YAGNI Strikes Again

This might also have been called "Premature Optimization Strikes Again".

For a given query, Suneido's query optimization chooses the "best" index to read each table by. But it also tries to determine if it is worthwhile to use additional indexes as well.

The problem is that using an additional index may not help, and may actually slow down the query.

Over the years, each time we ran into a case where it was doing more harm than good I've struggled to try to improve the heuristics.

One of the things that makes this hard is that the query optimizer doesn't really have enough information to know when additional indexes would be useful.

Another case came up recently. We added an index to speed up one thing and sometime later (through customer complaints) found that it had slowed down something else. (We probably need some performance tests to catch this kind of thing.)

Adding an index shouldn't slow anything down, it should only potentially speed things up. But extra indexes tend to lead to the query optimizer choosing additional indexes, and sometimes slowing things down.

As I was working on the current problem, I wanted to measure the speed without additional indexes so I disabled this feature.

Then I started to wonder if this feature was actually providing enough benefit to justify all these hassles (and slow downs). So I ran our test suite of over 1000 tests with additional indexes disabled and it made no difference to the speed!

That doesn't mean there aren't certain situations where this feature would be worthwhile. But it is a pretty good indication that overall it's not providing a lot of benefit. And there's no question that it's caused problems.

So I think I'll do some more testing and try it out in-house and if no problems come up I'll just remove this feature.

Obviously, I shouldn't have added this feature in the first place without "data" to tell me it was worthwhile. i.e. I shouldn't have prematurely optimized. The problem is, there's no way to know if it will be beneficial or not without implementing it. It's not like measuring a bottleneck in your code and then optimizing it. In this case, you're talking about whether adding something will help, and how can you "measure" that without implementing it?

Oh well, I guess there's nothing wrong with determining that a feature is more trouble than it's worth and ripping it out. You just have to get over the psychological hurdle of throwing away a bunch of work.

* YAGNI = you ain't gonna need it

Another Query Optimization

Database query optimization in Suneido is a collection of heuristics. Most of them have come from finding queries that aren't executed efficiently and then figuring out ways to improve it.

The latest example was a query like:

(table1 leftjoin table2) where table2_field = "stuff"

Joins are implemented by reading sequentially through the left hand table (or sub-query) and doing lookups on the right hand side. This means you can read through the left hand side in any order. The right hand side requires an index on the join fields (to do the lookups efficiently).

Normal join's are symmetrical, but the implementation isn't, so part of the optimization process is deciding whether to reverse the order of a join.

But leftjoin's preserve all the records from the left hand side even where there are no matching records on the right. This means leftjoin's are not reversible, which limits optimization and sometimes leads to inefficient execution.

The trick is that this case:

table1 leftjoin table2 where table2_field = "stuff"

is actually equivalent to:

table1 join table2 where table2_field = "stuff"

because table2_field can only be "stuff" if there are matching records.

Once we see that it's equivalent to a normal join, then it's reversible, and there are more opportunities for optimization.

You might wonder why the programmer wouldn't just see this and write the query with a join instead of a leftjoin. In this example, the leftjoin was in a view definition, with the where added later. So the programmer only saw:

myview where table2_field = "stuff"

Besides, programmers don't always catch these things. It's a lot better if the system handles it.

Suneido's query optimization has two main phases - transform which moves and merges operations, and optimize which chooses strategies and index use.

This new optimization will be in the transform phase. Suneido already tracks "fixed" fields that are restricted by where's to a constant value. So if we see a fixed (and non-empty) field on the right hand side of a leftjoin, we can convert to a regular join.

Note: Suneido already moves where's as close to the tables as possible, so even if the query starts out as:

(table1 leftjoin table2) where table2_field = "stuff"

it will be transformed to:

table1 leftjoin (table2 where table2_field = "stuff")

This makes it easier to "see" the fixed field on the right hand side.

This shouldn't be too hard too implement. Especially since I've been working on the join code fixing a bug I found recently (while working on jSuneido).

[I'm not sure how much sense this will make if you're not familiar with this stuff. I wrote it for my own notes as much as anything.]