[Patches] [ python-Patches-539949 ] dict.popitem(key=None)
noreply@sourceforge.net
noreply@sourceforge.net
Fri, 12 Apr 2002 08:12:15 -0700
Patches item #539949, was opened at 2002-04-05 14:38
You can respond by visiting:
http://sourceforge.net/tracker/?func=detail&atid=305470&aid=539949&group_id=5470
Category: Core (C code)
Group: Python 2.3
>Status: Closed
>Resolution: Accepted
Priority: 5
Submitted By: Raymond Hettinger (rhettinger)
Assigned to: Guido van Rossum (gvanrossum)
Summary: dict.popitem(key=None)
Initial Comment:
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.
----------------------------------------------------------------------
>Comment By: Guido van Rossum (gvanrossum)
Date: 2002-04-12 11:12
Message:
Logged In: YES
user_id=6380
Thanks! Accepted and checked in.
----------------------------------------------------------------------
Comment By: Raymond Hettinger (rhettinger)
Date: 2002-04-09 09:39
Message:
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.
----------------------------------------------------------------------
Comment By: Tim Peters (tim_one)
Date: 2002-04-08 12:46
Message:
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.
----------------------------------------------------------------------
Comment By: Raymond Hettinger (rhettinger)
Date: 2002-04-08 10:14
Message:
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
----------------------------------------------------------------------
Comment By: Tim Peters (tim_one)
Date: 2002-04-07 17:54
Message:
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.
----------------------------------------------------------------------
Comment By: Raymond Hettinger (rhettinger)
Date: 2002-04-06 22:00
Message:
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.
----------------------------------------------------------------------
Comment By: Neil Schemenauer (nascheme)
Date: 2002-04-06 20:51
Message:
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. :-)
----------------------------------------------------------------------
Comment By: Guido van Rossum (gvanrossum)
Date: 2002-04-06 20:16
Message:
Logged In: YES
user_id=6380
Not a bad idea, Neil! Care to work the code around to
implement that?
----------------------------------------------------------------------
Comment By: Neil Schemenauer (nascheme)
Date: 2002-04-06 20:14
Message:
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)
----------------------------------------------------------------------
Comment By: Raymond Hettinger (rhettinger)
Date: 2002-04-06 20:08
Message:
Logged In: YES
user_id=80475
The tests and documentation patches have been added.
----------------------------------------------------------------------
Comment By: Raymond Hettinger (rhettinger)
Date: 2002-04-06 12:23
Message:
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.
----------------------------------------------------------------------
Comment By: Tim Peters (tim_one)
Date: 2002-04-05 16:50
Message:
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?
----------------------------------------------------------------------
Comment By: Guido van Rossum (gvanrossum)
Date: 2002-04-05 16:47
Message:
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.
----------------------------------------------------------------------
Comment By: Guido van Rossum (gvanrossum)
Date: 2002-04-05 16:38
Message:
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.
----------------------------------------------------------------------
Comment By: Guido van Rossum (gvanrossum)
Date: 2002-04-05 16:26
Message:
Logged In: YES
user_id=6380
Now, if you could also upload a unittest and a doc patch,
that would be great!
----------------------------------------------------------------------
Comment By: Raymond Hettinger (rhettinger)
Date: 2002-04-05 16:10
Message:
Logged In: YES
user_id=80475
Context diff uploaded at poppatch.c below.
----------------------------------------------------------------------
Comment By: Guido van Rossum (gvanrossum)
Date: 2002-04-05 15:11
Message:
Logged In: YES
user_id=6380
Please upload a context or unified diff.
----------------------------------------------------------------------
You can respond by visiting:
http://sourceforge.net/tracker/?func=detail&atid=305470&aid=539949&group_id=5470