What ails GHashTable?

I promised a closer look at GHashTable and ways to improve it; here’s that look and another batch of benchmarks to boot.

This time around I’ve dropped most of the other tables from the plots, keeping only khash and adding results from my GLib branch and Rust’s HashMap, the latter thanks to a pull request from Josh Stone. These tables have closely comparable performance and therefore provide a good reference. Besides, every table tested previously is either generally slower or more memory-hungry (or both), and including them would compress the interesting parts of the plot.

I’ll try to be brief this time¹. For more background, check out my previous post.

Bad distribution

First and foremost, the distribution was terrible with densely populated integer keyspaces. That’s taken care of with a small prime multiplier post-hash.

Peak memory waste

Previously, we’d resize by allocating new arrays and reinserting the entries, then freeing the old arrays. We now realloc() and rearrange the entries in place, lowering peak memory use by about a third. This can prevent going into swap or even crashing out on a memory-constrained system.

Overall memory waste

If you’ve got a sharp eye, you’ll notice that overall memory consumption is lower now too. Whereas the old implementation always made space for 64-bit keys and values, the new one will allocate 32 bits when possible and switch to bigger entries on demand. In the above test, the keys are integers in the range [0 .. 2³²-1], reducing memory consumption by 20% overall. If values had been in [0 .. 2³²-1] too, the reduction would’ve amounted to 40%. A caveat though — negative integers (e.g. from GINT_TO_POINTER()) still require 64 bits due to two’s complement/sign extension.

Load factor mistargeting

When GHashTable is subjected to churn/aging, it will accumulate tombstones, and eventually the sum of entries and tombstones will eclipse the maximum load, resulting in a cleanup. Since a cleanup is just a reinsertion in place, it’s handled similarly to a resize, and we take the opportunity to pick a better size when this happens. Unfortunately, the grow threshold was set at .5 if the table got filled up the rest of the way by tombstones, resulting in post-grow load factors as low as .25. That’s equal to the shrink threshold, so with a little (bad) luck it’d shrink back immediately afterwards.

I changed the threshold to .75, so the load factor intervals (not counting tombstones) now look like this:

  • <.25 → shrink immediately → .5
  • [.25 .. .75] → no change
  • [.75 .. .9375] → grow on cleanup → [.375 .. .46875]
  • >.9375 → grow immediately → .46875

This seems like a more reasonable stable range with less opportunity for fluctuation and waste, and there’s still lots of headroom for tombstones, so cleanups aren’t too frequent.

But it’s slower now?

In some cases, yes — can’t be helped. It’s well worth it, though. And sometimes it’s faster:

This particular run uses less memory than before, which is puzzling at first, since keys and values are both pointers. A look at the test’s smaps reveals the cause:

01199000-08fb8000 rw-p 00000000 00:00 0 [heap]

The heap happened to be mapped in the lower 4GiB range, and GHashTable can now store 32-bit entries efficiently. That means pointers too.

I caught khash doing something interesting in this benchmark. Some time after the aging cycle has started (1), it initiates a tombstone cleanup. In this case it decides to grow the table simultaneously, starting at (2). This could be an example of the kind of load factor mistargeting I mentioned above — certainly it would have a very low load factor for the remainder of the test.

Robin Hood to the rescue?

Short answer: No. Long answer:

Rust uses Robin Hood probing, and the linear shifts required for insertion and deletion start to get expensive as the table fills up. It also came in last in a lookup-heavy load I ran. On the other hand it avoids tombstones, so there’s no need for periodic cleanups, and deletions will make it progressively faster instead of slower. GHashTable’s quadratic probing seems to hold a slight edge, albeit workload-dependent and, well, slight. In any case, I couldn’t find a compelling reason to switch.

What about attack resistance?

The improved GHashTable is much more resistant to accidental misbehavior. However, it wouldn’t be too hard to mount a deliberate attack resulting in critically poor performance². That’s what makes Rust’s HashMap so interesting; it gets its attack resistance from SipHash, and if these benchmarks are anything to go by, it still performs really well overall. It’s only slightly slower and adds a reasonable 4 bytes of overhead per item relative to GHashTable, presumably because it’s storing 64-bit SipHash hashes vs. GHashTable’s 32-bit spit and glue.

I think we’d do well to adopt SipHash, but unfortunately GHashTable can’t support keyed hash functions without either backwards-incompatible API changes or a hacky scheme where we detect applications using the stock g_str_hash() etc. hashers and silently replace them with calls to corresponding keyed functions. For new code we could have something like g_hash_table_new_keyed() accepting e.g. GKeyedHasher.

