5 ms·

Python: hash, id and Dictionary Order

9 points by Nurdok 13y ago

civilian 13y ago
Really interesting about the internals of python! One of the first things the professor of my python class told us is that python dictionaries don't guarantee any order. So that's just always been in mind. It almost seems like a PHP-ism to assume that a dictionary would provide that. Understand thy data-types! # edit: And yeah-- I don't know why the stackoverflow link was the place to go. I don't like "RTFM" culture, but it was right there: http://docs.python.org/2/tutorial/datastructures.html#dictionaries http://docs.python.org/2/tutorial/datastructures.html#dictio... and also here in the book I learned python from: http://www.greenteapress.com/thinkpython/html/thinkpython012.html http://www.greenteapress.com/thinkpython/html/thinkpython012...
gus_massa 13y ago
The analysis about the internal details is interesting, but it's not surprising, from http://docs.python.org/2/library/stdtypes.html#dict.items http://docs.python.org/2/library/stdtypes.html#dict.items : > CPython implementation detail: Keys and values are listed in an arbitrary order which is non-random, varies across Python implementations, and depends on the dictionary’s history of insertions and deletions.
DrJosiah 13y ago
Python will generally use the system allocation functions (unless it knows more about the objects and whether they can be bulk allocated and used in freelists), and a given Python class (which is what you are creating) will have alignment that depends on its size and what the platform returns for a block of memory of sufficient size to fit the object. What do I mean? Say that you need to allocate 63 bytes of memory. No memory allocator will give you 63 bytes, you will actually get 64 or maybe more. Why? Because if you allocate 63, then the implication is that some other call to the allocator will return a memory offset just after your 63 bytes, leaving it unaligned WRT platform alignment expectations (which is 4 or 8 byte alignment for platforms I am familiar with). If it so happens that the classes you are building (the A, B, C, ... classes) are aligned on 128 byte boundaries, then it's likely that the allocator has put each class into a block size of 128 bytes. What would go into that 128 bytes? Refcounts, reference to the class dictionary (if any), reference to a __slots__ object, the base classes, etc. There is likely unused bytes in the tail end of that 128 byte block, and in some cases, empty space within the block (some 64 bit platforms require 8-byte alignment, even when a structure has 1, 2, or 4 byte integers). But yeah. Don't rely on dictionary ordering, and don't rely on 128 byte alignment of your classes.
- michaelmior 13y ago
  If you need ordering, just use collections.OrderedDict :)
  - DrJosiah 13y ago
    I knew about it before it was in the standard library, but thanks.

9 points by Nurdok 13y ago

Really interesting about the internals of python! One of the first things the professor of my python class told us is that python dictionaries don't guarantee any order. So that's just always been in mind. It almost seems like a PHP-ism to assume that a dictionary would provide that. Understand thy data-types! # edit: And yeah-- I don't know why the stackoverflow link was the place to go. I don't like "RTFM" culture, but it was right there: http://docs.python.org/2/tutorial/datastructures.html#dictionaries http://docs.python.org/2/tutorial/datastructures.html#dictio... and also here in the book I learned python from: http://www.greenteapress.com/thinkpython/html/thinkpython012.html http://www.greenteapress.com/thinkpython/html/thinkpython012...

gus_massa 13y ago

The analysis about the internal details is interesting, but it's not surprising, from http://docs.python.org/2/library/stdtypes.html#dict.items http://docs.python.org/2/library/stdtypes.html#dict.items : > CPython implementation detail: Keys and values are listed in an arbitrary order which is non-random, varies across Python implementations, and depends on the dictionary’s history of insertions and deletions.

DrJosiah 13y ago

Python will generally use the system allocation functions (unless it knows more about the objects and whether they can be bulk allocated and used in freelists), and a given Python class (which is what you are creating) will have alignment that depends on its size and what the platform returns for a block of memory of sufficient size to fit the object. What do I mean? Say that you need to allocate 63 bytes of memory. No memory allocator will give you 63 bytes, you will actually get 64 or maybe more. Why? Because if you allocate 63, then the implication is that some other call to the allocator will return a memory offset just after your 63 bytes, leaving it unaligned WRT platform alignment expectations (which is 4 or 8 byte alignment for platforms I am familiar with). If it so happens that the classes you are building (the A, B, C, ... classes) are aligned on 128 byte boundaries, then it's likely that the allocator has put each class into a block size of 128 bytes. What would go into that 128 bytes? Refcounts, reference to the class dictionary (if any), reference to a __slots__ object, the base classes, etc. There is likely unused bytes in the tail end of that 128 byte block, and in some cases, empty space within the block (some 64 bit platforms require 8-byte alignment, even when a structure has 1, 2, or 4 byte integers). But yeah. Don't rely on dictionary ordering, and don't rely on 128 byte alignment of your classes.

michaelmior 13y ago
If you need ordering, just use collections.OrderedDict :)
- DrJosiah 13y ago
  I knew about it before it was in the standard library, but thanks.