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

[Pharo-project] Issue with traits

by Igor Stasenko

Create a trait: Trait named: #ABBA uses: {} category: 'ABBA'. - add a method #foo to ABBA trait Then create 2 classes which using it: Object subclass: #ABBAB uses: ABBA instanceVariableNames: '' classVariableNames: '' poolDictionaries: '' category: 'ABBA'. Object subclass: #ABBAC uses: ABBA instanceVariableNames: '' classVariableNames: '' poolDictionaries: '' category: 'ABBA'. now what i found interesting: (ABBAB methodDict at: #foo) == (ABBAC methodDict at: #foo) but as side effect, we got this one: (ABBAB methodDict at: #foo) methodClass ==> ABBAC which i find a bit disturbing :( I'm not sure if given issue could have a major impact somewhere... But i would just #clone the trait method before installing it.. Yes, it takes more space, but it makes each of such methods unrelated. And i strongly assume that these methods should be unrelated, and moreover, recompiled for each class separately, because global var in one class could be a class var in another one, so a trait method, like: foo ^ Bar will behave depending on class environment. -- Best regards, Igor Stasenko AKA sig.

Oct. 21, 2009

[Pharo-project] Issue 1282: a:=Array new: SmallInteger maxVal. returns methodContext versus memory allocation error (was: [Vm-dev] Array new: SmallInteger maxVal)

by Petr VÃ¡cha

FYI ----- PÅ®VODNÃ ZPRÃVA ----- Od: "David T. Lewis" <lewis(a)mail.msen.com> Komu: "Squeak Virtual Machine Development Discussion" <vm-dev(a)lists.squeakfoundation.org> PÅedmÄt: Re: [Vm-dev] Array new: SmallInteger maxVal Datum: 21.10.2009 - 4:39:21 On Tue, Oct 06, 2009 at 06:58:30PM -0400, David T. Lewis wrote: > > On Tue, Oct 06, 2009 at 10:05:02PM +0200, Nicolas Cellier wrote: > > > > >From http://code.google.com/p/pharo/issues/detail?id=1282 > > Is this known? > > Thanks, it's known now :) > > Also added to Mantis at http://bugs.squeak.org/view.php?id=7405. > > Petr: Yes this is definitely a cool bug. A fix for this is on Mantis 7405 (http://bugs.squeak.org/view.php?id=7405) The VMMaker updates are in SqueakSource in VMMaker-dtl.142. A separate patch is needed for platforms/unix/vm/sqUnixMemory.c (see the Mantis report, patch also sent to Ian). I have not tested Windows or Mac OS, but the basic scenario now is that the VM will limit the size of memory increase requests to 31 bit integer so support code can check for overflows. The requests from the VM are guaranteed (I hope) be valid 31 bit integers. Allocation requests of > 950 MB seem to be possible, although I do not have enough memory on my PC to verify that it actually works. Limiting allocation requests to more reasonable limits would be the responsibility of the image. Dave

Oct. 21, 2009

Re: [Pharo-project] HashTable vs Dictionary

by Andres Valloud