A better option might be to add a brand new implementation and call it say, GHashMap — but we’d be duplicating functionality, and existing applications would need source code changes to see any benefit.


¹ Hey, at least I tried.

² If you can demo this on my GLib branch, I’ll send you a beer dogecoin nice postcard as thanks. Bonus points if you do it with g_str_hash().

A hash table re-hash

Hash tables! They’re everywhere. They’re also pretty boring, but I’ve had GLib issue #1198 sitting around for a while, and the GNOME move to GitLab resulted in a helpful reminder (or two) being sent out that convinced me to look into it again with an eye towards improving GHashTable and maybe answering some domain-typical questions, like “You’re using approach X, but I’ve heard approach Y is better. Why don’t you use that instead?” and “This other hash table is 10% faster in my extremely specific test. Why is your hash table so bad?”.

And unfairly paraphrased as those questions may be, I have to admit I’m curious too. Which means benchmarks. But first, what exactly makes a hash table good? Well, it depends on what you’re looking for. I made a list.

A miserable pile of tradeoffs

AKA hard choices. You have to make them.

Simple keys vs. complex keys: The former may be stored directly in the hash table and are quick to hash (e.g. integers), while the latter may be stored as pointers to external allocations requiring a more elaborate hash function and additional memory accesses (e.g. strings). If you have complex keys, you’ll suffer a penalty on lookups and when the hash table is resized, but this can be avoided by storing the generated hash for each key. However, for simple keys this is likely a waste of memory.

Size of the data set: Small data sets may fit entirely in cache memory. For those, a low instruction count can be beneficial, but as the table grows, memory latency starts to dominate, and you’ll get away with more complex code. The extra allowance can be used to improve cache efficiency, perhaps with bucketization or some other fancy scheme. If you know the exact size of the data set in advance, or if there’s an upper bound and memory is not an issue, you can avoid costly resizes.

Speed vs. memory generally: There are ways to trade off memory against speed directly. Google Sparsehash is an interesting example of this; it has the ability to allocate the table in small increments using many dynamically growing arrays of tightly packed entries. The arrays have a maximum size that can be set at compile time to yield a specific tradeoff between access times and per-entry memory overhead.

Distribution robustness: A good hash distribution is critical to preventing performance oopsies and, if you’re storing untrusted input, thwarting deliberate attacks. This can be costly in the average case, though, so there’s a gradient of approaches with power-of-two-sized tables and bitmask moduli at the low end, more elaborate hash functions and prime moduli somewhere in the middle, and cryptographically strong, salted hashes at the very high end. Chaining tables have an additional advantage here, since they don’t have to deal with primary clustering.

Mode of operation: Some tables can do fast lookups, but are slower when inserting or deleting entries. For instance, a table implementing the Robin Hood probing scheme with a high load factor may require a large number of entries to be shifted down to make room for an insertion, while lookups remain fast due to this algorithm’s inherent key ordering. An algorithm that replaces deleted entries with tombstones may need to periodically re-hash the entire table to get rid of those. Failed lookups can be much slower than successful ones. Sometimes it makes sense to target specific workloads, like the one where you’re filtering redundant entries from a dataset and using a hash table to keep track of what you’ve already seen. This is pretty common and requires insertion and lookup to be fast, but not deletion. Finally, there are more complex operations with specific behavior for key replacement, or iterating over part of the dataset while permuting it somehow.

Flexibility and convenience: Some implementations reserve part of the keyspace for internal use. For instance, Google Sparsehash reserves two values, one for unused entries and one for tombstones. These may be -1 and -2, or perhaps “u” and “t” if your keys are strings. In contrast, GHashTable lets you use the entire keyspace, including storing a value for the NULL key, at the cost of some extra bookkeeping memory (basically special cases of the stored hash field — see “complex keys” above). Preconditions are also nice to have when you slip up; the fastest implementations may resort to undefined behavior instead.

GC and debugger friendliness: If there’s a chance that your hash table will coexist with a garbage collector, it’s a good idea to play nice and clear keys and values when they’re removed from the table. This ensures you’re not tying up outside memory by keeping useless pointers to it. It also lets memory debuggers like Valgrind detect more leaks and whatnot. There is a slight speed penalty for doing this.

