Benchmark.hs

import Data.List
import qualified Data.Set as Set
import Criterion.Main 
import System.Random
 
itemsEqualOnDiff :: (Eq a) => [a] -> [a] -> Bool
itemsEqualOnDiff a b = null $ absDiff a b

absDiff :: (Eq a) => [a] -> [a] -> [a]
absDiff [] [] = []
absDiff [] b = b
absDiff a [] = a
absDiff (aHead:aTail) b = absDiff aTail $ delete aHead b

itemsEqualOnSort :: (Eq a, Ord a) => [a] -> [a] -> Bool
itemsEqualOnSort a b = sort a == sort b
 
-- Note: produces incorrect results for lists with duplicate items
itemsEqualOnSet :: (Eq a, Ord a) => [a] -> [a] -> Bool
itemsEqualOnSet a b = Set.fromList a == Set.fromList b

itemsEqualNaive :: (Eq a) => [a] -> [a] -> Bool
itemsEqualNaive xs ys = all (`elem` ys) xs && all (`elem` xs) ys

generateInput :: Int -> Int -> IO ([Int], [Int])
generateInput amount1 amount2 = do
  gen1 <- newStdGen
  gen2 <- newStdGen
  return (take amount1 $ randoms gen1, take amount2 $ randoms gen2)
 
main :: IO ()
main = do
  input1 <- generateInput 100 100
  input2 <- generateInput 10 100
  input3 <- generateInput 100 10
  input4 <- return ([0..99] :: [Int], [0..99] :: [Int])
  input5 <- return ([0..99] :: [Int], [99..0] :: [Int])
  defaultMain 
    [
      bgroup "random 100 100" [
          bench "itemsEqualOnDiff" $ nf (uncurry itemsEqualOnDiff) input1,
          bench "itemsEqualNaive" $ nf (uncurry itemsEqualNaive) input1,
          bench "itemsEqualOnSort" $ nf (uncurry itemsEqualOnSort) input1,
          bench "itemsEqualOnSet" $ nf (uncurry itemsEqualOnSet) input1
        ],
      bgroup "random 10 100" [
          bench "itemsEqualOnDiff" $ nf (uncurry itemsEqualOnDiff) input2,
          bench "itemsEqualNaive" $ nf (uncurry itemsEqualNaive) input2,
          bench "itemsEqualOnSort" $ nf (uncurry itemsEqualOnSort) input2,
          bench "itemsEqualOnSet" $ nf (uncurry itemsEqualOnSet) input2
        ],
      bgroup "random 100 10" [
          bench "itemsEqualOnDiff" $ nf (uncurry itemsEqualOnDiff) input3,
          bench "itemsEqualNaive" $ nf (uncurry itemsEqualNaive) input3,
          bench "itemsEqualOnSort" $ nf (uncurry itemsEqualOnSort) input3,
          bench "itemsEqualOnSet" $ nf (uncurry itemsEqualOnSet) input3
        ],
      bgroup "[0..99] [0..99]" [
          bench "itemsEqualOnDiff" $ nf (uncurry itemsEqualOnDiff) input4,
          bench "itemsEqualNaive" $ nf (uncurry itemsEqualNaive) input4,
          bench "itemsEqualOnSort" $ nf (uncurry itemsEqualOnSort) input4,
          bench "itemsEqualOnSet" $ nf (uncurry itemsEqualOnSet) input4
        ],
      bgroup "[0..99] [99..0]" [
          bench "itemsEqualOnDiff" $ nf (uncurry itemsEqualOnDiff) input5,
          bench "itemsEqualNaive" $ nf (uncurry itemsEqualNaive) input5,
          bench "itemsEqualOnSort" $ nf (uncurry itemsEqualOnSort) input5,
          bench "itemsEqualOnSet" $ nf (uncurry itemsEqualOnSet) input5
        ]
    ]

Output

warming up
estimating clock resolution...
mean is 988.2607 ns (640001 iterations)
found 1124139 outliers among 639999 samples (175.6%)
  514183 (80.3%) low severe
  609956 (95.3%) high severe
estimating cost of a clock call...
mean is 40.37861 ns (8 iterations)

benchmarking random 100 100/itemsEqualOnDiff
mean: 1.198004 us, lb 1.197092 us, ub 1.199059 us, ci 0.950
std dev: 5.039544 ns, lb 4.368224 ns, ub 6.064091 ns, ci 0.950

benchmarking random 100 100/itemsEqualNaive
mean: 929.8640 ns, lb 929.3751 ns, ub 930.4202 ns, ci 0.950
std dev: 2.676029 ns, lb 2.383578 ns, ub 3.016966 ns, ci 0.950