Martin, > You are, of course, correct. Well yes, thank you :), but it also helps when good, qualified people go over one's assertions to make sure they're not wrong. > -------------- > > First, the identity-based collections. > > The current IdentitySet and IdentityDictionary implementations do adjust > the hash function for large table sizes, with this code in #scanFor: > > finish > 4096 > ifTrue: [hash := anObject identityHash * (finish // 4096)] > ifFalse: [hash := anObject identityHash]. > start := (hash \\ finish) + 1. > > This makes IdentityDictionary pretty much as fast as it can be at most > sizes, but there's a problem here. Take a look at the HashTable > comparison graph: > > http://img247.echo.cx/img247/3702/chart8vv.png > > IdentityDictionary is fast at most sizes, but has problems right around > 4K of size. I'm going to assert (without testing, always dangerous in > performance work!) that this is because the hash spreading algorithm > above but always leaves an area at the end of the table array that never > gets any hash values mapped to it. This will be worst when the table > size is between 4K and 8K, when the multiplier is still 1. When the > number of objects in the dictionary gets high enough that the table > grows again, the hashes start being spread out and it gets fast again. > At first sight, it seems to me that this should be fixed along the lines of what you propose. > I'd suggest trying replacing the above code with something like this: > > hash := anObject identityHash * (finish // 4096 + 1) > start := (hash \\ finish) + 1. > > Not only better performing (I expect) but simpler. Possibly even > better-performing might be this: > > hash := anObject identityHash * <well-chosen constant> > start := (hash \\ finish) + 1. > > where the constant is large enough to get a spread across most of the > positive SmallInteger range, but not large enough to exceed it. Andres, > what's a good choice for the constant? Maybe a prime that is never close > to a prime used for a table size in these collections? > Actually, since Squeak/Pharo have hashMultiply, I'd guess that constant (1664525, IIRC) should suffice for the vast majority of cases (1664525 * 4095 > 1 billion, that should do). Hashed collection sizes (past the first trivial tiny sizes) should be chosen carefully. Knuth has some suggestions for how to select good prime sizes. In fact, 1664525 should be seen as one potential hashed collection size too (but never used as such). The hash book has all the details on this. > I'd suggest using a hash-spreading function on the equality-based > collections as well. Ideally, I'd do something along the lines of Object>>scaledIdentityHash ^self identityHash bitShift: 18 "I think, basically as much as possible without creating a large integer --- note that multiplying by a power of two has the effect of a permutation modulo a well chosen prime because gcd(2^k, wellChosenPrime) = 1 and so 2^k is inversible mod wellChosenPrime" implement Object>>hash ^self scaledIdentityHash "as opposed to identityHash" and then substitute sending scaledIdentityHash for identityHash in the identity based collections. This has several benefits. * All the scaling code in hashed collections, both identity and equality if they scale values, can be thrown away. * The index for an object becomes object hash "or scaledIdentityHash" \\ tableSize + 1 in all cases. That's so little work the whole method in which it is implemented can be inlined, removing another message send and making collections even more efficient. * Other senders of identityHash are not affected, particularly those that assume identityHash has a certain number of bits and so on. Finally, I am assuming that chaining means that each slot in the hash table has a pointer that says where the collision chain continues (or a node that points to the next node in the collision). It may be worthwhile to entertain using hash buckets, where the whole chain is in an array, particularly for identity collections if there's a primitive that scans for an object in an array. That structure is also useful to implement the symbol table (and all sorts of other tables, actually). As Martin says, mod special cases where you know you will have a lot of collisions, open addressing linear probing is the way to go. And, for special cases such as that of identityHash, it may be worthwhile considering comparing using == but implementing identityHash in terms of hash. After all, certainly if two objects are == they should have the same hash (and identityHash) values. Andres.

Oct. 21, 2009

Re: [Pharo-project] HashTable vs Dictionary

by Martin McClure

