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. _______________________________________________ Python-Dev mailing list Python-Dev@python.org http://mail.python.org/mailman/listinfo/python-dev Unsubscribe: http://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com
