[Pharo-project] Fwd: [squeak-dev] The Trunk: Traits-nice.248.mcz
For Trait experts only. ---------- Forwarded message ---------- From: <commits@source.squeak.org> Date: 2009/12/24 Subject: [squeak-dev] The Trunk: Traits-nice.248.mcz To: squeak-dev@lists.squeakfoundation.org, packages@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!
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@source.squeak.org> Date: 2009/12/24 Subject: [squeak-dev] The Trunk: Traits-nice.248.mcz To: squeak-dev@lists.squeakfoundation.org, packages@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@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
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@source.squeak.org> Date: 2009/12/24 Subject: [squeak-dev] The Trunk: Traits-nice.248.mcz To: squeak-dev@lists.squeakfoundation.org, packages@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@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
2009/12/24 Stéphane Ducasse <stephane.ducasse@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@source.squeak.org> Date: 2009/12/24 Subject: [squeak-dev] The Trunk: Traits-nice.248.mcz To: squeak-dev@lists.squeakfoundation.org, packages@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@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
:) 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....)
2009/12/24 Stéphane Ducasse <stephane.ducasse@inria.fr>:
do you have a slice for pharo?
http://code.google.com/p/pharo/issues/detail?id=1675 http://code.google.com/p/pharo/issues/detail?id=1676 http://code.google.com/p/pharo/issues/detail?id=1677 And I can offer you a soda... If I ever go to Lille, prepare the beers. Nicolas
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@source.squeak.org> Date: 2009/12/24 Subject: [squeak-dev] The Trunk: Traits-nice.248.mcz To: squeak-dev@lists.squeakfoundation.org, packages@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@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
Thanks I will integrate that later. (argh I should not read mails and finish that crap of file to be filled up) Stef On Dec 24, 2009, at 4:50 PM, Nicolas Cellier wrote:
2009/12/24 Stéphane Ducasse <stephane.ducasse@inria.fr>:
do you have a slice for pharo?
http://code.google.com/p/pharo/issues/detail?id=1675 http://code.google.com/p/pharo/issues/detail?id=1676 http://code.google.com/p/pharo/issues/detail?id=1677
And I can offer you a soda... If I ever go to Lille, prepare the beers.
Nicolas
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@source.squeak.org> Date: 2009/12/24 Subject: [squeak-dev] The Trunk: Traits-nice.248.mcz To: squeak-dev@lists.squeakfoundation.org, packages@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@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
_______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
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: <commits@source.squeak.org> Date: 2009/12/24 Subject: [squeak-dev] The Trunk: Traits-nice.248.mcz To: squeak-dev@lists.squeakfoundation.org, packages@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@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
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: <commits@source.squeak.org> Date: 2009/12/24 Subject: [squeak-dev] The Trunk: Traits-nice.248.mcz To: squeak-dev@lists.squeakfoundation.org, packages@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@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
participants (3)
-
Adrian Lienhard -
Nicolas Cellier -
Stéphane Ducasse