January 2016 - Pharo-dev - lists.pharo.org

Re: [Pharo-dev] Problem with gitfiletree numeration

by Mariano Martinez Peck

On Wed, Jan 13, 2016 at 9:33 PM, Alexandre Bergel <alexandre.bergel(a)me.com> wrote: > Hi Mariano > > Just wondering, are you using Spur? If yes, how come that you can use git? > Osprocess does not work with Spur > > First, I am changing GitFileTree to use my soon-to-be-released OSSubprocess :) Second, OSProcess SHOULD be fixed with the very last VM from CI: wget -O- get.pharo.org/vmLatest50 | bash Let me know if it worked. Cheers, > Alexandre > > Le 13 janv. 2016 Ã 09:12, Mariano Martinez Peck <marianopeck(a)gmail.com> a > Ã©crit : > > Hi guys, > > I wanted to know how you manage this situation. > I had my already existing project in shub repo. Last version > was OSSubprocess-MarianoMartinezPeck.43. I then created a github repo, > cloned it, and then with gitfiletree I commit for the first time. > > The problem is that the commit I did with GitFileTree received this MC > version: OSSubprocess-MarianoMartinezPeck.1. Normally I would not care. But > in this case I do care because every in a while I would like to > move/publish some versions from github to shub. And > OSSubprocess-MarianoMartinezPeck.1 has 2 problems: > > 1) It has an older version number but newer contents > 2) It's number is not unique. So if I copy versions created from github to > shub, they would override those versiones created in shub (like the very > old OSSubprocess-MarianoMartinezPeck.1 from shub) ?? > > How do you normally solve this? > > Thanks! > > -- > Mariano > http://marianopeck.wordpress.com > > -- Mariano http://marianopeck.wordpress.com

Jan. 14, 2016

Re: [Pharo-dev] Problem with gitfiletree numeration

by Alexandre Bergel

Hi Mariano Just wondering, are you using Spur? If yes, how come that you can use git? Osprocess does not work with Spur Alexandre > Le 13 janv. 2016 Ã 09:12, Mariano Martinez Peck <marianopeck(a)gmail.com> a Ã©crit : > > Hi guys, > > I wanted to know how you manage this situation. > I had my already existing project in shub repo. Last version was OSSubprocess-MarianoMartinezPeck.43. I then created a github repo, cloned it, and then with gitfiletree I commit for the first time. > > The problem is that the commit I did with GitFileTree received this MC version: OSSubprocess-MarianoMartinezPeck.1. Normally I would not care. But in this case I do care because every in a while I would like to move/publish some versions from github to shub. And OSSubprocess-MarianoMartinezPeck.1 has 2 problems: > > 1) It has an older version number but newer contents > 2) It's number is not unique. So if I copy versions created from github to shub, they would override those versiones created in shub (like the very old OSSubprocess-MarianoMartinezPeck.1 from shub) ?? > > How do you normally solve this? > > Thanks! > > -- > Mariano > http://marianopeck.wordpress.com

Jan. 14, 2016

Re: [Pharo-dev] Code reviews

by phil＠highoctane.be

