[Python-Dev] C coding experiment

[Andrew Durdin]

On 9/1/05, Raymond Hettinger <raymond.hettinger at verizon.net> wrote:
> The goal is to determine whether the setobject.c implementation would be
> improved by recoding the set_lookkey() function to optimize key
> insertion order using Brent's variation of Algorithm D (See Knuth vol.
> III, section 6.4, page 525).

Brent's variation depends on the next probe position for a key being
derivable just from the key and its current position. The use of
perturbation in set_lookkey() prevents that, as we cannot say, given a
key at a certain position, where the next probe location for that key
would have been, without doing a complete lookup of that key
(obviously too expensive).

It would be interesting to see whether Brent's variation or
perturbation give better expected overall performance -- the latter
may well prove better in most cases, as it should reduce the number of
probes needed for both successful and unsuccessful lookups, while
Brent's variation only speeds up successful lookups. Well, this sort
of question is what the experiment is meant to resolve, no?