December 2009 - Pharo-dev - lists.pharo.org

Re: [Pharo-project] Fwd: [squeak-dev] The Trunk: Traits-nice.248.mcz

by StÃ©phane Ducasse

>> > :) lucky guy, I wish I could do so (and my wife wishes a bit > stronger). Mountains are a bit flat, and snow is a bit sparse at > Nantes these days... Here even flatter I saw people pulling kids on slegde the 10 cm of snow we got :) I forgot you were at Nantes. I pass from time to time there. We should go and drink a beer (soda for me). Stef (okay I should not touch smalltalk today or mails.... just word and latex....)

Dec. 24, 2009

Re: [Pharo-project] What are MethodDictionary faults?

by StÃ©phane Ducasse

> Taking that explanation in mind, we can follow this three steps: > > \begin{enumerate} > \item Send the message {\em ImageSegment>>discoverActiveClasses} which forces a MethodDictionary fault in all classes. Yes! It sends the message {\em induceMDFault} to all classes except classes like Array Object Class Message MethodDictionary. After this, all classes but those ones, will have the {\em methodDict} with {\em nil}. > \item Do a few things, use the system for a while. Maybe even save and resume the image. > \item Now, it is easy. All classes that still have a nil in the {\em mehodDict} is because they were not used, and those who have something different from {\em nil} is because they were. With the message {\em ImageSegment>>activeClasses} you can restore all remaining MethodDictionary faults and return the active classes. And with the message {\em ImageSegment>>swapOutInactiveClasses} you can make up segments by grouping unused classes by system category and write them to disk. > > A very important thing is that if you send the message {\em discoverActiveClasses} you must then have to send the message {\em activeClasses} or {\em swapOutInactiveClasses} because otherwise you will have a lot of classes with the {\em methodDict} in {\em nil}. > > \end{enumerate} > > > is it clear ? Yes. So may be you should create an ImageSegment package and put the faultDescription as class extensions to this package. Did you try to see what are the inactive classes you get after a full coding sesssion with loading and saving code?

Dec. 24, 2009

Re: [Pharo-project] Fwd: [squeak-dev] The Trunk: Traits-nice.248.mcz

by Nicolas Cellier

