status: separation of expansion/optimization/memoization/execution

status: separation of expansion/optimization/memoization/execution

[Dirk Herrmann]

Hi folks,

just wanted to let you know that I have actually been working on the issue
above:  Currently I am splitting up built-in macros following the
following pattern:


Former function:

SCM
scm_m_foo (SCM expr, SCM env)
{
  /* perform syntax checking, expansion, minor optimizations and
     memoization in one step. */
  return <new_expr>;
}


New set of functions:

static SCM
expand_foo (SCM expr, SCM env)
{
  /* perform syntax checking and expansion.  After this step, the code is
     still valid scheme code.  However, not all features are used. */
  return expanded_expr;
}

static SCM
optimize_foo (SCM expr, SCM env SCM_UNUSED)
{
  /* Most optimization functions are empty upto now.  In some cases,
     minor optimizations are performed.  After this step, the code is
     still valid scheme code.  However, not all features are used.  */
  return optimized_expr;
}

static SCM
memoize_foo (SCM expr, SCM env)
{
  /* return the memoized form of foo.  In some cases, minor memoization
     related optimizations are performed.  After this step, the code is
     not valid scheme code any more, and, with the current printer and
     reader, it can not be written and re-read.  */
  return memoized_expr;
}

SCM
scm_m_foo (SCM expr, SCM env)
{
  /* first, call expand_foo.  Then, using the result, call optimize_foo.
     Then, using the result of optimize_foo, call memoize_foo. */
  return memoized_expr;
}


Basically, with the changes above everythings still works as before, that
is, expansion and friends are still executed dynamically during execution.
However, the functionality of each of the builtin-mmacros is more cleanly
separated into different tasks with different responsibilities.  And, I
have added more exhaustive syntax checks into the expand_foo functions.

Up to now I have done this only for "if", "set!", "and", "or", "case",
"cond" and "do".  I also have simplified SCM_CEVAL at those places, where
due to the more extensive syntax checks in expand_foo some execution-time
syntax checks could be eliminated.  (However, all this takes some time,
since I only manage to finish at most one macro each day.)

The effect so far is, that booting guile takes noticably longer (at least
15%), but for example executing the test-suite is almost as fast as before
(2% slower).  Unfortunately, it is not yet possible to achieve large
performance improvements.  This will only be possible when the steps are
really separated.  Then, memoizing variable locations in the memoize_foo
functions will be possible, which simply can not work at the moment:  One
reason is the re-writing of internal defines, which disallows the
memoization of variables until the expansion phase is completed.


I have, however, not taken care of keeping track of debugging information
so far.  That is, I would like to hear suggestions about how this should
be done, since I don't have looked into that issue yet.  If someone is
interested to give the stuff a review (with respect to the debugging
issues or just generally), I would be glad to send you the patches for
eval.c and eval.h.  If the debugging stuff is worked out, it could even
make sense to submit the changes so far to allow for a broader testing in
the head branch.


Best regards,
Dirk Herrmann


_______________________________________________
Guile-user mailing list
Guile-user@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-user

Re: status: separation of expansion/optimization/memoization/execution

[Rob Browning]

Dirk Herrmann <dirk@sallust.ida.ing.tu-bs.de> writes:

> Basically, with the changes above everythings still works as before,
> that is, expansion and friends are still executed dynamically during
> execution.  However, the functionality of each of the
> builtin-mmacros is more cleanly separated into different tasks with
> different responsibilities.  And, I have added more exhaustive
> syntax checks into the expand_foo functions.

Eeeeexcelent :>

> The effect so far is, that booting guile takes noticably longer (at least
> 15%), but for example executing the test-suite is almost as fast as before
> (2% slower).  Unfortunately, it is not yet possible to achieve large
> performance improvements.  This will only be possible when the steps are
> really separated.  Then, memoizing variable locations in the memoize_foo
> functions will be possible, which simply can not work at the moment:  One
> reason is the re-writing of internal defines, which disallows the
> memoization of variables until the expansion phase is completed.

I don't know if you *are* worrying about the performance cost right
now, but if you are, I'd say don't.  Even if guile stays 20% slower
for a while, the long term benefits (and potential speedups) of this
work far outweigh the medium-term performance cost.

