Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.python > #84581
| From | Terry Reedy <tjreedy@udel.edu> |
|---|---|
| Subject | Re: __bases__ misleading error message |
| Date | 2015-01-25 16:35 -0500 |
| References | (1 earlier) <54c39366$0$13006$c3e8da3$5496439d@news.astraweb.com> <MPG.2f2e298c14dbed69989692@nntp.aioe.org> <54c4606a$0$13002$c3e8da3$5496439d@news.astraweb.com> <MPG.2f2eecca37bc450998969a@nntp.aioe.org> <54c4dae1$0$13005$c3e8da3$5496439d@news.astraweb.com> |
| Newsgroups | comp.lang.python |
| Message-ID | <mailman.18135.1422221769.18130.python-list@python.org> (permalink) |
On 1/25/2015 7:00 AM, Steven D'Aprano wrote:
> What happens inside the dictionary? Dictionaries are "hash tables", so they
> are basically a big array of cells, and each cell is a pair of pointers,
> one for the key and one for the value:
>
> [dictionary header]
> [blank]
> [blank]
> [ptr to the string 'y', ptr to the int 42]
At the moment, for CPython, each entry has 3 items, with the first being
the cached hash of the key. Hash comparison is first used to test
whether keys are equal.
[hash('y'), ptr('y'), ptr(42)]
> [blank]
> [ptr to 'x', ptr to 23]
> [blank]
> [blank]
> [blank]
> [ptr to 'colour', ptr to 'red']
> [blank]
As you say, these are implementation details. CPython dicts for the
instances of at least some classes have a different, specialized
structure, with two arrays.
In the above, [blank] entries, which are about 1/2 to 2/3 of the
entries, take the same space as real entries (12 to 24 bytes). Raymond
H. has proposed that the standard dict have two arrays like so:
1. the first array is a sparse array of indexes into the second array:
[b, b, 2, b, 0, b, b, b, 1, b] (where b might be -1 interpreted as
<blank>), using only as many bytes as needed for the maximum index.
2. the second array is a compact array of entries in insertion order,
such as
[hash, ptr to 'x', ptr to 23]
[hash, ptr to 'colour', ptr to 'red']
[hash, ptr to the string 'y', ptr to the int 42]
Iteration would use the compact array, making all dicts OrderedDicts.
Pypy has already switched to this. It seems that on modern processors
with multilevel on-chip caches, the space reduction leads to cache-miss
reductions that compensate for the indirection cost.
--
Terry Jan Reedy
Back to comp.lang.python | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
__bases__ misleading error message Mario Figueiredo <marfig@gmail.com> - 2015-01-24 10:16 +0000
Re: __bases__ misleading error message Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-01-24 23:43 +1100
Re: __bases__ misleading error message Mario Figueiredo <marfig@gmail.com> - 2015-01-24 22:14 +0100
Re: __bases__ misleading error message Ian Kelly <ian.g.kelly@gmail.com> - 2015-01-24 14:45 -0700
Re: __bases__ misleading error message Mario Figueiredo <marfig@gmail.com> - 2015-01-24 23:09 +0100
Re: __bases__ misleading error message Chris Angelico <rosuav@gmail.com> - 2015-01-25 09:25 +1100
Re: __bases__ misleading error message Mario Figueiredo <marfig@gmail.com> - 2015-01-24 23:33 +0100
Re: __bases__ misleading error message Chris Angelico <rosuav@gmail.com> - 2015-01-25 09:37 +1100
Re: __bases__ misleading error message Mario Figueiredo <marfig@gmail.com> - 2015-01-24 23:59 +0100
Re: __bases__ misleading error message Terry Reedy <tjreedy@udel.edu> - 2015-01-24 16:58 -0500
Re: __bases__ misleading error message Mario Figueiredo <marfig@gmail.com> - 2015-01-24 23:02 +0100
Re: __bases__ misleading error message Ian Kelly <ian.g.kelly@gmail.com> - 2015-01-24 15:16 -0700
Re: __bases__ misleading error message Mario Figueiredo <marfig@gmail.com> - 2015-01-24 23:36 +0100
Re: __bases__ misleading error message Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-01-25 14:18 +1100
Re: __bases__ misleading error message Mario Figueiredo <marfig@gmail.com> - 2015-01-25 12:07 +0100
Re: __bases__ misleading error message Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-01-25 23:00 +1100
Re: __bases__ misleading error message Mario Figueiredo <marfig@gmail.com> - 2015-01-25 13:49 +0100
Re: __bases__ misleading error message Marko Rauhamaa <marko@pacujo.net> - 2015-01-25 14:53 +0200
Re: __bases__ misleading error message Terry Reedy <tjreedy@udel.edu> - 2015-01-25 16:35 -0500
Re: __bases__ misleading error message Ian Kelly <ian.g.kelly@gmail.com> - 2015-01-25 19:21 -0700
Re: __bases__ misleading error message Marco Buttu <marco.buttu@gmail.com> - 2015-01-24 23:09 +0100
Re: __bases__ misleading error message Marco Buttu <marco.buttu@gmail.com> - 2015-01-24 15:12 +0100
Re: __bases__ misleading error message Terry Reedy <tjreedy@udel.edu> - 2015-01-24 14:24 -0500
Re: __bases__ misleading error message Mario Figueiredo <marfig@gmail.com> - 2015-01-24 22:03 +0100
Re: __bases__ misleading error message Marco Buttu <marco.buttu@gmail.com> - 2015-01-24 22:51 +0100
Re: __bases__ misleading error message Terry Reedy <tjreedy@udel.edu> - 2015-01-24 19:55 -0500
Re: __bases__ misleading error message Marco Buttu <marco.buttu@gmail.com> - 2015-01-25 11:30 +0100
Re: __bases__ misleading error message Marco Buttu <marco.buttu@gmail.com> - 2015-01-24 22:51 +0100
csiph-web