Andres Valloud wrote: > In general terms, open addressing with linear probing should tie or beat > chaining. For this to happen, the hash function used must be of high > quality. If chaining is beating open addressing with linear probing, > I'd strongly suspect that the hash function used is producing > significant collisions or unevenly distributed values for the data set > in question. You may want to take a look at the Hash Analysis Tool I > wrote for VW (it's in the public Store repository under a MIT license). > For a more in-depth treatment of these matters, you may also want to > look at the hash book I wrote (www.lulu.com/avSmalltalkBooks) and its > matching Smalltalk Solutions 2008 presentation > (http://video.google.com/videoplay?docid=-7510297003494499688&hl=en#) You are, of course, correct. I agree that the place to focus on is the hash functions being used. And I believe that there are some simple improvements that can be made. From a (very!) brief look, this HashTable implementation appears to be inspired by difficulties caused by having only 4096 identity hash values in Squeak/Pharo. If you have a large collection using identity hash you will, by definition, have lots of collisions. The *best* (and most difficult) solution is to increase the number of identity hash values that can be stored in the object header. Until that can be done, we adjust as best we can... -------------- First, the identity-based collections. The current IdentitySet and IdentityDictionary implementations do adjust the hash function for large table sizes, with this code in #scanFor: finish > 4096 ifTrue: [hash := anObject identityHash * (finish // 4096)] ifFalse: [hash := anObject identityHash]. start := (hash \\ finish) + 1. This makes IdentityDictionary pretty much as fast as it can be at most sizes, but there's a problem here. Take a look at the HashTable comparison graph: http://img247.echo.cx/img247/3702/chart8vv.png IdentityDictionary is fast at most sizes, but has problems right around 4K of size. I'm going to assert (without testing, always dangerous in performance work!) that this is because the hash spreading algorithm above but always leaves an area at the end of the table array that never gets any hash values mapped to it. This will be worst when the table size is between 4K and 8K, when the multiplier is still 1. When the number of objects in the dictionary gets high enough that the table grows again, the hashes start being spread out and it gets fast again. I'd suggest trying replacing the above code with something like this: hash := anObject identityHash * (finish // 4096 + 1) start := (hash \\ finish) + 1. Not only better performing (I expect) but simpler. Possibly even better-performing might be this: hash := anObject identityHash * <well-chosen constant> start := (hash \\ finish) + 1. where the constant is large enough to get a spread across most of the positive SmallInteger range, but not large enough to exceed it. Andres, what's a good choice for the constant? Maybe a prime that is never close to a prime used for a table size in these collections? --------------- As the graph shows, Dictionary has a real problem when grown above 4000 entries, and I would expect Set to have a similar problem. I assume this is with objects that do not define a well-spread hash function, such as objects that implement hash as identity hash. And this is quite a few objects. I'd suggest using a hash-spreading function on the equality-based collections as well. Something like that used for IdentitySet *could* work, but if you give that formula objects whose hashes *are* already well-spread across the entire SmallInteger range, on most entries you'd be creating short-lived large integers, and if you're looking for performance you don't want to do that. Using #hashMultiply would probably improve things quite a bit, though it might be possible to do a bit better than that. With changes along these lines, I agree with Andres that linear-probing collections should be able to equal or beat the performance of chained collections, and are a better choice for general-purpose collections. Regards, -Martin

Oct. 21, 2009

Re: [Pharo-project] Class and Metaclass explanation in PBE

by Mariano Martinez Peck

On Tue, Oct 20, 2009 at 10:23 PM, Igor Stasenko <siguctua(a)gmail.com> wrote: > 2009/10/21 Mariano Martinez Peck <marianopeck(a)gmail.com>: > > Hi folks. I was reading chapter 13 of PBE and there is something I don't > > understand. > > > > In page 283 it says: > > > > "Every metaclass is-a class, hence inherits from Class. Class in turn > > inherits from its superclasses, ClassDescription and Behavior." > > > > page 278, rule 8, it says: > > > > "Every metaclass inherits from Class and Behavior." > > > > > > However, if I open a class browser, I see that Metaclass inherits from > > ClassDescription, not Class. So, I don't understand :( > > > > Can anyone clarify me this? > > > > The topmost superclass of Metaclass is a ProtoObject class (as for any > other class). > You can see it yourself: > Metaclass superclass superclass superclass superclass > > now if you take a look, what is the class of the above object, you'll see: > > (Metaclass superclass superclass superclass superclass) class > -> ProtoObject class > > and now: > > (ProtoObject class) superclass => Class > > Thanks Igor. This was the part I was missing :) > so, lets roll things back.. > > ProtoObject class superclass => Class > > means that ProtoObject object is an instance of class, which inherits > from Class. > Or, since ProtoObject is class itself, then the 'ProtoObject class' > expression should return a metaclass, then you can see that > a most basic metaclass inherits from Class. > > and hence: "Every metaclass inherits from Class and Behavior." > > > Thanks > > > > Mariano > > > > > > _______________________________________________ > > Pharo-project mailing list > > Pharo-project(a)lists.gforge.inria.fr > > http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project > > > > > > -- > Best regards, > Igor Stasenko AKA sig. > > _______________________________________________ > Pharo-project mailing list > Pharo-project(a)lists.gforge.inria.fr > http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project >

Oct. 21, 2009

[Pharo-project] bug with "Extended Search" of low panel of new inspector

by Mariano Martinez Peck

Hi folks (Romain?) There is a bug with the NewInspector. To reproduce: 1) just inspect something. 2) now, in the inspector go to the lower panel and write something. 3) Select it, right button, and click on "Extended Search" I won't bring the extended search, but it will open again the context menu (as when you right click). Bug ticket: http://code.google.com/p/pharo/issues/detail?id=1350 BTW, can we please rename NewInspector to Inspector ??? Or at least the title of the windows. I think that names like "New Inspector" or "Shout Workspace" are difficult to understand for newcomers. So, I would change, at least, the windows title of them to "Inspector" and "Workspace"

Oct. 21, 2009

Re: [Pharo-project] Class and Metaclass explanation in PBE

by Igor Stasenko

