Intermission

After SoC ended I left this blog on complete void. Now I'll probably change that next weeks. Because I needed an address to test OpenID and don't want my latest entry to be 2006 ;-)... Ok, truth is, I wanted to write more, not just random blog entries but also write more code, and talk about them here. Let's see if it will work this time.

Sold Arrays, Delivered Maps

The first idea was use Judy to backend implementation of arrays in Haskell. But, as became clear after a little thought and discussion (and specially pointed by Bulat++ in haskell-cafe), Judy library focus on good performance in dynamic arrays, but this wouldn't beat an memory region and data stored one next to another. The natural way to go was implementing a Map-like type. For this purpose was created a MapM type class to serve as interface for all possible Maps created (also tip by Bulat++)

Judy.IntMap is based on JudyL and allows as key-type any type that could be transformed into a word size representation. Judy.StrMap allows as key-type anything that could be stringable into a CString ending with a \0 character. Both Maps have a ordered traversal into its contents. Then Judy.Hash is based on JudyHS which allows as keys strings containing the \0 character in its strings (it stores the length of string instead of having an end identifier), but doesn't have ordered traversal.

To allow any Haskell type to be used as value for these Maps, was created an interface on top of StablePtrs that would create and deallocate them as needed. This can be modified for specific cases, e.g. Int types doesn't use StablePtrs since they fit in the Word reserved for values in Judy C library.

Saying that, all the tests I proposed in my application do benefit from Maps: Pugs project (as I already described), RBR (which was bounded by its use of Data.Map) and K-Nucleotide naive adaptation (in tests/k-judy.hs).

Pugs meets Judy

This post is also in Pugs' blog :)

In 2006-08-14 I started the Judy integration inside Pugs' trunk. This meant building both Judy and HsJudy in the default Pugs make command and using it for both IArray and IHash types (which represent Array and Hash perl types) and also for interning (convert strings/identifiers to words that have fast equality comparison). Lots of different build errors happened, but after a couple of days and help from the folks at #perl6, the build process became stable.

The most expected feature was providing a good support for sparse arrays, which was chosen by the Perl guys to be the default way to deal with arrays (cf. arrays as elements in contiguous space of memory, easy to navigate and access), and Judy solved this problem.

Some numbers comparing r12203 (pre-Judy) with r12215 (after Judy and some corrections to make it work correctly). I noticed that people in the channel usually get better numbers than I do, but anyway, using GHC 6.4.2, I got:

• ./pugs -C Parse-YAML src/perl6/Prelude.pm: uses the interning code, memory usage drops 15% and is 3% faster here.
• t/closure_traits/first.t was one of tests mentioned in channel. Here Judy version is 9% faster considering runtime (ignoring parsing time, which is the same for both).
• t/builtins/lists/minmax.t is little more than 10% faster for Judy (runtime measure too).

In feather, a P4 using GHC 6.4.1, now comparing r12203 against trunk, I got:

• ./pugs -C Parse-YAML src/perl6/Prelude.pm: uses the variable identifier interning code, 20% faster in trunk.
• t/closure_traits/first.t maintains around 10%.

Also, GHC 6.5 in general seems to be giving better performance: in my machine (an amd64 3200+) mandel.pl with Pugs on 6.5 runs in around 2m2s, with Pugs on 6.4.2 around 7m40s. For src/perl6/Prelude.pm its 4s versus 7s aprox. Since numbers are so different than feather it might mean there's something wrong with my GHC 6.4.2 binary...

Right now, only Judy.StrMap and Judy.IntMap are being used since we got some random segfaults with Judy.Hash. Changing between Judy.StrMap, Judy.Hash, Data.Map (with IORef help) and Data.HashTable now is very easy, since all of them instantiate MapM type-class.

In the near future I'll do some more posts about the SoC experience and all. :)