[Python-Dev] More compact dictionaries with faster iteration

[Antoine Pitrou]

Le Mon, 10 Dec 2012 11:16:49 -0500,
PJ Eby <pje at telecommunity.com> a écrit :

> On Mon, Dec 10, 2012 at 10:48 AM, Antoine Pitrou
> <solipsis at pitrou.net> wrote:
> > Le Mon, 10 Dec 2012 10:40:30 +0100,
> > Armin Rigo <arigo at tunes.org> a écrit :
> >> Hi Raymond,
> >>
> >> On Mon, Dec 10, 2012 at 2:44 AM, Raymond Hettinger
> >> <raymond.hettinger at gmail.com> 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'],
> >> >                 [-6480567542315338377, 'guido', 'blue']]
> >>
> >> 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 by
> >> the behavior of deletion. :-/
> >
> > If that's really an issue, we can deliberately scramble the
> > iteration order a bit :-) (of course it might negatively impact HW
> > prefetching)
> 
> 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.

I suspect that's what Raymond has in mind :-)

Regards

Antoine.