Re: [Python-Dev] More compact dictionaries with faster iteration

Hi all, On 1 January 2015 at 14:52, Maciej Fijalkowski wrote: > PS. I wonder who came up with the idea first, PHP or rhettinger and > who implemented it first (I'm pretty sure it was used in hippy before > it was used in Zend PHP) We'd need to look more in detail to that question, but a quick lo

Re: [Python-Dev] More compact dictionaries with faster iteration

On Wed, Dec 31, 2014 at 3:12 PM, Serhiy Storchaka wrote: > On 10.12.12 03:44, Raymond Hettinger wrote: >> >> The current memory layout for dictionaries is >> unnecessarily inefficient. It has a sparse table of >> 24-byte entries containing the hash value, key pointer, >> and value pointer. >> >>

Re: [Python-Dev] More compact dictionaries with faster iteration

On 10.12.12 03:44, Raymond Hettinger wrote: The current memory layout for dictionaries is unnecessarily inefficient. It has a sparse table of 24-byte entries containing the hash value, key pointer, and value pointer. Instead, the 24-byte entries should be stored in a dense table referenced by a

Re: [Python-Dev] More compact dictionaries with faster iteration

On Sun, May 19, 2013 at 7:27 AM, Raymond Hettinger wrote: > > On May 15, 2013, at 4:32 AM, Christian Tismer wrote: > > What is the current status of this discussion? > I'd like to know whether it is a considered alternative implementation. > > > As far as I can tell, I'm the only one working on i

Re: [Python-Dev] More compact dictionaries with faster iteration

On May 15, 2013, at 4:32 AM, Christian Tismer wrote: > What is the current status of this discussion? > I'd like to know whether it is a considered alternative implementation. As far as I can tell, I'm the only one working on it (and a bit slowly at that). My plan is to implement it for frozens

Re: [Python-Dev] More compact dictionaries with faster iteration

On Wed, May 15, 2013 at 2:36 PM, Christian Tismer wrote: > On 15.05.13 14:01, Stefan Drees wrote: >> >> Hi Chris, >> >> On 15.05.13 13:32 Christian Tismer wrote: >>> >>> Hi Raymond, >>> >>> On 08.01.13 15:49, Maciej Fijalkowski wrote: On Mon, Dec 10, 2012 at 3:44 AM, Raymond Hettinger >>

Re: [Python-Dev] More compact dictionaries with faster iteration

On 15.05.13 14:01, Stefan Drees wrote: Hi Chris, On 15.05.13 13:32 Christian Tismer wrote: Hi Raymond, On 08.01.13 15:49, Maciej Fijalkowski wrote: On Mon, Dec 10, 2012 at 3:44 AM, Raymond Hettinger wrote: The current memory layout for dictionaries is unnecessarily inefficient. It has a sp

Re: [Python-Dev] More compact dictionaries with faster iteration

Hi Chris, On 15.05.13 13:32 Christian Tismer wrote: Hi Raymond, On 08.01.13 15:49, Maciej Fijalkowski wrote: On Mon, Dec 10, 2012 at 3:44 AM, Raymond Hettinger wrote: The current memory layout for dictionaries is unnecessarily inefficient. It has a sparse table of 24-byte entries containing

Re: [Python-Dev] More compact dictionaries with faster iteration

Hi Raymond, On 08.01.13 15:49, Maciej Fijalkowski wrote: On Mon, Dec 10, 2012 at 3:44 AM, Raymond Hettinger wrote: The current memory layout for dictionaries is unnecessarily inefficient. It has a sparse table of 24-byte entries containing the hash value, key pointer, and value pointer. Inst

Re: [Python-Dev] More compact dictionaries with faster iteration

On Mon, Dec 10, 2012 at 3:44 AM, Raymond Hettinger wrote: > The current memory layout for dictionaries is > unnecessarily inefficient. It has a sparse table of > 24-byte entries containing the hash value, key pointer, > and value pointer. > > Instead, the 24-byte entries should be stored in a > d

Re: [Python-Dev] More compact dictionaries with faster iteration

On Mon, Jan 7, 2013 at 1:08 PM, Mark Shannon wrote: > > > On 07/01/13 10:55, Maciej Fijalkowski wrote: >> >> On Sun, Jan 6, 2013 at 11:40 PM, Kristján Valur Jónsson >> wrote: >>> >>> The memory part is also why I am interested in this approach. >>> Another thing has been bothering me. This is th

Re: [Python-Dev] More compact dictionaries with faster iteration

On 07/01/13 10:55, Maciej Fijalkowski wrote: On Sun, Jan 6, 2013 at 11:40 PM, Kristján Valur Jónsson wrote: The memory part is also why I am interested in this approach. Another thing has been bothering me. This is the fact that with the default implementation, the smll table is only ever p

Re: [Python-Dev] More compact dictionaries with faster iteration

On Sun, Jan 6, 2013 at 11:40 PM, Kristján Valur Jónsson wrote: > The memory part is also why I am interested in this approach. > Another thing has been bothering me. This is the fact that with the default > implementation, the smll table is only ever populated up to a certain > percentage, I ca

Re: [Python-Dev] More compact dictionaries with faster iteration

On Sun, Jan 6, 2013 at 10:40 PM, Kristján Valur Jónsson wrote: > A linear lookup in a handful of slots can't be that much of a bother, it is > only with larger number of entries that the O(1) property starts to matter. Something that I was thinking is if for small tables does make sense to actu

Re: [Python-Dev] More compact dictionaries with faster iteration

On Jan 6, 2013, at 1:40 PM, Kristján Valur Jónsson wrote: > The memory part is also why I am interested in this approach. > Another thing has been bothering me. This is the fact that with the default > implementation, the smll table is only ever populated up to a certain > percentage, I cant

Re: [Python-Dev] More compact dictionaries with faster iteration

On Jan 3, 2013, at 2:22 AM, Maciej Fijalkowski wrote: > Hello everyone. > > Thanks raymond for writing down a pure python version ;-) Thanks for running with it. > > I did an initial port to RPython for experiments. The results (on > large dicts only) are inconclusive - it's either a bit fas

