| 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 | |