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

[Pharo-project] issue 496: Morph>>heading

by Laval Jannik

Hi, Morph>>heading is from eToy. It is used to rotate a Morph. If we remove it, we remove the possibility to rotate a morph. What are your positions about this behavior ? Do we considere it as a system behavior or as an eToy thing which must be removed ? Cheers, --- Jannik Laval PhD Student - Rmod Team - INRIA Certified Project Management Associate (IPMA) http://www.jannik-laval.eu http://rmod.lille.inria.fr ---

Oct. 22, 2009

Re: [Pharo-project] Perfect hash [was: Re: HashTable vs Dictionary]

by Andres Valloud

Igor et al, > Let me simplify the goal of perfect hashing: > - suppose you having N unique integer numbers, without strictly > specified range (any number could lie in range 0..infinity). > - now we need to find a function such that, for each element 'x' in > the above finite set, following conditions met: > > 0 <= f(x) < k*N > > and for each pair of two different elements x , y in original set > f(x) <> f(y) > > and k < infinity > > As you can see , this function maps an arbitrary integer values > without specific range, to an > integer values in range [0..k*N], (k>=1). > Given that we need to deal with a limited number of elemens for each > particular set of numbers, such function can be found. > We just need to search for an optimal (minimal) k, which is < 2 and in > perfect case == 1. > > I thought I'd point out a subtle potential problem. Assume N = 1000, f(x_j) = j-1, and so k = 1 because 0 <= f(x_j) < N because 0 < j <= 1000. Now, store x_{7i} in a Set, for all i such that 1 <= 7i <= 1000. Clearly, f(x) is a perfect hash function as defined above. However, if the size of the table used by the set is a multiple of 7, performance will be terrible. By the way, you may want to check out the Hash Analysis Tool I wrote for VisualWorks. It's in the public Store repository (bundle name "Hash Analysis Tool", there's also an extensions bundle with more hash functions and data sets). My blog has a (somewhat passable excuse for a) manual here: http://blogten.blogspot.com/2008/02/hash-analysis-tool-manual.html. Andres.

Oct. 22, 2009

[Pharo-project] issue 429: collapseAll

by Laval Jannik

Hi all, In issue 429, when we do a "collapse all windows" PasteUpMorph>>collapseAll is invoked. This method collapse non window elements. But, when we do an "expand all windows", only windows are expanded. So my question is: Do we want to collapse all non window elements ? If yes, we must to expand them in "expand all windows" If no, I remove this behavior. Cheers, --- Jannik Laval PhD Student - Rmod Team - INRIA Certified Project Management Associate (IPMA) http://www.jannik-laval.eu http://rmod.lille.inria.fr ---

Oct. 22, 2009

Re: [Pharo-project] [squeak-dev] Re: Issue with traits

by Marcus Denker

On 21.10.2009, at 22:28, Ken.Dickey wrote: > Why not share the code? Just use a "cell" to hold the class and have > methodClass accessor do the indirection. > But based on which info should this indirection be made? The idea with a simple backpointer was done because it's already there in case of super-sends. So you would need to do something special there again (the last literal *has to be* a class for those methds). > If you have a bit in the method header, the VM could use it as a 0/1 > index > into the code to call to do (or not do) the extra indirection. If there is something that is a scarce resource, than it's bits in the method header. And I don't get it: there is one header per object, not one per reference. Thus the bit could not be diffrerent per *use* of the compiledMethod. > Just think of > the a trait method as a closure which is parameterized on the class. > > Am I missing something deep here? > You overlook complexity ;-) > -KenD > >> Message: 7 >> Date: Wed, 21 Oct 2009 09:41:08 +0200 >> From: Adrian Lienhard <adi(a)netstyle.ch> >> Subject: Re: [Pharo-project] [squeak-dev] Re: Issue with traits >> To: The general-purpose Squeak developers list >> <squeak-dev(a)lists.squeakfoundation.org>, Pharo >> Development >> <pharo-project(a)lists.gforge.inria.fr> >> Message-ID: <3C7E5C51-21A8-483A-81A0-40854430A43B(a)netstyle.ch> >> Content-Type: text/plain; charset=US-ASCII; format=flowed; delsp=yes >> >> I've fixed this issue in Pharo a couple of months ago. >> CompiledMethods >> are not shared anymore, so methodClass returns the expected class. At >> the time I implemented traits (2004?), there were no method >> properties >> and hence sharing compiled methods worked -- of course except for >> super sends in which case the method was always recompiled (so the >> answer to Andreas' question below is b)). >> >> Cheers, >> Adrian > > _______________________________________________ > Pharo-project mailing list > Pharo-project(a)lists.gforge.inria.fr > http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project

Oct. 22, 2009

Re: [Pharo-project] Perfect hash [was: Re: HashTable vs Dictionary]

by Martin McClure

Igor Stasenko wrote: > 2009/10/22 Martin McClure <martin(a)hand2mouse.com>: >> Igor Stasenko wrote: >>> Err, your thoughts went in wrong direction. >>> Let me simplify the goal of perfect hashing: >>> - suppose you having N unique integer numbers, without strictly >>> specified range (any number could lie in range 0..infinity). >>> - now we need to find a function such that, for each element 'x' in >>> the above finite set, following conditions met: >>> >>> 0 <= f(x) < k*N >>> >>> and for each pair of two different elements x , y in original set >>> f(x) <> f(y) >>> >>> and k < infinity >>> >>> As you can see , this function maps an arbitrary integer values >>> without specific range, to an >>> integer values in range [0..k*N], (k>=1). >>> Given that we need to deal with a limited number of elemens for each >>> particular set of numbers, such function can be found. >>> We just need to search for an optimal (minimal) k, which is < 2 and in >>> perfect case == 1. >>> >> Hi Igor, >> >> Yes, you have defined a perfect hash function nicely, and that is the >> definition I was assuming in my previous comments. >> >> And even if you find a perfect hash function for a given set of objects, >> the situations in which the resulting collection is useful are quite >> limited, which was the main idea behind my comments. >> >> Unless I've missed something? >> > Limited, why? > > As i said, suppose you have a collection which is modified rarely. > As an example: MethodDictionary, Smalltalk > as well as any collections which you using in your code as an > immutable storage, once populated. > > This can be done easily with few modifications to current classes. > Consider: > > Set>>scanFor: anObject > > - start := (anObject hash \\ finish) + 1. > + start := hashFunction ifNil: [ (anObject hash \\ finish) + 1 ] > ifNotNil: [ hashFunction value: anObject hash on: array ]. > > > now you can tell set to use custom hash function, by using a new method: > > Set>>rehashUsing: newHashFunction > > hashFunction := newHashFunction. > hashFunction ifNil: [ self rehashUsingOldWay ] ifNotNil: [ array := > hashFunction rehash: array filler: nil ]. > > > oh, and btw, such modifications don't assume what hash function will > be used , so you can forget about perfect hashing, if you don't like > it :) > Mainly, what it does, just replacing a hardcoded hash function , which > is '(anObject hash \\ finish) + 1' by one, provided by you. > Ah, thanks. That does indeed make more sense than what I originally thought you meant, sorry for the confusion. Pluggable hashes could be useful, though I've been quite happy with using subclasses for that, which keeps the code of the general collection class cleaner. However, this approach does mean that for perfect hash (not just pluggable hash function) you have to find an actual function that is fast and compact that is a perfect hash, or you've lost the slight advantage that perfect hashes have over good but imperfect hashes. And I doubt this can be done for something like a MethodDictionary. Also, you'd have to add code to control the size of the hash table to be the right size for the perfect hash function. Regards, -Martin

Oct. 22, 2009

Re: [Pharo-project] Perfect hash [was: Re: HashTable vs Dictionary]

by Igor Stasenko

2009/10/22 Martin McClure <martin(a)hand2mouse.com>: > Igor Stasenko wrote: >> >> Err, your thoughts went in wrong direction. >> Let me simplify the goal of perfect hashing: >> - suppose you having N unique integer numbers, without strictly >> specified range (any number could lie in range 0..infinity). >> - now we need to find a function such that, for each element 'x' in >> the above finite set, following conditions met: >> >> 0 <= f(x) < k*N >> >> and for each pair of two different elements x , y in original set >> Â f(x) <> f(y) >> >> and k < infinity >> >> As you can see , this function maps an arbitrary integer values >> without specific range, to an >> integer values in range [0..k*N], (k>=1). >> Given that we need to deal with a limited number of elemens for each >> particular set of numbers, such function can be found. >> We just need to search for an optimal (minimal) k, which is < 2 and in >> perfect case == 1. >> > > Hi Igor, > > Yes, you have defined a perfect hash function nicely, and that is the > definition I was assuming in my previous comments. > > And even if you find a perfect hash function for a given set of objects, > Â the situations in which the resulting collection is useful are quite > limited, which was the main idea behind my comments. > > Unless I've missed something? > Limited, why? As i said, suppose you have a collection which is modified rarely. As an example: MethodDictionary, Smalltalk as well as any collections which you using in your code as an immutable storage, once populated. This can be done easily with few modifications to current classes. Consider: Set>>scanFor: anObject - start := (anObject hash \\ finish) + 1. + start := hashFunction ifNil: [ (anObject hash \\ finish) + 1 ] ifNotNil: [ hashFunction value: anObject hash on: array ]. now you can tell set to use custom hash function, by using a new method: Set>>rehashUsing: newHashFunction hashFunction := newHashFunction. hashFunction ifNil: [ self rehashUsingOldWay ] ifNotNil: [ array := hashFunction rehash: array filler: nil ]. oh, and btw, such modifications don't assume what hash function will be used , so you can forget about perfect hashing, if you don't like it :) Mainly, what it does, just replacing a hardcoded hash function , which is '(anObject hash \\ finish) + 1' by one, provided by you. -- Best regards, Igor Stasenko AKA sig.

Oct. 22, 2009

Re: [Pharo-project] Perfect hash [was: Re: HashTable vs Dictionary]

by John M McIntosh

*cough* I can remember sitting at a client (rather late at night) under intense pressure looking at the performance curve that when straight up, because well some dictionary when over N elements and the hash target then resolved to a *very* long chain on an insert. Sadly mmm 12 years later we not been able to provide a decent hash logic for Smalltalk (aka Pharo) that removes the hassle of having to consider some specialized form of dictionary if the experienced programmer in the room twigs to the fact why that could be the problem... On 2009-10-21, at 7:54 PM, Martin McClure wrote: > Igor Stasenko wrote: >> >> Err, your thoughts went in wrong direction. >> Let me simplify the goal of perfect hashing: >> - suppose you having N unique integer numbers, without strictly >> specified range (any number could lie in range 0..infinity). >> - now we need to find a function such that, for each element 'x' in >> the above finite set, following conditions met: >> >> 0 <= f(x) < k*N >> >> and for each pair of two different elements x , y in original set >> f(x) <> f(y) >> >> and k < infinity >> >> As you can see , this function maps an arbitrary integer values >> without specific range, to an >> integer values in range [0..k*N], (k>=1). >> Given that we need to deal with a limited number of elemens for each >> particular set of numbers, such function can be found. >> We just need to search for an optimal (minimal) k, which is < 2 and >> in >> perfect case == 1. >> > > Hi Igor, > > Yes, you have defined a perfect hash function nicely, and that is the > definition I was assuming in my previous comments. > > And even if you find a perfect hash function for a given set of > objects, > the situations in which the resulting collection is useful are quite > limited, which was the main idea behind my comments. > > Unless I've missed something? > > Regards, > > -Martin > > _______________________________________________ > Pharo-project mailing list > Pharo-project(a)lists.gforge.inria.fr > http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project -- = = = ======================================================================== John M. McIntosh <johnmci(a)smalltalkconsulting.com> Twitter: squeaker68882 Corporate Smalltalk Consulting Ltd. http://www.smalltalkconsulting.com = = = ========================================================================

Oct. 22, 2009

Re: [Pharo-project] Perfect hash [was: Re: HashTable vs Dictionary]

by Martin McClure

Igor Stasenko wrote: > > Err, your thoughts went in wrong direction. > Let me simplify the goal of perfect hashing: > - suppose you having N unique integer numbers, without strictly > specified range (any number could lie in range 0..infinity). > - now we need to find a function such that, for each element 'x' in > the above finite set, following conditions met: > > 0 <= f(x) < k*N > > and for each pair of two different elements x , y in original set > f(x) <> f(y) > > and k < infinity > > As you can see , this function maps an arbitrary integer values > without specific range, to an > integer values in range [0..k*N], (k>=1). > Given that we need to deal with a limited number of elemens for each > particular set of numbers, such function can be found. > We just need to search for an optimal (minimal) k, which is < 2 and in > perfect case == 1. > Hi Igor, Yes, you have defined a perfect hash function nicely, and that is the definition I was assuming in my previous comments. And even if you find a perfect hash function for a given set of objects, the situations in which the resulting collection is useful are quite limited, which was the main idea behind my comments. Unless I've missed something? Regards, -Martin

Oct. 22, 2009

Re: [Pharo-project] Perfect hash [was: Re: HashTable vs Dictionary]

by Igor Stasenko

2009/10/22 Martin McClure <martin(a)hand2mouse.com>: > Igor Stasenko wrote: >> Well, you can always attack the problem from different side - create a >> Set and Dictionary >> which using a perfect hash algorythms. >> As you may know, a perfect hash is a function which producing unique >> values for a limited set of elements. >> So, that in sets hashed using perfect hash function, no collisions >> possible, and hence the access time to any element is O(1). >> >> The drawback of such approach, that finding a perfect hash function >> for a set of elements is time consuming (best ones, AFAIK, consuming >> O(k*n) time, where n is number of elements), so >> you would never want to use a perfect hashing for collections which >> tend to grow or shrink often. >> >> But for collections, which populated once, and then used for read-only >> access this is worth doing. > > > Hi Igor, > > I'm afraid I don't see the usefulness. What kind of read accesses will > you be doing on this hashed collection? I can think of only two kinds of > access that make sense: The 'is this object in this collection' > question, and iterating over the collection to do some operation on all > objects therein. > > For iteration, you might as well use an Array, and forget hashing > altogether. > > For the 'is this object in this collection' question, you might more > straightforwardly replace the perfectHash instvar with a Boolean > isInTheCollection instvar. Saves space and time; you don't need the > collection at all. > > Perfect hashing sounds cool, but is of quite limited usefulness. I can > see it being useful when *all* of the following are true: > > * There are a relatively small number of possible objects in the > universe that is being hashed. Then each object can be given a unique > (thus "perfect") hash value. > > * There are multiple collections that can contain exactly this universe > of objects, and no others. > > * Membership in each collection by a given object is not easily > predictable, or might vary over time. > >> And its quite easy to modify current classes to use a perfect hash: >> Â just add a perfectHash ivar to it, and if its not nil , then use it >> to find an index of item. >> And if perfectHash is nil, then we just use the current implementation. >> >> And of course, you need to implement a perfect hash search, which >> standing aside :) >> But then you could just do: >> >> set := something collect: [... ] asSet rehashWithPerfectHash. > > I don't think you can easily use class Set, or any existing > general-purpose collection class, to get a perfect hash. Existing > Smalltalk collection classes combine two functions sequentially to form > the hash function: The first function is a property of the object being > stored (typically implemented as #hash or #identityHash), and the second > function is a property of the collection itself (typically mod with the > current prime table size). > > If your object knows its perfect hash with respect to a given > collection, you don't want that collection adding anything to that > function. In particular, you don't want the collection to take a modulo, > because then your hash function is no longer perfect and collisions > become quite likely again, defeating the entire purpose. > > In general, you'd set it up so that the perfect hash value is exactly > the table index reserved for that object in the collection. Then that > slot either contains a reference to that object, or nil. In any > perfect-hash situation, you need a table the same size as your universe > in every collection. This means that the universe cannot change size > easily, and once it gets very large the space costs are no longer worth > the time savings. > Err, your thoughts went in wrong direction. Let me simplify the goal of perfect hashing: - suppose you having N unique integer numbers, without strictly specified range (any number could lie in range 0..infinity). - now we need to find a function such that, for each element 'x' in the above finite set, following conditions met: 0 <= f(x) < k*N and for each pair of two different elements x , y in original set f(x) <> f(y) and k < infinity As you can see , this function maps an arbitrary integer values without specific range, to an integer values in range [0..k*N], (k>=1). Given that we need to deal with a limited number of elemens for each particular set of numbers, such function can be found. We just need to search for an optimal (minimal) k, which is < 2 and in perfect case == 1. > Regards, > > -Martin > > _______________________________________________ > 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. 22, 2009

Re: [Pharo-project] Perfect hash [was: Re: HashTable vs Dictionary]

by Martin McClure

Igor Stasenko wrote: > Well, you can always attack the problem from different side - create a > Set and Dictionary > which using a perfect hash algorythms. > As you may know, a perfect hash is a function which producing unique > values for a limited set of elements. > So, that in sets hashed using perfect hash function, no collisions > possible, and hence the access time to any element is O(1). > > The drawback of such approach, that finding a perfect hash function > for a set of elements is time consuming (best ones, AFAIK, consuming > O(k*n) time, where n is number of elements), so > you would never want to use a perfect hashing for collections which > tend to grow or shrink often. > > But for collections, which populated once, and then used for read-only > access this is worth doing. Hi Igor, I'm afraid I don't see the usefulness. What kind of read accesses will you be doing on this hashed collection? I can think of only two kinds of access that make sense: The 'is this object in this collection' question, and iterating over the collection to do some operation on all objects therein. For iteration, you might as well use an Array, and forget hashing altogether. For the 'is this object in this collection' question, you might more straightforwardly replace the perfectHash instvar with a Boolean isInTheCollection instvar. Saves space and time; you don't need the collection at all. Perfect hashing sounds cool, but is of quite limited usefulness. I can see it being useful when *all* of the following are true: * There are a relatively small number of possible objects in the universe that is being hashed. Then each object can be given a unique (thus "perfect") hash value. * There are multiple collections that can contain exactly this universe of objects, and no others. * Membership in each collection by a given object is not easily predictable, or might vary over time. > And its quite easy to modify current classes to use a perfect hash: > just add a perfectHash ivar to it, and if its not nil , then use it > to find an index of item. > And if perfectHash is nil, then we just use the current implementation. > > And of course, you need to implement a perfect hash search, which > standing aside :) > But then you could just do: > > set := something collect: [... ] asSet rehashWithPerfectHash. I don't think you can easily use class Set, or any existing general-purpose collection class, to get a perfect hash. Existing Smalltalk collection classes combine two functions sequentially to form the hash function: The first function is a property of the object being stored (typically implemented as #hash or #identityHash), and the second function is a property of the collection itself (typically mod with the current prime table size). If your object knows its perfect hash with respect to a given collection, you don't want that collection adding anything to that function. In particular, you don't want the collection to take a modulo, because then your hash function is no longer perfect and collisions become quite likely again, defeating the entire purpose. In general, you'd set it up so that the perfect hash value is exactly the table index reserved for that object in the collection. Then that slot either contains a reference to that object, or nil. In any perfect-hash situation, you need a table the same size as your universe in every collection. This means that the universe cannot change size easily, and once it gets very large the space costs are no longer worth the time savings. Regards, -Martin

Oct. 22, 2009