Re: [Python-Dev] More compact dictionaries with faster iteration

er. K Frá: Python-Dev [python-dev-bounces+kristjan=ccpgames@python.org] fyrir hönd Maciej Fijalkowski [fij...@gmail.com] Sent: 5. janúar 2013 21:03 To: Antoine Pitrou Cc: Efni: Re: [Python-Dev] More compact dictionaries with faster iteration On Sat, Jan 5, 2013

Re: [Python-Dev] More compact dictionaries with faster iteration

On Sat, Jan 5, 2013 at 1:34 AM, Antoine Pitrou wrote: > On Thu, 3 Jan 2013 12:22:27 +0200 > Maciej Fijalkowski wrote: >> Hello everyone. >> >> Thanks raymond for writing down a pure python version ;-) >> >> I did an initial port to RPython for experiments. The results (on >> large dicts only) are

Re: [Python-Dev] More compact dictionaries with faster iteration

On Thu, 3 Jan 2013 12:22:27 +0200 Maciej Fijalkowski wrote: > Hello everyone. > > Thanks raymond for writing down a pure python version ;-) > > I did an initial port to RPython for experiments. The results (on > large dicts only) are inconclusive - it's either a bit faster or a bit > slower, dep

Re: [Python-Dev] More compact dictionaries with faster iteration

Hello everyone. Thanks raymond for writing down a pure python version ;-) I did an initial port to RPython for experiments. The results (on large dicts only) are inconclusive - it's either a bit faster or a bit slower, depending what exactly you do. There is a possibility I messed something up to

Re: [Python-Dev] More compact dictionaries with faster iteration

Good plan! On Tue, Dec 18, 2012 at 11:35 PM, Raymond Hettinger wrote: > > On Dec 11, 2012, at 1:13 AM, Antoine Pitrou wrote: > > > On Dec 10, 2012, at 2:48 AM, Christian Heimes > wrote: > > On the other hand every lookup and collision checks needs an > additional multiplication, addition and po

Re: [Python-Dev] More compact dictionaries with faster iteration