2009/12/24 StÃ©phane Ducasse <stephane.ducasse(a)inria.fr>: > do you have a slice for pharo? > Adrian is on holidays deep in the swiss moutain with no internet connection.... > But who knows :) > > Stef :) lucky guy, I wish I could do so (and my wife wishes a bit stronger). Mountains are a bit flat, and snow is a bit sparse at Nantes these days... Nicolas > On Dec 24, 2009, at 11:53 AM, Nicolas Cellier wrote: > >> For Trait experts only. >> >> >> ---------- Forwarded message ---------- >> From: Â <commits(a)source.squeak.org> >> Date: 2009/12/24 >> Subject: [squeak-dev] The Trunk: Traits-nice.248.mcz >> To: squeak-dev(a)lists.squeakfoundation.org, packages(a)lists.squeakfoundation.org >> >> >> Nicolas Cellier uploaded a new version of Traits to project The Trunk: >> http://source.squeak.org/trunk/Traits-nice.248.mcz >> >> ==================== Summary ==================== >> >> Name: Traits-nice.248 >> Author: nice >> Time: 24 December 2009, 11:49:10 am >> UUID: 557593d7-1db7-2347-bf40-2d40e3b91f55 >> Ancestors: Traits-nice.247 >> >> Move FixedIdentitySet off the Array hierarchy. >> Provide a fast implementation using MethodDictionary tricks >> - handles collisions (instead of blindly ignoring the entry) >> - eventually grow. >> >> I did not understand previous design decision... >> The conflict just did happen (I put a halt: and caught one in Object...) >> According to my own scale, make it work > make it fast. >> >> Rationale about the new design: >> #grow costs, but I think it is user responsibility to fix a >> reasonnable capacity. >> collisions handling should not cost much (except above 4096 entries) >> >> If any expert knowing the reasons for this class and knowing how to >> fire the profiling tests could have a look, thanks... >> >> =============== Diff against Traits-nice.247 =============== >> >> Item was changed: >> + Collection variableSubclass: #FixedIdentitySet >> + Â Â Â instanceVariableNames: 'tally capacity hashShift' >> - Array variableSubclass: #FixedIdentitySet >> - Â Â Â instanceVariableNames: 'tally capacity' >> Â Â Â Â classVariableNames: '' >> Â Â Â Â poolDictionaries: '' >> Â Â Â Â category: 'Traits-Requires'! >> >> + !FixedIdentitySet commentStamp: 'nice 12/24/2009 11:46' prior: 0! >> + This is a fast implementation of fixed size identity sets. >> + Same algorithm as MethodDictionary are used, and thus >> FixedIdentitySet is to IdentitySet what MethodDictionary is to >> IdentityDictionary. >> + The main features are: >> + 1) do not use an array instance variable so as to fast-up creation >> and every access >> + 2) due to the fixed allocated size, growing costs an expensive >> #become: operation. Preallocate me with care. >> + 3) my size is a power of two so the the hashing algorithm be most efficient. >> + 4) for maximum random access efficiency, at least half the storage >> area is always kept empty >> - !FixedIdentitySet commentStamp: 'NS 5/26/2005 13:00' prior: 0! >> - This is a fast but lazy implementation of fixed size identity sets. >> The two main difference to regular identity sets are: >> - >> - 1) These identity sets have a fixed size. If they are full, adding >> another element doesn't have any effect. >> - 2) No rehashing. If two elements were to be stored on the same >> position in the underlying array, one of them is simply discarded. >> >> + Unlike MethodDictionary, this class will scale a bit better over the >> 4096 basicSize limit inherent to identityHash, thanks to a proper >> bitShift.! >> - As a consequence of (1) and (2), these identity sets are very fast!! >> Note that this class inherits form Array. This is not clean but >> reduces memory overhead when instances are created.! >> >> Item was added: >> + ----- Method: FixedIdentitySet>>removeAll (in category 'removing') ----- >> + removeAll >> + Â Â Â tally = 0 ifTrue: [^self]. >> + Â Â Â 1 to: self basicSize do: [:i | self basicAt: i put: nil]. >> + Â Â Â tally := 0! >> >> Item was changed: >> + ----- Method: FixedIdentitySet>>add: (in category 'adding') ----- >> - ----- Method: FixedIdentitySet>>add: (in category 'accessing') ----- >> Â add: anObject >> + Â Â Â | index | >> + Â Â Â index := self scanFor: anObject. >> + Â Â Â (self basicAt: index) >> + Â Â Â Â Â Â Â ifNil: [ >> + Â Â Â Â Â Â Â Â Â Â Â self basicAt: index put: anObject. >> + Â Â Â Â Â Â Â Â Â Â Â tally := tally + 1. >> + Â Â Â Â Â Â Â Â Â Â Â self isFull ifTrue: [ self grow ]] >> + Â Â Â Â Â Â Â "ifNotNil: [] already inside". >> + Â Â Â ^anObject! >> - Â Â Â | index old | >> - Â Â Â self isFull ifTrue: [^ false]. >> - Â Â Â index := self indexOf: anObject. >> - Â Â Â old := self basicAt: index. >> - Â Â Â old == anObject ifTrue: [^ true]. >> - Â Â Â old ifNotNil: [^ false]. >> - Â Â Â self basicAt: index put: anObject. >> - Â Â Â tally := tally + 1. >> - Â Â Â ^ true! >> >> Item was changed: >> + ----- Method: FixedIdentitySet>>addAll:notIn: (in category 'adding') ----- >> - ----- Method: FixedIdentitySet>>addAll:notIn: (in category 'accessing') ----- >> Â addAll: aCollection notIn: notCollection >> Â Â Â Â aCollection do: [:each | >> - Â Â Â Â Â Â Â self isFull ifTrue: [^ self]. >> Â Â Â Â Â Â Â Â (notCollection includes: each) ifFalse: [self add: each]. >> Â Â Â Â ].! >> >> Item was changed: >> Â ----- Method: FixedIdentitySet class>>with:with:with:with:with: (in >> category 'instance creation') ----- >> Â with: firstObject with: secondObject with: thirdObject with: >> fourthObject with: fifthObject >> Â Â Â Â "Answer an instance of me, containing the five arguments as the >> elements." >> >> + Â Â Â ^ (self new: 5) >> - Â Â Â ^ self new >> Â Â Â Â Â Â Â Â add: firstObject; >> Â Â Â Â Â Â Â Â add: secondObject; >> Â Â Â Â Â Â Â Â add: thirdObject; >> Â Â Â Â Â Â Â Â add: fourthObject; >> Â Â Â Â Â Â Â Â add: fifthObject; >> Â Â Â Â Â Â Â Â yourself! >> >> Item was changed: >> Â ----- Method: FixedIdentitySet class>>with:with:with:with:with:with: >> (in category 'instance creation') ----- >> Â with: firstObject with: secondObject with: thirdObject with: >> fourthObject with: fifthObject with: sixthObject >> Â Â Â Â "Answer an instance of me, containing the six arguments as the elements." >> >> + Â Â Â ^ (self new: 6) >> - Â Â Â ^ self new >> Â Â Â Â Â Â Â Â add: firstObject; >> Â Â Â Â Â Â Â Â add: secondObject; >> Â Â Â Â Â Â Â Â add: thirdObject; >> Â Â Â Â Â Â Â Â add: fourthObject; >> Â Â Â Â Â Â Â Â add: fifthObject; >> Â Â Â Â Â Â Â Â add: sixthObject; >> Â Â Â Â Â Â Â Â yourself! >> >> Item was changed: >> + ----- Method: FixedIdentitySet class>>new (in category 'instance >> creation') ----- >> - ----- Method: FixedIdentitySet class>>new (in category 'constants') ----- >> Â new >> Â Â Â Â ^ self new: self defaultSize! >> >> Item was added: >> + ----- Method: FixedIdentitySet>>grow (in category 'private') ----- >> + grow >> + Â Â Â | newSelf | >> + Â Â Â newSelf := self species new: capacity * 2. Â "This will double >> the capacity" >> + Â Â Â self do: [ :anObject | newSelf add: anObject ]. >> + Â Â Â self become: newSelf! >> >> Item was changed: >> + ----- Method: FixedIdentitySet>>includes: (in category 'testing') ----- >> + includes: aSymbol >> + Â Â Â "This override assumes that pointsTo is a fast primitive" >> + >> + Â Â Â aSymbol ifNil: [^ false]. >> + Â Â Â ^ self pointsTo: aSymbol! >> - ----- Method: FixedIdentitySet>>includes: (in category 'accessing') ----- >> - includes: anObject >> - Â Â Â ^ (self basicAt: (self indexOf: anObject)) == anObject! >> >> Item was added: >> + ----- Method: FixedIdentitySet>>fixCollisionsFrom: (in category >> 'private') ----- >> + fixCollisionsFrom: start >> + Â Â Â "The element at start has been removed and replaced by nil. >> + Â Â Â This method moves forward from there, relocating any entries >> + Â Â Â that had been placed below due to collisions with this one." >> + >> + Â Â Â | key index mask | >> + Â Â Â index := start. >> + Â Â Â mask := self basicSize - 1. >> + Â Â Â [ (key := self basicAt: (index := (index bitAnd: mask) + 1)) >> == nil ] whileFalse: [ >> + Â Â Â Â Â Â Â | newIndex | >> + Â Â Â Â Â Â Â (newIndex := self scanFor: key) = index ifFalse: [ >> + Â Â Â Â Â Â Â Â Â Â Â | element | >> + Â Â Â Â Â Â Â Â Â Â Â element := self basicAt: index. >> + Â Â Â Â Â Â Â Â Â Â Â self basicAt: index put: (self basicAt: newIndex). >> + Â Â Â Â Â Â Â Â Â Â Â self basicAt: newIndex put: element.] ]! >> >> Item was changed: >> + ----- Method: FixedIdentitySet class>>new: (in category 'instance >> creation') ----- >> - ----- Method: FixedIdentitySet class>>new: (in category 'constants') ----- >> Â new: anInteger >> + Â Â Â ^ (self basicNew: (self arraySizeForCapacity: anInteger)) >> initializeCapacity: anInteger! >> - Â Â Â ^ (super new: (self arraySizeForCapacity: anInteger)) >> initializeCapacity: anInteger! >> >> Item was changed: >> + ----- Method: FixedIdentitySet>>remove:ifAbsent: (in category >> 'removing') ----- >> - ----- Method: FixedIdentitySet>>remove:ifAbsent: (in category >> 'accessing') ----- >> Â remove: anObject ifAbsent: aBlock >> + Â Â Â | index element | >> + Â Â Â index := self scanFor: anObject. >> + Â Â Â (element := self basicAt: index) ifNil: [ ^aBlock value ]. >> + Â Â Â self basicAt: index put: nil. >> + Â Â Â tally := tally - 1. >> + Â Â Â self fixCollisionsFrom: index. >> + Â Â Â ^element! >> - Â Â Â | index | >> - Â Â Â index := self indexOf: anObject. >> - Â Â Â ^ (self basicAt: index) == anObject >> - Â Â Â Â Â Â Â ifTrue: [self basicAt: index put: nil. tally := tally >> - 1. anObject] >> - Â Â Â Â Â Â Â ifFalse: [aBlock value].! >> >> Item was added: >> + ----- Method: FixedIdentitySet>>rehash (in category 'private') ----- >> + rehash >> + Â Â Â | newSelf | >> + Â Â Â newSelf := self species new: self size. >> + Â Â Â self do: [ :anObject | newSelf add: anObject ]. >> + Â Â Â ^newSelf! >> >> Item was changed: >> Â ----- Method: FixedIdentitySet>>initializeCapacity: (in category >> 'initialize-release') ----- >> Â initializeCapacity: anInteger >> Â Â Â Â tally := 0. >> + Â Â Â capacity := anInteger. >> + Â Â Â hashShift := self basicSize highBit - 4096 highBit max: 0! >> - Â Â Â capacity := anInteger.! >> >> Item was changed: >> + ----- Method: FixedIdentitySet class>>arraySizeForCapacity: (in >> category 'private') ----- >> - ----- Method: FixedIdentitySet class>>arraySizeForCapacity: (in >> category 'constants') ----- >> Â arraySizeForCapacity: anInteger >> Â Â Â Â "Because of the hash performance, the array size is always a power of 2 >> Â Â Â Â and at least twice as big as the capacity anInteger" >> >> Â Â Â Â ^ anInteger <= 0 >> Â Â Â Â Â Â Â Â ifTrue: [0] >> Â Â Â Â Â Â Â Â ifFalse: [1 << (anInteger << 1 - 1) highBit].! >> >> Item was added: >> + ----- Method: FixedIdentitySet>>scanFor: (in category 'private') ----- >> + 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 raise an error if no slot is found. This >> method will be overridden in various subclasses that have different >> interpretations for matching elements." >> + >> + Â Â Â | index start mask | >> + Â Â Â anObject ifNil: [self error: 'This class collection cannot >> handle nil as an element']. >> + Â Â Â mask := self basicSize - 1. >> + Â Â Â index := start := ((anObject identityHash bitShift: hashShift) >> bitAnd: mask) + 1. >> + Â Â Â [ >> + Â Â Â Â Â Â Â | element | >> + Â Â Â Â Â Â Â ((element := self basicAt: index) == nil or: [ element >> == anObject ]) >> + Â Â Â Â Â Â Â Â Â Â Â ifTrue: [ ^index ]. >> + Â Â Â Â Â Â Â (index := (index bitAnd: mask) + 1) = start ] whileFalse. >> + Â Â Â self errorNoFreeSpace! >> >> Item was removed: >> - ----- Method: FixedIdentitySet>>destructiveAdd: (in category >> 'accessing') ----- >> - destructiveAdd: anObject >> - Â Â Â | index old | >> - Â Â Â self isFull ifTrue: [^ false]. >> - Â Â Â index := self indexOf: anObject. >> - Â Â Â old := self basicAt: index. >> - Â Â Â self basicAt: index put: anObject. >> - Â Â Â old ifNil: [tally := tally + 1]. >> - Â Â Â ^ true! >> >> Item was removed: >> - ----- Method: FixedIdentitySet>>notFull (in category 'testing') ----- >> - notFull >> - Â Â Â ^ tally < capacity! >> >> Item was removed: >> - ----- Method: FixedIdentitySet>>addAll: (in category 'accessing') ----- >> - addAll: aCollection >> - Â Â Â aCollection do: [:each | >> - Â Â Â Â Â Â Â self isFull ifTrue: [^ self]. >> - Â Â Â Â Â Â Â self add: each. >> - Â Â Â ].! >> >> Item was removed: >> - ----- Method: FixedIdentitySet>>indexOf: (in category 'private') ----- >> - indexOf: anObject >> - Â Â Â anObject isNil ifTrue: [self error: 'This class collection >> cannot handle nil as an element']. >> - Â Â Â ^ (anObject identityHash bitAnd: self basicSize - 1) + 1! >> >> _______________________________________________ >> Pharo-project mailing list >> Pharo-project(a)lists.gforge.inria.fr >> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project > > > _______________________________________________ > Pharo-project mailing list > Pharo-project(a)lists.gforge.inria.fr > http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project >

