Debian Codegraph @

src/memo.c

raw
1 /*
2 * memo.c - memoization table
3 *
4 * Copyright (c) 2021-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/memoP.h"
38
39 /* See memoP.h for the design choices. */
40
41 /* NB: Get, Getv, Put and Putv procedures shouldn't throw a Scheme error. */
42
43 SCM_DEFINE_BUILTIN_CLASS_SIMPLE(Scm_MemoTableClass, NULL);
44
45 static ScmMemoTableStorage *new_storage(u_long capacity,
46 int entry_size,
47 u_long flags)
48 {
49 ScmMemoTableStorage *s = SCM_NEW(ScmMemoTableStorage);
50 s->capacity = capacity;
51 if (flags & SCM_MEMO_TABLE_WEAK) {
52 s->vec = SCM_NEW_ATOMIC_ARRAY(ScmAtomicVar,
53 capacity * entry_size);
54 } else {
55 s->vec = SCM_NEW_ARRAY(ScmAtomicVar,
56 capacity * entry_size);
57 }
58 return s;
59 }
60
61 ScmObj Scm_MakeMemoTable(u_long capacity, int num_keys, u_long flags)
62 {
63 ScmMemoTable *t = SCM_NEW(ScmMemoTable);
64 SCM_SET_CLASS(t, SCM_CLASS_MEMO_TABLE);
65 t->flags = flags;
66 t->num_keys = num_keys;
67 t->entry_size = (num_keys > 0? (num_keys+2) : (-num_keys+3));
68 t->storage = new_storage(capacity, t->entry_size, flags);
69 return SCM_OBJ(t);
70 }
71
72 /* common routine to extract # of fixed keys and # of rest keys */
73 static inline int get_numkeys(int nkeys, int *rest_keys)
74 {
75 *rest_keys = nkeys <= 0;
76 return (nkeys > 0 ? nkeys : -nkeys);
77 }
78
79 static inline int get_total_numkeys(int nkeys)
80 {
81 return (nkeys > 0? nkeys : -nkeys + 1);
82 }
83
84 /*
85 * hash and equality
86 *
87 * We use hard-wired hash/equality function.
88 * Objects are hashed/compared as eqv-hash and eqv?, except <string>,
89 * <box>, <mv-box> and <proxy-type>.
90 */
91
92 static inline _Bool equal_1(ScmObj a, ScmObj b)
93 {
94 if (SCM_STRINGP(a)) {
95 return SCM_STRINGP(b) && Scm_StringEqual(SCM_STRING(a), SCM_STRING(b));
96 } else if (SCM_BOXP(a)) {
97 return SCM_BOXP(b) && equal_1(SCM_BOX_VALUE(a), SCM_BOX_VALUE(b));
98 } else if (SCM_MVBOXP(a)) {
99 if (!SCM_MVBOXP(b) || SCM_MVBOX_SIZE(a)!=SCM_MVBOX_SIZE(b)) return FALSE;
100 for (ScmSmallInt i=0; i<SCM_MVBOX_SIZE(a); i++) {
101 if (!equal_1(SCM_MVBOX_VALUES(a)[i], SCM_MVBOX_VALUES(b)[i]))
102 return FALSE;
103 }
104 return TRUE;
105 } else if (SCM_PROXY_TYPE_P(a)) {
106 return SCM_PROXY_TYPE_P(b)
107 && SCM_EQ(Scm_ProxyTypeRef(SCM_PROXY_TYPE(a)),
108 Scm_ProxyTypeRef(SCM_PROXY_TYPE(b)));
109 } else {
110 return Scm_EqvP(a, b);
111 }
112 }
113
114 static inline u_long hash_1(ScmObj key)
115 {
116 if (SCM_STRINGP(key)) {
117 return Scm_HashString(SCM_STRING(key), 0);
118 } else if (SCM_BOXP(key)) {
119 return hash_1(SCM_BOX_VALUE(key));
120 } else if (SCM_MVBOXP(key)) {
121 u_long h = 0;
122 for (ScmSmallInt i=0; i<SCM_MVBOX_SIZE(key); i++) {
123 h = Scm_CombineHashValue(h, hash_1(SCM_MVBOX_VALUES(key)[i]));
124 }
125 return h;
126 } else if (SCM_PROXY_TYPE_P(key)) {
127 return hash_1(SCM_OBJ(Scm_ProxyTypeRef(SCM_PROXY_TYPE(key))));
128 } else {
129 return Scm_EqvHash(key);
130 }
131 }
132
133 static u_long memo_hashv(ScmObj *keys, int nkeys)
134 {
135 u_long v = (u_long)Scm_HashSaltRef();
136 int rest_keys;
137 int fixed_keys = get_numkeys(nkeys, &rest_keys);
138 for (int i = 0; i < fixed_keys; i++) {
139 u_long v1 = hash_1(keys[i]);
140 v = Scm_CombineHashValue(v, v1);
141 }
142 if (rest_keys) {
143 ScmObj rest = keys[fixed_keys], rp;
144 SCM_FOR_EACH(rp, rest) {
145 u_long v1 = hash_1(SCM_CAR(rp));
146 v = Scm_CombineHashValue(v, v1);
147 }
148 }
149 return v;
150 }
151
152 static _Bool memo_equalv(ScmObj *keys, int nkeys, ScmAtomicVar *entry_keys)
153 {
154 int rest_keys;
155 int fixed_keys = get_numkeys(nkeys, &rest_keys);
156 for (int i = 0; i < fixed_keys; i++) {
157 ScmObj k = (ScmObj)Scm_AtomicLoad(entry_keys+i);
158 if (!equal_1(keys[i], k)) return FALSE;
159 }
160 if (rest_keys) {
161 ScmObj rest = keys[fixed_keys], rp;
162 ScmObj entry_rest = (ScmObj)Scm_AtomicLoad(entry_keys+fixed_keys);
163 SCM_FOR_EACH(rp, rest) {
164 if (!SCM_PAIRP(entry_rest)) return FALSE;
165 if (!equal_1(SCM_CAR(rp), SCM_CAR(entry_rest))) return FALSE;
166 entry_rest = SCM_CDR(entry_rest);
167 }
168 }
169 return TRUE;
170 }
171
172 /*
173 * lookup
174 */
175
176 /* Returns #<unbound> if entry not found.
177 Be careful not to leak it to Scheme. */
178 ScmObj Scm_MemoTableGetv(ScmMemoTable *tab, ScmObj *keys, int nkeys)
179 {
180 int num_keys = get_total_numkeys(tab->num_keys);
181 if (num_keys != nkeys) return SCM_UNBOUND;
182 u_long hashv = memo_hashv(keys, tab->num_keys);
183 ScmAtomicWord hashv_hdr = (ScmAtomicWord)((hashv<<1)+1);
184
185 /* storage pointer may be swapped by another thread, but we're going to
186 operate on the current snapshot.*/
187 ScmMemoTableStorage *st = tab->storage;
188
189 for (u_long i = 0; i < st->capacity / 2; i++) {
190 u_long k = (hashv+i) % st->capacity;
191 u_long idx = k * tab->entry_size;
192 ScmAtomicWord entry_hdr = Scm_AtomicLoad(&st->vec[idx]);
193 if (entry_hdr == 0) return SCM_UNBOUND; /* not found */
194 if ((entry_hdr & 0x01) == 0
195 || entry_hdr != hashv_hdr) {
196 /* the entry is invalid, someone's working on it,
197 or it is with other hash value. */
198 continue;
199 }
200 if (memo_equalv(keys, tab->num_keys, &st->vec[idx+1])) {
201 /* found */
202 return SCM_OBJ(st->vec[idx + nkeys + 1]);
203 }
204 }
205 return SCM_UNBOUND;
206 }
207
208 ScmObj Scm_MemoTableGet(ScmMemoTable *tab, ScmObj keys)
209 {
210 int rest_keys;
211 int fixed_keys = get_numkeys(tab->num_keys, &rest_keys);
212 ScmSmallInt given_keys = Scm_Length(keys);
213 if ((!rest_keys && given_keys != fixed_keys)
214 || (rest_keys && given_keys < fixed_keys)) return SCM_UNBOUND;
215
216 ScmObj keyv[fixed_keys+rest_keys];
217 for (int i=0; i<fixed_keys; i++) {
218 keyv[i] = SCM_CAR(keys);
219 keys = SCM_CDR(keys);
220 }
221 if (rest_keys) keyv[fixed_keys] = keys;
222
223 return Scm_MemoTableGetv(tab, keyv, fixed_keys+rest_keys);
224 }
225
226 /*
227 * insert
228 */
229
230 static inline void insert_entry(ScmMemoTable *tab, ScmMemoTableStorage *st,
231 u_long entry_index, ScmAtomicWord hashv_hdr,
232 ScmObj *keys, ScmObj val)
233 {
234 int num_keys = get_total_numkeys(tab->num_keys);
235 for (int ik = 0; ik < num_keys; ik++) {
236 Scm_AtomicStore(&st->vec[entry_index+1+ik], (ScmAtomicWord)keys[ik]);
237 }
238 Scm_AtomicStore(&st->vec[entry_index+1+num_keys], (ScmAtomicWord)val);
239 Scm_AtomicStoreFull(&st->vec[entry_index], hashv_hdr);
240 }
241
242 /* returns TRUE on success, FALSE on failure */
243 static int search_and_insert(ScmMemoTable *tab, ScmMemoTableStorage *st,
244 ScmAtomicWord hashv_hdr, ScmObj *keys, ScmObj val,
245 ScmVM *vm)
246 {
247 u_long hashv = ((u_long)hashv_hdr) >> 1;
248 for (u_long i = 0; i < st->capacity / 2; i++) {
249 u_long k = (hashv+i) % st->capacity;
250 u_long idx = k * tab->entry_size;
251 ScmAtomicWord entry_hdr = Scm_AtomicLoad(&st->vec[idx]);
252 if (entry_hdr == 0) {
253 /* The table doesn't have the key. Try to claim this entry. */
254 ScmAtomicWord expected = entry_hdr;
255 if (Scm_AtomicCompareExchange(&st->vec[idx], &expected,
256 (ScmAtomicWord)vm)) {
257 insert_entry(tab, st, idx, hashv_hdr, keys, val);
258 return TRUE;
259 } else {
260 continue;
261 }
262 }
263 if ((entry_hdr & 0x03) == 0) {
264 /* Other thread is working on this entry. We skip. */
265 continue;
266 }
267 if ((entry_hdr & 0x01) == 0) {
268 /* This entry is marked invalid.
269 We may reuse this entry if it's safe. For now, we just skip. */
270 continue;
271 }
272 if (entry_hdr != hashv_hdr) {
273 /* This entry is already used. */
274 continue;
275 }
276 if (memo_equalv(keys, tab->num_keys, &st->vec[idx+1])) {
277 /* We already have the entry.
278 We set the value anyway, in case if the value has been
279 disappeared.
280
281 NB: It is possible that another thread have already seen
282 the value is 0 and gone to mark the header invalid. If it
283 happens, this insertion is ignored. It's ok because of
284 idempotency. */
285 Scm_AtomicStoreFull(&st->vec[idx+1+get_total_numkeys(tab->num_keys)],
286 (ScmAtomicWord)val);
287 return TRUE;
288 }
289 }
290 return FALSE;
291 }
292
293 static void extend_table(ScmMemoTable *tab)
294 {
295 ScmMemoTableStorage *orig_st = tab->storage;
296 ScmMemoTableStorage *new_st = new_storage(orig_st->capacity * 2,
297 tab->entry_size,
298 tab->flags);
299 int num_keys = get_total_numkeys(tab->num_keys);
300 ScmObj keys[num_keys];
301 ScmVM *self = Scm_VM();
302
303 /* Copy the existing entry into the new table.
304 Note: This may miss some entries that's are being added during
305 this operation, but it's ok. It won't change the outcome, just
306 costs extra time to re-compute that result. */
307 for (u_long i = 0; i < orig_st->capacity; i++) {
308 u_long idx = i * tab->entry_size;
309 ScmAtomicWord entry_hdr = Scm_AtomicLoad(&orig_st->vec[idx]);
310 if ((entry_hdr & 0x01) == 0) {
311 /* unused, invalid, or someone is working on it. */
312 continue;
313 }
314 for (int k = 0; k < num_keys; k++) {
315 keys[k] = SCM_OBJ(Scm_AtomicLoad(&orig_st->vec[idx+1+k]));
316 }
317 ScmObj val = SCM_OBJ(Scm_AtomicLoad(&orig_st->vec[idx+1+num_keys]));
318 if (!search_and_insert(tab, new_st, entry_hdr, keys, val, self)) {
319 Scm_Panic("memo table overflow double fault");
320 }
321 }
322 tab->storage = new_st;
323 }
324
325 ScmObj Scm_MemoTablePutv(ScmMemoTable *tab, ScmObj *keys, int nkeys, ScmObj val)
326 {
327 int num_keys = get_total_numkeys(tab->num_keys);
328 if (nkeys != num_keys) return SCM_FALSE;
329 u_long hashv = memo_hashv(keys, tab->num_keys);
330 ScmAtomicWord hashv_hdr = (ScmAtomicWord)((hashv<<1)+1);
331
332 ScmMemoTableStorage *st = tab->storage;
333 ScmVM *self = Scm_VM();
334
335 for (int retry = 0; retry < 3; retry++) {
336 if (search_and_insert(tab, st, hashv_hdr, keys, val, self)) {
337 return SCM_TRUE;
338 }
339 extend_table(tab);
340 st = tab->storage;
341 }
342 Scm_Warn("extending memo table failed.\n");
343 return SCM_FALSE;
344 }
345
346 ScmObj Scm_MemoTablePut(ScmMemoTable *tab, ScmObj keys, ScmObj val)
347 {
348 int rest_keys;
349 int fixed_keys = get_numkeys(tab->num_keys, &rest_keys);
350 ScmSmallInt given_keys = Scm_Length(keys);
351 if ((!rest_keys && given_keys != fixed_keys)
352 || (rest_keys && given_keys < fixed_keys)) return SCM_UNBOUND;
353
354 ScmObj keyv[fixed_keys+rest_keys];
355 for (int i=0; i<fixed_keys; i++) {
356 keyv[i] = SCM_CAR(keys);
357 keys = SCM_CDR(keys);
358 }
359 if (rest_keys) keyv[fixed_keys] = keys;
360
361 return Scm_MemoTablePutv(tab, keyv, fixed_keys+rest_keys, val);
362 }
363
364 /*
365 * for debugging
366 */
367
368 static inline void dump_1(ScmAtomicWord entry, int valid, ScmPort *port)
369 {
370 if (valid && entry) {
371 Scm_Printf(port, " %S\n", SCM_OBJ(entry));
372 } else if (valid) {
373 Scm_Printf(port, " #null\n");
374 } else {
375 Scm_Printf(port, " #unused\n");
376 }
377 }
378
379 /* This is not entirely thread-safe. We assume this is called manually
380 during interactive debugging. */
381 void Scm__MemoTableDump(ScmMemoTable *tab, ScmPort *port)
382 {
383 Scm_Printf(port, "memo-table %p (num_keys=%d entry_size=%d capacity=%d",
384 tab, tab->num_keys, tab->entry_size, tab->storage->capacity);
385 if (tab->flags & SCM_MEMO_TABLE_WEAK) {
386 Scm_Printf(port, " weak");
387 }
388 if (tab->flags & SCM_MEMO_TABLE_FIXED) {
389 Scm_Printf(port, " fixed");
390 }
391 Scm_Printf(port, ")\n");
392 u_long num_entries = tab->storage->capacity * tab->entry_size;
393 int rest_keys;
394 int fixed_keys = get_numkeys(tab->num_keys, &rest_keys);
395 for (u_long i = 0; i < num_entries; i += tab->entry_size) {
396 Scm_Printf(port, "%4d %08x\n", i/tab->entry_size,
397 tab->storage->vec[i]);
398 int valid = tab->storage->vec[i] & 0x01;
399 for (int j = 0; j < fixed_keys; j++) {
400 ScmAtomicWord key = Scm_AtomicLoad(&tab->storage->vec[i+1+j]);
401 dump_1(key, valid, port);
402 }
403 if (rest_keys) {
404 ScmAtomicWord keys = Scm_AtomicLoad(&tab->storage->vec[i+1+fixed_keys]);
405 dump_1(keys, valid, port);
406 }
407
408 ScmAtomicWord value =
409 Scm_AtomicLoad(&tab->storage->vec[i+1+fixed_keys+rest_keys]);
410 dump_1(value, valid, port);
411 }
412 }
413
414 /*
415 * initialization
416 */
417
418 void Scm__InitMemoTable(void)
419 {
420 ScmModule *mod = Scm_GaucheModule();
421 Scm_InitStaticClass(&Scm_MemoTableClass, "<memo-table>", mod, NULL, 0);
422 }