I am currently in a project where we use Phabricator. Interesting tool for sure but also a huge PITA as the flow isn't streamlined. Phil On Wed, Jan 13, 2016 at 7:26 PM, David Allouche <david(a)allouche.net> wrote: > > > On 13 Jan 2016, at 18:37, Ben Coman <btc(a)openinworld.com> wrote: > > > > On Thu, Jan 14, 2016 at 12:22 AM, David Allouche <david(a)allouche.net> > wrote: > >> > >> By the way, how do you guys do code reviews for code integrated into the > >> core? > > > > Its fairly informal. Once a Slice has been submitted to the > > Pharo5Inbox the associated Issue on Fogbugz is <Resolved> to "Fix > > review Needed" - people review it out and comment. Unfortunately with > > limited resources, sometime resolved issues can languish if reviewer > > don't feel its within their expertise, and often it falls the to small > > group of the core-devs from Inria. As Pharo grows more popular we > > may need some improved processes to reduce load on core-devs. > > I believe that is an area that needs improving. But probably not right now. > > > I'd be > > interested in what you've seen work in other environments. > > Unfortunately, I do not have a lot of direct and relevant experience > there. We did code reviews at Canonical, but I would never apply the kind > of process we used there in a community project. > > I do believe it is essential that the path from "someone submits code" and > "send code review" be as frictionless as possible. Code reviews are hard > and time consuming. Any time spent not actually reading and commenting code > is a put off. > > Concretely, that means I think a good, interactive, actively maintained, > web-based code review tool is essential. I heard good things about github. > But since people in this community seem to have a strong bias towards doing > everything in Pharo, that might not be such a good idea... > > In any case, I think it should be easy to review code without loading the > change in the image. > > > > > Have you seen these... > > http://pharo.org/contribute-propose-fix > > I have seen it. But I did not feel that was relevant to me: I was not yet > familiar with any of tools mentioned there, nor was I familiar with the > policies surrounding code contributions. > > > https://pharo.fogbugz.com/?W68 > > I had seen it too, when exploring the issue tracker. And similarly, I felt > it was not yet relevant to me. So I quickly forgot about it :-) > > I will be sure to refer to those documents as my involvement and > confidence increase. > > Regards. >

Jan. 13, 2016

Re: [Pharo-dev] Bad layoutFrame>>#hash

by David Allouche

> On 13 Jan 2016, at 20:32, stepharo <stepharo(a)free.fr> wrote: > > Hi david > > I would like to turn your post into a chapter for a forthcoming book so that people can read and get the idea. Yes I would be glad :-) Please just remember to credit the author. Is there a recommended license for Pharo documentation? If not, I am happy to release that text under the MIT License. I would also like to review your derived work. But that is not a requirement. > I did not think about the same object. Is it ok for you? > > Stef > > PS: May be this was obviosu for you that we should all get this out of your previous mail but it was not my case > and not after 8 hours on intense work. Sorry, I do not understand what you are saying here. I do not want to read between the lines, because I would probably misunderstand your intention. Regards.

Jan. 13, 2016

Re: [Pharo-dev] Bad layoutFrame>>#hash

by Nicolas Cellier

