Issue 4826 in pharo: Speedup MethodDictionary #rehash

Status: Accepted
Owner: marianopeck

New issue 4826 by marianopeck: Speedup MethodDictionary #rehash
http://code.google.com/p/pharo/issues/detail?id=4826

So...I had the idea to speed up rehash of MethodDIctionary without doing a  
become. And evne more, #become is used in a lot of places. You can read  
more in: http://forum.world.st/MethodDictionary-fast-rehash-td3820802.html

Now Levente has just (today!) commited a version to squeak that avoids the  
#bcome and still uses a primitive, hence, it avoids the inconcistent state.

I will provide a slice


_______________________________________________
Pharo-bugtracker mailing list
[hidden email]
http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-bugtracker

Comment #1 on issue 4826 by marianopeck: Speedup MethodDictionary #rehash
http://code.google.com/p/pharo/issues/detail?id=4826

I speed up rehashed up to 1500x times :)

Name: SLICE-Issue-4826-Speedup-MethodDictionary-rehash-MarianoMartinezPeck.1
Author: MarianoMartinezPeck
Time: 18 September 2011, 6:59:31 pm
UUID: e26601e8-6765-48b2-a230-8637a4a9386d
Ancestors:
Dependencies: Kernel-MarianoMartinezPeck.938,  
KernelTests-MarianoMartinezPeck.353

Fix to issue 4826

Just try this, before and anfter this fix:

   | methodDicts |
     methodDicts := OrderedCollection new.
     methodDicts addAll: ((SystemNavigation default  
allClassesInPackageNamed: 'System')
         collect: [ :aClass | aClass methodDict ]).
     methodDicts addAll: ((SystemNavigation default  
allClassesInPackageNamed: 'Morphic')
         collect: [ :aClass | aClass methodDict ]).

     Transcript show: [methodDicts do: [:each | each rehash]] timeToRun  
asString; cr.


As a matter of documentation, I paste Levente commit description in Squeak:

Use #copyFrom: and #becomeForward: instead of #become: during changes of  
MethodDictionaries. These changes assume that #copyFrom: is atomic (just  
like #become: and #becomeForward:), so the MethodDictionaries never get  
into an inconsistent state.
These changes speed up #rehash, #removeAll, #removeKey:ifAbsent and also  
#compact if the dictionary already has the smallest possible capacity. This  
means that #rehashAllInstances and #rehashWithoutBecome is not necessary  
anymore, so those were removed.




_______________________________________________
Pharo-bugtracker mailing list
[hidden email]
http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-bugtracker

Updates:
        Status: FixToInclude
        Labels: Milestone-1.4

Comment #2 on issue 4826 by [hidden email]: Speedup MethodDictionary  
#rehash
http://code.google.com/p/pharo/issues/detail?id=4826

:)
nice mariano.
Did you recompile all the system just to check?


_______________________________________________
Pharo-bugtracker mailing list
[hidden email]
http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-bugtracker

Comment #3 on issue 4826 by marianopeck: Speedup MethodDictionary #rehash
http://code.google.com/p/pharo/issues/detail?id=4826

No. But give me a minute. Because there is a second part ;)
And I want people to check it before being integrated.


_______________________________________________
Pharo-bugtracker mailing list
[hidden email]
http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-bugtracker

Updates:
        Status: FixProposed

Comment #4 on issue 4826 by marianopeck: Speedup MethodDictionary #rehash
http://code.google.com/p/pharo/issues/detail?id=4826

Well...I have added more improvemtns from Levente and I have merged all of  
the in one slice. In addition to the previous changes, I add the comments  
of Levene that I have integrated here:

MethodDictionary changes:
- fix: #compact shouldn't increase the load factor above 75% (see #sizeFor:  
on the class side)
- speed up #compact and #compactAllInstances by using #copyFrom: instead of  
#becomeForward: if the capacity of the dictionaries can't be reduced


I have run MethodDictionaryTest and they are all green. I could do a  
Compiler recompileAll without problems.

I attach a fileout because the +slice is broken in 1.4 (I will open a new  
ticket for this).




Attachments:
        MethodDictRehash.2.cs  4.9 KB


_______________________________________________
Pharo-bugtracker mailing list
[hidden email]
http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-bugtracker

Comment #5 on issue 4826 by marianopeck: Speedup MethodDictionary #rehash
http://code.google.com/p/pharo/issues/detail?id=4826

Just as a record, the commits of Levente are:

Name: Kernel-ul.625
Author: ul
Time: 18 September 2011, 11:54:02.722 am
UUID: 14b3a206-0a64-6049-83f2-fa4a151207cf
Ancestors: Kernel-ul.624

and

Name: Kernel-ul.626
Author: ul
Time: 18 September 2011, 3:18:04.315 pm
UUID: c917ec7b-b1ed-1849-bfb3-292cb3898035
Ancestors: Kernel-ul.625


_______________________________________________
Pharo-bugtracker mailing list
[hidden email]
http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-bugtracker

Updates:
        Cc: [hidden email]

Comment #6 on issue 4826 by [hidden email]: Speedup MethodDictionary  
#rehash
http://code.google.com/p/pharo/issues/detail?id=4826

thanks
Next time you come to lille you should explain the details to me on the  
black board.
I will of course read the code before :)

Stef


_______________________________________________
Pharo-bugtracker mailing list
[hidden email]
http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-bugtracker

Updates:
        Status: FixToInclude

Comment #7 on issue 4826 by marianopeck: Speedup MethodDictionary #rehash
http://code.google.com/p/pharo/issues/detail?id=4826

Well...since nobody answer, let integrate it! :)
Status: FixToInclude


_______________________________________________
Pharo-bugtracker mailing list
[hidden email]
http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-bugtracker

Updates:
        Status: Integrated

Comment #8 on issue 4826 by [hidden email]: Speedup MethodDictionary  
#rehash
http://code.google.com/p/pharo/issues/detail?id=4826

in 14155


_______________________________________________
Pharo-bugtracker mailing list
[hidden email]
http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-bugtracker