2009/10/21 Mariano Martinez Peck <marianopeck(a)gmail.com>: > Hi folks. I was reading chapter 13 of PBE and there is something I don't > understand. > > In page 283 it says: > > "Every metaclass is-a class, hence inherits from Class. Class in turn > inherits from its superclasses, ClassDescription and Behavior." > > page 278, rule 8, it says: > > "Every metaclass inherits from Class and Behavior." > > > However, if I open a class browser, I see that Metaclass inherits from > ClassDescription, not Class. So, I don't understand :( > > Can anyone clarify me this? > The topmost superclass of Metaclass is a ProtoObject class (as for any other class). You can see it yourself: Metaclass superclass superclass superclass superclass now if you take a look, what is the class of the above object, you'll see: (Metaclass superclass superclass superclass superclass) class -> ProtoObject class and now: (ProtoObject class) superclass => Class so, lets roll things back.. ProtoObject class superclass => Class means that ProtoObject object is an instance of class, which inherits from Class. Or, since ProtoObject is class itself, then the 'ProtoObject class' expression should return a metaclass, then you can see that a most basic metaclass inherits from Class. and hence: "Every metaclass inherits from Class and Behavior." > Thanks > > Mariano > > > _______________________________________________ > Pharo-project mailing list > Pharo-project(a)lists.gforge.inria.fr > http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project > -- Best regards, Igor Stasenko AKA sig.

Oct. 21, 2009

Re: [Pharo-project] HashTable vs Dictionary

by Andres Valloud

In general terms, open addressing with linear probing should tie or beat chaining. For this to happen, the hash function used must be of high quality. If chaining is beating open addressing with linear probing, I'd strongly suspect that the hash function used is producing significant collisions or unevenly distributed values for the data set in question. You may want to take a look at the Hash Analysis Tool I wrote for VW (it's in the public Store repository under a MIT license). For a more in-depth treatment of these matters, you may also want to look at the hash book I wrote (www.lulu.com/avSmalltalkBooks) and its matching Smalltalk Solutions 2008 presentation (http://video.google.com/videoplay?docid=-7510297003494499688&hl=en#) Andres. Lukas Renggli wrote: > 2009/10/20 Laval Jannik <jannik.laval(a)gmail.com>: > >> Hi, >> Since some weeks, >> We use in our projects the project HashTable, available >> at http://www.squeaksource.com/ht.html >> It could be a good idea to integrate these collections to replace Dictionary >> and Set. >> > > I don't think that this is generally a good idea. It might be > beneficial in your situation, but certainly not for everybody in all > situations. I've been using the HashTable implementation in several > projects with great success. In other projects I've been using the > BTree package on SqueakSource that provides similar functionality > optimized for yet another context. These highly specialized data > structures should only be applied if they make sense in the given > context (and if you understand both, the cost and gain). I guess this > was exactly the reason why SkipList was removed from the Pharo image. > > Lukas > >

Oct. 21, 2009

[Pharo-project] Class and Metaclass explanation in PBE

by Mariano Martinez Peck

Hi folks. I was reading chapter 13 of PBE and there is something I don't understand. In page 283 it says: "Every metaclass is-a class, hence inherits from Class. Class in turn inherits from its superclasses, ClassDescription and Behavior." page 278, rule 8, it says: "Every metaclass inherits from Class and Behavior." However, if I open a class browser, I see that Metaclass inherits from ClassDescription, not Class. So, I don't understand :( Can anyone clarify me this? Thanks Mariano

Oct. 21, 2009

Re: [Pharo-project] Question about deepCopy,

by Schwab,Wilhelm K

I'm going to briefly be a wise-guy to a (well intentioned) purpose. You appear to be suggesting that we call #deepCopy something else, and then fix it. One might drag the fix into #deepCopy?? But years ago now, #deepCopy fell from grace, perhaps for good reason. What I recall seeing in its place was #postCopy that can be overriden to ensure a distinct copy; that seemed to be in contrast to #shallowCopy. This deserves some attention to ensure that we do the correct thing. Bill -----Original Message----- From: pharo-project-bounces(a)lists.gforge.inria.fr [mailto:pharo-project-bounces@lists.gforge.inria.fr] On Behalf Of arnaud Jean Baptiste Sent: Tuesday, October 20, 2009 10:07 AM To: Pharo Development Subject: [Pharo-project] Question about deepCopy, question: deepCopy have this behavior : - copy self. - then send deepCopy on all instance var. this behavior, make infinite loop when a object have instance variable which reference to himself or more longer cycle. Why don't replace deepCopy by veryDeepCopy, same behavior but copy each object only once (create collection and keep reference). performance issue ? _______________________________________________ Pharo-project mailing list Pharo-project(a)lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project

Oct. 20, 2009