2016-01-13 20:34 GMT+01:00 stepharo <stepharo(a)free.fr>: > Nicolas > > two questions: > - should we integrate your float changes in Pharo? > - I would like to get a chapter explaining the points raised by david, > would you like to review it? > > Stef > > 1) yes, that's low hanging fruits if you have a good soul to review it. while at reviewing the other hashes... 2) maybe Le 13/1/16 19:31, Nicolas Cellier a Ã©crit : > > > > 2016-01-13 17:22 GMT+01:00 David Allouche <david(a)allouche.net>: > >> >> On 12 Jan 2016, at 20:59, stepharo <stepharo(a)free.fr> wrote: >> >> Hi david >> >> I rad the wikipedia page you mention and this looks a bit obvious to me. >> I knew this. >> now it does not really help fixing the problem you mention. >> >> Stef >> >> >> Since you asked for itâ¦ >> >> The #hash method is used in Pharo to separate objects in bucket-based >> data structures. >> >> It must have one required property which is required data integrity: >> >> >> - A. Objects that are equal according to #= *must* have equal hashes. >> >> >> It should have two desirable properties that are required to support the >> algorithmic assumptions of bucket-based data structures: >> >> >> - B. Objects that are *not* equal *should* have different hashes. >> Ideally, the probability of hash collision should by 1/N where N is the >> size of hash value space. >> - C. The hash values should spread as much as possible over their >> value space. For example: ProtoObject>>#identityHash. >> >> >> How these two desirable properties can be implemented depend on the >> actual distribution of the value used to compute the hash. >> >> An object can safely use XOR hashing if its instance variables are all >> different objects that already provide a hash method with these two >> properties. For example, an object whose behaviour is defined by several of >> singleton delegates of different classes that do not override Object>>#hash. >> >> But if the instance variables are not guaranteed to have those >> properties, it is necessary to more thoroughly "mix the bits". For example: >> SequenceableCollection>>#hash. >> >> hash >> | hash | >> >> hash := self species hash. >> 1 to: self size do: [:i | hash := (hash + (self at: i) hash) >> hashMultiply]. >> ^hash >> >> The mixing of the bits is done by the combination of addition and >> hashMultiply. The value of "species hash" does not need to be processed by >> hashMultiply, because it is probably computed by ProtoObject>>identityHash, >> and that already provides C. >> >> LayoutFrame is a particularly good example of a data structure that >> should *not* use XOR hashing. Its instance variables provide none of the >> required properties: SmallInteger>>#hash is just ^self. In addition, common >> LayoutFrame instances tend to use pairs of identical values in their >> instance variables. Like 0@0 corner: 1@1, or Margin fromNumber: 10. >> >> A good hash function for LayoutFrame needs to: >> >> >> 1. Get hashes for each instance variable that provides A and B. >> 2. Combine them in a way that is order-sensitive (to maintain B) and >> that does some extra mixing (to provide C). >> >> >> Now, we can assume that common values for the instance variables will be >> instances of SmallInteger, Float, or Fraction. >> >> By the way, you can see in Fraction>>#hash, that a comment mentions the >> assumption that the fraction is already reduced, that is what makes it >> acceptable to use bitXor. >> >> The hash of SmallInteger does provide A and B, but not C. The hash of >> Float is harder to understand, but tests show that it provide distinct >> values for 0.5, 0.25 and 0.125. So it hopefully provides B for the range of >> values of interest to LayoutFrame. >> >> > Note that Squeak has reduced the number of collisions for floats by not > erasing the most significant bits of each word. > I've tested the squeak implementation with Andres Valloud tool in VW, it > does not perform so bad for the sets I tested in term of collisions... > > Float>>hash > "Hash is reimplemented because = is implemented. Both words of the > float are used. (The bitShift:'s ensure that the intermediate results do > not become a large integer.) Care is taken to answer same hash as an equal > Integer." > > (self isFinite and: [self fractionPart = 0.0]) ifTrue: [^self > truncated hash]. > ^ ((self basicAt: 1) bitShift: -4) + > ((self basicAt: 2) bitShift: -4) > > I also changed Fraction to use a hashMultiply and made a more explicit > isAnExactFloat test. > > Fraction>>hash > "Hash is reimplemented because = is implemented." > > "Care is taken that a Fraction equal to a Float also has an equal hash" > self isAnExactFloat ifTrue: [^self asExactFloat hash]. > > "Else, I cannot be exactly equal to a Float, use own hash algorithm." > ^numerator hash hashMultiply bitXor: denominator hash > > Fraction>>isAnExactFloat > "Answer true if this Fraction can be converted exactly to a Float" > ^ denominator isPowerOfTwo > and: ["I have a reasonable significand: not too big" > numerator highBitOfMagnitude <= Float precision > and: ["I have a reasonable exponent: not too small" > Float emin + denominator highBitOfMagnitude <= Float > precision]] > > Fraction>>asExactFloat > "When we know that this Fraction is an exact Float, this conversion is > much faster than asFloat." > > ^numerator asFloat timesTwoPower: 1 - denominator highBit > > Not that Fraction should allways be reduced (this is an invariant of the > class, I hope well defined in class comment). > > Integer hash is not that good because the risk of occupying consecutive > buckets is high... I wonder if returning ^self hashMultiply would not > arrange things here and reduce the requirements for spreading hashMultiply > everywhere else? > > Nicolas > > Another class that has similar hashing constraints to LayoutFrame is >> Point. Its hash method is: >> >> hash >> "Hash is reimplemented because = is implemented." >> >> ^(x hash hashMultiply + y hash) hashMultiply >> >> It does not include species in the computation, which is less than ideal >> because it favours collisions with objects of different species that have a >> similar content and a the same #hash algorithm. >> >> Finally, it is probably not necessary or useful to use the accessors to >> get to the instance variables. >> >> So a good implementation would be this (untested, there might be a typo >> or two) >> >> hash >> | hash | >> hash := self species hash >> hash := (hash + leftFraction hash) hashMultiply >> hash := (hash + leftOffset hash) hashMultiply >> hash := (hash + topFraction hash) hashMultiply >> hash := (hash + topOffset hash) hashMultiply >> hash := (hash + rightFraction hash) hashMultiply >> hash := (hash + rightOffset hash) hashMultiply >> hash := (hash + bottomFraction hash) hashMultiply >> hash := (hash + bottomOffset hash) hashMultiply >> ^ hash >> >> I am sure you could have figured that by yourself, by thinking about how >> hash values are used and by looking at the code of kernel classes, instead >> of getting offended and turning all defensive. >> >> I hope we can both learn from this episode. I do not enjoy antagonising >> people, but I will not write lengthy messages like this one every time >> someone questions my thinking. >> >> Have a nice day. >> >> Le 11/1/16 10:09, David Allouche a Ã©crit : >> >> Since it's not obvious why xor-ing is a bad way to produce hash, here is >> a link that gives some background >> >> https://en.wikipedia.org/wiki/Hash_function#Uniformity >> >> On 11 Jan 2016, at 10:01, David Allouche <david(a)allouche.net> wrote: >> >> I happened to look at the new code for LayoutFrame>>#hash >> >> hash >> ^self species hash bitXor: >> (self leftFraction bitXor: >> (self leftOffset bitXor: >> (self topFraction bitXor: >> (self topOffset bitXor: >> (self rightFraction bitXor: >> (self rightOffset bitXor: >> (self bottomFraction bitXor: >> self bottomOffset))))))) >> >> This is a terrible, terrible way to compute a hash. >> >> 0 xor 0 = 1 xor 1 = 2 xor 2 = etc. >> >> NEVER compute hashes with xor, that's wrong, and it causes horrible, hard >> to debug, performance bugs down the road. >> >> SequenceableCollection>>#hash looks more like a correct way of doing it. >> I do not know what is the correct, efficient way to reuse this logic >> in LayoutFrame>>#hash. >> >> By the way, how do you guys do code reviews for code integrated into the >> core? >> >> >> >> >> >> >> > >

