The Software Life

On-line Database Compaction

2012-01-25T14:38:00.000-06:00

One of the weaknesses (at least in my mind) of Suneido's database is that it requires off-line compaction. i.e you have to periodically shut down the server and run a standalone compaction process.

Practically speaking, that hasn't been a big issue. With the mutable storage engine, database growth is relatively slow and you don't need to compact that often. Few of our customers run 24 x 7 so it's not a problem to shut down at night occasionally. Also, some of the updates we deploy have to be run single user anyway.

But with the immutable storage engine, even with my improved design, the database will grow faster, and require more frequent compaction.

It would sure be nice if you could compact on-line, in the background, while the server was running.

Thinking about my planned improvements, I realized this might now be relatively easy. (Actually, I think I could have used a similar approach before, it just became more obvious now.)

The basic idea is to use a read-only transaction, and its snapshot of the data base as of a certain point in time, to compact the database up to that point. (Just like the current off-line compaction.)

But since the database is active, you will probably have activity after that point. So then you reprocess any updates after your transaction and apply them to the new database. (This is similar to how crash recovery would reprocess updates that happened after the last good checkpoint.) When you "catch up", then you switch over to the new database (with some synchronization required).

There is a potential problem if the server is so busy that the compaction never catches up. In practice, the compaction could be scheduled at a slow time of the day, and most of our systems aren't continuously busy. In any case, this wouldn't "hurt" anything, other than performance. You could easily detect this situation and abort the compaction.

Although the server can continue to operate during the compaction, performance may be affected. (As it can be with our current on-line backups.) CPU time is usually not the problem these days. A bigger issue is that reading all the data can cause other working set data to be evicted from memory. One option may be to not use virtual memory to read the data. Then you're only competing for disk cache and not virtual memory space. What we've found with our on-line backups is that as long as you have lots of memory it's not a problem.

One benefit of building a new compacted database file (rather than compact in place) is that it is inherently crash proof, at least in the sense that if the server crashes, the current database won't be affected. The new database being created can simply be discarded.

In garbage collector terms this is equivalent to a "copying collector" i.e. it just copies the live data, rather than scanning all the data (live and dead) as, for example, a "mark-sweep" collector does.

Suneido does support on-line backups, taking advantage of snapshot isolation to make a consistent backup as of a certain point in time. With the append only immudb storage engine, another option would be to simply copy the bytes of the database file up to a certain point without paying any attention to interpreting the structure. If the data and indexes are in the same file, this would copy both. If they were in separate files you'd have the option of only copying the data (like the current on-line backup). However, this would still be somewhat larger than the current backup because it would include deleted records. On the other hand, it should be faster since it's just a bulk copy.

Note: These ideas, like my ideas for limiting database growth, are just ideas. I'm sure there are unseen complexities waiting to trip me up.

Problem or Opportunity?

2012-01-21T15:36:00.000-06:00

I started to get a little worried about the database growth problem with my immudb append-only storage engine for jSuneido. I could think of ways to reduce the growth a little bit, but not by much, and only at the cost of adding a bunch of complexity.

Was I going to have to throw out a year's work, when it seemed so promising? Having to throw out a few day's work is one thing, but a year? How could I have gone so far without seeing this problem? Especially since I knew perfectly well it was an issue with this approach.

I'm as much an eternal optimist as the next programmer, with a big enough ego to think I can solve most problems. But I'm also human with the standard intermittent feelings of inadequacy and stupidity. In other words, I was starting to worry. But I knew enough to give myself time to mull it over.

I was sitting eating lunch, reading a computer book when I started to think about the problem.

What if I wrote out the redirections as just a list of values? That would be a lot more compact than saving the changes to the hash trie. That would be fine while you were running because you'd still have the hash trie in memory. But what about restarting? How would you get the in-memory hash trie back? And how would you handle crash recovery?

It seemed like the problem wasn't so much the way I was saving the information, it was saving it so often, for every transaction. I did this so the on-disk data structure matched the in-memory data structure after every transaction commit.

But was that strictly necessary? What if you relaxed that constraint? What if you only wrote out all the extra information (btree nodes, redirections, db info) periodically? That would reduce the database growth a lot. You could then consider a continuum, from saving after every commit, to the opposite extreme of only saving when you shut down the server.

I realized that what I was thinking about was basically the idea of "checkpoints" - a standard database implementation technique. You could also think of it as simply deferring index writes to disk.

Crash recovery becomes a little harder - you'd have to start from the last good checkpoint and reprocess the data from transactions after that. Similar to how other database crash recovery reprocesses logs from the last checkpoint. This isn't quite as elegant or simple as being able to simply pick up from the last good commit, but crashes don't happen that often. And it was still a lot better than having to rebuild all the indexes after a crash as Suneido requires with the current mutable storage engine.

The beauty of this solution is that it doesn't require a lot of changes. The immutable persistent in-memory data structures and the code that uses them stays exactly the same. You just don't save it as often.

Of course, taanstaafl. The cost of this approach would be higher memory usage. Once the index changes are saved to disk you don't have to keep the in-memory versions. Obviously, if you don't save to disk, you do have to keep the in-memory versions. However, the memory cost is much less than the disk growth because the memory will be garbage collected. Memory is cheap and jSuneido assumes you have lots. (For small systems with limited memory, cSuneido is a better choice.)

Another benefit from saving after multiple transactions is that there can be considerable overlap. For example, if there are "hotspots" in the data that are frequently updated, you only save them once per checkpoint instead of once per commit.

So the commits would simply save the data records (inserts, updates, and deletes) to the database file, with no other information. The btrees would be updated in-memory only. Then periodically you would save a checkpoint with the btree and db info changes.

Thinking about it, I wonder if I needed the redirections with this approach. The point of the redirections is to save space by not path copying to the root. But periodic checkpoints may save enough space that redirections aren't as important. Eliminating them would definitely simplify the code - always a good thing!

I also realized that I could even write the checkpoints in a separate concurrent thread since they could use the persistent immutable data structures to view the state as of a certain point in time (just like transactions do) without any concurrency issues and without blocking ongoing database activity. The only trick would be coordinating writing to the database file. Even that coordination could be avoided if you wrote the checkpoints (i.e. the index btrees) to a separate file from the data. Although I like having everything in one file, it's certainly not essential.

They say that creative problem solving is a lot about combining known, existing pieces into new combinations. I had all the pieces I needed to solve this problem, I just had to put them together. (Ironically, I talked about a lot of the same pieces almost two years ago in A Faster, Cleaner Database Design for Suneido)

And so I go from thoughts of a depressing major failure, to feeling like a kid with a new Lego kit :-)

Houston, we have a problem

2012-01-19T17:36:00.000-06:00

I thought things were going well with my new immudb append-only storage engine. It finally passed all our application tests, and performance was looking good.

Then I noticed the amount of database growth when I ran our full application test suite:

mutable storage engine = 20mb
immutable storage engine = 400mb

Ouch. I always expected it to use more space - that's the cost of immutable persistent data structures. But I didn't expect it to be 20 times as much.

With immutable persistent data structures in memory, the space is reclaimed by garbage collection. But so far the only form of garbage collection for database space that Suneido has had is offline compaction.

It's a little surprising that the performance is good, even on hard disk rather than SSD. I assume that's because sequential writes are actually quite fast. And also because it's using memory mapped file access so it's not blocking.

Given that the performance is ok, the database growth might even be acceptable. It might just mean compacting the database nightly instead of weekly as we currently do. However, presumably the performance would be even better if it wasn't writing so much.

I think it's worth spending some time to see if I can improve it. The first step was to see what the breakdown of the space was. (Note: these figures are growth, not total size.)

96820 update transactions
data space 11 mb
btree node space 140 mb
redirection space 89 mb
db info space 148 mb

If you look at the growth per transaction it's only about 4 kb. That doesn't sound too bad, until you have 100,000 transactions.

The btree node space could likely be decreased a lot (maybe half?) by compression of the nodes, perhaps something as simple as prefix compression.

Redirection is used to avoid path copying all the way to the root in the btrees. It's stored as an immutable persistent hash trie. Unfortunately, it does have to do path copying itself and that may be part of the problem.

I also noticed that each subsequent run used more redirection space. That's a little curious because it's doing the same set of updates each time. However, as the total number of redirections grows, then path copying will grow.

The "db info" is another hash trie containing aggregate data about each table and index. The information is used for query optimization. It could use redirection instead of path copying but currently it doesn't because it's using the same hash trie implementation as the redirections. It currently stores a "blob" of information for each table.

One improvement would be to delete redirection and db info when a table or index is destroyed. However, this would help the tests more than actual application usage, since the tests create and destroy lots of temporary tables. This might mean actual application usage would not show as high database growth as the tests.

I'm not sure what to try first. It's too bad the space is coming from three similarly sized sources. If the majority had come from one source then that would be the obvious place to start. There's always a chance that there are bugs or design flaws causing part of the problem. Another variable to try adjusting is btree node size.

* You could argue that our application test suite ideally shouldn't be hitting the database at all. But that's not relevant to this post.

** The title of this post comes from Apollo 13

jSuneido immudb milestone

2012-01-12T21:05:00.000-06:00

As of today, my new append-only storage engine for jSuneido (immudb) successfully runs all our application tests. Of course, there are probably still bugs, but it's a big milestone.

And it runs the standard library portion of the tests roughly twice as fast as with the previous storage engine. It also loads databases from a dump roughly twice as fast. And crash recovery is hugely faster.

Overall, I'm pleased with how it's worked out, other than the transactions issues I posted about recently.

As usual, I was surprised when I looked at how long it's been since I started on this - almost exactly a year! Of course, I wasn't working on it full time, and I had to do quite a lot of refactoring on jSuneido to allow pluggable storage engines, but still a lot of work.

Next, I'm planning to work on the transaction issues. Hopefully that won't take a year!

See also: all the posts related to immudb

Suneido Database Transaction Puzzle

2012-01-08T17:04:00.000-06:00

When we converted the first large customer to jSuneido we ran into a lot of transaction conflicts. A lot more than we had with cSuneido. The question was why? (Note: jSuneido is working well, without many conflicts, both in-house and at a smaller client - this problem only showed up under heavy use.)

