[Python-Dev] C coding experiment

[Antoine Pitrou]

Hi,

> 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).

I've been experimenting on this subject with Raymond H.
You will find some code here: http://pitrou.net/python/sets/
  - hash1.py is an algorithmic simulation of the current set
implementation; it will give you statistics about e.g. the number of
table walks in various test cases (that you can customize, of course)
  - hash2.py is a very crude benchmark of the set implementation
  - brent-patch.txt is a patch against CPython CVS to add Brent's
variation to the set implementation; it made hash2.py between 5% slower
and 2% faster depending on the test case

I believe Raymond has since started experimenting on other approaches.

Regards

Antoine.