Debian Codegraph @

src/dispatch.c

raw
1 /*
2 * dispatch.c - method dispatch accelerator
3 *
4 * Copyright (c) 2017-2024 Shiro Kawai <[email protected]>
5 *
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions
8 * are met:
9 *
10 * 1. Redistributions of source code must retain the above copyright
11 * notice, this list of conditions and the following disclaimer.
12 *
13 * 2. Redistributions in binary form must reproduce the above copyright
14 * notice, this list of conditions and the following disclaimer in the
15 * documentation and/or other materials provided with the distribution.
16 *
17 * 3. Neither the name of the authors nor the names of its contributors
18 * may be used to endorse or promote products derived from this
19 * software without specific prior written permission.
20 *
21 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
22 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
23 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
24 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
25 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
26 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
27 * TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
28 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
29 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
30 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
31 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
32 */
33
34 #define LIBGAUCHE_BODY
35 #include "gauche.h"
36 #include "gauche/priv/configP.h"
37 #include "gauche/priv/atomicP.h"
38 #include "gauche/priv/dispatchP.h"
39
40 /*
41 * Method dispatch acceleration
42 *
43 * gf->dispatcher may contain a structure that accelerates method dispatch.
44 * The structure must be treated as opaque from other parts.
45 *
46 * In the current implementation, we use special open-addressing hash table.
47 * We don't use ScmHashCore for a few reasons:
48 *
49 * - We mutex modification of the table by gf->mutex, but we don't want
50 * to lock for searching it. ScmHashCore doesn't guarantee consistency
51 * of reading while modifying.
52 * - It is in performance critical path, and we can take advantage of
53 * domain knowledge to make it faster than generic implementation.
54 *
55 * At this moment, the dispatch accelerator isn't built automatically.
56 * You need to call gauche.object#generic-build-dispatcher! explicitly
57 * on a generic function. The effect varies depending on the methods
58 * the GF has, so we selectively turn on this feature for speed-sensitive
59 * GFs and see how it goes. If it is proven to be effective enough,
60 * we might implement an automated mechanism when GF meets certain
61 * criteria.
62 *
63 * We take advantage of the following facts:
64 *
65 * - Once we hit the leaf method we don't need to find less-specific
66 * methods at all.
67 * - Some generic functions has methods most of which are leaf methods,
68 * and can be mostly specialized by a single argument. The typical
69 * example is `ref'.
70 *
71 * When methods are mostly specilized by N-th argument, we call the N
72 * as AXIS (zero based). Typically, methods tend to be specialized by
73 * the first argument, in which case axis is 0.
74 *
75 * The method dispatcher contains a hash table, where each key is
76 * a tuple (<class>, <number-of-args>), and its value is a list of
77 * methods, whose axis specializer is <class> and which can take
78 * <number-of-args>.
79 *
80 * When a GF with dispatch accelerator is called, we retrieve the class
81 * of the axis of the actual argument, and lookup the hash table with
82 * that class and the number of actual arguments. If we have a hit,
83 * and the entry solely consists of leaf methods,
84 * the list of methods are the list of applicable methods---since there
85 * are no more specific methods, and we don't need to look for less specific
86 * methods. This means...
87 *
88 * - We don't need to go through the entire method list to find
89 * all applicable methods.
90 * - We don't need to allocate to construct the list of applicable
91 * methods.
92 *
93 * Note that if the entry has at least one non-leaf method, we have to
94 * fall back to the normal path, since there may be other applicable
95 * methods that might be called via next-method. To cut the overhead
96 * of checking, we keep the list of leaf methods and the one of non-leaf
97 * methods separately.
98 */
99
100 /* On concurrent access:
101 *
102 * We don't want to lock the method hash for every invocation of GF.
103 * So we employ some atomic pointer operations so that readers can
104 * see the consistent state even another thread is modifying it.
105 *
106 * We still acquire GF lock whenever we modify the mhash, so there's
107 * at most one thread that's modifying it. Modification is only required
108 * when a new method is added to the GF or any one of classes that
109 * specializes one of the methods is redefined.
110 *
111 * The modification is done by making a modified copy of (sub)structure
112 * and then swap the pointer atomically, thus the concurrent reader
113 * won't see inconsistent state.
114 *
115 * The locking on GF is done in class.c.
116 */
117
118 struct ScmMethodDispatcherRec {
119 int axis; /* Which argument we look at?
120 This is immutable. */
121 ScmAtomicVar methodHash; /* mhash. In case mhash is extended,
122 we atomically swap reference. */
123 };
124
125 typedef struct mhash_entry_rec {
126 ScmClass *klass;
127 int nargs;
128 ScmObj leaves; /* list of matching leaf methods */
129 ScmObj nonleaves; /* list of matching non-leaf methods */
130 } mhash_entry;
131
132 typedef struct mhash_rec {
133 int size; /* # of bins. power of 2. */
134 int num_entries; /* # of active entries. */
135 ScmAtomicVar bins[1]; /* Table. Each entry may have one of:
136 0 - free
137 1 - deleted
138 mhash_entry
139 We might atomically change the bin value,
140 which shouldn't affect concurrently reading
141 threads.
142 */
143 } mhash;
144
145
146 static inline u_long mhashfn(ScmClass *k, int nargs)
147 {
148 return (((SCM_WORD(k) >> 3) + nargs) * 2654435761UL) >> 20;
149 }
150
151 static mhash *make_mhash(int size)
152 {
153 mhash *mh = SCM_NEW2(mhash*, sizeof(mhash)+(sizeof(ScmAtomicWord)*(size-1)));
154 mh->size = size;
155 mh->num_entries = 0;
156 for (int i=0; i<size; i++) mh->bins[i] = 0;
157 return mh;
158 }
159
160 static ScmObj mhash_probe(const mhash *h, ScmClass *k, int nargs)
161 {
162 /* Quadratic probing
163 j = H_i(k,nargs) + (i + i^2)/2
164 H_{i+1} - H_i = ((i+1) + (i+1)^2 - (i + i^2))/2 = i + 1
165 */
166 u_long j = mhashfn(k, nargs) & (h->size - 1);
167 int i = 0;
168 for (; i < h->size; i++) {
169 /* Need to strip 'const', because of C11 error
170 http://www.open-std.org/jtc1/sc22/wg14/www/docs/summary.htm#dr_459 */
171 ScmAtomicVar *loc = (ScmAtomicVar*)&h->bins[j];
172 ScmWord w = SCM_WORD(Scm_AtomicLoad(loc));
173 if (w == 0) break;
174 if (w != 1) {
175 mhash_entry *e = (mhash_entry*)w;
176 if (e->klass == k && e->nargs == nargs) {
177 if (SCM_NULLP(e->nonleaves)) return e->leaves;
178 else return SCM_FALSE;
179 }
180 }
181 j = (j + i + 1) & (h->size - 1);
182 }
183 return SCM_FALSE;
184 }
185
186 static mhash *mhash_insert_1(mhash *h, ScmClass *k, int nargs, ScmMethod *m)
187 {
188 u_long j = mhashfn(k, nargs) & (h->size - 1);
189 long free_slot = -1;
190 ScmObj ltail = SCM_NIL, ntail = SCM_NIL;
191 int i = 0;
192 for (; i < h->size; i++) {
193 ScmWord w = SCM_WORD(Scm_AtomicLoad(&h->bins[j]));
194 if (w == 0) { /* end of chain */
195 if (free_slot < 0) free_slot = j;
196 break;
197 }
198 if (w == 1) {
199 if (free_slot < 0) free_slot = j;
200 continue;
201 }
202 mhash_entry *e = (mhash_entry*)w;
203 if (e->klass == k && e->nargs == nargs) {
204 free_slot = j;
205 ltail = e->leaves;
206 ntail = e->nonleaves;
207 h->num_entries--;
208 break;
209 }
210 j = (j + i + 1) & (h->size - 1);
211
212 }
213 SCM_ASSERT(free_slot >= 0);
214 mhash_entry *e = SCM_NEW(mhash_entry);
215 e->klass = k;
216 e->nargs = nargs;
217 e->leaves = SCM_METHOD_LEAF_P(m)? Scm_Cons(SCM_OBJ(m), ltail) : ltail;
218 e->nonleaves = SCM_METHOD_LEAF_P(m) ? ntail : Scm_Cons(SCM_OBJ(m), ntail);
219 Scm_AtomicStoreFull(&h->bins[free_slot], (ScmAtomicWord)e);
220 h->num_entries++;
221 return h;
222 }
223
224 static mhash *mhash_insert(mhash *h, ScmClass *k, int nargs, ScmMethod *m)
225 {
226 if (h->size <= h->num_entries*2) {
227 /* extend */
228 mhash *nh = make_mhash(h->size*2);
229 nh->num_entries = h->num_entries;
230 for (int i = 0; i < h->size; i++) {
231 ScmWord w = h->bins[i];
232 if (w == 0 || w == 1) continue;
233 mhash_entry *e = (mhash_entry*)w;
234 u_long j = mhashfn(e->klass, e->nargs) & (nh->size - 1);
235 int k = 0;
236 for (; k < nh->size; k++) {
237 if (SCM_WORD(nh->bins[j]) == 0) {
238 nh->bins[j] = w;
239 break;
240 }
241 j = (j + k + 1) & (nh->size - 1);
242 }
243 SCM_ASSERT(k < nh->size);
244 }
245 h = nh;
246 }
247 return mhash_insert_1(h, k, nargs, m);
248 }
249
250 static mhash *mhash_delete(mhash *h, ScmClass *k, int nargs, ScmMethod *m)
251 {
252 u_long j = mhashfn(k, nargs) & (h->size - 1);
253
254 int i = 0;
255 for (; i < h->size; i++) {
256 ScmWord w = SCM_WORD(Scm_AtomicLoad(&h->bins[j]));
257 if (w == 0) break;
258 if (w == 1) continue;
259 mhash_entry *e = (mhash_entry*)w;
260 if (e->klass == k && e->nargs == nargs) {
261 ScmObj ml = e->leaves;
262 ScmObj mn = e->nonleaves;
263 if (SCM_PAIRP(ml) && SCM_EQ(SCM_CAR(ml), SCM_OBJ(m))) {
264 ml = SCM_CDR(ml); /* fast path */
265 } else {
266 ml = Scm_Delete(SCM_OBJ(m), ml, SCM_CMP_EQ);
267 }
268 if (SCM_PAIRP(mn) && SCM_EQ(SCM_CAR(mn), SCM_OBJ(m))) {
269 mn = SCM_CDR(mn); /* fast path */
270 } else {
271 mn = Scm_Delete(SCM_OBJ(m), mn, SCM_CMP_EQ);
272 }
273
274 if (SCM_NULLP(ml) && SCM_NULLP(ml)) {
275 h->num_entries--;
276 Scm_AtomicStore(&h->bins[j], 1); /* mark as deleted */
277 } else {
278 mhash_entry *e = SCM_NEW(mhash_entry);
279 e->klass = k;
280 e->nargs = nargs;
281 e->leaves = ml;
282 e->nonleaves = mn;
283 Scm_AtomicStoreFull(&h->bins[j], (ScmAtomicWord)e);
284 }
285 break;
286 }
287 j = (j + i + 1) & (h->size - 1);
288 }
289 return h;
290 }
291
292 static void mhash_print(mhash *h, ScmPort *out)
293 {
294 Scm_Printf(out, "mhash size=%d num_entries=%d\n", h->size, h->num_entries);
295 for (int i=0; i<h->size; i++) {
296 ScmWord w = SCM_WORD(h->bins[i]);
297 if (w == 0) {
298 Scm_Printf(out, "[%3d] empty\n\n\n", i);
299 } else if (w == 1) {
300 Scm_Printf(out, "[%3d] deleted\n\n\n", i);
301 } else {
302 mhash_entry *e = (mhash_entry*)w;
303 Scm_Printf(out, "[%3d] %lu %S(%d)\n", i,
304 (mhashfn(e->klass, e->nargs) % h->size),
305 e->klass, e->nargs);
306 Scm_Printf(out, " Leaves: %S\n", e->leaves);
307 Scm_Printf(out, " NonLeaves:%S\n", e->nonleaves);
308 }
309 }
310 }
311
312 static mhash *add_method_to_dispatcher(mhash *h, int axis, ScmMethod *m)
313 {
314 int req = SCM_PROCEDURE_REQUIRED(m);
315 if (req >= axis) {
316 ScmClass *klass = m->specializers[axis];
317 if (SCM_PROCEDURE_OPTIONAL(m)) {
318 for (int k = req; k < SCM_DISPATCHER_MAX_NARGS; k++)
319 h = mhash_insert(h, klass, k, m);
320 } else {
321 h = mhash_insert(h, klass, req, m);
322 }
323 }
324 return h;
325 }
326
327 static mhash *delete_method_from_dispatcher(mhash *h, int axis, ScmMethod *m)
328 {
329 int req = SCM_PROCEDURE_REQUIRED(m);
330 if (req >= axis) {
331 ScmClass *klass = m->specializers[axis];
332 if (SCM_PROCEDURE_OPTIONAL(m)) {
333 for (int k = req; k < SCM_DISPATCHER_MAX_NARGS; k++)
334 h = mhash_delete(h, klass, k, m);
335 } else {
336 h = mhash_delete(h, klass, req, m);
337 }
338 }
339 return h;
340 }
341
342 /*
343 NB: We run through the method list twice, first process the
344 leaf methods, and then process non-leaf methods. Non-leaf methods
345 cancels the dispatcher entry and forces to go through normal route.
346 */
347 ScmMethodDispatcher *Scm__BuildMethodDispatcher(ScmObj methods, int axis)
348 {
349 mhash *mh = make_mhash(32);
350 ScmObj mm;
351 for (int i = 0; i < 2; i++) {
352 SCM_FOR_EACH(mm, methods) {
353 ScmMethod *m = SCM_METHOD(SCM_CAR(mm));
354 if ((i == 0 && SCM_METHOD_LEAF_P(m))
355 || (i == 1 && !SCM_METHOD_LEAF_P(m))) {
356 mh = add_method_to_dispatcher(mh, axis, m);
357 }
358 }
359 }
360 ScmMethodDispatcher *dis = SCM_NEW(ScmMethodDispatcher);
361 dis->axis = axis;
362 dis->methodHash = (ScmAtomicWord)mh;
363 return dis;
364 }
365
366 void Scm__MethodDispatcherAdd(ScmMethodDispatcher *dis, ScmMethod *m)
367 {
368 mhash *h = (mhash*)Scm_AtomicLoad(&dis->methodHash);
369 mhash *h2 = add_method_to_dispatcher(h, dis->axis, m);
370 if (h != h2) Scm_AtomicStore(&dis->methodHash, (ScmAtomicWord)h2);
371 }
372
373 void Scm__MethodDispatcherDelete(ScmMethodDispatcher *dis, ScmMethod *m)
374 {
375 mhash *h = (mhash*)Scm_AtomicLoad(&dis->methodHash);
376 mhash *h2 = delete_method_from_dispatcher(h, dis->axis, m);
377 if (h != h2) Scm_AtomicStore(&dis->methodHash, (ScmAtomicWord)h2);
378 }
379
380 ScmObj Scm__MethodDispatcherLookup(ScmMethodDispatcher *dis,
381 ScmClass **typev, int argc)
382 {
383 if (dis->axis <= argc) {
384 ScmClass *selector = typev[dis->axis];
385 mhash *h = (mhash*)Scm_AtomicLoad(&dis->methodHash);
386 return mhash_probe(h, selector, argc);
387 } else {
388 return SCM_FALSE;
389 }
390 }
391
392 ScmObj Scm__MethodDispatcherInfo(const ScmMethodDispatcher *dis)
393 {
394 ScmObj h = SCM_NIL, t = SCM_NIL;
395 /* Need to strip 'const', because of C11 error
396 http://www.open-std.org/jtc1/sc22/wg14/www/docs/summary.htm#dr_459 */
397 ScmAtomicVar *loc = (ScmAtomicVar*)&dis->methodHash;
398 const mhash *mh = (const mhash*)Scm_AtomicLoad(loc);
399 SCM_APPEND1(h, t, SCM_MAKE_KEYWORD("axis"));
400 SCM_APPEND1(h, t, SCM_MAKE_INT(dis->axis));
401 SCM_APPEND1(h, t, SCM_MAKE_KEYWORD("num-entries"));
402 SCM_APPEND1(h, t, SCM_MAKE_INT(mh->num_entries));
403 return h;
404 }
405
406 void Scm__MethodDispatcherDump(ScmMethodDispatcher *dis, ScmPort *port)
407 {
408 Scm_Printf(port, "MethodDispatcher axis=%d\n", dis->axis);
409 mhash_print((mhash*)dis->methodHash, port);
410 }