Index: Objects/dictobject.c =================================================================== RCS file: /cvsroot/python/python/dist/src/Objects/dictobject.c,v retrieving revision 2.96 diff -c -r2.96 dictobject.c *** Objects/dictobject.c 2001/05/27 07:39:22 2.96 --- Objects/dictobject.c 2001/05/31 03:29:23 *************** *** 85,123 **** iteration. */ - static long polys[] = { - /* 4 + 3, */ /* first active entry if MINSIZE == 4 */ - 8 + 3, /* first active entry if MINSIZE == 8 */ - 16 + 3, - 32 + 5, - 64 + 3, - 128 + 3, - 256 + 29, - 512 + 17, - 1024 + 9, - 2048 + 5, - 4096 + 83, - 8192 + 27, - 16384 + 43, - 32768 + 3, - 65536 + 45, - 131072 + 9, - 262144 + 39, - 524288 + 39, - 1048576 + 9, - 2097152 + 5, - 4194304 + 3, - 8388608 + 33, - 16777216 + 27, - 33554432 + 9, - 67108864 + 71, - 134217728 + 39, - 268435456 + 9, - 536870912 + 5, - 1073741824 + 83 - /* 2147483648 + 9 -- if we ever boost this to unsigned long */ - }; - /* Object used as dummy key to fill deleted entries */ static PyObject *dummy; /* Initialized by first call to newdictobject() */ --- 85,90 ---- *************** *** 168,174 **** int ma_fill; /* # Active + # Dummy */ int ma_used; /* # Active */ int ma_size; /* total # slots in ma_table */ - int ma_poly; /* appopriate entry from polys vector */ /* ma_table points to ma_smalltable for small tables, else to * additional malloc'ed memory. ma_table is never NULL! This rule * saves repeated runtime null-tests in the workhorse getitem and --- 135,140 ---- *************** *** 202,209 **** (mp)->ma_table = (mp)->ma_smalltable; \ (mp)->ma_size = MINSIZE; \ (mp)->ma_used = (mp)->ma_fill = 0; \ - (mp)->ma_poly = polys[0]; \ - assert(MINSIZE < (mp)->ma_poly && (mp)->ma_poly < MINSIZE*2); \ } while(0) PyObject * --- 168,173 ---- *************** *** 252,257 **** --- 216,240 ---- a dictentry* for which the me_value field is NULL. Exceptions are never reported by this function, and outstanding exceptions are maintained. */ + + /* #define DUMP_HASH_STUFF */ + #ifdef DUMP_HASH_STUFF + static int nEntry = 0, nCollide = 0, nTrip = 0; + #define BUMP_ENTRY ++nEntry + #define BUMP_COLLIDE ++nCollide + #define BUMP_TRIP ++nTrip + #define PRINT_HASH_STUFF \ + if ((nEntry & 0x1ff) == 0) \ + fprintf(stderr, "%d %d %d\n", nEntry, nCollide, nTrip) + + #else + #define BUMP_ENTRY + #define BUMP_COLLIDE + #define BUMP_TRIP + #define PRINT_HASH_STUFF + #endif + + static dictentry * lookdict(dictobject *mp, PyObject *key, register long hash) { *************** *** 265,270 **** --- 248,254 ---- register int checked_error = 0; register int cmp; PyObject *err_type, *err_value, *err_tb; + BUMP_ENTRY; /* We must come up with (i, incr) such that 0 <= i < ma_size and 0 < incr < ma_size and both are a function of hash. i is the initial table index and incr the initial probe offset. */ *************** *** 294,309 **** } freeslot = NULL; } ! /* Derive incr from hash, just to make it more arbitrary. Note that ! incr must not be 0, or we will get into an infinite loop.*/ ! incr = hash ^ ((unsigned long)hash >> 3); ! /* In the loop, me_key == dummy is by far (factor of 100s) the least likely outcome, so test for that last. */ for (;;) { ! if (!incr) ! incr = 1; /* and incr will never be 0 again */ ! ep = &ep0[(i + incr) & mask]; if (ep->me_key == NULL) { if (restore_error) PyErr_Restore(err_type, err_value, err_tb); --- 278,292 ---- } freeslot = NULL; } ! incr = hash; ! BUMP_COLLIDE; /* In the loop, me_key == dummy is by far (factor of 100s) the least likely outcome, so test for that last. */ for (;;) { ! BUMP_TRIP; ! i = (i << 2) + i + (incr & 0xf) + 1; ! incr >>= 4; ! ep = &ep0[i & mask]; if (ep->me_key == NULL) { if (restore_error) PyErr_Restore(err_type, err_value, err_tb); *************** *** 335,344 **** } else if (ep->me_key == dummy && freeslot == NULL) freeslot = ep; - /* Cycle through GF(2**n). */ - if (incr & 1) - incr ^= mp->ma_poly; /* clears the lowest bit */ - incr >>= 1; } } --- 318,323 ---- *************** *** 370,375 **** --- 349,356 ---- mp->ma_lookup = lookdict; return lookdict(mp, key, hash); } + BUMP_ENTRY; + PRINT_HASH_STUFF; /* We must come up with (i, incr) such that 0 <= i < ma_size and 0 < incr < ma_size and both are a function of hash */ i = hash & mask; *************** *** 387,400 **** } /* Derive incr from hash, just to make it more arbitrary. Note that incr must not be 0, or we will get into an infinite loop.*/ ! incr = hash ^ ((unsigned long)hash >> 3); ! /* In the loop, me_key == dummy is by far (factor of 100s) the least likely outcome, so test for that last. */ for (;;) { ! if (!incr) ! incr = 1; /* and incr will never be 0 again */ ! ep = &ep0[(i + incr) & mask]; if (ep->me_key == NULL) return freeslot == NULL ? ep : freeslot; if (ep->me_key == key --- 368,382 ---- } /* Derive incr from hash, just to make it more arbitrary. Note that incr must not be 0, or we will get into an infinite loop.*/ ! incr = hash; ! BUMP_COLLIDE; /* In the loop, me_key == dummy is by far (factor of 100s) the least likely outcome, so test for that last. */ for (;;) { ! BUMP_TRIP; ! i = (i << 2) + i + (incr & 0xf) + 1; ! incr >>= 4; ! ep = &ep0[i & mask]; if (ep->me_key == NULL) return freeslot == NULL ? ep : freeslot; if (ep->me_key == key *************** *** 404,413 **** return ep; if (ep->me_key == dummy && freeslot == NULL) freeslot = ep; - /* Cycle through GF(2**n). */ - if (incr & 1) - incr ^= mp->ma_poly; /* clears the lowest bit */ - incr >>= 1; } } --- 386,391 ---- *************** *** 448,454 **** static int dictresize(dictobject *mp, int minused) { ! int newsize, newpoly; dictentry *oldtable, *newtable, *ep; int i; int is_oldtable_malloced; --- 426,432 ---- static int dictresize(dictobject *mp, int minused) { ! int newsize; dictentry *oldtable, *newtable, *ep; int i; int is_oldtable_malloced; *************** *** 456,475 **** assert(minused >= 0); ! /* Find the smallest table size > minused, and its poly[] entry. */ ! newpoly = 0; ! newsize = MINSIZE; ! for (i = 0; i < sizeof(polys)/sizeof(polys[0]); ++i) { ! if (newsize > minused) { ! newpoly = polys[i]; ! break; ! } ! newsize <<= 1; ! if (newsize < 0) /* overflow */ ! break; ! } ! if (newpoly == 0) { ! /* Ran out of polynomials or newsize overflowed. */ PyErr_NoMemory(); return -1; } --- 434,445 ---- assert(minused >= 0); ! /* Find the smallest table size > minused. */ ! for (newsize = MINSIZE; ! newsize <= minused && newsize >= 0; ! newsize <<= 1) ! ; ! if (newsize < 0) { PyErr_NoMemory(); return -1; } *************** *** 511,517 **** mp->ma_table = newtable; mp->ma_size = newsize; memset(newtable, 0, sizeof(dictentry) * newsize); - mp->ma_poly = newpoly; mp->ma_used = 0; i = mp->ma_fill; mp->ma_fill = 0; --- 481,486 ----