Other externalities: Memory fragmentation, peak memory use, etc. goes here. Open addressing helps with the former, since the hash table then only makes a few big allocations which the allocator can satisfy with mmap() and simply munmap() when they’re not needed anymore. Chaining hash tables make lots of heap allocations, which can get interspersed with other allocations leaving tiny holes all over when freed. Bad!

A note on benchmarks

This isn’t the first time, or the second time, or likely even the 100th time someone posts a bunch of hash table benchmarks on the Internet, but it may be the second or third time or so that GHashTable makes an appearance. Strange maybe, given its install base must number in the millions — but on the other hand, it’s quite tiny (and boring). The venerable hash table benchmarks by Nick Welch still rule the DuckDuckGo ranking, and they’re useful and nice despite a few significant flaws: Notably, there’s a bug that causes the C++ implementations to hash pointers to strings instead of the strings themselves, they use virtual size as a measure of memory consumption, and they only sample a single data point at the end of each test run, so there’s no intra-run data.

He also classifies GHashTable as a “Joe Sixpack” of hash tables, which is uh… pretty much what we’re going for! See also: The Everyman’s Hash Table (with apologies to Philip).

Anyway. The first issue is easily remedied by using std::string in the C++ string tests. Unfortunately, it comes with extra overhead, but I think that’s fair when looking at out-of-the-box performance.

The second issue is a bit murkier, but it makes sense to measure the amount of memory that the kernel has to provide additional physical backing for at runtime, i.e. memory pages dirtied by the process. This excludes untouched virtual memory, read-only mappings from shared objects, etc. while still capturing the effects of allocator overhead and heap fragmentation. On Linux, it can be read from /proc/<pid>/smaps as the sum of all Private_Dirty and Swap fields. However, polling this file has a big impact on performance and penalizes processes with more mappings unfairly, so in the end I settled on the AnonRSS field from /proc/<pid>/status, which works out to almost the same thing in practice, but with a lower and much more fair penalty.

In order to provide a continuous stream of samples, I wrote a small piece of C code that runs each test in a child process while monitoring its output and sampling AnonRSS a hundred times or so per second. Overkill, yes, but it’s useful for capturing those brief memory peaks. The child process writes a byte to stdout per 1000 operations performed so we can measure progress. The timestamps are all in wall-clock time.

The tests themselves haven’t changed that much relative to Welch’s, but I added some to look for worst-case behavior (spaced integers, aging) and threw in khash, a potentially very fast C hash table. I ran the below benchmarks on an Intel i7-4770 Haswell workstation. They should be fairly representative of modern 64-bit architectures.

Some results

As you may have gathered from the above, it’s almost impossible to make an apples-to-apples comparison. Benchmarks don’t capture every aspect of performance, and I’m not out to pick on any specific implementation, YMMV, etc. With that in mind, we can still learn quite a bit.

“Sequential” here means {1, 2, …}. The integer tests all map 64-bit integers to void *, except for the Python one, which maps PyLong_FromLong() PyObjects to a single shared PyObject value created in the same manner at the start of the test. This results in an extra performance hit from the allocator and type system, but it’s a surprisingly good showing regardless. Ruby uses INT2FIX() for both, which avoids extra allocations and makes for a correspondingly low memory overhead. Still, it’s slow in this use case. GHashTable embeds integers in pointers using GINT_TO_POINTER(), but this is only portable for 32-bit integers.

When a hash table starts to fill up, it must be resized. The most common way to do this is to allocate the new map, re-inserting elements from the old map into it, and then freeing the old map. Memory use peaks when this happens (1) because you’re briefly keeping two maps around. I already knew that Google Sparsehash’s sparse mode allows it to allocate and free buckets in small increments, but khash’s behavior (2) surprised me — it realloc()s and rearranges the key and value arrays in-place using an eviction scheme. It’s a neat trick that’s probably readily applicable in GHashTable too.

Speaking of GHashTable, it does well. Suspiciously well, in fact, and the reason is g_direct_hash() mapping input keys {1, 2, …} to corresponding buckets {1, 2, …} hitting the same cache lines repeatedly. This may sound like a good thing, but it’s actually quite bad, as we’ll see later in this post. Normally I’d expect khash to be faster, but its hash function is not as cache-friendly:

#define kh_int64_hash_func(key) (khint32_t)((key)>>33^(key)^(key)<<11)

Finally, it’s worth mentioning Boost’s unique allocation pattern (3). I don’t know what’s going on there, but if I had to guess, I’d say it keeps supplemental map data in an array that can simply be freed just prior to each resize.