Dec. 24, 2009

Re: [Pharo-project] What are MethodDictionary faults?

by Mariano Martinez Peck

On Thu, Dec 24, 2009 at 12:09 PM, StÃ©phane Ducasse < stephane.ducasse(a)inria.fr> wrote: > > > > Suppose you evaluate this steps: > > > > Smalltalk at: #MDFaultDict put: Dictionary new. > > ImageSegment discoverActiveClasses > > > > .... do something here, browse, whatever .... > > > > ImageSegment activeClasses > > > > Here, you can change activeClasses to use recoverFromMDFaultWithTrace > instead of recoverFromMDFault > > and with this you can see who used that class. It is stored in Smalltalk > at: #MDFaultDict > > Ok good to know that it is working. At some point doing that would just > crash. > > > Ok...at least that is what I understood, but as this is not working, I am > not sure. > > This is correct. > > > What I suggest: > > - create a new category in the class and move all the methods that > could be removed. Tag them as deprecated. > > do not deprecated them since this is working. :) > > > - in imageSegments just clean :) > > What is the link with imageSegment? > > Sorry I am lazy, I will copy paste a piece of a .tex \section{Discovering used and unused classes} There is some work that it is quite related to ImageSegment and it is used to discover used and unused classes. There is a possibility to force a MethodDictionary fault with the message {\em ClassDescription>>induceMDFault}. This method copies the {\em methodDict} in the {\em organization} slot. Actually, it creates an Array with the {\em methodDict} and the {\em organization} and set it in the {\em organization} slot. Finally, it sets a {\em nil} to the {\em methodDict} instance variable. After this is done, when that class is used and the {\em methodDict} is asked\,---\,it is very important to acces the {\em methodDict} using the getter\,---\, it checks whether it is nil or not. If it is nil, it will search for that {\em methodDict} in the Array of the {\em organizaction} and it will then copy it to the {\em methodDict} instance variable. Taking that explanation in mind, we can follow this three steps: \begin{enumerate} \item Send the message {\em ImageSegment>>discoverActiveClasses} which forces a MethodDictionary fault in all classes. Yes! It sends the message {\em induceMDFault} to all classes except classes like Array Object Class Message MethodDictionary. After this, all classes but those ones, will have the {\em methodDict} with {\em nil}. \item Do a few things, use the system for a while. Maybe even save and resume the image. \item Now, it is easy. All classes that still have a nil in the {\em mehodDict} is because they were not used, and those who have something different from {\em nil} is because they were. With the message {\em ImageSegment>>activeClasses} you can restore all remaining MethodDictionary faults and return the active classes. And with the message {\em ImageSegment>>swapOutInactiveClasses} you can make up segments by grouping unused classes by system category and write them to disk. A very important thing is that if you send the message {\em discoverActiveClasses} you must then have to send the message {\em activeClasses} or {\em swapOutInactiveClasses} because otherwise you will have a lot of classes with the {\em methodDict} in {\em nil}. \end{enumerate} is it clear ? > > > > > > Ok. Perfect. > > > > Cheers > > > > Mariano > > > > Stef > > _______________________________________________ > > Pharo-project mailing list > > Pharo-project(a)lists.gforge.inria.fr > > http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project > > > > _______________________________________________ > > Pharo-project mailing list > > Pharo-project(a)lists.gforge.inria.fr > > http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project > > > _______________________________________________ > Pharo-project mailing list > Pharo-project(a)lists.gforge.inria.fr > http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project >

Dec. 24, 2009

Re: [Pharo-project] New pharo images

by StÃ©phane Ducasse

Yes now we are just looking for the magic incanation to install them as title, code font.... Stef On Dec 24, 2009, at 11:44 AM, Alain Plantec wrote: > StÃ©phane Ducasse a Ã©crit : >>> 2009/12/24 StÃ©phane Ducasse <stephane.ducasse(a)inria.fr>: >>> >>>> Damien in 1.1 may be we should put the nice little font of Cuis on :) >>>> >>> Tell me what I should do. >>> >> >> We should check the code of settings to see how the preferences is done >> when we press the launch button on the side of the install bitmap DejaVu fonts >> > I've checked, we have "bitmap dejavu sans" with sizes 7, 9 and 12. > Alain > > _______________________________________________ > Pharo-project mailing list > Pharo-project(a)lists.gforge.inria.fr > http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project

Dec. 24, 2009

Re: [Pharo-project] Fwd: [squeak-dev] The Trunk: Traits-nice.248.mcz

by StÃ©phane Ducasse

