Large Scale Java Design

I ran into a problem when I reached the point where I wanted to start integrating my append-only database storage engine into the rest of Suneido.

The problem was that the old storage engine was too tightly coupled with the rest of Suneido. Not very good design on my part, but in my defense, the design came from the old C++ code, much of which is 10 or 15 years old.

So how should the code be structured? What's the best way to use Java packages and interfaces to reduce coupling? I looked for the Java equivalent of Large Scale C++ Software Design by John Lakos. (Seeing that it was published in 1996, I guess I don't really have an excuse for the poor structure of my old code!) But there doesn't seemed to be an equivalent for Java. (Let me know if you have suggestions.)

There are books like Effective Java but they're mostly about small scale. And there are books about J2EE architecture, but I'm not using J2EE.

Books like Growing Object-Oriented Software (recommended) talk about coupling from the view point of testability, but don't explicitly give guidelines for high level architecture.

In addition, what I needed wasn't just less coupling. I needed to be able to configure the code to run with either storage engine. For that, there couldn't be any static coupling between the storage engine and the rest of the code.

One really crude way to do this would be to simply rename one of the two storage engine packages to be the name referenced by the rest of the code. That would require changing every source file. Eclipse would do that, but it wouldn't play well with version control. And I would have to manually ensure that the two packages were defined the same public methods.

Instead I decided to clean up my architecture. In case it's helpful to anyone else, I'll sketch out what I came up with. Some of it is standard advice, some is a little more specific to what I needed. None of it is particularly original or unique.

First, other packages (i.e. the rest of the system) should only reference interfaces that are defined in a separate interface package.

That means no direct field access, you have to use setters and getters for public access.

It also means no public static methods or constructors. Instead there is an interface for a "package" object. A singleton instance of the package object is created at startup. All access to the package starts here. So to use the new storage engine you just have to use its package object. This class contains any public constructors and static methods and is the only public class in the package.

One mistake I made, coming new to Java from C++, was to make methods either private or public. I should have been using package scope a lot more than public. (Which might explain why it's the default in Java!) Now, the only methods that are public are the ones implementing public interfaces.

It's nice that Java (since version 5 / 1.5) allows covariant return types. i.e. the public interface can say that a method returns another public interface, but the actual method implementation can return the concrete type. This reduces the need for casting within the package.

I've finished refactoring so the old storage engine code follows these guidelines. I thought I might run into areas that would take a lot of redesign, but it's gone surprisingly smoothly.

Next I have to refactor the new append-only storage engine to implement the same interfaces. Then I should be able to easily switch between the two.

Of course, the interface I've extracted from the old storage engine doesn't match the new storage engine so I'll have to do some refactoring to end up with a common interface.

As usual, the code is public in Suneido's Mercurial repository on SourceForge.

The LMAX Architecture

A good article by Martin Fowler on a very interesting architecture.

The LMAX Architecture: "LMAX is a new retail financial trading platform. As a result it has to process many trades with low latency. The system is built on the JVM platform and centers on a Business Logic Processor that can handle 6 million orders per second on a single thread. The Business Logic Processor runs entirely in-memory using event sourcing. The Business Logic Processor is surrounded by Disruptors - a concurrency component that implements a network of queues that operate without needing locks. During the design process the team concluded that recent directions in high-performance concurrency models using queues are fundamentally at odds with modern CPU design."

Dreaded Deadlock

I was doing some refactoring and came across a stress test that I hadn't run for a while. (it's too slow to include in my unit test suite)

I ran it and it hung up. What the ...?

I thought maybe it was my refactoring but I reverted my changes and it still hung.

The test is multithreaded and using the Eclipse debugger I could see the threads were all hung at the some spot. It wasn't an infinite loop, but it was a synchronized method.

I used jConsole's deadlock detector to confirm what was going on.

Suspiciously, I had recently made a "minor" change to this exact part of the code.

The funny part was that I made the change because FindBugs reported a potential concurrency problem.

I removed the synchronized and used volatile instead and that fixed the problem. I think volatile is ok in this instance, but it's always hard to know for sure.

I think FindBugs was correct that there was a problem. My mistake was slapping in a fix without really thinking it through. That's definitely a no-no when it comes to concurrency. It's a good example of how the "intuition" that adding more locks can't hurt is very wrong.

My second mistake was not running the related stress tests when I made the change. I need to add the stress tests to our continuous build system at work. And maybe set up something at home as well, if I can make it lightweight enough.

Yet another reminder that concurrency is hard! (not that I should have needed the reminder)

Mockito for Suneido

From the Couch 12 - Mockito for Suneido

I've been using Mockito for writing tests for jSuneido and I really like it.

So I decided to write something like it for Suneido ...more

Upgrading to Eclipse Indigo

The latest version of the Eclipse IDE, version 3.7 named Indigo, was release a few days ago.

For me, this was the smoothest upgrade so far. My jSuneido project still seems to build just fine, and the tests still all succeed.

All but one of the plugins I use was available through the Eclipse Marketplace (under the Help menu). Going through the Marketplace is a lot easier than the old style of entering a URL for an update site. The plugin that was not available has not been marked as compatible with Indigo, not surprising as it doesn't seem to be under active development. There are other metrics plugins, but the nice thing about this one is that it also displayed dependencies graphs. But it's probably the plugin I use least, so it wasn't a big deal. The other plugins I use (that were available) are: Bytecode Outline (for ASM), EclEmma Code Coverage, FindBugs, and MercurialEclipse.

I haven't really noticed any major improvements, but I'm sure there are some.

The only minor annoyance I noticed was that it spent a long time at first downloading the Maven indexes. Maven support is built in now, but my project doesn't use it, so I'm not sure why it needed to download the indexes. But even this wasn't a big deal since it happened in the background. (I just noticed it in the Progress view and in my network activity.) I tried to use Maven another time but just made a mess and gave up. Maybe I should try again now that support is built in.

If my experience is typical, then I wouldn't be afraid to upgrade.

Are ten apps all you need?

Ten apps is all I need - (37signals)

I disagree. I regularly use a bunch of non-Apple apps e.g. offline Wikipedia, iBird, oMaps, Topo Maps, Evernote, MobileRSS, BlogPress, TripIt, Photoshop Express, Yelp, Facebook, Twitter, SmartGo. *

I agree no one needs hundreds of thousands of apps. But you need a large selection in order to find the ones you want - you need the long tail. It's the same problem when you try to reduce the number of features in software. Sure, no one person uses all the features, but different people use different features.

The popularity of the platform draws the developers that you need to get the apps you want.

One of the big things that would stop me from using another phone or tablet (e.g. Android) would be the availability of the apps that I want.

PS. I'd also disagree with listing the Weather app as one that Apple "nailed".  It's very basic and I don't find it very useful. I believe it's getting updated in IOS 5.

* A number of these I use because they work offline. Outside Canada, or even out of town, I don't have constant connectivity.

Language-induced brain damage

elliotth's blog: Language-induced brain damage is better than the alternative

An interesting blog post.

And I'm glad I'm not the only one that thinks java.nio.buffers sucks. (Although, in my latest append-only database storage engine they haven't been that big a problem - maybe I've learnt how to use them to avoid the worst problems.)

Apps

A couple of interesting free iPhone apps I've come across:

LeafSnap - take a picture of a leaf and get it identified. I haven't been able to test this much since we have no leaves yet! But I love the idea. Only some US trees so far but more promised.

Photosynth - helps you photograph panaramas, stitches them together, and lets you view them. From Microsoft.

A part of me would like to escape the Apple closed world, maybe buy an Android tablet instead of an iPad. But I really like the huge variety of apps. Some of them come out on Android as well, but not all of them.

Suneido's Record Structure Revisited

After my last blog post on Suneido's record data structure, the wasted byte in the header started to bug me. I know where it originally came from, I simply had a C struct like:

struct
     {
     char type;
     short nfields;
     ...

C/C++ automatically adds a byte of padding after the char so that the short is aligned.

Most of the time the padding was invisible and when I did think about it, I figured if the average record is, for example, 100 bytes, then it's only 1% overhead, no big deal.

After the last blog post I was wondering how I could eliminate that byte of padding. There are only three types, so it only really requires two bits. And the full range of nfields isn't really required, so you could store the type in two bits of nfields, still leaving a maximum number of fields of 16,383.

That actually cuts two bytes, not just one. But still, that's only 2%.

But then I realized that Suneido also uses this record format to store keys within btree nodes. And keys are shorter. If the average key is 10 or 20 bytes, then the overhead is 10 or 20%, not 2%. That's a little more significant.

And it's not just the memory space, it's also garbage collection overhead, and disk reads and writes. And it's also copying overhead when "updating" immutable data records and btree nodes.

One of the reasons I kept the same record format in jSuneido as in cSuneido was so that dumps from cSuneido could be directly loaded into jSuneido without converting the record format. But btrees are not moved from one version to another, so they could easily use a different, more compact format. And it wouldn't be hard to convert the format when loading cSuneido dumps.

One drawback to this approach is that when the offsets are 4 byte ints, then a 2 byte header will mean the offsets are not aligned. This might be more of a concern in cSuneido, where records are used more heavily and are accessed more directly. But I don't think it's a big issue in jSuneido.

It wasn't too hard to implement. With one table of about 1600 records that was 1 mb in size (including indexes) the database was about 5% smaller after the changes. Not bad for a few hours work and very little added complexity.

Suneido's Record Data Structure

Both cSuneido and jSuneido use the same data structure for low level record storage.

type is one of 'c' (char, 1 byte), 's' (short, 2 bytes), or 'l' (long, 4 bytes) and specifies the size of the length and offset values. (In Java, a better choice of types would have been 'b' (byte), 's' (short), and 'i' (int)). (Calling a 4 byte integer "long" is a leftover from the days when int's were 2 bytes.)

There is one byte of padding after the type byte. (Originally a result of C struct padding.) Or the type can be treated as a 2 byte little endian short integer.

nfields is a short (2 byte) integer count of the number of fields in the record.

length is the overall number of bytes in the record. When calculating field sizes as the difference between two offsets, it is handy to be able to reference the length as offset[-1].

The fields data is variable length and stored in reverse order.

In cSuneido records are used as mutable data structures. As fields are added, the offsets and fields grow towards each other. Before storing in the database file they are copied to the exact size required. As a mutable data structure, one drawback of the design is that when the record is reallocated to a larger size, all the offsets change. If the field data was at the beginning and the offsets at the end, then reallocating would not change the offsets and they could simply be copied to the new record. The tradeoff would be that accessing the offsets would be more awkward since they would not start at a fixed location in the record.

In jSuneido records are stored in NIO ByteBuffer's. They are only used as immutable data structures (at least in the new storage engine). A RecordBuilder is used to collect the data so that the record can then be created the exact size required. (i.e. with no unused space between the offsets and the fields)

Allowing different sizes for the length and offsets makes the overhead low for small records (an empty record is only 5 bytes) while still allowing for large records (up to 32k fields and 2gb length).

Having an array of offsets allows random access to the fields. For example, a search on the Nth field can access that field directly, without having to scan through the record. Of course, this is only an advantage because Suneido does not convert records to an internal format to search them.

Offsets are used rather than pointers because records are intended to be stored in the database where pointers would not be usable.

In this design empty fields still take up space in the offsets array although not in the field data. (e.g. in the common short type, empty fields take 2 bytes each) This seems like a reasonable tradeoff for the ability to randomly access fields.

The C++ source code is in record.h and record.cpp and the Java code is in Record.java

Semi-Immutable Data Structures

In the new append-only database storage engine for jSuneido I've ended up with several data structures that are "semi-immutable" i.e. they are immutable some of the time and mutable some of the time.

(These are in-memory data structures, the database file itself is only ever appended to, existing data is always immutable i.e. never updated.)

I've flip flopped back and forth a few times from completely immutable to partially immutable, but I seemed to have settled on partially immutable.

The overall "state" of the database is kept immutably. When a database transaction starts, it "copies" this state. (The "copy" consisting of just a few pointers to persistent immutable data structures.)

"Inside" a transaction, the data structures can become mutable. The first update a transaction does will path copy nodes up to the root. This "disconnects" the data structure from the overall databases state. Nodes within the data structure can now be either shared and immutable or not shared and mutable.

(Allowing mutability within transactions is "safe" because transactions are thread-contained i.e. only one thread at a time works on a transaction.)

The main advantage of this approach is performance since nodes can be updated with less copying.

At the end of a transaction commit, the new state is stored (persisted) in the database file. This converts all the nodes back to immutable.

This semi-immutable approach is used both for the table index btrees and the hash tries used to store redirects and database info (e.g. btree roots).

jSuneido append-only database fomat

The following is as much for my own review as anything.

The database file layout is quite simple - it consists of a sequence of commits.

Each commit has a header (size and timestamp) and a trailer (checksum and size). Given the leading and trailing sizes, the commits can be traversed forwards and backwards.

The body of a commit consists of the data records (table rows), btree nodes, and hash trie nodes followed by pointers to the roots and redirects hash tries.

The roots hash trie points to the btree indexes as well as other database information. As I've talked about before, the redirects are used to avoid path copying in the btrees.

When the database is opened, the roots and redirects are accessed at a fixed offset from the end of the file. Together they provide access to the database at a certain point in time.

Read-only transactions, operating as-of a certain point in time simply use the roots and redirects as of when they started. They can operate completely independently because the data they are looking at is immutable. There are no locks or concurrency issues.

When the database is opened, the checksums of the last few commits are verified to confirm that the database was previously closed properly. (This uses the trailing size to traverse the commits from the end of the file backwards.)

If this checking fails, then crash recovery is done. The commits are traversed from the beginning of the file (using the leading sizes) and the checksums are verified. The file is then truncated after the last good commit. (This is much simpler and faster than the current system.)

Checksums are of the raw data - they do not care about the logical contents of the commits. They use Adler32 checksums for speed.

Note: Although it's not shown in the diagram, there may be "padding" between elements in the file. This is because the memory mapped file is mapped and extended in "chunks" of 64 mb. Elements are not allowed to straddle chunks, so padding may be required at the end of a chunk if an element won't fit. Since there is no sequential access to elements within commits, this padding has no effect, other than a very small amount of wasted space.

All of this is implemented and working well. But I've still got a fair bit of work left to integrate this new storage engine into the rest of the database code. Sadly, I don't have a nice clean storage engine interface :-(

As usual, the code is available in the Suneido project Mercurial repository on SourceForge. The new storage engine code is in the immudb package.

NativeJ Java Launcher

If you're looking for a way to run Java programs as Windows services, or launch them from an exe, I would highly recommend Dobysoft's NativeJ

The software works well, but more importantly, they have bent over backwards to accomodate our needs. Granted we paid for it, but $150 doesn't cover a lot of support, let alone programming.

Previously we used JSL to run as a service and Launch4J for a launcher. Both are free and worked ok, but we ran into problems with Launch4J not returning the exit code. (a known issue) It's open source so I guess we could have dug into it and tried to fix it, but I was looking for something that would handle both services and launcher together and NativeJ looks like a good solution.

PDP-11 Emulator running V6 Unix - in Javascript!

http://pdp11.aiju.de/

Amazing!

I was in high school when I got my first Unix account on a computer science system at the university. It might have been a PDP-11. I remember struggling to teach myself C from Kernighan and Ritchie when all I knew was Basic. And of course way too shy to actually ask anyone for help.

A Fractal Tree Implementation

I couldn't resist whipping up a quick implementation of a fractal tree, even though I don't really need it for anything. I'm a sucker for a good algorithm :-)

The code can be amazingly simple. Here's my first cut at insertion:

public void add(T x) {
     Object[] tmp = new Object[] { x };
     int i = 0;
     for (; nodes[i] != null; ++i) {
          tmp = merge(nodes[i], tmp);
          nodes[i] = null;
     }
     nodes[i] = tmp;
}

merge simply merges two sorted arrays into a new larger array.

This works fine, but it will chew through a lot of memory allocating new arrays. The space will be reclaimed by the garbage collector, but it seems a little wasteful.

So I modified it to pre-allocate the first few levels of small arrays since these are the ones that get the heavy activity. (e.g. the first four levels of size 1, 2, 4, and 8 will handle 15/16 of adds) This complicates the code a bit, but not too badly.

Iteration is quite simple as well - just merging the sorted nodes.

The full code is in SourceForge

Fractal Trees

Another interesting data structure is the Fractal Tree used by Tokutek's TokuDB (another MySQL variant). I think this is related to the stratified data structure (at least some of the description is similar).

B-trees are at one point in the range of insert speed versus lookup speed. Fractal trees are much faster at inserts, but slower at queries.

It's easy to see how inserts work, and that most of them would be very fast. But part of the reason it's fast is that the cost is amortized - there are occasional big operations (a little like having to resize a hash table). It sounds like they're doing these in a background thread to avoid delays, but that has to make querying tricky.

And querying seems tricky regardless. A naive binary search in each level is going to be slow (and potentially many disk accesses or at least cache misses). To speed this up they add pointers from each value to it's position in the next level. They don't go into detail, but I have to think maintaining these pointers is going to make inserts more complex.

I'm not sure how this approach would work for an append-only index. Again, the average insert wouldn't write much, but the occasional insert that caused a lot of merging would write a lot. Maybe the amortized cost would still be reasonable.

It seems like it would make an interesting sort algorithm, but I have no idea how the performance would compare. It's a little like a merge sort, which has good performance.

Doesn't look like this is something I can use directly, but it's always good to learn new approaches.

B-tree Arcana

I recently ran across a new article on Stratified B-trees and versioning dictionaries. I have to admit I didn't really follow their data structure or algorithm. I looked at some of the references, for example to Cache-Oblivious Streaming B-trees but the ideas seem too complicated to be directly useful to me.

However, there were some bits that were interesting to me. They talked about the space blowups and inefficient caching in path copying CoW (copy-on-write) B-trees.

each update may cause an entire new path to be written – to update a 16-byte key/value pair in a tree of depth 3 with 256K block size, one must first do 3x256K random reads and then write 768K of data (see http://bit.ly/gL7AQ1 which reported 2GB of log data per 50MB of index data)

I'm hoping to avoid this using redirection (based on ideas from RethinkDB). By redirecting instead of path copying, you only need to copy the node you're updating, not all the nodes on the path to the root. (And the nodes can be orders of magnitude smaller - see below.)

Many systems use indirect access through a mapping table all the time. Instead, I use direct access whenever possible, and only indirect to updated data. That feels like it should be better, but without a lot of analysis it's hard to be sure. It does reduce space overhead somewhat.

One of the big issues with CoW B-trees is garbage collecting the old nodes. I have to admit I punt on this, requiring occasional database compaction instead. (This also removes all the redirection.) Not so good if you want to run 24x7 but it's a tricky problem and for our customers occasional maintenance downtime isn't a big deal.

Another interesting point was on SSD's (solid state drives).

SSDs handle small random reads very effectively, but perform poorly at random writes (the recent Intel X25M can perform 35,000 4KB random reads/s, but an order of magnitude fewer writes). However, they can perform very efficiently for large sequential writes.

That fits really well with CoW append-only B-trees since they do exactly that - random reads but sequential writes. And I recently got a new computer at work with an SSD :-) so I'll be able to do some testing.

Another point that caught my eye was that their arrays doubled in size between levels. Not understanding their system, I'm not completely sure what this means. But it rang a bell because I've been considering doing something similar with my B-tree nodes. Often, B-trees use large node sizes to reduce the number of random disk IO's. But large nodes don't work well with copy-on-write. And random IO's aren't as bad with SSD or just large disk caches.

I still need to do some testing to determine the best size, but I think it will be quite small. But I wonder if it would make sense to make nodes larger as you go "up" the tree towards the root. The leaf nodes are updated most often so it makes sense to make them small. But as you go up the tree the nodes are read more and updated less. Increasing (e.g. doubling) the size of the nodes at each level would decrease the number of tree levels and reduce the number of random IO's. And since larger nodes would split less often, higher tree levels would get updated even less frequently.

If I was in the academic world I'd need to figure out the theoretical performance of my approach under DAM (direct access machine) or CO (cache oblivious) models. Instead, I'll do some quick and dirty benchmarks and if there's not a big performance difference go with the simplest code.

Dead End

I've been plugging away at the new append-only storage engine for jSuneido. I have a decent proof of concept, but it's still a long way from production.

Recently I was working on btree iteration. Usually btree's link the leaf nodes to simplify iteration. But this linking is problematic with an append-only btree. So the iteration has to work a little differently. One of the problems is how to handle changes made during the iteration. Being in an immutable mindset, my immediate thought was to iterate through a "snapshot" of the btree. (Since snapshots are just a pointer in immutable persistent data structures.)

But then I realized I was only immutable on disk. In memory, within a transaction, I was using mutable data structures. So I jumped in and converted my btree's and the redirection hash trie map to fully immutable. After I'd pretty much finished this, I realized I should have looked closer before I leaped. But when you have a hammer, everything looks like a nail :-)

Iterating through a snapshot won't work. For example, if you update a record during iteration, the iteration would see an out of date version of the record, and might even try to update this "stale" data. Back to the drawing board.

On the positive side, I improved the code quite a bit. I've lost track of how many times I've refactored, reshuffled, rewritten this new storage engine code. It's not that big - currently about 2500 lines. You wouldn't think there'd be that many ways to arrange it!

Since I ended up not needing full immutability I changed it back to being immutable in memory (better performance). But I couldn't just revert the code because I wanted to keep some of the improvements I'd made.

About three days work on a dead end path. Oh well, if you're trying to come up with something new you have to expect a few dead ends. Not the first time, and I'm sure it won't be the last.

Interview with Uncle Bob

I enjoyed this podcast of an interview with Robert Martin aka Uncle Bob.

It's interesting to hear how he still likes to spend his time programming after 40 years (as opposed to getting sucked into management or other activities).

More on Java assert

Java's assert is a mixed blessing.

It's nice syntactic sugar. I'd rather write:

assert x == 0 : "expected x = 0, got " + x;

than:

if (x != 0)
    throw new AssertionError("expected x = 0, got " + x);

You could make your own assert so you could write:

verify(x == 0, "expected x = 0, got " + x);

But there is are subtle but important differences. With your own function, the error message is always constructed, whether the error is thrown or not. Whereas with assert, as with writing out the if, the error message will only be constructed if the assert fails. That doesn't matter if the message is just a literal string (or there's no message) but if the message requires, for example, calling toString on a complex object you could take a significant performance hit. There's also the lesser overhead of calling a function. It's possible that the JVM JIT optimizer will in-line the function so it becomes equivalent to writing out the "if" and therefore eliminate the overhead, but I'm not sure if it's "safe" to count on this.

The downside of assert is that you have to remember to enable it. (My blog post on this is one of my most visited. Google for "enable java assert" and it's currently the third result.) One way to avoid this is to write a test to confirm that asserts are enabled. I did this after I got burnt by disabled assertions a second time.

I just ran into another problem with this. We were looking at using NativeJ but it doesn't appear to have any way to pass the -ea option since it uses the java dll rather than the actual java executable.

I discovered that there is a way to enable assertions from within the code:

ClassLoader.getSystemClassLoader()
     .setPackageAssertionStatus("suneido", true);

It only applies to classes loaded after this, but I have it as the first statement of my main method which should be the first class loaded.

Another wrinkle to assert is that the exception it throws is AssertionError which is an Error. The Java exception hierarchy is:

Throwable
    Error
    Exception
        RuntimeException

Only RuntimeException's can be thrown without declaring them. "Normal" code is only supposed to catch Exception, not Error. But in Suneido, I don't want an assertion failure to "crash" the system, I want to be able to catch them. But to do that, I have to catch Throwable, which is not the recommended practice. I could use two catch's - one for Exception and one for AssertionError. But apart from the extra code, I wonder if there aren't other Error's that I would want to catch.

One way around the AssertionError issue would again be to write my own assert function so I could throw whatever exception I wanted (e.g. a RuntimeException). But as I explained above, there are issues with that.

Yet another option is to use a javac (the Java compiler) annotation processor (like fa.jar) that converts assert to if-throw. But that seems a little scary.

Of course, a lot of this is due to wanting to keep the assertions enabled, even in production. I'm a believer in this since so many problems don't show up till the software gets used for real. However, it does mean you have to be a little careful to make the asserts fast enough for production.

The People Behind The Software

I like how this video is about the people and the emotions behind the software.

A JVM Does That?

Cliff Click's recent blog post led me to the slides for his talk "A JVM Does That" - interesting stuff.

A quote from his post:

Java appears to have plateaued (although Projects Lambda and Coin may give it a serious boost), but the JVM is on a roll. Where people used to target C as their “assembly” of choice years ago (to avoid having to do code-generation), they now target the JVM – which avoids the code-gen AND supplies a GC, AND a well-understood threading model, plus true type-safety.

jSuneido Goes Live

Almost three years after starting the project, the Java version of Suneido is now live in production. Last night one of my programmers switched our in-house accounting and customer support system over to jSuneido (thanks Kim). We have about 40 fairly heavy users so it's a good test.

We had a few minor problems today but for the most part it went quite smoothly. When I brought it up with several people they said they didn't notice anything different, which is what I want to hear. Several people thought it was faster. My own impression was mostly that it felt "smoother" - no annoying pauses like we've been running into lately.

(Honestly, I'm amazed that cSuneido manages to handle as many users as it does. When I designed it I never thought it would. It's definitely benefited from Moore's law.)

Our current server is only a dual core machine with 6 gb of memory. It doesn't really have enough cores or memory for jSuneido to take advantage of. We're in the process of getting a new i7 server with 8 cores (counting hyperthreading) and 24 gb of memory (thanks Dorlan). That should be a better platform for jSuneido.

One of the main goals of jSuneido was to scale better to handle larger systems with more users. For smaller systems cSuneido uses less resources. But it can't take advantage of 64 bit systems with large amounts of memory and multiple cores. jSuneido can.

Three years of work to reach this point. Not full time, but close to half my time. That's a lot of hours. It feels good to reach this point. No doubt there will be issues to deal with, but that's to be expected. In many ways it's just a transition between phases of the project. With climbing, reaching the top is only half the battle, the other half is getting down. With software, writing it is only half the battle, the other half is running, fixing, maintaining, and improving it.

This kind of project definitely requires being able to handle deferred gratification. But just as important is to take pleasure in the work itself, as well as in the end result. If I didn't enjoy the day to day programming (most days anyway!) there's no way I would do it for the relatively small amount of final gratification.  It's not like anyone really understands what you've done or what it took to get there. The external rewards just aren't enough to justify something like this. The process itself has to be sufficient reward. Any pats on the back at the end are just icing on the cake.

I'm deliberately making a point of marking this milestone. It's good to celebrate small victories along the way. Too often they slide by and with no punctuation it can seem like just one long slog. It must have been an even bigger milestone when the original version of Suneido first went into production, but I can't even remember it. I remember thinking that I would reward myself with one of the brand new flat screen monitors (that dates it!). But I never did, because it never seemed like I was "finished" - there was always as much road ahead of me as there was behind. Here's to the road ahead.

ThreadPoolExecutor

I've been working with ThreadPoolExecutor and it's a little confusing so I thought I'd share my experience.

Some background - Executor is a simple interface:

An object that executes submitted Runnable tasks. This interface provides a way of decoupling task submission from the mechanics of how each task will be run, including details of thread use, scheduling, etc. An Executor is normally used instead of explicitly creating threads.

A ThreadPoolExecutor uses a pool of threads to execute the tasks. The trick is in configuring it. I wanted:

• no threads when it's idle
• a limited number of threads when it's busy
• a bounded queue

You have to read the documentation for ThreadPoolExecutor very carefully. Forget about your preconceptions of how it "probably" works. 

You can specify "core pool size" and "max pool size". Normally "core" threads do not time out. You also specify the type of queue (bounded, unbounded, or synchronous), and the rejection policy.

There are a couple of gotcha's. 

• Even if activity is very low and one thread could handle it, the full number of core threads will be created. 
• Even if activity is high and all the core threads are busy, additional threads will not be created until the queue is full. 

Both of these are because it's very hard to know if a thread is idle. 

They combine to lead to a common mistake - setting core size to 0 because you want all the threads to time out, and using an unbounded queue, which will never be full. Using a large queue is almost as bad because additional threads won't be created until that many requests are queued up - ouch!

Here's what I ended up with:

private static final int CORE_THREADS = 0;
private static final int MAX_THREADS = 8;
private static final int KEEP_ALIVE = 1;
private static final ThreadPoolExecutor executor =
     new ThreadPoolExecutor(CORE_THREADS, MAX_THREADS,
          KEEP_ALIVE, TimeUnit.MINUTES,
          new SynchronousQueue<Runnable>(),
          threadFactory, 
          new ThreadPoolExecutor.CallerRunsPolicy());

A SynchronousQueue is a zero size queue, it hands off items directly. Because its remainingCapacity is always zero, it is always "full", so up to MAX_THREADS will be created as needed.

Without a queue and with a maximum number of threads, it's possible that tasks will need to be rejected. By specifying the CallerRunsPolicy rejected tasks will be executed by the calling thread. This is a simple feedback mechanism that will throttle requests since the caller won't be able to accept additional requests while it's busy executing a task.

I chose MAX_THREADS of 8 to be a bit bigger than the expected number of cpu cores (to allow for some threads being blocked). In our actual usage one or two threads seem to be sufficient.

There is a standard Executors.newCachedThreadPool but the documentation isn't specific about what its configuration is. From other sources it appears quite similar to my configuration - zero core threads and a SynchronousQueue. However, it has unlimited MAX_THREADS instead of CallerRunsPolicy. In my case, I wanted to limit the number of thread because each holds some limited resources.

I'm not an expert on this stuff, so suggestions or criticisms are welcome.

Mockito

I've been reading Growing Object-Oriented Software, Guided by Tests. I write automated tests for my code, but I'm not especially good at it. Partly because I'm not very good at writing testable code. Which is partly because I don't usually code test first. My problem is that I know enough to know that I don't know enough!

Anyway, I decided I should try to clean up my act a little. I wanted to try using a mocking library. I did a few minutes of research and looked at a comparison between EasyMock and jMock. Then I ran across Mockito and it looked simple and easy to use.

I added the jar to my project and wrote my first test with it. No problems and very easy to use.

But it's never that easy. I ran my build, which uses Proguard, and got a ton of errors and warnings :-(

I probably could have fixed them, but I took the easy way out and just configured my build to exclude the tests. I only ever run them from Eclipse anyway. It's not the ideal solution but it'll do for now.

In the process I cleaned up my Ant build file. When I first created it I was even more ignorant about Ant and Java and Proguard than I am now.

I've revised a few more tests to use Mockito and I'm quite happy with it. If you're programming in Java and aren't using a mocking library, give it a try.

Management

A few days ago I fired one of my programmers. It's one of the parts of my "job" that I could do without. Thankfully, I've only had to do it a few times. He's been with us quite a while, and although I was never quite happy with his work, there were alway extenuating circumstances and I kept hoping things would turn around. Eventually, I had to admit that it probably wasn't going to get any better.

It went about as well as these things can. No arguments, no tears. He actually admitted he really hadn't been very interested in the work. I hope he can find work that does motivate him. We all spend too much of our lives at work to waste it doing stuff we don't enjoy.

Despite being a partner in a small business with 40 employees I'm not much of a "business man" or manager. I've learnt enough to get by and I do as little as I can responsibly get away with. If it starts to take too much of my time I get unhappy. I'm still a programmer at heart, and if I spend a day at the office without writing a line of code I get grouchy. And no, answering coding questions and reviewing code doesn't count!

I'm lucky to have a partner who's happy (or at least willing) to look after the business and marketing and sales side. And lucky to have programmers (and a customer support team) who do a great job without a great manager.

I Give Up

I spoke too soon with my Hamcrest post. I was getting a clean compile and build, but when I ran the tests I got a security exception!

Based on what I found on the internet, this is because the hamcrest-core supplied by Eclipse is signed, but the hamcrest-library I downloaded separately isn't.

The suggested solutions is to make sure the unsigned one is first on the Eclipse build path. But mine was already first. I tried playing around with the order but it didn't help.

So I gave up and removed hamcrest-library. I'll just live with the matchers in the hamcrest-core supplied by Eclipse. I've wasted enough time and mental energy already.

Sometimes this stuff is just not as easy as it should be :-(

It's a good reminder of how much using Suneido simplifies life for my developers. (Not that they would agree that their life is simple!) The downside is that we don't have access to all these third party tools and libraries. But the huge upside is that we don't have to fight to integrate all those disparate pieces.

Eclipse Hamcrest Runaround

I started reading Growing Object-Oriented Software and it talked about using the Hamcrest matchers with jUnit. It sounded like a good idea so the next time I was writing a test I tried using them.

The first problem is where to import assertThat from. That turned out to be easy, it's in org.junit.Assert along with the normal assertEquals etc.

The next question is where to import the matchers like equalTo. I found that in org.hamcrest.Matchers.

Next I wanted a lessThan matcher but I couldn't find it.

It turns out jUnit only includes Hamcrest core which doesn't have lessThan. I searched on the internet and didn't find a lot of help. I found a question on StackOverflow that suggested replacing the Eclipse supplied junit and hamcrest-core with junit-dep and hamcrest-all

I tried this and at first it seemed to work ok. But then I went to build my jars and Proguard gave all kinds of errors about missing dependencies.

I've been meaning to look into Maven and it's supposed to handle dependencies, so I thought I'd give it a try. Since I'm using Eclipse I looked for an Eclipse add-on for Maven. I found one and installed it. Big mistake. Not only did it not help with the dependency problems (at least I couldn't figure out how) but it also messed up my project. No problem, I thought, I'll just uninstall it. Except it left a mess behind. I ended up restoring my Eclipse install, but I still had problems. I kept getting errors referencing maven but I couldn't find any references to maven in my project. Eventually I found that the launch configurations for your project are stored in the workspace, not in the project. (That doesn't make much sense to me, but I'm sure there's some good reason.) After I deleted those (easier than trying to fix them) things were back to before the Maven detour.

It said I was missing jMock and EasyMock so I went and found those jars and added them. But it still wanted some kind of Ant jar. That seemed like a little much.

I saw there were various other jars for Hamcrest but frustratingly, no explanation of them. (I did find someone had filed an issue that there should be an explanation, but no one had responded.) I downloaded the complete package and it contained a readme that gave some explanation. It looked like I wanted hamcrest-core and hamcrest-library rather than hamcrest-all.

That eliminated the dependencies on jMock and EasyMock and Ant. But I still got an error that junit was referencing something that was missing from hamcrest. I thought maybe it was a version issue, so I tried multiple versions of junit and multiple versions of hamcrest but no luck.

Then I realized that the junit supplied by Eclipse includes hamcrest-core. So maybe all I needed to do was go back to that, and then add hamcrest-library. Sure enough, that did the trick.

No doubt the junit and hamcrest and eclipse folks would say, of course, it's obvious. But it sure wasn't obvious to me.

jSuneido Immutable Database

I've made a good start on rewriting the jSuneido database as an immutable persistent data structure.

It's hard to know what to call it. Overall, it's not immutable, since you can add, update, and delete like any database. The "immutable" part is that once data is written to the database file it's never updated.

You could call it "append only" because you only ever append to the database file, never update. But again, that sounds like you can't update or delete, which you can.

I started bottom up, writing a persistent hash trie to store the redirections. This is similar to my persistent hash map but designed to be stored in the database file. I also rewrote my memory mapped file access, simplifying it a lot. Now I'm working on the btree code.

The code seems a lot cleaner this time. Of course, it always does at the beginning of a rewrite because you haven't handled all the details yet. But I'm still optimistic.

As usual I'm struggling with how much to optimize. The conventional wisdom is that you write the code and then if it's too slow you profile it and optimize the problem areas. But what is "too slow" in a language or a database? You always want as much speed as you can get (without sacrificing robustness and maintainability). And that wisdom assumes that speed problems will be localized. But if the slowness is spread diffusely through the code, then it's not so easy to optimize after the fact. It's a bit like saying you can add good design after the fact.

A big part of performance is the right algorithms. Another part is implementing those algorithms efficiently on your platform. If I can "cut with the grain" of Java I think I can do more with less.

I have a lot better handle on Java and the JVM than I did when I did the first implementation. And at that point I was simply trying to port the cSuneido code, not redesign it. Now that I have a working implementation I have the freedom to explore alternatives. And I'll have something to compare performance to.

It won't be till I get to the transaction code that I'll really see how this redesign will work out. I'm hoping that the immutability of the database will simplify transaction handling. We'll see.

The Joy of Programming

It's ridiculous how good I can feel after accomplishing a decent programming task smoothly. I almost feel a bit foolish getting pleasure from something so ... geeky. But it's a bit like a good run. It feels like you've done something worthwhile, even if it only benefits you.

Last evening, with the new MacBook Air on my lap, I cleaned up one of the last parts of the jSuneido compiler that I was uncomfortable with. I had already figured out what I wanted to do, and for once I didn't run into any unexpected problems, finishing tidily in the amount of time I had.

Previously, I'd been building a list of constants (other than strings and int's that Java handles) and then stuffing this list into the instance of the compiled class. Then, to speed things up in the generated code, I loaded an array of the constants into a local variable. It worked ok, but a lot of functions didn't need any constants. Unfortunately, I had to generate the load before I knew if there would be any. And it would be tricky to determine ahead of time if there would be any. Plus, ideally, constants should be static final so the optimizer would know they were constant.

With the new changes, I create a static final field for each constant, and then generate a  class initializer that initialized them. Accesses to the constants are simple GETSTATIC instructions. The only trick was how to get the list of constants from the compiler to the class initializer. I ended up using a static field (basically a global variable). A bit ugly, but I couldn't come up with a better way. To handle multi-threading I used a ThreadLocal. (My first thought was a ConcurrentHashMap keyed by ClassLoader, but ThreadLocal was simpler.)

I don't know how much difference this will make to performance, but I really wanted to generate code that was clean and similar to compiled Java. I think I'm pretty much there. (Apart from boxed integers and the extra layer of method/call dispatch.)

Damn! Reviewing the code as I write this I realize I missed something. (I use that list of constants in the instance for a couple of other minor things.) Oh well, can't take away how good I felt when I thought it had all gone smoothly! Good thing I'm not superstitious or I'd think I'd jinxed myself talking about how well it had gone :-) Hopefully it won't be too hard to handle.

jSuneido Catching Up with cSuneido

It's been a while since I paid attention to the relative speed of jSuneido versus cSuneido. I just realized that with my recent optimizations, jSuneido now runs the standard library test suite in pretty much the same time as cSuneido.

In some ways that's not surprising, the JVM is a sophisticated platform - the garbage collector is very fast and multi-threaded, the JIT compiles to optimized machine code, etc.

On the other hand, Java forces a lot more overhead than C++. Integers have to be boxed, classes can only be nested by reference not embedding, you can't use pointers, you can't allocate objects on the stack, and so on. It's impressive that the JVM can overcome these "drawbacks".

It's nice to reach this point. And a nice confirmation that I wasn't totally out to lunch deciding to use Java and the JVM to re-implement Suneido.

Of course, the real advantage of jSuneido over cSuneido is that the server is multi-threaded and will scale to take advantage of multiple cores.

informIT eBooks

As I've written before (here and here), I prefer to buy ebooks without DRM, not because I want to pirate them, but because dealing with DRM is a pain in the you-know-where, especially when you have multiple devices you want to access them from.

This is (as far as I know) almost impossible for mainstream books. But for computer books it's not too bad. Both Pragmatic Programmers and O'Reilly sell DRM free ebooks. And I've recently started buying ebooks from informIT (mostly Addison-Wesley ones).

The other issue with ebooks is format. The Kindle currently only handles mobi and pdf. And pdf's are generally painful to read on ebook readers because they have a fixed, usually large (e.g. 8.5 x 11) page size, with big margins. Because of this I bought one of the bigger 9.7" Kindle DX's, and it helps, but it's still not great.

The Kindle helpfully trims white margins on pdf's, but the problem is that the ebooks informIT is providing are images of the paper books so they have stuff like page numbers and titles in the top and bottom margins which prevent trimming from working properly. And worse, the stuff in the margins is not symmetrical so odd pages end up trimmed differently than even pages which means the zoom level keeps changing. Not the end of the world, but annoying.

Both Pragmatic and O'Reilly provide ebooks in epub, mobi, and pdf. But informIT only provides epub and pdf. At first I made do with the pdf's but eventually I got fed up and started looking for alternatives.

I thought about looking for some tool to process the pdf's and crop the margins. But that's not the only problem. Kindle doesn't let you highlight sections of text in pdf's, only in mobi. And the pdf's I've had from informIT haven't had any hyperlinks (e.g. from the table of contents) although pdf's are able to do that.

I took a look at the epub's from informIT and they seemed better, at least they were hyperlinked. So I looked for tools to convert epub to mobi. Stanza was one that was suggested and I already had it installed so I gave it a try. I like Stanza but it didn't do a very good job of converting these epubs to mobi.

The other tool that was suggested was Calibre. A plus for Calibre is that it's an open source project. The user interface is a little confusing but it did a great job of converting epub to mobi, including the cover image and hyperlinks. And it even recognized when I plugged in my Kindle and let me copy the books over. I downloaded the epub versions of all my informIT books and converted them - a big improvement.

I wish I'd got fed up sooner! I could have avoided a lot of painful pdf reading.

Although I'm happy to be able to get Addison-Wesley ebooks from informIT, I do have a minor complaint - their sleazy marketing. I got an email offering me a limited time 50% off deal. Sounded good to me so I found a few books I'd been planning to get. They came to something like $80. When I entered the 50% off code the price only dropped to around $70. That's a very strange 50%. Looking closer I found that you normally get 30% off, and over $55 it goes up to 35%. So the 50% deal was only 15% better than usual. I realize this is a common marketing scam, but it still annoys me. O'Reilly plays some similar games but not quite as bad.

jSuneido Compiler Optimizations

For my own reference, and to justify my month of work, I thought I'd go over some of the optimizations I've done recently. The changes involve:

• how functions/methods/blocks are compiled
• how calls are compiled
• the run-time support code e.g. in Ops, SuValue, SuClass, SuInstance, etc.

My original scheme was that arguments were passed in an array i.e. in the style of Java's variable arguments. For simplicity additional local variables were also stored in this array. This had a nice side benefit that the array could be used to capture the local variables for blocks (aka closures).

The downside is that every call had to allocate an argument array, and often re-allocate it to accommodate default arguments or local variables. And access to variables requires larger and presumably slower code. (ALOAD, ICONST, AALOAD/STORE instead of just ALOAD/STORE)

To keep the calling code smaller I was generating calls via helper functions (with variations for 1 to 9 arguments) that built the argument array. One drawback of this approach is that it added another level to the call stack. This can impede optimization since the Hotspot JVM only in-lines a limited depth.

The first step was to compile with Java arguments and locals for functions (and methods) that did not use blocks.

Then I realized that if a block didn't share any variables with its containing scope, it could be compiled as a standalone function. Which is nice because blocks require allocating a new instance of the block for each instantiation, whereas standalone functions don't since they are "static". And it meant that the outer function could then be compiled without the argument array. Determing if a function shares variables with blocks is a little tricky e.g. you have to ignore block parameters, except when you have nested blocks and an inner block references an outer blocks parameter. See AstSharesVars

Where I still needed the argument array I changed the calling code to build it in-line, without a helper function. This is what the Java compiler does with varargs calls. Generating code that is similar to what javac produces is a good idea because the JVM JIT compiler is tuned for that kind of code.

One of the complications of a dynamic language is that when you're compiling a call you don't know anything about what you'll end up calling.

On top of this, Suneido allows "fancier" argument passing and receiving than Java. This means there can be mismatches where a call is "simple" and the function is "fancy", or where the call is "fancy" and the function is simple. So there needs to be adapter functions to handle this. But you still want a "simple" call to a "simple" function to be direct.

Each Suneido function/method is compiled into a Java class that has Java methods for simple calls and fancy calls. If the Suneido function/method is simple, then it implements the simple method and the fancy method is an adapter (that pulls arguments out of a varargs array). (for example, see SuFunction2, the base class for two argument functions) If the Suneido function/method is fancy, then it implements the fancy method and the simple method is an adapter (that builds an argument array).

In cSuneido, all values derive from SuValue and you can simply call virtual methods. But jSuneido uses native types e.g. for strings and numbers. (To avoid the overhead of wrappers.) So you need something between calls and implementations that uses "companion" objects for methods on Java native types. For example, Ops.eval2 (simple method calls with two arguments) looks like:

Object eval2(Object x, Object method, Object arg1, Object arg2) {
    return target(x).lookup(method).eval2(x, arg1, arg2);
}

For SuValue's (which have a lookup method) target simply returns x. For Java native types it returns a companion object (which has a lookup method). lookup then returns the method object.

One issue I ran into is that now I'm using actual Java locals, the code has to pass the Java verifier's checking for possibly uninitialized variables. I ran into a bunch of our Suneido code that wouldn't compile because of this. In some cases the code was correct - the variable would always be initialized, but the logic was too complex for the verifier to confirm it. In other cases the code was just plain wrong, but only in obscure cases that probably never got used. I could have generated code to initialize every variable to satisfy the verifier, but it was easier just to "fix" our Suneido code.

The "fast path" is now quite direct, and doesn't involve too deep a call stack so the JIT compiler should be able to in-line it.

The remaining slow down over Java comes from method lookup and from using "boxed" integers (i.e. Integer instead of int). The usual optimization for method lookup is call site caching. I could roll my own, but it probably makes more sense to wait for JSR 292 in Java 7. Currently, there's not much you can do about having to use boxed integers in a dynamic language. Within functions it would be possible to recognize that a variable was only ever an int and generate code based on that. I'm not sure it's worth it - Suneido code doesn't usually do a lot of integer calculations. It's much more likely to be limited by database speed.

This Developer's Life

This Developer's Life - Stories About Developers and Their Lives

I just came across this podcast and started listening to it. So far I'm really enjoying it. It's nice to hear more of the human, personal side to "the software life". And I enjoy the music interspersed. Check it out.

I also listen to Scott's Hanselminutes but it's a totally different podcast, much more technical and Microsoft focused. (I use it to keep up on Microsoft technology, which I feel I should be aware of even if I tend to avoid it.)

Optimizing jSuneido Argument Passing - part 2

I think I've finished optimizing jSuneido's argument passing and function calling. The "few days" I optimistically estimated in my last post turned into almost a month. I can't believe it's taken me that long! But I can't argue with the calendar.

I gained about 10% in speed. (running the stdlib tests) That might not seem like much, but that means function call overhead was previously more than 10%, presumably quite a bit more since I didn't improve it that much. Considering that's a percentage of total time, including database access, that's quite an improvement.

When I was "finished", I wanted to check that it was actually doing what I thought it was, mostly in terms of which call paths were being used the most.

I could insert some counters, but I figured a profiler would be the best approach. The obvious choice with Eclipse is their Test and Performance Tools Platform. It was easy to install, but when I tried to use it I discovered it's not supported on OS X. It's funny - the better open source tools get, the higher our expectations are. I'm quite annoyed when what I want isn't available!

NetBeans has a profiler built in so I thought I'd try that. I installed the latest copy and imported my Eclipse project. I had some annoying errors because NetBeans assumes that your application code won't reference your test code. But include the tests as part of the application so they can be run outside the development environment. I assume there's some way to re-configure this, but I took the shortcut of simply commenting out the offending code.

I finally got the profiler working, but it was incredibly slow, and crashed with "out of memory". I messed around a bit but didn't want to waste too much time on it.

I went back to manually inserting counters, the profiling equivalent of debugging with print statements. I got mostly the results I expected, except that one of the slow call paths was being executed way more often than I thought it should be.

So I was back to needing a profiler to track down the problem. I'd previously had a trial version of YourKit, so this time I downloaded a trial version of JProfiler. It ran much faster than the NetBeans profiler and gave good results. But unfortunately, it didn't help me find my problem. (Probably just due to my lack of familiarity.)

I resorted to using a breakpoint in the debugger and hitting continue over and over again checking the the call stack each time. I soon spotted the problem. I hadn't bothered optimizing one case in the compiler because I assumed it was rare. And indeed, when I added counters, it was very rare, only occurring a handful of times. The problem was, those handful of occurrences were executed a huge number of times. I needed to be optimizing the cases that occurred a lot dynamically, not statically.

Although I only optimize common, simple cases, they account for about 98% of the calls, which explains why my optimizations made a significant difference.

One of my other questions was how many arguments I needed to optimize for. I started out with handling up to 9 arguments, but based on what I saw, the number of calls dropped off rapidly over 3 or 4 arguments, so I went with optimizing up to 4.

I can't decide whether it's worth buying YourKit or JProfiler. It doesn't seem like I want a profiler often enough to justify buying one. Of course, if I had one, and learnt how it worked, maybe I'd use it more often.

Append Only Databases

The more I think about the redirection idea from RethinkDB the more I like it.

The usual way to implement a persistent immutable tree data structure is "copy on write". i.e. when you need to update a node, you copy it and update the copy. The trick is that other nodes that point to this one then also need to be updated (to point to the new node) so they have to be copied as well, and this continues up to the root of the tree. The new root becomes the way to access the new version of the tree. Old roots provide access to old versions of the tree. In memory, this works well since copying nodes is fast and old nodes that are no longer referenced will be garbage collected. But when you're writing to disk, instead of just updating one node, now you have to write every node up the tree to the root. Even if the tree is shallow, as btrees usually are, it's still a lot of extra writing. And on top of the speed issues, it also means your database grows much faster.

The redirection idea replaces creating new copies of all the parent nodes with just adding a "redirection" specifying that accesses to the old version of the leaf node should be redirected to the new leaf node. A new version of the tree now consists of a set of redirections, rather than a new root. And you only need a single redirection for the updated leaf node, regardless of the depth of the tree. There is added overhead checking for redirection as you access the tree, but this is minimal, assuming the redirections are in memory (they're small).

One catch is that redirections will accumulate over time. Although, if you update the same node multiple times (which is fairly common) you will just be "replacing" the same redirection. (Both will exist on disk, but in memory you only need the most recent.)

At first I didn't see the big advantage of redirection. I could get similar performance improvements by lazily writing index nodes.

But the weakness of delayed writes is that if you crash you can't count on the indexes being intact. Any delayed writes that hadn't happened yet would be lost.

The current Suneido database has a similar weakness. Although it doesn't delay writes, it updates index nodes, and if the computer or OS crashes, you don't know if those writes succeeded.

The current solution is that crash recovery simply rebuilds indexes. This is simple and works well for small databases. But for big databases, it can take a significant amount of time, during which the customer's system is down. Crashes are supposed to be rare, but it's amazing how often it happens. (bad hardware, bad power, human factors)

Of course, you don't need the redirection trick to make an append only index. But without it you do a lot more writing to disk and performance suffers.

Even with an append only database, you still don't know for sure that all your data got physically written to disk, especially with memory mapped access, and writes being re-ordered. But the advantage is that you only have to worry about the end of the file, and you can easily use checksums to verify what was written.

On top of the crash recovery benefits, there are a number of other interesting benefits from an append only database. Backups become trivial, even while the database is running - you just copy the file, ignoring any partial writes at the end. Replication is similarly easy - you just copy the new parts as they're added to the database.

Concurrency also benefits, as it usually does with immutable data structures. Read transactions do not require any locking, and so should scale well. Commits need to be appended to the end of the database one at a time, obviously, but writing to a memory mapped file is fast.

Another nice side benefit is that the redirections can also be viewed as a list of the changed nodes. That makes comparing and merging changes a lot easier than tree compares and merges. (When a transaction commits, it needs to merge its changes, which it has been making on top of the state of the database when it started, with the current state of the database, which may have been modified by commits that happened since it started.)

Ironically, I was already using a similar sort of redirection internally to handle updated nodes that hadn't been committed (written) yet. But I never made the connection to tree updating.

I love having a tricky design problem to chew on. Other people might like to do puzzles or play computer games, I like to work on software design problems. I like to get absorbed enough that when I half wake up in the night and stagger to the bathroom, my brain picks up where it left off and I start puzzling over some thorny issue, even though I'm half asleep.

The Deep Threat

"It was an illuminating moment: the deep threat isn’t losing my job, it’s working on something for which I lack passion."

- John Nack

Social Search?

"search is getting more social every day and tomorrow's recommendations from people you know via Facebook are infinitely more valuable than search results from yesterday's algorithm"
- Publishing needs a social strategy - O'Reilly Radar:

Really? What kinds of searches are we talking about? When I search for some technical question or someone searches for e.g. a solution to an aquarium problem, is Facebook really going to help? Personally, I think I'd rather have "yesterday's algorithm".

Sure, if I'm looking for something like a restaurant recommendation then I'd be interested in what my friends have to say. But unless you have a huge, well travelled circle of friends, how likely is it that they'll have recommendations for some random city you're in? And if the recommendations aren't coming from friends, then we're back to regular search.

This "everything is social" craze drives me crazy. Believe it or not, Facebook is not the ultimate answer to every problem.

Goodbye Google App Engine

Goodbye Google App Engine

Definitely a different picture than Google paints.

I would think twice about using Google App Engine after reading this.

Maybe we'll just stick with Amazon EC2

Optimizing jSuneido Argument Passing

Up till now jSuneido has always passed arguments as an Object[] array, similar to a Java function defined as (Object... args)

Suneido has features (e.g. named arguments) that sometimes requires this flexible argument passing. But most of the time it could use Java's standard argument passing.

I've wanted to optimize this for a while, and it was one of the motivations for the compiler overhaul (see part 1 and part 2).

Having finished adding client mode, I sat down to start working on optimizing argument passing. When I started to think about what was required, it began to seem like a fair bit of work.

I decided that first I should determine if the change was worthwhile. (In the back of my mind I was thinking it probably wouldn't be that much better and I wouldn't have to implement it.)

First I measured what percentage of calls were simple enough to optimize. I was surprised to see it was about 90%. But it makes sense, most calls are simple.

Next I measured what kind of improvement the optimization would give. For a function that didn't do much work, I got about a 30% speedup. (Of course, for functions that did a lot of work the argument passing overhead would be negligible and there would be little or no speedup.)

Those figures were just from quick and dirty tests but I was only looking for rough orders of magnitude results.

The changes avoid allocating and filling an argument array and also avoid the argument "massaging" required for more complex cases. The calls are simpler and use less byte code. This means they have a better chance of being inlined by the JVM JIT byte code compiler. The calls are also more similar to those produced by compiling Java code and therefore have a better chance of being recognized and optimized by the JIT compiler.

To me, these numbers justified spending a few days making the changes. Thankfully, I was able to implement it in a way that allowed me to transition gradually. So far I have optimized the argument passing for calling built-in functions. I still have some work to do to handle other kinds of calls, but the general approach seems sound. I don't think it'll be quite as bad as I thought.

You can see the code on SourceForge

One Bump in an Otherwise Smooth iMac Upgrade

I recently upgraded my 24" Core 2 Duo iMac to a 27" i7 iMac.

My usual rule of thumb is not to upgrade till the new machine will be twice as fast as the old one. But that rule is getting harder to judge. For a single thread, the i7 is not twice as fast. But with 8 threads (4 cores plus hyper-threading) it definitely has the potential to run much more than twice as fast. The iPhone MacTracker app shows the new machine with a benchmark of 9292 versus the old machine at 3995. I'm not sure what benchmark that's using.

I've been thinking about upgrading for a while but as winter arrives and I spend more time on the computer, I figured it was time. Another motivation for the upgrade was to be able to test the multi-threading in jSuneido better.

I really wanted to get the SSD drive to see how that would affect performance. But that option is still very expensive. Especially since I'd still need a big hard drive as well for all my photographs. So I didn't go for it this time. I'm not sure how big a difference it would have made for me. My understanding is that it mostly speeds up boot and application start times. But I generally boot only once a day and tend to start apps and then use them for a long time. It would be interesting to see how Suneido's database performed on an SSD.

I did upgrade from 4gb of memory to 8gb. Most of the time 4gb is fine, but when I run two copies of Eclipse (Java and C++), Windows under Parallels, Chrome with a bunch of tabs, etc. then things started to get noticeably sluggish. With the new machine things don't seem to slow down at all. And I can allocate more memory and cores to my Windows virtual machine. I also upgraded from a 1tb hard disk to 2tb. I hadn't filled up the 1tb, but I figure you can never have too much hard disk space and the cost difference wasn't that big.

Migrating from one machine to the other went amazingly smoothly and quickly - the easiest migration I've done. With Windows machines I never try to migrate any settings or applications since you need to clean everything out periodically anyway. I'm sure even with OS X there is a certain amount of "junk" accumulating (e.g. old settings) but it doesn't seem to cause any problems.

I used OS X's migration tool but I wasn't sure what method to connect the machines - Firewire, direct network connection, network via LAN, or via Time Machine backup. In the end I went with migrating from the Time Machine backup, partly because it didn't tie up my old machine and I could keep working.

Some estimates from the web made me think it might take 10 or 20 hours to migrate roughly 600gb, but it was closer to 2 hours - nice.

The one speed bump in this process was my working copy of jSuneido. I keep this Eclipse workspace in my DropBox so I can access it from work (or wherever). Because I migrated from a Time Machine backup, my new workspace was a few hours out of date. DropBox on the new machine copied these old files over the newer ones. Then DropBox on the old machine copied the old files over it's newer ones. So now both copies were messed up. No big deal - DropBox keeps old versions, I'd just recover those. Except I couldn't figure out any easy way to recover the correct set of files without a lot of manual work. (I could only see how to restore one manually selected file at a time, with no way to easily locate the correct set of files that needed to be restored.) No problem - I'd get the files back from version control. Except for some reason I couldn't connect to version control anymore. Somehow the unfortunate DropBox syncing had messed up something to do with the SSL keys. Except the keys were still there since I could check out a new copy from version control. Eventually, after a certain amount of thrashing and flailing I got a functional workspace. I still ended up losing about 2 hours of work, but thankfully it was debugging work driven by failing tests and it didn't take long to figure out / remember the changes.

Although the new 27" display is only about 10% bigger than the old 24", the resolution has increased from 1920 x 1200 to 2560 x 1440 - almost a third bigger, and quite a noticeable difference. But because of the higher DPI resolution, everything got smaller. As my eyes get older, smaller text is not a good thing!

After all these years, with all the changes in display sizes and resolutions, you'd think we'd have better ways to adjust font sizes. Most people simply resort to overriding the display resolution to make things bigger, but that's a really ugly solution. But I can see why they do it. There's no easy way in OS X to globally adjust font sizes. You can only tweak them in a few specific places. Windows is actually a little better in this regard, but still not great. And even if you manage to change the OS, you still run into applications that disregard global settings.

And history continues to repeat itself. iPhone apps were all designed for a specific fixed pixel size and resolution. Then the iPad comes along and the "solution" is an ugly pixel doubling. Then the higher resolution retina display arrives and causes more confusion. When will we learn!

Even Eclipse, that lets you tweak every setting under the sun, has no way to adjust the font size in secondary views like the Navigator or Outline. This has been a well known problem in Eclipse since at least 2002 (e.g. this bug or this one) but they still haven't done anything about it. I'm sure it's a tricky problem but how hard can it be? Is it really harder than all the other tricky problems they solve? Surely there's something they could do. Instead they seem to be more interested in either denying there's a problem, arguing about which group is responsible for it, or reiterating all the reasons why it's awkward to fix.

Of course, it's open source, so the final defense is always - fix it yourself. Sure, I'll dive into millions of lines of code and find the exact spot and way to tweak it. I think it might be just a little easier for the developers that spend all there time in there to do it. I won't ask them to fix the bugs in my open source code, if they don't ask me to fix the bugs in their open source code.

On the positive side, Eclipse's flexibility with arranging all the panes virtually any way you want lets me take advantage of the extra space. It's a little funny though, because even with a big font, the actual source code pane is only about 1/3 of the screen. It's nice to have so many other panes visible all the time, but there are times when it would be nice to hide (or "dim") all the other stuff so I could focus on the code.

All in all, I'm pretty happy with the upgrade.

Note: No computers were killed in this story :-)  Shelley is taking over my old iMac and her nephew is taking over her old Windows machine.

Giving Up on Amanda

For the last few months we've been trying to implement Amanda for backups in our office.

The two main choices for open source backups seem to be Amanda and Bacula. Amanda was supposed to be easier to set up than Bacula so that's what we chose. (There are also commercial options but they tend to be expensive and even less flexible.)

Unfortunately, it hasn't gone smoothly. Every time we think we have it working it starts failing semi-randomly. Certain workstations will fail some nights with cryptic errors, then work other nights without us changing anything.

We've had some support from the Amanda community. At one point they suggested running a new beta version which appeared to solve some problems, but not all of them.

To add to the problems, when we upgraded Linux, Amanda broke. That's certainly not unique to Amanda, but it's yet another hassle.

I'm sure Amanda works well for a lot of people. Presumably there's something different in our server or network or workstations that leads to the problems. But that doesn't help us. We have a medium size network of about 60 machines - not small, but not especially big either. We're not Linux experts, but we're not totally newbies either.

I'm sure we could solve the current problems eventually, but I've lost confidence. It just seems like we'd have to expect more problems in the future. And it's complex enough that if the person that set it up wasn't here, we'd be lost.

For some things this might be acceptable, but for backups I want something that "just works", that I can count on to be reliable and trouble free. For us, Amanda just doesn't appear to be the answer.

For the last ten years or so we've been using a home-brew backup system. It's simple, but that's a good property. It has reliably done the job. And when we needed to adjust it we could. And it was simple enough that even unfamiliar people could dive in and grasp what it was doing and figure out how to change it or fix it.

The reason we tried to move to Amanda is that we wanted to improve our system. Currently we rely on the server "pulling" backups via open shares. But for security we want to get rid of the open shares which means the workstations have to "push" backups. At the same time, we wanted to start encrypting backups on the workstations. In theory Amanda will do what we want.

I finally decided to pull the plug on trying to use Amanda. And as crazy as it might sound, we're going to try building a new home-brew system. I don't think it'll take us any more time than what we spent on trying to use Amanda.

You might think backups are too critical to trust to a home-brew system. But I'm more willing to trust a simple transparent solution that I understand, rather than someone else's complex black box. (Technically Amanda's not a black box since it's open source, but practically speaking we're not likely to spend the time to figure out how it works.)

And of course, we'll use Suneido to implement it. Suneido actually fits the requirements quite well - we can use it for a central server database, and run a client on the workstations. It's small and easy to deploy, and of course, we're very familiar with it. We'll see how it goes.