Fwd: Adding FasterSets to Pharo: update

> From: Ralph Boland <[hidden email]>
> Date: October 30, 2009 6:44:17 AM GMT+01:00
> To: Levente Uzonyi <[hidden email]>
> Cc: Stéphane Ducasse <[hidden email]>
> Subject: Re: Adding FasterSets to Pharo: update
>
> 2009/10/29 Levente Uzonyi <[hidden email]>:
>> 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