do you have a slice for pharo? Adrian is on holidays deep in the swiss moutain with no internet connection.... But who knows :) Stef On Dec 24, 2009, at 11:53 AM, Nicolas Cellier wrote: > For Trait experts only. > > > ---------- Forwarded message ---------- > From: <commits(a)source.squeak.org> > Date: 2009/12/24 > Subject: [squeak-dev] The Trunk: Traits-nice.248.mcz > To: squeak-dev(a)lists.squeakfoundation.org, packages(a)lists.squeakfoundation.org > > > Nicolas Cellier uploaded a new version of Traits to project The Trunk: > http://source.squeak.org/trunk/Traits-nice.248.mcz > > ==================== Summary ==================== > > Name: Traits-nice.248 > Author: nice > Time: 24 December 2009, 11:49:10 am > UUID: 557593d7-1db7-2347-bf40-2d40e3b91f55 > Ancestors: Traits-nice.247 > > Move FixedIdentitySet off the Array hierarchy. > Provide a fast implementation using MethodDictionary tricks > - handles collisions (instead of blindly ignoring the entry) > - eventually grow. > > I did not understand previous design decision... > The conflict just did happen (I put a halt: and caught one in Object...) > According to my own scale, make it work > make it fast. > > Rationale about the new design: > #grow costs, but I think it is user responsibility to fix a > reasonnable capacity. > collisions handling should not cost much (except above 4096 entries) > > If any expert knowing the reasons for this class and knowing how to > fire the profiling tests could have a look, thanks... > > =============== Diff against Traits-nice.247 =============== > > Item was changed: > + Collection variableSubclass: #FixedIdentitySet > + instanceVariableNames: 'tally capacity hashShift' > - Array variableSubclass: #FixedIdentitySet > - instanceVariableNames: 'tally capacity' > classVariableNames: '' > poolDictionaries: '' > category: 'Traits-Requires'! > > + !FixedIdentitySet commentStamp: 'nice 12/24/2009 11:46' prior: 0! > + This is a fast implementation of fixed size identity sets. > + Same algorithm as MethodDictionary are used, and thus > FixedIdentitySet is to IdentitySet what MethodDictionary is to > IdentityDictionary. > + The main features are: > + 1) do not use an array instance variable so as to fast-up creation > and every access > + 2) due to the fixed allocated size, growing costs an expensive > #become: operation. Preallocate me with care. > + 3) my size is a power of two so the the hashing algorithm be most efficient. > + 4) for maximum random access efficiency, at least half the storage > area is always kept empty > - !FixedIdentitySet commentStamp: 'NS 5/26/2005 13:00' prior: 0! > - This is a fast but lazy implementation of fixed size identity sets. > The two main difference to regular identity sets are: > - > - 1) These identity sets have a fixed size. If they are full, adding > another element doesn't have any effect. > - 2) No rehashing. If two elements were to be stored on the same > position in the underlying array, one of them is simply discarded. > > + Unlike MethodDictionary, this class will scale a bit better over the > 4096 basicSize limit inherent to identityHash, thanks to a proper > bitShift.! > - As a consequence of (1) and (2), these identity sets are very fast!! > Note that this class inherits form Array. This is not clean but > reduces memory overhead when instances are created.! > > Item was added: > + ----- Method: FixedIdentitySet>>removeAll (in category 'removing') ----- > + removeAll > + tally = 0 ifTrue: [^self]. > + 1 to: self basicSize do: [:i | self basicAt: i put: nil]. > + tally := 0! > > Item was changed: > + ----- Method: FixedIdentitySet>>add: (in category 'adding') ----- > - ----- Method: FixedIdentitySet>>add: (in category 'accessing') ----- > add: anObject > + | index | > + index := self scanFor: anObject. > + (self basicAt: index) > + ifNil: [ > + self basicAt: index put: anObject. > + tally := tally + 1. > + self isFull ifTrue: [ self grow ]] > + "ifNotNil: [] already inside". > + ^anObject! > - | index old | > - self isFull ifTrue: [^ false]. > - index := self indexOf: anObject. > - old := self basicAt: index. > - old == anObject ifTrue: [^ true]. > - old ifNotNil: [^ false]. > - self basicAt: index put: anObject. > - tally := tally + 1. > - ^ true! > > Item was changed: > + ----- Method: FixedIdentitySet>>addAll:notIn: (in category 'adding') ----- > - ----- Method: FixedIdentitySet>>addAll:notIn: (in category 'accessing') ----- > addAll: aCollection notIn: notCollection > aCollection do: [:each | > - self isFull ifTrue: [^ self]. > (notCollection includes: each) ifFalse: [self add: each]. > ].! > > Item was changed: > ----- Method: FixedIdentitySet class>>with:with:with:with:with: (in > category 'instance creation') ----- > with: firstObject with: secondObject with: thirdObject with: > fourthObject with: fifthObject > "Answer an instance of me, containing the five arguments as the > elements." > > + ^ (self new: 5) > - ^ self new > add: firstObject; > add: secondObject; > add: thirdObject; > add: fourthObject; > add: fifthObject; > yourself! > > Item was changed: > ----- Method: FixedIdentitySet class>>with:with:with:with:with:with: > (in category 'instance creation') ----- > with: firstObject with: secondObject with: thirdObject with: > fourthObject with: fifthObject with: sixthObject > "Answer an instance of me, containing the six arguments as the elements." > > + ^ (self new: 6) > - ^ self new > add: firstObject; > add: secondObject; > add: thirdObject; > add: fourthObject; > add: fifthObject; > add: sixthObject; > yourself! > > Item was changed: > + ----- Method: FixedIdentitySet class>>new (in category 'instance > creation') ----- > - ----- Method: FixedIdentitySet class>>new (in category 'constants') ----- > new > ^ self new: self defaultSize! > > Item was added: > + ----- Method: FixedIdentitySet>>grow (in category 'private') ----- > + grow > + | newSelf | > + newSelf := self species new: capacity * 2. "This will double > the capacity" > + self do: [ :anObject | newSelf add: anObject ]. > + self become: newSelf! > > Item was changed: > + ----- Method: FixedIdentitySet>>includes: (in category 'testing') ----- > + includes: aSymbol > + "This override assumes that pointsTo is a fast primitive" > + > + aSymbol ifNil: [^ false]. > + ^ self pointsTo: aSymbol! > - ----- Method: FixedIdentitySet>>includes: (in category 'accessing') ----- > - includes: anObject > - ^ (self basicAt: (self indexOf: anObject)) == anObject! > > Item was added: > + ----- Method: FixedIdentitySet>>fixCollisionsFrom: (in category > 'private') ----- > + fixCollisionsFrom: start > + "The element at start has been removed and replaced by nil. > + This method moves forward from there, relocating any entries > + that had been placed below due to collisions with this one." > + > + | key index mask | > + index := start. > + mask := self basicSize - 1. > + [ (key := self basicAt: (index := (index bitAnd: mask) + 1)) > == nil ] whileFalse: [ > + | newIndex | > + (newIndex := self scanFor: key) = index ifFalse: [ > + | element | > + element := self basicAt: index. > + self basicAt: index put: (self basicAt: newIndex). > + self basicAt: newIndex put: element.] ]! > > Item was changed: > + ----- Method: FixedIdentitySet class>>new: (in category 'instance > creation') ----- > - ----- Method: FixedIdentitySet class>>new: (in category 'constants') ----- > new: anInteger > + ^ (self basicNew: (self arraySizeForCapacity: anInteger)) > initializeCapacity: anInteger! > - ^ (super new: (self arraySizeForCapacity: anInteger)) > initializeCapacity: anInteger! > > Item was changed: > + ----- Method: FixedIdentitySet>>remove:ifAbsent: (in category > 'removing') ----- > - ----- Method: FixedIdentitySet>>remove:ifAbsent: (in category > 'accessing') ----- > remove: anObject ifAbsent: aBlock > + | index element | > + index := self scanFor: anObject. > + (element := self basicAt: index) ifNil: [ ^aBlock value ]. > + self basicAt: index put: nil. > + tally := tally - 1. > + self fixCollisionsFrom: index. > + ^element! > - | index | > - index := self indexOf: anObject. > - ^ (self basicAt: index) == anObject > - ifTrue: [self basicAt: index put: nil. tally := tally > - 1. anObject] > - ifFalse: [aBlock value].! > > Item was added: > + ----- Method: FixedIdentitySet>>rehash (in category 'private') ----- > + rehash > + | newSelf | > + newSelf := self species new: self size. > + self do: [ :anObject | newSelf add: anObject ]. > + ^newSelf! > > Item was changed: > ----- Method: FixedIdentitySet>>initializeCapacity: (in category > 'initialize-release') ----- > initializeCapacity: anInteger > tally := 0. > + capacity := anInteger. > + hashShift := self basicSize highBit - 4096 highBit max: 0! > - capacity := anInteger.! > > Item was changed: > + ----- Method: FixedIdentitySet class>>arraySizeForCapacity: (in > category 'private') ----- > - ----- Method: FixedIdentitySet class>>arraySizeForCapacity: (in > category 'constants') ----- > arraySizeForCapacity: anInteger > "Because of the hash performance, the array size is always a power of 2 > and at least twice as big as the capacity anInteger" > > ^ anInteger <= 0 > ifTrue: [0] > ifFalse: [1 << (anInteger << 1 - 1) highBit].! > > Item was added: > + ----- Method: FixedIdentitySet>>scanFor: (in category 'private') ----- > + 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 raise an error if no slot is found. This > method will be overridden in various subclasses that have different > interpretations for matching elements." > + > + | index start mask | > + anObject ifNil: [self error: 'This class collection cannot > handle nil as an element']. > + mask := self basicSize - 1. > + index := start := ((anObject identityHash bitShift: hashShift) > bitAnd: mask) + 1. > + [ > + | element | > + ((element := self basicAt: index) == nil or: [ element > == anObject ]) > + ifTrue: [ ^index ]. > + (index := (index bitAnd: mask) + 1) = start ] whileFalse. > + self errorNoFreeSpace! > > Item was removed: > - ----- Method: FixedIdentitySet>>destructiveAdd: (in category > 'accessing') ----- > - destructiveAdd: anObject > - | index old | > - self isFull ifTrue: [^ false]. > - index := self indexOf: anObject. > - old := self basicAt: index. > - self basicAt: index put: anObject. > - old ifNil: [tally := tally + 1]. > - ^ true! > > Item was removed: > - ----- Method: FixedIdentitySet>>notFull (in category 'testing') ----- > - notFull > - ^ tally < capacity! > > Item was removed: > - ----- Method: FixedIdentitySet>>addAll: (in category 'accessing') ----- > - addAll: aCollection > - aCollection do: [:each | > - self isFull ifTrue: [^ self]. > - self add: each. > - ].! > > Item was removed: > - ----- Method: FixedIdentitySet>>indexOf: (in category 'private') ----- > - indexOf: anObject > - anObject isNil ifTrue: [self error: 'This class collection > cannot handle nil as an element']. > - ^ (anObject identityHash bitAnd: self basicSize - 1) + 1! > > _______________________________________________ > Pharo-project mailing list > Pharo-project(a)lists.gforge.inria.fr > http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project

