Performance of Scan?

[Boarders]

Recently I was benchmarking various versions of what essentially amounts to:

scan_add = scanl1 (+)

I wondered how the foldl does at this task and so ran benchmarking on the input [0..10^6]. I tried the following implementation:

foldl_scan = scan (postscan L.sum)

Criterion gives the following output:

benchmarking scans/scanl
time                 10.87 ms   (10.78 ms .. 11.00 ms)
                     0.999 R²   (0.998 R² .. 1.000 R²)
mean                 10.93 ms   (10.88 ms .. 11.03 ms)
std dev              182.5 μs   (115.2 μs .. 336.6 μs)

benchmarking scans/foldl_scan
time                 108.1 ms   (102.5 ms .. 115.9 ms)
                     0.997 R²   (0.992 R² .. 1.000 R²)
mean                 112.1 ms   (110.0 ms .. 114.5 ms)
std dev              3.523 ms   (2.842 ms .. 4.492 ms)
variance introduced by outliers: 11% (moderately inflated)

Is performance like this on an example like this to be expected?

I should note that what I really want is to have:

runningTotal :: Num a => [a] -> ([a], a)

>>> runningTotal [1,2,3] = ([1,3,6], 6)

I don't know how to do this in one pass with the foldl library but doing it naively in haskell (as the foldl documentation suggests one shouldn't do):

dumb :: Num a => [a] -> (a, [a])
dumb xs = let adds = scanl1 (+) xs in (sum xs, adds)

gives extremely good performance on the same benchmark:

time                 14.86 ms   (14.77 ms .. 14.95 ms)
                     1.000 R²   (1.000 R² .. 1.000 R²)
mean                 14.83 ms   (14.79 ms .. 14.88 ms)
std dev              112.8 μs   (90.04 μs .. 140.8 μs)

[Gabriella439]

@Boarders: The thing that the foldl library is optimizing for is maximum memory residence since the library is built to compute things in constant space, so the real thing to compare would be heap usage for the two programs

[Boarders]

@Gabriel439 : Thanks for the reply (this is also a very nice library btw!)! I did try running the examples from the documentation (i.e. the various sumAndLength functions) using an input list [1..10^6]. On my machine I get these numbers:

benchmarking folds/sumAndLength
time                 6.251 ms   (6.180 ms .. 6.369 ms)
                     0.997 R²   (0.991 R² .. 0.999 R²)
mean                 6.352 ms   (6.304 ms .. 6.436 ms)
std dev              194.9 μs   (117.1 μs .. 320.2 μs)
allocated:           0.434 R²   (0.222 R² .. 0.735 R²)
  iters              97.634     (67.423 .. 133.574)
  y                  2598.304   (1829.205 .. 3547.639)
variance introduced by outliers: 13% (moderately inflated)

benchmarking folds/sumAndLength'
time                 113.6 ms   (103.3 ms .. 127.7 ms)
                     0.989 R²   (0.958 R² .. 0.999 R²)
mean                 127.4 ms   (121.5 ms .. 132.6 ms)
std dev              8.730 ms   (6.654 ms .. 10.73 ms)
allocated:           1.000 R²   (1.000 R² .. 1.000 R²)
  iters              8.123e7    (8.123e7 .. 8.123e7)
  y                  2531.429   (1840.000 .. 6804.103)
variance introduced by outliers: 12% (moderately inflated)

benchmarking folds/sumAndLength_Pair
time                 3.337 ms   (3.305 ms .. 3.378 ms)
                     0.997 R²   (0.994 R² .. 0.999 R²)
mean                 3.477 ms   (3.435 ms .. 3.531 ms)
std dev              154.2 μs   (116.6 μs .. 201.8 μs)
allocated:           0.362 R²   (0.151 R² .. 0.595 R²)
  iters              55.297     (33.753 .. 77.049)
  y                  2602.037   (1911.721 .. 3400.515)
variance introduced by outliers: 26% (moderately inflated)

benchmarking folds/sumAndLength_foldl
time                 7.706 ms   (7.215 ms .. 8.198 ms)
                     0.978 R²   (0.958 R² .. 0.992 R²)
mean                 7.414 ms   (7.263 ms .. 7.717 ms)
std dev              598.4 μs   (381.5 μs .. 960.4 μs)
allocated:           1.000 R²   (1.000 R² .. 1.000 R²)
  iters              5.600e7    (5.600e7 .. 5.600e7)
  y                  2630.881   (1712.713 .. 3742.472)
variance introduced by outliers: 45% (moderately inflated)

With implementations:

sumAndLength :: Num a => [a] -> (a, Int)
sumAndLength xs = (sum xs, length xs)

sumAndLength' :: Num a => [a] -> (a, Int)
sumAndLength' xs = foldl' step (0, 0) xs
  where
    step (x, y) n = (x + n, y + 1)

data Pair a b = Pair !a !b

sumAndLength_Pair :: Num a => [a] -> (a, Int)
sumAndLength_Pair xs = done (foldl' step (Pair 0 0) xs)
  where
    step (Pair x y) n = Pair (x + n) (y + 1)

    done (Pair x y) = (x, y)


sumAndLength_foldl = L.fold ((,) <$> L.sum <*> L.length)

Is this the correct measure for the library and if so are these numbers to be expected? I would be happy to make a pull request with these benchmarks added if they are relevant to the library.

EDIT: I got the numbers wrong but the point remains largely identical.

[Gabriella439]

@Boarders: Yeah, that is the correct measurement. I think most of the difference in performance is due to L.fold internally using "foldl' implemented in terms of foldr", which sometimes has a worse constant factor than Data.List.foldl', but exposes more opportunities for fusion

I'd also welcome adding the benchmarks to the library

[Boarders]

Running this on the list [1..10^7] and then on the list [1..10^8] gives the following:

[1..10^7]

benchmarking folds/sumAndLength
time                 53.07 ms   (52.21 ms .. 53.95 ms)
                     0.999 R²   (0.996 R² .. 1.000 R²)
mean                 56.26 ms   (55.16 ms .. 58.80 ms)
std dev              2.952 ms   (1.306 ms .. 4.894 ms)
allocated:           0.018 R²   (0.000 R² .. 1.000 R²)
  iters              64.923     (-278.199 .. 400.204)
  y                  3058.667   (562.886 .. 5332.815)
variance introduced by outliers: 15% (moderately inflated)

benchmarking folds/sumAndLength'
time                 1.182 s    (725.8 ms .. 1.551 s)
                     0.983 R²   (0.938 R² .. 1.000 R²)
mean                 1.135 s    (1.059 s .. 1.212 s)
std dev              90.70 ms   (70.05 ms .. 106.5 ms)
allocated:           1.000 R²   (1.000 R² .. 1.000 R²)
  iters              8.123e8    (8.123e8 .. NaN)
  y                  1840.000   (-3496.000 .. 15080.000)
variance introduced by outliers: 21% (moderately inflated)

benchmarking folds/sumAndLength_Pair
time                 29.67 ms   (29.60 ms .. 29.77 ms)
                     1.000 R²   (1.000 R² .. 1.000 R²)
mean                 29.72 ms   (29.68 ms .. 29.78 ms)
std dev              99.76 μs   (71.03 μs .. 147.6 μs)
allocated:           0.007 R²   (0.000 R² .. 1.000 R²)
  iters              25.333     (-134.912 .. 165.825)
  y                  2806.824   (1544.843 .. 4540.874)

benchmarking folds/sumAndLength_foldl
time                 64.28 ms   (64.08 ms .. 64.55 ms)
                     1.000 R²   (1.000 R² .. 1.000 R²)
mean                 64.17 ms   (64.06 ms .. 64.29 ms)
std dev              206.6 μs   (146.3 μs .. 287.0 μs)
allocated:           1.000 R²   (1.000 R² .. 1.000 R²)
  iters              5.600e8    (5.600e8 .. 5.600e8)
  y                  3388.800   (1840.000 .. 5939.765)

[1..10^8]

benchmarking folds/sumAndLength
time                 549.6 ms   (544.3 ms .. 556.4 ms)
                     1.000 R²   (1.000 R² .. 1.000 R²)
mean                 545.0 ms   (542.2 ms .. 546.6 ms)
std dev              2.744 ms   (1.217 ms .. 3.832 ms)
allocated:           0.003 R²   (0.001 R² .. 1.000 R²)
  iters              18.400     (-752.000 .. 960.000)
  y                  2268.000   (984.000 .. 4408.000)
variance introduced by outliers: 19% (moderately inflated)

benchmarking folds/sumAndLength'
time                 11.45 s    (9.275 s .. 14.55 s)
                     0.992 R²   (0.976 R² .. 1.000 R²)
mean                 11.66 s    (11.03 s .. 12.41 s)
std dev              765.8 ms   (322.2 ms .. 1.060 s)
allocated:           1.000 R²   (1.000 R² .. 1.000 R²)
  iters              8.123e9    (8.123e9 .. 8.123e9)
  y                  6752.000   (2696.000 .. 10808.000)
variance introduced by outliers: 19% (moderately inflated)

benchmarking folds/sumAndLength_Pair
time                 313.5 ms   (301.8 ms .. 330.1 ms)
                     0.999 R²   (0.996 R² .. 1.000 R²)
mean                 303.8 ms   (299.2 ms .. 311.6 ms)
std dev              7.006 ms   (3.634 ms .. 9.273 ms)
allocated:           0.535 R²   (0.385 R² .. 1.000 R²)
  iters              830.400    (56.000 .. 2234.000)
  y                  291.200    (-5420.000 .. 1840.000)
variance introduced by outliers: 16% (moderately inflated)

benchmarking folds/sumAndLength_foldl
time                 659.3 ms   (NaN s .. 704.5 ms)
                     0.999 R²   (0.999 R² .. 1.000 R²)
mean                 657.6 ms   (649.2 ms .. 665.6 ms)
std dev              9.581 ms   (6.488 ms .. 11.38 ms)
allocated:           1.000 R²   (1.000 R² .. 1.000 R²)
  iters              5.600e9    (5.600e9 .. 5.600e9)
  y                  4740.000   (-536.000 .. 14104.000)
variance introduced by outliers: 19% (moderately inflated)

This makes it seem like the foldl library definitely does not compute things in constant memory.

[Boarders]

The benchmark that I wrote for this is here. When I get some free time I will add something similar to the library. It does look though like there is a space leak in the code.

[agrue]

Your first example uses scan; there was a space leak in scan and scanM that I just fixed (See #137). Your other examples are folds, so I can't comment on those.