Formal proposal: replace Data.List.inits

[David Feuer]

What I'm seeing is very different from what you're seeing. In
particular, my tests with   print $ sum $ concat $ inits [1..10000]
indicate that your initsT' function is much faster, and allocates much
less than, the initsQ version. Could you explain what your test was
doing? What version of GHC were you running them on? Another thing: I
also see the performance impact of using take' instead of take, but I
can't for the life of me understand why. Do you know?

If others see similar results, I think we should scrap initsQ and use
your initsT'.

On Tue, Aug 19, 2014 at 6:42 PM, Bertram Felgenhauer
<bertram.felgenhauer at googlemail.com> wrote:
> David Feuer wrote:
>> I don't know why you're looking at initsHO, which is almost the same as
>> initsR but slightly slower. Have you looked at initsQ (preferably
>> implemented with scanl')? That's the one that fixes the bad cases.
>
> No, because I looked at the wrong part of your mail. Adding timings:
>
>> > - using only first elements of result lists:
>> >
>> > > sum' $ map head $ tail $ inits [1..10000]
>> > 10000
>> > (5.38 secs, 5905331504 bytes)
>> > > sum' $ map head $ tail $ initsR [1..10000]
>> > 10000
>> > (0.55 secs, 1203045184 bytes)
>> > > sum' $ map head $ tail $ initsHO [1..10000]
>> > 10000
>> > (1.11 secs, 1205462216 bytes)
>> > > sum' $ map head $ tail $ initsT [1..10000]
>> > 10000
>> > (0.01 secs, 7226208 bytes)
>> > > sum' $ map head $ tail $ initsT' [1..10000]
>> > 10000
>> > (0.01 secs, 8119224 bytes)
>> sum' $ map head $ tail $ initsQ [1..10000]
> 10000
> (0.01 secs, 7309616 bytes)
>> sum' $ map head $ tail $ initsQ' [1..10000]
> 10000
> (0.01 secs, 8908320 bytes)
>
> All these results are pretty meaningless beyond demonstrating
> that initsT and initsQ are sufficiently lazy.
>
>> >
>> > - using whole result:
>> >
>> > > sum' $ map sum' $ tail $ inits [1..10000]
>> > 166716670000
>> > (7.79 secs, 7900276296 bytes)
>> > > sum' $ map sum' $ tail $ initsR [1..10000]
>> > 166716670000
>> > (1.35 secs, 2006560272 bytes)
>> > > sum' $ map sum' $ tail $ initsHO [1..10000]
>> > 166716670000
>> > (1.93 secs, 2003170216 bytes)
>> > > sum' $ map sum' $ tail $ initsT [1..10000]
>> > 166716670000
>> > (2.16 secs, 3603697344 bytes)
>> > > sum' $ map sum' $ tail $ initsT' [1..10000]
>> > 166716670000
>> > (1.61 secs, 3603897320 bytes)
>
>> sum' $ map sum' $ tail $ initsQ [1..10000]
> 166716670000
> (3.30 secs, 3194869384 bytes)
>> sum' $ map sum' $ tail $ initsQ' [1..10000]
> 166716670000
> (3.26 secs, 3195015296 bytes)
>
> I've also run some criterion benchmarks, see the html files at
>
>   http://int-e.eu/~bf3/haskell/inits/
>
> (Is there a way to get criterion to split the summary table in
> its html output by groups?)
>
> Inits.hs contains the various inits implementations.
> inits.tar.gz contains everything.
>
> Interestingly, initsQ looks better than initsT in these benchmarks.
>
> Cheers,
>
> Bertram
>
>
> _______________________________________________
> Libraries mailing list
> Libraries at haskell.org
> http://www.haskell.org/mailman/listinfo/libraries