This is essentially the same plot, but with the time dimension replaced by insertion count. It’s a good way to directly compare the tables’ memory use over their life cycles. Again, GHashTable looks good due to its dense access pattern, with entries concentrated in a small number of memory pages.

Yet another way of slicing it. This one’s like the previous plot, but the memory use is per item held in the table. The fill-resize cycles are clearly visible. Sparsehash (sparse) is almost optimal at ~16 bytes per item, while GHashTable also stores its calculated hashes, for an additional 4 bytes.

Still noisy even after gnuplot smoothing, this is an approximation of the various tables’ throughput over time. The interesting bits are kind of squeezed in there at the start of the plot, so let’s zoom in…

Hash table operations are constant time, right? Well — technically yes, but if you’re unlucky and your insertion triggers a resize, you may end up waiting for almost as long as all the previous insertions put together. If you need predictable performance, you must either find a way to set the size in advance or use a slower-and-steadier data structure. Also noteworthy: Sparsehash (dense) is by far the fastest at peak performance, but it struggles a bit with resizes and comes in second.

This one merits a little extra explanation: Some hash tables are fast and others are small, but how do you measure overall resource consumption? The answer is to multiply time by memory, which gets you a single dimension measured in byte-seconds. It’s more abstract, and it’s not immediately obvious if a particular Bs measurement is good or bad, but relatively it makes a lot of sense: If you use twice as much memory as your competitor, you can make up for it by being twice as fast. Since both resources are affected by diminishing returns, a good all-rounder like GHashTable should try to hit the sweet spot between the two.

Memory use varies over time, and consequently it’s not enough to multiply the final memory consumption by total run time. What you really want is the area under the graph in the first plot (memory use over time), and you get there by summing up all the little byte-second slices covered by your measurements. You plot the running sum as you sweep from left to right, and the result will look like the above.

It’s not enough to just insert items, sometimes you have to delete them too. In the above plot, I’m inserting 20M items as before, and then deleting them all in order. The hash table itself is not freed. As you can probably tell, there’s a lot going on here!

First, this is unfair to Ruby, since I suspect it needs a GC pass and I couldn’t find an easy way to do it from the C API. Sorry. Python’s plot is weird (and kind of good?) — it seems like it’s trimming memory in small increments. In GLib land, GHashTable dutifully shrinks as we go, and since it keeps everything in a handful of big allocations that can be kept in separate memory maps, there is minimal heap pollution and no special tricks needed to return memory to the OS. Sparsehash only shrinks on insert (this makes it faster), so I added a single insert after the deletions to help it along. I also put in a malloc_trim(0) without which the other C++ implementations would be left sitting on a heap full of garbage — but even with the trim in, Boost and std::unordered_map bottom out at ~200MB in use. khash is unable to shrink at all; there’s a TODO in the code saying as much.

You may have noticed there are horizontal “tails” on this one — they’re due to a short sleep at the end of each test to make sure we capture the final memory use.

Another insertion test, but instead of a {1, 2, …} sequence it’s now integers pseudorandomly chosen from the range [0 .. 2²⁸-1] with a fixed seed. Ruby performs about the same as before, but everyone else got slower, putting it in the middle of the pack. This is also a more realistic assessment of GHashTable. Note that we’re making calls to random() here, which adds a constant overhead — not a big problem, since it should affect everyone equally and we’re not that interested in absolute timings — but a better test might use a pregenerated input array.

GHashTable is neck-and-neck with Sparsehash (dense), but they’re both outmatched by khash.

With spaced integers in the sequence {256, 512, 768, …}, the wheels come off Sparsehash and khash. Both implementations use table sizes that are powers of two, likely because it makes the modulo operation faster (it’s just a bitmask) and because they use quadratic probing, which is only really efficient in powers of two. The downside is that integers with equal low-order bits will be assigned to a small number of common buckets forcing them to probe a lot.

GHashTable also uses quadratic probing in a power-of-two-sized table, but it’s immune to this particular pattern due to a twist: For each lookup, the initial probe is made with a prime modulus, after which it switches to a bitmask. This means there is a small number of buckets unreachable to the initial probe, but this number is very small in practice. I.e. for the first few table sizes (8, 16, 32, 64, 128, 256), the number of unreachable buckets is 1, 3, 1, 3, 1, and 5. Subsequent probing will reach these.

