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