I should point out that the changesets I sent implement the scaledIdentityHash approach I just wrote about in the previous email. The mutation methodology is more robust as well (note it can also be used to implement the primIdentityHash approach). Finally, the prime table in the changesets I sent is better. Martin and I need to iron out a small detail to see if we can get rid of some code. Andres. Stéphane Ducasse wrote:
Martin
are these changes related to the graphs you sent? I will have a look after my hospital check. Andres? Nicolas? Any feedback? Martin I imagine that I can package the changes :)
Stef
On Oct 24, 2009, at 4:01 AM, Martin McClure wrote:
OK, here's a filein that improves Pharo hashed collection performance quite a bit. Large collections are much faster, and small ones are pretty much the same speed as before. There are basically two fairly simple changes; the basic structure and algorithms of the collections is unchanged. The changes:
1. Spread identity hash values. 2. Make table sizes prime.
File it into PharoCore-1.0-10491rc1.image. It'll take a minute or two since it has to rehash the world halfway through. I don't know how to make another kind of packaging that can do that, so I'll leave that to someone else.
After the filein, there are some test failures, most of which do not seem to be *directly* related. I'm hoping someone that knows the affected tests can take a look and comment:
Unexpectedly pass ObjectFinalizerTests>>#testFinalizationOfEquals Not clear why, but this does not seem to be a problem :-)
Fails HostWindowTests>>#testOne But this test fails in the core image on Linux; HostWindows do not seem to be implemented for Linux.
Error on FontTest>>#testMultistringFont Japanese StrikeFonts have nil characterToGlyphMap, #createCharacterToGlyphMap answers nil, not immediately clear how this is supposed to be initialized for fonts with codepoints > 255.
PackageInfoTest>>testKernelPackage because some method in kernel package for Object is not in Object. I've changed #hash, so that's probably it.
Regards,
-Martin 'From Pharo1.0rc1 of 19 October 2009 [Latest update: #10491] on 23 October 2009 at 5:54:55 pm'!
!ProtoObject methodsFor: 'comparing' stamp: 'MartinMcClure 10/22/2009 22:30'! identityHashTEMP "Answer a SmallInteger whose value is related to the receiver's identity. This method must not be overridden, except by SmallInteger. Primitive. Fails if the receiver is a SmallInteger. Essential. See Object documentation whatIsAPrimitive.
Do not override."
^self primIdentityHash bitShift: 18! !
!Object methodsFor: 'comparing' stamp: 'MartinMcClure 10/22/2009 22:46'! hashTEMP "Answer a SmallInteger whose value is related to the receiver's identity. May be overridden, and should be overridden in any classes that define = "
^ self primIdentityHash bitShift: 18! !
!ProtoObject methodsFor: 'comparing' stamp: 'MartinMcClure 10/22/2009 21:13'! primIdentityHash "Answer a SmallInteger whose value is related to the receiver's identity. This method must not be overridden, except by SmallInteger. Primitive. Fails if the receiver is a SmallInteger. Essential. See Object documentation whatIsAPrimitive.
Do not override."
<primitive: 75> self primitiveFailed! !
!SmallInteger methodsFor: 'comparing' stamp: 'MartinMcClure 10/23/2009 17:53'! primIdentityHash "Senders of primIdentityHash do it because they expect to get an answer from 1-4095. So they should not send this to SmallIntegers, but should use #identityHash"
"^self shouldNotImplement"
"...OK, only here for the sake of FixedIdentitySet, which may not need it since it is probably not used for Integers. And FixedIdentitySet itself may not be needed now that IdentitySets are faster."
^self! !
!IdentityDictionary methodsFor: 'private' stamp: 'MartinMcClure 10/23/2009 14:55'! scanFor: anObject "Scan the key array for the first slot containing either a nil (indicating an empty slot) or an element that matches anObject. Answer the index of that slot or zero if no slot is found. This method will be overridden in various subclasses that have different interpretations for matching elements." | finish hash start element | finish := array size. start := (anObject identityHash \\ finish) + 1.
"Search from (hash mod size) to the end." start to: finish do: [:index | ((element := array at: index) == nil or: [element key == anObject]) ifTrue: [^ index ]].
"Search from 1 to where we started." 1 to: start-1 do: [:index | ((element := array at: index) == nil or: [element key == anObject]) ifTrue: [^ index ]].
^ 0 "No match AND no empty slot"! !
!IdentitySet methodsFor: 'private' stamp: 'MartinMcClure 10/23/2009 14:57'! scanFor: anObject "Scan the key array for the first slot containing either a nil (indicating an empty slot) or an element that matches anObject. Answer the index of that slot or zero if no slot is found. This method will be overridden in various subclasses that have different interpretations for matching elements." | finish hash start element | finish := array size. start := (anObject identityHash \\ finish) + 1.
"Search from (hash mod size) to the end." start to: finish do: [:index | ((element := array at: index) == nil or: [element == anObject]) ifTrue: [^ index ]].
"Search from 1 to where we started." 1 to: start-1 do: [:index | ((element := array at: index) == nil or: [element == anObject]) ifTrue: [^ index ]].
^ 0 "No match AND no empty slot"! !
!MethodDictionary methodsFor: 'private' stamp: 'MartinMcClure 10/22/2009 21:24'! scanFor: anObject "Scan the key array for the first slot containing either a nil (indicating an empty slot) or an element that matches anObject. Answer the index of that slot or zero if no slot is found. This method will be overridden in various subclasses that have different interpretations for matching elements." | element start finish | finish := array size. start := (anObject primIdentityHash \\ finish) + 1.
"Search from (hash mod size) to the end." start to: finish do: [:index | ((element := self basicAt: index) == nil or: [element == anObject]) ifTrue: [^ index ]].
"Search from 1 to where we started." 1 to: start-1 do: [:index | ((element := self basicAt: index) == nil or: [element == anObject]) ifTrue: [^ index ]].
^ 0 "No match AND no empty slot"! !
!WeakIdentityKeyDictionary methodsFor: 'private' stamp: 'MartinMcClure 10/23/2009 14:54'! scanFor: anObject "ar 10/21/2000: The method has been copied to this location to indicate that whenever #scanFor: changes #scanForNil: must be changed in the receiver as well." "Scan the key array for the first slot containing either a nil (indicating an empty slot) or an element that matches anObject. Answer the index of that slot or zero if no slot is found. This method will be overridden in various subclasses that have different interpretations for matching elements." | element start finish hash | finish := array size. start := (anObject identityHash \\ finish) + 1.
"Search from (hash mod size) to the end." start to: finish do: [:index | ((element := array at: index) == nil or: [element key == anObject]) ifTrue: [^ index ]].
"Search from 1 to where we started." 1 to: start-1 do: [:index | ((element := array at: index) == nil or: [element key == anObject]) ifTrue: [^ index ]].
^ 0 "No match AND no empty slot"! !
!WeakIdentityKeyDictionary methodsFor: 'private' stamp: 'MartinMcClure 10/23/2009 14:54'! scanForNil: anObject "Private. Scan the key array for the first slot containing nil (indicating an empty slot). Answer the index of that slot." | start finish hash | finish := array size. start := (anObject identityHash \\ array size) + 1.
"Search from (hash mod size) to the end." start to: finish do: [:index | (array at: index) == nil ifTrue: [^ index ]].
"Search from 1 to where we started." 1 to: start-1 do: [:index | (array at: index) == nil ifTrue: [^ index ]].
^ 0 "No match AND no empty slot"! !
"---------------------Do surgery and rehash before continuing--------------------------"!
| dict method | dict := ProtoObject methodDictionary. method := dict at: #identityHashTEMP. dict at: #identityHash put: method. dict := Object methodDictionary. method := dict at: #hashTEMP. dict at: #identityHash put: method.
Set rehashAllSets.!
"---------- Life should be... better now :-) -----------------------------"!
!ProtoObject methodsFor: 'comparing' stamp: 'MartinMcClure 10/22/2009 22:30'! identityHash "Answer a SmallInteger whose value is related to the receiver's identity. This method must not be overridden, except by SmallInteger. Primitive. Fails if the receiver is a SmallInteger. Essential. See Object documentation whatIsAPrimitive.
Do not override."
^self primIdentityHash bitShift: 18! !
!Object methodsFor: 'comparing' stamp: 'MartinMcClure 10/22/2009 22:46'! hash "Answer a SmallInteger whose value is related to the receiver's identity. May be overridden, and should be overridden in any classes that define = "
^ self primIdentityHash bitShift: 18! !
!FixedIdentitySet methodsFor: 'private' stamp: 'MartinMcClure 10/23/2009 14:49'! indexOf: anObject anObject isNil ifTrue: [self error: 'This class collection cannot handle nil as an element']. ^ (anObject primIdentityHash bitAnd: self basicSize - 1) + 1! !
!Set class methodsFor: 'sizing' stamp: 'MartinMcClure 10/23/2009 09:44'! goodPrimes "Answer a sorted array of prime numbers less than one hundred million that make good hash table sizes. Should be expanded to more numbers if folks want to make larger collections. Need to check with Andres' book when I get back to work to see if I remembered it right :-)
Generated with this code:
| prevPrime primes goodPrimes | goodPrimes := OrderedCollection new. primes := Integer largePrimesUpTo: 100000000. goodPrimes add: 5. prevPrime := 5. primes do: [:prime | prime > (prevPrime * 4 // 3) ifTrue: [| lowByte | lowByte := prime bitAnd: 16rFF. (lowByte > 10 and: [lowByte < 245]) ifTrue: [goodPrimes add: prime. prevPrime := prime]]]. ^goodPrimes asArray printString"
^#(5 11 17 23 31 43 59 79 107 149 199 269 359 479 641 857 1151 1549 2069 2767 3691 4931 6577 8779 11717 15629 20849 27799 37087 49451 65951 87943 117259 156347 208463 277961 370619 494167 658897 878539 1171393 1561883 2082527 2776727 3702313 4936423 6581909 8775947 11701267 15601723 20802317 27736427 36981911 49309219 65745677 87660917)! ]style[(10 311 405 337)f2b,f2,f1,f2! !
!Set class methodsFor: 'sizing' stamp: 'MartinMcClure 10/23/2009 10:14'! goodPrimeAtLeast: lowerLimit "Answer the next good prime >= lowerlimit. If lowerLimit is larger than the largest known good prime, just make it odd."
| primes low mid high prime | primes := self goodPrimes. low := 1. high := primes size. lowerLimit > (primes at: high) ifTrue: [^lowerLimit even ifTrue: [lowerLimit + 1] ifFalse: [lowerLimit]]. [mid := high - low // 2 + low. prime := primes at: mid. prime < lowerLimit ifTrue: [low := mid] ifFalse: [high := mid]. high - low <= 1 ifTrue: [^primes at: high]. prime == lowerLimit ifTrue: [^prime]] repeat
! ]style[(28 158 411)f2b,f2,f1! !
!Set methodsFor: 'private' stamp: 'MartinMcClure 10/23/2009 10:25'! growSize "Answer what my next higher table size should be" ^ self class goodPrimeAtLeast: array size * 2! !
!Set methodsFor: 'private' stamp: 'MartinMcClure 10/23/2009 10:25'! grow "Grow the elements array and reinsert the old elements" | oldElements | oldElements := array. array := Array new: self growSize. tally := 0. oldElements do: [:each | each == nil ifFalse: [self noCheckAdd: each]]! !
!Set class methodsFor: 'instance creation' stamp: 'MartinMcClure 10/23/2009 10:19'! sizeFor: nElements "Large enough size to hold nElements with some slop (see fullCheck)" nElements <= 0 ifTrue: [^ 5]. ^ self goodPrimeAtLeast: (nElements+1*4//3)! !
!WeakSet methodsFor: 'private' stamp: 'MartinMcClure 10/23/2009 10:26'! grow "Grow the elements array if needed. Since WeakSets just nil their slots, alot of the occupied (in the eyes of the set) slots are usually empty. Doubling size if unneeded can lead to BAD performance, therefore we see if reassigning the <live> elements to a Set of similiar size leads to a sufficiently (50% used here) empty set first. and reinsert the old elements" |oldTally| oldTally := tally. self growTo: array size. oldTally >> 1 < tally ifTrue: [ self growTo: self growSize]! !
!MethodPragmaTest methodsFor: 'testing-primitives' stamp: 'MartinMcClure 10/23/2009 12:37'! testPrimitiveIndexed2 "This test useses the #identityHash primitive."
self compile: '<primitive: 75> ^ #idHash' selector: #idHash. self assert: self idHash = self primIdentityHash.! !
!SmallInteger reorganize! ('arithmetic' * + - / // \\ gcd: quo:) ('bit manipulation' bitAnd: bitOr: bitShift: bitXor: hashMultiply highBit highBitOfMagnitude lowBit) ('comparing' < <= = > >= hash identityHash primIdentityHash ~=) ('converting' as31BitSmallInt asFloat) ('copying' clone deepCopy shallowCopy veryDeepCopyWith:) ('printing' decimalDigitLength destinationBuffer: numberOfDigitsInBase: printOn:base: printOn:base:nDigits: printString printStringBase: printStringBase:nDigits: threeDigitName) ('system primitives' asOop digitAt: digitAt:put: digitLength instVarAt: nextInstance nextObject) ('testing' even isLarge odd) ('private' fromString:radix: highBitOfPositiveReceiver) !
!Set class reorganize! ('initialization' quickRehashAllSets rehashAllSets) ('sizing' goodPrimeAtLeast: goodPrimes) ('instance creation' new new: newFrom: sizeFor:) !
ProtoObject removeSelector: #identityHashTEMP! Object removeSelector: #hashTEMP!
!ProtoObject reorganize! ('apply primitives' tryNamedPrimitive tryNamedPrimitive: tryNamedPrimitive:with: tryNamedPrimitive:with:with: tryNamedPrimitive:with:with:with: tryNamedPrimitive:with:with:with:with: tryNamedPrimitive:with:with:with:with:with: tryNamedPrimitive:with:with:with:with:with:with: tryNamedPrimitive:with:with:with:with:with:with:with: tryPrimitive:withArgs:) ('closure-prims' privGetInstVar: privRemoteReturnTo: privSetInHolder: privSetInstVar:put: privStoreIn:instVar:) ('comparing' == identityHash primIdentityHash ~~) ('debugging' doOnlyOnce: flag: rearmOneShot withArgs:executeMethod:) ('initialize-release' initialize) ('method execution' executeMethod: with:executeMethod: with:with:executeMethod: with:with:with:executeMethod: with:with:with:with:executeMethod:) ('objects from disk' rehash) ('system primitives' become: cannotInterpret: doesNotUnderstand: nextInstance nextObject) ('testing' ifNil: ifNil:ifNotNil: ifNotNil: ifNotNil:ifNil: isInMemory isNil pointsTo:) !
_______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
_______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project .