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

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

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

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