[Python-Dev] shrinking dicts

[Tim Peters]

[Vladimir Marangozov, *almost* seems ready to give up on a counter-
 productive dict pessimization <wink>]

> ...
> There is, however, a small percentage of dicts which are used
> below 1/3 of their size. I must say, below 1/3 of their peek size,
> because dowsizing is also rare. To trigger a downsize, 1/3 new
> entries of the peek size must be inserted.

Not so, although "on average" 1/6 may be correct.  Look at an extreme:  Say
a dict has size 333 (it can't, but it makes the math obvious ...).  Say it
contains 221 items.  Now someone deletes them all, one at a time.  used==0
and fill==221 at this point.  They insert one new key that happens to hit
one of the 333-221 = 112 remaining NULL keys.  Then used==1 and fill==222.
They insert a 2nd key, and before the dict is searched the new fill of 222
triggers the 2/3rds load-factor resizing -- which asks for a new size of 1*2
== 2.

For the minority of dicts that go up and down in size wildly many times, the
current behavior is fine.

> Besides these observations, after looking at the code one more
> time, I can't really understand why the resize logic is based on
> the "fill" watermark and not on "used". fill = used + dummy, but
> since lookdict returns the first free slot (null or dummy), I don't
> really see what's the point of using a fill watermark...

Let's just consider an unsuccessful search.  Then it does return "the first"
free slot, but not necessarily at the time it *sees* the first free slot.
So long as it sees a dummy, it has to keep searching; the search doesn't end
until it finds a NULL.  So consider this, assuming the resize triggered only
on "used":

d = {}
for i in xrange(50000):
    d[random.randrange(1000000)] = 1
for k in d.keys():
    del d[k]
# now there are 50000 dummy dict keys, and some number of NULLs

# loop invariant:  used == 0
for i in xrange(sys.maxint):
    j = random.randrange(10000000)
    d[j] = 1
    del d[j]
    assert not d.has_key(i)

However many NULL slots remained, the last loop eventually transforms them
*all* into dummies.  The dummies act exactly like "real keys" with respect
to expected time for an unsuccessful search, which is why it's thoroughly
appropriate to include dummies in the load factor computation.  The loop
will run slower and slower as the percentage of dummies approaches 100%, and
each failing has_key approaches O(N) time.

In most hash table implementations that's the worst that can happen (and
it's a disaster), but under Python's implementation it's worse:  Python
never checks to see whether the probe sequence "wraps around", so the first
search after the last NULL is changed to a dummy never ends.

Counting the dummies in the load-factor computation prevents all that:  no
matter how much inserts and deletes are intermixed, the "effective load
factor" stays under 2/3rds so gives excellent expected-case behavior; and it
also protects against an all-dummy dict, making the lack of an expensive
inner-loop "wrapped around?" check safe.

> Perhaps you can enlighten me on this. Using only the "used" metrics
> seems fine to me. I even deactivated "fill" and replaced it with "used"
> to see what happens -- no visible changes, except a tiny speedup I'm
> willing to neglect.

You need a mix of deletes and inserts for the dummies to make a difference;
dicts that always grow don't have dummies, so they're not likely to have any
dummy-related problems either <wink>.  Try this (untested):

import time
from random import randrange
N = 1000
thatmany = [None] * N

while 1:
    start = time.clock()
    for i in thatmany:
        d[randrange(10000000)] = 1
    for i in d.keys():
        del d[i]
    finish = time.clock()
    print round(finish - start, 3)

Succeeding iterations of the outer loop should grow dramatically slower, and
finally get into an infinite loop, despite that "used" never exceeds N.

Short course rewording:  for purposes of predicting expected search time, a
dummy is the same as a live key, because finding a dummy doesn't end a
search -- it has to press on until either finding the key it was looking
for, or finding a NULL.  And with a mix of insertions and deletions, and if
the hash function is doing a good job, then over time all the slots in the
table will become either live or dummy, even if "used" stays within a very
small range.

So, that's why <wink>.

dictobject-may-be-the-subtlest-object-there-is-ly y'rs  - tim