[Disclaimer - this post is largely to clarify and review my own thinking. My apologies if it's somewhat cryptic.]

A lot of the conflicts could be traced back to application issues that we could fix e.g. having an alert inside a transaction (so the transaction was kept open too long) or not retrying.

But there were still too many conflicts. I ended up adding an option for snapshot isolation rather than serializable snapshot isolation. That eliminated most of the conflicts, but it opens up the potential for inconsistencies and I'm not really happy with it.

My initial assumption was that jSuneido was more "strict" than cSuneido and that was why there were more conflicts. jSuneido implements the algorithm from Serializable Isolation for Snapshot Databases by Cahill, Rohm, and Fekete [CRF], whereas cSuneido does "read validation" i.e. when a transaction commits it verifies that all of its reads are still valid.

But when I thought about the two approaches, I realized that cSuneido's read validation is actually more restrictive than jSuneido's CRF algorithm. Read validation requires transactions to serialize as of their commit time, whereas CRF allows re-ordering (as long as there are no dependency cycles that would prevent it). Otherwise, they are basically doing the same thing.

So I was back to trying to figure out why jSuneido was getting more conflicts.

The CRF approach does admit some "false positives" i.e. spurious conflicts that are not really conflicts. Because it's an "incremental" approach, the conflict flags can get set by transactions that don't end up overlapping or that later abort. As the rate of conflicts rises, this effect will get worse. It's possible this accounts for some of the jSuneido conflicts but I don't think it's the main reason. (Note: cSuneido's read validation only looks at committed transactions so it doesn't degrade in this fashion.)

One major difference is that jSuneido tracks reads and writes by B-tree index node rather than by individual record. This handles phantoms and simplifies merging transaction updates, but it can lead to more conflicts. For example, if a table only has only a few rows, then all updates will be in the the same B-tree node and overlapping transactions will always conflict. Similarly, appending keys at the end of an index is likely to conflict due to updating the same node.

cSuneido handles phantoms by tracking the index ranges that a transaction reads. Read validation then checks whether any concurrent writes from other transactions fell within those ranges.

My current thinking is that tracking reads and writes by B-tree node is what accounts for jSuneido getting more conflicts, although I don't have an easy way to "prove" this. If I'm correct, then the solution is to track index ranges rather than B-tree nodes. But, that's not so easy with CRF since it uses read locks on items - harder to do with ranges. And you have to deal with concurrent changes to B-tree nodes, which would require a complex tree merge.

So I think I'll probably go back to read validation instead of the CRF approach. It does mean more work during commits, and since commits are single-threaded, that will reduce the concurrency of commits. On the other hand, CRF required access to shared locks which reduces the concurrency of reads and writes. And if commits did turn out to be a bottle-neck, I think it would be relatively easy to multi-thread the commit process e.g. using one task per index. (Since indexes are independent, this should parallelize well.)

But it still leaves the question of how to handle concurrent B-tree updates if I'm no longer "locking" nodes. One approach I've been considering is to delay updating the actual "master" B-tree indexes until a transaction commits. Then the updates are single-threaded and there are no concurrent updates to deal with. Again, this puts more work into the commit, but I think this can be addressed as above.

(cSuneido handles this issue by keeping multiple versions of keys in the B-tree nodes. But this is tricky and doesn't fit well with the append-only approach that I'm concentrating on.)

However, transactions still need to "see" their own updates, so you'd have to have some kind of additional per-transaction indexes that you would transparently "merge" with the master ones. These could be B-tree indexes, but since they are in-memory, there are probably better data structures. One possibility is a "merge tree". I called this a "fractal tree" in a couple of blog posts (here and here) but the simple structure I'm talking about is not really the same as Tokutek's fractal tree. Since those blog posts I wrote an improved version (MergeTree.java) which I'm now using for temporary indexes required by queries.

A merge tree will be fast for inserts (faster than a B-tree) but slower for lookups. Accumulating updates in a per-transaction merge tree and then applying them to the master B-tree during commit will also have the side benefit of applying the updates to the B-tree in sorted order, which is optimal for B-trees.

Thinking about this, I have an idea for another potentially large optimization. Serializability really only cares about the records that the application sees. This is not the same as the records that the low level query execution reads. For example, if you have an index on fields a,b,c and you query on b, the low level code will scan the entire index, perhaps only returning a few records (possibly none). If you just track the index range that was read by the low level code, then it will appear that all the records were read. This will mean a much greater chance of conflicts than if you tracked the records that the application actually received.

However, I don't want to mix levels and have the query execution code worry about transaction read tracking. I think what I can do is have the query code pass a "black box" predicate to the low level database code. Then the transaction read validation can use the predicate when validating reads. i.e. writes by other transactions that do not match the predicate cannot have been seen and can be ignored.

One remaining issue is "bulk" updates since none of these approaches are great for updating a huge number of records. It may be reasonable to allow the application code to "lock" a table. This would prevent concurrent updates, and would allow updating the master B-trees directly, without accumulating updates in memory.

The problem with all of this is that it relies on an embarrassing amount of guess work and seat of the pants intuition. (Based on a fair bit of experience, but even experienced intuition is probably wrong as often as it's right.) Ideally, you'd test out these ideas before jumping into implementing them. But it's just not feasible. Any one of these issues would make a good research project. And even then, you'd only have analyzed a single issue - not how it relates to all the other issues.

The solution space is just too large. Which, of course, is also what makes it fun. It would be pretty boring if it was simple enough to analyze exhaustively, and have no questions about the best approach. The chances of me stumbling on a solution that is better than what is out there is slim, but at least it exists.

The timing actually isn't too bad. I'm just finishing up debugging the append-only storage engine. (So far, the performance looks promising, perhaps as much as twice as fast.) Once I finish that I can take a look at these transaction ideas and see what I can do.

Installing the Energy Detective

2012-01-02T15:07:00.000-06:00

It's been an adventure installing the TED 5000 home energy monitor that I got to complement my new solar PV system. (See my Sustainable Adventure blog posts: Solar Powered and Rock Paper Sun.) I'm putting this post on my computer blog because it's more on the technical side. Sorry, it's a long post, I won't be offended if you don't read it. If nothing else, I'm hoping it might help other people with their installations.

I was nervous about installing it in the first place, because I'm not really comfortable messing around in the house breaker box. It didn't help that my last encounter with the house electrical system was when I tried to drill a hole through the back of a closet to run a network cable and managed to hit the electrical wiring inside the wall and short it out. (Annoying Shelley since it left her office without power.) But it's supposed to be straightforward, and I'm supposed to be a technical person. (If I'd been smarter I would have had the electrician install it when they installed the solar panels.)

You have to shut off the main breaker to the house, which means no lights. A headlamp is very handy.

I had to install two MTU's (Measuring and Transmission Units) each with two CT (Current Transformer) sensors that clamp over the power wires, plus a Gateway unit that connects to your network.

My breaker box has two sections - an upper part with the main breaker, and a lower part with all the house breakers. I assume the idea is that you shut off the main breaker and then you can work in the lower section with no danger. Except I couldn't fit the main CT clamps in the lower section - the only place I could fit them was in the upper section. (where the power is still live on the external side of the main breaker)

I initially only installed the main (usage) MTU because the solar instructions showed two different configurations and I wasn't sure which one I had, which meant I wasn't sure which wires to put the solar CT clamps on, or even if I was supposed to install it in the house breaker box, or outside in the solar breaker box.

Next I had to find an empty power outlet (ideally not too distant from the breaker box) for the Gateway unit. It also had to be close enough to connect to my router. I used the same outlet that my solar panel monitoring unit was plugged into. Both it and the TED gateway use power line communications. (Filling up this outlet didn't make me popular because it was the one that Shelley had been using to plug in chargers for gadgets.)

Of course, my Apple Time Capsule router did not have any more free ports. (I used up the last one for the solar system.) So I had to run out and pick up a switch to get more ports.

Thankfully, I didn't have any trouble with the power line communications, as many people seem to. It probably helps that the office is at the same end of the house as the breaker box. I also remembered reading Jon Udell's blog post about installing a TED. The problem is that some of the TED instructions say to connect the black and the red wires, and some of the instructions say to connect just the black wire. (Not the only issue with their instructions.) Apparently, you should only connect the black one. In which case, why do they have the red one? Are there circumstances when you'd want to connect the red one?

The other thing the printed instructions don't mention is that if you only connect the black wire, then you have to specify that in the configuration. i.e. the default in the configuration doesn't match the instructions, sigh. This issue is fairly obvious because the voltage reads 60 instead of 120 V. Still, it took me a while to discover the setting. At first I assumed I had installed something wrong.

The final step is to connect to the system from your computer. This was a little confusing. It seemed to be a browser based interface, but the instructions also told you to download and run their "installer". I'm always reluctant to install software like this unless I really have to, especially since a lot of the time it's totally unnecessary (like the software that comes with your camera). The instructions said to connect to http://ted5000 with your browser but that didn't work. So I gave in and ran their "installer", which turned out to NOT be an installer at all - it's just a utility that locates the IP address that your Gateway is on.

After all that, it seemed to be functional!

At first, I didn't think it was that critical to monitor the solar system, since it had it's own monitor. But then I realized that I still wasn't really measuring the household energy usage. Instead, I was measuring the "net" i.e. the usage minus the solar generation. And to make it worse, with the default settings for the main MTU, the system assumes that usage will always be positive. But with the solar system, that's plain wrong - when the sun's shining, my usage should be negative, but it was still showing as positive. The reason they do this (absolute value) is so it still works when people install the CT's backwards. (Of course, the instructions don't tell you any of this. I gleaned it from their forum.)

I eventually figured out that I had the first configuration in their solar instructions. I shut off the power and opened up the breaker box again. Eventually I managed to find the right wires in the rat's nest, get the clamps on them, and squeeze them into the box enough that I could get the cover back on. (If it was a suitcase, I'd be sitting on it to get it closed!)

In this configuration my main MTU is configured as "Adjusted Load". What they don't make clear is that this means it handles negative values, which means that suddenly it's critical to have the CT's the right way around. Of course, I had mine backwards. And of course, you don't discover this till you close everything back up and turn the power back on. The instructions tell you to leave the cover off till you verify the system is working, but it's such a tight squeeze getting my cover on, that I feel better doing it with the power off.

Part of the blame for getting them backwards lies in the instructions. The printed instructions that come in the box say to orient the red dots "towards the source of the power". As far as I can tell from my install, that's just plain wrong. The Installation Pictorial on the web site is better - it shows the red dots oriented the opposite way. But the text says to orient the red dots "towards the breaker". That's correct for their picture, but if you ended up putting the clamps on the other side of the main breaker (as I would have if there had been room), then the dots would not be facing the main breaker and the instructions would again be wrong. The video shows the dots the wrong way (AFAIK) and the voice over simply says "make sure you get them the right way", not very helpful.

So I had to reverse the main CT's, which meant opening both sections of the breaker box (you can't take the cover off the top part without first taking the cover off the bottom part) It's easy to put the clamps on the wires, but the main power wires are really heavy and stiff. Although there's a fair bit of room in the top section, it isn't easy to get the clamps turned so the cover will fit back on.

I'm probably overly paranoid, but I did most of this work with rubber soled shoes, gloves, and one hand in my pocket. I'm a belt and suspenders kind of a person, if you hadn't figured that out by now!

It's pretty obvious that getting the CT's backwards has been a common problem - not surprising given their instructions. You'd think by now they would at least have corrected and improved their instructions. They attempted to handle the issue by having the software ignore the polarity in the default configuration. But that just makes it worse in a more complex setup like mine. Why not just add a configuration option to reverse the polarity? I can't see why that would be difficult software-wise. And for customers it would sure be a lot simpler than opening everything back up to physically reverse them. Rather than ignore polarity, the default setup could simply detect the polarity and adjust the setting automatically. Then you wouldn't need confusing instructions about red dots at all.

Finally, I think it's all working properly! Usage shows positive, solar generation shows negative, and the net is either positive or negative depending on whether I'm generating more than I'm using.

In the end I think I turned off the power and opened up the breaker box four times. And every time I turned the power off I had to reset all the clocks in the house.

I didn't bother buying the TED display unit since I knew there were iPhone apps. I've installed the free TED-O-Meter iPhone app which is basic but functional. I bought iTED ($.99) because it had a graph, but the graph doesn't handle negative kW values. I may try some of the others.

One thing I really like about the solar panel system is that I can monitor it from anywhere through the internet. That's because the solar system sends the data to an outside server. The TED system doesn't work that way, instead the data is collected on the Gateway device, which runs a web server so you can access it. That means I can't access it from outside my local network. (Unless I want to punch holes in my firewall and deal with my dynamic IP etc.) It also means all my data is on the Gateway so I'm probably going to lose it at some point e.g. if I update the firmware.

To get around this, the TED system can post the data to an external service. (commonly Google PowerMeter, until they discontinued it.) Unfortunately, this didn't go smoothly. Every time I tried to activate it, it would time out connecting to the server. I tried several different services so I don't think it was a server problem. Eventually I got it to work, but unfortunately I wasn't scientific enough to isolate what the issue was. I tried various combinations of: switching browsers, trying different services, resetting the gateway, entering the url with and without "http://", and turning the OS X firewall on and off. Presumably, it's the gateway sending the data, so my computer and its firewall shouldn't be relevant, but it's possible they have client side Javascript running on the browser that tests the connection during activation.

It's hard to tell which of these third party services is the "best". TED will only post to a single service so I can only try one at a time. I succeeded first with PlotWatt so I'll give them a try. I had emailed them about my connection problem and they responded quickly and helpfully so that's a good sign. The way their system works, they have to collect a certain amount of data before it's functional so I'll have to be patient. Of course, my initial data is a mess because half of it has the wrong polarity!

It would be nice if there were standards for all these home monitoring and automation systems. As it is every manufacturer and every type of system seems to do things differently and none of them work together.

Overall, the TED 5000 systems seems ok. I definitely think they could improve their instructions and documentation. And I think they could simplify installation if they added a polarity option to the software. Personally, I'd prefer if they sent the data to an internet service, but I can see where being able to operate independently could be valuable (e.g. if you don't have an internet connection). I'm glad they use a browser based interface rather than proprietary client software. The user interface is adequate. And it's great that their are third party services and apps.

Overview of my rat's nest.

The main (usage) CT's

The solar CT's in the bottom of the box and the two MTU's mounted outside

Part of the TED display, showing usage of 178w, solar generation of 426w (cloudy),

with the net result of -248w, negative meaning I'm sending excess power to the grid.

Approval Tests

2011-12-24T12:46:00.001-06:00

I recently listened to a Herding Code podcast on Approval Tests.

The basic idea is that instead of writing:

assert(x == <some-value>)

instead you write:

approve(x)

and when you run the test it shows you the result and asks you to "approve" it. Once you've approved a value, the test will pass (without interaction) as long as the result doesn't change.

If the value is something simple like a number, there's not much point. But if the value is a more complex object like an invoice, then it's much simpler to approve the whole thing than to write a lot of asserts.

I can't see it replacing conventional style asserts, but it seems like it could be useful.

Textastic

2011-12-16T16:09:00.001-06:00

I was looking for some way to have my Suneido source code on my iPad. More for viewing than to actually write code. I tried a few things, and settled on Textastic.

I was able to retrieve my cSuneido code from the SourceForge Subversion repository, but I didn't manage to get the jSuneido code from Mercurial. (It may just have been really slow. Or maybe it was trying to download the history?) So I just copied my source directory to Dropbox and pulled it from there.

I used it a few times while I was traveling recently and it worked well. For example, I'd get an email from my staff asking what a particular error message meant and I was able to find it in the source code and see where it came from.

Textastic is somewhat compatible with TextMate. I have a copy of TextMate on my Mac but I don't actually use it much since I tend to work in Eclipse.

From my limited use, I'd recommend it. It's not free, but for $10 you can't go too far wrong.

Long Polling with Suneido

2011-10-19T17:33:00.000-06:00

It started with our summer student deciding to build an "instant messenger" in Suneido. I'm not sure what prompted this, but it seemed like an interesting challenge so I let him run with it.

The trick is the "instant" part. His initial approach was to store the messages in a database table, and poll the table for changes. To make it "instant" he wanted to poll very frequently, at least once a second, and preferably more. We have about 50 users, if they are all polling every second, that's an extra 50 queries per second. I wasn't too keen on this.

I suggested we set up a separate HttpServer for the messenger, and keep the "outstanding" messages in memory, so polling didn't have to hit the database. (New messages were still written to a history table in the database, but that's not as frequent as the polling.) This took the load off the main database server, and made the requests faster.

I explained that a better way to make it "instant" was to use Comet style long polling where the server simply doesn't respond to the request until something is available. This means a lot more connections to the server since every client always has an outstanding request, which can be an issue depending on the server. But we were using jSuneido for the messenger HTTP server, and 50 connections wasn't a problem.

But the client side is also an issue. If we're going to be waiting a potentially long time for a response, the client can't be waiting "blocked", we need to make the request asynchronously. Suneido doesn't have a lot of support for aynchronous programming, but it does have a Thread function that allows you to execute code in a separate "fiber" - not a real thread, more like a coroutine. (On jSuneido "Thread" uses a real thread.)

We've never used Thread much because it has always seemed a little flaky. But it is basically sound because it's what the Suneido database server uses to handle multiple users - and that is solid. And it's also how SocketServer is implemented, and that also works well (e.g. in HttpServer)

One issue is that you want to avoid updating the GUI from a thread. That is easy to do by using Delayed with a 0 delay to process the response. Delayed works via the Windows message queue, which is processed by the main fiber. The code running inside the thread looks like:

forever
{
if "" isnt response = Http.Get(uri)
Delayed(0, ResponseProcessor(response))
}

(plus catching exceptions etc.)

However, we haven't eliminated polling, we've just moved it to the messenger HTTP server, since it must poll for new messages. (Since Suneido doesn't have any way to "wait" for something.) The code looks something like:

400.Times
{
if Suneido.MessagesAvailable
return ...
Sleep(100)
}
return ""

400 times 100ms is 40 seconds, less than the default timeout of 60 seconds. Checking once every 100 ms (1/10 of a second) is a light load on the server, most of the time it's sleeping. (Note: this wouldn't work well on a cSuneido HTTP server because Sleep would block all the other fibers.)

This has ended up working remarkably well - the messenger is "instant" with little load on the server or client.

JUnit Max

2011-10-18T20:02:00.003-06:00

I've been using JUnit Max for the last few days. It's an Eclipse extension that automatically runs your tests every time you save a change.

Normally I'd stick to open source options (which this is not), but I figure Kent Beck deserves some support.

It's taking me a little getting used to - makes me nervous not running the tests manually. It's designed to be unobtrusive, but part of me wants more blatant feedback that my tests passed.

One of my motivations for using it is to make sure I'm running all the tests, not just the one I'm working on. I've been caught a few times where I didn't discover I broke something elsewhere till some time afterwards.

Even with a fast machine, it still takes a while for the tests to run (although I'm the only one to blame for the speed of the tests), but at least they run in the background and I can continue working.

The web site is pretty minimal and there is no documentation as far as I can tell, but then again, it's pretty self explanatory.

One of the things that prompted me to try it was listening to a podcast with Kent Beck on Software Engineering Radio (recommended).

JUnit Max has had a bit of a rocky history, pulled in 2009, relaunched in 2010. I think it's a worthwhile product and I hope it's successful.

Zite: Personalized Magazine for iPad

2011-10-16T07:49:00.000-06:00

I've been playing with this a little. I like how it analyzes your on-line presence and suggests material. And then lets you "vote" material up or down. It found quite a few interesting computer articles I hadn't seen. Of course, the last thing I need is more stuff to read!

Zite: Personalized Magazine for iPad (free, ad supported)

The Grass Always Seems Greener

2011-10-07T15:31:00.000-06:00

After tracking down the third bug to the same area of the code, I decided I had to stop adding more special cases and come up with a better solution.

The code was in the B-tree (technically B+-tree) implementation in my new append-only storage engine for jSuneido.

I'll try to explain the problem. I combine keys with a child node pointer. That leaves the question of whether a key points to the values less than it, or greater than it. I've always gone with greater than. But the problem is that when you do a lower bound binary search, the resulting position is one higher than the one you want. For example, if the tree node contains the keys 2, 4, 6, 8, the leaf containing 5 will be pointed at by the "4". But a lower bound binary search will give the position where you would insert 5, i.e. the position of the "6" key.

You can adjust for this, but it gets ugly. After the multiple bugs, I started to think that making the keys point to values less than the key would be cleaner because you wouldn't have the off by one problem.

So yesterday morning I set out to change the code. It's not a large amount of code and the changes were straightforward, but the code is fairly complex, and the "greater than" assumption was hidden in more places than I would have liked.

Eight hours later I had all my tests passing again. And it did simplify some parts of the code. But it also turned out (not surprisingly) that this approach had its own drawbacks. For example, a standard optimization is to detect when keys are being added in order (i.e. to the "end" of the B-tree) and to put only the new key in the new node, keeping the old full node intact. The way my code works, this is much easier with the "greater than" approach.

I'm sure I could have got it all worked out, but switching approaches was not the clear winner that I'd hoped.

Actual written code, with all it's messiness, always seems inferior to an imagined alternative, which is always perfectly clean. (And therefore, the grass is always greener title.) But when you implement the alternative, it often ends up just as messy as what you had before. (This relates to never rewrite from scratch)

I came up for air, ate some supper, realized I hadn't stepped foot outside the house all day, and considered my options. A glass of wine in hand, I returned to the computer. I wanted to "finish" working on it while all the details were fresh in my mind. I knew I wouldn't get a chance to work on it again for a week or so, and then I'd have to get back up to speed.

I threw out all the changes I'd made. (Except for a few additional tests I'd written.) Annoying, but at least it was only a days work.

By carefully adjusting the code I was able to keep the old approach, but remove most of the special cases that had been causing me trouble. The code is quite a bit cleaner now. I still have the off by one adjustment, but it's in a single place now.

Meanwhile, I've been reading Tokutek's blog about how COLA (cache oblivious lookahead array) style fractal trees are so much better than B-trees. That grass sure looks greener over there :-)

