homepage

This patch implements the feature request at
http://sourceforge.net/tracker/index.php?
func=detail&aid=495086&group_id=5470&atid=355470 which 
asks for an optional argument to popitem so that it 
returns a key/value pair for a specified key or, if 
not specified, an arbitrary key.
The benefit is in providing a fast, explicit way to 
retrieve and remove and particular key/value pair from 
a dictionary. By using only a single lookup, it is 
faster than the usual Python code:
 value = d[key]
 del d[key]
 return (key, value)
which now becomes:
 return d.popitem(key)
There is no magic or new code in the implementation -- 
it uses a few lines each from getitem, delitem, and 
popitem. If an argument is specified, the new code is 
run; otherwise, the existing code is run. This 
assures that the patch does not cause a performance 
penalty.
The diff is about -3 lines and +25 lines.
There are four sections:
1. Replacement code for dict_popitem in dictobject.c
2. Replacement docstring for popitem in dictobject.c
3. Replacement registration line for popitem in 
dictobject.c
4. Sample Python test code.

Logged In: YES 
user_id=6380
Please upload a context or unified diff.

Logged In: YES 
user_id=80475
Context diff uploaded at poppatch.c below.

Logged In: YES 
user_id=6380
Now, if you could also upload a unittest and a doc patch,
that would be great!

Logged In: YES 
user_id=6380
I've reviewed the patch and see only cosmetic things that
need to be changed. I'll check it in as soon as you submit a
unittest and doc patch.

Logged In: YES 
user_id=6380
FYI, I'm uploading my version of the patch, with code
cleanup, as popdict2.txt. I've moved the popitem-with-arg
code before the allocation of res, because there were
several places where this code returned NULL without
DECREF'ing res. Repeating the PyTuple_New(2) call seemed the
lesser evil.

Logged In: YES 
user_id=31435
Are there examples of concrete use cases? The idea that 
dict.popitem(k) returns (k, dict[k]) seems kinda goofy, 
since you necessarily already have k.
So the question is whether this is the function signature 
that's really desired, or whether it's too much a hack. As 
is, it slows down popitem() without an argument because it 
requires using a fancier calling sequence, and because it 
now defers that case to a taken branch; it's also much 
slower than a function that just returned v could be, due 
to the need to allocate a 2-tuple to hold a redundant copy 
of the key.
Perhaps there are use cases of the form
 k, v = dict.popitem(f(x, y, z))
where the key is known only implicitly?

Logged In: YES 
user_id=80475
Q: Does the new function signature slow the existing no 
argument case? A: Yes. The function is already so fast, 
that the small overhead of PyArg_ParseTuple is measurable. 
My timing shows a 8% drop in speed.
Q: Is _,v=d.popitem(k) slower than v=d.popvalue(k)? A: 
Yes. Though popvalue is a non-existing strawman, it would 
be quicker: it would cost two calls to Py_DECREF while 
saving a call to PyTuple_New and two calls to 
PyTuple_SET_ITEM. Still, the running time for popvalue 
would be dominated by the rest of the function and not the 
single malloc. Also, I think it unlikely that the 
dictionary interface would ever be expanded for popvalue, 
so the comparison is moot.
Q: Are there cases where (k,v) is needed? A: Yes. One 
common case is where the tuple still needs to be formed to 
help build another dictionary: dict([d.popitem(k) for k in 
xferlist]) or [n.__setitem__(d.popitem(k)) for k in 
xferlist].
Also, it is useful when the key is computed by a function 
and then needs to be used in an expression. I often do 
something like that with setdefault: uniqInOrder=
[u.setdefault(k,k) for k in alist if k not in u].
Also, when the key is computed by a function, it may need 
to be saved only when .popitem succeeds but not when the 
key is missing: "get and remove key if present; trigger 
exception if absent" This pattern is used in validating 
user input keys for deletion.
Q: Where is the unittest and doc patch? A: Coming this 
weekend.

Logged In: YES 
user_id=80475
The tests and documentation patches have been added.

Logged In: YES 
user_id=35752
I think this should be implemented as pop() instead:
 D.pop([key]) -> value -- remove and return value by key
(default a random value)
It makes no sense to return the key when you already have
it. pop() also matches well with list pop():
 L.pop([index]) -> item -- remove and return item at index
(default last)

Logged In: YES 
user_id=6380
Not a bad idea, Neil! Care to work the code around to
implement that?

Logged In: YES 
user_id=35752
Here's a quick implementation. D.pop() is not as efficient
as it could be (it uses popitem and then promply deallocates
the item tuple). I'm not sure it matters though.
Someone should probably check the refcounts. I always screw
them up. :-)

Logged In: YES 
user_id=80475
Here's a more fleshed-out implementation of D.pop(). It 
doesn't rely on popitem(), doesn't malloc a tuple, and the 
refcounts should be correct.
One change from Neil's version, since k isn't being 
returned, then an arbitrary pair doesn't make sense, so the 
key argument to pop is required rather than optional.
The diff is off of 2.123.

Logged In: YES 
user_id=31435
I like Raymond's new pop(). Problems:
+ "speficied" is misspelled in the docstring.
+ Should be declared METH_O, not METH_VARARGS (mimic how, 
e.g., dict_update is set up).
+ The decrefs have to be reworked: a decref can trigger 
calls back into arbitrary Python code, due to __del__ 
methods getting invoked. This means you can never leave 
any live object in an insane or inconsistent state *during* 
a decref. What you need to do instead is first capture the 
key and value into local vrbls, plug dummy and NULL in to 
the dict slot, and decrement the used count. This leaves 
the dict in a consistent state again. Only then is it safe 
to decref the key and value.

Logged In: YES 
user_id=80475
Here is a revised patch for D.pop() incorporating Tim's 
ideas:
+ Docstring spelling fixed
+ Switched to METH_O instead of METH_VARARGS
+ Delayed decref until dict entry in consistent state
+ Removed unused int i=0 variable
+ Tabs replaced with spaces

Logged In: YES 
user_id=31435
Getting closer! Two more questions:
+ Why switch from tabs to spaces? The rest of this file 
uses hard tabs, and that's what Guido prefers in C source.
+ Think hard about whether we really want to decref the 
value -- I doubt we do, as we're *transferring* ownership 
of the value from the dict to the caller.

Logged In: YES 
user_id=80475
Here is a revised patch for D.pop() with hard tabs and 
corrected reference counts. In a DEBUG build, I validated 
the ref counts against equivalent steps: vv=d[k]; del d[k].
And, after Tim's suggestions, the code is fast and light.
In addition to d.pop(k), GvR's patch for d.popitem(k) 
should also go in. The (k,v) return value feeds directly 
into d.__setitem__ or a dict(itemlist) constructor (see the 
code fragments in the 4/6/02 post). The only downside is 
the time to process METH_VARARGS.

Logged In: YES 
user_id=6380
Thanks! Accepted and checked in.