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