Image using high CPU in WeakIdentityKeyDictionary>>scanFor:

Ross Boylan RossBoylan at stanfordalumni.org
Tue Sep 20 07:15:15 UTC 2005


Thank you both for your responses.  It will take me awhile to absorb
and react fully to them, but there are a couple things I can offer
now.

First,
WeakIdentityKeyDictionary allInstances collect: [:x | x size]
 #(2831 48 3588)
so clearly I have some above the pain threshhold mentioned below.

On Mon, Sep 19, 2005 at 09:47:43PM -0700, Daniel Vainsencher wrote:
> Actually the scanfor of weakIDDicts in 3.9a is reasonable looking (as 
> opposed, for example to weakset, weakkeydict, Dictionary, Set and so 
> forth, which are quite terrible above ~3000 entries. I'm talking 
> specifically about the calculation of "start", which really determines 
> how well the hash values will be spread out.
> 
> Ross, can you post WeakIDDict>>scanFor: as implemented in your image? 
> just to make sure.
> 
'From Squeak3.2 of 29 April 2002 [latest update: #4956] on 19 September 2005 at 11:58:11 pm'!

!WeakIdentityKeyDictionary methodsFor: 'private' stamp: 'ar 2/11/2001 01:41'!
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 |
	start _ (anObject identityHash \\ array size) + 1.
	finish _ array size.

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


Is that OK, or should I send a gzipped version?  I remember vaguely
that may be useful because of line-ending differences.

More to come.

Thanks again.
Ross

One follow-up question:
...
> David T. Lewis wrote:
...
> >The problem I saw was that #scanFor: degraded horribly when there
> >were a lot of entries in the WeakRegistry. In normal Squeak usage,
> >this did not happen, but in my case I was accidentally accumulating
> >a lot of entries in the registry (*).
...
> >(*) Specifically, I was using a subclass of StandardFileStream to
> >represent the end points of an operating system pipe; then I made
> >and destroyed large numbers of these in the course of making command
> >pipelines (see CommandShell on SqueakMap). After running a large
> >number of SUnit tests, these things would accumulate in the registry
> >to the point where performance degraded horribly. Once I found the
> >culprit, I just quit registering the pipe endpoints (which of course
> >are transient things that don't need to be registered), and my
> >"CPU problem" went away.

Was this registration something you did explicitly, or did it happen
behind the scenes?  Or perhaps I'm not understanding what you mean by
register.  The "registration" that I'm doing, that I'm aware of, is
registering dependents.  I think I'm using a mix of the old and new
systems for doing so (when:send:to: and update/changed).  I suspect
you mean something else.

Ross



More information about the Squeak-dev mailing list