Re: expansion, memoization, and evaluation...

From: Rob Browning <rlb@defaultvalue.org>
Cc: Dirk Herrmann <dirk@ida.ing.tu-bs.de>, guile-devel@gnu.org
Subject: Re: expansion, memoization, and evaluation...
Date: Wed, 04 Dec 2002 15:11:02 -0600	[thread overview]
Message-ID: <878yz5fq1l.fsf@raven.i.defaultvalue.org> (raw)
In-Reply-To: <xy765uaw9d7.fsf@linnaeus.i-did-not-set--mail-host-address--so-tickle-me> (Mikael Djurfeldt's message of "Wed, 04 Dec 2002 08:07:00 +0100")

Mikael Djurfeldt <mdj@kvast.blakulla.net> writes:

>> You may have already said this, but if the method is called later with
>> "different types", then does it have to notice that and recompute?
>
> No, that copy of the compiled code will never be called with anything
> but the types it's compiled for.

OK, so does that mean that at each invocation, you need to look at the
incoming types and check to see if you already have a cached method
that matches the incoming signature?  i.e. if you have

  (blah)
  (foo bar baz)
  (blarg)

and foo is a generic function, and last time through, bar and baz were
integers, but this time bar and baz are strings.  Would the current
behavior be for goops to check, notice this, and build a new
"precompiled" invocation for two strings?  (Just trying to check to
see that I understand...)

> Hmm... What do you mean by "control the object code"?  Surely, there
> is nothing about what I've said about goops which prevents the
> optimizations in the "alternate approach" from being done?

Well as yet I don't have a clear idea in mind, and in fact a number of
the optimizations I've thought of would require flow and scope
analysis.  To some extent I'm just speculating about possibilities,
inspired by clever (non-goops-specific) hacks that can be possible
when you know enough about a closed region of source.  For example, if
you know that within a given function (or closed set of functions) you
use some set of symbols, and within the set you have big (case foo
...)  statements using those symbols, you may be able to compile the
object code to use plain integers to represent these symbols and then
issue c-style switches to handle the case statements.  Alternately you
might be able to use a "small consecutive integers" numbering scheme
to represent the integers and then per-case vector jump tables with
those integers as indices for the case statements.  Either way should
beat the much more naive O(N) approach:

  if (SCM_EQ_P (foo, x_sym)) { ... }
  else if (SCM_EQ_P (foo, y_sym)) { ... }
  ...

> Maybe there's a misunderstanding here: Goops gives source back to
> the compiler.  The compiler then can continue to do whatever
> optimizations it chooses to, and also has full control over the
> object code it's emitting.

That makes sense.  The reason I was confused was because it sounded
like goops was making decisions based on the runtime types of
arguments, and if so, and if you were doing compilation offline, then
you wouldn't have access to that information.  Your comment about
possibly having to use type flow analysis for offline compilation
cleared that up for me.

(Of course if the guile compiler were implemented targeting C, and if
 guile were to "Depends: gcc", we might be able to use dlopen/dlsym to
 support heavyweight online compilation.  Though first-time execution
 would be awfully painful unless your machine was really fast ;>)

-- 
Rob Browning
rlb @defaultvalue.org, @linuxdevel.com, and @debian.org
Previously @cs.utexas.edu
GPG starting 2002-11-03 = 14DD 432F AE39 534D B592  F9A0 25C8 D377 8C7E 73A4

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