[Help-smalltalk] [PATCH] Faster hashed collection copy

[Paolo Bonzini]

I'm flushing this since I had it around since before 3.0.  The speedup 
for three copies of a 20,000-element Dictionary or Set is around 30% 
(from ~600ms to ~450ms on my machine).  Committed to master only.

Paolo

diff --git a/ChangeLog b/ChangeLog
index 6b54fc0..14ce6c2 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,11 @@
+2008-01-22  Paolo Bonzini  <address@hidden>
+
+       * kernel/Dictionary.st: Rewrite #findElementIndex:.
+       * kernel/WeakObjects.st: Ditto.
+       * kernel/HashedColl.st: Ditto, and store nil before calling it
+       from #rehashObjectsAfter:.
+       * kernel/LookupTable.st: Ditto, and also use it in #whileGrowingAt:put:.
+
 2008-01-18  Paolo Bonzini  <address@hidden>
 
        * scripts/Package.st: Change default -t value for --list-files,
diff --git a/kernel/Dictionary.st b/kernel/Dictionary.st
index 0811140..4e34db3 100644
--- a/kernel/Dictionary.st
+++ b/kernel/Dictionary.st
@@ -531,11 +531,21 @@ certain special cases.'>
     ]
 
     findElementIndex: anObject [
-       "anObject is the content of an indexed variable. See what slot it should
-        be inserted in."
-
-       <category: 'private methods'>
-       ^self findIndex: anObject key
+        "Tries to see where anObject can be placed as an indexed variable.
+        As soon as nil is found, the index of that slot is answered.
+        anObject also comes from an indexed variable."
+
+        <category: 'private methods'>
+        | index size element |
+        self beConsistent.
+
+        "Sorry for the lack of readability, but I want speed... :-)"
+        index := (anObject key hash scramble bitAnd: (size := self primSize) - 
1) + 1.
+   
+        [(element := self primAt: index) isNil
+            ifTrue: [^index].
+        index == size ifTrue: [index := 1] ifFalse: [index := index + 1]]
+                repeat
     ]
 
     findIndex: anObject [
diff --git a/kernel/HashedColl.st b/kernel/HashedColl.st
index 76ea310..198afb5 100644
--- a/kernel/HashedColl.st
+++ b/kernel/HashedColl.st
@@ -316,11 +316,10 @@ give fast responses on their presence in the collection.'>
        element := self primAt: i.
        element notNil] 
                whileTrue: 
-                   [j := self findElementIndex: element.
-                   (self primAt: j) isNil 
-                       ifTrue: 
-                           [self primAt: j put: element.
-                           self primAt: i put: nil]]
+                   [self primAt: i put: nil.
+                   j := self findElementIndex: element.
+                   self primAt: j put: element.
+                   j = i ifFalse: [self primAt: i put: nil]]
     ]
 
     hashFor: anObject [
@@ -331,11 +330,21 @@ give fast responses on their presence in the collection.'>
     ]
 
     findElementIndex: anObject [
-       "anObject is the content of an indexed variable. See what slot it should
-        be inserted in."
-
-       <category: 'private methods'>
-       ^self findIndex: anObject
+        "Tries to see where anObject can be placed as an indexed variable.
+        As soon as nil is found, the index of that slot is answered.
+        anObject also comes from an indexed variable."
+
+        <category: 'private methods'>
+        | index size element |
+        self beConsistent.
+
+        "Sorry for the lack of readability, but I want speed... :-)"
+        index := (anObject hash scramble bitAnd: (size := self primSize) - 1) 
+ 1.
+   
+        [(element := self primAt: index) isNil
+            ifTrue: [^index].
+        index == size ifTrue: [index := 1] ifFalse: [index := index + 1]]
+                repeat
     ]
 
     findIndex: anObject [
diff --git a/kernel/LookupTable.st b/kernel/LookupTable.st
index c827d2a..a054407 100644
--- a/kernel/LookupTable.st
+++ b/kernel/LookupTable.st
@@ -250,13 +250,13 @@ equality comparison message #= to determine equivalence 
of indices.'>
        key := self primAt: i.
        key notNil] 
                whileTrue: 
-                   [j := self findElementIndex: key.
-                   (self primAt: j) isNil 
-                       ifTrue: 
-                           [self primAt: j put: key.
-                           self valueAt: j put: (self valueAt: i).
-                           self primAt: i put: nil.
-                           self valueAt: i put: nil]]
+                   [self primAt: i put: nil.
+                   j := self findElementIndex: element.
+                   self primAt: j put: element.
+                   j = i ifFalse: [
+                       self valueAt: j put: (self valueAt: i).
+                       self primAt: i put: nil.
+                       self valueAt: i put: nil]]
     ]
 
     copyAllFrom: aDictionary [
@@ -282,7 +282,7 @@ equality comparison message #= to determine equivalence of 
indices.'>
 
        <category: 'private methods'>
        | index |
-       self primAt: (index := self findIndex: key) put: key.
+       self primAt: (index := self findElementIndex: key) put: key.
        self valueAt: index put: value.
        tally := tally + 1.
        ^value
@@ -321,11 +321,21 @@ equality comparison message #= to determine equivalence 
of indices.'>
     ]
 
     findElementIndex: anObject [
-       "anObject is the content of an indexed variable. See what slot it should
-        be inserted in."
-
-       <category: 'private methods'>
-       ^self findIndex: anObject
+        "Tries to see where anObject can be placed as an indexed variable.
+        As soon as nil is found, the index of that slot is answered.
+        anObject also comes from an indexed variable."
+
+        <category: 'private methods'>
+        | index size element |
+        self beConsistent.
+
+        "Sorry for the lack of readability, but I want speed... :-)"
+        index := (anObject hash scramble bitAnd: (size := self primSize) - 1) 
+ 1.
+   
+        [(element := self primAt: index) isNil
+            ifTrue: [^index].
+        index == size ifTrue: [index := 1] ifFalse: [index := index + 1]]
+                repeat
     ]
 
     findIndex: anObject [
diff --git a/kernel/WeakObjects.st b/kernel/WeakObjects.st
index 5c892b8..37717b0 100644
--- a/kernel/WeakObjects.st
+++ b/kernel/WeakObjects.st
@@ -286,11 +286,20 @@ one of them, I swiftly remove all.'>
     ]
 
     findElementIndex: anObject [
-       "anObject is the content of an indexed variable. See what slot it should
-        be inserted in."
-
-       <category: 'private'>
-       ^self findIndex: anObject key
+        "Tries to see if anObject exists as an indexed variable. As soon as nil
+         is found, the index of that slot is answered"
+
+        <category: 'private methods'>
+        | index size element |
+        self beConsistent.
+
+        "Sorry for the lack of readability, but I want speed... :-)"
+        index := (anObject key hash scramble bitAnd: (size := self primSize) - 
1) + 1.
+   
+        [(element := self primAt: index) isNil
+            ifTrue: [^index].
+        index == size ifTrue: [index := 1] ifFalse: [index := index + 1]]
+                repeat
     ]
 
     findIndex: anObject [