[Patches] [Patch #102733] {}.popitem() implementation

[noreply@sourceforge.net]

Patch #102733 has been updated. 

Project: python
Category: core (C code)
Status: Open
Submitted by: gvanrossum
Assigned to : tim_one
Summary: {}.popitem() implementation

Follow-Ups:

Date: 2000-Dec-09 14:01
By: gvanrossum

Comment:
New patch uploaded.  This is really Tim Peters's patch, including the correction he posted on Sat, 9 Dec 2000 16:09:30.

I don't know why Tim's original suggested "improvement" worked so well for me -- it really did improve a lot over the original version.  Oh well.
-------------------------------------------------------

Date: 2000-Dec-08 10:28
By: gvanrossum

Comment:
Tim (or anyone else): can you improve this?

It has excellent performance as long as you only do a single dictionary at a time, but goes quadratic if you call popitem() for two identical dictionaries in lock-step.

Maybe jumping criss-cross through the hash table like lookdict does would improve that; but I don't understand the math used for that ("Cycle through GF(2^n)-{0}" ???).

Here's a test program:

import time

for run in range(1000):
    print "run =", run
    for log2size in range(10, 18):
        size = 2**log2size
        print "log2size =", log2size,
        print "size =", size
        a = {}
        t0 = time.clock()
        while 1:
            i = len(a)
            if i >= size:
                break
            a[`i`] = i
        t1 = time.clock()
        print "%.1f usec per item to build (total %.3f sec)" % (
            (1e6*(t1-t0)/size), t1-t0)
        b = a.copy()
        t0 = time.clock()
        try:
            while 1:
                a.popitem()
                b.popitem()
        except KeyError:
            pass
        t1 = time.clock()
        print "%.1f usec per item to destroy twins (total %.3f sec)" % (
            (1e6*(t1-t0)/size), t1-t0)
        assert not a, a
        assert not b, b

-------------------------------------------------------

Date: 2000-Dec-08 10:58
By: tim_one

Comment:
While I haven't yet actually tried it, I'm pretty sure you'd get much better performance (linear) in your test case by changing "finger = i+1" to "finger = i", and no matter how many dicts you march over in lockstep.  In the case of a single dict, it adds a trivial amount of overhead per lookup (one extra C-speed trip around the loop per lookup).

The reason "GF(2^n)-{)}" confuses you is because he should have written "**" instead of "^" <wink>.  In essense, it means "visit each of the 2**n bit patterns exactly once, except for the all-zero pattern", and the "GF" means Galois Field, the theoretical basis for why the bit manipulations actually achieve that.  I don't believe it would help:  the sequence of bit patterns visited remains fixed, and if you continue to move the finger "one beyond" you'll get the same problem (the first pass thru two lockstep iters creates gaps that the second pass has to skip over; the second pass doubles the size of those gaps; the third pass doubles them again, etc).

I agree that sharing one finger is very attractive.  +1.
-------------------------------------------------------

Date: 2000-Dec-08 11:04
By: gvanrossum

Comment:
New patch with Tim's suggestion.  Works well!
-------------------------------------------------------

Date: 2000-Dec-08 14:55
By: tim_one

Comment:
Actually, your test program with the new patch continues to show rotten behavior for me.  dict.copy() returns a dict with the same value, but not necessarily the same internal structure.  This is easy to see by changing the test's inner loop to

while 1:
    gota = a.popitem()
    gotb = b.popitem()
    assert gota == gotb, (gota, gotb, len(a), len(b))

This fails instantly for me:

run = 0
log2size = 10 size = 1024
10.2 usec per item to build (total 0.010 sec)
Traceback (most recent call last):
  File "tdict.py", line 27, in ?
    assert gota == gotb, (gota, gotb, len(a), len(b))
AssertionError: (('773', 773), ('479', 479), 1023, 1023)

If I make the dicts truly identical, by building b via the same operations in the same order as occurred for a, then the assert doesn't trigger and performance is wonderful (deleting the dicts is faster than building them).  But in that case, the original "finger = i+1" is also very good (just a little slower).  My head analysis of that case was wrong:  the first pass does create a checkerboard pattern in both dicts, but the second pass systematically hits the holes created by the first pass.

Are you sure your test program worked a lot better after the patch?  Best I can tell, what I'm seeing has very little to do with the finger strategy and very much to do with accidents in the way dict.copy() works.
-------------------------------------------------------

-------------------------------------------------------
For more info, visit:

http://sourceforge.net/patch/?func=detailpatch&patch_id=102733&group_id=5470