LFVM-STG Compilation

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

LFVM-STG Compilation

james faure
Hello,
I want to introduce the STG backend I am currently working on:
I'd love to see how much interest there is for this, to receive any comments, and find out if I've missed anything !

The goal is to massively speed up compilation times and generate faster and clearer code, and in that respect I am already quite successful. Llvm is very well suited for encoding a (lazy) functional language, however the evaluation mechanism is very different to ghc's stg, there is notably no continuation passing nor result registers. In LFVM, all non constant let bindings are given an llvm function. I believe this approach is more natural, the llvm more accurately reflects the source code and we get proper stack traces in a debugger.

Status:
The project is barely a month old, and I'm working to support everything ghc's code generation supports.
The STG is heavily based on the one found in ghc and, at this time and as far as I can tell, supports everything except multithreading, a gc and lazy evaluation. The current idea I think is very promising is to use an inferred pi calculus to elegantly implement all 3 missing parts at once.

Pi calculus [1] (process calculus) In the STG
  • Multithreading occurs for arguments of functions with >1 arity
  • Perfect garbage collection is quite probably possible [2], where allocation creates a new pi name, and its uses are modeled by pi calculus communication
  • Perfect Lazy evaluation (in the sense that the wrapper and associated wrapped type overhead is coerced away after the first evaluation) is possible in the pi calculus and closely linked the gc model. I intend to make strict evaluation the default, If you want lazy (for MonadFix or infinite lists or whatever), you must request it.

