That is great.
Have you any data about the speedup relative to map sizes?
Milan Straka's benchmarks ran only on very small maps (<= 2^10 elements),
I'd be interested in whether size plays a significant role in the effect.

I just ran an ad-hoc test to get an indication of of the performance gains scale with the map size. I ran the lookup benchmark, which looks up all the elements in a map, and I got a 37% improvement running with a map size of 2^22 elements. Compare this to the 42% gain I get on the same benchmark with a map of 2^10 elements. This is just an indication as I didn't really investigate where the time went. It's something I'd like to look into in the future.

It'd be worthwhile to rerun all the benchmarks on a larger map on a machine with a lot of RAM. The number of elements is simple to change in benchmarks/Benchmarks.hs. To run the benchmark do:

$ cd benchmarks

$ ghc -DTESTING --make -O2 -fforce-recomp -i.. Benchmarks.hs

$ ./Benchmarks

and the run the benchmarks against the old vesion:

$ ghc -DTESTING --make -O2 -fforce-recomp -i../../containers-0.3.0.0 Benchmarks.hs

$ ./Benchmarks

It'll take a while if you use large maps as criterion runs each benchmark 100 times.

I recommend using GHC 6.12.3 as it performs better than e.g. 6.12.1.

-- Johan