thoughts on peval

thoughts on peval

[Andy Wingo]

Hi,

I was playing around with peval early this morning -- yay jetlag -- and
had some notes I'd like to share.

Firstly, I added a let-values inliner to peval.  It was fairly pleasant
to write.  It can do things like:

(let ((x 0))
  (call-with-values
      (lambda () (if (zero? x) (values 1 2) (values 3 4)))
    (lambda (a b)
      (+ a b))))
=> 3

By that I mean to say that it inlines to 3, at compile time.  Good
times!  Goes to show that peval is fairly flexible.

My goal is to have peval do well when compiling psyntax to produce
psyntax-pp.scm.  However it does not currently work -- the peval
aborts.  Looking into this issue, it seems that peval does not work for
any of our .scm files (!!!).  The reason for this is that the code that
looks to inline applications bails for a number of common procedure
types, including module-ref forms.  Module-refs are mostly produced by
macro expansion, such as the call to define-module* that starts most of
our .scm files.

I tried making peval leave module-ref calls alone, and it does let peval
proceed, but then things explode: since there is practically no
constraint on inlining, the code size and compilation time explodes.
Any call to a procedure whose definition is known is eligible for
inlining if any argument to the procedure is constant, including lambda
arguments, regardless of the size of the procedure being inlined.  It is
so bad that optimize.scm can't even compile itself, if you add a simple
clause for <module-ref> in the <application> block.

This concerns me a great deal.  We will need to work hard to
retain/regain O(N) compile times.  Before peval, compile times (with a
bootstrapped compiler) were roughly linear in program size.  If we
diverge too much now, we won't be able to compile large programs.

A short-term solution would be to add heuristics.  A more proper
solution would involve effort and size counters, as in the Waddell and
Dybvig paper.  It sounds doable.

Peval probably also needs to thread around some idea of the "context" --
whether an expression is in effect, value, test, or tail position.  This
can help enable additional optimizations.  It would help if peval were
demand-driven, as in that paper, so you would know in which context to
evaluate the operands; but, step by step.

Also, I think that peval is probably inlining too much, at least by
default.  By the time that code hits peval, all definitions in a file
are in one big <sequence>.  Peval assumes those definitions are static,
but that has not historically been the case.  At least by default, we
should only inline statically-bound definitions.

Finally I think that we should be more pragmatic regarding lexical
set!.  One set! should not abort optimization of an entire form.

I suppose the blockers for the next release would be the excessive
inlining thing.  We should also fix toplevel inlining.  Ludo, what do
you think?

Cheers,

Andy
-- 
http://wingolog.org/

Re: thoughts on peval

[Ludovic Courtès]

Hi Andy,

Thanks for taking the time to review the code, I greatly appreciate it!

Andy Wingo <wingo@pobox.com> skribis:

> (let ((x 0))
>   (call-with-values
>       (lambda () (if (zero? x) (values 1 2) (values 3 4)))
>     (lambda (a b)
>       (+ a b))))
> => 3

Ah, cool (which makes part of my previous message moot.)

> My goal is to have peval do well when compiling psyntax to produce
> psyntax-pp.scm.  However it does not currently work -- the peval
> aborts.  Looking into this issue, it seems that peval does not work for
> any of our .scm files (!!!).  The reason for this is that the code that
> looks to inline applications bails for a number of common procedure
> types, including module-ref forms.  Module-refs are mostly produced by
> macro expansion, such as the call to define-module* that starts most of
> our .scm files.

Oooh, ahem, good catch!

> I tried making peval leave module-ref calls alone, and it does let peval
> proceed, but then things explode: since there is practically no
> constraint on inlining, the code size and compilation time explodes.
> Any call to a procedure whose definition is known is eligible for
> inlining if any argument to the procedure is constant, including lambda
> arguments, regardless of the size of the procedure being inlined.

Well, top-level procedures aren’t inlined, right?

--8<---------------cut here---------------start------------->8---
scheme@(language tree-il optimize)> (define til (cut compile <> #:to 'tree-il))
scheme@(language tree-il optimize)> (peval (til '(begin (define (foo x) x) (define (bar x) (foo x)) (bar 2))))
$2 = #<tree-il (begin (define foo (lambda ((name . foo)) (lambda-case (((x) #f #f #f () (#{x 16303}#)) (lexical x #{x 16303}#))))) (define bar (lambda ((name . bar)) (lambda-case (((x) #f #f #f () (#{x 16301}#)) (apply (toplevel foo) (lexical x #{x 16301}#)))))) (apply (toplevel bar) (const 2)))>
--8<---------------cut here---------------end--------------->8---

So there must be something else going on?

> This concerns me a great deal.  We will need to work hard to
> retain/regain O(N) compile times.  Before peval, compile times (with a
> bootstrapped compiler) were roughly linear in program size.  If we
> diverge too much now, we won't be able to compile large programs.

Agreed.

> Also, I think that peval is probably inlining too much, at least by
> default.  By the time that code hits peval, all definitions in a file
> are in one big <sequence>.  Peval assumes those definitions are static,
> but that has not historically been the case.  At least by default, we
> should only inline statically-bound definitions.

This is not the case AFAICT–i.e., top-level definitions are *not*
eligible for inlining (this is a todo in optimize.scm and in my original
post.)

I was well aware of the risk of excessive inlining, but I thought that
this and the two other conditions to abort inlining would mitigate the
problem (the two other conditions being: any static args, and no
recursive calls in the residual code.)

> Finally I think that we should be more pragmatic regarding lexical
> set!.  One set! should not abort optimization of an entire form.

Sure.  My first approach was: let’s see if we can optimize common
functional idioms, and we’ll see later about imperative idioms, which
are much more difficult to handle.  Bailing out upon set! & co. was a
simple way to ensure peval wouldn’t do anything wrong with that code.

> I suppose the blockers for the next release would be the excessive
> inlining thing.  We should also fix toplevel inlining.  Ludo, what do
> you think?

I think you raise very good concerns, and I agree with the blockers.
However, there’s no top-level inlining AFAIK, so we should find out what
exactly goes wrong.

Thanks,
Ludo’.

Re: thoughts on peval

[Andy Wingo]

Hi,

On Wed 21 Sep 2011 11:31, ludo@gnu.org (Ludovic Courtès) writes:

> Well, top-level procedures aren’t inlined, right?
>
> scheme@(language tree-il optimize)> (define til (cut compile <> #:to 'tree-il))
> scheme@(language tree-il optimize)> (peval (til '(begin (define (foo x) x) (define (bar x) (foo x)) (bar 2))))
> $2 = #<tree-il (begin (define foo (lambda ((name . foo)) (lambda-case (((x) #f #f #f () (#{x 16303}#)) (lexical x #{x 16303}#))))) (define bar (lambda ((name . bar)) (lambda-case (((x) #f #f #f () (#{x 16301}#)) (apply (toplevel foo) (lexical x #{x 16301}#)))))) (apply (toplevel bar) (const 2)))>
>
> So there must be something else going on?

I mean top-level definitions in a file, not in a REPL.  In the REPL they
are compiled separately, whereas for a file, all the toplevel
expressions and definitions are compiled together in one <sequence>,
which currenyly allows them to be inlined (though, see below...)

>> Also, I think that peval is probably inlining too much, at least by
>> default.  By the time that code hits peval, all definitions in a file
>> are in one big <sequence>.  Peval assumes those definitions are static,
>> but that has not historically been the case.  At least by default, we
>> should only inline statically-bound definitions.
>
> This is not the case AFAICT–i.e., top-level definitions are *not*
> eligible for inlining (this is a todo in optimize.scm and in my original
> post.)

Ah, I see that now.  I assumed the local-toplevel-env was being used for
this purpose.  My mistake.

> I was well aware of the risk of excessive inlining, but I thought that
> this and the two other conditions to abort inlining would mitigate the
> problem (the two other conditions being: any static args, and no
> recursive calls in the residual code.)

Well, add a (($ <module-ref>) app) clause to that (match proc ...)
block, and trace what it's doing.  It's pretty crazy :)

Cheers,

Andy
-- 
http://wingolog.org/

Re: thoughts on peval

[Ludovic Courtès]

Hi!

Andy Wingo <wingo@pobox.com> skribis:

> On Wed 21 Sep 2011 11:31, ludo@gnu.org (Ludovic Courtès) writes:

[...]

>> I was well aware of the risk of excessive inlining, but I thought that
>> this and the two other conditions to abort inlining would mitigate the
>> problem (the two other conditions being: any static args, and no
>> recursive calls in the residual code.)
>
> Well, add a (($ <module-ref>) app) clause to that (match proc ...)
> block, and trace what it's doing.  It's pretty crazy :)

OK, will do!

Thanks,
Ludo’.

peval & let-values

[Ludovic Courtès]

[-- Attachment #1: Type: text/plain, Size: 421 bytes --]

Hi,

Andy Wingo <wingo@pobox.com> skribis:

> Firstly, I added a let-values inliner to peval.  It was fairly pleasant
> to write.  It can do things like:
>
> (let ((x 0))
>   (call-with-values
>       (lambda () (if (zero? x) (values 1 2) (values 3 4)))
>     (lambda (a b)
>       (+ a b))))
> => 3

This example doesn’t seem to work as is, presumably because
‘call-with-values’ doesn’t get “primitivized”:


[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: Type: text/x-patch, Size: 560 bytes --]

diff --git a/test-suite/tests/tree-il.test b/test-suite/tests/tree-il.test
index 63b74ad..0074aa0 100644
--- a/test-suite/tests/tree-il.test
+++ b/test-suite/tests/tree-il.test
@@ -621,6 +621,15 @@
     (const 3))
 
   (pass-if-peval
+    ;; First order, let-values.
+    (let ((x 0))
+      (call-with-values
+          (lambda () (if (zero? x) (values 1 2) (values 3 4)))
+        (lambda (a b)
+          (+ a b))))
+    (const 3))
+
+  (pass-if-peval
     ;; First order, coalesced.
     (cons 0 (cons 1 (cons 2 (list 3 4 5))))
     (const (0 1 2 3 4 5)))

[-- Attachment #3: Type: text/plain, Size: 10 bytes --]


Ludo’.

Re: peval & let-values

[Andy Wingo]

Hi,

On Wed 21 Sep 2011 15:28, ludo@gnu.org (Ludovic Courtès) writes:

> Andy Wingo <wingo@pobox.com> skribis:
>
>> (let ((x 0))
>>   (call-with-values
>>       (lambda () (if (zero? x) (values 1 2) (values 3 4)))
>>     (lambda (a b)
>>       (+ a b))))
>> => 3
>
> This example doesn’t seem to work as is, presumably because
> ‘call-with-values’ doesn’t get “primitivized”:

It does work at the REPL however, as primitives are resolved and
expanded before `peval' is run.

Andy
-- 
http://wingolog.org/