[Python-Dev] More compact dictionaries with faster iteration (original) (raw)

Terry Reedy tjreedy at udel.edu
Mon Dec 10 21:50:15 CET 2012

On 12/10/2012 1:38 PM, PJ Eby wrote:

On Mon, Dec 10, 2012 at 1:01 PM, Armin Rigo <arigo at tunes.org> wrote:

On Mon, Dec 10, 2012 at 5:16 PM, PJ Eby <pje at telecommunity.com> wrote:

On the other hand, this would also make a fast ordered dictionary subclass possible, just by not using the free list for additions, combined with periodic compaction before adds or after deletes.

Technically, I could see Python switching to ordered dictionaries everywhere. Raymond's insight suddenly makes it easy for CPython and PyPy, and at least Jython could use the LinkedHashMap class (although this would need checking with Jython guys). What about IronPython? Also, note that using ordered dictionaries carries a performance cost for dictionaries whose keys change a lot. This probably wouldn't affect most dictionaries in most programs, because module and object dictionaries generally don't delete and re-add a lot of keys very often. But in cases where a dictionary is used as a queue or stack or something of that sort, the packing costs could add up. Under the current scheme, as long as collisions were minimal, the contents wouldn't be repacked very often. Without numbers it's hard to say for certain, but the advantage to keeping ordered dictionaries a distinct type is that the standard dictionary type can then get that extra bit of speed in exchange for dropping the ordering requirement.

I think that there should be a separate OrderedDict class (or subclass) and that the dict docs should warn (if not now) that while iterating a dict may, in some circumstances, give items in insertion or sort order, it will not in all cases. Example of the latter:

d = {8:0, 9:0, 15:0, 13:0, 14:0} for k in d: print(k)

8 9 13 14 15

If one entered the keys in sorted order, as might be natural, one might mistakenly think that insertion order was being reproduced.

-- Terry Jan Reedy

More information about the Python-Dev mailing list