Dec. 24, 2009

Re: [Pharo-project] Fwd: [squeak-dev] The Trunk: Traits-nice.248.mcz

by StÃ©phane Ducasse

Thanks nicolas there are part of traits that inherit heavy optimisation that nathanael did in 2002-3 to get subs second browser update showing traits and classes feedback. One of these days we will have to clean that too. Stef On Dec 24, 2009, at 11:53 AM, Nicolas Cellier wrote: > For Trait experts only. > > > ---------- Forwarded message ---------- > From: <commits(a)source.squeak.org> > Date: 2009/12/24 > Subject: [squeak-dev] The Trunk: Traits-nice.248.mcz > To: squeak-dev(a)lists.squeakfoundation.org, packages(a)lists.squeakfoundation.org > > > Nicolas Cellier uploaded a new version of Traits to project The Trunk: > http://source.squeak.org/trunk/Traits-nice.248.mcz > > ==================== Summary ==================== > > Name: Traits-nice.248 > Author: nice > Time: 24 December 2009, 11:49:10 am > UUID: 557593d7-1db7-2347-bf40-2d40e3b91f55 > Ancestors: Traits-nice.247 > > Move FixedIdentitySet off the Array hierarchy. > Provide a fast implementation using MethodDictionary tricks > - handles collisions (instead of blindly ignoring the entry) > - eventually grow. > > I did not understand previous design decision... > The conflict just did happen (I put a halt: and caught one in Object...) > According to my own scale, make it work > make it fast. > > Rationale about the new design: > #grow costs, but I think it is user responsibility to fix a > reasonnable capacity. > collisions handling should not cost much (except above 4096 entries) > > If any expert knowing the reasons for this class and knowing how to > fire the profiling tests could have a look, thanks... > > =============== Diff against Traits-nice.247 =============== > > Item was changed: > + Collection variableSubclass: #FixedIdentitySet > + instanceVariableNames: 'tally capacity hashShift' > - Array variableSubclass: #FixedIdentitySet > - instanceVariableNames: 'tally capacity' > classVariableNames: '' > poolDictionaries: '' > category: 'Traits-Requires'! > > + !FixedIdentitySet commentStamp: 'nice 12/24/2009 11:46' prior: 0! > + This is a fast implementation of fixed size identity sets. > + Same algorithm as MethodDictionary are used, and thus > FixedIdentitySet is to IdentitySet what MethodDictionary is to > IdentityDictionary. > + The main features are: > + 1) do not use an array instance variable so as to fast-up creation > and every access > + 2) due to the fixed allocated size, growing costs an expensive > #become: operation. Preallocate me with care. > + 3) my size is a power of two so the the hashing algorithm be most efficient. > + 4) for maximum random access efficiency, at least half the storage > area is always kept empty > - !FixedIdentitySet commentStamp: 'NS 5/26/2005 13:00' prior: 0! > - This is a fast but lazy implementation of fixed size identity sets. > The two main difference to regular identity sets are: > - > - 1) These identity sets have a fixed size. If they are full, adding > another element doesn't have any effect. > - 2) No rehashing. If two elements were to be stored on the same > position in the underlying array, one of them is simply discarded. > > + Unlike MethodDictionary, this class will scale a bit better over the > 4096 basicSize limit inherent to identityHash, thanks to a proper > bitShift.! > - As a consequence of (1) and (2), these identity sets are very fast!! > Note that this class inherits form Array. This is not clean but > reduces memory overhead when instances are created.! > > Item was added: > + ----- Method: FixedIdentitySet>>removeAll (in category 'removing') ----- > + removeAll > + tally = 0 ifTrue: [^self]. > + 1 to: self basicSize do: [:i | self basicAt: i put: nil]. > + tally := 0! > > Item was changed: > + ----- Method: FixedIdentitySet>>add: (in category 'adding') ----- > - ----- Method: FixedIdentitySet>>add: (in category 'accessing') ----- > add: anObject > + | index | > + index := self scanFor: anObject. > + (self basicAt: index) > + ifNil: [ > + self basicAt: index put: anObject. > + tally := tally + 1. > + self isFull ifTrue: [ self grow ]] > + "ifNotNil: [] already inside". > + ^anObject! > - | index old | > - self isFull ifTrue: [^ false]. > - index := self indexOf: anObject. > - old := self basicAt: index. > - old == anObject ifTrue: [^ true]. > - old ifNotNil: [^ false]. > - self basicAt: index put: anObject. > - tally := tally + 1. > - ^ true! > > Item was changed: > + ----- Method: FixedIdentitySet>>addAll:notIn: (in category 'adding') ----- > - ----- Method: FixedIdentitySet>>addAll:notIn: (in category 'accessing') ----- > addAll: aCollection notIn: notCollection > aCollection do: [:each | > - self isFull ifTrue: [^ self]. > (notCollection includes: each) ifFalse: [self add: each]. > ].! > > Item was changed: > ----- Method: FixedIdentitySet class>>with:with:with:with:with: (in > category 'instance creation') ----- > with: firstObject with: secondObject with: thirdObject with: > fourthObject with: fifthObject > "Answer an instance of me, containing the five arguments as the > elements." > > + ^ (self new: 5) > - ^ self new > add: firstObject; > add: secondObject; > add: thirdObject; > add: fourthObject; > add: fifthObject; > yourself! > > Item was changed: > ----- Method: FixedIdentitySet class>>with:with:with:with:with:with: > (in category 'instance creation') ----- > with: firstObject with: secondObject with: thirdObject with: > fourthObject with: fifthObject with: sixthObject > "Answer an instance of me, containing the six arguments as the elements." > > + ^ (self new: 6) > - ^ self new > add: firstObject; > add: secondObject; > add: thirdObject; > add: fourthObject; > add: fifthObject; > add: sixthObject; > yourself! > > Item was changed: > + ----- Method: FixedIdentitySet class>>new (in category 'instance > creation') ----- > - ----- Method: FixedIdentitySet class>>new (in category 'constants') ----- > new > ^ self new: self defaultSize! > > Item was added: > + ----- Method: FixedIdentitySet>>grow (in category 'private') ----- > + grow > + | newSelf | > + newSelf := self species new: capacity * 2. "This will double > the capacity" > + self do: [ :anObject | newSelf add: anObject ]. > + self become: newSelf! > > Item was changed: > + ----- Method: FixedIdentitySet>>includes: (in category 'testing') ----- > + includes: aSymbol > + "This override assumes that pointsTo is a fast primitive" > + > + aSymbol ifNil: [^ false]. > + ^ self pointsTo: aSymbol! > - ----- Method: FixedIdentitySet>>includes: (in category 'accessing') ----- > - includes: anObject > - ^ (self basicAt: (self indexOf: anObject)) == anObject! > > Item was added: > + ----- Method: FixedIdentitySet>>fixCollisionsFrom: (in category > 'private') ----- > + fixCollisionsFrom: start > + "The element at start has been removed and replaced by nil. > + This method moves forward from there, relocating any entries > + that had been placed below due to collisions with this one." > + > + | key index mask | > + index := start. > + mask := self basicSize - 1. > + [ (key := self basicAt: (index := (index bitAnd: mask) + 1)) > == nil ] whileFalse: [ > + | newIndex | > + (newIndex := self scanFor: key) = index ifFalse: [ > + | element | > + element := self basicAt: index. > + self basicAt: index put: (self basicAt: newIndex). > + self basicAt: newIndex put: element.] ]! > > Item was changed: > + ----- Method: FixedIdentitySet class>>new: (in category 'instance > creation') ----- > - ----- Method: FixedIdentitySet class>>new: (in category 'constants') ----- > new: anInteger > + ^ (self basicNew: (self arraySizeForCapacity: anInteger)) > initializeCapacity: anInteger! > - ^ (super new: (self arraySizeForCapacity: anInteger)) > initializeCapacity: anInteger! > > Item was changed: > + ----- Method: FixedIdentitySet>>remove:ifAbsent: (in category > 'removing') ----- > - ----- Method: FixedIdentitySet>>remove:ifAbsent: (in category > 'accessing') ----- > remove: anObject ifAbsent: aBlock > + | index element | > + index := self scanFor: anObject. > + (element := self basicAt: index) ifNil: [ ^aBlock value ]. > + self basicAt: index put: nil. > + tally := tally - 1. > + self fixCollisionsFrom: index. > + ^element! > - | index | > - index := self indexOf: anObject. > - ^ (self basicAt: index) == anObject > - ifTrue: [self basicAt: index put: nil. tally := tally > - 1. anObject] > - ifFalse: [aBlock value].! > > Item was added: > + ----- Method: FixedIdentitySet>>rehash (in category 'private') ----- > + rehash > + | newSelf | > + newSelf := self species new: self size. > + self do: [ :anObject | newSelf add: anObject ]. > + ^newSelf! > > Item was changed: > ----- Method: FixedIdentitySet>>initializeCapacity: (in category > 'initialize-release') ----- > initializeCapacity: anInteger > tally := 0. > + capacity := anInteger. > + hashShift := self basicSize highBit - 4096 highBit max: 0! > - capacity := anInteger.! > > Item was changed: > + ----- Method: FixedIdentitySet class>>arraySizeForCapacity: (in > category 'private') ----- > - ----- Method: FixedIdentitySet class>>arraySizeForCapacity: (in > category 'constants') ----- > arraySizeForCapacity: anInteger > "Because of the hash performance, the array size is always a power of 2 > and at least twice as big as the capacity anInteger" > > ^ anInteger <= 0 > ifTrue: [0] > ifFalse: [1 << (anInteger << 1 - 1) highBit].! > > Item was added: > + ----- Method: FixedIdentitySet>>scanFor: (in category 'private') ----- > + 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 raise an error if no slot is found. This > method will be overridden in various subclasses that have different > interpretations for matching elements." > + > + | index start mask | > + anObject ifNil: [self error: 'This class collection cannot > handle nil as an element']. > + mask := self basicSize - 1. > + index := start := ((anObject identityHash bitShift: hashShift) > bitAnd: mask) + 1. > + [ > + | element | > + ((element := self basicAt: index) == nil or: [ element > == anObject ]) > + ifTrue: [ ^index ]. > + (index := (index bitAnd: mask) + 1) = start ] whileFalse. > + self errorNoFreeSpace! > > Item was removed: > - ----- Method: FixedIdentitySet>>destructiveAdd: (in category > 'accessing') ----- > - destructiveAdd: anObject > - | index old | > - self isFull ifTrue: [^ false]. > - index := self indexOf: anObject. > - old := self basicAt: index. > - self basicAt: index put: anObject. > - old ifNil: [tally := tally + 1]. > - ^ true! > > Item was removed: > - ----- Method: FixedIdentitySet>>notFull (in category 'testing') ----- > - notFull > - ^ tally < capacity! > > Item was removed: > - ----- Method: FixedIdentitySet>>addAll: (in category 'accessing') ----- > - addAll: aCollection > - aCollection do: [:each | > - self isFull ifTrue: [^ self]. > - self add: each. > - ].! > > Item was removed: > - ----- Method: FixedIdentitySet>>indexOf: (in category 'private') ----- > - indexOf: anObject > - anObject isNil ifTrue: [self error: 'This class collection > cannot handle nil as an element']. > - ^ (anObject identityHash bitAnd: self basicSize - 1) + 1! > > _______________________________________________ > Pharo-project mailing list > Pharo-project(a)lists.gforge.inria.fr > http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project