Jan. 13, 2016

Re: [Pharo-dev] Bad layoutFrame>>#hash

by Nicolas Cellier

2016-01-13 19:55 GMT+01:00 David Allouche <david(a)allouche.net>: > > On 13 Jan 2016, at 19:31, Nicolas Cellier < > nicolas.cellier.aka.nice(a)gmail.com> wrote: > > Note that Squeak has reduced the number of collisions for floats by not > erasing the most significant bits of each word. > I've tested the squeak implementation with Andres Valloud tool in VW, it > does not perform so bad for the sets I tested in term of collisions... > > Float>>hash > "Hash is reimplemented because = is implemented. Both words of the > float are used. (The bitShift:'s ensure that the intermediate results do > not become a large integer.) Care is taken to answer same hash as an equal > Integer." > > (self isFinite and: [self fractionPart = 0.0]) ifTrue: [^self > truncated hash]. > ^ ((self basicAt: 1) bitShift: -4) + > ((self basicAt: 2) bitShift: -4) > > I also changed Fraction to use a hashMultiply and made a more explicit > isAnExactFloat test. > > Fraction>>hash > "Hash is reimplemented because = is implemented." > > "Care is taken that a Fraction equal to a Float also has an equal hash" > self isAnExactFloat ifTrue: [^self asExactFloat hash]. > > "Else, I cannot be exactly equal to a Float, use own hash algorithm." > ^numerator hash hashMultiply bitXor: denominator hash > > Fraction>>isAnExactFloat > "Answer true if this Fraction can be converted exactly to a Float" > ^ denominator isPowerOfTwo > and: ["I have a reasonable significand: not too big" > numerator highBitOfMagnitude <= Float precision > and: ["I have a reasonable exponent: not too small" > Float emin + denominator highBitOfMagnitude <= Float > precision]] > > Fraction>>asExactFloat > "When we know that this Fraction is an exact Float, this conversion is > much faster than asFloat." > > ^numerator asFloat timesTwoPower: 1 - denominator highBit > > Not that Fraction should allways be reduced (this is an invariant of the > class, I hope well defined in class comment). > > Integer hash is not that good because the risk of occupying consecutive > buckets is high... I wonder if returning ^self hashMultiply would not > arrange things here and reduce the requirements for spreading hashMultiply > everywhere else? > > > The risk does not really lie in occupying consecutive buckets. The risk is > rather that integers used as keys could have a pattern that cause bucket > collisions. For example, if all key are multiple of 100, and the bucket > count is 2, 4, 5, 10, 20, 25 or 50. > > It would make more sense to solve this problem by using multiplyHash in > the bucket data structure classes, instead of having to pay this > computation cost in SmallInteger. > > Ah yes, I thought the same. > Also, using it in SmallInteger would not dispense from using it in the > #hash method of classes that use SmallInteger, because it matters that each > component of the hash is processed a different number of times by > multiplyHash. > > Agree again, bad suggestion from my side, because using + or bitXor: without breaking symmetry with hashMultiply would lead to bad distribution of hashes... Consider I posted too fast :) BTW a 64 bits spur could have a larger hash pattern (small integers are 61 bits wide sign included, and identityHash is longer too, so there's no reason to stick to 28 bits).

