[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[Help-smalltalk] [PATCH] Faster hashed collection copy
From: |
Paolo Bonzini |
Subject: |
[Help-smalltalk] [PATCH] Faster hashed collection copy |
Date: |
Tue, 22 Jan 2008 17:36:50 +0100 |
User-agent: |
Thunderbird 2.0.0.9 (Macintosh/20071031) |
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 [
[Prev in Thread] |
Current Thread |
[Next in Thread] |
- [Help-smalltalk] [PATCH] Faster hashed collection copy,
Paolo Bonzini <=