Map.toList performance in Haskell

Question

In the code below I'm benchmarking my implementation of Bucket Sort.

The bucketsort function uses the result from _bucketsort but flattens it to a single list. To my surprise this process (Map.toList) takes a lot of time.

module Main where
import System.Random
import Criterion.Main
import qualified Data.List as List
import qualified Data.Map as Map
import Data.Maybe

insert :: (Ord a) => a -> [a] -> [a]
insert x [] = [x]
insert x (y:xs)
    | x <= y    = x:y:xs
    | otherwise = y : insert x xs

bucketsort :: (Integral a) => [a] -> [a]
bucketsort xs = List.concatMap (snd) . Map.toList $ _bucketsort xs Map.empty

_bucketsort :: (Integral k) => [k] -> Map.Map k [k] -> Map.Map k [k]
_bucketsort [] map = map
_bucketsort (x:xs) map =
    let bucket = x `div` 3
        bucketlist = maybeToList $ Map.lookup bucket map
        bucketInsert x [] = [x]
        bucketInsert x xs = insert x $ head xs
        ys = bucketInsert x bucketlist
        newMap = Map.insert bucket ys map
    in _bucketsort xs newMap

dataset n = List.take n $ randomRs (0, 9999) (mkStdGen 42)

main = defaultMain [ bench "bucketsort 96080" $ whnf bucketsort ((dataset 96080) :: [Int])
                   , bench "_bucketsort 96080" $ whnf _bucketsort ((dataset 96080):: [Int])]

And here's the output of the benchmarking by Criterion:

C:\>benchmark_bucketsort.exe
warming up
estimating clock resolution...
mean is 1.353299 us (640001 iterations)
found 1278266 outliers among 639999 samples (199.7%)
  638267 (99.7%) low severe
  639999 (100.0%) high severe
estimating cost of a clock call...
mean is 105.8728 ns (8 iterations)
found 14 outliers among 8 samples (175.0%)
  7 (87.5%) low severe
  7 (87.5%) high severe

benchmarking bucketsort 96080
collecting 100 samples, 1 iterations each, in estimated 24.35308 s
Warning: Couldn't open /dev/urandom
Warning: using system clock for seed instead (quality will be lower)
mean: 187.2037 ms, lb 182.7181 ms, ub 191.3842 ms, ci 0.950
std dev: 22.15054 ms, lb 19.47241 ms, ub 25.64983 ms, ci 0.950
variance introduced by outliers: 84.194%
variance is severely inflated by outliers

benchmarking _bucketsort 96080
mean: 8.823789 ns, lb 8.654692 ns, ub 9.049314 ns, ci 0.950
std dev: 952.9240 ps, lb 723.0241 ps, ub 1.154097 ns, ci 0.950
found 13 outliers among 100 samples (13.0%)
  13 (13.0%) high severe
variance introduced by outliers: 82.077%
variance is severely inflated by outliers

I wouldn't be surprised if my bucketsort function could be written a lot better and hopefully faster. But as of yet I haven't figured out how.

Also, any improvements/comments on my Haskell code are more than welcome.

Answer 1

You are not fully applying _bucketsort in your second benchmark, and are therefore just evaluating a partially applied function to WHNF, which unsurprisingly is quite fast.

Changing the relevant lines to

main = defaultMain [ bench "bucketsort 96080"  $ whnf bucketsort ((dataset 96080) :: [Int])
                   , bench "_bucketsort 96080" $ whnf (flip _bucketsort Map.empty) ((dataset 96080):: [Int])]

yields (on my machine):

warming up
estimating clock resolution...
mean is 2.357120 us (320001 iterations)
found 2630 outliers among 319999 samples (0.8%)
  2427 (0.8%) high severe
estimating cost of a clock call...
mean is 666.7750 ns (14 iterations)
found 1 outliers among 14 samples (7.1%)
  1 (7.1%) high severe

benchmarking bucketsort 96080
collecting 100 samples, 1 iterations each, in estimated 34.66980 s
mean: 244.3280 ms, lb 238.0601 ms, ub 250.6725 ms, ci 0.950
std dev: 32.37658 ms, lb 28.02356 ms, ub 38.10187 ms, ci 0.950
found 3 outliers among 100 samples (3.0%)
  3 (3.0%) low mild
variance introduced by outliers: 87.311%
variance is severely inflated by outliers

benchmarking _bucketsort 96080
collecting 100 samples, 1 iterations each, in estimated 24.65911 s
mean: 244.9425 ms, lb 239.1011 ms, ub 251.0300 ms, ci 0.950
std dev: 30.68877 ms, lb 26.48151 ms, ub 36.20961 ms, ci 0.950
variance introduced by outliers: 86.247%
variance is severely inflated by outliers

Note furthermore that this benchmark isn't fully forcing the list, because whnf on a list will only evaluate the top-level constructor. This explains why both benchmarks have nearly the same performance now. Switching both benchmarks to nf changes the times to 369.3022ms and 354.3513ms, respectively, making bucketsort somewhat slower again.