HCoop / bpt / guile.git / blame
| Commit | Line | Data |
|---|---|---|
| a98cef7e KN |
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 |