Farewell to Steve

2011-10-06T10:30:00.000-06:00

I sat down with my iPad last night to catch up on my blog reading and the first thing I saw was about Steve having died. We knew it was probable, but it was still a shock. When someone is so much larger than life, you don't want to believe they are bound by the same physical laws as the rest of us.

Apple started in 1977, at a time when I was becoming increasingly absorbed by computers. My first job (only job really, other than Axon) was at a local computer store. In the service department I repaired countless Apple II's. I remember when we first saw the Lisa, and then the Mac. It's hard to communicate what a revolution it was. Nowadays the world is filled with similar amazing gadgets, but not back then.

What a long way Apple has come, and a bumpy road at times. As an entrepreneur myself at that point, I remember my shock at Steve getting kicked out of his own company. Apple struggled and Microsoft grew to dominate. Back then we could not have imagined Apple ending up bigger than Microsoft. (Any more than we imagined Microsoft overtaking IBM.) And the idea that Apple would become the most valuable company in the world would have seemed like total fantasy. Steve returning to Apple and leading it to world domination still seems like a fairy tale.

Steve's abilities as a showman and salesman were alien to a geek like me. To me, what set him apart was his focus on design and user experience. Obviously, he didn't personally do all the design work. But I have to think he played a huge part in gathering and guiding his team, and shaping their culture and priorities. I can't help but wonder how things will change at Apple with Steve gone. In the short term, they will, no doubt, continue on much the same path. But in the long run, I wonder. (Just as I wonder how Axon will change when I'm not there. Not necessarily for the worse, but inevitably different.)

I don't agree with everything that Steve and Apple have done. Their closed, controlled, curated (and taxed) world is not my ideal, but it's hard to argue with what they have achieved. Apple's financial accomplishments are impressive. Even more impressive, is that they have one of the highest customer satisfaction ratings. What other company has grown so large, and yet still pleased so many people?

All in all, his life was an insanely great story.

We'll miss you Steve.

Concurrency Continued

2011-09-06T13:33:00.002-06:00

I figured I'd better write a concurrency stress test for my DbHashTrie semi-immutable data structure, to increase my confidence that there were no problems. (Of course, a test can never prove the absence of problems.)

I write my test and it passes. But as a good cynical/skeptical tester, I tweak it so it should fail. It still passes?! I realize that I'm running in multiple threads and if an assert fails it'll just throw an exception and that thread will silently die, swallowing the exception. Oops. I add try-catch around the thread body.

Now it fails, as expected. I remove the tweak, expecting it to now succeed. It still fails! I remove the multi-threading. It still fails. Huh!? This code is in live use, if there's a bug, that's definitely not good.

After thrashing for a (thankfully short) time, I realize it was a bug in my test, not the actual code. To make it worse, I've been caught by the same thing multiple times. Some day I'll learn! When building a map-like data structure with random keys, you have to remember that you could get duplicate keys, which in most maps will overwrite the previous value. If your test checks for the original value, it'll fail since it'll get the new value.

Finally the test seems to be working properly. Except that it's not maxing out my cores. Since it's entirely in memory, with no IO, I can't see why it wouldn't. I play around with various parameters like the number of threads, size of data, and number of iterations but it still doesn't max out my cpu usage. (I use iStat Menus to show my cpu usage all the time on the menu bar so I can easily monitor what's going on.)

The only thing I can think of is the locking. I comment out the two places with synchronized and re-run the tests. Voila, all eight cores at 100%. Not normally what you want to see, but in this case it was.

Hmmm... if it wasn't maxing out the cpu, it must have been running slower. I add some timing. Yikes, the synchronized version is over 10 times slower! (45 seconds with synchronized, 3.8 seconds without.)

Of course, this is close to a worst case scenario since the test doesn't do much more than call the one synchronized method. And although the locking is per node, every access has to start at the root node. Java locks are very fast these days, but only when uncontested. And in this case the nodes at the root of the tree will be heavily contested.

If it was a single variable I could just make it volatile, but it's an array, and putting volatile on an array only makes the reference volatile, not the contents. That's where AtomicReferenceArray comes in. It had crossed my mind a few times, but the interface is quite different from an array so it would be a bit of a hassle to switch. I'd also have to write my own versions of Arrays.copyOf and System.arraycopy

I changed the code to use AtomicReferenceArray. It was a bit slower than the raw array, but not a lot (5 seconds, versus 3.8).

I also did some checking, and the JVM spec does guarantee that updates are atomic (except for long's and double's). So I think I'm safe not doing anything special for concurrent access. That means threads could read stale values. Which means there could potentially be a data race where two threads could end up loading the same node at the same time. But as far as I can figure, this should be benign since they will both get the same node (it's never modified in the memory-mapped file) and therefore it doesn't matter which one wins. I think it's equivalent to how String calculates its hashCode lazily.

