Stream fusion for Hackage

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
12 messages Options
Reply | Threaded
Open this post in threaded view
|

Stream fusion for Hackage

Don Stewart-2
Just a quick announce: the stream fusion library for lists,
that Duncan Coutts, Roman Leshchinskiy and I worked on earlier this year
is now available on Hackage as a standalone package:

    http://hackage.haskell.org/cgi-bin/hackage-scripts/package/stream-fusion-0.1.1

As described in the recent paper:

    "Stream Fusion: From Lists to Streams to Nothing at All"
    Duncan Coutts, Roman Leshchinskiy and Don Stewart. ICFP 2007

This is a drop-in replacement for Data.List.

Haddocks here,

    http://code.haskell.org/~dons/doc/stream-fusion/

(but note the interface is exactly the same as the Data.List library)

You might expect some small percent performance improvement for list
heavy programs, using ghc 6.8 and this list library with -O2 (use
-ddump-simpl-stats and look for:

    STREAM stream/unstream fusion

messages, indicating your intermediate lists are getting removed.

To get an idea of what is happening, consider this list program:

    foo :: Int -> Int
    foo n = sum (replicate n 1)

Compiled with ghc-6.8.1 -O2 -ddump-simpl

Normally, as sum is a left fold, an intermediate lazy list is allocated
between the call to sum and replicate, as GHC currently does:

    foo :: Int# -> Int#
    foo n = Data.List.sum (case <=# n 0 of
                                False -> go n
                                True  -> [])
        where
            go :: Int# -> [Int]   -- intermediate list!
            go n = case <=# n 1 of
                        False -> 1 : (go (n -# 1))
                        True  -> [1]

By using Data.List.Stream instead, you get a strict fused loop instead,
with no intermediate structure allocated:

    loop_sum :: Int# -> Int# -> Int#
    loop_sum k n  = case <=# n 0 of
                False -> loop_sum (k +# 1) (n -# 1)
                True  -> k

    foo :: Int# -> Int#
    foo n = loop_sum 0 n

This is a the halfway mark before porting other sequence types --
especially Data.ByteString -- over to the full stream fusion model (in
particular, strict bytestrings will benefit a lot, due to the O(n) cost
of intermediate bytestrings being removed).

The stream fusion types and combinators are also available in stripped
down form in the mlton sml compiler's extended prelude.

Enjoy.

-- Don
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Stream fusion for Hackage

Andrew Coppin
Don Stewart wrote:

> Just a quick announce: the stream fusion library for lists,
> that Duncan Coutts, Roman Leshchinskiy and I worked on earlier this year
> is now available on Hackage as a standalone package:
>
>     http://hackage.haskell.org/cgi-bin/hackage-scripts/package/stream-fusion-0.1.1
>
> As described in the recent paper:
>
>     "Stream Fusion: From Lists to Streams to Nothing at All"
>     Duncan Coutts, Roman Leshchinskiy and Don Stewart. ICFP 2007
>
> This is a drop-in replacement for Data.List.
>  

So let me get this straight... If I take a program that does lots of
list processing, and import this module instead of Data.List, the
program will magically go faster?

Sounds good to me! :-D

I wonder if this will make my Burrows-Weeler Transform program go any
faster? That's 100% list processing...

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Stream fusion for Hackage

Tom Schrijvers-2
In reply to this post by Don Stewart-2
On Sat, 17 Nov 2007, Don Stewart wrote:

> Just a quick announce: the stream fusion library for lists,
> that Duncan Coutts, Roman Leshchinskiy and I worked on earlier this year
> is now available on Hackage as a standalone package:
>
>    http://hackage.haskell.org/cgi-bin/hackage-scripts/package/stream-fusion-0.1.1
>
> As described in the recent paper:
>
>    "Stream Fusion: From Lists to Streams to Nothing at All"
>    Duncan Coutts, Roman Leshchinskiy and Don Stewart. ICFP 2007
>
> This is a drop-in replacement for Data.List.

Will it eventually replace Data.List in GHC?

Tom

--
Tom Schrijvers

Department of Computer Science
K.U. Leuven
Celestijnenlaan 200A
B-3001 Heverlee
Belgium

tel: +32 16 327544
e-mail: [hidden email]
url: http://www.cs.kuleuven.be/~toms/
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Stream fusion for Hackage

Don Stewart-2
Tom.Schrijvers:

> On Sat, 17 Nov 2007, Don Stewart wrote:
>
> >Just a quick announce: the stream fusion library for lists,
> >that Duncan Coutts, Roman Leshchinskiy and I worked on earlier this year
> >is now available on Hackage as a standalone package:
> >
> >   http://hackage.haskell.org/cgi-bin/hackage-scripts/package/stream-fusion-0.1.1
> >
> >As described in the recent paper:
> >
> >   "Stream Fusion: From Lists to Streams to Nothing at All"
> >   Duncan Coutts, Roman Leshchinskiy and Don Stewart. ICFP 2007
> >
> >This is a drop-in replacement for Data.List.
>
> Will it eventually replace Data.List in GHC?

That is the plan, yep.
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

RE: Stream fusion for Hackage

Simon Peyton Jones
| > Will it eventually replace Data.List in GHC?
|
| That is the plan, yep.

But first we need to solve the concatMap problem, no?

So far as I know, fold/build has the property that if fusion doesn't happen, no harm is done. But streams risk making the program *worse* if Good Things do not happen to happen.  This makes me anxious.

Simon

| -----Original Message-----
| From: [hidden email] [mailto:[hidden email]] On Behalf Of Don Stewart
| Sent: 18 November 2007 20:09
| To: Tom Schrijvers
| Cc: [hidden email]
| Subject: Re: [Haskell-cafe] Stream fusion for Hackage
|
| Tom.Schrijvers:
| > On Sat, 17 Nov 2007, Don Stewart wrote:
| >
| > >Just a quick announce: the stream fusion library for lists,
| > >that Duncan Coutts, Roman Leshchinskiy and I worked on earlier this year
| > >is now available on Hackage as a standalone package:
| > >
| > >   http://hackage.haskell.org/cgi-bin/hackage-scripts/package/stream-fusion-0.1.1
| > >
| > >As described in the recent paper:
| > >
| > >   "Stream Fusion: From Lists to Streams to Nothing at All"
| > >   Duncan Coutts, Roman Leshchinskiy and Don Stewart. ICFP 2007
| > >
| > >This is a drop-in replacement for Data.List.
| >
| > Will it eventually replace Data.List in GHC?
|
| That is the plan, yep.
| _______________________________________________
| Haskell-Cafe mailing list
| [hidden email]
| http://www.haskell.org/mailman/listinfo/haskell-cafe
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Stream fusion for Hackage

David Roundy-2
In reply to this post by Don Stewart-2
On Sat, Nov 17, 2007 at 06:31:08PM -0800, Don Stewart wrote:
> Just a quick announce: the stream fusion library for lists,
> that Duncan Coutts, Roman Leshchinskiy and I worked on earlier this year
> is now available on Hackage as a standalone package:

Just to note: I'm excited about one day using this with darcs.  Right now
we're using (in the unstable branch) our own list type so we can use type
witnesses.  I look forward to making this as efficient as the built-in
lists (or more efficient?) one of these days... (and I've no suggestions on
the namespace question).
--
David Roundy
Department of Physics
Oregon State University
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Stream fusion for Hackage

Don Stewart-2
In reply to this post by Simon Peyton Jones


simonpj:
> | > Will it eventually replace Data.List in GHC?
> |
> | That is the plan, yep.
>
> But first we need to solve the concatMap problem, no?
>
> So far as I know, fold/build has the property that if fusion doesn't happen, no harm is done. But streams risk making the program *worse* if Good Things do not happen to happen.  This makes me anxious.
>
> Simon

Yep, me too. We'll be using it in ByteString and other strict arrays
first, where the issues are much simpler, then looking at what can be
done with lists.

-- Don
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Fun with Cabal on Windows! [Stream fusion for Hackage]

Andrew Coppin
In reply to this post by Don Stewart-2
Don Stewart wrote:

> Just a quick announce: the stream fusion library for lists,
> that Duncan Coutts, Roman Leshchinskiy and I worked on earlier this year
> is now available on Hackage as a standalone package:
>
>     http://hackage.haskell.org/cgi-bin/hackage-scripts/package/stream-fusion-0.1.1
>
> As described in the recent paper:
>
>     "Stream Fusion: From Lists to Streams to Nothing at All"
>     Duncan Coutts, Roman Leshchinskiy and Don Stewart. ICFP 2007
>
> This is a drop-in replacement for Data.List.
>  

Well, I just tried to install this, and as per usual, Cabal has having
none of it.

C:\fusion\> runhaskell Setup configure
Configuring stream-fusion-0.1.1...
Setup: ld is required but it could not be found.

Well, no, this is Windoze, we don't have ld here...

On the other hand... hold on, doesn't GHC use GCC and ld?

On closer inspection, it seems that there *is* an LD.EXE on my
harddrive. Cabal is simply failing to find it. Great.

It turns out, the standard GHC installer automatically adds
C:\ghc\ghc-6.8.1.\bin to the search path. This contains GHC.EXE (and
other things), but LD.EXE and friends aren't in there. Those are found
in C:\ghc\ghc-6.8.1\gcc-lib. If you temporarily add *that* to your path...

C:\fusion\> set PATH=%PATH%;C:\ghc\ghc-6.8.1\gcc-lib
C:\fusion\> runhaskell Setup configure
Configuring stream-fusion-0.1.1...

C:\fusion\> runhaskell Setup build
Preprocessing library stream-fusion-0.1.1...
Building stream-fusion-0.1.1...
[1 of 3] Compiling Data.Stream      ( Data/Stream.hs,
dist\build/Data/Stream.o )


Data/Stream.hs:585:4:
    Warning: Pattern match(es) are non-exhaustive
             In the definition of `next':
                 Patterns not matched: (_ :!: (Just (L _))) :!: S2
[2 of 3] Compiling Data.List.Stream ( Data/List/Stream.hs,
dist\build/Data/List/Stream.o )
[3 of 3] Compiling Control.Monad.Stream ( Control/Monad/Stream.hs,
dist\build/Control/Monad/Stream.o )
C:\ghc\ghc-6.8.1\bin\ar.exe: creating dist\build\libHSstream-fusion-0.1.1.a

C:\fusion\> runhaskell Cabal install
Installing: C:\Program Files\Haskell\stream-fusion-0.1.1\ghc-6.8.1
Registering stream-fusion-0.1.1...
Reading package info from "dist\\installed-pkg-config" ... done.
Saving old package config file... done.
Writing new package config file... done.

OH...MY...GOD... I just successfully installed my first *ever* Cabal
package! o_O

[I haven't tried to compile anything using it yet. But ghc-pkg seems to
report that it's all in there just fine...]

I'm posting this information just in case any other poor soul on Windows
wants to try to install stuff with Cabal. It seems that if you simply
install GHC, it installs Cabal too, and adds GHC to your searchpath, and
yet Cabal won't find ld out of the box. (Surely that can't be correct?)
However, just by temporarily altering the search path (you don't even
have to do it permanently) you can fix it. At least, for this particular
package it fixes it...

PS. Somebody suggested configure --with-ld=PATH. This didn't work at all...

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Fun with Cabal on Windows! [Stream fusion for Hackage]

Thomas Schilling-2
On Mon, 2007-11-19 at 20:29 +0000, Andrew Coppin wrote:

> Don Stewart wrote:
> > Just a quick announce: the stream fusion library for lists,
> > that Duncan Coutts, Roman Leshchinskiy and I worked on earlier this year
> > is now available on Hackage as a standalone package:
> >
> >     http://hackage.haskell.org/cgi-bin/hackage-scripts/package/stream-fusion-0.1.1
> >
> > As described in the recent paper:
> >
> >     "Stream Fusion: From Lists to Streams to Nothing at All"
> >     Duncan Coutts, Roman Leshchinskiy and Don Stewart. ICFP 2007
> >
> > This is a drop-in replacement for Data.List.
> >  
>
> Well, I just tried to install this, and as per usual, Cabal has having
> none of it.
>
> C:\fusion\> runhaskell Setup configure
> Configuring stream-fusion-0.1.1...
> Setup: ld is required but it could not be found.
>
> Well, no, this is Windoze, we don't have ld here...
>
> On the other hand... hold on, doesn't GHC use GCC and ld?
>
> On closer inspection, it seems that there *is* an LD.EXE on my
> harddrive. Cabal is simply failing to find it. Great.
>
> It turns out, the standard GHC installer automatically adds
> C:\ghc\ghc-6.8.1.\bin to the search path. This contains GHC.EXE (and
> other things), but LD.EXE and friends aren't in there. Those are found
> in C:\ghc\ghc-6.8.1\gcc-lib. If you temporarily add *that* to your path...
>
> C:\fusion\> set PATH=%PATH%;C:\ghc\ghc-6.8.1\gcc-lib
> C:\fusion\> runhaskell Setup configure
> Configuring stream-fusion-0.1.1...

Hm, this actually is supposed to work.  Could you please re-run this
procedure with the original path and with maximum verbosity?  I.e.:

  > runhaskell Setup configure -v3

In any case though, if you have problems with Cabal or cabal-install,
send a bug report -- Windows might not be number one priority (since
most of the developers don't use it (often)) don't expect us to fix bugs
that we don't know about.  (Naturally.)

Thanks,

/ Thomas

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Fun with Cabal on Windows! [Stream fusion for Hackage]

Radosław Grzanka-2
Hi,

I have same problem.

> Hm, this actually is supposed to work.  Could you please re-run this
> procedure with the original path and with maximum verbosity?  I.e.:
>
>   > runhaskell Setup configure -v3

Here is the problem:

D:\private\haskell\MaybeT-0.1.0>runghc Setup.hs configure -v3
Configuring MaybeT-0.1.0...
Creating dist (and its parents)
C:\ghc\ghc-6.8.1\bin\ghc.exe --numeric-version
looking for package tool: ghc-pkg near compiler in C:\ghc\ghc-6.8.1\bin
found package tool in C:\ghc\ghc-6.8.1\bin\ghc-pkg.exe
C:\ghc\ghc-6.8.1\bin\ghc-pkg.exe --version
Setup.hs: ld is required but it could not be found.

I took a liberty of filing this in bug report for cabal.
http://hackage.haskell.org/trac/hackage/ticket/182

Thanks,
  Radek.

--
Codeside: http://codeside.org/
Przedszkole Miejskie nr 86 w Lodzi: http://www.pm86.pl/
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Fun with Cabal on Windows! [Stream fusion for Hackage]

Olivier Boudry
In reply to this post by Andrew Coppin
On 11/19/07, Andrew Coppin <[hidden email]> wrote:
Well, I just tried to install this, and as per usual, Cabal has having
none of it.

C:\fusion\> runhaskell Setup configure
Configuring stream-fusion-0.1.1...
Setup: ld is required but it could not be found.

Hi Andrew,

I had the same problem with ghc-6.8.1 and solved it by adding C:\ghc\ghc-6.8.1\gcc-lib to my PATH variable in environment variables. A copy of ld.exe is in this directory.

In ghc-6.6.1, ld.exe was in the same place and it was working out of the box for me. I don't understand why it is not found any more with ghc-6.8.1.

Cheers,

Olivier.

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Fun with Cabal on Windows! [Stream fusion for Hackage]

Duncan Coutts
On Tue, 2007-11-20 at 10:35 -0500, Olivier Boudry wrote:

> On 11/19/07, Andrew Coppin <[hidden email]> wrote:
>         Well, I just tried to install this, and as per usual, Cabal
>         has having
>         none of it.
>        
>         C:\fusion\> runhaskell Setup configure
>         Configuring stream-fusion-0.1.1...
>         Setup: ld is required but it could not be found.
>
> Hi Andrew,
>
> I had the same problem with ghc-6.8.1 and solved it by adding C:\ghc
> \ghc-6.8.1\gcc-lib to my PATH variable in environment variables. A
> copy of ld.exe is in this directory.
>
> In ghc-6.6.1, ld.exe was in the same place and it was working out of
> the box for me. I don't understand why it is not found any more with
> ghc-6.8.1.

It turned out that it was a bug that was introduced in Cabal shortly
before the release that went with ghc-6.8.1. We added an extra test to
check if ld supports the -x flag. This change inadvertently broke the
code that finds ld on windows. I can tell you more of the gory details
if you care :-). It's fixed now and will be in the release that goes
with ghc 6.8.2.

Duncan
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe