- Pharo-dev - lists.pharo.org

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

by David Allouche

> 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. 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.

Jan. 13, 2016

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

by Nicolas Cellier

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] Code reviews

by David Allouche

> 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] GitFileTree and Metacello load from github problem

by Mariano Martinez Peck

On Wed, Jan 13, 2016 at 2:24 PM, Thierry Goubier <thierry.goubier(a)gmail.com> wrote: > Hi Mariano, > > yes, this is > > https://pharo.fogbugz.com/f/cases/17125/Metadata-less-compatibility-with-Fi… > . > > It was integrated in Pharo5 (50470) then reverted at one point, so it's > no more in the image. I'm trying to reactivate it, but I don't > understand what the CI error is. > > It's the necessary support for FileTree to handle a filetree without > metadata format. > OK, indeed, it was that bug. I just manually loaded the slice and it worked perfectly. Until integrate it I will handle this in my image building :( Gofer it package: 'SLICE-Issue-17125-Metadata-less-compatibility-with-FileTree'; smalltalkhubUser: 'Pharo' project: 'Pharo50Inbox'; load. > > Thierry > > Le 13/01/2016 18:13, Mariano Martinez Peck a Ã©crit : > >> Hi... I am totally dumb today or what?? >> >> I am trying to load: >> >> Metacello new baseline: 'OSSubprocess'; repository: >> 'github://marianopeck/OSSubprocess:master/repository'; load. >> >> And I am getting this error: >> >> However, I am getting this error: >> >> File Not Found: >> >> 'File @ >> >> /Users/mariano/Trabajo/PharoConsortium/imagenes/github-cache/marianopeck/OSSubprocess/master/marianopeck-OSSubprocess-18ae52f/repository/OSSubprocess-Tests.package/monticello.meta/version' >> >> And doing a ls i get: >> >> ls -la >> >> /Users/mariano/Trabajo/PharoConsortium/imagenes/github-cache/marianopeck/OSSubprocess/master/marianopeck-OSSubprocess-18ae52f/repository/OSSubprocess-Tests.package/monticello.meta/ >> >> -rw-r--r-- 1 mariano staff 55 Jan 13 14:03 categories.st >> <http://categories.st> -rw-r--r-- 1 mariano staff 0 Jan 13 14:03 >> initializers.st <http://initializers.st> -rw-r--r-- 1 mariano staff >> 27 Jan 13 14:03 package >> >> >> There is no 'version' file as this guy is trying to load. >> >> The package was saved using GitFileTree. >> >> Thanks in advacne >> >> -- Mariano http://marianopeck.wordpress.com >> > > > -- Mariano http://marianopeck.wordpress.com

Jan. 13, 2016

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

by David Allouche

> On 13 Jan 2016, at 18:09, Stephan Eggermont <stephan(a)stack.nl> wrote: > > Name: SLICE-Issue-17363-LayoutFrame-fractions-0--0-corner-1--1--LayoutFrame-identity-should-be-true-and-it-is-not-StephanEggermont.2 > Author: StephanEggermont > Time: 13 January 2016, 6:06:01.571074 pm > UUID: 9a5e9ae3-1357-4bfb-921a-3762d57402fd > Ancestors: > Dependencies: Morphic-Base-StephanEggermont.529 > > Better hash both in distribution and in working with Float coordinates > > > > hash > ^(((((((( self species hash > + leftFraction hash) hashMultiply > + leftOffset hash) hashMultiply > + topFraction hash) hashMultiply > + topOffset hash) hashMultiply > + rightFraction hash) hashMultiply > + rightOffset hash) hashMultiply > + bottomFraction hash) hashMultiply > + bottomOffset hash) hashMultiply Thank you for integrating the fix. I just realised I forgot to put in "." expression separators in my code. Why did you use a single expression instead of using a temporary variable? I find it harder to understand.

Jan. 13, 2016

Code reviews

by Ben Coman

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'd be interested in what you've seen work in other environments. Have you seen these... http://pharo.org/contribute-propose-fix https://pharo.fogbugz.com/?W68 cheers -ben

Jan. 13, 2016

Re: [Pharo-dev] GitFileTree and Metacello load from github problem

by Thierry Goubier