The question is, do I trust this reasoning? Or do I go with the safer, but slower and uglier AtomicReferenceArray?

A little searching on the web turns up: Date-Race-Ful Lazy Initialization for Performance. Ironically, this both confirms my reasoning, and also identifies a bug in my code. I was accessing the shared variable more than once in my code, which can lead to problems due to memory access re-ordering. Easily fixed, but yet another example that it's hard to reason correctly about this stuff. (Just to hammer the point home, another article I found, Implementing hashCode, has the same bug with reading the variable multiple times without using volatile.)

The blog post also references a section in Effective Java (2nd ed) by Joshua Bloch so I dig my copy out and review it. It confirms that the single-check idiom is valid, but also recommends using double checked locking with a volatile variable instead. Even for the single check idiom, it recommends using a volatile variable, although it's not strictly necessary.

After all that, I think I'm going to go with the simplest code with the raw array, non-volatile, and unsynchronized. That's not because I trust my reasoning, but because I trust the explanation and examples of people who are much smarter than me.

Concurrency Strikes Again

2011-09-05T20:54:00.000-06:00

I thought it would be a relatively quick job to multiple-thread building the indexes when loading a database dump. Three days of thrashing later I more or less had it working.

But it was only about 10% faster so I ripped out my three days worth of work - not a big enough improvement to justify the extra complexity. I'm a bit puzzled by the limited improvement, but the speed is probably dominated by other factors. (e.g. reading and writing the files.)

The story doesn't end there though. Along the way I was seeing some very puzzling debugging output. So after abandoning my initial goal I started to dig into what was going on.

The bad news is that I found some serious concurrency flaws in my transaction handling. The good news is that I fixed them. Obviously, I need more/better tests.

Immutable data structures are great for concurrency, but they can have significant overhead compared to regular mutable ones. So, to try to get the best of both worlds, I have some semi-immutable data structures. The idea is that they are immutable when shared between threads, but mutable when confined to one thread. As always, the devil is in the details.

I found that I had inadvertently ended up sharing when mutable, leading to some ugly bugs. The data structure becomes immutable after you persist it to disk. But I had updated the master copy before saving instead of after. A small mistake with big consequences. To make sure I don't make a similar problem in the future I added asserts in relevant places to ensure that it was immutable when it should be.

Another potential issue was that even when immutable, it's only "effectively" immutable since the data structure is loaded from disk lazily. I had synchronized the updates but not the reads. That might actually be ok in this case, as long as writing a reference (pointer) is atomic. But I decided it was better to synchronize in a few more places than depend on something I wasn't sure about.

Append-Only Database Performance

2011-09-02T09:30:00.000-06:00

I've been working on the append-only storage engine for jSuneido and most recently dumping and loading. I was flipping back and forth between storage engines and it seemed like the new one was faster. I decided to time it and sure enough, with the new append-only storage engine, loading a database was close to twice as fast - nice!

Note: This was not any kind of scientific benchmark. It was a relatively small database (130mb) and only loading. But still, a promising early result.

This is also still single-threaded. I've been itching to try using multiple threads to build indexes. Each index is relatively independent so it should be feasible, but I'm currently using an "exclusive" transaction so it's a little tricky. This should speed up loading even more.

Emergent Design & Functional Thinking

2011-08-30T11:35:00.000-06:00

Some good articles by Neal Ford (ThoughtWorks) on the IBM developerWorks site:

Emergent Design

Functional Thinking

Mostly Java with a bit of Groovy.

These are in line with much of my thinking these days regarding immutability, coupling, composition, etc.

Why Amazon Can't Make a Kindle in the USA

2011-08-27T12:10:00.001-06:00

An interesting series of articles:

Part 1: Why Amazon Can't Make a Kindle in the USA

Part 2: Does it really matter whether Amazon can make a Kindle in the USA?

Part 3: Amazon & Kindle Part 3: It’s not just manufacturing!

Part 4: Amazon & Kindle Part 4: Some good news (finally)!

Benchmark Surprises

2011-08-17T18:14:00.001-06:00

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.

Scala Again

2011-08-07T11:40:00.000-06:00

Recently I've been re-reading Odersky's Scala book (the new edition). I looked back at my original blog posts about Scala and was surprised to see they were over two years old. Time flies!

I set up a copy of Eclipse (3.7 Indigo) with the latest Scala plugin (2.0.0beta09) so I could play around.

One of the examples in the book (and other places) is using case classes and pattern matching to simplify algebraic equations. I do some of that in Suneido (both in the language and the database query optimization) so it's somewhat familiar. Here are the classes:

I chose two optimizations - subtraction of two constant numbers, and addition of zero

This version works for a single level:

BinOp("-", Num(2), Num(2)) => Num(0)

BinOp("+", Var("x"), Num(0)) => Var("x")

The obvious way to make it handle multiple levels is:

But this is top down, which doesn't handle cases like:

BinOp("+", Var("x"), BinOp("-", Num(2), Num(2)))

=> BinOp("+",Var("x"),Num(0))

We need to operate bottom up, which means processing a node's children before itself:

BinOp("+", Var("x"), BinOp("-", Num(2), Num(2)))

=> Var("x")

One thing that bugs me about the recursive versions is that they copy every node, even if they're not changing anything. In Suneido I do something like:

arg = simplify(node.arg)

if (arg != node.arg)

node = new UnOp(node.op, arg)

But that seemed verbose and didn't fit with this Scala code. Instead, I added "alter" methods to UnOp and BinOp like:

so simplify only had to change slightly:

Of course, I ask myself if this is premature optimization. Obviously, for this simple test, it's unnecessary. On the other hand, it was part of my exploration.

