[ENH][FIX] Fulltext: IdentityHash

Scott A Crosby crosby at qwes.math.cmu.edu
Mon Feb 18 07:18:34 UTC 2002


Here are the 4 identityhash fixing patches, in order. They *should* go in
before fulltext.[*]

In the IdentityHash changesets.. These work, but during the installation,
identityset's *are temporarily* in an *inconsistent* state. It appears
that, at least in the default image, this temporary inconsistency doesn't
cause a problem.

All sets are rehashed to restore consistency. (Far more work is done
rehashing than strictly necessary, but oh well. MethodDictionaries don't
need to be rehashed, but are.) There should be two full rehashes in these
changesets

Scott


[*] Although independent of fulltext, these changeset *should go in*
before the FullText stuff. This is because users of fulltext will be
creating large sets and dictionaries, potentially hitting performance
issues this solves, and increasing the risk that there will be a large and
potentially inconsistent IdentitySet/Dictionary in the image.




-------------- next part --------------
'From Squeak3.1alpha of 7 March 2001 [latest update: #4164] on 9 October 2001 at 8:41:08 pm'!
"Postscript:
Leave the line above, and replace the rest of this comment by a useful one.
Executable statements should follow this comment, and should
be separated by periods, with no exclamation points (!!).
Be sure to put any further comments in double-quotes, like this one."

Smalltalk at: #Switchover put: false.
!

-------------- next part --------------
'From Squeak3.1alpha of 7 March 2001 [latest update: #4164] on 9 October 2001 at 8:18:19 pm'!
"Change Set:		PrefixChanges
Date:			9 October 2001
Author:			Scott Crosby

<your descriptive text goes here>"!


!ProtoObject methodsFor: 'comparing' stamp: 'sac 10/9/2001 19:42'!
hashBits
	"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! !

!ProtoObject methodsFor: 'comparing' stamp: 'sac 10/9/2001 19:48'!
identityHash
	Switchover ifTrue:
		[^self hashBits * 100799.]
		ifFalse:
		[^self hashBits].! !


!MethodDictionary methodsFor: 'private' stamp: 'sac 10/9/2001 19:42'!
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 |
	start _ (anObject hashBits \\ array size) + 1.
	finish _ array size.

	"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"! !


!SystemTracer methodsFor: 'mapping oops' stamp: 'sac 10/9/2001 19:43'!
mapAt: obj
	"Return the new oop for this object"
	| bucket |
	bucket _ oopMap at: obj hashBits+1.
	1 to: bucket size by: 3 do: 
		[:i | obj == (bucket at: i)
			ifTrue: ["Promote this entry for rapid access"
					i > 1 ifTrue: [1 to: 3 do: [:j | bucket swap: j with: i-1+j]].
					^ bucket at: 2]].
	^ UnassignedOop! !

!SystemTracer methodsFor: 'mapping oops' stamp: 'sac 10/9/2001 19:43'!
mapAt: obj put: oop with: hash
	"Assign the new oop for this object"
	| bucket |
	bucket _ oopMap at: obj hashBits +1.

	"Check for multiple writes (debug only)"
"	1 to: bucket size by: 3 do: 
		[:i | obj == (bucket at: i) ifTrue: [self halt]].
"
	oopMap at: obj identityHash+1 put: (Array with: obj with: oop with: hash) , bucket! !

!SystemTracer methodsFor: 'mapping oops' stamp: 'sac 10/9/2001 20:17'!
mapHashAt: obj
	"Return the new hash for this object"
	| bucket |
	bucket _ oopMap at: obj hashBits + 1.
	1 to: bucket size by: 3 do: 
		[:i | obj == (bucket at: i) ifTrue: [^ bucket at: i+2]].
	self halt! !

Switchover _ true. Set rehashAllSets.
!

-------------- next part --------------
'From Squeak3.1alpha of 7 March 2001 [latest update: #4164] on 9 October 2001 at 8:52:40 pm'!

!ProtoObject methodsFor: 'comparing' stamp: 'sac 10/9/2001 20:25'!
identityHash
	^self hashBits * 100799.
! !

Smalltalk removeKey: #Switchover!

-------------- next part --------------
'From Squeak3.2alpha of 11 October 2001 [latest update: #4646] on 17 February 2002 at 11:06:49 pm'!

!IdentityDictionary methodsFor: 'private' stamp: 'sac 12/9/2001 07:07'!
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.
hash _ anObject identityHash.
	start _ hash \\ array size + 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: 'sac 12/9/2001 07:07'!
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.

		hash _ anObject identityHash.
	start _ hash \\ array size + 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"! !

"Postscript:
Rehash all sets to insure consistancy."
Set rehashAllSets

!



More information about the Squeak-dev mailing list