Skip to content

Instantly share code, notes, and snippets.

@int-e

int-e/IntMapFAL.hs

Last active July 19, 2020 07:00
Star
Embed
What would you like to do?
Learn more about clone URLs
Download ZIP
fromAscList stuff
Raw
README.md

Scratch files relating to fromAscList

  • IntMapFAL.hs -- various implementations of fromList for Data.IntMap
    • fromList, fromAscList, fromDistinctAsclist: current implementation as of 9231fd7a298cc30b07b5b9c31eb1e7eff6a14738
    • fromList1: implementation from #653
    • fromDistinctAscList1: as proposed in #654
    • fromDistinctAscList1a: as proposed in #654 (abandoned specialization)
    • fromAscList1: naive on-the-fly key collapsing
    • fromAscList1a: improved on-the-fly key collapsing... this version is faster than fromDistinctAscList1a!
    • fromDistinctAscList1b, fromDistinctAscList1c, fromDistinctAscList1d, fromDistinctAscList1e: various attempts at matching the speed of fromAscList1a
    • fromAscList1b, fromAscList1c: attempted micro-optimizations
  • IntMapFAL.out -- corresponding benchmark results (best of breed modulo minor fluctuations: fromAscList1a)
  • IntMapFAL2.hs -- check that implementing fromList in terms of fromListWithKey does not hurt performance
  • IntMapFAL2.out -- corresponding benchmark results
  • IntSetFAL.hs -- implement fromAscList for sets based on fromAscListWithKey
  • IntSetFAL.out -- corresponding benchmark results

Scratch files relating toe fromList

