- Pharo-dev - lists.pharo.org

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

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

by stepharo

Thanks for your post it was really nice. > > I am sure you could have figured that by yourself, If I asked this is that I could not. And I read the book on hash numbers. > 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 do not know where you see me offended and defensive. I asked because the wikipedia page was giving no information that I could use. So please do not read between the lines else tell me I can also ignore your emails. Stef > > 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] How to get launcher launching Spur images?

by Esteban A. Maringolo

Damien, Is the Ubuntu PPA updated automatically by the CI? Regards! Esteban A. Maringolo 2016-01-13 13:34 GMT-03:00 Stephan Eggermont <stephan(a)stack.nl>: > On 13-01-16 17:09, Serge Stinckwich wrote: >> >> Great ! Works for me now with the last version on mac os x. >> >> Maybe new binary version for windows and mac should be provide here for >> newbies: >> https://ci.inria.fr/pharo/view/Launcher/ > > > I've committed a new configuration, promoting this to #stable > and using the latest versions of dependencies. > > It is not yet really friendly enough for newbies, but that's a next step > > Stephan > >

Jan. 13, 2016

Re: [Pharo-dev] Sounds like Goodies

by stepharo

Olivier Auverlot started to port his rebol text library and it includes levenshtein distance too. Le 13/1/16 16:50, Torsten Bergmann a Ã©crit : > The dolphin 7 open source repo includes some contributions from Udo including > an implementation for Levenshtein distance [1]. It's a single method + test case and easy to > port. > > The algorithm [2] is useful to find out how close two strings are (approximate string matching). > > There is also SoundEx [4] and SoundsLike [5] (Soundex, Double Metaphone and NYSIIS algorithms) > for Pharo available. > > I just want to let anyone know - just in case someone works on a more "robust" autocompletion > that is also typo aware. ;) > Having custom templates [6] like in Eclipse would also be good to have in future Pharo code editor. > > More to add to the wishlist? Damn ... Santa already passed by... > > Have fun > T. > > [1] https://github.com/dolphinsmalltalk/Contributions/tree/master/Udo%20Schneid… > [2] https://en.wikipedia.org/wiki/Levenshtein_distance > [3] https://github.com/dolphinsmalltalk/Contributions/tree/master/Udo%20Schneid… > [4] http://smalltalkhub.com/#!/~riverdusty/SXSoundEx > [5] http://www.smalltalkhub.com/#!/~UdoSchneider/SoundsLike > [6] http://www.tutorialspoint.com/eclipse/eclipse_code_templates.htm > >

Jan. 13, 2016

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

by stepharo

Thanks I will try the latest version of the configuration Before it did not work for me. Le 13/1/16 17:34, Stephan Eggermont a Ã©crit : > On 13-01-16 17:09, Serge Stinckwich wrote: >> Great ! Works for me now with the last version on mac os x. >> >> Maybe new binary version for windows and mac should be provide here >> for newbies: >> https://ci.inria.fr/pharo/view/Launcher/ > > I've committed a new configuration, promoting this to #stable > and using the latest versions of dependencies. > > It is not yet really friendly enough for newbies, but that's a next step > > Stephan > > >

Jan. 13, 2016

Re: [Pharo-dev] Right to Left languages and fonts

by Jimmie Houchin

Hello, In a brief exploration. I may look more later. But the Linux Libertine font has a reasonably nice Latin, Greek, and Hebrew and to my understanding many others, set of characters. I like them much better than the original Ariel which I used. The Ariel on Linux is not the Ariel Unicode MS. They may be nearly identical, but I don't know as I have not seen the MS font. Thanks again. Jimmie On 01/11/2016 09:32 AM, Sven Van Caekenberghe wrote: > Jimmy, > > Use the right font, for example Ariel Unicode MS, and you'll be able > to display strings in those languages just fine. Processing these > strings also works just fine. > > [Snip screenshot, see original message] > > Now, editing them right-to-left is not possible. > > Sven > >> On 11 Jan 2016, at 15:50, Jimmie Houchin <jlhouchin(a)gmail.com >> <mailto:jlhouchin@gmail.com>> wrote: >> >> Hello, >> >> I briefly tried to copy/paste, read from file, some Hebrew text. I >> simply get some strange characters. >> >> From a brief search of the archives. I did not find any means of >> doing a right to left language. I also am not sure how to use a >> Hebrew font. Font issues would also apply for when I want to use Greek. >> >> What would be needed to do right to left and use the right Hebrew font? >> >> I believe these issues would also apply to anyone wanting Arabic or >> any other such languages. >> >> The last message I can easily find is in August of 2014. Maybe Pharo >> isn't the right tool for this job at the moment. But I did want to >> explore the potential of it being so. >> >> Thanks for any help. >> >> Jimmie >> >

Jan. 13, 2016