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 <[email protected]>:
>> 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: <[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
_______________________________________________
Pharo-project mailing list
[email protected]
http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