Dec. 24, 2009

Re: [Pharo-project] What are MethodDictionary faults?

by StÃ©phane Ducasse

> Suppose you evaluate this steps: > > Smalltalk at: #MDFaultDict put: Dictionary new. > ImageSegment discoverActiveClasses > > .... do something here, browse, whatever .... > > ImageSegment activeClasses > > Here, you can change activeClasses to use recoverFromMDFaultWithTrace instead of recoverFromMDFault > and with this you can see who used that class. It is stored in Smalltalk at: #MDFaultDict Ok good to know that it is working. At some point doing that would just crash. > Ok...at least that is what I understood, but as this is not working, I am not sure. This is correct. > What I suggest: > - create a new category in the class and move all the methods that could be removed. Tag them as deprecated. do not deprecated them since this is working. :) > - in imageSegments just clean :) What is the link with imageSegment? > > > Ok. Perfect. > > Cheers > > Mariano > > Stef > _______________________________________________ > Pharo-project mailing list > Pharo-project(a)lists.gforge.inria.fr > http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project > > _______________________________________________ > Pharo-project mailing list > Pharo-project(a)lists.gforge.inria.fr > http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project

Dec. 24, 2009

Re: [Pharo-project] What are MethodDictionary faults?

by Mariano Martinez Peck

On Thu, Dec 24, 2009 at 11:46 AM, StÃ©phane Ducasse < stephane.ducasse(a)inria.fr> wrote: > > What's MW ? > > MethodWrapper. But you cannot wrap the complete system like do: (if I > remember correctly). > > ok > > Yes, I noticed that too. Is very probable that messages very general that > are used a lot will bring the class again. > > Yes the problem is to identify them. > We tried a bit not too much with mathieu but was not obvious > > yes haha > > That's the idea of the tracer. WIth this tracer you *should* be able to > see the messages chain that makes you bring the class (why it was used). But > I don't know if this stuff is working, as you said. > > which tracer? > > Suppose you evaluate this steps: Smalltalk at: #MDFaultDict put: Dictionary new. ImageSegment discoverActiveClasses .... do something here, browse, whatever .... ImageSegment activeClasses Here, you can change activeClasses to use recoverFromMDFaultWithTrace instead of recoverFromMDFault and with this you can see who used that class. It is stored in Smalltalk at: #MDFaultDict Ok...at least that is what I understood, but as this is not working, I am not sure. What I suggest: > - create a new category in the class and move all the methods that > could be removed. Tag them as deprecated. - in imageSegments just clean :) > > Ok. Perfect. Cheers Mariano Stef > _______________________________________________ > Pharo-project mailing list > Pharo-project(a)lists.gforge.inria.fr > http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project >