Hi Mariano, yes, this is https://pharo.fogbugz.com/f/cases/17125/Metadata-less-compatibility-with-Fi…. It was integrated in Pharo5 (50470) then reverted at one point, so it's no more in the image. I'm trying to reactivate it, but I don't understand what the CI error is. It's the necessary support for FileTree to handle a filetree without metadata format. Thierry Le 13/01/2016 18:13, Mariano Martinez Peck a Ã©crit : > Hi... I am totally dumb today or what?? > > I am trying to load: > > Metacello new baseline: 'OSSubprocess'; repository: > 'github://marianopeck/OSSubprocess:master/repository'; load. > > And I am getting this error: > > However, I am getting this error: > > File Not Found: > > 'File @ > /Users/mariano/Trabajo/PharoConsortium/imagenes/github-cache/marianopeck/OSSubprocess/master/marianopeck-OSSubprocess-18ae52f/repository/OSSubprocess-Tests.package/monticello.meta/version' > > And doing a ls i get: > > ls -la > /Users/mariano/Trabajo/PharoConsortium/imagenes/github-cache/marianopeck/OSSubprocess/master/marianopeck-OSSubprocess-18ae52f/repository/OSSubprocess-Tests.package/monticello.meta/ > > -rw-r--r-- 1 mariano staff 55 Jan 13 14:03 categories.st > <http://categories.st> -rw-r--r-- 1 mariano staff 0 Jan 13 14:03 > initializers.st <http://initializers.st> -rw-r--r-- 1 mariano staff > 27 Jan 13 14:03 package > > > There is no 'version' file as this guy is trying to load. > > The package was saved using GitFileTree. > > Thanks in advacne > > -- Mariano http://marianopeck.wordpress.com

Jan. 13, 2016

GitFileTree and Metacello load from github problem

by Mariano Martinez Peck

Hi... I am totally dumb today or what?? I am trying to load: Metacello new baseline: 'OSSubprocess'; repository: 'github://marianopeck/OSSubprocess:master/repository'; load. And I am getting this error: However, I am getting this error: File Not Found: 'File @ /Users/mariano/Trabajo/PharoConsortium/imagenes/github-cache/marianopeck/OSSubprocess/master/marianopeck-OSSubprocess-18ae52f/repository/OSSubprocess-Tests.package/monticello.meta/version' And doing a ls i get: ls -la /Users/mariano/Trabajo/PharoConsortium/imagenes/github-cache/marianopeck/OSSubprocess/master/marianopeck-OSSubprocess-18ae52f/repository/OSSubprocess-Tests.package/monticello.meta/ -rw-r--r-- 1 mariano staff 55 Jan 13 14:03 categories.st -rw-r--r-- 1 mariano staff 0 Jan 13 14:03 initializers.st -rw-r--r-- 1 mariano staff 27 Jan 13 14:03 package There is no 'version' file as this guy is trying to load. The package was saved using GitFileTree. Thanks in advacne -- Mariano http://marianopeck.wordpress.com

Jan. 13, 2016

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

by Stephan Eggermont

Name: SLICE-Issue-17363-LayoutFrame-fractions-0--0-corner-1--1--LayoutFrame-identity-should-be-true-and-it-is-not-StephanEggermont.2 Author: StephanEggermont Time: 13 January 2016, 6:06:01.571074 pm UUID: 9a5e9ae3-1357-4bfb-921a-3762d57402fd Ancestors: Dependencies: Morphic-Base-StephanEggermont.529 Better hash both in distribution and in working with Float coordinates hash ^(((((((( self species hash + leftFraction hash) hashMultiply + leftOffset hash) hashMultiply + topFraction hash) hashMultiply + topOffset hash) hashMultiply + rightFraction hash) hashMultiply + rightOffset hash) hashMultiply + bottomFraction hash) hashMultiply + bottomOffset hash) hashMultiply

Jan. 13, 2016

Re: [Pharo-dev] Problem with gitfiletree numeration

by Ben Coman

>>>>> 2016-01-13 13:12 GMT+01:00 Mariano Martinez Peck >>>>> <marianopeck(a)gmail.com>: >>>>>> >>>>>> 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? >>>>> On Wed, Jan 13, 2016 at 10:46 PM, David Allouche <david(a)allouche.net> wrote: > > Removing commits from a git branch is only really problematic if there are > outstanding, unmerged branches out there, since it tends to cause false > merge conflicts. > > Locals clones of the public repository WILL complain about a divergence, but > they can be fixed by "git pull --force". That is probably acceptable in your > context, since you appear to be in a "botched history" situation. > > Taking a step back, any distributed version control that uses explicit > revision numbers for ordering is broken by design. Yes, Monticello, I am > looking at you. > > That was one of the design mistakes of GNU Arch, and the reason why all the > DVCS that followed it (bzr, hg, git) identify revisions by UUIDs and define > ordering exclusively by the ancestry graph. Experience has also shown that > using content-based UUIDs like hg and git is preferable, for performance and > integrity, to using arbitrary UUIDs like bzr did. > > Disclaimer: I am (not yet) familiar with the Monticello model, so I might be > all wrong. But I am quite knowledgeable about DVCS design in general. >From the little I know about Monticello I believe you are correct. Its a known problem - just no-one has got to tackle it yet. I'm not familiar with this space, but you may be interested in Ring [1] , Epicea [2], libgit[3], in-image github[4]. cheers -ben [1] http://rmod.lille.inria.fr/archives/talks/2010-Smalltalks-Uquillas-Ring.pdf [2] http://arxiv.org/pdf/1309.4334.pdf [3] https://github.com/theseion/LibGit [4] http://forum.world.st/Basic-versioning-of-GitHub-repositories-from-within-P…

Jan. 13, 2016