Raw
IntMapFAL.hs
-- ghc -O2 -hide-package containers IntMapFAL.hs && ./IntMapFAL --small | tee IntMapFAL.out
{-# LANGUAGE BangPatterns #-}
{-# LANGUAGE RankNTypes #-}
import Control.DeepSeq (rnf)
import Control.Exception (evaluate)
import Gauge (bench, bgroup, env, defaultMain, whnf)
import Data.List (foldl')
import qualified Data.IntMap as M
import qualified Data.IntMap.Strict as MS
import Data.Maybe (fromMaybe)
import Prelude hiding (lookup)
import GHC.Exts (inline)
import Data.IntMap.Internal (IntMap (..), Prefix, Mask, Key, size, link, branchMask, mask, shorter, nomatch, zero)
import qualified Data.IntMap.Internal as I
main = do
defaultMain $ [test (s*sz) sk |
sz <- [10^i | i <- [0..5]],
(s, sk) <- if sz == 1 then [(1,1)] else [(1,1), (-1,51791)]]
test sz sk =
env (let m = M.fromAscList elems :: M.IntMap Int in evaluate $ rnf [m]) $ \m -> bgroup n
[ bench "fromList" $ whnf M.fromList elems
, bench "fromList1" $ whnf fromList1 elems
, bench "fromAscList" $ whnf M.fromAscList elems
, bench "fromAscList1" $ whnf fromAscList1 elems
, bench "fromAscList1a" $ whnf fromAscList1a elems
, bench "fromAscList1b" $ whnf fromAscList1b elems
, bench "fromDistinctAscList" $ whnf M.fromDistinctAscList elems
, bench "fromDistinctAscList1" $ whnf fromDistinctAscList1 elems
, bench "fromDistinctAscList1a" $ whnf fromDistinctAscList1a elems
, bench "fromDistinctAscList1b" $ whnf fromDistinctAscList1b elems
, bench "fromDistinctAscList1c" $ whnf fromDistinctAscList1c elems
, bench "fromDistinctAscList1d" $ whnf fromDistinctAscList1d elems
, bench "fromDistinctAscList1e" $ whnf fromDistinctAscList1e elems
]
where
n = "[" ++ show sz ++ "," ++ show sk ++ "]"
elems = zip keys values
keys = map (sk*) (if sz < 0 then [2*sz `div` 3.. -sz `div` 3] else [0..sz])
values = [1..]
data Inserted a = Inserted !(IntMap a) ![(Key,a)]
fromDistinctAscList1 :: [(Key,a)] -> IntMap a
fromDistinctAscList1 [] = Nil
fromDistinctAscList1 ((kx,vx) : zs0) = addAll kx (Tip kx vx) zs0
where
-- invariant for `addAll` and `addMany`: `kx` is a key in the map `tx`.
addAll !kx !tx []
= tx
addAll !kx !tx ((ky,vy) : zs)
| m <- branchMask kx ky
, Inserted ty zs' <- addMany m ky (Tip ky vy) zs
= addAll kx (link ky ty kx tx) zs'
-- addMany adds all elements that have the same prefix as `kx` w.r.t.
-- the branch mask `m` to `tx`.
addMany !m !kx tx []
= Inserted tx []
addMany !m !kx tx zs0@((ky,vy) : zs)
| mask kx m /= mask ky m
= Inserted tx zs0
| Inserted ty zs' <- addMany (branchMask kx ky) ky (Tip ky vy) zs
= addMany m kx (link ky ty kx tx) zs'
fromDistinctAscList1a :: [(Key,a)] -> IntMap a
fromDistinctAscList1a [] = Nil
fromDistinctAscList1a ((kx,vx) : zs0) = addAll kx (Tip kx vx) zs0
where
-- invariant for `addAll` and `addMany`: `kx` is a key in the map `tx`.
addAll !kx tx []
= tx
addAll !kx tx ((ky,vy) : zs)
| m <- branchMask kx ky
, Inserted ty zs' <- addMany m ky (Tip ky vy) zs
= addAll kx (link ky ty kx tx) zs'
-- addMany adds all elements that have the same prefix as `kx` w.r.t.
-- the branch mask `m` to `tx`.
addMany !m !kx tx []
= Inserted tx []
addMany !m !kx tx zs0@((ky,vy) : zs)
| mask kx m /= mask ky m
= Inserted tx zs0
| m' <- branchMask kx ky
, Inserted ty zs' <- addMany m' ky (Tip ky vy) zs
= addMany m kx (Bin (mask kx m') m' tx ty) zs'
fromDistinctAscList1b :: [(Key,a)] -> IntMap a
fromDistinctAscList1b [] = Nil
fromDistinctAscList1b ((kx,vx) : zs1) = addAll' kx vx zs1
where
addAll' !kx vx [] = inline addAll kx (Tip kx vx) []
addAll' !kx vx ((ky,vy) : zs) = inline addAll kx (Tip kx vx) ((ky,vy) : zs)
-- invariant for `addAll` and `addMany`: `kx` is a key in the map `tx`.
addAll !kx !tx []
= tx
addAll !kx !tx ((ky,vy) : zs)
| m <- branchMask kx ky
, Inserted ty zs' <- addMany' m ky vy zs
= addAll kx (link ky ty kx tx) zs'
addMany' !m !kx vx [] = inline addMany m kx (Tip kx vx) []
addMany' !m !kx vx ((ky,vy) : zs) = inline addMany m kx (Tip kx vx) ((ky,vy) : zs)
-- addMany adds all elements that have the same prefix as `kx` w.r.t.
-- the branch mask `m` to `tx`.
addMany !m !kx tx []
= Inserted tx []
addMany !m !kx tx zs0@((ky,vy) : zs)
| mask kx m /= mask ky m
= Inserted tx zs0
| Inserted ty zs' <- addMany' (branchMask kx ky) ky vy zs
= addMany m kx (link ky ty kx tx) zs'
fromDistinctAscList1c :: [(Key,a)] -> IntMap a
fromDistinctAscList1c [] = Nil
fromDistinctAscList1c ((kx,vx) : zs1) = inline addAll kx (Tip kx vx) zs1
where
-- invariant for `addAll` and `addMany`: `kx` is a key in the map `tx`.
addAll !kx !tx []
= tx
addAll !kx !tx ((ky,vy) : zs)
| m <- branchMask kx ky
, Inserted ty zs' <- addMany m ky (Tip ky vy) zs
= addAll kx (link ky ty kx tx) zs'
-- addMany adds all elements that have the same prefix as `kx` w.r.t.
-- the branch mask `m` to `tx`.
addMany !m !kx tx []
= Inserted tx []
addMany !m !kx tx zs0@((ky,vy) : zs)
| mask kx m /= mask ky m
= Inserted tx zs0
| Inserted ty zs' <- addMany (branchMask kx ky) ky (Tip ky vy) zs
= addMany m kx (link ky ty kx tx) zs'
fromDistinctAscList1d :: [(Key,a)] -> IntMap a
fromDistinctAscList1d [] = Nil
fromDistinctAscList1d ((kx,vx) : zs1) = inline addAll kx (Tip kx vx) zs1
where
-- invariant for `addAll` and `addMany`: `kx` is a key in the map `tx`.
addAll !kx !tx []
= tx
addAll !kx !tx ((ky,vy) : zs)
| m <- branchMask kx ky
, Inserted ty zs' <- inline addMany m ky (Tip ky vy) zs
= addAll kx (link ky ty kx tx) zs'
-- addMany adds all elements that have the same prefix as `kx` w.r.t.
-- the branch mask `m` to `tx`.
addMany !m !kx tx []
= Inserted tx []
addMany !m !kx tx zs0@((ky,vy) : zs)
| mask kx m /= mask ky m
= Inserted tx zs0
| Inserted ty zs' <- addMany (branchMask kx ky) ky (Tip ky vy) zs
= addMany m kx (link ky ty kx tx) zs'
fromDistinctAscList1e :: [(Key,a)] -> IntMap a
fromDistinctAscList1e [] = Nil
fromDistinctAscList1e ((kx,vx) : zs1) = addAll' kx vx zs1
where
addAll' !kx vx [] = Tip kx vx
addAll' !kx vx ((ky,vy) : zs)
| m <- branchMask kx ky
, Inserted ty zs' <- addMany' m ky vy zs
= addAll kx (link ky ty kx (Tip kx vx)) zs'
-- invariant for `addAll` and `addMany`: `kx` is a key in the map `tx`.
addAll !kx !tx []
= tx
addAll !kx !tx ((ky,vy) : zs)
| m <- branchMask kx ky
, Inserted ty zs' <- addMany' m ky vy zs
= addAll kx (link ky ty kx tx) zs'
addMany' !m !kx vx [] = Inserted (Tip kx vx) []
addMany' !m !kx vx zs0@((ky,vy) : zs)
| mask kx m /= mask ky m
= Inserted (Tip kx vx) zs0
| Inserted ty zs' <- addMany' (branchMask kx ky) ky vy zs
= addMany m kx (link ky ty kx (Tip kx vx)) zs'
-- addMany adds all elements that have the same prefix as `kx` w.r.t.
-- the branch mask `m` to `tx`.
addMany !m !kx tx []
= Inserted tx []
addMany !m !kx tx zs0@((ky,vy) : zs)
| mask kx m /= mask ky m
= Inserted tx zs0
| Inserted ty zs' <- addMany' (branchMask kx ky) ky vy zs
= addMany m kx (link ky ty kx tx) zs'
fromAscList1 :: [(Key,a)] -> IntMap a
fromAscList1 [] = Nil
fromAscList1 ((kx,vx) : zs0) = addAll' kx vx zs0
where
addAll' !kx vx [] = Tip kx vx
addAll' !kx vx ((ky,vy) : zs)
| kx == ky = addAll' ky vy zs
| otherwise = addAll kx (Tip kx vx) ((ky,vy) : zs)
-- invariant for `addAll` and `addMany`: `kx` is a key in the map `tx`.
addAll !kx !tx []
= tx
addAll !kx !tx ((ky,vy) : zs)
| m <- branchMask kx ky
, Inserted ty zs' <- addMany' m ky vy zs
= addAll kx (link ky ty kx tx) zs'
addMany' !m !kx vx [] = Inserted (Tip kx vx) []
addMany' !m !kx vx ((ky,vy) : zs)
| kx == ky = addMany' m ky vy zs
| otherwise = addMany m kx (Tip kx vx) ((ky,vy) : zs)
-- addMany adds all elements that have the same prefix as `kx` w.r.t.
-- the branch mask `m` to `tx`.
addMany !m !kx tx []
= Inserted tx []
addMany !m !kx tx zs0@((ky,vy) : zs)
| mask kx m /= mask ky m
= Inserted tx zs0
| Inserted ty zs' <- addMany' (branchMask kx ky) ky vy zs
= addMany m kx (link ky ty kx tx) zs'
fromAscList1a :: [(Key,a)] -> IntMap a
fromAscList1a [] = Nil
fromAscList1a ((kx,vx) : zs1) = addAll' kx vx zs1
where
-- `addAll'` collects all keys equal to `kx` into a single value,
-- and then proceeds with `addAll`.
addAll' !kx vx [] = Tip kx vx
addAll' !kx vx ((ky,vy) : zs)
| kx == ky
= addAll' ky vy zs
| m <- branchMask kx ky
, Inserted ty zs' <- addMany' m ky vy zs
= addAll kx (link ky ty kx (Tip kx vx)) zs'
-- for `addAll` and `addMany`, kx is /a/ key inside the tree `tx`
-- `addAll` consumes the rest of the list, adding to the tree `tx`
addAll !kx !tx []
= tx
addAll !kx !tx ((ky,vy) : zs)
| m <- branchMask kx ky
, Inserted ty zs' <- addMany' m ky vy zs
= addAll kx (link ky ty kx tx) zs'
-- `addMany'` is similar to `addAll'`, but proceeds with `addMany'`.
addMany' !m !kx vx [] = Inserted (Tip kx vx) []
addMany' !m !kx vx zs0@((ky,vy) : zs)
| kx == ky
= addMany' m ky vy zs
| mask kx m /= mask ky m
= Inserted (Tip kx vx) zs0
| Inserted ty zs' <- addMany' (branchMask kx ky) ky vy zs
= addMany m kx (link ky ty kx (Tip kx vx)) zs'
-- `addAll` adds to `tx` all keys whose prefix w.r.t. `m` agrees with `kx`.
addMany !m !kx tx []
= Inserted tx []
addMany !m !kx tx zs0@((ky,vy) : zs)
| mask kx m /= mask ky m
= Inserted tx zs0
| Inserted ty zs' <- addMany' (branchMask kx ky) ky vy zs
= addMany m kx (link ky ty kx tx) zs'
fromAscList1b :: [(Key,a)] -> IntMap a
fromAscList1b [] = Nil
fromAscList1b ((kx,vx) : zs0) = addAll' kx vx zs0
where
addAll' !kx vx [] = Tip kx vx
addAll' !kx vx ((ky,vy) : zs)
| kx == ky = addAll' ky vy zs
| otherwise = inline addAll kx (Tip kx vx) ((ky,vy) : zs)
-- invariant for `addAll` and `addMany`: `kx` is a key in the map `tx`.
addAll !kx !tx []
= tx
addAll !kx !tx ((ky,vy) : zs)
| m <- branchMask kx ky
, Inserted ty zs' <- addMany' m ky vy zs
= addAll kx (link ky ty kx tx) zs'
addMany' !m !kx vx [] = Inserted (Tip kx vx) []
addMany' !m !kx vx ((ky,vy) : zs)
| kx == ky = addMany' m ky vy zs
| otherwise = inline addMany m kx (Tip kx vx) ((ky,vy) : zs)
-- addMany adds all elements that have the same prefix as `kx` w.r.t.
-- the branch mask `m` to `tx`.
addMany !m !kx tx []
= Inserted tx []
addMany !m !kx tx zs0@((ky,vy) : zs)
| mask kx m /= mask ky m
= Inserted tx zs0
| Inserted ty zs' <- addMany' (branchMask kx ky) ky vy zs
= addMany m kx (link ky ty kx tx) zs'
fromAscList1c :: [(Key,a)] -> IntMap a
fromAscList1c [] = Nil
fromAscList1c ((kx,vx) : zs1) = addAll' kx vx zs1
where
addAll' !kx vx [] = Tip kx vx
addAll' !kx vx ((ky,vy) : zs)
| kx == ky
= addAll' ky vy zs
| m <- branchMask kx ky
, Inserted ty zs' <- addMany' m ky vy zs
= addAll kx (link ky ty kx (Tip kx vx)) zs'
-- invariant for `addAll` and `addMany`: `kx` is a key in the map `tx`.
addAll !kx tx []
= tx
addAll !kx tx ((ky,vy) : zs)
| m <- branchMask kx ky
, Inserted ty zs' <- addMany' m ky vy zs
= addAll kx (link ky ty kx tx) zs'
addMany' !m !kx vx [] = Inserted (Tip kx vx) []
addMany' !m !kx vx zs0@((ky,vy) : zs)
| kx == ky
= addMany' m ky vy zs
| mask kx m /= mask ky m
= Inserted (Tip kx vx) zs0
| Inserted ty zs' <- addMany' (branchMask kx ky) ky vy zs
= addMany m kx (link ky ty kx (Tip kx vx)) zs'
-- addMany adds all elements that have the same prefix as `kx` w.r.t.
-- the branch mask `m` to `tx`.
addMany !m !kx tx []
= Inserted tx []
addMany !m !kx tx zs0@((ky,vy) : zs)
| mask kx m /= mask ky m
= Inserted tx zs0
| Inserted ty zs' <- addMany' (branchMask kx ky) ky vy zs
= addMany m kx (link ky ty kx tx) zs'
------------------------------------------------------------------------------
-- fromList implementation from #653
------------------------------------------------------------------------------
fromList1 :: [(Key,a)] -> IntMap a
fromList1 = insertAll Nil
{-# NOINLINE fromList1 #-}
-- [Note: fromList]
--
-- The obvious way to build a map from a list is just to fold over the list
-- inserting each entry into the accumulator map. The problem is that this
-- rebuilds the path from the root *every single time*. To avoid this, we
-- insert as many elements as we can into the current subtree, backing out
-- one level at a time when necessary.
insertAll :: IntMap a -> [(Key, a)] -> IntMap a
insertAll m [] = m
insertAll m ((k,x) : kxs)
| Inserted m' r <- insertSome m k x kxs
= insertAll m' r
-- | Insert at least one entry into an 'IntMap' or subtree. If
-- others fit in the same resulting subtree, insert them too.
-- Return the new map and remaining values.
insertSome :: IntMap a -> Key -> a -> [(Key, a)] -> Inserted a
insertSome t@(Bin p m l r) !k x kxs
| nomatch k p m
= insertMany (link k (Tip k x) p t) kxs
| zero k m
, Inserted l' kxs' <- insertSome l k x kxs
= insertMany (Bin p m l' r) kxs'
| Inserted r' kxs' <- insertSome r k x kxs
= insertMany (Bin p m l r') kxs'
insertSome t@(Tip ky _) k x kxs
| k == ky
= insertMany (Tip k x) kxs
| otherwise
= insertMany (link k (Tip k x) ky t) kxs
insertSome Nil k x kxs = insertMany (Tip k x) kxs
-- | Try to insert some entries into a subtree of an 'IntMap'. If
-- they belong in some other subtree, just don't insert them.
insertMany :: IntMap a -> [(Key, a)] -> Inserted a
insertMany t [] = Inserted t []
insertMany t@(Bin p m _ _) kxs@((k, x) : kxs')
| nomatch k p m
= Inserted t kxs
| otherwise
= insertSome t k x kxs'
insertMany t@(Tip ky _) kxs@((k, x) : kxs')
| k==ky = insertSome t k x kxs'
| otherwise = Inserted t kxs
insertMany Nil kxs = Inserted Nil kxs -- Unused case
Raw
IntMapFAL.out
[1,1]/fromList mean 19.96 ns ( +- 100.6 ps )
[1,1]/fromList1 mean 24.57 ns ( +- 219.6 ps )
[1,1]/fromAscList mean 35.77 ns ( +- 315.4 ps )
[1,1]/fromAscList1 mean 22.37 ns ( +- 280.0 ps )
[1,1]/fromAscList1a mean 21.24 ns ( +- 1.071 ns )
[1,1]/fromAscList1b mean 19.75 ns ( +- 94.72 ps )
[1,1]/fromDistinctAscList mean 26.66 ns ( +- 111.2 ps )
[1,1]/fromDistinctAscList1 mean 20.45 ns ( +- 45.62 ps )
[1,1]/fromDistinctAscList1a mean 20.40 ns ( +- 168.2 ps )
[1,1]/fromDistinctAscList1b mean 17.31 ns ( +- 285.6 ps )
[1,1]/fromDistinctAscList1c mean 19.30 ns ( +- 1.484 ns )
[1,1]/fromDistinctAscList1d mean 17.29 ns ( +- 254.2 ps )
[1,1]/fromDistinctAscList1e mean 18.95 ns ( +- 723.2 ps )
[10,1]/fromList mean 133.3 ns ( +- 2.753 ns )
[10,1]/fromList1 mean 194.7 ns ( +- 1.733 ns )
[10,1]/fromAscList mean 291.8 ns ( +- 2.959 ns )
[10,1]/fromAscList1 mean 176.3 ns ( +- 1.817 ns )
[10,1]/fromAscList1a mean 142.4 ns ( +- 1.102 ns )
[10,1]/fromAscList1b mean 133.4 ns ( +- 738.2 ps )
[10,1]/fromDistinctAscList mean 183.1 ns ( +- 2.872 ns )
[10,1]/fromDistinctAscList1 mean 142.4 ns ( +- 520.0 ps )
[10,1]/fromDistinctAscList1a mean 144.9 ns ( +- 1.275 ns )
[10,1]/fromDistinctAscList1b mean 163.1 ns ( +- 2.865 ns )
[10,1]/fromDistinctAscList1c mean 142.6 ns ( +- 2.104 ns )
[10,1]/fromDistinctAscList1d mean 140.1 ns ( +- 1.599 ns )
[10,1]/fromDistinctAscList1e mean 138.1 ns ( +- 2.319 ns )
[-10,51791]/fromList mean 156.1 ns ( +- 3.261 ns )
[-10,51791]/fromList1 mean 206.4 ns ( +- 2.760 ns )
[-10,51791]/fromAscList mean 312.7 ns ( +- 1.505 ns )
[-10,51791]/fromAscList1 mean 192.2 ns ( +- 1.122 ns )
[-10,51791]/fromAscList1a mean 156.8 ns ( +- 971.6 ps )
[-10,51791]/fromAscList1b mean 149.6 ns ( +- 3.354 ns )
[-10,51791]/fromDistinctAscList mean 200.9 ns ( +- 2.823 ns )
[-10,51791]/fromDistinctAscList1 mean 158.2 ns ( +- 1.828 ns )
[-10,51791]/fromDistinctAscList1a mean 158.3 ns ( +- 4.138 ns )
[-10,51791]/fromDistinctAscList1b mean 175.4 ns ( +- 683.2 ps )
[-10,51791]/fromDistinctAscList1c mean 155.6 ns ( +- 844.6 ps )
[-10,51791]/fromDistinctAscList1d mean 153.6 ns ( +- 1.646 ns )
[-10,51791]/fromDistinctAscList1e mean 150.6 ns ( +- 1.408 ns )
[100,1]/fromList mean 2.083 μs ( +- 22.39 ns )
[100,1]/fromList1 mean 1.918 μs ( +- 14.94 ns )
[100,1]/fromAscList mean 3.053 μs ( +- 65.91 ns )
[100,1]/fromAscList1 mean 1.778 μs ( +- 22.50 ns )
[100,1]/fromAscList1a mean 1.473 μs ( +- 9.788 ns )
[100,1]/fromAscList1b mean 1.421 μs ( +- 12.13 ns )
[100,1]/fromDistinctAscList mean 1.941 μs ( +- 65.06 ns )
[100,1]/fromDistinctAscList1 mean 1.619 μs ( +- 59.30 ns )
[100,1]/fromDistinctAscList1a mean 1.576 μs ( +- 29.12 ns )
[100,1]/fromDistinctAscList1b mean 1.646 μs ( +- 14.79 ns )
[100,1]/fromDistinctAscList1c mean 1.578 μs ( +- 29.25 ns )
[100,1]/fromDistinctAscList1d mean 1.573 μs ( +- 64.65 ns )
[100,1]/fromDistinctAscList1e mean 1.487 μs ( +- 82.64 ns )
[-100,51791]/fromList mean 2.335 μs ( +- 71.67 ns )
[-100,51791]/fromList1 mean 1.962 μs ( +- 22.17 ns )
[-100,51791]/fromAscList mean 3.104 μs ( +- 52.80 ns )
[-100,51791]/fromAscList1 mean 1.815 μs ( +- 17.61 ns )
[-100,51791]/fromAscList1a mean 1.466 μs ( +- 18.02 ns )
[-100,51791]/fromAscList1b mean 1.420 μs ( +- 34.63 ns )
[-100,51791]/fromDistinctAscList mean 1.981 μs ( +- 101.2 ns )
[-100,51791]/fromDistinctAscList1 mean 1.586 μs ( +- 27.46 ns )
[-100,51791]/fromDistinctAscList1a mean 1.541 μs ( +- 50.34 ns )
[-100,51791]/fromDistinctAscList1b mean 1.750 μs ( +- 56.57 ns )
[-100,51791]/fromDistinctAscList1c mean 1.567 μs ( +- 41.05 ns )
[-100,51791]/fromDistinctAscList1d mean 1.583 μs ( +- 33.34 ns )
[-100,51791]/fromDistinctAscList1e mean 1.476 μs ( +- 29.09 ns )
[1000,1]/fromList mean 36.25 μs ( +- 385.5 ns )
[1000,1]/fromList1 mean 20.66 μs ( +- 113.3 ns )
[1000,1]/fromAscList mean 32.09 μs ( +- 613.1 ns )
[1000,1]/fromAscList1 mean 19.23 μs ( +- 80.08 ns )
[1000,1]/fromAscList1a mean 15.52 μs ( +- 120.4 ns )
[1000,1]/fromAscList1b mean 15.09 μs ( +- 136.9 ns )
[1000,1]/fromDistinctAscList mean 20.14 μs ( +- 437.3 ns )
[1000,1]/fromDistinctAscList1 mean 16.99 μs ( +- 290.3 ns )
[1000,1]/fromDistinctAscList1a mean 16.39 μs ( +- 399.2 ns )
[1000,1]/fromDistinctAscList1b mean 17.77 μs ( +- 94.49 ns )
[1000,1]/fromDistinctAscList1c mean 17.08 μs ( +- 439.6 ns )
[1000,1]/fromDistinctAscList1d mean 16.76 μs ( +- 416.7 ns )
[1000,1]/fromDistinctAscList1e mean 15.54 μs ( +- 132.2 ns )
[-1000,51791]/fromList mean 40.32 μs ( +- 328.1 ns )
[-1000,51791]/fromList1 mean 22.05 μs ( +- 1.069 μs )
[-1000,51791]/fromAscList mean 36.16 μs ( +- 1.129 μs )
[-1000,51791]/fromAscList1 mean 20.62 μs ( +- 842.4 ns )
[-1000,51791]/fromAscList1a mean 15.93 μs ( +- 214.1 ns )
[-1000,51791]/fromAscList1b mean 15.89 μs ( +- 569.9 ns )
[-1000,51791]/fromDistinctAscList mean 20.50 μs ( +- 700.0 ns )
[-1000,51791]/fromDistinctAscList1 mean 17.01 μs ( +- 244.6 ns )
[-1000,51791]/fromDistinctAscList1a mean 18.11 μs ( +- 443.8 ns )
[-1000,51791]/fromDistinctAscList1b mean 18.93 μs ( +- 474.6 ns )
[-1000,51791]/fromDistinctAscList1c mean 17.30 μs ( +- 294.2 ns )
[-1000,51791]/fromDistinctAscList1d mean 17.32 μs ( +- 402.4 ns )
[-1000,51791]/fromDistinctAscList1e mean 15.84 μs ( +- 179.2 ns )
[10000,1]/fromList mean 1.158 ms ( +- 8.190 μs )
[10000,1]/fromList1 mean 304.6 μs ( +- 1.047 μs )
[10000,1]/fromAscList mean 992.0 μs ( +- 14.90 μs )
[10000,1]/fromAscList1 mean 304.3 μs ( +- 1.570 μs )
[10000,1]/fromAscList1a mean 227.9 μs ( +- 1.016 μs )
[10000,1]/fromAscList1b mean 222.6 μs ( +- 728.8 ns )
[10000,1]/fromDistinctAscList mean 309.0 μs ( +- 3.195 μs )
[10000,1]/fromDistinctAscList1 mean 243.4 μs ( +- 4.675 μs )
[10000,1]/fromDistinctAscList1a mean 232.0 μs ( +- 2.451 μs )
[10000,1]/fromDistinctAscList1b mean 281.1 μs ( +- 1.136 μs )
[10000,1]/fromDistinctAscList1c mean 240.2 μs ( +- 2.666 μs )
[10000,1]/fromDistinctAscList1d mean 240.6 μs ( +- 3.909 μs )
[10000,1]/fromDistinctAscList1e mean 228.1 μs ( +- 895.6 ns )
[-10000,51791]/fromList mean 1.223 ms ( +- 13.76 μs )
[-10000,51791]/fromList1 mean 315.9 μs ( +- 1.681 μs )
[-10000,51791]/fromAscList mean 1.078 ms ( +- 11.78 μs )
[-10000,51791]/fromAscList1 mean 322.5 μs ( +- 3.483 μs )
[-10000,51791]/fromAscList1a mean 237.2 μs ( +- 2.126 μs )
[-10000,51791]/fromAscList1b mean 232.5 μs ( +- 1.459 μs )
[-10000,51791]/fromDistinctAscList mean 318.7 μs ( +- 5.809 μs )
[-10000,51791]/fromDistinctAscList1 mean 249.5 μs ( +- 2.985 μs )
[-10000,51791]/fromDistinctAscList1a mean 250.0 μs ( +- 4.007 μs )
[-10000,51791]/fromDistinctAscList1b mean 294.4 μs ( +- 4.271 μs )
[-10000,51791]/fromDistinctAscList1c mean 248.1 μs ( +- 2.012 μs )
[-10000,51791]/fromDistinctAscList1d mean 250.2 μs ( +- 3.705 μs )
[-10000,51791]/fromDistinctAscList1e mean 236.6 μs ( +- 1.945 μs )
[100000,1]/fromList mean 13.96 ms ( +- 495.0 μs )
[100000,1]/fromList1 mean 9.904 ms ( +- 291.2 μs )
[100000,1]/fromAscList mean 11.36 ms ( +- 346.5 μs )
[100000,1]/fromAscList1 mean 9.770 ms ( +- 275.3 μs )
[100000,1]/fromAscList1a mean 8.968 ms ( +- 381.8 μs )
[100000,1]/fromAscList1b mean 8.962 ms ( +- 336.9 μs )
[100000,1]/fromDistinctAscList mean 10.06 ms ( +- 333.7 μs )
[100000,1]/fromDistinctAscList1 mean 9.171 ms ( +- 303.1 μs )
[100000,1]/fromDistinctAscList1a mean 9.095 ms ( +- 313.4 μs )
[100000,1]/fromDistinctAscList1b mean 9.428 ms ( +- 260.0 μs )
[100000,1]/fromDistinctAscList1c mean 9.054 ms ( +- 313.7 μs )
[100000,1]/fromDistinctAscList1d mean 9.077 ms ( +- 355.6 μs )
[100000,1]/fromDistinctAscList1e mean 8.925 ms ( +- 309.6 μs )
[-100000,51791]/fromList mean 14.38 ms ( +- 327.7 μs )
[-100000,51791]/fromList1 mean 10.31 ms ( +- 286.1 μs )
[-100000,51791]/fromAscList mean 11.81 ms ( +- 405.3 μs )
[-100000,51791]/fromAscList1 mean 10.10 ms ( +- 257.6 μs )
[-100000,51791]/fromAscList1a mean 9.255 ms ( +- 423.9 μs )
[-100000,51791]/fromAscList1b mean 9.262 ms ( +- 357.7 μs )
[-100000,51791]/fromDistinctAscList mean 10.38 ms ( +- 367.5 μs )
[-100000,51791]/fromDistinctAscList1 mean 9.430 ms ( +- 399.9 μs )
[-100000,51791]/fromDistinctAscList1a mean 9.391 ms ( +- 287.0 μs )
[-100000,51791]/fromDistinctAscList1b mean 9.943 ms ( +- 262.4 μs )
[-100000,51791]/fromDistinctAscList1c mean 9.287 ms ( +- 284.9 μs )
[-100000,51791]/fromDistinctAscList1d mean 9.389 ms ( +- 427.9 μs )
[-100000,51791]/fromDistinctAscList1e mean 9.155 ms ( +- 422.2 μs )
[1000000,1]/fromList mean 148.9 ms ( +- 13.02 ms )
[1000000,1]/fromList1 mean 98.69 ms ( +- 10.50 ms )
[1000000,1]/fromAscList mean 94.35 ms ( +- 10.49 ms )
[1000000,1]/fromAscList1 mean 97.91 ms ( +- 10.52 ms )
[1000000,1]/fromAscList1a mean 93.71 ms ( +- 10.71 ms )
[1000000,1]/fromAscList1b mean 93.41 ms ( +- 10.64 ms )
[1000000,1]/fromDistinctAscList mean 94.29 ms ( +- 10.61 ms )
[1000000,1]/fromDistinctAscList1 mean 96.53 ms ( +- 11.47 ms )
[1000000,1]/fromDistinctAscList1a mean 94.76 ms ( +- 10.52 ms )
[1000000,1]/fromDistinctAscList1b mean 96.40 ms ( +- 10.40 ms )
[1000000,1]/fromDistinctAscList1c mean 95.03 ms ( +- 10.70 ms )
[1000000,1]/fromDistinctAscList1d mean 94.99 ms ( +- 10.64 ms )
[1000000,1]/fromDistinctAscList1e mean 94.07 ms ( +- 10.87 ms )
[-1000000,51791]/fromList mean 158.9 ms ( +- 12.51 ms )
[-1000000,51791]/fromList1 mean 103.8 ms ( +- 10.96 ms )
[-1000000,51791]/fromAscList mean 99.59 ms ( +- 10.95 ms )
[-1000000,51791]/fromAscList1 mean 103.4 ms ( +- 11.06 ms )
[-1000000,51791]/fromAscList1a mean 98.45 ms ( +- 11.05 ms )
[-1000000,51791]/fromAscList1b mean 97.53 ms ( +- 10.91 ms )
[-1000000,51791]/fromDistinctAscList mean 99.68 ms ( +- 11.29 ms )
[-1000000,51791]/fromDistinctAscList1 mean 100.5 ms ( +- 10.50 ms )
[-1000000,51791]/fromDistinctAscList1a mean 100.9 ms ( +- 11.21 ms )
[-1000000,51791]/fromDistinctAscList1b mean 101.2 ms ( +- 10.74 ms )
[-1000000,51791]/fromDistinctAscList1c mean 100.1 ms ( +- 11.36 ms )
[-1000000,51791]/fromDistinctAscList1d mean 100.2 ms ( +- 11.06 ms )
[-1000000,51791]/fromDistinctAscList1e mean 99.57 ms ( +- 11.21 ms )
[10000000,1]/fromList mean 1.538 s ( +- 120.9 ms )
[10000000,1]/fromList1 mean 991.5 ms ( +- 103.6 ms )
[10000000,1]/fromAscList mean 940.9 ms ( +- 105.3 ms )
[10000000,1]/fromAscList1 mean 980.4 ms ( +- 102.8 ms )
[10000000,1]/fromAscList1a mean 942.8 ms ( +- 106.6 ms )
[10000000,1]/fromAscList1b mean 941.4 ms ( +- 107.2 ms )
[10000000,1]/fromDistinctAscList mean 943.0 ms ( +- 104.2 ms )
[10000000,1]/fromDistinctAscList1 mean 950.0 ms ( +- 106.4 ms )
[10000000,1]/fromDistinctAscList1a mean 939.1 ms ( +- 103.8 ms )
[10000000,1]/fromDistinctAscList1b mean 982.2 ms ( +- 108.1 ms )
[10000000,1]/fromDistinctAscList1c mean 951.8 ms ( +- 107.7 ms )
[10000000,1]/fromDistinctAscList1d mean 954.7 ms ( +- 108.3 ms )
[10000000,1]/fromDistinctAscList1e mean 944.1 ms ( +- 102.5 ms )
[-10000000,51791]/fromList mean 1.657 s ( +- 112.6 ms )
[-10000000,51791]/fromList1 mean 1.029 s ( +- 101.1 ms )
[-10000000,51791]/fromAscList mean 968.8 ms ( +- 102.5 ms )
[-10000000,51791]/fromAscList1 mean 1.026 s ( +- 105.8 ms )
[-10000000,51791]/fromAscList1a mean 978.7 ms ( +- 100.6 ms )
[-10000000,51791]/fromAscList1b mean 985.3 ms ( +- 107.5 ms )
[-10000000,51791]/fromDistinctAscList mean 982.6 ms ( +- 106.5 ms )
[-10000000,51791]/fromDistinctAscList1 mean 990.6 ms ( +- 100.3 ms )
[-10000000,51791]/fromDistinctAscList1a mean 998.6 ms ( +- 106.8 ms )
[-10000000,51791]/fromDistinctAscList1b mean 1.004 s ( +- 100.8 ms )
[-10000000,51791]/fromDistinctAscList1c mean 976.9 ms ( +- 107.1 ms )
[-10000000,51791]/fromDistinctAscList1d mean 974.9 ms ( +- 103.2 ms )
[-10000000,51791]/fromDistinctAscList1e mean 967.1 ms ( +- 98.94 ms )
Raw
IntMapFAL2.hs
-- ghc -O2 -hide-package containers IntMapFAL2.hs && ./IntMapFAL2 --small | tee IntMapFAL2.out
{-# LANGUAGE BangPatterns #-}
{-# LANGUAGE RankNTypes #-}
import Control.DeepSeq (rnf)
import Control.Exception (evaluate)
import Gauge (bench, bgroup, env, defaultMain, whnf)
import Data.List (foldl')
import qualified Data.IntMap as M
import qualified Data.IntMap.Strict as MS
import Data.Maybe (fromMaybe)
import Prelude hiding (lookup)
import GHC.Exts (inline)
import Data.IntMap.Internal (IntMap (..), Prefix, Mask, Key, size, link, branchMask, mask, shorter, nomatch, zero)
import qualified Data.IntMap.Internal as I
main = do
defaultMain $ [test (s*sz) sk |
sz <- [10^i | i <- [0..5]],
(s, sk) <- if sz == 1 then [(1,1)] else [(1,1), (-1,51791)]]
test sz sk =
env (let m = M.fromAscList elems :: M.IntMap Int in evaluate $ rnf [m]) $ \m -> bgroup n
[ bench "fromList" $ whnf M.fromList elems
, bench "fromList1" $ whnf fromList1 elems
, bench "fromAscList" $ whnf M.fromAscList elems
, bench "fromAscList1a" $ whnf fromAscList1a elems
, bench "fromAscList1f" $ whnf fromAscList1f elems
, bench "fromDistinctAscList" $ whnf M.fromDistinctAscList elems
]
where
n = "[" ++ show sz ++ "," ++ show sk ++ "]"
elems = zip keys values
keys = map (sk*) (if sz < 0 then [2*sz `div` 3.. -sz `div` 3] else [0..sz])
values = [1..]
data Inserted a = Inserted !(IntMap a) ![(Key,a)]
fromAscList1a :: [(Key,a)] -> IntMap a
fromAscList1a [] = Nil
fromAscList1a ((kx,vx) : zs1) = addAll' kx vx zs1
where
-- `addAll'` collects all keys equal to `kx` into a single value,
-- and then proceeds with `addAll`.
addAll' !kx vx [] = Tip kx vx
addAll' !kx vx ((ky,vy) : zs)
| kx == ky
= addAll' ky vy zs
| m <- branchMask kx ky
, Inserted ty zs' <- addMany' m ky vy zs
= addAll kx (link ky ty kx (Tip kx vx)) zs'
-- for `addAll` and `addMany`, kx is /a/ key inside the tree `tx`
-- `addAll` consumes the rest of the list, adding to the tree `tx`
addAll !kx !tx []
= tx
addAll !kx !tx ((ky,vy) : zs)
| m <- branchMask kx ky
, Inserted ty zs' <- addMany' m ky vy zs
= addAll kx (link ky ty kx tx) zs'
-- `addMany'` is similar to `addAll'`, but proceeds with `addMany'`.
addMany' !m !kx vx [] = Inserted (Tip kx vx) []
addMany' !m !kx vx zs0@((ky,vy) : zs)
| kx == ky
= addMany' m ky vy zs
| mask kx m /= mask ky m
= Inserted (Tip kx vx) zs0
| Inserted ty zs' <- addMany' (branchMask kx ky) ky vy zs
= addMany m kx (link ky ty kx (Tip kx vx)) zs'
-- `addAll` adds to `tx` all keys whose prefix w.r.t. `m` agrees with `kx`.
addMany !m !kx tx []
= Inserted tx []
addMany !m !kx tx zs0@((ky,vy) : zs)
| mask kx m /= mask ky m
= Inserted tx zs0
| Inserted ty zs' <- addMany' (branchMask kx ky) ky vy zs
= addMany m kx (link ky ty kx tx) zs'
fromAscList1f :: [(Key,a)] -> IntMap a
fromAscList1f zs = fromAscListWithKey1 (\_ x _ -> x) zs
fromAscListWithKey1 :: (Key -> a -> a -> a) -> [(Key,a)] -> IntMap a
fromAscListWithKey1 f [] = Nil
fromAscListWithKey1 f ((kx,vx) : zs1) = addAll' kx vx zs1
where
-- `addAll'` collects all keys equal to `kx` into a single value,
-- and then proceeds with `addAll`.
addAll' !kx vx [] = Tip kx vx
addAll' !kx vx ((ky,vy) : zs)
| kx == ky
= let v = f kx vy vx in addAll' ky v zs
-- inlined: | otherwise = addAll kx (Tip kx vx) (ky : zs)
| m <- branchMask kx ky
, Inserted ty zs' <- addMany' m ky vy zs
= addAll kx (link ky ty kx (Tip kx vx)) zs'
-- for `addAll` and `addMany`, kx is /a/ key inside the tree `tx`
-- `addAll` consumes the rest of the list, adding to the tree `tx`
addAll !kx !tx []
= tx
addAll !kx !tx ((ky,vy) : zs)
| m <- branchMask kx ky
, Inserted ty zs' <- addMany' m ky vy zs
= addAll kx (link ky ty kx tx) zs'
-- `addMany'` is similar to `addAll'`, but proceeds with `addMany'`.
addMany' !m !kx vx [] = Inserted (Tip kx vx) []
addMany' !m !kx vx zs0@((ky,vy) : zs)
| kx == ky
= let v = f kx vy vx in addMany' m ky v zs
-- inlined: | otherwise = addMany m kx (Tip kx vx) (ky : zs)
| mask kx m /= mask ky m
= Inserted (Tip kx vx) zs0
| Inserted ty zs' <- addMany' (branchMask kx ky) ky vy zs
= addMany m kx (link ky ty kx (Tip kx vx)) zs'
-- `addAll` adds to `tx` all keys whose prefix w.r.t. `m` agrees with `kx`.
addMany !m !kx tx []
= Inserted tx []
addMany !m !kx tx zs0@((ky,vy) : zs)
| mask kx m /= mask ky m
= Inserted tx zs0
| Inserted ty zs' <- addMany' (branchMask kx ky) ky vy zs
= addMany m kx (link ky ty kx tx) zs'
------------------------------------------------------------------------------
-- fromList implementation from #653
------------------------------------------------------------------------------
fromList1 :: [(Key,a)] -> IntMap a
fromList1 = insertAll Nil
{-# NOINLINE fromList1 #-}
-- [Note: fromList]
--
-- The obvious way to build a map from a list is just to fold over the list
-- inserting each entry into the accumulator map. The problem is that this
-- rebuilds the path from the root *every single time*. To avoid this, we
-- insert as many elements as we can into the current subtree, backing out
-- one level at a time when necessary.
insertAll :: IntMap a -> [(Key, a)] -> IntMap a
insertAll m [] = m
insertAll m ((k,x) : kxs)
| Inserted m' r <- insertSome m k x kxs
= insertAll m' r
-- | Insert at least one entry into an 'IntMap' or subtree. If
-- others fit in the same resulting subtree, insert them too.
-- Return the new map and remaining values.
insertSome :: IntMap a -> Key -> a -> [(Key, a)] -> Inserted a
insertSome t@(Bin p m l r) !k x kxs
| nomatch k p m
= insertMany (link k (Tip k x) p t) kxs
| zero k m
, Inserted l' kxs' <- insertSome l k x kxs
= insertMany (Bin p m l' r) kxs'
| Inserted r' kxs' <- insertSome r k x kxs
= insertMany (Bin p m l r') kxs'
insertSome t@(Tip ky _) k x kxs
| k == ky
= insertMany (Tip k x) kxs
| otherwise
= insertMany (link k (Tip k x) ky t) kxs
insertSome Nil k x kxs = insertMany (Tip k x) kxs
-- | Try to insert some entries into a subtree of an 'IntMap'. If
-- they belong in some other subtree, just don't insert them.
insertMany :: IntMap a -> [(Key, a)] -> Inserted a
insertMany t [] = Inserted t []
insertMany t@(Bin p m _ _) kxs@((k, x) : kxs')
| nomatch k p m
= Inserted t kxs
| otherwise
= insertSome t k x kxs'
insertMany t@(Tip ky _) kxs@((k, x) : kxs')
| k==ky = insertSome t k x kxs'
| otherwise = Inserted t kxs
insertMany Nil kxs = Inserted Nil kxs -- Unused case
Raw
IntMapFAL2.out
[1,1]/fromList mean 19.81 ns ( +- 79.53 ps )
[1,1]/fromList1 mean 24.50 ns ( +- 44.19 ps )
[1,1]/fromAscList mean 35.53 ns ( +- 65.03 ps )
[1,1]/fromAscList1a mean 20.21 ns ( +- 31.45 ps )
[1,1]/fromAscList1f mean 19.74 ns ( +- 61.62 ps )
[1,1]/fromDistinctAscList mean 26.73 ns ( +- 60.06 ps )
[10,1]/fromList mean 151.0 ns ( +- 2.284 ns )
[10,1]/fromList1 mean 197.1 ns ( +- 754.5 ps )
[10,1]/fromAscList mean 284.7 ns ( +- 1.716 ns )
[10,1]/fromAscList1a mean 153.1 ns ( +- 779.4 ps )
[10,1]/fromAscList1f mean 147.9 ns ( +- 1.607 ns )
[10,1]/fromDistinctAscList mean 184.9 ns ( +- 2.055 ns )
[-10,51791]/fromList mean 185.2 ns ( +- 6.556 ns )
[-10,51791]/fromList1 mean 207.6 ns ( +- 3.434 ns )
[-10,51791]/fromAscList mean 317.8 ns ( +- 3.396 ns )
[-10,51791]/fromAscList1a mean 166.4 ns ( +- 801.6 ps )
[-10,51791]/fromAscList1f mean 161.7 ns ( +- 1.476 ns )
[-10,51791]/fromDistinctAscList mean 207.2 ns ( +- 1.427 ns )
[100,1]/fromList mean 2.622 μs ( +- 51.23 ns )
[100,1]/fromList1 mean 2.021 μs ( +- 10.33 ns )
[100,1]/fromAscList mean 3.132 μs ( +- 19.76 ns )
[100,1]/fromAscList1a mean 1.665 μs ( +- 12.78 ns )
[100,1]/fromAscList1f mean 1.603 μs ( +- 16.14 ns )
[100,1]/fromDistinctAscList mean 2.004 μs ( +- 33.81 ns )
[-100,51791]/fromList mean 2.830 μs ( +- 193.3 ns )
[-100,51791]/fromList1 mean 2.086 μs ( +- 39.03 ns )
[-100,51791]/fromAscList mean 3.229 μs ( +- 30.41 ns )
[-100,51791]/fromAscList1a mean 1.752 μs ( +- 44.35 ns )
[-100,51791]/fromAscList1f mean 1.668 μs ( +- 62.23 ns )
[-100,51791]/fromDistinctAscList mean 2.151 μs ( +- 51.08 ns )
[1000,1]/fromList mean 40.05 μs ( +- 460.3 ns )
[1000,1]/fromList1 mean 21.39 μs ( +- 118.4 ns )
[1000,1]/fromAscList mean 33.30 μs ( +- 635.6 ns )
[1000,1]/fromAscList1a mean 17.37 μs ( +- 146.1 ns )
[1000,1]/fromAscList1f mean 16.45 μs ( +- 248.8 ns )
[1000,1]/fromDistinctAscList mean 21.44 μs ( +- 312.5 ns )
[-1000,51791]/fromList mean 43.78 μs ( +- 473.5 ns )
[-1000,51791]/fromList1 mean 22.34 μs ( +- 262.5 ns )
[-1000,51791]/fromAscList mean 37.30 μs ( +- 815.6 ns )
[-1000,51791]/fromAscList1a mean 19.28 μs ( +- 316.4 ns )
[-1000,51791]/fromAscList1f mean 18.32 μs ( +- 344.4 ns )
[-1000,51791]/fromDistinctAscList mean 23.20 μs ( +- 578.7 ns )
[10000,1]/fromList mean 1.190 ms ( +- 8.678 μs )
[10000,1]/fromList1 mean 308.9 μs ( +- 1.481 μs )
[10000,1]/fromAscList mean 1.006 ms ( +- 13.58 μs )
[10000,1]/fromAscList1a mean 243.4 μs ( +- 1.976 μs )
[10000,1]/fromAscList1f mean 231.6 μs ( +- 1.649 μs )
[10000,1]/fromDistinctAscList mean 320.6 μs ( +- 3.896 μs )
[-10000,51791]/fromList mean 1.277 ms ( +- 13.42 μs )
[-10000,51791]/fromList1 mean 331.4 μs ( +- 3.339 μs )
[-10000,51791]/fromAscList mean 1.118 ms ( +- 14.94 μs )
[-10000,51791]/fromAscList1a mean 268.9 μs ( +- 4.440 μs )
[-10000,51791]/fromAscList1f mean 250.5 μs ( +- 7.029 μs )
[-10000,51791]/fromDistinctAscList mean 345.0 μs ( +- 8.581 μs )
[100000,1]/fromList mean 14.40 ms ( +- 456.1 μs )
[100000,1]/fromList1 mean 9.961 ms ( +- 287.0 μs )
[100000,1]/fromAscList mean 11.52 ms ( +- 358.0 μs )
[100000,1]/fromAscList1a mean 9.069 ms ( +- 239.0 μs )
[100000,1]/fromAscList1f mean 8.936 ms ( +- 367.9 μs )
[100000,1]/fromDistinctAscList mean 10.13 ms ( +- 349.4 μs )
[-100000,51791]/fromList mean 15.00 ms ( +- 433.6 μs )
[-100000,51791]/fromList1 mean 10.52 ms ( +- 321.1 μs )
[-100000,51791]/fromAscList mean 12.31 ms ( +- 353.9 μs )
[-100000,51791]/fromAscList1a mean 9.407 ms ( +- 317.4 μs )
[-100000,51791]/fromAscList1f mean 9.322 ms ( +- 335.8 μs )
[-100000,51791]/fromDistinctAscList mean 10.59 ms ( +- 379.3 μs )
Raw
IntMapFL.hs
-- ghc -O2 -hide-package containers IntMapFL.hs && ./IntMapFL --small | tee IntMapFL.out
{-# LANGUAGE BangPatterns #-}
{-# LANGUAGE RankNTypes #-}
import Control.DeepSeq (rnf)
import Control.Exception (evaluate)
import Gauge (bench, bgroup, env, defaultMain, whnf)
import Data.List (foldl')
import qualified Data.IntMap as M
import qualified Data.IntMap.Strict as MS
import Data.Maybe (fromMaybe)
import Prelude hiding (lookup)
import GHC.Exts (inline)
import Data.IntMap.Internal (IntMap (..), Prefix, Mask, Key, size, link, branchMask, mask, shorter, nomatch, zero)
import qualified Data.IntMap.Internal as I
main = do
defaultMain $
[test sz ls
| sz <- [10^i | i <- [0..6]],
ls <-
[map (sk*) (if sz < 0 then [2*sz `div` 3.. -sz `div` 3] else [0..sz])
| (s, sk) <- [(1,1), (-1,51791)]] ++
[[i+o | i <- [0..sz `div` 2], o <- [0, sz `div` 3]]]]
test sz keys =
env (let m = M.fromAscList elems :: M.IntMap Int in evaluate $ rnf [m]) $ \m -> bgroup n
[ bench "fromList" $ whnf M.fromList elems
, bench "fromList1" $ whnf fromList1 elems
, bench "fromList2" $ whnf fromList2 elems
, bench "fromList3" $ whnf fromList3 elems
]
where
n = "[" ++ show sz ++ "," ++ show (take 2 keys) ++ "]"
elems = zip keys values
values = [1..]
data Inserted a = Inserted !(IntMap a) ![(Key,a)]
------------------------------------------------------------------------------
-- fromList implementation from #653
------------------------------------------------------------------------------
{-# NOINLINE fromList1 #-}
fromList1 :: [(Key,a)] -> IntMap a
fromList1 = insertAll Nil
where
-- [Note: fromList]
--
-- The obvious way to build a map from a list is just to fold over the list
-- inserting each entry into the accumulator map. The problem is that this
-- rebuilds the path from the root *every single time*. To avoid this, we
-- insert as many elements as we can into the current subtree, backing out
-- one level at a time when necessary.
insertAll :: IntMap a -> [(Key, a)] -> IntMap a
insertAll m [] = m
insertAll m ((k,x) : kxs)
| Inserted m' r <- insertSome m k x kxs
= insertAll m' r
-- | Insert at least one entry into an 'IntMap' or subtree. If
-- others fit in the same resulting subtree, insert them too.
-- Return the new map and remaining values.
insertSome :: IntMap a -> Key -> a -> [(Key, a)] -> Inserted a
insertSome t@(Bin p m l r) !k x kxs
| nomatch k p m
= insertMany (link k (Tip k x) p t) kxs
| zero k m
, Inserted l' kxs' <- insertSome l k x kxs
= insertMany (Bin p m l' r) kxs'
| Inserted r' kxs' <- insertSome r k x kxs
= insertMany (Bin p m l r') kxs'
insertSome t@(Tip ky _) k x kxs
| k == ky
= insertMany (Tip k x) kxs
| otherwise
= insertMany (link k (Tip k x) ky t) kxs
insertSome Nil k x kxs = insertMany (Tip k x) kxs
-- | Try to insert some entries into a subtree of an 'IntMap'. If
-- they belong in some other subtree, just don't insert them.
insertMany :: IntMap a -> [(Key, a)] -> Inserted a
insertMany t [] = Inserted t []
insertMany t@(Bin p m _ _) kxs@((k, x) : kxs')
| nomatch k p m
= Inserted t kxs
| otherwise
= insertSome t k x kxs'
insertMany t@(Tip ky _) kxs@((k, x) : kxs')
| k==ky = insertSome t k x kxs'
| otherwise = Inserted t kxs
insertMany Nil kxs = Inserted Nil kxs -- Unused case
{-# NOINLINE fromList2 #-}
fromList2 :: [(Key,a)] -> IntMap a
fromList2 = insertAll Nil
where
-- [Note: fromList]
--
-- The obvious way to build a map from a list is just to fold over the list
-- inserting each entry into the accumulator map. The problem is that this
-- rebuilds the path from the root *every single time*. To avoid this, we
-- insert as many elements as we can into the current subtree, backing out
-- one level at a time when necessary.
insertAll :: IntMap a -> [(Key, a)] -> IntMap a
insertAll m [] = m
insertAll m ((k,x) : kxs)
= case insertSome m k x kxs of
InsertedNil m' -> insertAll m' []
InsertedCons m' k x kxs' -> insertAll m' ((k, x) : kxs')
-- | Insert at least one entry into an 'IntMap' or subtree. If
-- others fit in the same resulting subtree, insert them too.
-- Return the new map and remaining values.
insertSome :: IntMap a -> Key -> a -> [(Key, a)] -> Inserted' a
insertSome t@(Bin p m l r) !k x kxs
| nomatch k p m
= insertMany (link k (Tip k x) p t) kxs
| zero k m
= case insertSome l k x kxs of
InsertedNil l' -> insertMany (Bin p m l' r) []
InsertedCons l' k x kxs' -> insertMany (Bin p m l' r) ((k, x) : kxs')
| otherwise
= case insertSome r k x kxs of
InsertedNil r' -> insertMany (Bin p m l r') []
InsertedCons r' k x kxs' -> insertMany (Bin p m l r') ((k, x) : kxs')
insertSome t@(Tip ky _) k x kxs
| k == ky
= insertMany (Tip k x) kxs
| otherwise
= insertMany (link k (Tip k x) ky t) kxs
insertSome Nil k x kxs = insertMany (Tip k x) kxs
-- | Try to insert some entries into a subtree of an 'IntMap'. If
-- they belong in some other subtree, just don't insert them.
insertMany :: IntMap a -> [(Key, a)] -> Inserted' a
insertMany t [] = InsertedNil t
insertMany t@(Bin p m _ _) kxs@((k, x) : kxs')
| nomatch k p m
= InsertedCons t k x kxs'
| otherwise
= insertSome t k x kxs'
insertMany t@(Tip ky _) kxs@((k, x) : kxs')
| k==ky = insertSome t k x kxs'
| otherwise = InsertedCons t k x kxs'
insertMany Nil kxs = InsertedNil Nil -- Unused case
data Inserted' a
= InsertedNil !(IntMap a)
| InsertedCons !(IntMap a) !Key a ![(Key,a)]
{-# NOINLINE fromList3 #-}
-- fromList2 with some manual inlining... which has *no* effect on the
-- resulting runtime... (ghc is smart)
fromList3 :: [(Key,a)] -> IntMap a
fromList3 = insertAll Nil
where
insertAll :: IntMap a -> [(Key, a)] -> IntMap a
insertAll m [] = m
insertAll m ((k,x) : kxs)
= case insertSome m k x kxs of
InsertedNil m' -> m'
InsertedCons m' k x kxs' -> insertAll' m' k x kxs'
insertAll' m k x kxs
= case insertSome m k x kxs of
InsertedNil m' -> m'
InsertedCons m' k x kxs' -> insertAll' m' k x kxs'
insertSome :: IntMap a -> Key -> a -> [(Key, a)] -> Inserted' a
insertSome t@(Bin p m l r) !k x kxs
| nomatch k p m
= insertMany (link k (Tip k x) p t) kxs
| zero k m
= case insertSome l k x kxs of
InsertedNil l' -> InsertedNil (Bin p m l' r)
InsertedCons l' k x kxs' -> insertMany' (Bin p m l' r) k x kxs'
| otherwise
= case insertSome r k x kxs of
InsertedNil r' -> InsertedNil (Bin p m l r')
InsertedCons r' k x kxs' -> insertMany' (Bin p m l r') k x kxs'
insertSome t@(Tip ky _) k x kxs
| k == ky
= insertMany (Tip k x) kxs
| otherwise
= insertMany (link k (Tip k x) ky t) kxs
insertSome Nil k x kxs = insertMany (Tip k x) kxs
insertMany :: IntMap a -> [(Key, a)] -> Inserted' a
insertMany t [] = InsertedNil t
insertMany t ((k, x) : kxs') = insertMany' t k x kxs'
insertMany' t@(Bin p m _ _) k x kxs'
| nomatch k p m
= InsertedCons t k x kxs'
| otherwise
= insertSome t k x kxs'
insertMany' t@(Tip ky _) k x kxs'
| k==ky = insertSome t k x kxs'
| otherwise = InsertedCons t k x kxs'
insertMany' Nil !k x kxs' = InsertedNil Nil -- Unused case
Raw
IntMapFL.out
[1,[0,1]]/fromList mean 19.43 ns ( +- 23.65 ps )
[1,[0,1]]/fromList1 mean 23.06 ns ( +- 29.54 ps )
[1,[0,1]]/fromList2 mean 22.14 ns ( +- 85.05 ps )
[1,[0,1]]/fromList3 mean 19.48 ns ( +- 26.81 ps )
[1,[0,51791]]/fromList mean 19.91 ns ( +- 20.28 ps )
[1,[0,51791]]/fromList1 mean 23.10 ns ( +- 27.95 ps )
[1,[0,51791]]/fromList2 mean 22.19 ns ( +- 55.32 ps )
[1,[0,51791]]/fromList3 mean 19.50 ns ( +- 57.87 ps )
[1,[0,0]]/fromList mean 16.80 ns ( +- 53.54 ps )
[1,[0,0]]/fromList1 mean 15.81 ns ( +- 33.71 ps )
[1,[0,0]]/fromList2 mean 14.60 ns ( +- 31.35 ps )
[1,[0,0]]/fromList3 mean 13.26 ns ( +- 40.96 ps )
[10,[0,1]]/fromList mean 132.1 ns ( +- 932.4 ps )
[10,[0,1]]/fromList1 mean 174.2 ns ( +- 1.306 ns )
[10,[0,1]]/fromList2 mean 140.3 ns ( +- 715.9 ps )
[10,[0,1]]/fromList3 mean 168.2 ns ( +- 296.9 ps )
[10,[0,51791]]/fromList mean 145.3 ns ( +- 508.6 ps )
[10,[0,51791]]/fromList1 mean 165.6 ns ( +- 453.3 ps )
[10,[0,51791]]/fromList2 mean 136.1 ns ( +- 725.7 ps )
[10,[0,51791]]/fromList3 mean 155.3 ns ( +- 287.6 ps )
[10,[0,3]]/fromList mean 171.8 ns ( +- 662.5 ps )
[10,[0,3]]/fromList1 mean 213.5 ns ( +- 1.638 ns )
[10,[0,3]]/fromList2 mean 188.7 ns ( +- 406.4 ps )
[10,[0,3]]/fromList3 mean 201.7 ns ( +- 1.186 ns )
[100,[0,1]]/fromList mean 1.999 μs ( +- 22.96 ns )
[100,[0,1]]/fromList1 mean 1.818 μs ( +- 2.818 ns )
[100,[0,1]]/fromList2 mean 1.463 μs ( +- 1.645 ns )
[100,[0,1]]/fromList3 mean 1.713 μs ( +- 9.049 ns )
[100,[0,51791]]/fromList mean 2.002 μs ( +- 11.73 ns )
[100,[0,51791]]/fromList1 mean 1.820 μs ( +- 16.11 ns )
[100,[0,51791]]/fromList2 mean 1.435 μs ( +- 3.726 ns )
[100,[0,51791]]/fromList3 mean 1.728 μs ( +- 11.81 ns )
[100,[0,33]]/fromList mean 2.453 μs ( +- 12.94 ns )
[100,[0,33]]/fromList1 mean 3.883 μs ( +- 56.00 ns )
[100,[0,33]]/fromList2 mean 3.258 μs ( +- 74.26 ns )
[100,[0,33]]/fromList3 mean 3.694 μs ( +- 13.42 ns )
[1000,[0,1]]/fromList mean 31.71 μs ( +- 132.4 ns )
[1000,[0,1]]/fromList1 mean 19.49 μs ( +- 245.6 ns )
[1000,[0,1]]/fromList2 mean 16.22 μs ( +- 47.80 ns )
[1000,[0,1]]/fromList3 mean 18.93 μs ( +- 132.0 ns )
[1000,[0,51791]]/fromList mean 32.43 μs ( +- 98.25 ns )
[1000,[0,51791]]/fromList1 mean 21.97 μs ( +- 1.181 μs )
[1000,[0,51791]]/fromList2 mean 16.49 μs ( +- 42.41 ns )
[1000,[0,51791]]/fromList3 mean 19.74 μs ( +- 187.0 ns )
[1000,[0,333]]/fromList mean 48.92 μs ( +- 149.1 ns )
[1000,[0,333]]/fromList1 mean 67.91 μs ( +- 148.4 ns )
[1000,[0,333]]/fromList2 mean 65.67 μs ( +- 173.7 ns )
[1000,[0,333]]/fromList3 mean 70.12 μs ( +- 183.3 ns )
[10000,[0,1]]/fromList mean 1.088 ms ( +- 6.264 μs )
[10000,[0,1]]/fromList1 mean 290.7 μs ( +- 1.043 μs )
[10000,[0,1]]/fromList2 mean 348.7 μs ( +- 36.87 μs )
[10000,[0,1]]/fromList3 mean 432.9 μs ( +- 3.354 μs )
[10000,[0,51791]]/fromList mean 1.127 ms ( +- 7.511 μs )
[10000,[0,51791]]/fromList1 mean 311.5 μs ( +- 9.061 μs )
[10000,[0,51791]]/fromList2 mean 336.3 μs ( +- 31.00 μs )
[10000,[0,51791]]/fromList3 mean 461.5 μs ( +- 6.065 μs )
[10000,[0,3333]]/fromList mean 1.316 ms ( +- 4.792 μs )
[10000,[0,3333]]/fromList1 mean 1.548 ms ( +- 9.449 μs )
[10000,[0,3333]]/fromList2 mean 1.522 ms ( +- 6.414 μs )
[10000,[0,3333]]/fromList3 mean 1.573 ms ( +- 8.556 μs )
[100000,[0,1]]/fromList mean 13.27 ms ( +- 406.3 μs )
[100000,[0,1]]/fromList1 mean 9.527 ms ( +- 256.5 μs )
[100000,[0,1]]/fromList2 mean 9.282 ms ( +- 249.5 μs )
[100000,[0,1]]/fromList3 mean 9.455 ms ( +- 258.4 μs )
[100000,[0,51791]]/fromList mean 13.54 ms ( +- 383.9 μs )
[100000,[0,51791]]/fromList1 mean 9.919 ms ( +- 262.6 μs )
[100000,[0,51791]]/fromList2 mean 9.552 ms ( +- 207.8 μs )
[100000,[0,51791]]/fromList3 mean 9.874 ms ( +- 264.4 μs )
[100000,[0,33333]]/fromList mean 15.33 ms ( +- 310.0 μs )
[100000,[0,33333]]/fromList1 mean 18.22 ms ( +- 347.3 μs )
[100000,[0,33333]]/fromList2 mean 17.88 ms ( +- 296.5 μs )
[100000,[0,33333]]/fromList3 mean 18.38 ms ( +- 306.3 μs )
[1000000,[0,1]]/fromList mean 141.6 ms ( +- 12.27 ms )
[1000000,[0,1]]/fromList1 mean 95.13 ms ( +- 10.14 ms )
[1000000,[0,1]]/fromList2 mean 92.41 ms ( +- 9.987 ms )
[1000000,[0,1]]/fromList3 mean 95.23 ms ( +- 9.953 ms )
[1000000,[0,51791]]/fromList mean 144.4 ms ( +- 11.55 ms )
[1000000,[0,51791]]/fromList1 mean 99.49 ms ( +- 10.49 ms )
[1000000,[0,51791]]/fromList2 mean 96.58 ms ( +- 10.25 ms )
[1000000,[0,51791]]/fromList3 mean 100.5 ms ( +- 10.24 ms )
[1000000,[0,333333]]/fromList mean 166.3 ms ( +- 12.56 ms )
[1000000,[0,333333]]/fromList1 mean 202.8 ms ( +- 11.23 ms )
[1000000,[0,333333]]/fromList2 mean 194.1 ms ( +- 10.99 ms )
[1000000,[0,333333]]/fromList3 mean 199.3 ms ( +- 10.62 ms )
[10000000,[0,1]]/fromList mean 1.498 s ( +- 123.6 ms )
[10000000,[0,1]]/fromList1 mean 952.9 ms ( +- 100.2 ms )
[10000000,[0,1]]/fromList2 mean 927.5 ms ( +- 99.82 ms )
[10000000,[0,1]]/fromList3 mean 956.3 ms ( +- 99.77 ms )
[10000000,[0,51791]]/fromList mean 1.560 s ( +- 113.6 ms )
[10000000,[0,51791]]/fromList1 mean 1.003 s ( +- 103.4 ms )
[10000000,[0,51791]]/fromList2 mean 973.2 ms ( +- 103.6 ms )
[10000000,[0,51791]]/fromList3 mean 1.019 s ( +- 102.6 ms )
[10000000,[0,3333333]]/fromList mean 1.775 s ( +- 126.2 ms )
[10000000,[0,3333333]]/fromList1 mean 2.221 s ( +- 109.9 ms )
[10000000,[0,3333333]]/fromList2 mean 2.118 s ( +- 104.4 ms )
[10000000,[0,3333333]]/fromList3 mean 2.162 s ( +- 106.7 ms )
Raw
IntSetFAL.hs
-- ghc -O2 -hide-package containers IntSetFAL.hs && ./IntSetFAL --small | tee IntSetFAL.out
{-# LANGUAGE BangPatterns #-}
{-# LANGUAGE RankNTypes #-}
import Control.DeepSeq (rnf)
import Control.Exception (evaluate)
import Gauge (bench, bgroup, env, defaultMain, whnf)
import Data.List (foldl')
import qualified Data.IntSet as S
import Data.Maybe (fromMaybe)
import Prelude hiding (lookup)
import GHC.Exts (inline)
import Data.IntSet.Internal (IntSet (..), Prefix, Mask, Key, BitMap, size, zero, bitmapOf, prefixBitMask)
import Data.IntMap.Internal (nomatch, shorter, mask, branchMask)
import qualified Data.IntSet.Internal as I
import Data.Bits
main = do
defaultMain $ [test (s*sz) sk |
sz <- [10^i | i <- [0..5]],
(s, sk) <- [(1,1), (-1,51791)]]
test sz sk =
env (let m = S.fromAscList elems :: S.IntSet in evaluate $ rnf [m]) $ \m -> bgroup n
[ bench "fromList" $ whnf S.fromList elems
, bench "fromList1" $ whnf fromList1 elems
, bench "fromAscList" $ whnf S.fromAscList elems
, bench "fromAscList1" $ whnf fromAscList1 elems
, bench "fromDistinctAscList" $ whnf S.fromDistinctAscList elems
]
where
n = "[" ++ show sz ++ "," ++ show sk ++ "]"
elems = keys
keys = map (sk*) (if sz < 0 then [2*sz `div` 3.. -sz `div` 3] else [0..sz])
data Inserted = Inserted !IntSet ![Key]
fromAscList1 :: [Key] -> IntSet
fromAscList1 [] = Nil
fromAscList1 (kx : zs1) = addAll' (prefixOf kx) (bitmapOf kx) zs1
where
-- `addAll'` collects all keys with the prefix `px` into a single
-- bitmap, and then proceeds with `addAll`.
addAll' !px !bm [] = Tip px bm
addAll' !px !bm (ky : zs)
| px == prefixOf ky
= addAll' px (bm .|. bitmapOf ky) zs
-- inlined: | otherwise = addAll px (Tip px bm) (ky : zs)
| py <- prefixOf ky
, m <- branchMask px py
, Inserted ty zs' <- addMany' m py (bitmapOf ky) zs
= addAll px (link py ty px (Tip px bm)) zs'
-- Note: for `addAll` and `addMany`, px is /a/ prefix inside the tree `tx`
-- `addAll` consumes the rest of the list, adding to the tree `tx`
addAll !px !tx []
= tx
addAll !px !tx (ky : zs)
| py <- prefixOf ky
, m <- branchMask px py
, Inserted ty zs' <- addMany' m py (bitmapOf ky) zs
= addAll px (link py ty px tx) zs'
-- `addMany'` is similar to `addAll'`, but proceeds with `addMany'`.
addMany' !m !px !bm [] = Inserted (Tip px bm) []
addMany' !m !px !bm zs0@(ky : zs)
| px == prefixOf ky
= addMany' m px (bm .|. bitmapOf ky) zs
-- inlined: | otherwise = addMany m px (Tip px bm) (ky : zs)
| mask px m /= mask ky m
= Inserted (Tip (prefixOf px) bm) zs0
| py <- prefixOf ky
, Inserted ty zs' <- addMany' (branchMask px py) py (bitmapOf ky) zs
= addMany m px (link py ty px (Tip px bm)) zs'
-- `addAll` adds to `tx` all keys whose prefix w.r.t. `m` agrees with `px`.
addMany !m !px tx []
= Inserted tx []
addMany !m !px tx zs0@(ky : zs)
| mask px m /= mask ky m
= Inserted tx zs0
| py <- prefixOf ky
, Inserted ty zs' <- addMany' (branchMask px ky) py (bitmapOf ky) zs
= addMany m px (link py ty px tx) zs'
------------------------------------------------------------------------------
-- fromList implementation from #653
------------------------------------------------------------------------------
-- | /O(n*min(n,W))/. Create a set from a list of integers.
fromList1 :: [Key] -> IntSet
fromList1 = insertAll Nil
{-# NOINLINE fromList1 #-}
insertAll :: IntSet -> [Key] -> IntSet
insertAll m [] = m
insertAll m (k : kxs)
| Inserted m' r <- insertSome m (prefixOf k) (bitmapOf k) kxs
= insertAll m' r
-- | Insert at least one entry into an 'IntSet' or subtree. If
-- others fit in the same resulting subtree, insert them too.
-- Return the new set and remaining values.
insertSome :: IntSet -> Prefix -> BitMap -> [Key] -> Inserted
insertSome t@(Bin p m l r) !k !x kxs
| nomatch k p m
= insertMany (link k (Tip k x) p t) kxs
| zero k m
, Inserted l' kxs' <- insertSome l k x kxs
= insertMany (Bin p m l' r) kxs'
| Inserted r' kxs' <- insertSome r k x kxs
= insertMany (Bin p m l r') kxs'
insertSome t@(Tip ky y) k x kxs
| k == ky
= insertMany (Tip k (x .|. y)) kxs
| otherwise
= insertMany (link k (Tip k x) ky t) kxs
insertSome Nil k x kxs = insertMany (Tip k x) kxs
-- | Try to insert some entries into a subtree of an 'IntMap'. If
-- they belong in some other subtree, just don't insert them.
insertMany :: IntSet -> [Key] -> Inserted
insertMany t [] = Inserted t []
insertMany t@(Bin p m _ _) kxs@(kx : kxs')
| nomatch (prefixOf kx) p m
= Inserted t kxs
| otherwise
= insertSome t (prefixOf kx) (bitmapOf kx) kxs'
insertMany t@(Tip ky _) kxs@(kx : kxs')
| prefixOf kx==ky
= insertSome t (prefixOf kx) (bitmapOf kx) kxs'
| otherwise
= Inserted t kxs
insertMany Nil kxs = Inserted Nil kxs -- Unused case
{--------------------------------------------------------------------
Link
--------------------------------------------------------------------}
link :: Prefix -> IntSet -> Prefix -> IntSet -> IntSet
link p1 t1 p2 t2
| zero p1 m = Bin p m t1 t2
| otherwise = Bin p m t2 t1
where
m = branchMask p1 p2
p = mask p1 m
{-# INLINE link #-}
prefixOf :: Int -> Prefix
prefixOf x = x .&. prefixBitMask
{-# INLINE prefixOf #-}
Raw
IntSetFAL.out
[1,1]/fromList mean 16.25 ns ( +- 47.28 ps )
[1,1]/fromList1 mean 15.66 ns ( +- 27.76 ps )
[1,1]/fromAscList mean 20.33 ns ( +- 28.16 ps )
[1,1]/fromAscList1 mean 10.84 ns ( +- 42.61 ps )
[1,1]/fromAscList1a mean 10.57 ns ( +- 19.20 ps )
[1,1]/fromDistinctAscList mean 13.76 ns ( +- 26.12 ps )
[-1,51791]/fromList mean 32.13 ns ( +- 168.1 ps )
[-1,51791]/fromList1 mean 38.07 ns ( +- 109.8 ps )
[-1,51791]/fromAscList mean 58.25 ns ( +- 129.6 ps )
[-1,51791]/fromAscList1 mean 29.46 ns ( +- 55.25 ps )
[-1,51791]/fromAscList1a mean 29.42 ns ( +- 86.65 ps )
[-1,51791]/fromDistinctAscList mean 42.55 ns ( +- 167.0 ps )
[10,1]/fromList mean 65.51 ns ( +- 106.6 ps )
[10,1]/fromList1 mean 50.32 ns ( +- 535.4 ps )
[10,1]/fromAscList mean 114.3 ns ( +- 1.055 ns )
[10,1]/fromAscList1 mean 37.85 ns ( +- 298.6 ps )
[10,1]/fromAscList1a mean 35.95 ns ( +- 387.5 ps )
[10,1]/fromDistinctAscList mean 45.69 ns ( +- 400.6 ps )
[-10,51791]/fromList mean 161.0 ns ( +- 5.401 ns )
[-10,51791]/fromList1 mean 216.1 ns ( +- 3.493 ns )
[-10,51791]/fromAscList mean 279.5 ns ( +- 3.350 ns )
[-10,51791]/fromAscList1 mean 149.1 ns ( +- 1.327 ns )
[-10,51791]/fromAscList1a mean 150.7 ns ( +- 2.081 ns )
[-10,51791]/fromDistinctAscList mean 197.8 ns ( +- 3.644 ns )
[100,1]/fromList mean 685.2 ns ( +- 819.9 ps )
[100,1]/fromList1 mean 384.7 ns ( +- 3.294 ns )
[100,1]/fromAscList mean 1.045 μs ( +- 2.011 ns )
[100,1]/fromAscList1 mean 314.9 ns ( +- 1.352 ns )
[100,1]/fromAscList1a mean 310.3 ns ( +- 919.3 ps )
[100,1]/fromDistinctAscList mean 352.2 ns ( +- 2.374 ns )
[-100,51791]/fromList mean 2.715 μs ( +- 126.1 ns )
[-100,51791]/fromList1 mean 1.973 μs ( +- 53.27 ns )
[-100,51791]/fromAscList mean 2.908 μs ( +- 23.44 ns )
[-100,51791]/fromAscList1 mean 1.514 μs ( +- 66.58 ns )
[-100,51791]/fromAscList1a mean 1.540 μs ( +- 110.7 ns )
[-100,51791]/fromDistinctAscList mean 1.968 μs ( +- 78.88 ns )
[1000,1]/fromList mean 15.09 μs ( +- 179.5 ns )
[1000,1]/fromList1 mean 3.959 μs ( +- 30.98 ns )
[1000,1]/fromAscList mean 10.62 μs ( +- 96.06 ns )
[1000,1]/fromAscList1 mean 3.485 μs ( +- 21.47 ns )
[1000,1]/fromAscList1a mean 3.465 μs ( +- 15.71 ns )
[1000,1]/fromDistinctAscList mean 3.608 μs ( +- 17.72 ns )
[-1000,51791]/fromList mean 41.56 μs ( +- 657.8 ns )
[-1000,51791]/fromList1 mean 20.39 μs ( +- 486.0 ns )
[-1000,51791]/fromAscList mean 30.31 μs ( +- 473.3 ns )
[-1000,51791]/fromAscList1 mean 15.36 μs ( +- 386.5 ns )
[-1000,51791]/fromAscList1a mean 15.52 μs ( +- 397.5 ns )
[-1000,51791]/fromDistinctAscList mean 20.84 μs ( +- 815.6 ns )
[10000,1]/fromList mean 240.6 μs ( +- 2.536 μs )
[10000,1]/fromList1 mean 38.79 μs ( +- 108.4 ns )
[10000,1]/fromAscList mean 107.4 μs ( +- 139.5 ns )
[10000,1]/fromAscList1 mean 34.12 μs ( +- 68.15 ns )
[10000,1]/fromAscList1a mean 34.22 μs ( +- 113.9 ns )
[10000,1]/fromDistinctAscList mean 35.49 μs ( +- 390.5 ns )
[-10000,51791]/fromList mean 1.128 ms ( +- 11.23 μs )
[-10000,51791]/fromList1 mean 289.8 μs ( +- 3.570 μs )
[-10000,51791]/fromAscList mean 713.3 μs ( +- 13.66 μs )
[-10000,51791]/fromAscList1 mean 228.4 μs ( +- 6.227 μs )
[-10000,51791]/fromAscList1a mean 227.3 μs ( +- 4.131 μs )
[-10000,51791]/fromDistinctAscList mean 304.9 μs ( +- 8.183 μs )
[100000,1]/fromList mean 3.330 ms ( +- 21.28 μs )
[100000,1]/fromList1 mean 387.8 μs ( +- 852.9 ns )
[100000,1]/fromAscList mean 1.181 ms ( +- 22.59 μs )
[100000,1]/fromAscList1 mean 339.6 μs ( +- 792.5 ns )
[100000,1]/fromAscList1a mean 340.5 μs ( +- 895.0 ns )
[100000,1]/fromDistinctAscList mean 353.8 μs ( +- 1.010 μs )
[-100000,51791]/fromList mean 13.85 ms ( +- 223.1 μs )
[-100000,51791]/fromList1 mean 9.073 ms ( +- 168.6 μs )
[-100000,51791]/fromAscList mean 10.57 ms ( +- 255.6 μs )
[-100000,51791]/fromAscList1 mean 8.106 ms ( +- 226.4 μs )
[-100000,51791]/fromAscList1a mean 8.032 ms ( +- 226.6 μs )
[-100000,51791]/fromDistinctAscList mean 9.036 ms ( +- 138.5 μs )
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment