<div dir="ltr"><div dir="ltr"><div dir="ltr">In high performance Haskell, you will often find yourself using sequential structures besides lists. For example, an unboxed vector implementation is over 100x faster than any of the proposed list implementations. <div><br></div><div>Code: <a href="https://gist.github.com/wyager/45946f9f1531351468e4366b7ba168fa">https://gist.github.com/wyager/45946f9f1531351468e4366b7ba168fa</a></div><div><br></div><div>Benchmark result: <a href="https://gist.github.com/wyager/96e7876a4b170d83dca971dd152e475e">https://gist.github.com/wyager/96e7876a4b170d83dca971dd152e475e</a></div><div><br></div><div>GHC is very powerful, and can often do a surprisingly good job of optimizing away list allocations and such. However, in sharing-heavy applications like this (and if random indexing is helpful), Vectors can be much more efficient.</div></div></div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Thu, Aug 1, 2019 at 5:25 PM Jaro Reinders <<a href="mailto:jaro.reinders@gmail.com">jaro.reinders@gmail.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex">I just realized seqTails and seqInits are unnecessary, seqList is enough.<br>
<br>
On 01-08-2019 11:04, Jaro Reinders wrote:<br>
> Replying to myself, you can actually write an evaluation function that<br>
> forces all values in the result of tails and inits in linear time:<br>
> <br>
> -- force the result of tails in linear time<br>
> seqTails (x:xs) = x `deepseq` seqList xs<br>
> seqTails [] = ()<br>
> <br>
> -- force all the values in a list to whnf in linear time<br>
> -- <a href="https://wiki.haskell.org/Weak_head_normal_form" rel="noreferrer" target="_blank">https://wiki.haskell.org/Weak_head_normal_form</a><br>
> seqList (x:xs) = x `seq` seqList xs<br>
> seqList [] = ()<br>
> <br>
> -- force the result of inits in linear time<br>
> seqInits xs = last xs `deepseq` seqList xs<br>
> <br>
> Try it in ghci with :sprint<br>
> (<a href="https://downloads.haskell.org/~ghc/latest/docs/html/users_guide/ghci.html#ghci-cmd-:sprint" rel="noreferrer" target="_blank">https://downloads.haskell.org/~ghc/latest/docs/html/users_guide/ghci.html#ghci-cmd-:sprint</a>):<br>
> <br>
> > let x = tails [1..3::Int]<br>
> > :sprint x<br>
> x = _<br>
> > seqTails x<br>
> ()<br>
> > :sprint x<br>
> x = [[1,2,3],[2,3],[3],[]]<br>
> <br>
> > let y = inits [1..3::Int]<br>
> > :sprint y<br>
> y = _<br>
> > seqInits y<br>
> ()<br>
> > :sprint y<br>
> y = [[],[1],[1,2],[1,2,3]]<br>
> <br>
> Using criterion you can see that it is actually linear time:<br>
> <br>
> main = defaultMain<br>
> [ bgroup "inits"<br>
> [ bench "1000" $ whnf (seqInits . inits) [1..1000 :: Int]<br>
> , bench "10000" $ whnf (seqInits . inits) [1..10000 :: Int]<br>
> , bench "100000" $ whnf (seqInits . inits) [1..100000 :: Int]<br>
> , bench "1000000" $ whnf (seqInits . inits) [1..1000000 :: Int]<br>
> ]<br>
> , bgroup "tails"<br>
> [ bench "1000" $ whnf (seqTails . tails) [1..1000 :: Int]<br>
> , bench "10000" $ whnf (seqTails . tails) [1..10000 :: Int]<br>
> , bench "100000" $ whnf (seqTails . tails) [1..100000 :: Int]<br>
> , bench "1000000" $ whnf (seqTails . tails) [1..1000000 :: Int]<br>
> ]<br>
> ]<br>
> <br>
> <br>
> benchmarking inits/1000<br>
> time 204.2 μs (203.2 μs .. 205.4 μs)<br>
> 1.000 R² (1.000 R² .. 1.000 R²)<br>
> mean 203.4 μs (202.8 μs .. 204.1 μs)<br>
> std dev 2.163 μs (1.755 μs .. 2.664 μs)<br>
> <br>
> benchmarking inits/10000<br>
> time 3.127 ms (3.107 ms .. 3.148 ms)<br>
> 1.000 R² (0.999 R² .. 1.000 R²)<br>
> mean 3.105 ms (3.088 ms .. 3.118 ms)<br>
> std dev 45.73 μs (32.97 μs .. 69.14 μs)<br>
> <br>
> benchmarking inits/100000<br>
> time 41.05 ms (39.11 ms .. 42.87 ms)<br>
> 0.993 R² (0.988 R² .. 0.998 R²)<br>
> mean 41.52 ms (40.62 ms .. 42.46 ms)<br>
> std dev 1.912 ms (1.330 ms .. 2.930 ms)<br>
> variance introduced by outliers: 12% (moderately inflated)<br>
> <br>
> benchmarking inits/1000000<br>
> time 423.0 ms (318.2 ms .. 535.5 ms)<br>
> 0.991 R² (0.969 R² .. 1.000 R²)<br>
> mean 459.1 ms (428.8 ms .. 505.2 ms)<br>
> std dev 44.05 ms (10.06 ms .. 58.49 ms)<br>
> variance introduced by outliers: 22% (moderately inflated)<br>
> <br>
> <br>
> <br>
> benchmarking tails/1000<br>
> time 8.811 μs (8.768 μs .. 8.873 μs)<br>
> 1.000 R² (0.999 R² .. 1.000 R²)<br>
> mean 8.874 μs (8.819 μs .. 8.963 μs)<br>
> std dev 225.7 ns (168.4 ns .. 325.2 ns)<br>
> variance introduced by outliers: 28% (moderately inflated)<br>
> <br>
> benchmarking tails/10000<br>
> time 87.21 μs (86.85 μs .. 87.79 μs)<br>
> 1.000 R² (0.999 R² .. 1.000 R²)<br>
> mean 87.42 μs (87.01 μs .. 87.88 μs)<br>
> std dev 1.481 μs (1.132 μs .. 1.953 μs)<br>
> variance introduced by outliers: 11% (moderately inflated)<br>
> <br>
> benchmarking tails/100000<br>
> time 886.9 μs (882.9 μs .. 890.9 μs)<br>
> 1.000 R² (1.000 R² .. 1.000 R²)<br>
> mean 881.5 μs (878.1 μs .. 885.7 μs)<br>
> std dev 12.40 μs (9.598 μs .. 18.97 μs)<br>
> <br>
> benchmarking tails/1000000<br>
> time 9.796 ms (9.757 ms .. 9.840 ms)<br>
> 1.000 R² (1.000 R² .. 1.000 R²)<br>
> mean 9.817 ms (9.791 ms .. 9.845 ms)<br>
> std dev 78.47 μs (60.63 μs .. 99.31 μs)<br>
> <br>
> <br>
> On 01-08-2019 10:25, Jaro Reinders wrote:<br>
>> If you fully evaluate the list produced by tails, then you're still<br>
>> spending O(n^2) time, because that is just the size of the produced<br>
>> list. But constructing the list and the memory taken by the list is<br>
>> O(n), because most of the lists are shared<br>
>> (<a href="https://wiki.haskell.org/Sharing" rel="noreferrer" target="_blank">https://wiki.haskell.org/Sharing</a>).<br>
>><br>
>> On 01-08-2019 04:45, Todd Wilson wrote:<br>
>>> It seems that, asymptotically, tails is O(n) while inits is O(n^2) in<br>
>>> both time and space (when fully evaluated)<br>
_______________________________________________<br>
Haskell-Cafe mailing list<br>
To (un)subscribe, modify options or view archives go to:<br>
<a href="http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe" rel="noreferrer" target="_blank">http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe</a><br>
Only members subscribed via the mailman list are allowed to post.</blockquote></div>