Begin forwarded message:

From: Ralph Boland <rpboland@gmail.com> Date: October 30, 2009 6:44:17 AM GMT+01:00 To: Levente Uzonyi <leves@elte.hu> Cc: Stéphane Ducasse <stephane.ducasse@inria.fr> Subject: Re: Adding FasterSets to Pharo: update

2009/10/29 Levente Uzonyi <leves@elte.hu>:

...

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.

The version of rehash in WeakKeyToCollectionDictionary is different from the other versions. I never bothered to figure out exactly what it does and just left it alone. Despite what you say my opinion is still that it is needed but I will leave it to those making the final decision to decide.

...

...

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.

This is not correct. ScanForEmptySlotFor: is analogous to scanForNil: You did not implement a method analogous to scanForNilFrom: and obviously never used it either. In my opinion the use of scanForNilFrom: makes the code cleaner but it is not a major issue if it is not used.

...

...

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

I don't know what these stats are about. I am merely quoting the stats you posted for the first version of faster sets that you released. They indicated that for class Set your method rehash was appx 15% faster than the version in FasterSets and your method add: was appx 1% faster than the version in FasterSets.

...

...

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 don't know whether nastyAddNew: should be added to Pharo/Squeak or not. I'll leave that for others to decide. However, I consider nastyAddNew: to be preferable to what you propose.

...

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?

The current code currently supports intersection of sets/dictionaries but it is slower than the version in FasterSets because the FasterSets version avoids unnecessary compares. If you believe that intersection for sets in the current code is controversial and should be changed or removed fine. FasterSets is not entering this debate; it is merely providing faster versions of intersection than what is already in the code.

...

...

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

Regards,

Ralph Boland