I always struggle with this question of premature optimization. The problem is (as I've written about before) if you totally ignore performance issues, you can easily end up with a program that, for example, does several times as much allocation as it needs to. And that sub-optimal code won't be conveniently in one hot spot - it'll be spread throughout your code. Allocation in modern JVM's is very fast, but garbage collection and memory bandwidth and cache effects still cost.

The more I play with Scala, the more I like it.

Append-Only Database Progress

2011-07-30T14:12:00.000-06:00

This won't mean much to anyone but me, but it's the culmination of several weeks of refactoring. This test runs a simple query using both the current storage engine and the new append-only storage engine, by simply choosing which DatabasePackage to use. All the query parsing, optimization, and execution is common, just the low level storage engine is different. While the query is simple, a lot of things have to work at the lower levels to make it function, so it's a good milestone.

This is using jUnit's ability to run tests with multiple sets of parameters.

Upgrading to Lion

2011-07-21T20:36:00.000-06:00

As much as I know better than to rush to new technology, I couldn't resist upgrading to Lion right away.

I wasn't really paying attention, but it took about an hour to download the 4gb update from the App Store.

I knew I had four machines to update (my iMac and MacBook, and Shelley's iMac and MacBook) so I looked up online how to update multiple machines from a single download.

The trick is that there is a disk image inside the download that you can use to make a bootable DVD or USB drive. But you need to do that after you download, but before you install. One of the better explanations was HOW TO: Do a Clean Install of OS X Lion

Without thinking, I started burning a DVD, only to realize that the MacBook Air's don't have DVD drives. So I grabbed the thumb drive I had handy and tried to use it. But it was only 4gb and the image didn't fit. I thought I'd have to get a bigger thumb drive but then I remembered I had a small USB hard disk that I use for backing up photos when travelling. It was more than big enough.

The install went smoothly. Again, I didn't time it, but it was something like half an hour.

The next morning, when I tried to start Eclipse to do some programming, I got "no JRE installed" and it asked if I wanted to install one. I said yes and after quite a long pause (30 seconds?) it installed one and Eclipse started. Not bad!

I needed to reselect the JRE in Eclipse. Then a test failed because I'd forgotten to enable asserts on that JRE. But after that, all the tests passed. So far so good.

Then I found Mercurial was broken. A quick internet search found Mercurial SCM (hg) fix for OS X 10.7 Lion. Even better, I read to the bottom before I tried the fix and found there was an updated installer for Mercurial on Lion. I downloaded and installed it and Mercurial was back in business.

It did take quite a while to re-index for Spotlight searching but that happened in the background.

iTunes gave me a rather frightening message about not being able to save my music library, but it seems to be working fine.

Those are really the only problems I've had so far. Not too bad, considering.

I updated my MacBook using the USB hard disk. It went smoothly also.

One change that is going to take some getting used to is the reversing of the scroll direction. Admittedly, the old way does seem backwards - pulling your finger down to scroll up. Now it's the same as the iPhone or iPad, with a metaphor of dragging the page around. But old habits are hard to break and I keep trying to scroll the wrong direction. And I still use Windows at work which will be the opposite way, although with a mouse wheel rather than swiping on a Magic Mouse.

I can't imagine Microsoft having the guts to make this kind of change. Nor can I imagine Microsoft users standing for it - they would just flip the setting to "Classic" mode. (The same way most of my staff immediately switched new versions of Windows to the old Classic appearance, despite my protests.) It would be interesting to know how many Mac users switch it back to the old way.

There will probably be other issues I haven't run into yet, but so far it's been a pretty smooth update.

Java BufferedInputStream Problem

2011-07-20T15:11:00.000-06:00

I ran into a problem loading a large database dump from cSuneido into jSuneido.

After several hours of debugging, I found if I changed this:

InputStream fin = new BufferedInputStream(
new FileInputStream(filename));

to:

InputStream fin = new FileInputStream(filename);

(i.e. removed the BufferedInputStream)

Then it worked ?!

I searched on the web for BufferedInputStream problems but didn't find anything relevant.

One thing that is suspicious is that this is probably the first file I've tried to load that is larger than 4 gb (i.e. the limit for a 32 bit integer), although I'm not sure why that would be a problem for BufferedInputStream. You'd think it would just be reading sequentially. Unless it's trying to do something clever like memory mapping the whole file.

Note: This is on a 64 bit JVM.

I'm just going to omit the BufferedInputStream for now, but it would be nice to know why there was a problem.

I guess I could go dig up the OpenJDK code for BufferedInputStream but I'm not that motivated.

Anybody have any information or thoughts on this?

Large Scale Java Design

2011-07-19T12:22:00.000-06:00

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

2011-07-12T12:52:00.000-06:00

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

2011-07-07T15:37:00.001-06:00

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

2011-06-30T18:21:00.000-06:00

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

2011-06-25T17:16:00.000-06:00

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?

2011-06-23T12:35:00.000-06:00

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

2011-05-30T18:26:00.000-06:00

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

2011-05-04T21:14:00.000-06:00

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

2011-04-30T13:28:00.000-06:00

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

2011-04-28T13:56:00.000-06:00

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

2011-04-26T10:32:00.000-06:00

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

2011-04-24T09:02:00.000-06:00

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

2011-04-21T16:32:00.000-06:00

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!

2011-04-20T11:08:00.000-06:00

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

2011-04-17T09:40:00.000-06:00

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

2011-04-15T09:27:00.000-06:00

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

2011-04-14T10:35:00.000-06:00

I recently ran across a new article on Stratiﬁed 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 ﬁrst 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 efﬁciently 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

2011-04-13T15:20:00.000-06:00

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

2011-03-30T12:06:00.000-06:00

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

2011-03-27T11:23:00.000-06:00

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

2011-03-27T10:19:00.000-06:00

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

A JVM Does That?

2011-03-20T11:49:00.000-06:00

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

2011-03-16T20:54:00.000-06:00

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

2011-03-09T10:39:00.000-06:00

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

2011-03-03T21:00:00.000-06:00

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

2011-01-15T19:03:00.000-06:00

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

2011-01-09T07:33:00.000-06:00

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

2011-01-08T20:27:00.001-06:00

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

2011-01-08T18:31:00.000-06:00

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

2010-12-28T20:37:00.000-06:00

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

2010-12-27T19:23:00.000-06:00

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

2010-12-26T12:45:00.000-06:00

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

2010-12-24T11:51:00.000-06:00

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

2010-12-24T10:40:00.000-06:00

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

2010-12-22T14:42:00.000-06:00

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

2010-12-20T11:16:00.000-06:00

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

2010-12-05T13:10:00.001-06:00

"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?

2010-11-25T09:46:00.000-06:00

"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

2010-11-23T09:32:00.000-06:00

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

2010-11-21T16:55:00.000-06:00

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

2010-11-21T10:45:00.000-06:00

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

2010-11-19T18:06:00.000-06:00

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.

RethinkDB

2010-11-19T12:19:00.000-06:00

I just listened to a podcast from the MySQL conference from RethinkDB about better database storage engines. Apart from being an interesting talk, a lot of what they were talking about parallels my own ideas in Suneido.

For example, they talk about log structured append-only data storage. Suneido's database has always worked this way.

Next they talk about append-only indexes. Suneido does not have this, but it is something I've been thinking about. (see my post A Faster, Cleaner Database Design for Suneido). They have a different idea for reducing index writes. It's an interesting solution, but more complex. It won't be as fast as delaying writes, but it would allow crash recovery without rebuilding indexes (as Suneido requires).

I mostly arrived at these design ideas from basic principles e.g. immutable structures are better for concurrency. But it sounds like the file system folks have been working on a lot of the same ideas. It's hard to keep up with everything that might possibly be relevant.

The other interesting part of this talk was the idea that there are a lot of pieces that have to work together and performance depends on the combination. This means there is a huge possibility space that is hard to explore.

Java, Oracle, GUI, and jSuneido

2010-11-17T10:54:00.000-06:00

A Suneido developer had a few questions that he thought I should blog about, so here goes. (Disclaimer: I'm not an expert on Oracle or Java and don't have any inside knowledge.)

What will happen with Java with Oracle buying Sun? Do I regret choosing Java to rewrite Suneido?

Oracle buying Sun does make me a little nervous but I don't think Java is going to go away, there is too much of it out there.

I don't regret choosing Java to rewrite Suneido. There aren't a lot of mainstream alternatives - .Net would be a possibility, with Mono on Linux. I think .Net is a good platform, but I like being tied to Microsoft even less than I like being tied to Oracle. And I think Java is less tied to Oracle than .Net is tied to Microsoft.

There are, of course, other alternatives like LLVM or Parrot, but they don't have the same kind of support behind them.

I've heard persuasive arguments (albeit mostly from Oracle) that it is to Oracle's benefit to keep Java alive and "open" since much of Oracle's software is written in Java. They might try to charge for stuff but probably at the enterprise end, which doesn't bother me too much.

I do wish Java moved a little faster. Java 7 is taking forever, and now a lot of it has been postponed to Java 8. Meanwhile, Microsoft has moved surprizingly quickly with advancing .Net. On the positive side, the new features in Java 7 for dynamic languages (JSR 292) will be very nice. And I do want stability, so I can't complain too much.

I don't think the Oracle buyout has any effect on jSuneido in the short term. I'm using Java 6 which is readily available.

What platform are you using to develop jSuneido?

I do most of my development on Mac OS X using Eclipse. I run the Windows cSuneido client using Parallels. I'm pretty happy with this. The only minor hassle was that Apple was really slow to release new versions of Java. And Sun/Oracle don't directly release OS X versions. You could get new OS X versions of Java from other places but it was an extra hassle. Now Apple has announced that they won't be distributing Java any more. This isn't a big deal - Microsoft doesn't distribute Java either. It would be nice if Oracle would add OS X as one of their supported platforms. (Not just on Open JDK.)

But this is only the development environment. In terms of deploying the jSuneido server I expect it will be mostly Windows and Linux. There aren't many people using OS X for servers. And Apple just discontinued their rack mount server.

I also do some development on my Windows machine at work. There are slight differences, but mostly I can use the identical Eclipse setup.

I haven't done any testing on Linux. I would hope it would be fine but there could be minor issues. If we were only working on Windows then there might be more, but Linux shouldn't be too different from OS X.

We are getting close to switching our in-house accounting/crm system over to jSuneido. This will be a good test since we have about 40 users. Currently we have a Windows server to run this system and a Linux server for other things. Once we are running on jSuneido we are hoping to get rid of the Windows server and just use the Linux one. So Linux support is definitely coming.

Where can I get a copy of jSuneido?

Currently, the only way to get it is as source code from Mercurial on SourceForge:

http://suneido.hg.sourceforge.net:8000/hgroot/suneido/jsuneido

I haven't started posting pre-built jar file releases yet, but probably soon. If anyone is interested in getting a copy to experiment with, just let me know and I can send you one.

What about a GUI for jSuneido?

Currently, jSuneido does not have any GUI. cSuneido's GUI is Windows based so it's not portable.

In the long run it would be nice to add a GUI to jSuneido. Then, eventually, I could stop supporting cSuneido. Maintaining two parallel versions is a lot of extra work.

The conventional Java approaches would be Swing or SWT.

Another idea would be to try to use the newer GUI system from Java FX, but there's not much support for using it outside of FX yet.

Another possibility would be to switch to a web based GUI, even for local use. That's an intriguing idea that would be fun to investigate. The downside is that instead of just Suneido code, you'd have HTML and CSS and JavaScript and AJAX. Not exactly the self-contained model that Suneido has had up till now.

The bigger issue for us is that we have a lot of code based on the old GUI system. So a priority for us would be to minimize the porting effort.

Upgrading Eclipse to Helios (3.6)

2010-11-14T17:05:00.000-06:00

I recently upgraded my development environment for jSuneido to Helios (version 3.6) from Galileo (3.5).

Helios has been out since June but I needed to wait for the plugins I use to be updated. Actually, this was one of the things that nudged me to update since one of my plugins started giving errors on Galileo after they updated it for Helios.

It went quite smoothly. The plugins I use are:

Mercurial Eclipse
Bytecode Outline
EclEmma Java Code Coverage
FindBugs
Metrics (State of Flow)

A new version of Eclipse used to mean a bunch of great new stuff. But like most software products, it's matured and development has slowed down, at least in terms of major new features. In normal usage I didn't notice much difference.

One welcome addition is the Eclipse Marketplace (on the Help menu with the other update functions). EclEmma, Bytecode Outline, Mercurial Eclipse, and FindBugs can all be installed through the marketplace, which is a lot nicer since you don't have to go to their web site, find the url of the update site, copy it, and then paste it into Eclipse. The other plugins show up in the marketplace, but don't have an install button. I'm not sure why, but it's a new feature so you have to expect some hiccups.

A minor complaint is that the marketplace is implemented as a wizard, even though it isn't really a multi-step process. Wizards can be a reasonable approach, but I think they're overused sometimes.

Email Overload

2010-11-09T15:40:00.000-06:00

And you thought you had too much email :-)

This was on the latest Thunderbird. Not sure what I did to trigger it - looks like some kind of overflow.

jSuneido Compiler Overhaul Part 2

2010-10-29T12:59:00.000-06:00

After my last post I was thinking more and more about switching from single pass compiling to compiling via an Abstract Syntax Tree (AST).

I wasn't really intending to work on this, but I had a bit of time and I thought I'd just investigate it. Of course, then I got sucked into it and 10 days later I have the changes done. I'm pretty happy with the results. A big part of getting sucked into it was that it became even more obvious that there were a lot of advantages.

Previously I had lexer, parser, and code generator, with the parser directly driving the code generator. Now I have lexer, parser, AST generator, and code generator.

I'm very glad that from the beginning I had separated the parser from the actions. The parser calls methods on an object that implements an interface. This seems obvious, but too many systems like YACC/Bison and ANTLR encourage you to mix the actions in with the grammar rules. And doing this does make it easier to at first. But it is not very flexible. Because I'd kept them separate, I could implement AST generation without touching the parser. Although I haven't used it, I understand Tatoo splits the parser and the actions. (Note: Although I initially tried using ANTLR for jSuneido, the current parser, like the cSuneido one, is a hand written recursive descent parser.)

While I was at it, I also split off the parts of the code generator that interface with ASM to generate the actual byte code. The code generator is still JVM byte code specific, but at a little higher level. And now it would be easy to use an alternative way to generator byte code, instead of ASM.

When the parser was directly driving the code generation, I needed quite a few intermediate actions that were triggered part way through parsing a grammar rule. These were no longer needed and removing them cleaned up the parser quite a bit.

Having the entire AST available for code generation is a lot simpler than trying to generate code as you parse. It removed a lot of complexity from the code generation (including removing all the clever deferred processing with a simulated stack). And it let me implement a number of improvements that weren't feasible with the single pass approach.

Despite adding a new stage to the compile process, because it was so much simpler I'm pretty sure I actually ended up with less code than before. That's always a nice result!

The only downside is that compiling may be slightly slower, although I suspect the difference will be minimal. Code is compiled on the fly, but the compiled code is kept in memory, so it only really affects startup, which is not that critical for a long running server.

In retrospect, I should have taken the AST approach with jSuneido right from the start. But at the time, I was trying to focus on porting the C++ code, and fighting the constant urge to redesign everything.

Continuous Deployment

2010-10-25T10:07:00.000-06:00

I listened to a podcast recently about a company doing continuous deployment. I was interested because my company does continuous deployment, and not just of a web application, but of a desktop app. From what I can tell, this is still quite rare.

They were asked how frequently they deploy, and they said every two weeks. I was a little surprised. Obviously it's a long way from yearly releases, but to me, every two weeks is not exactly "continuous".

Part of the issue is that "continuous" often gets mixed up with "automated". For example, continuous build or integration systems are as much about the automation as they are about continuous. But the primary goal is the "continuous" part. The automation is a secondary requirement needed to satisfy the primary goal of continuous.

Of course, "continuous" seldom actually means "continuous". It usually means "frequent". Continuous builds might happen nightly, or might be triggered by commits to version control.

Our continuous deployment means daily, Monday to Thursday nights. We don't deploy Friday in case there are problems and we don't have anyone working on the weekends.

Our big nightmare is that something goes wrong with an update and all of our roughly 500 installations will be down. Of course, we have a big test suite that has to pass, but tests are never perfect. To reduce the risk we deploy to about ten "beta" sites first. Everyone else gets that update two days later. Having ten beta sites down is something we can handle, and they're aware they're beta sites so they're a little more understanding. In practice, we've had very few major problems.

We have a single central version control (similar to Subversion). Anything committed to version control automatically gets deployed. The problem is when we're working on a bigger or riskier change, we can't send it to version control until it's finished. But not committing regularly leads to conflicts and merge issues, and also means we're only tracking the changes with a large granularity and can't revert back to intermediate steps. Plus, version control is the main way we share code. If the changes haven't been sent to version control, it's awkward for other people to get access to them for review or testing. I think the solution would be a distributed version control system like Git or Mercurial where we can have multiple repositories.

I'm looking forward to reading Continuous Delivery although I think the focus is on web applications.

What, Why, How

2010-10-23T17:00:00.000-06:00

Say why not what for version control comments, and comments in code. The code itself tells you "what", the useful extra information is "why". Don't say "added a new method", or "changed the xyz method" - that's obvious from the code. Do say, "changes for the xyz feature" or "fixing bug 1023".

Say what not how in names. i.e. interface and variable names. The users shouldn't need to know "how", they just care about "what". You want to be able to change the "how" implementation, without changing the users. Don't call a variable "namesLinkedList", just call it "namesList". It might currently be a linked list, but later you might want to implement it with a different kind of list.

jSuneido Compiler Overhaul

2010-10-17T10:11:00.000-06:00

Implementing a language to run on the JVM means deciding how to "map" the features of the language onto the features of the JVM.

When I started writing jSuneido it seemed like the obvious way to compile a Suneido class was as a Java class, so that's the direction I took.

The problem is, Suneido doesn't just have classes, it also has standalone functions (outside any class). So I made these Java classes with a single method.

Suneido also has blocks (closures). So I compiled these as additional methods inside the class currently being compiled.

As I gradually implemented Suneido's features, this approach got more and more complex and ugly. It all worked but I wasn't very happy with it. And it became quite fragile, any modification was likely to break things.

So I decided to overhaul the code and take a different approach - compiling each class method, standalone function, or block as a separate Java class with a single method. I just finished this overhaul.

Of course, the end result is never as simple and clean as you envision when you start. It's definitely better, but there are always awkward corners.

Unfortunately, more and more of the improvements I want to make are running into the limitations of single-pass compiling, an approach I carried over from cSuneido. I have a feeling that sooner or later I am going to have to bite the bullet and switch to compiling to an abstract syntax tree (AST) first, and then generate JVM byte code from it. That will open the way for a lot of other optimizations.

Java + Guava + Windows = Glitches

2010-10-15T09:02:00.000-06:00

Some of my jSuneido tests started failing, some of them intermittently, but only on Windows. There were two problems, both related to deleting files.

The first was that deleting a directory in the tear down was failing every time. The test created the directory so I figured it probably wasn't permissions. I could delete the directory from Windows without any problems. The test ran fine in cSuneido.

I copied the Guava methods I was calling into my own class and added debugging. I tracked the problem down to Guava's Files.deleteDirectoryContents which is called by Files.deleteRecursively. It has the following:

// Symbolic links will have different canonical and absolute paths
if (!directory.getCanonicalPath().equals(directory.getAbsolutePath())) {
return;
}

The problem was that getCanonicalPath and getAbsolutePath were returning slightly different values, even though there was no symbolic link involved - one had "jsuneido" and the other had "jSuneido". So the directory contents wasn't deleted so the directory delete failed. From the Windows Explorer and from the command line it was only "jsuneido". I even renamed the directed and renamed it back. I don't know where the upper case version was coming from. It could have been named that way sometime in the past. I suspect the glitch may come from remnants of the old short and long filename handling in Windows, perhaps in combination with the way Java implements these methods on Windows.

I ended up leaving the code copied into my own class with the problem lines removed. Not an ideal solution but I'm not sure what else to do.

My other thought at looking at this Guava code was that if that test was extracted into a separate method called something like isSymbolicLink, then the code would be clearer and they wouldn't need the comment. And that might make it slightly more likely that someone would try to come up with a better implementation.

The other problem was that new RandomAccessFile was failing intermittently when it followed file.delete. My guess is that Windows does some of the file deletion asynchronously and it doesn't always finish in time so the file creation fails because the file exists. The workaround was to do file.createNewFile before new RandomAccessFile. I'm not sure why this solves the problem, you'd think file.createNewFile would have the same problem. Maybe it calls some Windows API function that waits for pending deletes to finish. Again, not an ideal fix, but the best I could come up with.

Neither of these problems showed up on OS X. For the most part Java's write-once-run-anywhere has held true but there are always leaky abstractions.

Using ProGuard on jSuneido

2010-09-28T18:38:00.000-06:00

ProGuard is a free Java class file shrinker, optimizer, obfuscator, and preverifier.

I'd seen a few mentions of ProGuard and then when I was updating to the latest version of the Guava library I saw that they were recommending it. So I decided to try using it on jSuneido.

It shrunk the size of the jSuneido jar from 2.5 mb to 1.4 mb. That's pretty good for an hour or two of setup.

I haven't tried the optimization yet, partly because the Guava instructions disabled it. I'm not sure why.

ProGuard also does preverification which should improve startup time, although that's not a big issue for the server usage that jSuneido is aimed at.

It took some trial and error to get a configuration file that worked. I'm not sure it's optimal yet. I still get some warnings from Guava (mentioned in their instructions) and from jUnit, but they don't appear to cause any problems.

Eclipse += Mercurial

2010-09-23T17:53:00.000-06:00

It wasn't quite as easy as I would have liked to get the MercurialEclipse plugin working, but it certainly could have been worse.

It was easy to install the Eclipse plugin using the update site: http://cbes.javaforge.com/update

But when I tried to import my project from Mercurial I got a bunch of errors about passwords.

I found a post from someone with the same problem, with a pointer to instructions on how to solve it.

I guess the simple username + password doesn't work with MercurialEclipse, at least on OS X. Sigh.

The answer is to use an SSH key, which I'd avoided till now, but it turned out to be straightforward with the help of the SourceForge instructions. It sounds like it might be a bit trickier on my Windows box - I haven't tried that yet.

I tweaked a few things for the new setup, committed those changes, and pushed the changes to the SourceForge repository. Seems like I'm good to go :-)

The Revenge of the Intuitive

2010-09-23T09:31:00.000-06:00

Interesting article by Brian Eno on the user experience problem of too many options, a problem we struggle with all the time with our software. The challenge is that it is the users themselves that keep asking for more options, despite the fact that it ends up making the software harder to use.

Wired 7.01: The Revenge of the Intuitive

Moving jSuneido from Subversion to Mercurial

2010-09-21T17:44:00.000-06:00

I've been planning on moving from Subversion to a distributed version control system for a while. Initially I assumed it would be Git since that's what I heard the most about. But I recently listened to a podcast with Eric Sink where he said Mercurial had better Windows support and was simpler to use, especially for Subversion users. An article on InfoQ confirmed this. And Google code has Subversion and Mercurial but not Git. And Joel Spolsky and Fog Creek had picked Mercurial. Joel even wrote a tutorial for Mercurial. So I decided to give Mercurial a try.

When explaining distributed version control a lot of people start by saying there's no central repository, it's peer to peer. This throws off a lot of people because they want a central repository. It's the explanation that's wrong. You can have a central repository, and most people do. The difference is that it's a matter of convention, it's not dictated by the software. And you can also have multiple repositories.

For me, the advantages would be having the complete history locally, even when I'm off-line, and being able to easily branch and merge locally.

Here are the steps I used to convert jSuneido from Subversion to Mercurial. (I haven't converted C Suneido yet, but that shouldn't be too hard, just more history so it'll be slower.)

Download and install Mercurial on OS X from mercurial.selenic.com

Convert the existing SourceForge Subversion repository to a local Mercurial repository:

hg convert http://suneido.svn.sourceforge.net/svnroot/suneido/jsuneido

Ideally you wouldn't convert directly across the network. Instead you'd clone your Subversion repository to your local machine and convert from there. That's primarily so if you have to tweak your conversion and re-run it, you're not dealing with the network delays multiple times.

I was lucky since my Subversion history did not have anything tricky like branches to deal with. And cloning the Subversion repository looked painful. I figured I could probably get away with doing the convert directly. It ended up taking a couple of hours to run.

One nice thing about convert is that you can run it again to pick up incremental changes. (I had to do this once because I had forgotten to send my latest change to Subversion.)

To check out the result I copied the repository to Windows (under Parallels) and installed TortoiseHg. The repository looked reasonable. (A little roundabout, but I wanted TortoiseHg anyway.) TortoiseHg seems to work well.

Enable Mercurial for the Suneido SourceForge project. Add a second repository for jsuneido. See sourceforge.net/apps/trac/sourceforge/wiki/Mercurial

Push the local Mercurial repository to SourceForge.

hg push ssh://amckinlay@suneido.hg.sourceforge.net/hgroot/suneido/jsuneido

I could have also done this with TortoiseHg (but don't look for a "Push" menu option, it's under Synchronize)

I can now browse the repository on SourceForge.

I found the series of three blog posts starting with From Subversion to Mercurial. Part 1, Setting the Stage quite helpful.

Next I have to figure out the Eclipse plugin for Mercurial. I hope it's less hassle than the Subversion one!

Stylebot

2010-09-21T12:54:00.000-06:00

Changing the Look of the Web with Stylebot - Google Open Source Blog

A very nice Chrome extension that lets you easily create custom stylesheets for web sites. For example, I often want a different text size for a given site, or to hide certain annoying elements (e.g. ads!)

This is a good example of how Chrome seems to be pulling ahead in the browser competition.

Balsamiq Mockups

2010-09-17T14:26:00.000-06:00

I've heard several people say good things about Balsamiq Mockups. I haven't used it myself but I'm planning to give it a try. I like how it produces something that looks like a sketch so people don't get the mistaken idea that it's a finished design.

What Can't the iPad Do?

2010-09-11T21:02:00.001-06:00

The girl next to me on the bus had an iPad, so I asked her how she liked it. I expected the usual "it's great", but instead I got "I don't" I asked her why and she said there was too much stuff it couldn't do. I didn't get a chance to dig deeper.

Someone else I know bought an iPad and immediately got someone to jailbreak it for them. Why? Because there's too much stuff it can't do otherwise. When I asked for examples they couldn't really give me any. This is a non-technical person, it's not that they wanted to do anything special.

Obviously, there are things that an iPad is not ideal for. And there are things that an iPad can't do. But there are a huge number of apps and for most people, I just can't see what it "can't" do. All most people do is email and Internet anyway.

It can't run big programs like Photoshop, but most people don't need that. You can't run Microsoft Office, but you can get word processing and spreadsheets.

The touchscreen keyboard is not great for typing a lot, but most people don't type a lot. And if you really need it you can use a Bluetooth keyboard. Most people are happy typing on their cellphone! (I manage to type quite long blog posts only iPhone.)

I would guess one of the reasons for this idea is that people get overinflated expectations from all the hype. And when it doesn't (can't) live up to them, they have to blame it on something.

Which is where the critics come in. People don't remember the specific criticisms like the lack of multi-tasking or cameras or memory cards. All they remember is that "there's stuff it can't do".

And there's always the most common reason people say you can't do something - simply because they don't know how to do it. We get that all the time with our software. You ask people how they like the software and they say it's ok but they really wish it could do xyz. Half the time it already can, they just didn't know it.

iPhone Undo/Redo

2010-09-10T08:41:00.001-06:00

I've was getting ready to write a blog post asking why the iPhone doesn't have undo/redo. Selecting text is tricky and it's easy to delete more than you wanted and then have no way to get it back. But when I did a quick search before writing the post, I found it does have it!

If you shake your iPhone you get an undo/redo popup. It appears you can even undo multiple steps, at least in the Notes app.

I'm surprised I didn't run across some mention of this before now. I'm not surprised I didn't discover it on my own. I don't tend to stop and shake my phone in the middle of typing! Maybe the idea is that you get so frustrated you shake your phone?

Honestly, I think this is poor design. First, it's not discoverable. And when people, even experienced ones, don't discover a feature they're probably going to assume it doesn't exist. Second, when I'm typing I generally hold the phone steady in my left hand and type with my right. Shaking is not a natural action, it's like having to take your hands off the keyboard.

Wouldn't it make sense to put an undo key on the keyboard? It could be on the secondary punctuation layout. At least then it would be discoverable. You could still keep the shake interface - presumably someone at Apple thinks it's great.

Connecting the Dots

2010-08-13T09:58:00.000-06:00

Sometimes I'm a little slow :-(

One of the talks at the JVM conference was about a JVM for mobile devices. It used a single pass compiler with no intermediate representation. Suneido also does this but there are some issues with it. Suneido takes the obvious approach of generating a push when it encounters an operand, and an operation when it encounters an operator (after processing its operands). This works great with simple expressions like "a + b" which compiles to "push a, push b, add". But it falls down for more complex things, even for "a = b" since you don't want to push the value of "a". I work around these issues but the code is ugly. And worse, a lot of the ugliness is in the parser, even though the issue is really with code generation.

I wasn't happy with it but, consciously or not, I assumed it was essential rather than accidental complexity. So I didn't look hard enough for a better solution. .

So I was curious to hear more about their approach. The topic only got one bullet point, something like "code generation by abstract interpretation".

I started thinking about what that meant. I'm pretty sure what they meant is that you only generate code when you encounter an operator. When you encounter an operand like a literal or variable, you push it on a compile time stack, "simulating" execution. Then you can defer generation of code until you know what is needed.

As I thought about this, I realized I knew about this technique, I'd read about it before. But for some reason I never connected it to my code generation issues.

So when I got home from the conferences I spent three days refactoring the code generation in jSuneido. It wasn't quite as straightforward as I imagined (it never is!). The parser code is definitely cleaner but I had to add more code to the code generator than I would have liked. Overall, I think it's better. I broke a lot of tests in the process, but I finally got them all passing again last night.

Now I can quite easily add a number of optimizations that I've been wanting to do:

- constant folding

- call private methods directly (no method lookup required)

- call built-in global functions/classes directly

However, there are still things I'd like to do that are difficult with a single pass compile. For example, knowing which local variables are read or written by closures. One way to handle this would be to re-compile if the assumptions were wrong, using information from the first try to do it correctly the second time. But that seems ugly. Maybe I need to drop the single pass compile and just generate an AST.

JVM Languages Summit Day 2

2010-07-28T09:46:00.000-06:00

Another good day of talks starting with Doug Lea on parallel recursive decomposition using fork-join. Amazing how much subtle tweaking is require to get good performance.

This led into Joshua Bloch's talk on performance. There is so much complexity in all the layers from CPU to OS to language that performance varies a lot. He showed a simple example of a Java program that gave consistent times on multiple runs within a given JVM, but sometimes when you restarted the JVM it would consistently give quite different results! Cliff Click's theory was that it was caused by non-deterministic behavior of the JIT compiler since it runs concurrently. The behavior is still "correct", it can just settle into different states. The solution? Run tests over multiple (eg. 40) different JVM instances. That's on any given machine, of course you should also test on different CPU's and different numbers of cores. Easy for them to say.

Neal Gafter talked about Microsoft's LINQ technology - pretty cool, although nothing to do with the JVM.

Kresten Thorup talked about his Erlang implementation on the JVM using Kilim for coroutines. Erlang is an interesting language, and quite different from Java so it was interesting to see how he implemented it. He actually runs the byte code produced by the existing Erlang compiler.

I talked to Remi Forax about whether I should use his JSR292 backport in jSuneido. This would let me use the new technology before Java 7 is released (who knows when). Of course, he said I should. But ... it means developing with the "beta" JDK 7 which still has bugs and is not supported by IDE's. And then it requires an extra run-time agent. I'm not sure I want to complicate my life that much!

JVM Languages Summit Day 1

2010-07-26T20:50:00.000-06:00

My hotel is "behind" the Sun/Oracle campus so I had to circle around through the endless acres of parking lots to get to the right entrance. But it was pretty easy, and not as far as it looked on the map. I've never had much to do with giant organizations so it's still a little mind boggling when you use an automated kiosk (like the ones at the airport) to get your visitors badge.

The sessions were a real mixture, from stuff where the nuances were pretty much over my head, to thinly veiled sales pitches with no technical details. It was pretty neat to be in the company of people you're used to thinking of as gurus, like Doug Lea, John Rose, Joshua Bloch, and Cliff Click. And nice to see they have their frustrations with the technology also.

It's naive of me, but unconsciously I expect really smart people to be "rational", and it's always a bit of a disappointment when that proves to be untrue. Smart people have egos, are insecure, or argumentative, or negative, or defensive, or obnoxious, just like everyone else.

Maybe I'm just too soft, but I felt bad for one guy who basically got told he was doing it wrong. It seems like they could just have well asked "did you consider ..." or "what would you think about ...", rather than just "that's wrong, you should have done ..."

Mostly I just listened to the conversations. In the Java / JVM area I still feel like a relative novice and I'm not sure I have much to contribute yet. But for the most part I didn't feel too much out of my depth, so that's good.

OSCON Wrapup

2010-07-25T09:10:00.000-06:00

The last two days of OSCON were good.

I got to hear Rob Pike talk about the Go language. Rob is a legend in software and Go is a cool language. In some ways Go is more like C or C++ in that it's compiled to machine code with no VM. But unlike C++ it compiles extremely fast. For what he called a party trick he showed it compiling every time he typed a character - and it kept up. It has features I miss in Java like pointers (but safe) and values on the stack (not always allocated). It also has "goroutines" - lightweight threads like coroutines. But its attractions aren't quite sufficient to tempt me away from Java. They don't even have a Windows version yet, let alone all the support libraries and frameworks that Java has.

I also got to hear another legend, Walter Bright, talk about his D language. I used Walter's C and C++ compilers for many years. D also has some very interesting features. Andrei Alexandrescu of Modern C++ Design fame is now working on D and has written The D Programming Language book.

One feature D has that is sorely missing from other languages is the ability to declare functions as "pure" (ie. no side effects) and have the compiler verify it. This (not lambdas) is the key to functional programming. And yet languages like Scala that claim to support functional programming don't have this.

I also went to a talk by Tim Bray whose blog I read. He was working at Sun but moved to Google after the Oracle buyout. His talk was on concurrency. He was very pro Erlang and Clojure but didn't mention Scala. When asked about it he said he thought the Scala language was too big. It does have a sophisticated type system, but the actual syntax is quite simple - smaller than Java. Scala's Actor implementation has been criticized but it's been improved in 2.8 and there are alternatives like Akka.

OSCON Another Day

2010-07-21T23:00:00.000-06:00

After the less than thrilling key notes, I went to another Scala session. A lot of it was repetition, but I learn a bit more at each one. The recurring theme seems to be if you're going to use Scala, use Simple Build Tool (SBT).

Next I went to a talk on GPARS, a Groovy concurrency library. The talk was as much about concurrent programming patterns as about Groovy, which suited me.

Next, I was going to go to one of the database talks, but then I realized it was a vendor presentation and they're usually more sales spiel than technical. Looking for an alternative I noticed Robert (R0ml) Lefkowitz had a talk on Competition versus Collaboration. If you've never listened to one of his talks, it's well worth it. They are as much performances as presentations and always thought provoking. (search for Lefkowitz on the Conversations Network)

Next was a talk on Clojure (a Lisp that runs on the JVM). The title was "Practical Clojure Programming" which sounds like an intro, but it was actually about build tools, IDE's, and deployment. Like most of the audience, I would have rather heard more about Clojure itself. I guess we should have read the description closer.

Finally, I snuck into the Emerging Languages Camp to hear Charles Nutter talk about Myrah (formerly Duby) his close-to-the-JVM-but-like-Ruby language. I would have been tempted to go to the Emerging Languages Camp (it was even free) but by the time they announced it, I'd already signed up for the regular sessions.

All in all, a pretty good day. Lots of food for thought, which is, of course, the point.

One thing I forgot to mention yesterday is that a lot of the Scala people are also (or ex-) Ruby/Rails people. Maybe that's simply because they're the kind of people that like to learn/adopt new things.

But a lot of people left Java and went to Ruby, so it's surprising to see them coming almost full circle back to Scala. Scala is better than Java, but it's still a statically typed language like Java, which is part of what people seemed to reject. Maybe Ruby wasn't the silver bullet they were hoping. Maybe it was performance issues. Maybe they realized that static typing does have advantages after all. Maybe they realized the advantages of running on the JVM (although jRuby allows that). Maybe Scala's improvements over Java are enough to win people back.

OSCON Part One - Scala

2010-07-20T19:21:00.000-06:00

I just finished the first day and a half of OSCON - in the Scala Summit. And contrary to my anti-social nature, I even went to a Scala meetup last night.

As I've written before, I'm quite intrigued with the Scala programming language. It runs on the JVM and interfaces well with Java. It combines functional and object-oriented programming. It has actors for concurrency. And it has a rich type system that is probably Turing complete, like C++ templates.

Scala seems to be attracting a lot of attention. Of course, the Scala Summit attendees are all keen, but there were also several other language developers (like Charles Nutter of jRuby) interested in borrowing ideas from Scala.

Programming in Java is like driving a truck. It's not fast or fuel efficient or fun to drive or comfortable. But it gets the job done without a lot of problems and it can haul just about anything.

Why do people like to drive a fast car? It's not like they regularly need go from 0 to 60 in 5 seconds, or hit 200 km/hr. But they like to know that if they "need" to, they could.

Similarly, I think people like to know their language "has a lot of power under the hood", even if they never use it. And it gives lots of potential for books and conference talks that keep people excited.

And like you could use C++ simply as a better C, you can use Scala as a better Java. This lets less sophisticated users get involved as well.

The funny part is that it's very reminiscent of C++. There were all kinds of talks and articles and books about all the cool stuff you could do with templates and other fancy C++ features. Now, all you hear are negative comments about C++, too complicated, too hard to use, etc. I start to think I'm the only person that liked C++.

But there are differences too. Scala didn't try to be backwards compatible with Java the way C++ was backwards compatible with C. And Java already had object-oriented programming, so Scala isn't as big a jump as C++ (in that respect).

If nothing else, it's made me really want to spend some more time with Scala. It will sound crazy, but I'm very tempted to rewrite jSuneido in Scala. Thankfully, that's something that could be done gradually. I think it would let me make the code much smaller and cleaner. I think it would also make it easier to switch back and forth with Suneido coding, since Scala has things like named and default arguments, optional semicolons, and type inference that make the code much more similar to Suneido code.

Time Capsules

2010-07-07T12:18:00.001-06:00

I use an Apple Time Capsule for my home wireless router and backup storage.

Time Capsules have a bad reputation for dying and I've had mine for quite a few years so I was a little nervous about it. If it died I wouldn't have a backup of my iMac. Which would be ok unless it happened to die at the same time. This seems unlikely, but it's surprising how often you do get simultaneous failures. For example, a power surge due to lightning. I can also keep the external drive at work so I have an offsite backup in case the house burns down.

I had a 500gb external drive that I'd used for backups, but it's not big enough to do a complete backup of my 1tb iMac. So I went and bought a Lacie 2tb external drive and used SuperDuper to make a backup. I used the free version, but I'll probably get the paid version so I can update the backup without redoing it.

Then I decided I should also backup my MacBook and my MacMini. I didn't have much critical stuff on them, but a backup would save hassle if I needed to restore. But SuperDuper takes over the whole drive so how could I backup additional machines? The answer seemed to be to partition the drive, but I didn't want to have to redo my iMac backup (600gb takes a while to backup, even with Firewire 800). I searched on the web and found various complicated ways to resize partitions. Finally, I found that with recent OS X you can resize right from the Disk Utility. All the complicated instructions were for older versions of OS X.

The "funny" part of this story is that a few days later I went to use wireless and it wasn't working. I went and checked on the Time Capsule and it was turned off. Strange, because I leave it running all the time. I turned it on and about 10 seconds later it turned itself back off.

My computer was still fine, so I didn't actually need the external backup, but I was glad to have it nonetheless.

I phoned the local Apple dealer (Neural Net). The receptionist wanted me to bring it in and they would look at it in the next few days. I didn't want to be without internet for days so she let me speak to the technician. When I described the symptoms he said the power supply had died. But Apple doesn't let them repair them and doesn't supply any parts. Apple has been promoting their environmentally friendly products, but no matter how they're built, a non-repairable "disposable" product isn't very environmentally friendly.

I would have preferred to give Neural Net the business but they didn't have any Time Capsules in stock so I picked up a 2tb Time Capsule from Future Shop. 10 minutes after opening the box I was back up and running. (Although the initial Time Machine backups took considerably longer.)

One nice thing is that Time Machine backups seem to be a lot less intrusive. Before, when Time Machine kicked in it would really bog down my machine. If I was trying to work I'd often stop it. But now I don't even notice when it runs. I'm not sure how a new external device would change the load on my computer, but it's nice anyway.

My old Time Capsule ran quite hot, even when it wasn't doing anything. I was hoping the new ones would be better, but it seems much the same. I haven't measured it, but I assume heat means power consumption. I'm not sure why it can't go into a low power mode when it's not active. The other reason they run hot is that they have no ventilation or heat sink. Apparently there is an internal fan but all it does is stir the air around inside a small sealed box. You'd think they could come up with some better heat management without compromising their design. I would guess the heat is one of the big reasons they have a reputation for dying. Electronic components tend to have a shorter life at higher temperatures.

Rather than throwing out the old Time Capsule, I passed it on to one of the guys at work that tinkers with hardware. I thought he could at least extract the 1tb drive. But he managed to repair the power supply and is using the whole unit. I guess the hardest part was getting the case open! I'm glad it was saved from the landfill for a while longer.

Now that I have a bigger drive I thought I might as well backup Shelley's Windows machine as well. I have it set up with Mozy for on-line backups but just with the free 2gb account so I'm only backing up selected things. I'd seen Mozy will now backup to external drives so I thought I'd set this up. Unfortunately, it only backs up to directly attached drives (i.e. internal or USB) not to network drives. I'm not sure what the logic is behind that choice. I could use different software, but I think what I'll do (I haven't got round to it yet) is to use the old 500gb external drive.

iPhone Multi-tasking

2010-07-06T08:41:00.000-06:00

A lot of people made a big thing about how the iPhone didn't have multi-tasking. But personally, I never saw any of the reasons as very compelling. Given limited cpu power and memory and a tiny screen, it made perfect sense to single task.

Sure, there are probably a few reasonable uses of multi-tasking. But there are way more potential abuses.

I look at my Windows machine, which is continually thrashing away when I'm not doing anything. Every piece of software I install wants to run stuff in the background. Just to check for updates once a week they want to have a process running constantly. That's not a benefit, that's abuse.

Two days after I installed iOS 4 with its long awaited multi-tasking, I went to use my iPhone in the morning and the battery was totally dead - it wouldn't even turn on. It had plenty of power the evening before. I can't be 100% sure of the culprit, but I assume it must have been some application left running by the new multi-tasking. I suspect it was a mapping app that I'd been playing with, probably running the GPS constantly or something like that.

On the other hand, according to Apple, most apps do not actually run in the background, they just get suspended and resumed. If that's really true in all cases, then I'm not sure what drained my battery overnight.

So now I find myself regularly "killing" all the active apps because I'm paranoid about this kind of scenario. Great, a "feature" has imposed a large manual overhead on me.

Hopefully the situation will improve once apps are updated to work better with the multi-tasking. But there will always be poorly behaving apps.

What I find strange is that Apple went from not allowing multi-tasking, to making it the default, with no way to switch it off. It seems like an option that you had to explicitly turn on (or at least some way to disable it) would have still silenced the critics, but wouldn't have imposed the cost on those of us that didn't want it.

Chromium Embedded continued

2010-06-25T13:04:00.000-06:00

Previously I got the Chromium Embedded (CEF) sample application to compile (and run). That was only a tiny step towards what I needed to do.

Suneido has a DLL interface, but it can only handle straightforward interfaces. Although CEF has a DLL with a C interface, it's fairly complicated. So I decided I needed to write a small DLL that Suneido could call that would talk to CEF.

But I wasn't sure what the minimum functionality I'd need. The sample application is actually quite large and complex because it is demonstrating a bunch of features like extensions and plugins. So I started by whittling down the sample to the bare minimum. That process helped me identify the core functions I'd need.

It took me a certain amount of struggling to recall / figure out how to build a Windows DLL. (It's not something I do very often.) Eventually I got to the point where Suneido could see the DLL functions. But calling them didn't work (it gave some weird stack errors). Now what?

Then I remembered the issues with building single-threaded versus multi-threaded. The main version of Suneido we use is built single-threaded (/ML), but CEF is built multi-threaded (/MT). I tried it with a multi-threaded build of Suneido and it worked! (Suneido is still single-threaded, it's just linked with the multi-thread runtime libraries.) Here is Chromium Embedded running in a Suneido window:

Coincidentally, the single/multi-thread version issue has also come up in another area. I'm looking at upgrading my work computer to Windows 7. But before I take the plunge I want to make sure the software I need is going to run under Windows 7. One of the "oldest" packages I use is Visual C++ 2003 (VC7). I would have moved to a more recent version long ago, but VC7 still generates the smallest, fastest executable. I think the main reason for this, is that VC7 was the last version that supported building with the single-threaded libraries. (/ML) I'd prefer to use GCC but it doesn't handle the interface with the Internet Explorer browser component. (It's also a bit slower, but not too bad.) So using CEF instead of IE might also allow switching to GCC.

Updating ASM

2010-06-24T16:03:00.000-06:00

jSuneido uses ASM to generate Java byte code. I was using 3.1 and the current version is 3.3

I wasn't sure if this would be easy or hard. It turned out to be somewhere in between.

First I tried to update my Eclipse plugin. That was a little confusing because I had three update sites showing ASM - eclipse.org, asm.ow2.org, and andrei.gmxhome.de. I'm guessing the eclipse.org one is something internal to Eclipse. I thought asm.ow2.org would be the correct location, but it didn't have the latest version.

Next I downloaded asm-3.3.jar but that didn't work, I needed to download asm-3.3.zip and extract asm-all-3.3.jar This wasn't entirely a surprise because previously I was using multiple asm jar files. I'm not quite sure why the asm-3.3.jar is available as a separate download, but not the asm-all-3.3.jar

Of course, tests failed. The first message was:

java.lang.IndexOutOfBoundsException: Trying to access an inexistant local variable 0
at org.objectweb.asm.tree.analysis.Frame.setLocal(Unknown Source)
at org.objectweb.asm.tree.analysis.Analyzer.analyze(Unknown Source)
at org.objectweb.asm.util.CheckMethodAdapter$1.visitEnd(Unknown Source)
at org.objectweb.asm.util.CheckMethodAdapter.visitEnd(Unknown Source)
at org.objectweb.asm.tree.MethodNode.accept(Unknown Source)
at org.objectweb.asm.commons.TryCatchBlockSorter.visitEnd(Unknown Source)
at org.objectweb.asm.MethodAdapter.visitEnd(Unknown Source)

[I thought "inexistant" was a typo, but it appears to be the French version of nonexistent.]

I searched for other people having this problem and found:

When visitMaxs returns an ArrayIndexOutOfBoundsException, more information would be nice

and

ClassWriter.COMPUTE_FRAMES causes java.lang.ArrayIndexOutOfBoundsException

I didn't resolve this. As a workaround I use CheckClass(visitor, false) to turn off the data flow checks. I am probably doing something wrong, but the byte code passes Java's verification and it runs ok, so presumably it's nothing too serious?

The next problem was that you now have to call visitTryCatchBlock before defining any of it's labels. At first I thought that was easy to fix, just move the calls from the end of the try-catch block to the beginning. But one test failed - with nested try-catch blocks. The problem is that the JVM searches the exception table in order. So inner blocks must come before outer ones. By emitting at the end of the blocks I got the right order. But now that I was forced to emit at the beginning of the blocks, the order was wrong.

This stumped me for a while. The problem is that jSuneido (and cSuneido) compiles in a single pass, generating code as it parses. This avoids building a syntax tree. But it doesn't give much flexibility in the order of generating code. I was having scary thoughts of having to make two passes, or switching over to building an intermediate tree. Of course, I could just go back to ASM 3.1, but in the long run I'd probably need to upgrade (e.g. for invoke dynamic support).

Again I searched for other people having this problem and didn't find anything. I was going to post on the ASM Tracker, but before I did I figured I'd better make sure there wasn't an existing post. As it turned out there was: Provide exception table sorting functionality (I'm not sure why my Google searches didn't find it.) Not only had someone else had the same problem, but they'd come up with a solution, and it was now included in ASM. All I had to do was add TryCatchBlockSorter. It's actually quite simple, once you know that the table is accumulated in a way that allows it to be sorted.

Still, I'm not sure why they added this requirement. It seemed to work fine without it in the previous version.

After that, I just had to fix a few tests to take into account the slight differences in the generated try-catch code and I was back in business.

Chromium Embedded

2010-06-18T16:56:00.000-06:00

Our Suneido applications use the Internet Explorer browser component included in Windows.

This works pretty well, but we are running into a few problems:
- people have a wide variety of IE versions
- some people have Javascript turned off
- security settings are getting more and more restrictive

And in the long run I'd like to run on Mac and Linux which don't have IE built in for some reason :-)

So I've been thinking about using another browser component that we can have better control over. Initially I was looking at Gecko (the Mozilla Firefox engine). There's even a Mozilla ActiveX control with the same interface as IE, but it requires registry changes which isn't always feasible for our clients. I tried to find a workaround for the registry issue but couldn't get it working (and no one on Stack Overflow had an answer).

The recent trend seems to be to use WebKit - like in Safari, Chrome, Google Earth, etc. I found the Chromium Embedded project that seems like it would do the trick.

As a first step, I thought I should try to build the example application.Four hours later I think I have achieved this. Since it wasn't easy, I thought I'd recount the saga in case it might help someone else.

First, the standard build environment seems to be Visual Studio C++ 2005. I had various other version installed but not that one. Unfortunately, it's been replaced by VS 2008 which I tried building with, but it gave a lot of errors. (Although maybe the fixes below would have worked?)

A Stack Overflow post led me to someone's page with links to old versions. When I installed, I got compatibility warnings which suggested some updates. I downloaded the updates but when I tried to install it failed, saying the software wasn't installed. (Even though I could run it.) Instead, I was able to get the updates by running Windows Update.

When I tried to build it couldn't find atlbase.h That's because Visual Studio Express (the free version) doesn't come with the Windows SDK. I already had a Windows Server 2003 SDK installed so I updated Tools - Options to point to it.

But I still got errors about shlwapi.lib missing. It turns out this is part of "Microsoft Web Workshop (IE) SDK", an optional part of the SDK. So I tracked down the right SDK installer and installed it.

Next, I had to patch atlbase.h and atlwin.h as explained in a Code Project post. This cleaned up a bunch more errors. But I was still getting errors about _Module which I fixed based on yet another post.

Then I got errors that I was missing opengl32.lib which stumped me for a while till I found someone else with a similar problem, and ended up at instructions for adding the SDK libraries to Visual Studio. Since you don't actually need opengl32.lib, I'm not sure why the project specifies it.

Initially the Debug version built. It ran, but it had a bad tendency to crash. The Release version seems to be fine.

Another issue is that it's big, about 20mb for the required dll's. I guess that's not that big these days, but it's still a fair size to deploy over the internet.

This all seems way harder than it should be. I realize it's Windows and Visual Studio and C++ and open source, but still! Maybe I've been spoiled by working with Java lately. Java does have benefits.

Azul's Better GC

2010-06-16T11:05:00.000-06:00

InfoQ: Azul Systems To Open Source Significant Technology in Managed Runtime Initiative

Interesting. The more cores you have, the more garbage collection (GC) you need - a result of the shared memory model. So even if you avoid killing your multi-threaded performance with locking overhead, you still have scaling issues with GC.

This may also put pressure on Java to do more to avoid heap allocation (e.g. escape analysis and fixnums).

Responsive Web Design

2010-06-15T09:15:00.000-06:00

A List Apart: Articles: Responsive Web Design

Nice techniques for handling todays huge variation in screen size - from mobile phones to 30 inch monitors.

Email Lives

2010-06-11T21:20:00.000-06:00

Hello Lego World

2010-06-05T15:31:00.001-06:00

Very cool!

via John Nack

Phone Companies Antics

2010-06-02T12:12:00.000-06:00

I had a phone call from Rogers yesterday trying to sell me a "Rocket Stick". I asked if I could use my existing data plan. "Oh, do you have a data plan?" they replied.

I wish these companies would get their act together and use the information they have. They say they're calling me because I'm a "valued customer" but they don't even have my account information. Of course, it's probably a different department or outsourced or one of a dozen other excuses. But it makes them look stupid. One of the first rules of selling is to know your customer.

So they asked me what my plan was ($30 per month for 6gb) and told me "Yes, you can switch to a shared plan". I was pleasantly surprised because I assumed the answer would be "no".

The new plan would be $45 per month for 1gb. Wait a minute, you want me to pay 50% more for 1/6 the service? "Yes, but it would be shared." No thanks, doesn't sound like a good deal to me. (I don't use 6gb and 1gb would probably be fine, but I still don't want to pay more for less! And with 6gb I don't have to worry about my usage, which is a big plus.)

Actually, what I'm really interested in is the Mobile MiFi Hotspot. Then I could use it with my laptop and Shelley would use it with her iPod Touch or laptop at the same time. (Plus any future wifi devices.) I'd looked this up before, but it just said "Out of Stock". I asked about it and they told me they used to have them, but there was some problem with the batteries. That sounded a little lame to me - they're still selling them in the US.

Note: In theory I can share my data plan by tethering my MacBook to my iPhone but it hasn't worked too well when I tried and I haven't spent the time to figure it out. And I don't think that would help with other devices.

see also: AT&T’s cynical act

Impossible Things

2010-06-01T13:46:00.001-06:00

"Why, sometimes I've believed as many as six impossible things before breakfast." Alice in Wonderland

I was testing jSuneido on a Windows system and I got:

java.io.IOException
at java.nio.MappedByteBuffer.force0(Native Method)
at java.nio.MappedByteBuffer.force(MappedByteBuffer.java:154)

So I went to add a try-catch to log this error. But Eclipse told me MappedByteBuffer.force doesn't throw IOException

I check the documentation but it didn't mention IOException either.

This is a "checked" exception, meaning you can't throw it without declaring that you throw it, and you can't call something that may throw it without catching it.

But I guess all that goes out the window when you get down to native methods.

I just caught the more general base Exception instead.

PS. I wasn't able to recreate the error, I just hope it won't come back to haunt me.

Apple Overtakes Microsoft in Market Value

2010-05-30T10:25:00.000-06:00

Apple Overtakes Microsoft in Market Value: End of an Era?: "At the close of Wednesday’s trading, Apple was valued at $222 billion, while Microsoft was worth $219 billion. Apple’s shares ended the day at $244.11, while Microsoft’s finished at a seven-month low of $25.01. And it isn’t only Cupertino’s successes, but also Redmond’s failures that are responsible for the new power dynamic between the two companies. Overall, Microsoft stock is down 20 percent compared to 10 years ago, while the value of Apple’s has grown tenfold over the same period."