benchmarking random 100 100/itemsEqualOnSort
mean: 6.023235 us, lb 6.015157 us, ub 6.031514 us, ci 0.950
std dev: 41.76089 ns, lb 36.83852 ns, ub 48.06660 ns, ci 0.950

benchmarking random 100 100/itemsEqualOnSet
mean: 16.45466 us, lb 16.42851 us, ub 16.47834 us, ci 0.950
std dev: 126.9636 ns, lb 107.0879 ns, ub 156.3286 ns, ci 0.950

benchmarking random 10 100/itemsEqualOnDiff
mean: 135.9157 ns, lb 135.8144 ns, ub 136.0209 ns, ci 0.950
std dev: 529.7355 ps, lb 468.4469 ps, ub 610.2283 ps, ci 0.950

benchmarking random 10 100/itemsEqualNaive
mean: 929.9834 ns, lb 929.4314 ns, ub 930.6427 ns, ci 0.950
std dev: 3.073013 ns, lb 2.699540 ns, ub 3.676217 ns, ci 0.950

benchmarking random 10 100/itemsEqualOnSort
mean: 3.336991 us, lb 3.332013 us, ub 3.342242 us, ci 0.950
std dev: 26.27884 ns, lb 23.13360 ns, ub 30.87266 ns, ci 0.950

benchmarking random 10 100/itemsEqualOnSet
mean: 8.385784 us, lb 8.368574 us, ub 8.403415 us, ci 0.950
std dev: 88.96902 ns, lb 79.03825 ns, ub 101.7275 ns, ci 0.950

benchmarking random 100 10/itemsEqualOnDiff
mean: 1.204659 us, lb 1.203755 us, ub 1.205703 us, ci 0.950
std dev: 4.982297 ns, lb 4.281779 ns, ub 6.183801 ns, ci 0.950

benchmarking random 100 10/itemsEqualNaive
mean: 114.0267 ns, lb 113.9620 ns, ub 114.0953 ns, ci 0.950
std dev: 343.6866 ps, lb 304.8662 ps, ub 395.5064 ps, ci 0.950

benchmarking random 100 10/itemsEqualOnSort
mean: 3.285705 us, lb 3.281160 us, ub 3.290409 us, ci 0.950
std dev: 23.73831 ns, lb 20.88172 ns, ub 27.44608 ns, ci 0.950

benchmarking random 100 10/itemsEqualOnSet
mean: 8.159887 us, lb 8.149621 us, ub 8.170133 us, ci 0.950
std dev: 52.53210 ns, lb 46.66306 ns, ub 59.74423 ns, ci 0.950

benchmarking [0..99] [0..99]/itemsEqualOnDiff
mean: 1.147811 us, lb 1.147095 us, ub 1.148757 us, ci 0.950
std dev: 4.192552 ns, lb 3.393398 ns, ub 5.831377 ns, ci 0.950

benchmarking [0..99] [0..99]/itemsEqualNaive
mean: 94.07999 us, lb 93.95991 us, ub 94.13114 us, ci 0.950
std dev: 379.4334 ns, lb 190.4914 ns, ub 789.1650 ns, ci 0.950

benchmarking [0..99] [0..99]/itemsEqualOnSort
mean: 3.134826 us, lb 3.131943 us, ub 3.138005 us, ci 0.950
std dev: 15.55833 ns, lb 13.75411 ns, ub 17.75900 ns, ci 0.950

benchmarking [0..99] [0..99]/itemsEqualOnSet
mean: 20.59833 us, lb 20.56693 us, ub 20.63245 us, ci 0.950
std dev: 167.7794 ns, lb 147.9475 ns, ub 198.3435 ns, ci 0.950

benchmarking [0..99] [99..0]/itemsEqualOnDiff
mean: 16.25316 ns, lb 16.24223 ns, ub 16.26517 ns, ci 0.950
std dev: 58.73772 ps, lb 51.39849 ps, ub 68.29472 ps, ci 0.950

benchmarking [0..99] [99..0]/itemsEqualNaive
mean: 20.10484 ns, lb 20.09001 ns, ub 20.12118 ns, ci 0.950
std dev: 79.54973 ps, lb 70.53075 ps, ub 90.99370 ps, ci 0.950

benchmarking [0..99] [99..0]/itemsEqualOnSort
mean: 1.029432 us, lb 1.028066 us, ub 1.030944 us, ci 0.950
std dev: 7.388647 ns, lb 6.477373 ns, ub 8.848523 ns, ci 0.950

benchmarking [0..99] [99..0]/itemsEqualOnSet
mean: 8.362957 us, lb 8.355623 us, ub 8.372454 us, ci 0.950
std dev: 42.17929 ns, lb 33.87256 ns, ub 63.53781 ns, ci 0.950