Dec. 24, 2009

[Pharo-project] Fwd: [squeak-dev] The Trunk: Traits-nice.248.mcz

by Nicolas Cellier

For Trait experts only. ---------- Forwarded message ---------- From: <commits(a)source.squeak.org> Date: 2009/12/24 Subject: [squeak-dev] The Trunk: Traits-nice.248.mcz To: squeak-dev(a)lists.squeakfoundation.org, packages(a)lists.squeakfoundation.org Nicolas Cellier uploaded a new version of Traits to project The Trunk: http://source.squeak.org/trunk/Traits-nice.248.mcz ==================== Summary ==================== Name: Traits-nice.248 Author: nice Time: 24 December 2009, 11:49:10 am UUID: 557593d7-1db7-2347-bf40-2d40e3b91f55 Ancestors: Traits-nice.247 Move FixedIdentitySet off the Array hierarchy. Provide a fast implementation using MethodDictionary tricks - handles collisions (instead of blindly ignoring the entry) - eventually grow. I did not understand previous design decision... The conflict just did happen (I put a halt: and caught one in Object...) According to my own scale, make it work > make it fast. Rationale about the new design: #grow costs, but I think it is user responsibility to fix a reasonnable capacity. collisions handling should not cost much (except above 4096 entries) If any expert knowing the reasons for this class and knowing how to fire the profiling tests could have a look, thanks... =============== Diff against Traits-nice.247 =============== Item was changed: + Collection variableSubclass: #FixedIdentitySet + Â Â Â instanceVariableNames: 'tally capacity hashShift' - Array variableSubclass: #FixedIdentitySet - Â Â Â instanceVariableNames: 'tally capacity' Â Â Â Â classVariableNames: '' Â Â Â Â poolDictionaries: '' Â Â Â Â category: 'Traits-Requires'! + !FixedIdentitySet commentStamp: 'nice 12/24/2009 11:46' prior: 0! + This is a fast implementation of fixed size identity sets. + Same algorithm as MethodDictionary are used, and thus FixedIdentitySet is to IdentitySet what MethodDictionary is to IdentityDictionary. + The main features are: + 1) do not use an array instance variable so as to fast-up creation and every access + 2) due to the fixed allocated size, growing costs an expensive #become: operation. Preallocate me with care. + 3) my size is a power of two so the the hashing algorithm be most efficient. + 4) for maximum random access efficiency, at least half the storage area is always kept empty - !FixedIdentitySet commentStamp: 'NS 5/26/2005 13:00' prior: 0! - This is a fast but lazy implementation of fixed size identity sets. The two main difference to regular identity sets are: - - 1) These identity sets have a fixed size. If they are full, adding another element doesn't have any effect. - 2) No rehashing. If two elements were to be stored on the same position in the underlying array, one of them is simply discarded. + Unlike MethodDictionary, this class will scale a bit better over the 4096 basicSize limit inherent to identityHash, thanks to a proper bitShift.! - As a consequence of (1) and (2), these identity sets are very fast!! Note that this class inherits form Array. This is not clean but reduces memory overhead when instances are created.! Item was added: + ----- Method: FixedIdentitySet>>removeAll (in category 'removing') ----- + removeAll + Â Â Â tally = 0 ifTrue: [^self]. + Â Â Â 1 to: self basicSize do: [:i | self basicAt: i put: nil]. + Â Â Â tally := 0! Item was changed: + ----- Method: FixedIdentitySet>>add: (in category 'adding') ----- - ----- Method: FixedIdentitySet>>add: (in category 'accessing') ----- Â add: anObject + Â Â Â | index | + Â Â Â index := self scanFor: anObject. + Â Â Â (self basicAt: index) + Â Â Â Â Â Â Â ifNil: [ + Â Â Â Â Â Â Â Â Â Â Â self basicAt: index put: anObject. + Â Â Â Â Â Â Â Â Â Â Â tally := tally + 1. + Â Â Â Â Â Â Â Â Â Â Â self isFull ifTrue: [ self grow ]] + Â Â Â Â Â Â Â "ifNotNil: [] already inside". + Â Â Â ^anObject! - Â Â Â | index old | - Â Â Â self isFull ifTrue: [^ false]. - Â Â Â index := self indexOf: anObject. - Â Â Â old := self basicAt: index. - Â Â Â old == anObject ifTrue: [^ true]. - Â Â Â old ifNotNil: [^ false]. - Â Â Â self basicAt: index put: anObject. - Â Â Â tally := tally + 1. - Â Â Â ^ true! Item was changed: + ----- Method: FixedIdentitySet>>addAll:notIn: (in category 'adding') ----- - ----- Method: FixedIdentitySet>>addAll:notIn: (in category 'accessing') ----- Â addAll: aCollection notIn: notCollection Â Â Â Â aCollection do: [:each | - Â Â Â Â Â Â Â self isFull ifTrue: [^ self]. Â Â Â Â Â Â Â Â (notCollection includes: each) ifFalse: [self add: each]. Â Â Â Â ].! Item was changed: Â ----- Method: FixedIdentitySet class>>with:with:with:with:with: (in category 'instance creation') ----- Â with: firstObject with: secondObject with: thirdObject with: fourthObject with: fifthObject Â Â Â Â "Answer an instance of me, containing the five arguments as the elements." + Â Â Â ^ (self new: 5) - Â Â Â ^ self new Â Â Â Â Â Â Â Â add: firstObject; Â Â Â Â Â Â Â Â add: secondObject; Â Â Â Â Â Â Â Â add: thirdObject; Â Â Â Â Â Â Â Â add: fourthObject; Â Â Â Â Â Â Â Â add: fifthObject; Â Â Â Â Â Â Â Â yourself! Item was changed: Â ----- Method: FixedIdentitySet class>>with:with:with:with:with:with: (in category 'instance creation') ----- Â with: firstObject with: secondObject with: thirdObject with: fourthObject with: fifthObject with: sixthObject Â Â Â Â "Answer an instance of me, containing the six arguments as the elements." + Â Â Â ^ (self new: 6) - Â Â Â ^ self new Â Â Â Â Â Â Â Â add: firstObject; Â Â Â Â Â Â Â Â add: secondObject; Â Â Â Â Â Â Â Â add: thirdObject; Â Â Â Â Â Â Â Â add: fourthObject; Â Â Â Â Â Â Â Â add: fifthObject; Â Â Â Â Â Â Â Â add: sixthObject; Â Â Â Â Â Â Â Â yourself! Item was changed: + ----- Method: FixedIdentitySet class>>new (in category 'instance creation') ----- - ----- Method: FixedIdentitySet class>>new (in category 'constants') ----- Â new Â Â Â Â ^ self new: self defaultSize! Item was added: + ----- Method: FixedIdentitySet>>grow (in category 'private') ----- + grow + Â Â Â | newSelf | + Â Â Â newSelf := self species new: capacity * 2. Â "This will double the capacity" + Â Â Â self do: [ :anObject | newSelf add: anObject ]. + Â Â Â self become: newSelf! Item was changed: + ----- Method: FixedIdentitySet>>includes: (in category 'testing') ----- + includes: aSymbol + Â Â Â "This override assumes that pointsTo is a fast primitive" + + Â Â Â aSymbol ifNil: [^ false]. + Â Â Â ^ self pointsTo: aSymbol! - ----- Method: FixedIdentitySet>>includes: (in category 'accessing') ----- - includes: anObject - Â Â Â ^ (self basicAt: (self indexOf: anObject)) == anObject! Item was added: + ----- Method: FixedIdentitySet>>fixCollisionsFrom: (in category 'private') ----- + fixCollisionsFrom: start + Â Â Â "The element at start has been removed and replaced by nil. + Â Â Â This method moves forward from there, relocating any entries + Â Â Â that had been placed below due to collisions with this one." + + Â Â Â | key index mask | + Â Â Â index := start. + Â Â Â mask := self basicSize - 1. + Â Â Â [ (key := self basicAt: (index := (index bitAnd: mask) + 1)) == nil ] whileFalse: [ + Â Â Â Â Â Â Â | newIndex | + Â Â Â Â Â Â Â (newIndex := self scanFor: key) = index ifFalse: [ + Â Â Â Â Â Â Â Â Â Â Â | element | + Â Â Â Â Â Â Â Â Â Â Â element := self basicAt: index. + Â Â Â Â Â Â Â Â Â Â Â self basicAt: index put: (self basicAt: newIndex). + Â Â Â Â Â Â Â Â Â Â Â self basicAt: newIndex put: element.] ]! Item was changed: + ----- Method: FixedIdentitySet class>>new: (in category 'instance creation') ----- - ----- Method: FixedIdentitySet class>>new: (in category 'constants') ----- Â new: anInteger + Â Â Â ^ (self basicNew: (self arraySizeForCapacity: anInteger)) initializeCapacity: anInteger! - Â Â Â ^ (super new: (self arraySizeForCapacity: anInteger)) initializeCapacity: anInteger! Item was changed: + ----- Method: FixedIdentitySet>>remove:ifAbsent: (in category 'removing') ----- - ----- Method: FixedIdentitySet>>remove:ifAbsent: (in category 'accessing') ----- Â remove: anObject ifAbsent: aBlock + Â Â Â | index element | + Â Â Â index := self scanFor: anObject. + Â Â Â (element := self basicAt: index) ifNil: [ ^aBlock value ]. + Â Â Â self basicAt: index put: nil. + Â Â Â tally := tally - 1. + Â Â Â self fixCollisionsFrom: index. + Â Â Â ^element! - Â Â Â | index | - Â Â Â index := self indexOf: anObject. - Â Â Â ^ (self basicAt: index) == anObject - Â Â Â Â Â Â Â ifTrue: [self basicAt: index put: nil. tally := tally - 1. anObject] - Â Â Â Â Â Â Â ifFalse: [aBlock value].! Item was added: + ----- Method: FixedIdentitySet>>rehash (in category 'private') ----- + rehash + Â Â Â | newSelf | + Â Â Â newSelf := self species new: self size. + Â Â Â self do: [ :anObject | newSelf add: anObject ]. + Â Â Â ^newSelf! Item was changed: Â ----- Method: FixedIdentitySet>>initializeCapacity: (in category 'initialize-release') ----- Â initializeCapacity: anInteger Â Â Â Â tally := 0. + Â Â Â capacity := anInteger. + Â Â Â hashShift := self basicSize highBit - 4096 highBit max: 0! - Â Â Â capacity := anInteger.! Item was changed: + ----- Method: FixedIdentitySet class>>arraySizeForCapacity: (in category 'private') ----- - ----- Method: FixedIdentitySet class>>arraySizeForCapacity: (in category 'constants') ----- Â arraySizeForCapacity: anInteger Â Â Â Â "Because of the hash performance, the array size is always a power of 2 Â Â Â Â and at least twice as big as the capacity anInteger" Â Â Â Â ^ anInteger <= 0 Â Â Â Â Â Â Â Â ifTrue: [0] Â Â Â Â Â Â Â Â ifFalse: [1 << (anInteger << 1 - 1) highBit].! Item was added: + ----- Method: FixedIdentitySet>>scanFor: (in category 'private') ----- + 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 raise an error if no slot is found. This method will be overridden in various subclasses that have different interpretations for matching elements." + + Â Â Â | index start mask | + Â Â Â anObject ifNil: [self error: 'This class collection cannot handle nil as an element']. + Â Â Â mask := self basicSize - 1. + Â Â Â index := start := ((anObject identityHash bitShift: hashShift) bitAnd: mask) + 1. + Â Â Â [ + Â Â Â Â Â Â Â | element | + Â Â Â Â Â Â Â ((element := self basicAt: index) == nil or: [ element == anObject ]) + Â Â Â Â Â Â Â Â Â Â Â ifTrue: [ ^index ]. + Â Â Â Â Â Â Â (index := (index bitAnd: mask) + 1) = start ] whileFalse. + Â Â Â self errorNoFreeSpace! Item was removed: - ----- Method: FixedIdentitySet>>destructiveAdd: (in category 'accessing') ----- - destructiveAdd: anObject - Â Â Â | index old | - Â Â Â self isFull ifTrue: [^ false]. - Â Â Â index := self indexOf: anObject. - Â Â Â old := self basicAt: index. - Â Â Â self basicAt: index put: anObject. - Â Â Â old ifNil: [tally := tally + 1]. - Â Â Â ^ true! Item was removed: - ----- Method: FixedIdentitySet>>notFull (in category 'testing') ----- - notFull - Â Â Â ^ tally < capacity! Item was removed: - ----- Method: FixedIdentitySet>>addAll: (in category 'accessing') ----- - addAll: aCollection - Â Â Â aCollection do: [:each | - Â Â Â Â Â Â Â self isFull ifTrue: [^ self]. - Â Â Â Â Â Â Â self add: each. - Â Â Â ].! Item was removed: - ----- Method: FixedIdentitySet>>indexOf: (in category 'private') ----- - indexOf: anObject - Â Â Â anObject isNil ifTrue: [self error: 'This class collection cannot handle nil as an element']. - Â Â Â ^ (anObject identityHash bitAnd: self basicSize - 1) + 1!

Dec. 24, 2009