[Python-Dev] C coding experiment (original) (raw)

Andrew Durdin adurdin at gmail.com
Fri Sep 16 14:25:00 CEST 2005

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 setlookkey() 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?

More information about the Python-Dev mailing list