Hedge.hs

-- Is Set.union better than O(n+m) in some cases?

import Criterion.Main (Benchmark, bench, bgroup, defaultMain, env, whnf)
import Data.Set (Set, fromList, union)

main :: IO ()
main = defaultMain [ bgroup "union" $ map benchUnion sizes ]

-- Grow Set size exponentially, under the hypothesis that
-- Set.union will be O(log n) in this special case.
sizes :: [(Int,Int)]
sizes = take 10 $ zip [0..] $ iterate (*2) 2048

-- We take the special case where the largest element in
-- the first set is smaller than the smallest element in
-- the second set. In this case, union should reduce to
-- concatenation and rebalance.
inputs :: Int -> IO (Set Int, Set Int)
inputs n = return (fromList [1..n], fromList [n+1..2*n])

-- Be careful to fully construct the input sets before
-- we start measuring.
benchUnion :: (Int,Int) -> Benchmark
benchUnion (i,n) = env (inputs n) $ bench (show i) . whnf (uncurry union)