BTW has anyone else played with valgrind
http://developer.kde.org/~sewardj/docs/manual.html?  I'm planning to
play with it, but so far have only had a chance to see that it doesn't
like some of our ptr manipulations.  I also wonder if cachegrind might
be able to tell us anything useful...

> I have, however, not taken care of keeping track of debugging
> information so far.  That is, I would like to hear suggestions about
> how this should be done, since I don't have looked into that issue
> yet.  If someone is interested to give the stuff a review (with
> respect to the debugging issues or just generally), I would be glad
> to send you the patches for eval.c and eval.h.

I don't really know a lot about how debugging's being handled now, so
I'm not the best person to comment here.

> If the debugging stuff is worked out, it could even make sense to
> submit the changes so far to allow for a broader testing in the head
> branch.

Absolutely.  Actually I'd even say that if the debugging info is not
worked out, but if we think it *can* be worked out within a couple of
months, and if everything else is OK, then perhaps you should go ahead
and merge.  Your work will definitely get more attention in HEAD.

-- 
Rob Browning
rlb @defaultvalue.org, @linuxdevel.com, and @debian.org
Previously @cs.utexas.edu
GPG=1C58 8B2C FB5E 3F64 EA5C  64AE 78FE E5FE F0CB A0AD

_______________________________________________
Guile-user mailing list
Guile-user@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-user

Re: status: separation of expansion/optimization/memoization/execution

[Han-Wen]

rlb@defaultvalue.org writes:
> 
> BTW has anyone else played with valgrind
> http://developer.kde.org/~sewardj/docs/manual.html?  I'm planning to
> play with it, but so far have only had a chance to see that it doesn't
> like some of our ptr manipulations.  I also wonder if cachegrind might
> be able to tell us anything useful...

Yes, I tried running it on lilypond (which is linked to GUILE). I got
a ton of warnings that was not able to suppress (it seems that the
suppressions don't work for valgrind internal functions, like
strncmp).  Running valgrind for checking is probably pointless for
GUILE, as GUILE manages its own memory; the stack scanning GC also
generates lots of spurious warnings.

I did run it through the CPU cache simulator, which indicated that
gc_mark, gc_sweep and scm_ceval are causing a lot of cache misses.  I
hope to improve the GC part when I can compile guile with GCC 3.1 ;
GCC 3.1 supports prefetch instructions, so cache misses can be
decreased by doing stuff like

	  mark_cons:
	      prefetch (cdr)
	      scm_gc_mark (car)
	      ptr = cdr;
	      goto mark_again;


probably there are some techniques to boost cache rates for eval() as
well.



This is with the java-tree GC benchmark:

--------------------------------------------------------------------------------
I1 cache:         16384 B, 32 B, 4-way associative
D1 cache:         16384 B, 32 B, 4-way associative
L2 cache:         524288 B, 32 B, 4-way associative
Command:          ./libguile/.libs/lt-guile -s /tmp/graphs.sch
Events recorded:  Ir I1mr I2mr Dr D1mr D2mr Dw D1mw D2mw
Events shown:     Ir I1mr I2mr Dr D1mr D2mr Dw D1mw D2mw
Event sort order: Ir I1mr I2mr Dr D1mr D2mr Dw D1mw D2mw
Thresholds:       99 0 0 0 0 0 0 0 0
Include dirs:     
User annotated:   
Auto-annotation:  off

--------------------------------------------------------------------------------
         Ir    I1mr   I2mr          Dr      D1mr    D2mr         Dw    D1mw   D2mw 
--------------------------------------------------------------------------------
566,304,440 177,926 22,634 214,093,739 5,330,222 439,850 60,193,298 122,340 31,098  PROGRAM TOTALS

--------------------------------------------------------------------------------
         Ir   I1mr  I2mr         Dr      D1mr    D2mr         Dw   D1mw   D2mw  file:function
