Unordered-containers slower than hashmap for simple ordered insert

[ndmitchell]

Given:

import qualified Data.HashMap as M1 -- from hashmap
import Data.List
import qualified Data.HashMap.Strict as M2 -- from unordered-containers
import System.Time.Extra -- from the extra package
import Control.Exception

{-# NOINLINE block #-}
block :: [Int] -> [Int]
block = id

main = do
    (print =<<) $ duration $ evaluate $ M1.size $ foldl' (\mp i -> M1.insert i i mp) mempty $ block [1..1000000]
    (print =<<) $ duration $ evaluate $ M2.size $ foldl' (\mp i -> M2.insert i i mp) mempty $ block [1..1000000]

I get the output:

(0.2766973,1000000)
(0.7305192,1000000)

Namely, unordered-containers is 3x slower. I believe this, but with a smaller number in the list, is why Shake is faster on hashmap, as per ndmitchell/shake#418. I submit this separately from #119 because there are no collisions and all keys are packed to the lower bits, so it should avoid all the nasty behaviours in #119, but then still goes slower.

The results persist if I swap the order of the tests, so it does not seem to be GC based. Windows 32bit, GHC 7.10.2, hashmap-1.3.0.1, unordered-containers-0.2.7.0.

[ndmitchell]

CC @augustss

[tibbe]

I don't have time to look at this just now, but I know that u-c is somewhat slower on pure inserts compared to IntMap (there's more memory allocated as the tree is fatter). There are some memory optimizations to be done (there's a recent OPSLA paper about it), but nothing I have time for now.

[sjakobi]

@tibbe What's that OPSLA paper?

[tibbe]

@sjakobi maybe it was https://2015.splashcon.org/details/splash2015-artifacts/3/Optimizing-Hash-Array-Mapped-Tries-for-Fast-and-Lean-Immutable-JVM-Collections. I no longer remember.

[sjakobi]

#387 may help to speed up insertions.