So how likely is this kind of key distribution in practice? I think it’s fairly likely. One example I can think of is when your keys are pointers. This is reasonable enough when you’re keeping sets of objects around and you’re only interested in knowing whether an object belongs to a given set, or maybe you’re associating objects with some extra data. Alignment ensures limited variation in the low-order key bits. Another example is if you have some kind of sparse multidimensional array with indexes packed into integer keys.

Total resource consumption is as you’d expect. I should add that there are ways around this — Sparsehash and khash will both let you use a more complex hash function if you supply it yourself, at the cost of lower performance in the general case.

Yikes! This is the most complex test, consisting of populating the table with 20M random integers in the range 0-20M and then aging it by alternatingly deleting and inserting random integers for another 20M iterations. A busy database of objects indexed by integer IDs might look something like this, and if it were backed by GHashTable or Sparsehash (sparse), it’d be a painfully slow one. It’s hard to tell from the plot, but khash completes in only 4s.

Remember how I said GHashTable did suspiciously well in the first test? Well,

We’re paying the price. When there are a lot of keys smaller than the hash table modulus, they tend to concentrate in the low-numbered buckets, and when tombstones start to build up it gets clogged and probes take forever. Fortunately this is easy to fix — just multiply the generated hashes by a small, odd number before taking the modulo. The compiler reduces the multiplication to a few shifts and adds, but cache performance suffers slightly since keys are now more spread out.

On a happier note…

All the tests so far have been on integer keys, so here’s one with strings of the form “mystring-%d” where the decimal part is a pseudorandomly chosen integer in the range [0 .. 2³¹-1] resulting in strings that are 10-19 bytes long. khash and GHashTable, being the only tables that use plain C strings, come out on top. Ruby does okay with rb_str_new2(), Python and QHash are on par using PyDict_SetItemString() and QString respectively. The other C++ implementations use std::string, and Sparsehash is really not loving it. It almost looks like there’s a bug somewhere — either it’s copying/hashing the strings too often, or it’s just not made for std::string. My impression based on a cursory search is that people tend to write their own hash functions/adapters for it.

GHashTable’s on its home turf here. Since it stores the calculated hashes, it can avoid rehashing the keys on resize, and it can skip most full key compares when probing. Longer strings would hand it an even bigger advantage.

Conclusion

This post is really all about the details, but if I had to extract some general lessons from it, I’d go with these:

  • Tradeoffs, tradeoffs everywhere.
  • Worst-case behavior matters.
  • GHashTable is decent, except for one situation where it’s patently awful.
  • There’s some room for improvement in general, cf. robustness and peak memory use.

My hash-table-shootout fork is on Github. I was going to go into detail about potential GHashTable improvements, but I think I’ll save that for another post. This one is way too long already. If you got this far, thanks for reading!

Introducing Chafa

Chafa

Here’s something I didn’t know: The DEC VT100 turns 40 in August. This factlet comes courtesy of Wikipedia, as I’m not quite old and wise enough to have made its acquaintance outside of a museum. None the less, the VT100 and its extended family of hard-working office furniture has always been with me in terms of the ECMA-48 standard, better known as ANSI X3.64 or simply (and these days, probably as accurately as any formal descriptor) “ANSI codes“, which it helped pioneer.

This pinnacle of 1970s UX is somehow still going strong, and recent developments like lots and lots of colors, ubiquitous Unicode support, good monospace fonts, etc. have opened up some interesting possibilities for creative abuse in a rich tradition that dates all the way back to manual typewriters, if not further. Previous entrants in this category are the venerable aalib and libcaca, and more recently there’s timg and others that use the U+2580 half-block symbol.

I wrote a small tool to further improve on this. It combines a range of Unicode symbols in an attempt to minimize the squared error of the output, and has plenty of bells and whistles besides. Check it out.

GNOME and Rust

I’ve been keeping an eye on Rust for a while now, so when I read Alberto’s statement of support for more Rust use in GNOME, I couldn’t resist piling on…

From the perspective of someone who’s quite used to C, it does indeed seem to tick all the boxes. High performance, suitability for low-level tasks and C ABI compatibility tend to be sticking points with new languages — and Rust kills it in those departments. Anyone who needs further convincing should read up on Raph Levien’s font renderer. The usual caveat about details vis-a-vis the Devil applies, but the general idea looks exactly right. Rust’s expressiveness and lack of baggage means it could even outperform C for non-trivial code, on top of all the other advantages.

