[PATCH] Faster hashed collection copy

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  <[hidden email]>
+
+ * 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  <[hidden email]>
 
  * 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 [

_______________________________________________
help-smalltalk mailing list
[hidden email]
http://lists.gnu.org/mailman/listinfo/help-smalltalk