- Pharo-dev - lists.pharo.org

Re: [Pharo-project] Fwd: hasEqualElements:

by Eliot Miranda

On Thu, Dec 24, 2009 at 12:21 PM, Levente Uzonyi <leves(a)elte.hu> wrote: > On Thu, 24 Dec 2009, csrabak(a)bol.com.br wrote: > > > Em 24/12/2009 01:21, Levente Uzonyi < leves(a)elte.hu > escreveu: > > > >> On Thu, 24 Dec 2009, csrabak(a)bol.com.br wrote: > >> > >>> Em 23/12/2009 22:51, Nicolas Cellier escreveu: > >>> > >>>> 2009/12/24 : > >>>>> Igor, Sometimes a fallacy can be written by clever people, by > >>>>> accident. If you pay attention to the line: (size := self size) > >>>>> = otherCollection size ifFalse: [^false]. I all Smalltalks > >>>>> [Except Pharo to what I wrote a comment in issue 1637 > >>>>> http://code.google.com/p/pharo/issues/detail?id=1637] this would > >>>>> return false if self be not Collection or otheCollection > >>>>> isKindOf: Collection not. This happens because in these > >>>>> Smalltalks Object>>size returns zero. > >>>>> Not so sure. Try 1.0 size, then 1.0 at: 1.0 size in you > >>>> favourite > >>>> dialect. > >>> Nicolas, > >>> In Squeak 3.10.2-7179: > >>> 1.0 size -> 2 "OK I'm surprised here" > >> It's not surprising since Float is a variable word subclass of > >> Number. :) > >> > >>> 1.0 at: 1.0 size -> 0 "this will not work anymore in Pharo because > >>> indices have to be Integer in Pharo right now" > >> The index is 2, so it will work. Btw, I wonder how pharo can force > >> Integer indices if the vm accepts Floats too. > >> > > Levente, > > > > In fact VM _does_ _not_ accept Floats as indices. There is a hack in > > Squeak code (which in fact contradicts the comment in the method) in > > the #at: methods that make a conversion from Number to Integer. > > > > If you comment that code out you'll see the VM #at: (via the primitive) > > will fail with Floats. > > True, and cool, since this hack can be removed. Now I wonder why did I > assume that the vm has this hack. :) > This 'hack' is as old as Smalltalk-80 V2 and is AFAICT in all Smalltalk-80 derived Smalltalks: !Object methodsFor: 'accessing'! at: index "Answer the value of an indexable field in the receiver. Fail if the argument index is not an Integer or is out of bounds. Essential. See documentation in Object metaclass." <primitive: 60> index isInteger ifTrue: [self errorSubscriptBounds: index]. (index isKindOf: Number) ifTrue: [^self at: index truncated] ifFalse: [self errorNonIntegerIndex]! It is also free in the sense that the failure code is only invoked when the primitive fails and so adds nothing to the cost of successful accesses, which are the high dynamic frequency operation. It will also show up under profiling if one is concerned about efficiency, and so isn't a hidden cost. It is also in keeping with Smalltalk's mixed mode/arbitrary precision implicit coercion number system that one *can* use fractions or floats as indices. Stripping out coercions like this will make the system more brittle. So please do *not* remove this "hack". I think it's a feature and a useful one. > > Levente > > > > > -- > > Cesar Rabak > > > > _______________________________________________ > > Pharo-project mailing list > > Pharo-project(a)lists.gforge.inria.fr > > http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project > > > > _______________________________________________ > Pharo-project mailing list > Pharo-project(a)lists.gforge.inria.fr > http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project >

Dec. 24, 2009

Re: [Pharo-project] Fwd: hasEqualElements:

by Levente Uzonyi

On Thu, 24 Dec 2009, csrabak(a)bol.com.br wrote: > Em 24/12/2009 01:21, Levente Uzonyi < leves(a)elte.hu > escreveu: > >> On Thu, 24 Dec 2009, csrabak(a)bol.com.br wrote: >> >>> Em 23/12/2009 22:51, Nicolas Cellier escreveu: >>> >>>> 2009/12/24 : >>>>> Igor, Sometimes a fallacy can be written by clever people, by >>>>> accident. If you pay attention to the line: (size := self size) >>>>> = otherCollection size ifFalse: [^false]. I all Smalltalks >>>>> [Except Pharo to what I wrote a comment in issue 1637 >>>>> http://code.google.com/p/pharo/issues/detail?id=1637] this would >>>>> return false if self be not Collection or otheCollection >>>>> isKindOf: Collection not. This happens because in these >>>>> Smalltalks Object>>size returns zero. >>>>> Not so sure. Try 1.0 size, then 1.0 at: 1.0 size in you >>>> favourite >>>> dialect. >>> Nicolas, >>> In Squeak 3.10.2-7179: >>> 1.0 size -> 2 "OK I'm surprised here" >> It's not surprising since Float is a variable word subclass of >> Number. :) >> >>> 1.0 at: 1.0 size -> 0 "this will not work anymore in Pharo because >>> indices have to be Integer in Pharo right now" >> The index is 2, so it will work. Btw, I wonder how pharo can force >> Integer indices if the vm accepts Floats too. >> > Levente, > > In fact VM _does_ _not_ accept Floats as indices. There is a hack in > Squeak code (which in fact contradicts the comment in the method) in > the #at: methods that make a conversion from Number to Integer. > > If you comment that code out you'll see the VM #at: (via the primitive) > will fail with Floats. True, and cool, since this hack can be removed. Now I wonder why did I assume that the vm has this hack. :) Levente > > -- > Cesar Rabak > > _______________________________________________ > Pharo-project mailing list > Pharo-project(a)lists.gforge.inria.fr > http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project >

Dec. 24, 2009

[Pharo-project] Fonts

by Schwab,Wilhelm K

Hello all, I just looked at the 12.2 web image, and noted that the Fonts directory is gone, but the anti-aliased fonts appear to be working. Is there simple summary of the relevant changes and what they imply for the end user? It looks like good things have happened, but what? Lukas, are your build scripts on the Wiki updated for the changes? Bill

Dec. 24, 2009

Re: [Pharo-project] Search squeaksource for all senders of a method?

by csrabak＠bol.com.br

Yes. . . Christmas eve here so my reasoning is being impaired a little bit :-) []s -- Cesar Rabak Em 24/12/2009 15:29, Mariano Martinez Peck < marianopeck(a)gmail.com > escreveu: On Thu, Dec 24, 2009 at 6:10 PM, <csrabak(a)bol.com.br> wrote: I think we'll need to have squeaksource ported to Seaside to do this... I think squeaksource is already done with seaside. Did you wanted to say gemstone ? my 0.0199999.... -- Cesar Rabak Em 24/12/2009 02:16, Adrian Kuhn < akuhn(a)iam.unibe.ch > escreveu: I would like search squeaksource for all senders of a method. How could this be done? How would I approach doing this? --AA _______________________________________________ Pharo-project mailing list Pharo-project(a)lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project _______________________________________________ Pharo-project mailing list Pharo-project(a)lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project

Dec. 24, 2009

Re: [Pharo-project] Search squeaksource for all senders of a method?

by Dale Henrichs

It has been on the todo list for quite awhile ... I'm just getting around to getting the most recent SqueakSource running in GemStone ... the GemSource instance is still running the Seaside2.6 version:) For GemStone, the mcz files are stored in a Dictionary in the repository. Something to look forward to in the new year? Dale ----- "Lukas Renggli" <renggli(a)gmail.com> wrote: | It is on the nice-to-have list since the beginning (5 years). | Unfortunately there is currently no index and searching 7 GB of | compressed versions is not practically feasible either. | | Maybe the GemStone version has a solution to that? AFAIK they keep | the | versions all in the stone and could easily index the internal data. | | Lukas | | -- | Lukas Renggli | http://www.lukas-renggli.ch | | _______________________________________________ | Pharo-project mailing list | Pharo-project(a)lists.gforge.inria.fr | http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project

Dec. 24, 2009

Re: [Pharo-project] Search squeaksource for all senders of a method?

by Mariano Martinez Peck

On Thu, Dec 24, 2009 at 6:10 PM, <csrabak(a)bol.com.br> wrote: > I think we'll need to have squeaksource ported to Seaside to do this... > > I think squeaksource is already done with seaside. Did you wanted to say gemstone ? > my 0.0199999.... > > -- > Cesar Rabak > > > Em 24/12/2009 02:16, Adrian Kuhn < akuhn(a)iam.unibe.ch > escreveu: > > > I would like search squeaksource for all senders of a method. > How could this be done? How would I approach doing this? > > --AA > > > > _______________________________________________ > Pharo-project mailing list > Pharo-project(a)lists.gforge.inria.fr > http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project > > > _______________________________________________ > Pharo-project mailing list > Pharo-project(a)lists.gforge.inria.fr > http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project >

Dec. 24, 2009

Re: [Pharo-project] Search squeaksource for all senders of a method?

by csrabak＠bol.com.br

I think we'll need to have squeaksource ported to Seaside to do this... my 0.0199999.... -- Cesar Rabak Em 24/12/2009 02:16, Adrian Kuhn < akuhn(a)iam.unibe.ch > escreveu: I would like search squeaksource for all senders of a method. How could this be done? How would I approach doing this? --AA _______________________________________________ Pharo-project mailing list Pharo-project(a)lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project

Dec. 24, 2009

Re: [Pharo-project] Fwd: hasEqualElements:

by csrabak＠bol.com.br

Em 24/12/2009 01:21, Levente Uzonyi < leves(a)elte.hu > escreveu: > On Thu, 24 Dec 2009, csrabak(a)bol.com.br wrote: > > > Em 23/12/2009 22:51, Nicolas Cellier escreveu: > > > >> 2009/12/24 : > >>> Igor, Sometimes a fallacy can be written by clever people, by > >>> accident. If you pay attention to the line: (size := self size) > >>> = otherCollection size ifFalse: [^false]. I all Smalltalks > >>> [Except Pharo to what I wrote a comment in issue 1637 > >>> http://code.google.com/p/pharo/issues/detail?id=1637] this would > >>> return false if self be not Collection or otheCollection > >>> isKindOf: Collection not. This happens because in these > >>> Smalltalks Object>>size returns zero. > >>> Not so sure. Try 1.0 size, then 1.0 at: 1.0 size in you > >> favourite > >> dialect. > > Nicolas, > > In Squeak 3.10.2-7179: > > 1.0 size -> 2 "OK I'm surprised here" > It's not surprising since Float is a variable word subclass of > Number. :) > > > 1.0 at: 1.0 size -> 0 "this will not work anymore in Pharo because > > indices have to be Integer in Pharo right now" > The index is 2, so it will work. Btw, I wonder how pharo can force > Integer indices if the vm accepts Floats too. > Levente, In fact VM _does_ _not_ accept Floats as indices. There is a hack in Squeak code (which in fact contradicts the comment in the method) in the #at: methods that make a conversion from Number to Integer. If you comment that code out you'll see the VM #at: (via the primitive) will fail with Floats. -- Cesar Rabak

Dec. 24, 2009

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

by StÃ©phane Ducasse

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

Dec. 24, 2009

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

by Nicolas Cellier

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

Dec. 24, 2009