Begin forwarded message:
From: Levente Uzonyi <leves@elte.hu> Date: October 30, 2009 3:29:33 AM GMT+01:00 To: Ralph Boland <rpboland@gmail.com> Cc: Stéphane Ducasse <stephane.ducasse@inria.fr> Subject: Re: Adding FasterSets to Pharo: update
Hi!
On Thu, 29 Oct 2009, Ralph Boland wrote:
In Levente's code class WeakKeyToCollectionDictionary->rehash seems to be missing. This appears to be a mistate to me but I will live it to Levente to explain it. The fix, if needed, is simple.
Only Set and MethodDictionary implements #rehash in the trunk version. #rehash sends #growTo: which sends #noCheckNoGrowFillFrom: which is implemented by WeakKeyToCollectionDictionary.
b) Levente's version does not use method scanForNilFrom: (He would probably call the method scanForEmptySlotFrom:). I don't know why he didn't do this: it clearly cleaner.
It's called #scanForEmptySlotFor:, because WeakSet has a flag for empty slots, not nil.
b) The improvement in performance for method add: in Levente's version is insignificant (appx 1%); this difference could easily be made up in minor changes to my code. Thus here I consider there to be no difference.
Don't let the garbage collector fool you. See http://leves.web.elte.hu/collections/DictionaryBenchmarkResults.txt . The values in the table are microseconds/element without gc time. The benchmark code is here http://leves.web.elte.hu/collections/DictionaryBenchmark.st A similar benchmark's result for Set:
Trunk: Size 1000 2000 5000 10000 20000 50000 100000 200000 500000 add: (included) 0.5 0.2 0.36 0.46 0.365 0.392 0.394 0.406 0.4112 add: (not included) 1.5 1.6 1.38 1.35 1.365 1.25 1.261 1.252 1.5192 includes: (included) 0.3 0.5 0.42 0.41 0.395 0.432 0.457 0.4695 0.4442 includes: (not included) 0.2 0.5 0.56 0.51 0.51 0.632 0.66 0.6525 0.5994 like: (included) 0.5 0.4 0.4 0.36 0.345 0.37 0.393 0.4105 0.3854 like: (not included) 0.4 0.45 0.52 0.44 0.445 0.566 0.593 0.5895 0.536 rehash 0.5 0.4 0.32 0.33 0.33 0.338 0.342 0.326 0.3386 remove:ifAbsent: (included) 0.7 0.95 1.02 0.99 1.015 1.228 1.238 1.2485 0.9282 remove:ifAbsent: (not included) 0.4 0.5 0.58 0.54 0.575 0.686 0.699 0.6985 0.6586
Pharo: Size 1000 2000 5000 10000 20000 50000 100000 200000 500000 add: (included) 0.4 0.45 0.5 0.45 0.44 0.462 0.465 0.4705 0.499 add: (not included) 2.0 2.0 1.72 1.67 1.715 1.57 1.582 1.57 2.0874 includes: (included) 0.5 0.5 0.56 0.6 0.52 0.52 0.547 0.5335 0.5814 includes: (not included) 0.7 0.85 0.8 1.03 0.865 0.804 0.804 0.8265 0.8734 like: (included) 0.7 0.45 0.4 0.5 0.395 0.382 0.399 0.3935 0.4208 like: (not included) 0.3 0.65 0.66 0.9 0.705 0.66 0.659 0.679 0.783 rehash 0.9 0.6 0.64 0.69 0.63 0.604 0.615 0.6285 0.6964 remove:ifAbsent: (included) 2.0 1.95 2.16 6.59 2.165 2.052 1.981 2.092 2.0544 remove:ifAbsent: (not included) 0.9 0.85 0.92 1.05 0.9 0.84 0.878 0.869 1.0232
Pharo with Andres's hacks: Size 1000 2000 5000 10000 20000 50000 100000 200000 500000 add: (included) 0.5 0.5 0.46 0.49 0.475 0.466 0.458 0.4935 0.5306 add: (not included) 1.7 2.35 2.26 2.02 2.15 2.12 2.298 2.021 2.0332 includes: (included) 0.6 0.5 0.56 0.53 0.62 0.528 0.539 0.533 0.588 includes: (not included) 0.8 0.8 0.74 0.77 0.745 0.7 0.694 0.706 0.7814 like: (included) 0.1 0.2 0.36 0.4 0.485 0.386 0.39 0.382 0.4312 like: (not included) 0.4 0.8 0.6 0.66 0.605 0.576 0.566 0.5835 0.6554 rehash 0.6 0.55 0.62 0.58 0.575 0.586 0.599 0.5825 0.6044 remove:ifAbsent: (included) 1.5 1.95 1.86 1.97 1.905 1.786 1.763 1.8005 1.9346 remove:ifAbsent: (not included) 0.7 0.75 0.82 0.82 0.84 0.774 0.771 0.7755 0.8418
If you're interrested in the benchmark code, let me know.
b) Levente's version does not apply the FasterSets idea to MethodDictionary. I am not sure why he did not do this but it may have something to do with the fact that mistakes can easily corrupt your image. The version in FasterSets works fine though it took three tries for me to get it right (mostly because of carelessness).
It would be easy to modify MethodDictionary, but it has a different implementation, so most methods would have to be overridden and the performance benefits would be insignificant, because #become: is much (~80x) slower than the actual rehash for an average sized MethodDictionary. Btw, MethodDictionaries are rarely grown.
c) I left methods intersection and nastyAddNew: out of classes Set and Dictionary for the initial version of FasterSets to keep the number of changes to a minimum. At your request I added them to the current version. These methods are not in Levente's version. They are public methods that provide performance improvements. If desired they could easily be added to Levente's version.
#nastyAddNew: is not really useful IMO, if you want to be nasty, you can use "private" methods: aSet atNewIndex: (set scanForNil: anObject) put: anObject. It's even faster and if you do this, you probably know what you're doing.
I'm not really interrested in #intersecion:, but I found it controversal. What's the intersecion of a Set and an IdentitySet? Do you check identity or equality?
I recommend that
1) You use Levente's version.
Feel free to grab it.
2) Sort out the issue of no rehash method for Class WeakKeyToCollectionDictionary.
See above.
3) Modify his code to use method scanForNilFrom: (calling it scanForEmptySlotFrom:).
See above.
4) Decide if you want to add methods intersect: and nastyAddNew:. I can add these if you want.
See my opinion above.
5) Release a version of Pharo with these changes. 6) In the following release of Pharo add the changes to MethodDictionary to use The FasterSets Idea. I sugggest doing this separately from everything else just because it is a bit hairy. I would not leave this change out because MethodDictionary is too important a class not to have these improvements.
See above.
You can post this on the Pharo newsgroup if you like but perhaps you should get Levente's opinion first.
Go ahead, I'm already subscribed to the pharo list because I couldn't stop myself to respond to a false statement.
Cheers, Levente