On Dec 11, 2012, at 1:13 AM, Antoine Pitrou wrote: >> >> On Dec 10, 2012, at 2:48 AM, Christian Heimes >> wrote: >> >>> On the other hand every lookup and collision checks needs an >>> additional multiplication, addition and pointer dereferencing: >>> >>> entry = entries_baseaddr + sizeof(Py

Re: [Python-Dev] More compact dictionaries with faster iteration

On 12/13/2012 06:11 AM, PJ Eby wrote: On Wed, Dec 12, 2012 at 5:06 PM, Dag Sverre Seljebotn wrote: Perfect hashing already separates "hash table" from "contents" (sort of), and saves the memory in much the same way. Yes, you can repeat the trick and have 2 levels of indirection, but that then

Re: [Python-Dev] More compact dictionaries with faster iteration

On Wed, Dec 12, 2012 at 5:06 PM, Dag Sverre Seljebotn wrote: > Perfect hashing already separates "hash table" from "contents" (sort of), > and saves the memory in much the same way. > > Yes, you can repeat the trick and have 2 levels of indirection, but that > then requires an additional table of

Re: [Python-Dev] More compact dictionaries with faster iteration

On 12/12/2012 11:06 PM, Dag Sverre Seljebotn wrote: On 12/12/2012 10:31 PM, PJ Eby wrote: On Wed, Dec 12, 2012 at 3:37 PM, Dag Sverre Seljebotn wrote: On 12/12/2012 01:15 AM, Nick Coghlan wrote: On Wed, Dec 12, 2012 at 5:37 AM, Dino Viehland mailto:di...@microsoft.com>> wrote: OTOH cha

Re: [Python-Dev] More compact dictionaries with faster iteration

On 12/12/2012 10:31 PM, PJ Eby wrote: On Wed, Dec 12, 2012 at 3:37 PM, Dag Sverre Seljebotn wrote: On 12/12/2012 01:15 AM, Nick Coghlan wrote: On Wed, Dec 12, 2012 at 5:37 AM, Dino Viehland mailto:di...@microsoft.com>> wrote: OTOH changing certain dictionaries in IronPython (such as key

Re: [Python-Dev] More compact dictionaries with faster iteration

On Wed, Dec 12, 2012 at 3:37 PM, Dag Sverre Seljebotn wrote: > On 12/12/2012 01:15 AM, Nick Coghlan wrote: >> >> On Wed, Dec 12, 2012 at 5:37 AM, Dino Viehland > > wrote: >> >> OTOH changing certain dictionaries in IronPython (such as keyword >> args) to be >>

Re: [Python-Dev] More compact dictionaries with faster iteration

On 12/12/2012 01:15 AM, Nick Coghlan wrote: On Wed, Dec 12, 2012 at 5:37 AM, Dino Viehland mailto:di...@microsoft.com>> wrote: OTOH changing certain dictionaries in IronPython (such as keyword args) to be ordered would certainly be possible. Personally I just wouldn't want to se

Re: [Python-Dev] More compact dictionaries with faster iteration

On Wed, Dec 12, 2012 at 5:37 AM, Dino Viehland wrote: > OTOH changing certain dictionaries in IronPython (such as keyword args) to > be > ordered would certainly be possible. Personally I just wouldn't want to > see it > be the default as that seems like unnecessary overhead when the specialized

Re: [Python-Dev] More compact dictionaries with faster iteration

PJ wrote: > Actually, IronPython may already have ordered dictionaries by default; see: > > http://mail.python.org/pipermail/ironpython-users/2006- > May/002319.html > > It's described as an implementation detail that may change, perhaps that > could be changed to being unchanging. ;-) > I t

Re: [Python-Dev] More compact dictionaries with faster iteration

Yet some comments about your Python implementation. 1. Don't use "is FREE" and "is DUMMY" as array doesn't preserve identity. 2. Wrong limits used in _make_index(): 128 overflows 'b', 65536 overflows 'h' and 'l' can be not enough for ssize_t. 3. round_upto_powtwo() can be implemented as 1 <<

Re: [Python-Dev] More compact dictionaries with faster iteration

Le Tue, 11 Dec 2012 08:41:32 +, Mark Shannon a écrit : > > > > If you have a suggested allocation pattern or other > > constructive suggestion, it would be would welcome. > It seems like a reasonable starting point. > Trying to avoid resizing the index array and the entries array at the > sam

Re: [Python-Dev] More compact dictionaries with faster iteration

Le Mon, 10 Dec 2012 18:17:57 -0500, Raymond Hettinger a écrit : > > On Dec 10, 2012, at 2:48 AM, Christian Heimes > wrote: > > > On the other hand every lookup and collision checks needs an > > additional multiplication, addition and pointer dereferencing: > > > > entry = entries_baseaddr + s

Re: [Python-Dev] More compact dictionaries with faster iteration

On 11/12/12 03:45, Raymond Hettinger wrote: On Dec 10, 2012, at 7:04 PM, Mark Shannon mailto:m...@hotpy.org>> wrote: Another approach is to pre-allocate the two-thirds maximum (This is simple and fast but gives the smallest space savings.) What do you mean by maximum? A dict with an index

Re: [Python-Dev] More compact dictionaries with faster iteration

On Dec 10, 2012, at 4:02 AM, Serhiy Storchaka wrote: > On 10.12.12 05:30, Raymond Hettinger wrote: >> On Dec 9, 2012, at 10:03 PM, MRAB > > wrote: >>> What happens when a key is deleted? Will that leave an empty slot in >>> the entry array? >> Yes. See the __d

Re: [Python-Dev] More compact dictionaries with faster iteration

On Mon, Dec 10, 2012 at 08:53:17AM -0800, Barry Warsaw wrote: > On Dec 10, 2012, at 05:39 PM, Christian Heimes wrote: > > >I had ARM platforms in mind, too. Unfortunately we don't have any ARM > >platforms for testing and performance measurement. Even Trent's > >Snakebite doesn't have ARM boxes. I

Re: [Python-Dev] More compact dictionaries with faster iteration

On Dec 10, 2012, at 7:04 PM, Mark Shannon wrote: >> Another approach is to pre-allocate the two-thirds maximum >> (This is simple and fast but gives the smallest space savings.) > > What do you mean by maximum? A dict with an index table size of 8 gets resized when it is two-thirds full, so th

Re: [Python-Dev] More compact dictionaries with faster iteration

On 10/12/12 23:39, Raymond Hettinger wrote: On Dec 10, 2012, at 4:06 AM, Mark Shannon mailto:m...@hotpy.org>> wrote: Instead, the 24-byte entries should be stored in a dense table referenced by a sparse table of indices. What minimum size and resizing factor do you propose for the entries

Re: [Python-Dev] More compact dictionaries with faster iteration

On Dec 10, 2012, at 1:38 PM, PJ Eby wrote: > 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 expec

Re: [Python-Dev] More compact dictionaries with faster iteration

On Dec 10, 2012, at 4:06 AM, Mark Shannon wrote: >> Instead, the 24-byte entries should be stored in a >> dense table referenced by a sparse table of indices. > > What minimum size and resizing factor do you propose for the entries array? There are many ways to do this. I don't know which is

Re: [Python-Dev] More compact dictionaries with faster iteration

On Mon, Dec 10, 2012 at 3:13 PM, fwierzbi...@gmail.com wrote: > On Mon, Dec 10, 2012 at 10:01 AM, Armin Rigo wrote: >> 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

Re: [Python-Dev] More compact dictionaries with faster iteration

On Dec 10, 2012, at 2:48 AM, Christian Heimes wrote: > On the other hand every lookup and collision checks needs an additional > multiplication, addition and pointer dereferencing: > > entry = entries_baseaddr + sizeof(PyDictKeyEntry) * idx Currently, the dict implementation allows alternati

Re: [Python-Dev] More compact dictionaries with faster iteration

On Mon, Dec 10, 2012 at 10:01 AM, Armin Rigo wrote: > 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 Jy

Re: [Python-Dev] More compact dictionaries with faster iteration

On Mon, Dec 10, 2012 at 5:14 PM, Andrew Svetlov wrote: > Please, no. dict and kwargs should be unordered without any assumptions. Why? ___ Python-Dev mailing list Python-Dev@python.org http://mail.python.org/mailman/listinfo/python-dev Unsubscribe: htt

Re: [Python-Dev] More compact dictionaries with faster iteration

On Mon, Dec 10, 2012 at 4:29 PM, Tim Delaney wrote: > Whilst I think Python should not move to ordered dictionaries everywhere, I > would say there is an argument (no pun intended) for making **kwargs a > dictionary that maintains insertion order *if there are no deletions*. Oooh. Me likey. The

Re: [Python-Dev] More compact dictionaries with faster iteration

On Mon, Dec 10, 2012 at 11:29 PM, Tim Delaney wrote: > On 11 December 2012 05:01, Armin Rigo wrote: >> >> Hi Philip, >> >> On Mon, Dec 10, 2012 at 5:16 PM, PJ Eby wrote: >> > On the other hand, this would also make a fast ordered dictionary >> > subclass possible, just by not using the free list

Re: [Python-Dev] More compact dictionaries with faster iteration

On 11 December 2012 05:01, Armin Rigo wrote: > Hi Philip, > > On Mon, Dec 10, 2012 at 5:16 PM, PJ Eby 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 ad

Re: [Python-Dev] More compact dictionaries with faster iteration

On 12/10/2012 1:38 PM, PJ Eby wrote: On Mon, Dec 10, 2012 at 1:01 PM, Armin Rigo wrote: On Mon, Dec 10, 2012 at 5:16 PM, PJ Eby 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 com

Re: [Python-Dev] More compact dictionaries with faster iteration

On Mon, 10 Dec 2012 11:53:17 -0500 Barry Warsaw wrote: > On Dec 10, 2012, at 05:39 PM, Christian Heimes wrote: > > >I had ARM platforms in mind, too. Unfortunately we don't have any ARM > >platforms for testing and performance measurement. Even Trent's > >Snakebite doesn't have ARM boxes. I've a

Re: [Python-Dev] More compact dictionaries with faster iteration

On Mon, Dec 10, 2012 at 1:01 PM, Armin Rigo wrote: > On Mon, Dec 10, 2012 at 5:16 PM, PJ Eby 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 d

Re: [Python-Dev] More compact dictionaries with faster iteration

On Mon, 10 Dec 2012 16:06:23 +, krist...@ccpgames.com wrote: > Indeed, I had to change the dict tuning parameters to make dicts > behave reasonably on the PS3. > > Interesting stuff indeed. Out of both curiosity and a possible application of my own for the information, what values did you end

Re: [Python-Dev] More compact dictionaries with faster iteration

Hi Philip, On Mon, Dec 10, 2012 at 5:16 PM, PJ Eby 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 swit

Re: [Python-Dev] More compact dictionaries with faster iteration

On Dec 10, 2012, at 05:39 PM, Christian Heimes wrote: >I had ARM platforms in mind, too. Unfortunately we don't have any ARM >platforms for testing and performance measurement. Even Trent's >Snakebite doesn't have ARM boxes. I've a first generation Raspberry Pi, >that's all. I have a few ARM mach

Re: [Python-Dev] More compact dictionaries with faster iteration

2 15:28 > To: python-dev@python.org > Subject: Re: [Python-Dev] More compact dictionaries with faster iteration > > I'd be interested to see what effect this has on memory constrained > platforms such as many current ARM applications (mostly likely 32bit for > now). Python&#

Re: [Python-Dev] More compact dictionaries with faster iteration

Am 10.12.2012 16:28, schrieb Barry Warsaw: > I'd be interested to see what effect this has on memory constrained platforms > such as many current ARM applications (mostly likely 32bit for now). Python's > memory consumption is an overheard complaint for folks developing for those > platforms. I h

Re: [Python-Dev] More compact dictionaries with faster iteration

On Mon, Dec 10, 2012 at 10:28 AM, Barry Warsaw wrote: > On Dec 10, 2012, at 08:48 AM, Christian Heimes wrote: > > >It's hard to predict how the extra CPU instructions are going to affect > >the performance on different CPUs and scenarios. My guts tell me that > >your proposal is going to perform

Re: [Python-Dev] More compact dictionaries with faster iteration

Le Mon, 10 Dec 2012 11:16:49 -0500, PJ Eby a écrit : > On Mon, Dec 10, 2012 at 10:48 AM, Antoine Pitrou > wrote: > > Le Mon, 10 Dec 2012 10:40:30 +0100, > > Armin Rigo a écrit : > >> Hi Raymond, > >> > >> On Mon, Dec 10, 2012 at 2:44 AM, Raymond Hettinger > >> wrote: > >> > Instead, the data s

Re: [Python-Dev] More compact dictionaries with faster iteration

On Mon, Dec 10, 2012 at 10:48 AM, Antoine Pitrou wrote: > Le Mon, 10 Dec 2012 10:40:30 +0100, > Armin Rigo a écrit : >> Hi Raymond, >> >> On Mon, Dec 10, 2012 at 2:44 AM, Raymond Hettinger >> wrote: >> > Instead, the data should be organized as follows: >> > >> > indices = [None, 1, None, N

Re: [Python-Dev] More compact dictionaries with faster iteration

On 10/12/12 20:40, Armin Rigo wrote: As a side note, your suggestion also enables order-preserving dictionaries: iter() would automatically yield items in the order they were inserted, as long as there was no deletion. People will immediately start relying on this "feature"... and be confused

Re: [Python-Dev] More compact dictionaries with faster iteration

Le Mon, 10 Dec 2012 10:40:30 +0100, Armin Rigo a écrit : > Hi Raymond, > > On Mon, Dec 10, 2012 at 2:44 AM, Raymond Hettinger > wrote: > > Instead, the data should be organized as follows: > > > > indices = [None, 1, None, None, None, 0, None, 2] > > entries = [[-9092791511155847987, '

Re: [Python-Dev] More compact dictionaries with faster iteration

On Dec 10, 2012, at 08:48 AM, Christian Heimes wrote: >It's hard to predict how the extra CPU instructions are going to affect >the performance on different CPUs and scenarios. My guts tell me that >your proposal is going to perform better on modern CPUs with lots of L1 >and L2 cache and in an ave

Re: [Python-Dev] More compact dictionaries with faster iteration

Hi! 2012/12/10 Armin Rigo > Hi Raymond, > > On Mon, Dec 10, 2012 at 2:44 AM, Raymond Hettinger > wrote: > > Instead, the data should be organized as follows: > > > > indices = [None, 1, None, None, None, 0, None, 2] > > entries = [[-9092791511155847987, 'timmy', 'red'], > >

Re: [Python-Dev] More compact dictionaries with faster iteration

Hi Raymond, On Mon, Dec 10, 2012 at 2:44 AM, Raymond Hettinger wrote: > Instead, the data should be organized as follows: > > indices = [None, 1, None, None, None, 0, None, 2] > entries = [[-9092791511155847987, 'timmy', 'red'], > [-8522787127447073495, 'barry', 'green']

Re: [Python-Dev] More compact dictionaries with faster iteration

On 10/12/12 01:44, Raymond Hettinger wrote: The current memory layout for dictionaries is unnecessarily inefficient. It has a sparse table of 24-byte entries containing the hash value, key pointer, and value pointer. Instead, the 24-byte entries should be stored in a dense table referenced by a

Re: [Python-Dev] More compact dictionaries with faster iteration

On 10.12.12 09:48, Christian Heimes wrote: On the other hand every lookup and collision checks needs an additional multiplication, addition and pointer dereferencing: entry = entries_baseaddr + sizeof(PyDictKeyEntry) * idx I think that main slowdown will be in getting index from array with

Re: [Python-Dev] More compact dictionaries with faster iteration

On 10.12.12 05:30, Raymond Hettinger wrote: On Dec 9, 2012, at 10:03 PM, MRAB mailto:pyt...@mrabarnett.plus.com>> wrote: What happens when a key is deleted? Will that leave an empty slot in the entry array? Yes. See the __delitem__() method in the pure python implemention at http://code.active

Re: [Python-Dev] More compact dictionaries with faster iteration

Hello Raymond Am 10.12.2012 02:44, schrieb Raymond Hettinger: > Another benefit is that resizing is faster and > touches fewer pieces of memory. Currently, every > hash/key/value entry is moved or copied during a > resize. In the new layout, only the indices are > updated. For the most part, t

Re: [Python-Dev] More compact dictionaries with faster iteration

On Sun, Dec 9, 2012 at 5:44 PM, Raymond Hettinger < raymond.hettin...@gmail.com> wrote: > The current memory layout for dictionaries is > unnecessarily inefficient. It has a sparse table of > 24-byte entries containing the hash value, key pointer, > and value pointer. > > Instead, the 24-byte ent

Re: [Python-Dev] More compact dictionaries with faster iteration

On Dec 9, 2012, at 10:03 PM, MRAB wrote: > What happens when a key is deleted? Will that leave an empty slot in > the entry array? Yes. See the __delitem__() method in the pure python implemention at http://code.activestate.com/recipes/578375 > If so, will the array be compacted if the propor

Re: [Python-Dev] More compact dictionaries with faster iteration

On 2012-12-10 01:44, Raymond Hettinger wrote: The current memory layout for dictionaries is unnecessarily inefficient. It has a sparse table of 24-byte entries containing the hash value, key pointer, and value pointer. Instead, the 24-byte entries should be stored in a dense table referenced by

[Python-Dev] More compact dictionaries with faster iteration

The current memory layout for dictionaries is unnecessarily inefficient. It has a sparse table of 24-byte entries containing the hash value, key pointer, and value pointer. Instead, the 24-byte entries should be stored in a dense table referenced by a sparse table of indices. For example, the di