[prev in list] [next in list] [prev in thread] [next in thread] 

List:       openjdk-openjfx-dev
Subject:    Re: [9] Review request for 8140503: JavaFX "Pair" Hash Code Collisions
From:       Jim Graham <james.graham () oracle ! com>
Date:       2015-11-24 20:41:09
Message-ID: 5654CB65.906 () oracle ! com
[Download RAW message or body]

That sounds good.

			...jim

On 11/23/15 12:32 PM, Vadim Pakhnushev wrote:
> How about "Improve javafx.util.Pair hash code computation" ?
>
> Vadim
>
> On 23.11.2015 22:56, Jim Graham wrote:
>> Looks fine to me.  Perhaps the synopsis on the bug should be changed
>> to "... hash code computation causes more collisions than it should"?
>>
>>             ...jim
>>
>> On 11/23/15 6:11 AM, Vadim Pakhnushev wrote:
>>> Guys,
>>> Could you please review the updated fix?
>>>
>>> https://bugs.openjdk.java.net/browse/JDK-8140503
>>> http://cr.openjdk.java.net/~vadim/8140503/webrev.01/
>>>
>>> Thanks,
>>> Vadim
>>>
>>> On 04.11.2015 1:43, Kevin Rushforth wrote:
>>>> Inlining it seems like a fine way to go to me, too. As another point
>>>> of reference, we use 7/31 in other places in JavaFX.
>>>>
>>>> -- Kevin
>>>>
>>>>
>>>> Jim Graham wrote:
>>>>> Absolutely, this report uncovered an unrelated NPE bug which is
>>>>> helpful, and apparently different constants might affect the
>>>>> collision probabilities (which were already very unlikely to begin
>>>>> with), but the bug report was definitely filed primarily as a
>>>>> misunderstanding.
>>>>>
>>>>> One thing to note - perhaps small numbers are more likely to be
>>>>> encountered so the larger the prime, the less likelihood of getting a
>>>>> collision. I wouldn't recommend using too large of a prime since the
>>>>> probability is already so low even with 13, and larger primes may
>>>>> increase the size of the byte code and compiled code since larger
>>>>> constants take more complicated instructions to deal with. Josh Bloch
>>>>> recommended a base of 17 and a multiplier of 37 in Chapter 3 of
>>>>> Effective Java, but he also admitted that the numbers were arbitrary
>>>>> except for the multiplier needing to be an odd prime.
>>>>>
>>>>> One reason 13 might be too low depends on the probability that Pair
>>>>> is used in hash cases with lots of very small numbers. Adding in a
>>>>> base prime and using a little bit larger prime multiplier quickly
>>>>> turns lots of small numbers into massively distributed hashes - even
>>>>> with 31 or 17/37.
>>>>>
>>>>> I kind of feel like using the existing utility is overkill for just 2
>>>>> objects since it requires constructing an array object to use it. I'd
>>>>> be just as happy (perhaps even more so) if we just upgraded the code
>>>>> to check key for null and use a little larger prime, but keep it
>>>>> inlined...
>>>>>
>>>>> ...jim
>>>>>
>>>>> On 11/3/15 1:43 PM, Alexander Kouznetsov wrote:
>>>>>> Moreover, the following two sentences:
>>>>>>
>>>>>> "However, this is an incorrect way to compute a hash code of two
>>>>>> values."
>>>>>> "This can lead to hard-to-find bugs anywhere that instances of
>>>>>> Pair are
>>>>>> used in a data structure like a HashSet or HashTable."
>>>>>>
>>>>>> seem to indicate misunderstanding of what hashcode is and how it
>>>>>> is to
>>>>>> be used.
>>>>>>
>>>>>> Best regards,
>>>>>> Alexander Kouznetsov
>>>>>> (408) 276-0387
>>>>>>
>>>>>> On 3 ноя 2015 13:42, Alexander Kouznetsov wrote:
>>>>>>> After the fix, you should expect another incident report of
>>>>>>>
>>>>>>> Objects.hash(1, 0) == Objects.hash(0, 31)
>>>>>>>
>>>>>>> always true :-)
>>>>>>>
>>>>>>> I'd rather file another bug on key == null causing NPE and closing
>>>>>>> this one as incomplete or not an issue.
>>>>>>>
>>>>>>> Best regards,
>>>>>>> Alexander Kouznetsov
>>>>>>> (408) 276-0387
>>>>>>>
>>>>>>> On 3 ноя 2015 12:07, Vadim Pakhnushev wrote:
>>>>>>>> Hmm, yeah, the actual difference is in the prime number only
>>>>>>>> (that is
>>>>>>>> changing the algorithm only doesn't improve anything), so the only
>>>>>>>> remaining reason to fix this is that Objects.hash guards against
>>>>>>>> null
>>>>>>>> values (and I forgot to mention it in the review).
>>>>>>>> The key in Pair could actually be null and in this case hashCode
>>>>>>>> will
>>>>>>>> throw NPE.
>>>>>>>>
>>>>>>>> Vadim
>>>>>>>>
>>>>>>>> On 03.11.2015 23:01, Vadim Pakhnushev wrote:
>>>>>>>>> Well, not exactly... Previously it was 13*hash(a) + hash(b) and
>>>>>>>>> now
>>>>>>>>> it's 31*(31 + hash(a)) + hash(b).
>>>>>>>>> And apparently it improves the quality somehow. I did a test with
>>>>>>>>> 100^4 combinations and collision probability dropped by the factor
>>>>>>>>> of 3 from 0.065% to 0.022%.
>>>>>>>>> Not really impressive, but still, and it uses well-defined utility
>>>>>>>>> method.
>>>>>>>>> Yeah, I know it's not really a bug since you don't want to rely on
>>>>>>>>> the hashCode at all...
>>>>>>>>>
>>>>>>>>> Thanks,
>>>>>>>>> Vadim
>>>>>>>>>
>>>>>>>>> On 03.11.2015 22:35, Jim Graham wrote:
>>>>>>>>>> All this does is change the prime constant used to produce the
>>>>>>>>>> hash
>>>>>>>>>> value.
>>>>>>>>>>
>>>>>>>>>> Objects.hash(a, b) uses 31*hash(a) + hash(b) instead of the
>>>>>>>>>> 13*hash(a) + hash(b) that the embedded implementation uses.
>>>>>>>>>>
>>>>>>>>>> I don't really think this is a bug. The fact that Integer objects
>>>>>>>>>> make it easy to reverse engineer and compute collisions of any
>>>>>>>>>> reasonable hash combination computation don't mean that the
>>>>>>>>>> technique has a bug, it just means that the submitter can read
>>>>>>>>>> the
>>>>>>>>>> code and think of a counter-example.
>>>>>>>>>>
>>>>>>>>>> If there are practical problems being caused for some particular
>>>>>>>>>> and popular use case by the use of this particular constant "13",
>>>>>>>>>> then we need to understand those issues and come up with a more
>>>>>>>>>> comprehensive solution than to simply hand off to another
>>>>>>>>>> mechanism
>>>>>>>>>> which uses the same procedure with a different prime constant...
>>>>>>>>>>
>>>>>>>>>> ...jim
>>>>>>>>>>
>>>>>>>>>> On 11/3/15 3:06 AM, Vadim Pakhnushev wrote:
>>>>>>>>>>> Hi Chien,
>>>>>>>>>>>
>>>>>>>>>>> Could you please review the fix:
>>>>>>>>>>> https://bugs.openjdk.java.net/browse/JDK-8140503
>>>>>>>>>>> http://cr.openjdk.java.net/~vadim/8140503/webrev.00/
>>>>>>>>>>>
>>>>>>>>>>> Thanks,
>>>>>>>>>>> Vadim
>>>>>>>>>
>>>>>>>>
>>>>>>>
>>>>>>
>>>
>
[prev in list] [next in list] [prev in thread] [next in thread]