To be fair, the text below just shows that Dictionary / Set in Pharo
degrade from O(1) to O(n) as it has to search through all the elements
in the Set/Dictionary. It's not that those high factors are constants
because of better implementation. Pinocchio dictionaries just stay O(1).
The only way to degrade Pinocchio dictionaries is by giving it bad
hashes; but that's something you can't solve in all cases anyway.
cheers,
Toon
This forces the dictionary to miss a lot more often. Since all the
keys are grouped together this is the worst case for Squeak/Pharo
dictionaries if you want to look something up that's not there. This
are the results on Squeak 4.1:
PBDictionary 0.0261 +/-0.0017
PBSTDictionary 5.235 +/-0.01
So around 200x faster in case of PDictionary.
While PDictionary stays stable (even slightly faster, go figure),
Squeak dictionaries degrade immensely! On Pharo the results are a bit
better, but still very much degraded:
PBDictionary 0.02387 +/-0.00014
PBSTDictionary 1.6577 +/-0.0036
So around 60x faster in case of PDictionary.
If on Set I ensure that all elements will be found, I get the
following result for #includes:
PBSetIncludes 0.00440 +/-0.0001100000000000001
PBSTSetIncludes 0.004000 +/-9.6e-5
making PSet marginally slower. However, once you start not finding
elements, with the same change as before, (to: size*10 by: 10):
PBSetIncludes 0.00443 +/-0.0001
PBSTSetIncludes 0.9844000000000005 +/-0.0017
So around 220x faster in case of PSet. While PSet and PDictionary
never really suffer from collisions, normal Squeak/Pharo dictionaries
suffer immensely and grow up to 200x slower. Btw, this last benchmark
was run on Pharo.
_______________________________________________
Pharo-project mailing list
[email protected]
http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
