I would removed them or at least package them under Collections and remove them from Core.
On Dec 24, 2009, at 1:36 PM, Adrian Lienhard wrote: > On Dec 24, 2009, at 11:53 , Nicolas Cellier wrote: > >> For Trait experts only. > > Actually, this is not related to Traits... For historical reasons the > requires/provided algorithm by Nathanael (and Andrew Black and Daniel > Vainsencher?) was added together with Traits to 3.9 and hence it ended > up in the category 'Traits-Requires' and in the Traits package. > > I think we should fix this and move FixedIdentitySet into the > collection hierarchy and the classes RequiredSelectors etal. to their > own package. Are there any tools that use this data? Do we want to > keep this in the image at all? > > Cheers, > Adrian > > >> >> >> ---------- Forwarded message ---------- >> From: <[email protected]> >> Date: 2009/12/24 >> Subject: [squeak-dev] The Trunk: Traits-nice.248.mcz >> To: [email protected], >> [email protected] >> >> >> 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 >> [email protected] >> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project > > > _______________________________________________ > Pharo-project mailing list > [email protected] > http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project _______________________________________________ Pharo-project mailing list [email protected] http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
