[Python-Dev] More compact dictionaries with faster iteration

[Antoine Pitrou]

Le Mon, 10 Dec 2012 18:17:57 -0500,
Raymond Hettinger <raymond.hettinger at gmail.com> a écrit :
> 
> On Dec 10, 2012, at 2:48 AM, Christian Heimes <christian at python.org>
> 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 alternative lookup
> functions based on whether the keys are all strings.
> The choice of lookup function is stored in a function pointer.
> That lets each lookup use the currently active lookup
> function without having to make any computations or branches.

An indirect function call is technically a branch, as seen from the CPU
(and not necessarily a very predictable one, although recent Intel
CPUs are said to be quite good at that).

Regards

Antoine.