Prestazioni Map.toList in Haskell

Question

Nel codice seguente sto analizzando la mia implementazione di Ordinamento Bucket.

La funzione bucketsort utilizza il risultato da _bucketsort ma lo appiattisce in un unico elenco. Con mia sorpresa questo processo (Map.toList) richiede molto tempo.

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])] 

Ed ecco l'output del benchmarking da 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 

non sarei sorpreso se la mia funzione bucketsort potrebbe essere scritta molto meglio e si spera più veloce. Ma per ora non ho capito come.

Inoltre, eventuali miglioramenti/commenti sul mio codice Haskell sono più che benvenuti.

Answer 1

Non si sta applicando completamente _bucketsort nel secondo benchmark e pertanto si sta valutando solo una funzione parzialmente applicata a WHNF, che in modo non sorprendente è abbastanza veloce.

Modifica delle linee rilevanti per

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

rendimenti (sulla mia macchina):

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 

Nota inoltre che questo benchmark non sta forzando completamente la lista, perché whnf in un elenco soltanto volontà valutare il costruttore di livello superiore. Questo spiega perché entrambi i benchmark hanno quasi le stesse prestazioni ora. Passando entrambi i benchmark a nf, le volte cambiano rispettivamente a 369.3022ms e 354.3513ms, rendendo nuovamente bucketsort un po 'più lento.