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 |