--------------------------------------------------------------------------------
188,450,666 28,572 4,577 69,348,246 1,248,161   6,579 18,620,442 22,047     84  eval.c:scm_ceval
 94,460,034  1,574   368 31,701,931 1,627,987 249,416  7,924,122 14,992  1,579  gc-mark.c:scm_gc_mark_dependencies
 90,846,605  7,899   114 38,685,160   620,624 134,205  5,581,738    746      8  gc-card.c:scm_sweep_card
 36,806,561    479    76 12,092,342    63,732      79  1,526,389      0      0  eval.c:scm_ilookup
 36,027,996     92    11 11,734,622   487,301   2,201  5,880,036 14,057  1,682  gc-mark.c:scm_gc_mark
 12,369,948    642   642  5,936,102   422,488   9,297  1,083,306      0      0  weaks.c:scm_mark_weak_vector_spines
 11,620,162    652   652  4,374,134   353,606   1,097  1,193,150     47      0  weaks.c:scm_scan_weak_vectors
 11,124,410    873    37  5,781,750   106,113      38  2,669,915      7      0  ../libguile/inline.h:scm_acons
  7,826,240  6,519   337  2,201,130    67,895     173    733,710      0      0  vectors.c:scm_vector_ref
  7,241,746    448     5  3,897,614    67,863      27  1,671,236     20      0  ../libguile/inline.h:scm_cons
  7,217,944    902   232  1,740,251     4,410       4  1,332,234  3,415     10  eval.c:scm_eval_args
  6,957,761 16,749 1,561  6,956,140    54,050   2,073        702      6      6  ???:???


-- 

Han-Wen Nienhuys   |   hanwen@cs.uu.nl   |   http://www.cs.uu.nl/~hanwen 

_______________________________________________
Guile-user mailing list
Guile-user@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-user

Re: status: separation of expansion/optimization/memoization/execution

[Marius Vollmer]

Dirk Herrmann <dirk@sallust.ida.ing.tu-bs.de> writes:

> Basically, with the changes above everythings still works as before, that
> is, expansion and friends are still executed dynamically during execution.
> However, the functionality of each of the builtin-mmacros is more cleanly
> separated into different tasks with different responsibilities.  And, I
> have added more exhaustive syntax checks into the expand_foo functions.

Hmm, what is the purpose of this seperation?  As far as I can see, the
important thing is the separate memoization from execution, not the
various stages of memoization itself.

_______________________________________________
Guile-user mailing list
Guile-user@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-user

Re: status: separation of expansion/optimization/memoization/execution

[Neil Jerram]

>>>>> "Dirk" == Dirk Herrmann <dirk@sallust.ida.ing.tu-bs.de> writes:

    Dirk> I have, however, not taken care of keeping track of
    Dirk> debugging information so far.  That is, I would like to hear
    Dirk> suggestions about how this should be done, since I don't
    Dirk> have looked into that issue yet.  If someone is interested
    Dirk> to give the stuff a review (with respect to the debugging
    Dirk> issues or just generally), I would be glad to send you the
    Dirk> patches for eval.c and eval.h.

I'd be happy to look at these.

        Neil


_______________________________________________
Guile-user mailing list
Guile-user@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-user

Re: status: separation of expansion/optimization/memoization/execution

[Dirk Herrmann]

On 5 Aug 2002, Marius Vollmer wrote:

> Dirk Herrmann <dirk@sallust.ida.ing.tu-bs.de> writes:
> 
> > Basically, with the changes above everythings still works as before, that
> > is, expansion and friends are still executed dynamically during execution.
> > However, the functionality of each of the builtin-mmacros is more cleanly
> > separated into different tasks with different responsibilities.  And, I
> > have added more exhaustive syntax checks into the expand_foo functions.
> 
> Hmm, what is the purpose of this seperation?  As far as I can see, the
> important thing is the separate memoization from execution, not the
> various stages of memoization itself.

Well, I have to agree that I am not yet sure whether this separation is
actually necessary.  For me, this is a means to get a clearer idea of what
is actually going on - especially in the context of weird stuff like the
conversion of internal defines into letrecs and so on.  And, it is
actually quite simple to do this separation while doing the separation of
memoization from execution.

Maybe it makes sense to combine some of the steps later on.  But, on the
other hand, it may also be beneficial to have such a separation later, in
order to be able to insert an optional optimization step between expansion
and memoization.

Best regards,
Dirk


_______________________________________________
Guile-user mailing list
Guile-user@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-user

Re: status: separation of expansion/optimization/memoization/execution

[Dirk Herrmann]

On 5 Aug 2002, Neil Jerram wrote:

> >>>>> "Dirk" == Dirk Herrmann <dirk@sallust.ida.ing.tu-bs.de> writes:
> 
>     Dirk> I have, however, not taken care of keeping track of
>     Dirk> debugging information so far.  That is, I would like to hear
>     Dirk> suggestions about how this should be done, since I don't
>     Dirk> have looked into that issue yet.  If someone is interested
>     Dirk> to give the stuff a review (with respect to the debugging
>     Dirk> issues or just generally), I would be glad to send you the
>     Dirk> patches for eval.c and eval.h.
> 
> I'd be happy to look at these.

Great,  I will send a patch to you as soon as I have reached a state again
in which guile compiles :-)

Best regards,
Dirk


_______________________________________________
Guile-user mailing list
Guile-user@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-user

Re: status: separation of expansion/optimization/memoization/execution

[Marius Vollmer]

Dirk Herrmann <dirk@sallust.ida.ing.tu-bs.de> writes:

> > Hmm, what is the purpose of this seperation?  As far as I can see, the
> > important thing is the separate memoization from execution, not the
> > various stages of memoization itself.
> 
> Well, I have to agree that I am not yet sure whether this separation is
> actually necessary.  For me, this is a means to get a clearer idea of what
> is actually going on

Ok, but you are seeing a significant loss inperformance because of
them, right?  Although I think it is acceptable to make on-the-fly
compilation more expensive in order to allow ahead-of-time
compilation, we should not do it gratuitously.  It will be a long way
until we might no longer want to care about the on-the-fly compiler
since everybody compiles their important code ahead-of-time anyway.

So, cleaning up the existing lazy memoizer is a very good thing
indeed.  But I'd say you should also make sure that you don't
significantly lose performance by doing it.  That part of Guile will
be performance-critical for quite some time.

-- 
GPG: D5D4E405 - 2F9B BCCC 8527 692A 04E3  331E FAF8 226A D5D4 E405


_______________________________________________
Guile-user mailing list
Guile-user@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-user

Re: status: separation of expansion/optimization/memoization/execution

[Dirk Herrmann]

On 10 Aug 2002, Marius Vollmer wrote:

> So, cleaning up the existing lazy memoizer is a very good thing
> indeed.  But I'd say you should also make sure that you don't
> significantly lose performance by doing it.  That part of Guile will
> be performance-critical for quite some time.

At the current state I can't decide yet, whether after the changes guile's
speed will at all differ from before.  Too many optimizations of the
scheme code are not possible yet, until the separation is complete.  If
there is a performance problem then, it will be easier to optimize the
evaluator then.  There are, however, a lot of open questions:

* in principle, memoization could memoize all variable references.  That
  would mean, the execution could be freed of all checks for symbols and
  variable lookups - this would have been done by the memoizer.

  Benefits:  
  - no symbol lookups in the executor
  - quoted symbols could be made into symbols, getting rid of one level of
    quoting

  Problems:
  - how to deal with undefined symbols?
  - should 'undefine' still be possible, and if so, how?

* should the executor ever run over an undefined symbol?  This could be
  checked during expansion and memoization.  If it is known that during
  exection all symbols are defined, this eliminates one test during
  variable lookup.

Best regards,
Dirk



_______________________________________________
Guile-user mailing list
Guile-user@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-user

Re: status: separation of expansion/optimization/memoization/execution

[Marius Vollmer]

Dirk Herrmann <dirk@sallust.ida.ing.tu-bs.de> writes:

> On 10 Aug 2002, Marius Vollmer wrote:
> 
> > So, cleaning up the existing lazy memoizer is a very good thing
> > indeed.  But I'd say you should also make sure that you don't
> > significantly lose performance by doing it.  That part of Guile will
> > be performance-critical for quite some time.
> 
> At the current state I can't decide yet, whether after the changes guile's
> speed will at all differ from before.  Too many optimizations of the
> scheme code are not possible yet, until the separation is complete.

Are there optimizations that will be possible after the separation
that are not possible now?

In any case, please proceed carefully.  Making a branch is probably a
good idea.

-- 
GPG: D5D4E405 - 2F9B BCCC 8527 692A 04E3  331E FAF8 226A D5D4 E405


_______________________________________________
Guile-user mailing list
Guile-user@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-user