2016-01-13 20:34 GMT+01:00 stepharo <[email protected]>: > 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 <[email protected]>: > >> >> On 12 Jan 2016, at 20:59, stepharo <[email protected]> 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 <[email protected]> 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? >> >> >> >> >> >> >> > >
