Re: GNU Guile branch, wip-peval-predicates, created. v2.0.5-100-g59c5570

Re: GNU Guile branch, wip-peval-predicates, created. v2.0.5-100-g59c5570

[Mark H Weaver]

Hi Andy,

> commit 59c557056cff1ce6146b4d689eeee922300b6278
> Author: Andy Wingo <wingo-e+AXbWqSrlAAvxtiuMwx3w@public.gmane.org>
> Date:   Tue Apr 10 15:56:23 2012 -0700
>
>     peval: elide redundant predicates; eliminate some common subexpressions
>     
>     * module/language/tree-il/peval.scm (fold-constants): Returns #f instead
>       of the expression, as all continuations handle #f themselves.
>       (negate, bailout?, extract-facts, infer, infer-defined?)
>       (infer-struct-vtable): New helpers.

I haven't looked at the code, but it sounds like you are trying to
eliminate redundant 'struct-vtable' checks.  Unfortunately, it seems to
me that this cannot be done safely.  In practice, the checks look like:

  (eq? (struct-vtable s) <foo>)

Both of the values being compared here are fetched from mutable
locations.  The 'struct-vtable' field is mutable, and <foo> is usually a
top-level variable that is also mutable.  Furthermore, both of these
things are mutated in practice when a GOOPS class is redefined, IIUC.

Am I missing something?

    Thanks,
      Mark

Re: GNU Guile branch, wip-peval-predicates, created. v2.0.5-100-g59c5570

[Noah Lavine]

At first I thought you were right. But then I realized there's an even
deeper problem here. Imagine implementing a record mutator like this:

(define (set-foo-a! foo new-value)
  (if (is-foo? foo)
     (%unsafe-set-foo-a! foo new-value)
     (error)))

That code is incorrect, by the same logic you used: something could
change the class of foo in between the is-foo? call and the
%unsafe-set-foo-a! call. You need some atomic check-and-set operation
in order to do this safely.

Unfortunately, I don't see a correct way short of some sort of mutex.
A mutex for each record would be a lot of overhead, but what about a
mutex per class, that has to be acquired to change any instance of the
class to or from a different class? Changing a class is a rare enough
operation that we should not optimize for it, I think. Also, if we had
such a mutex, we could use it to eliminate redundant struct-vtable
checks correctly, by acquiring it at the beginning of a function and
releasing it at the end.

I'm somewhat afraid, however, that the real solution is changing how
we deal with parallelism, and that is a much bigger problem.

Noah

On Fri, Apr 13, 2012 at 10:22 AM, Mark H Weaver <mhw@netris.org> wrote:
> Hi Andy,
>
>> commit 59c557056cff1ce6146b4d689eeee922300b6278
>> Author: Andy Wingo <wingo-e+AXbWqSrlAAvxtiuMwx3w@public.gmane.org>
>> Date:   Tue Apr 10 15:56:23 2012 -0700
>>
>>     peval: elide redundant predicates; eliminate some common subexpressions
>>
>>     * module/language/tree-il/peval.scm (fold-constants): Returns #f instead
>>       of the expression, as all continuations handle #f themselves.
>>       (negate, bailout?, extract-facts, infer, infer-defined?)
>>       (infer-struct-vtable): New helpers.
>
> I haven't looked at the code, but it sounds like you are trying to
> eliminate redundant 'struct-vtable' checks.  Unfortunately, it seems to
> me that this cannot be done safely.  In practice, the checks look like:
>
>  (eq? (struct-vtable s) <foo>)
>
> Both of the values being compared here are fetched from mutable
> locations.  The 'struct-vtable' field is mutable, and <foo> is usually a
> top-level variable that is also mutable.  Furthermore, both of these
> things are mutated in practice when a GOOPS class is redefined, IIUC.
>
> Am I missing something?
>
>    Thanks,
>      Mark
>

Re: GNU Guile branch, wip-peval-predicates, created. v2.0.5-100-g59c5570

[Ludovic Courtès]

Noah Lavine <noah.b.lavine@gmail.com> skribis:

> I'm somewhat afraid, however, that the real solution is changing how
> we deal with parallelism, and that is a much bigger problem.

And this is where functional setters come in.  ;-)

Ludo’.

Re: GNU Guile branch, wip-peval-predicates, created. v2.0.5-100-g59c5570

[Noah Lavine]

On Fri, Apr 13, 2012 at 3:59 PM, Ludovic Courtès <ludo@gnu.org> wrote:
> Noah Lavine <noah.b.lavine@gmail.com> skribis:
>
>> I'm somewhat afraid, however, that the real solution is changing how
>> we deal with parallelism, and that is a much bigger problem.
>
> And this is where functional setters come in.  ;-)

Yes, functional data structures solve this. But the trouble is that
you can't take advantage of this to generate better code unless your
compiler knows that you will never mutate certain variables. Maybe you
could put something together with lots of caching code and
invalidating it if the assumptions change.

Noah

Re: GNU Guile branch, wip-peval-predicates, created. v2.0.5-100-g59c5570

[Andy Wingo]

Hi,

On Fri 13 Apr 2012 07:22, Mark H Weaver <mhw@netris.org> writes:

>>     * module/language/tree-il/peval.scm (fold-constants): Returns #f instead
>>       of the expression, as all continuations handle #f themselves.
>>       (negate, bailout?, extract-facts, infer, infer-defined?)
>>       (infer-struct-vtable): New helpers.
>
> I haven't looked at the code, but it sounds like you are trying to
> eliminate redundant 'struct-vtable' checks.  Unfortunately, it seems to
> me that this cannot be done safely.

The identity of the vtable does not change when it is redefined.  If the
vtable is redefined, the equality check still succeeds.  There are
comments in the source.

In the end though, that branch is turning into a more general effects
analysis + CSE pass, for which I'll push a different branch shortly.

Regards,

Andy
-- 
http://wingolog.org/

Re: GNU Guile branch, wip-peval-predicates, created. v2.0.5-100-g59c5570

[Mark H Weaver]

Hi Andy,

Andy Wingo <wingo@pobox.com> writes:
> On Fri 13 Apr 2012 07:22, Mark H Weaver <mhw@netris.org> writes:
>>>     * module/language/tree-il/peval.scm (fold-constants): Returns #f instead
>>>       of the expression, as all continuations handle #f themselves.
>>>       (negate, bailout?, extract-facts, infer, infer-defined?)
>>>       (infer-struct-vtable): New helpers.
>>
>> I haven't looked at the code, but it sounds like you are trying to
>> eliminate redundant 'struct-vtable' checks.  Unfortunately, it seems to
>> me that this cannot be done safely.
>
> The identity of the vtable does not change when it is redefined.  If the
> vtable is redefined, the equality check still succeeds.  There are
> comments in the source.

Okay, I've just reread:

  http://wingolog.org/archives/2009/11/09/class-redefinition-in-guile

and I see that I had some misconceptions about this.  Point taken: when
a class is redefined, the result of 'struct-vtable' on the instances
remain the same.

Nonetheless, the vtable checks involve comparisons with a mutable
top-level variable.  Whenever unknown code is run (e.g. when a top-level
procedure is called) you must assume the worst: that any top-level
variable might have been 'set!'.

    Regards,
      Mark

Re: GNU Guile branch, wip-peval-predicates, created. v2.0.5-100-g59c5570

[Andy Wingo]

Hi,

On Fri 13 Apr 2012 10:07, Mark H Weaver <mhw@netris.org> writes:

> Nonetheless, the vtable checks involve comparisons with a mutable
> top-level variable.  Whenever unknown code is run (e.g. when a top-level
> procedure is called) you must assume the worst: that any top-level
> variable might have been 'set!'.

You probably saw, but wip-cse does effects analysis to prove that the
toplevel hasn't been set! by intervening expressions.

There is of course the question of what optimizations like this may be
made in the presence of concurrently executing threads.  For example, in
wip-cse the following expression folds:

  (if (eq? x y) (eq? x y) #f) => (eq? x y)

This is because there was no toplevel-set! in between the first and
second checks.  The possible side effects of referencing X or Y would
happen on the first check or not at all, so the second expression can
cause no effects.  (If CSE sees a call to an unknown procedure, it's
assumed that it can cause any effect, and thus such a call does not
commute with anything but a "constant" expression.)

But OK, the question here is, what if another thread is concurrently
mutating X and Y?  If this were C++ or Java, the answer would be that
they can still fold, because access to a multithreaded mutable needs to
be synchronized.  I think this is reasonable.  What do you think?

Andy
-- 
http://wingolog.org/

Re: GNU Guile branch, wip-peval-predicates, created. v2.0.5-100-g59c5570

[David Kastrup]

Andy Wingo <wingo@pobox.com> writes:

> But OK, the question here is, what if another thread is concurrently
> mutating X and Y?  If this were C++ or Java, the answer would be that
> they can still fold, because access to a multithreaded mutable needs
> to be synchronized.  I think this is reasonable.  What do you think?

You don't even need multithreading for undefined effects of sequence
ordering in C/C++.

  i = i++;

is already undefined.  Scheme has several non-guarantees regarding
execution order as well (like the order in which function arguments will
get evaluated).

History time: Fortran specifies that if array arguments to a function do
not point to distinct objects, the results are undefined.  C passes
arrays (actually, vectors) using pointers, and a pointer is a memory
reference that can point anywhere in an array, and there are no
restrictions about the same-object relations (whether at the same
address or with an offset) of several arguments: the behavior is
well-defined either way.

The C99 standard or whatever it was allows passing multidimensional
arrays to functions.  In addition, you can use the "restrict" pointer
syntax (total hell to use, by the way) to tell the compiler that a
pointer argument to a function is not in an aliasing relation to other
pointers accessible to the function.

As a result, it has now become theoretically possible to write C code
for multidimensional array manipulations that can be optimized as well
as naively written Fortran code from 1960.  In practice, however, it
turns out that both code writers as well as compiler writers are not
quite up to the task yet.

Lesson: make hard to find and optimize corner cases undefined behavior
if you don't want to make it almost impossible to write code that can be
optimized well.  The more assumptions an optimizer is allowed to make by
default, the better it can do its work.  _Without_ special help by the
programmer.  And if we wanted to rely on special help by the programmer,
it would be more straightforward if we let the programmer write the
assembly code rather than the compiler.

-- 
David Kastrup

Re: GNU Guile branch, wip-peval-predicates, created. v2.0.5-100-g59c5570

[Ludovic Courtès]

Hi,

Andy Wingo <wingo@pobox.com> skribis:

> But OK, the question here is, what if another thread is concurrently
> mutating X and Y?  If this were C++ or Java, the answer would be that
> they can still fold, because access to a multithreaded mutable needs to
> be synchronized.  I think this is reasonable.  What do you think?

I agree.

Ludo’.

Re: GNU Guile branch, wip-peval-predicates, created. v2.0.5-100-g59c5570

[David Kastrup]

ludo@gnu.org (Ludovic Courtès) writes:

> Andy Wingo <wingo@pobox.com> skribis:
>
>> But OK, the question here is, what if another thread is concurrently
>> mutating X and Y?  If this were C++ or Java, the answer would be that
>> they can still fold, because access to a multithreaded mutable needs to
>> be synchronized.  I think this is reasonable.  What do you think?
>
> I agree.

I just reread what I replied, and it was probably hard to detect the
implicit "I too" between the lines of the diatribe.

-- 
David Kastrup