doc/goops.mail

   1 From: Mikael Djurfeldt <mdj@mdj.nada.kth.se>
   2 Subject: Re: After GOOPS integration: Computation with native types!
   3 To: Keisuke Nishida <kxn30@po.cwru.edu>
   4 Cc: djurfeldt@nada.kth.se, guile@sourceware.cygnus.com
   5 Cc: djurfeldt@nada.kth.se
   6 Date: 17 Aug 2000 03:01:13 +0200
   7
   8 Keisuke Nishida <kxn30@po.cwru.edu> writes:
   9
  10 > Do I need to include some special feature in my VM?  Hmm, but maybe
  11 > I shouldn't do that now...
  12
  13 Probably not, so I probably shouldn't answer, but...  :)
  14
  15 You'll need to include some extremely efficient mechanism to do
  16 multi-method dispatch.  The SCM_IM_DISPATCH form, with its
  17 implementation at line 2250 in eval.c, is the current basis for
  18 efficient dispatch in GOOPS.
  19
  20 I think we should develop a new instruction for the VM which
  21 corresponds to the SCM_IM_DISPATCH form.
  22
  23 This form serves both the purpose to map argument types to the correct
  24 code, and as a cache of compiled methods.
  25
  26 Notice that I talk about cmethods below, not methods.  In GOOPS, the
  27 GF has a set of methods, but each method has a "code-table" mapping
  28 argument types to code compiled for those particular concrete types.
  29 (So, in essence, GOOPS methods abstractly do a deeper level of type
  30 dispatch.)
  31
  32 The SCM_IM_DISPATCH form has two shapes, depending on whether we use
  33 sequential search (few cmethods) or hashed lookup (many cmethods).
  34
  35 Shape 1:
  36
  37  (#@dispatch args N-SPECIALIZED #((TYPE1 ... ENV FORMALS FORM1 ...) ...) GF)
  38
  39 Shape 2:
  40
  41  (#@dispatch args N-SPECIALIZED HASHSET MASK
  42              #((TYPE1 ... ENV FORMALS FORM1 ...) ...)
  43              GF)
  44
  45 `args' is (I hope!) a now historic obscure optimization.
  46
  47 N-SPECIALIZED is the maximum number of arguments t do type checking
  48 on.  This is used early termination of argument checking where the
  49 already checked arguments are enough to pick out the cmethod.
  50
  51 The vector is the cache proper.
  52
  53 During sequential search the argument types are simply checked against
  54 each entry.
  55
  56 The method for hashed dispatch is described in:
  57
  58 http://www.parc.xerox.com/csl/groups/sda/publications/papers/Kiczales-Andreas-PCL
  59
  60 In this method, each class has a hash code.  Dispatch means summing
  61 the hash codes for all arguments (up til N-SPECIALIZED) and using the
  62 sum to pick a location in the cache.  The cache is sequentially
  63 searched for an argument type match from that point.
  64
  65 Kiczales introduced a clever method to maximize the probability of a
  66 direct cache hit.  We actually have 8 separate sets of hash codes for
  67 all types.  The hash set to use is selected specifically per GF and is
  68 optimized to give fastest average hit.
  69
  70
  71 What we could try to do as soon as the VM is complete enough is to
  72 represent the cmethods as chunks of byte code.  In the current GOOPS
  73 code, the compilation step (which is currently empty) is situated in
  74 `compile-cmethod' in guile-oops/compile.scm.  [Apologies for the
  75 terrible code.  That particular part was written at Arlanda airport
  76 after a sleepless night (packing luggage, not coding), on my way to
  77 visit Marius (who, BTW, didn't take GOOPS seriously.  ;-)]
  78