I'm not sure if we should be basing all our decisions on measurements done with Map Int. Clients using Map Int can already get a huge speed boost by switching to IntMap. Let's use something more realistic like Map ByteString or Map Integer with some big Integers.