There are risks too, of course. I’d worry about adoption, growth and the availability of bindings/libraries/other features, like a good optional GC for high-level apps (there is at least one in the works, but it doesn’t seem to be quite ready for prime-time yet). Rust is on an upwards trajectory, and there doesn’t seem to be many tasks where it’s eminently unsuitable, so in theory, it could have a wide reach: operating systems, platform libraries, both client- and server-side applications, games and so on. However, it doesn’t appear to be the de facto language in many contexts yet. Consider the statement “If I learn language X, I will then be able to work on Y.” Substitute for X: Java, Javascript, Python, ObjC, C, C++, C# or even Visual Basic — and Y becomes obvious. How does Rust fare?

That is, of course, a very conservative argument, while in my mind the GNOME project represents, for better or worse, and C use notwithstanding, a more radical F/OSS philosophy. Its founding was essentially formulated as a revolt against the Qt license (and a limited choice of programming languages!), it was an early adopter of Git for version control, and it’s a driver for Wayland and Flatpak now. For what it’s worth, speaking as mostly a downstream integrator, I wouldn’t mind it if GNOME embraced its DNA yet again and fully opened the door to Rust.

Novell hack week, day 4

Four days down. How time flies when you’re having fun. I must admit that Sterling is barely past the point where it creates a panel applet that does nothing – but on the other hand, I’ve absorbed a bit of how-to on C# and Mono tools. It’s rather pleasant so far.

Apart from the panel applet business, I’ve gotten the build framework for GConf schemas, gettext, icons and UI files out of the way, so I think it’s fair to say it’s getting ready to administer kicks to the proverbial hindside. I’ll have a public Git repo up sometime tomorrow.

Sterling panel applet
Hey, it’s a start.

Novell hack week, day 2

Day 2 is at an end, and I’ve spent it learning about C# and Mono tools, looking into how other projects do stuff. I now have a Git repository with a fledgling project structure, and a more solid foundation to work from knowledge-wise.

I feel a little bad for posting that Monodevelop screenshot yesterday. The intention wasn’t to make Monodevelop look bad, but rather to convey the occasional feeling of exasperation you can get when learning to use new tools, moving outside your comfort zone. I was using the older version that comes with openSUSE 10.3, assuming that would’ve been patched to fix most serious issues. I was wrong.

Fortunately, the eminent Mr. Hutchinson pointed me in the right direction – I got a newer version from one of his build service repos, and that works much better, although it still spews a little to the terminal. You can tell a lot of work went into it; this is the first time I’ve felt like I’m using a true IDE on Linux, i.e. the “integration” part actually works.

Mike arrived from Mexico City last night and will be spending the next couple of days here. His tiny new Lenovo X series Thinkpad looks totally sweet, but he spent a lot of time fighting poor wireless drivers. I guess most of us can empathize with that. Tomorrow, Tambet and Federico will hopefully join us, and we can all bask in teh hack week synergy.

Novell hack week, day 1

Novell’s hack week has started. For those of you who don’t know what a hack week is, it’s a work week where we, the programmers at Novell, get to goof around with more or less whatever project we find interesting.

I’ve chosen to start a new project called “Sterling”, the goal of which is to keep better track of my moneys. I’ve used GnuCash to do this for some time, but it’s clunky and overkill for my uses. I want to streamline the process of entering transactions and otherwise keep the complexity down, especially for people like me who know (and care) little about accounting. Indeed, I want the UI to resemble Tomboy‘s in many ways:

  • Always running, with a panel applet interface.
  • Desktop-global “new transaction” hotkey.
  • Per-user database, no open/save dialogs.
  • Implicit save on edit.
  • Type-ahead completion of transaction description.
  • Suggesting details of transaction based on similar past transactions.
  • Tagging of transactions for easy cross-sectioning.
  • Simple search-as-you-type view of transaction history.
  • Multiple currencies recognized by their ISO 4217 codes.

Star Trek future features:

  • Currency conversion (use Google?).
  • Multiple registers (similar to books in Tomboy).
  • Export to XML, merge from XML.
  • Remote synchronization (by Zeroconf discovery or specific URI) allowing for shared databases.
  • Desktop search integration.
  • Drop-dead attractive graphs.

In order to make things as difficult for myself as possible, I’ve decided to learn something new and do it in C#/Mono. Of course, I’m already running into trouble…

MonoDevelop got stuck

Strange but true. I miss C, Emacs, Automake already.