ghc -O Chop.hs -fforce-recomp -rtsopts./Chop -g -t png -k png +RTS -K100M1,000,000文字のStringに対してchopしています。空白がない文字列と、'a'と空白交互に出てくる文字列、空白だけの文字列の3種類で計測しています。
どの入力でもchopFoldr'（foldr + isSpaceを前にしたもの）が最速。
連続した空白がほとんど無い場合はスタックも伸びず2度のreverseも不要なchopFoldr'が速い。空白だけの場合はfoldr系はスタックを消費してしまうが、chopReverseも2度のreverseだけでなくdropWhileする範囲が増えるので、結果的にはchopFoldr'が速い。
| module Main where | |
| import Control.DeepSeq (deepseq) | |
| import Control.Exception (evaluate) | |
| import Criterion (bench, bgroup, nf) | |
| import Criterion.Main (defaultMain) | |
| import Data.Char (isSpace) | |
| import Prelude hiding (reverse, dropWhile) | |
| reverse :: [a] -> [a] | |
| reverse l = rev l [] | |
| where | |
| rev [] a = a | |
| rev (x:xs) a = rev xs (x:a) | |
| dropWhile :: (a -> Bool) -> [a] -> [a] | |
| dropWhile _ [] = [] | |
| dropWhile p xs@(x:xs') | |
| | p x = dropWhile p xs' | |
| | otherwise = xs | |
| chopReverse :: String -> String | |
| chopReverse = reverse . dropWhile isSpace . reverse | |
| chopFoldr :: String -> String | |
| chopFoldr = foldr f [] | |
| where | |
| f c [] | |
| | isSpace c = [] | |
| | otherwise = c:[] | |
| f c cs = c:cs | |
| chopFoldr' :: String -> String | |
| chopFoldr' = foldr f [] | |
| where | |
| f c cs | |
| | isSpace c && null cs = [] | |
| | otherwise = c:cs | |
| chopCPS :: String -> String | |
| chopCPS xs = foldl go id xs [] | |
| where | |
| go k c [] | |
| | isSpace c = k [] | |
| | otherwise = k (c:[]) | |
| go k c cs = k (c:cs) | |
| chopCPS' :: String -> String | |
| chopCPS' xs = foldl go id xs [] | |
| where | |
| go k c [] = k ((if isSpace c then id else (c:)) []) | |
| go k c cs = k (c:cs) | |
| chopCPS'' :: String -> String | |
| chopCPS'' xs = foldl go id xs [] | |
| where | |
| go k c cs | |
| | isSpace c && null cs = k [] | |
| | otherwise = k (c:cs) | |
| main :: IO () | |
| main = do | |
| benchmark | |
| -- evaluate $ chopFoldr' $ spaces 10000000 | |
| return () | |
| benchmark :: IO () | |
| benchmark = do | |
| let !st1000000 = let ss = string 1000000 in ss `deepseq` ss | |
| !ss1000000 = let ss = strspc 1000000 in ss `deepseq` ss | |
| !sp1000000 = let ss = spaces 1000000 in ss `deepseq` ss | |
| defaultMain | |
| [ bgroup "chop-string" | |
| [ bench "reverse" $ nf chopReverse st1000000 | |
| , bench "foldr" $ nf chopFoldr st1000000 | |
| , bench "foldr'" $ nf chopFoldr' st1000000 | |
| , bench "CPS" $ nf chopCPS st1000000 | |
| , bench "CPS'" $ nf chopCPS' st1000000 | |
| , bench "CPS''" $ nf chopCPS'' st1000000 | |
| ] | |
| , bgroup "chop-strspc" | |
| [ bench "reverse" $ nf chopReverse ss1000000 | |
| , bench "foldr" $ nf chopFoldr ss1000000 | |
| , bench "foldr'" $ nf chopFoldr' ss1000000 | |
| , bench "CPS" $ nf chopCPS ss1000000 | |
| , bench "CPS'" $ nf chopCPS' ss1000000 | |
| , bench "CPS''" $ nf chopCPS'' ss1000000 | |
| ] | |
| , bgroup "chop-spaces" | |
| [ bench "reverse" $ nf chopReverse sp1000000 | |
| , bench "foldr" $ nf chopFoldr sp1000000 | |
| , bench "foldr'" $ nf chopFoldr' sp1000000 | |
| , bench "CPS" $ nf chopCPS sp1000000 | |
| , bench "CPS'" $ nf chopCPS' sp1000000 | |
| , bench "CPS''" $ nf chopCPS'' sp1000000 | |
| ] | |
| ] | |
| string :: Int -> String | |
| string n = replicate n 'a' | |
| strspc :: Int -> String | |
| strspc n = take n $ cycle "a " | |
| spaces :: Int -> String | |
| spaces n = replicate n ' ' |
| warming up | |
| estimating clock resolution... | |
| mean is 9.785411 us (80001 iterations) | |
| found 35626 outliers among 79999 samples (44.5%) | |
| 18047 (22.6%) low severe | |
| 17579 (22.0%) high severe | |
| estimating cost of a clock call... | |
| mean is 99.09776 ns (74 iterations) | |
| found 10 outliers among 74 samples (13.5%) | |
| 1 (1.4%) high mild | |
| 9 (12.2%) high severe | |
| benchmarking chop-string/reverse | |
| collecting 100 samples, 1 iterations each, in estimated 16.40429 s | |
| mean: 241.6449 ms, lb 227.3405 ms, ub 255.9365 ms, ci 0.950 | |
| std dev: 72.92843 ms, lb 70.45506 ms, ub 77.68597 ms, ci 0.950 | |
| variance introduced by outliers: 3.000% | |
| variance is slightly inflated by outliers | |
| benchmarking chop-string/foldr | |
| collecting 100 samples, 1 iterations each, in estimated 67.58680 s | |
| mean: 712.0433 ms, lb 698.9535 ms, ub 726.8065 ms, ci 0.950 | |
| std dev: 71.46399 ms, lb 64.00021 ms, ub 86.70723 ms, ci 0.950 | |
| benchmarking chop-string/foldr' | |
| collecting 100 samples, 1 iterations each, in estimated 6.207991 s | |
| mean: 68.64650 ms, lb 66.90684 ms, ub 71.56666 ms, ci 0.950 | |
| std dev: 11.27203 ms, lb 7.548996 ms, ub 16.21609 ms, ci 0.950 | |
| benchmarking chop-string/CPS | |
| collecting 100 samples, 1 iterations each, in estimated 74.04840 s | |
| mean: 638.5145 ms, lb 601.1176 ms, ub 675.9074 ms, ci 0.950 | |
| std dev: 191.8131 ms, lb 178.3142 ms, ub 206.7595 ms, ci 0.950 | |
| variance introduced by outliers: 5.999% | |
| variance is slightly inflated by outliers | |
| benchmarking chop-string/CPS' | |
| collecting 100 samples, 1 iterations each, in estimated 27.37780 s | |
| mean: 411.6403 ms, lb 398.3822 ms, ub 426.5395 ms, ci 0.950 | |
| std dev: 71.97342 ms, lb 59.74985 ms, ub 87.24584 ms, ci 0.950 | |
| found 28 outliers among 100 samples (28.0%) | |
| 10 (10.0%) low severe | |
| 2 (2.0%) low mild | |
| 4 (4.0%) high mild | |
| 12 (12.0%) high severe | |
| variance introduced by outliers: 2.000% | |
| variance is slightly inflated by outliers | |
| benchmarking chop-string/CPS'' | |
| collecting 100 samples, 1 iterations each, in estimated 40.99610 s | |
| mean: 394.1977 ms, lb 379.4157 ms, ub 407.1842 ms, ci 0.950 | |
| std dev: 70.82964 ms, lb 62.27607 ms, ub 78.28748 ms, ci 0.950 | |
| found 21 outliers among 100 samples (21.0%) | |
| 20 (20.0%) low mild | |
| variance introduced by outliers: 2.000% | |
| variance is slightly inflated by outliers | |
| benchmarking chop-strspc/reverse | |
| collecting 100 samples, 1 iterations each, in estimated 27.86911 s | |
| mean: 246.4413 ms, lb 233.9072 ms, ub 259.4601 ms, ci 0.950 | |
| std dev: 65.29586 ms, lb 57.21395 ms, ub 75.12526 ms, ci 0.950 | |
| found 3 outliers among 100 samples (3.0%) | |
| 3 (3.0%) high mild | |
| variance introduced by outliers: 2.000% | |
| variance is slightly inflated by outliers | |
| benchmarking chop-strspc/foldr | |
| collecting 100 samples, 1 iterations each, in estimated 74.50049 s | |
| mean: 690.6038 ms, lb 680.5922 ms, ub 702.9399 ms, ci 0.950 | |
| std dev: 56.66894 ms, lb 47.24067 ms, ub 81.62895 ms, ci 0.950 | |
| benchmarking chop-strspc/foldr' | |
| mean: 42.55023 ms, lb 41.74964 ms, ub 44.70775 ms, ci 0.950 | |
| std dev: 6.172415 ms, lb 2.194789 ms, ub 12.72451 ms, ci 0.950 | |
| benchmarking chop-strspc/CPS | |
| collecting 100 samples, 1 iterations each, in estimated 51.67131 s | |
| mean: 590.9113 ms, lb 575.6454 ms, ub 605.9091 ms, ci 0.950 | |
| std dev: 77.98474 ms, lb 66.54682 ms, ub 93.34781 ms, ci 0.950 | |
| found 5 outliers among 100 samples (5.0%) | |
| 4 (4.0%) low mild | |
| variance introduced by outliers: 2.000% | |
| variance is slightly inflated by outliers | |
| benchmarking chop-strspc/CPS' | |
| collecting 100 samples, 1 iterations each, in estimated 39.64171 s | |
| mean: 404.0109 ms, lb 401.9010 ms, ub 407.9852 ms, ci 0.950 | |
| std dev: 14.35609 ms, lb 8.870366 ms, ub 23.99680 ms, ci 0.950 | |
| benchmarking chop-strspc/CPS'' | |
| collecting 100 samples, 1 iterations each, in estimated 37.60769 s | |
| mean: 374.7899 ms, lb 373.6585 ms, ub 376.2250 ms, ci 0.950 | |
| std dev: 6.503821 ms, lb 5.405233 ms, ub 7.704324 ms, ci 0.950 | |
| benchmarking chop-spaces/reverse | |
| collecting 100 samples, 1 iterations each, in estimated 8.136916 s | |
| mean: 114.2309 ms, lb 108.5386 ms, ub 119.7284 ms, ci 0.950 | |
| std dev: 28.54081 ms, lb 26.65981 ms, ub 30.66028 ms, ci 0.950 | |
| benchmarking chop-spaces/foldr | |
| mean: 37.09930 ms, lb 34.24411 ms, ub 40.70451 ms, ci 0.950 | |
| std dev: 16.31691 ms, lb 13.52355 ms, ub 19.24418 ms, ci 0.950 | |
| benchmarking chop-spaces/foldr' | |
| mean: 38.28595 ms, lb 33.43125 ms, ub 47.42654 ms, ci 0.950 | |
| std dev: 33.13593 ms, lb 18.40383 ms, ub 54.50525 ms, ci 0.950 | |
| found 10 outliers among 100 samples (10.0%) | |
| 8 (8.0%) high mild | |
| 2 (2.0%) high severe | |
| variance introduced by outliers: 3.000% | |
| variance is slightly inflated by outliers | |
| benchmarking chop-spaces/CPS | |
| collecting 100 samples, 1 iterations each, in estimated 76.42150 s | |
| mean: 654.8620 ms, lb 631.7833 ms, ub 678.1068 ms, ci 0.950 | |
| std dev: 118.6497 ms, lb 103.0706 ms, ub 138.3991 ms, ci 0.950 | |
| found 5 outliers among 100 samples (5.0%) | |
| 2 (2.0%) low mild | |
| 3 (3.0%) high mild | |
| variance introduced by outliers: 3.000% | |
| variance is slightly inflated by outliers | |
| benchmarking chop-spaces/CPS' | |
| collecting 100 samples, 1 iterations each, in estimated 42.06960 s | |
| mean: 406.8134 ms, lb 391.9791 ms, ub 421.5591 ms, ci 0.950 | |
| std dev: 75.83106 ms, lb 68.17951 ms, ub 84.53761 ms, ci 0.950 | |
| variance introduced by outliers: 2.000% | |
| variance is slightly inflated by outliers | |
| benchmarking chop-spaces/CPS'' | |
| collecting 100 samples, 1 iterations each, in estimated 32.48031 s | |
| mean: 389.8063 ms, lb 375.3149 ms, ub 403.8776 ms, ci 0.950 | |
| std dev: 73.22882 ms, lb 67.16954 ms, ub 79.88329 ms, ci 0.950 | |
| variance introduced by outliers: 2.000% | |
| variance is slightly inflated by outliers |