James Faure (Discord: J4#0303)


_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.
Reply | Threaded
Open this post in threaded view
|

Re: LFVM-STG Compilation

Bryan Richter-2
Speeding up compile times would be excellent! Do you have benchmarks? Estimates?

ZuriHac is coming up, and I want to devote my participation time to improving ghc's usability, one way or another. Improving compile times would be the best usability boon I can think of. If there is promise in this project, I'd like to learn about any way I could help out.


On Thu, 9 May 2019, 15.54 james faure, <[hidden email]> wrote:
Hello,
I want to introduce the STG backend I am currently working on:
I'd love to see how much interest there is for this, to receive any comments, and find out if I've missed anything !

The goal is to massively speed up compilation times and generate faster and clearer code, and in that respect I am already quite successful. Llvm is very well suited for encoding a (lazy) functional language, however the evaluation mechanism is very different to ghc's stg, there is notably no continuation passing nor result registers. In LFVM, all non constant let bindings are given an llvm function. I believe this approach is more natural, the llvm more accurately reflects the source code and we get proper stack traces in a debugger.

Status:
The project is barely a month old, and I'm working to support everything ghc's code generation supports.
The STG is heavily based on the one found in ghc and, at this time and as far as I can tell, supports everything except multithreading, a gc and lazy evaluation. The current idea I think is very promising is to use an inferred pi calculus to elegantly implement all 3 missing parts at once.

Pi calculus [1] (process calculus) In the STG
  • Multithreading occurs for arguments of functions with >1 arity
  • Perfect garbage collection is quite probably possible [2], where allocation creates a new pi name, and its uses are modeled by pi calculus communication
  • Perfect Lazy evaluation (in the sense that the wrapper and associated wrapped type overhead is coerced away after the first evaluation) is possible in the pi calculus and closely linked the gc model. I intend to make strict evaluation the default, If you want lazy (for MonadFix or infinite lists or whatever), you must request it.

James Faure (Discord: J4#0303)

_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.

_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.
Reply | Threaded
Open this post in threaded view
|

Re: LFVM-STG Compilation

Viktor Dukhovni
In reply to this post by james faure
On Thu, May 09, 2019 at 12:54:01PM +0000, james faure wrote:

> Pi calculus [1] (process calculus) In the STG
>
>   *   Multithreading occurs for arguments of functions with >1 arity
>
>   *   Perfect garbage collection is quite probably possible [2], where
>       allocation creates a new pi name, and its uses are modeled by pi calculus
>       communication
>
>   *   Perfect Lazy evaluation (in the sense that the wrapper and associated
>       wrapped type overhead is coerced away after the first evaluation) is
>       possible in the pi calculus and closely linked the gc model. I intend
>       to make strict evaluation the default, If you want lazy (for MonadFix
>       or infinite lists or whatever), you must request it.

The ideas sound very interesting, but could you elaborate on the
"strict by default" aspect?  Who's the "you" who'd have to request
lazy evaluation?  Is this something internal to the compiler with
strictness analysis generating the "requests" internally, or would
all existing application and library code that expects lazy evaluation
need to be updated with explicit laziness annotations?

--
        Viktor.
_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.
Reply | Threaded
Open this post in threaded view
|

Re: LFVM-STG Compilation

james faure
Haskell has the '~' and '!' that can be used to specify strictness of constructor parameters, If nothing is given lfvm will assume '!'. It's worth noting that it's not always easy to tell when laziness can pay off, the classic example of 'take 3 . sort' being something that benefits from lazy evaluation. Perhaps cases like these can be resolved by marking 'take' as preferring lazy lists.

So yes, This strict by default approach probably means some library code will need to be updated to avoid unnecessarily forcing huge lists to be evaluated, although I don't think the effects will be that massive, for lists I can't think of many functions besides 'take' and 'head' that don't need the whole list. Besides the vast majority of the time I would assume one uses all the data one creates. In the above example, you're relying on sort to operate in a certain way - if it uses a bubble sort for example, then that's unfortunate.

From: Haskell-Cafe <[hidden email]> on behalf of Viktor Dukhovni <[hidden email]>
Sent: Thursday, May 9, 2019 7:40 PM
To: [hidden email]
Subject: Re: [Haskell-cafe] LFVM-STG Compilation
 
On Thu, May 09, 2019 at 12:54:01PM +0000, james faure wrote:

> Pi calculus [1] (process calculus) In the STG
>
>   *   Multithreading occurs for arguments of functions with >1 arity
>
>   *   Perfect garbage collection is quite probably possible [2], where
>       allocation creates a new pi name, and its uses are modeled by pi calculus
>       communication
>
>   *   Perfect Lazy evaluation (in the sense that the wrapper and associated
>       wrapped type overhead is coerced away after the first evaluation) is
>       possible in the pi calculus and closely linked the gc model. I intend
>       to make strict evaluation the default, If you want lazy (for MonadFix
>       or infinite lists or whatever), you must request it.

The ideas sound very interesting, but could you elaborate on the
"strict by default" aspect?  Who's the "you" who'd have to request
lazy evaluation?  Is this something internal to the compiler with
strictness analysis generating the "requests" internally, or would
all existing application and library code that expects lazy evaluation
need to be updated with explicit laziness annotations?

--
        Viktor.
_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.

_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.
Reply | Threaded
Open this post in threaded view
|

Re: LFVM-STG Compilation

Theodore Lief Gannon
Do not underestimate the repercussions of strict-by-default. I have quite a bit of production code which would bottom out (or at best *massively* over-allocate) without pervasive laziness.

On Thu, May 9, 2019, 11:11 AM james faure <[hidden email]> wrote:
Haskell has the '~' and '!' that can be used to specify strictness of constructor parameters, If nothing is given lfvm will assume '!'. It's worth noting that it's not always easy to tell when laziness can pay off, the classic example of 'take 3 . sort' being something that benefits from lazy evaluation. Perhaps cases like these can be resolved by marking 'take' as preferring lazy lists.

So yes, This strict by default approach probably means some library code will need to be updated to avoid unnecessarily forcing huge lists to be evaluated, although I don't think the effects will be that massive, for lists I can't think of many functions besides 'take' and 'head' that don't need the whole list. Besides the vast majority of the time I would assume one uses all the data one creates. In the above example, you're relying on sort to operate in a certain way - if it uses a bubble sort for example, then that's unfortunate.

From: Haskell-Cafe <[hidden email]> on behalf of Viktor Dukhovni <[hidden email]>
Sent: Thursday, May 9, 2019 7:40 PM
To: [hidden email]
Subject: Re: [Haskell-cafe] LFVM-STG Compilation
 
On Thu, May 09, 2019 at 12:54:01PM +0000, james faure wrote:

> Pi calculus [1] (process calculus) In the STG
>
>   *   Multithreading occurs for arguments of functions with >1 arity
>
>   *   Perfect garbage collection is quite probably possible [2], where
>       allocation creates a new pi name, and its uses are modeled by pi calculus
>       communication
>
>   *   Perfect Lazy evaluation (in the sense that the wrapper and associated
>       wrapped type overhead is coerced away after the first evaluation) is
>       possible in the pi calculus and closely linked the gc model. I intend
>       to make strict evaluation the default, If you want lazy (for MonadFix
>       or infinite lists or whatever), you must request it.

The ideas sound very interesting, but could you elaborate on the
"strict by default" aspect?  Who's the "you" who'd have to request
lazy evaluation?  Is this something internal to the compiler with
strictness analysis generating the "requests" internally, or would
all existing application and library code that expects lazy evaluation
need to be updated with explicit laziness annotations?

--
        Viktor.
_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.
_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.

_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.
Reply | Threaded
Open this post in threaded view
|

Re: LFVM-STG Compilation

Brandon Allbery
The same is true of the Prelude. You might want to look at what's happened with -XStrict and even -XStrictData. Both end up meaning you replace or rewrite a bunch of library functions, because lots of things rely on laziness either for memory usage or to avoid bottoms.

In short, if you are still talking about Haskell, default-strict isn't an option. A strict Haskell-*like* language is an option, but it won't be Haskell; its idioms will be different and library compatibility will be dubious at best.

On Thu, May 9, 2019 at 5:22 PM Theodore Lief Gannon <[hidden email]> wrote:
Do not underestimate the repercussions of strict-by-default. I have quite a bit of production code which would bottom out (or at best *massively* over-allocate) without pervasive laziness.

On Thu, May 9, 2019, 11:11 AM james faure <[hidden email]> wrote:
Haskell has the '~' and '!' that can be used to specify strictness of constructor parameters, If nothing is given lfvm will assume '!'. It's worth noting that it's not always easy to tell when laziness can pay off, the classic example of 'take 3 . sort' being something that benefits from lazy evaluation. Perhaps cases like these can be resolved by marking 'take' as preferring lazy lists.

So yes, This strict by default approach probably means some library code will need to be updated to avoid unnecessarily forcing huge lists to be evaluated, although I don't think the effects will be that massive, for lists I can't think of many functions besides 'take' and 'head' that don't need the whole list. Besides the vast majority of the time I would assume one uses all the data one creates. In the above example, you're relying on sort to operate in a certain way - if it uses a bubble sort for example, then that's unfortunate.

From: Haskell-Cafe <[hidden email]> on behalf of Viktor Dukhovni <[hidden email]>
Sent: Thursday, May 9, 2019 7:40 PM
To: [hidden email]
Subject: Re: [Haskell-cafe] LFVM-STG Compilation
 
On Thu, May 09, 2019 at 12:54:01PM +0000, james faure wrote:

> Pi calculus [1] (process calculus) In the STG
>
>   *   Multithreading occurs for arguments of functions with >1 arity
>
>   *   Perfect garbage collection is quite probably possible [2], where
>       allocation creates a new pi name, and its uses are modeled by pi calculus
>       communication
>
>   *   Perfect Lazy evaluation (in the sense that the wrapper and associated
>       wrapped type overhead is coerced away after the first evaluation) is
>       possible in the pi calculus and closely linked the gc model. I intend
>       to make strict evaluation the default, If you want lazy (for MonadFix
>       or infinite lists or whatever), you must request it.

The ideas sound very interesting, but could you elaborate on the
"strict by default" aspect?  Who's the "you" who'd have to request
lazy evaluation?  Is this something internal to the compiler with
strictness analysis generating the "requests" internally, or would
all existing application and library code that expects lazy evaluation
need to be updated with explicit laziness annotations?

--
        Viktor.
_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.
_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.
_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.


--
brandon s allbery kf8nh

_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.
Reply | Threaded
Open this post in threaded view
|

Re: LFVM-STG Compilation

Viktor Dukhovni
> On May 9, 2019, at 6:04 PM, Brandon Allbery <[hidden email]> wrote:
>
> In short, if you are still talking about Haskell, default-strict isn't an option. A strict Haskell-*like* language is an option, but it won't be Haskell; its idioms will be different and library compatibility will be dubious at best.

That's my take too.  Lazy by default pervades the language, and strict
by default simply is not Haskell.  There are some modules where I can
get away with and may benefit from "{-# LANGUAGE Strict #-}", but the
default must remain lazy.  Code I write implicitly depends on default
lazy behaviour, and rewriting it all is not an option.  At that point
I'd be using Rust or some other language...

--
        Viktor.

_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.
Reply | Threaded
Open this post in threaded view
|

Re: LFVM-STG Compilation

Sven Panne-2
In reply to this post by Brandon Allbery
Am Fr., 10. Mai 2019 um 00:05 Uhr schrieb Brandon Allbery <[hidden email]>:
[...] In short, if you are still talking about Haskell, default-strict isn't an option. A strict Haskell-*like* language is an option, but it won't be Haskell; its idioms will be different and library compatibility will be dubious at best.

+1. I think one (quite old) point has been missed so far in this discussion: "Strict evaluation is fundamentally flawed for function reuse.", see http://augustss.blogspot.com/2011/05/.

_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.