chicken-hackers
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [Chicken-hackers] csc -profile has problems


From: Peter Bex
Subject: Re: [Chicken-hackers] csc -profile has problems
Date: Fri, 18 Mar 2016 20:51:16 +0100
User-agent: Mutt/1.5.21 (2010-09-15)

On Sat, Mar 05, 2016 at 05:20:42PM +0100, Peter Bex wrote:
> I have whittled it down to a minimal test case:
> 
> (module comparators (in-order? swapped?)
>   (import chicken scheme)
>   (: comparator-says-yes? (* * * --> boolean))
>   (define (comparator-says-yes? comparator a b) (comparator a b))
>   (define (swapped? comparator a b) (comparator-says-yes? comparator b a))
>   (define (in-order? comparator a b) (comparator-says-yes? comparator a b)))
> 
> Interestingly, if you remove the definition of swapped? or in-order?, it
> works.  And if you remove the type declaration, it also works.  Likely
> it's an interaction between the optimizer and the scrutinizer.

I've figured out the cause!  The "-->" part of the type is the culprit
because it declares the procedure to be pure, which triggers prevents
the proper code path from being taken in the compiler.  It's rather
hairy, but I'll attempt to explain this.

When a hidden(!) procedure has a rest argument, it will get optimised so
it accepts one additional argument _instead of_ the rest arguments.  This
should be the pre-allocated rest list.  The callers are then modified so
they cons the rest argument instead of the callee.

So for example:

(define (foo x . y) (apply + x y))
(bar 1 2)

will get compiled to:

(define (foo x y) (apply + x y))
(bar 1 (list 2))

When you run -debug o, this will be shown as "merged explicitly consed
rest parameter" for the callee, and "consed rest parameter at call site"
for each caller.  If you compile the simplified test case I quoted in my
previous mail, with and without the type declaration using "-debug o"
and you watch the output, there's one glaring difference: the version
with type declaration will only show the "merged explicitly consed rest
parameter" (for the callee), and not the call sites.

comparator-says-yes? is not exported here and called in two places.
If it is called in only one place, it will be inlined, which means the
problem doesn't crop up.  If comparator-says-yes? would be exported, the
procedure's arguments can't be tweaked so the problem doesn't occur either.

Attached is a patch to fix the problem: The old code would detect the
purity of comparator-says-yes (due to the type declaration) and then
do a greedy grab of the node, and try to drop it.  If it couldn't drop
it, it would just recurse without ever applying any other optimisations
like the consing of the callee's rest list (and potentially this means
we had lost some other optimisation opportunities for other cases too).

The patch simply lifts the first part to the surrounding cond, so the
next optimisation will be attempted if any of the and-let* components
turn out to be #f, instead of just falling back to a recursive call to
"walk" on the sub-expressions.

I'm not 100% happy with how this works: the consing of the callee rest
lists is strictly speaking *not* an optimisation: the optimisation is
the fact that the caller can be replaced like that.  I think the callers
should be changed right away when this is determined.  However, that
would (probably?) be a very big and dangerous change.

The attached patch also includes a test that triggers the case in an
unpatched compiler.  But this is pretty brittle, as it relies on
specifics of the current implementation like that it decides not to
inline this particular procedure if it's called in two places.

Ah well, better than no tests at all, I suppose.

Cheers,
Peter

Attachment: 0001-Don-t-shortcut-pure-calls-in-the-optimiser.patch
Description: Text Data

Attachment: signature.asc
Description: Digital signature


reply via email to

[Prev in Thread] Current Thread [Next in Thread]