Jan. 13, 2016

Re: [Pharo-dev] How to get launcher launching Spur images?

by Damien Cassou

On January 13, 2016 8:27:10 PM GMT+01:00, "Esteban A. Maringolo" <emaringolo(a)gmail.com> wrote: >Is the Ubuntu PPA updated automatically by the CI? No. Markus, on CC, is responsible for that. -- Damien Cassou http://damiencassou.seasidehosting.st "Success is the ability to go from one failure to another without losing enthusiasm." --Winston Churchill

Jan. 13, 2016

Re: [Pharo-dev] Bad layoutFrame>>#hash

by stepharo

Nicolas two questions: - should we integrate your float changes in Pharo? - I would like to get a chapter explaining the points raised by david, would you like to review it? Stef Le 13/1/16 19:31, Nicolas Cellier a Ã©crit : > > > 2016-01-13 17:22 GMT+01:00 David Allouche <david(a)allouche.net > <mailto:david@allouche.net>>: > > >> On 12 Jan 2016, at 20:59, stepharo <stepharo(a)free.fr >> <mailto:stepharo@free.fr>> wrote: >> >> Hi david >> >> I rad the wikipedia page you mention and this looks a bit obvious >> to me. I knew this. >> now it does not really help fixing the problem you mention. >> >> Stef > > Since you asked for itâ¦ > > The #hash method is used in Pharo to separate objects in > bucket-based data structures. > > It must have one required property which is required data integrity: > > * A. Objects that are equal according to #= *must* have equal > hashes. > > > It should have two desirable properties that are required to > support the algorithmic assumptions of bucket-based data structures: > > * B. Objects that are *not* equal *should* have different > hashes. Ideally, the probability of hash collision should by > 1/N where N is the size of hash value space. > * C. The hash values should spread as much as possible over > their value space. For example: ProtoObject>>#identityHash. > > > How these two desirable properties can be implemented depend on > the actual distribution of the value used to compute the hash. > > An object can safely use XOR hashing if its instance variables are > all different objects that already provide a hash method with > these two properties. For example, an object whose behaviour is > defined by several of singleton delegates of different classes > that do not override Object>>#hash. > > But if the instance variables are not guaranteed to have those > properties, it is necessary to more thoroughly "mix the bits". For > example: SequenceableCollection>>#hash. > > hash > | hash | > > hash := self species hash. > 1 to: self size do: [:i | hash := (hash + (self at: i) hash) > hashMultiply]. > ^hash > > The mixing of the bits is done by the combination of addition and > hashMultiply. The value of "species hash" does not need to be > processed by hashMultiply, because it is probably computed by > ProtoObject>>identityHash, and that already provides C. > > LayoutFrame is a particularly good example of a data structure > that should *not* use XOR hashing. Its instance variables provide > none of the required properties: SmallInteger>>#hash is just > ^self. In addition, common LayoutFrame instances tend to use pairs > of identical values in their instance variables. Like 0@0 corner: > 1@1, or Margin fromNumber: 10. > > A good hash function for LayoutFrame needs to: > > 1. Get hashes for each instance variable that provides A and B. > 2. Combine them in a way that is order-sensitive (to maintain B) > and that does some extra mixing (to provide C). > > > Now, we can assume that common values for the instance variables > will be instances of SmallInteger, Float, or Fraction. > > By the way, you can see in Fraction>>#hash, that a comment > mentions the assumption that the fraction is already reduced, that > is what makes it acceptable to use bitXor. > > The hash of SmallInteger does provide A and B, but not C. The hash > of Float is harder to understand, but tests show that it provide > distinct values for 0.5, 0.25 and 0.125. So it hopefully provides > B for the range of values of interest to LayoutFrame. > > > Note that Squeak has reduced the number of collisions for floats by > not erasing the most significant bits of each word. > I've tested the squeak implementation with Andres Valloud tool in VW, > it does not perform so bad for the sets I tested in term of collisions... > > Float>>hash > "Hash is reimplemented because = is implemented. Both words of the > float are used. (The bitShift:'s ensure that the intermediate results > do not become a large integer.) Care is taken to answer same hash as > an equal Integer." > > (self isFinite and: [self fractionPart = 0.0]) ifTrue: [^self > truncated hash]. > ^ ((self basicAt: 1) bitShift: -4) + > ((self basicAt: 2) bitShift: -4) > > I also changed Fraction to use a hashMultiply and made a more explicit > isAnExactFloat test. > > Fraction>>hash > "Hash is reimplemented because = is implemented." > > "Care is taken that a Fraction equal to a Float also has an equal > hash" > self isAnExactFloat ifTrue: [^self asExactFloat hash]. > > "Else, I cannot be exactly equal to a Float, use own hash algorithm." > ^numerator hash hashMultiply bitXor: denominator hash > > Fraction>>isAnExactFloat > "Answer true if this Fraction can be converted exactly to a Float" > ^ denominator isPowerOfTwo > and: ["I have a reasonable significand: not too big" > numerator highBitOfMagnitude <= Float precision > and: ["I have a reasonable exponent: not too small" > Float emin + denominator highBitOfMagnitude <= > Float precision]] > > Fraction>>asExactFloat > "When we know that this Fraction is an exact Float, this > conversion is much faster than asFloat." > > ^numerator asFloat timesTwoPower: 1 - denominator highBit > > Not that Fraction should allways be reduced (this is an invariant of > the class, I hope well defined in class comment). > > Integer hash is not that good because the risk of occupying > consecutive buckets is high... I wonder if returning ^self > hashMultiply would not arrange things here and reduce the requirements > for spreading hashMultiply everywhere else? > > Nicolas > > Another class that has similar hashing constraints to LayoutFrame > is Point. Its hash method is: > > hash > "Hash is reimplemented because = is implemented." > > ^(x hash hashMultiply + y hash) hashMultiply > > It does not include species in the computation, which is less than > ideal because it favours collisions with objects of different > species that have a similar content and a the same #hash algorithm. > > Finally, it is probably not necessary or useful to use the > accessors to get to the instance variables. > > So a good implementation would be this (untested, there might be a > typo or two) > > hash > | hash | > hash := self species hash > hash := (hash + leftFraction hash) hashMultiply > hash := (hash + leftOffset hash) hashMultiply > hash := (hash + topFraction hash) hashMultiply > hash := (hash + topOffset hash) hashMultiply > hash := (hash + rightFraction hash) hashMultiply > hash := (hash + rightOffset hash) hashMultiply > hash := (hash + bottomFraction hash) hashMultiply > hash := (hash + bottomOffset hash) hashMultiply > ^ hash > > I am sure you could have figured that by yourself, by thinking > about how hash values are used and by looking at the code of > kernel classes, instead of getting offended and turning all defensive. > > I hope we can both learn from this episode. I do not enjoy > antagonising people, but I will not write lengthy messages like > this one every time someone questions my thinking. > > Have a nice day. > >> Le 11/1/16 10:09, David Allouche a Ã©crit : >>> Since it's not obvious why xor-ing is a bad way to produce hash, >>> here is a link that gives some background >>> >>> https://en.wikipedia.org/wiki/Hash_function#Uniformity >>> >>>> On 11 Jan 2016, at 10:01, David Allouche <david(a)allouche.net >>>> <mailto:david@allouche.net>> wrote: >>>> >>>> I happened to look at the new code for LayoutFrame>>#hash >>>> >>>> hash >>>> ^self species hash bitXor: >>>> (self leftFraction bitXor: >>>> (self leftOffset bitXor: >>>> (self topFraction bitXor: >>>> (self topOffset bitXor: >>>> (self rightFraction bitXor: >>>> (self rightOffset bitXor: >>>> (self bottomFraction bitXor: >>>> self bottomOffset))))))) >>>> >>>> This is a terrible, terrible way to compute a hash. >>>> >>>> 0 xor 0 = 1 xor 1 = 2 xor 2 = etc. >>>> >>>> NEVER compute hashes with xor, that's wrong, and it causes >>>> horrible, hard to debug, performance bugs down the road. >>>> >>>> SequenceableCollection>>#hash looks more like a correct way of >>>> doing it. I do not know what is the correct, efficient way to >>>> reuse this logic in LayoutFrame>>#hash. >>>> >>>> By the way, how do you guys do code reviews for code integrated >>>> into the core? >>>> >>> >>> >> >> > >

Jan. 13, 2016

Re: [Pharo-dev] Bad layoutFrame>>#hash

by Stephan Eggermont

On 13-01-16 18:38, David Allouche wrote: > Why did you use a single expression instead of using a temporary variable? I find it harder to understand. I did find it very slightly easier to understand. It is not a strong opinion however. The ideomatic smalltalk would be ^#(leftFraction leftOffset topFraction topOffset rightFraction rightOffset bottomFraction bottomOffset) inject: self species hash into: [:hashValue :selector | (hashValue + self perform: selector) hashMultiply ] but that would be slower. I would be tempted to add a binary message Integer>>+** aNumber ^(aNumber +self hash) hashMultiply (I'd prefer +#*, but that doesn't parse) hash ^self species hash +** leftFraction +** leftOffset +** topFraction +** topOffset +** rightFraction +** rightOffset +** bottomFraction +** bottomOffset Stephan

Jan. 13, 2016

Re: [Pharo-dev] Bad layoutFrame>>#hash

by stepharo

Hi david I would like to turn your post into a chapter for a forthcoming book so that people can read and get the idea. I did not think about the same object. Is it ok for you? Stef PS: May be this was obviosu for you that we should all get this out of your previous mail but it was not my case and not after 8 hours on intense work. Le 13/1/16 17:22, David Allouche a Ã©crit : > >> On 12 Jan 2016, at 20:59, stepharo <stepharo(a)free.fr >> <mailto:stepharo@free.fr>> wrote: >> >> Hi david >> >> I rad the wikipedia page you mention and this looks a bit obvious to >> me. I knew this. >> now it does not really help fixing the problem you mention. >> >> Stef > > Since you asked for itâ¦ > > The #hash method is used in Pharo to separate objects in bucket-based > data structures. > > It must have one required property which is required data integrity: > > * A. Objects that are equal according to #= *must* have equal hashes. > > > It should have two desirable properties that are required to support > the algorithmic assumptions of bucket-based data structures: > > * B. Objects that are *not* equal *should* have different hashes. > Ideally, the probability of hash collision should by 1/N where N > is the size of hash value space. > * C. The hash values should spread as much as possible over their > value space. For example: ProtoObject>>#identityHash. > > > How these two desirable properties can be implemented depend on the > actual distribution of the value used to compute the hash. > > An object can safely use XOR hashing if its instance variables are all > different objects that already provide a hash method with these two > properties. For example, an object whose behaviour is defined by > several of singleton delegates of different classes that do not > override Object>>#hash. > > But if the instance variables are not guaranteed to have those > properties, it is necessary to more thoroughly "mix the bits". For > example: SequenceableCollection>>#hash. > > hash > | hash | > > hash := self species hash. > 1 to: self size do: [:i | hash := (hash + (self at: i) hash) > hashMultiply]. > ^hash > > The mixing of the bits is done by the combination of addition and > hashMultiply. The value of "species hash" does not need to be > processed by hashMultiply, because it is probably computed by > ProtoObject>>identityHash, and that already provides C. > > LayoutFrame is a particularly good example of a data structure that > should *not* use XOR hashing. Its instance variables provide none of > the required properties: SmallInteger>>#hash is just ^self. In > addition, common LayoutFrame instances tend to use pairs of identical > values in their instance variables. Like 0@0 corner: 1@1, or Margin > fromNumber: 10. > > A good hash function for LayoutFrame needs to: > > 1. Get hashes for each instance variable that provides A and B. > 2. Combine them in a way that is order-sensitive (to maintain B) and > that does some extra mixing (to provide C). > > > Now, we can assume that common values for the instance variables will > be instances of SmallInteger, Float, or Fraction. > > By the way, you can see in Fraction>>#hash, that a comment mentions > the assumption that the fraction is already reduced, that is what > makes it acceptable to use bitXor. > > The hash of SmallInteger does provide A and B, but not C. The hash of > Float is harder to understand, but tests show that it provide distinct > values for 0.5, 0.25 and 0.125. So it hopefully provides B for the > range of values of interest to LayoutFrame. > > Another class that has similar hashing constraints to LayoutFrame is > Point. Its hash method is: > > hash > "Hash is reimplemented because = is implemented." > > ^(x hash hashMultiply + y hash) hashMultiply > > It does not include species in the computation, which is less than > ideal because it favours collisions with objects of different species > that have a similar content and a the same #hash algorithm. > > Finally, it is probably not necessary or useful to use the accessors > to get to the instance variables. > > So a good implementation would be this (untested, there might be a > typo or two) > > hash > | hash | > hash := self species hash > hash := (hash + leftFraction hash) hashMultiply > hash := (hash + leftOffset hash) hashMultiply > hash := (hash + topFraction hash) hashMultiply > hash := (hash + topOffset hash) hashMultiply > hash := (hash + rightFraction hash) hashMultiply > hash := (hash + rightOffset hash) hashMultiply > hash := (hash + bottomFraction hash) hashMultiply > hash := (hash + bottomOffset hash) hashMultiply > ^ hash > > I am sure you could have figured that by yourself, by thinking about > how hash values are used and by looking at the code of kernel classes, > instead of getting offended and turning all defensive. > > I hope we can both learn from this episode. I do not enjoy > antagonising people, but I will not write lengthy messages like this > one every time someone questions my thinking. > > Have a nice day. > >> Le 11/1/16 10:09, David Allouche a Ã©crit : >>> Since it's not obvious why xor-ing is a bad way to produce hash, >>> here is a link that gives some background >>> >>> https://en.wikipedia.org/wiki/Hash_function#Uniformity >>> >>>> On 11 Jan 2016, at 10:01, David Allouche <david(a)allouche.net> wrote: >>>> >>>> I happened to look at the new code for LayoutFrame>>#hash >>>> >>>> hash >>>> ^self species hash bitXor: >>>> (self leftFraction bitXor: >>>> (self leftOffset bitXor: >>>> (self topFraction bitXor: >>>> (self topOffset bitXor: >>>> (self rightFraction bitXor: >>>> (self rightOffset bitXor: >>>> (self bottomFraction bitXor: >>>> self bottomOffset))))))) >>>> >>>> This is a terrible, terrible way to compute a hash. >>>> >>>> 0 xor 0 = 1 xor 1 = 2 xor 2 = etc. >>>> >>>> NEVER compute hashes with xor, that's wrong, and it causes >>>> horrible, hard to debug, performance bugs down the road. >>>> >>>> SequenceableCollection>>#hash looks more like a correct way of >>>> doing it. I do not know what is the correct, efficient way to reuse >>>> this logic in LayoutFrame>>#hash. >>>> >>>> By the way, how do you guys do code reviews for code integrated >>>> into the core? >>>> >>> >>> >> >> >

Jan. 13, 2016