8 ms·

JVM Anatomy Quark #26: Identity Hash Code

101 points by fniephaus 5y ago

matheusmoreira 5y ago
Love to read about these implementation details!
- xxs 5y ago
  There is a caveat the article doesn't mention, it's not possible to use both synchronized/lock elision and System.identityHashCode. The 4bytes in the object header are either used for the hashCode or the threadId(not java.lang.Thread.getId()), holding the monitor. +2 control bits. Also the stuff has not changed for the past... 14y or so. It's pretty old news.
  - _old_dude_ 5y ago
    It's changing now https://wiki.openjdk.java.net/display/lilliput https://wiki.openjdk.java.net/display/lilliput
  - eMGm4D0zgUAVXc7 5y ago
    Can you clarify what is not possible or provide a link please? I haven't heard of this, and don't understand what you said well enough to google it myself.
    - xxs 5y ago
      That's an article[0] from Dave Dice (a quick search for "biased lock java hashCode header) Edit: Found a copy[1] of the early Cliff Click's blog... For whatever reasons google doesn't have it listed (so I typed the url. cliffc.org is empty as well.. Other than that Java's hotspot source is available too. [0]: https://blogs.oracle.com/dave/biased-locking-in-hotspot https://blogs.oracle.com/dave/biased-locking-in-hotspot [1]: https://www.h2o.ai/blog/biased-locking/ https://www.h2o.ai/blog/biased-locking/
      - eMGm4D0zgUAVXc7 5y ago
        Thanks! So am I correctly understanding this as: Using identityHashCode() does not prevent locks from working, it merely prevents the performance optimization of biased locking (which Java 15 disables by default anyway)?
        xxs 5y ago
        Something like that. The biased locking is an overall a software fix for a hardware shortcoming, notably CAS being slow (and need for a fence on the read part, but that's pretty much free on the most of the hardware nowadays). Lack of biased locking could be quite detrimental to CHM wide use. OTOH it'd mean a smaller header/memory footprint, which is nice. If you are interested in the Java internals Cliff Click's (who is the original hotspot architect) insights of a decade ago will worth your while.
teknopaul 5y ago
"It is a frequent source of bugs to change the object in such a way that its hashCode changes after it was used" (citation needed) I have never seen that. 20 years in the game. I can't remember ever having seen anyone use a mutable object for a hashmap key.
- xxs 5y ago
  >I have never seen that. 20 years in the game. I have seen that a bit too many times, it's pretty terrible. People debug and print HashMap contents, and complain the thing is broken... as get(Object) just returns null, finding an empty bucket. I guess, you have been a bit more lucky than I was. Definitely seen too many mutable keys.
- teknopaul 5y ago
  to be honest I can't bring to mimd any code that changes a value without recalling put(), code that does that would smell so bad you would spot it by the @author
- mumblemumble 5y ago
  It's all private code, so I can't give you a citation, but I've often helped junior devs with bugs due to this. The most common way to get there starts with creating a "bean" object. And then, since it's a bean, it has mutable getters and setters. On everything, because that's just the standard way that people are (or at least were) taught to do these things in Java. And then you ask your IDE to give you equals and hashCode implementations, and yeah sure whatever just use all the fields. And then, later on, you need some sort of lookup table that cross-references the data modeled by this bean with some outside source of information. So of course that's a HashMap. And then you go through your objects and update them all based on that information. Maybe you just edit the description or the lastUsed field, who knows. All sorts of possibilities here. In any case, there's your bug.
  - cogman10 5y ago
    I've seen it as well. Usually it takes the form of "I added object x to a HashSet, then while processing things I update a field in object x used in the hashcode. Object x no longer appears in the set".
MauranKilom 5y ago
I don't see how > "Not suprisingly, [...] global counters [...] are poorly distributed as well." is true. I mean, yes, they are not uniformly distributed, but that was never the requirement. As the article itself states, the desired property is that "the values for distinct objects are more or less distinct". With a global counter, you get maximally distinct hash codes. More distinct than any of the other approaches (and not less than any user-implemented function), at least until 2^31 object allocations. Yes, after 2^31 objects you will get repeated values, but that is trivially the case for any pattern of assigning 31 bit hash codes to distinct objects (and any of the pseudo-random approaches will get birthday-paradoxed much sooner, and much harder). The only case where this could matter is in an adversarial scenario where someone is trying to DoS your hash map with crafted inputs. But according to the article itself, it would take 4+ minutes (120 ns * 2^31) of only allocating objects for each global counter wrapping. If an adversary can reliably achieve that already, what's the point in slowing down a hash map by an epsilon every four minutes?
- nlitened 5y ago
  > the values for distinct objects are more or less distinct I think these words of author understate the requirement of good distribution of hash codes. As far as I understand, ideally the hash codes for different objects should be as distinct as practically possible, so that they are often put into separate buckets of a hash table. Consecutively allocated objects will have almost all bits of their addresses equal.
  - MauranKilom 5y ago
    I wouldn't trust any hash table where a hash function yielding consecutive integers would inherently lead to bad behavior. Can you tell me a popular hash-to-bucket reduction that performs badly for this case? I will concede that there are plenty of schemes where insufficient entropy in lower bits causes problems. Combining those with the global counter hash and e.g. only inserting every 64th allocated object could be a failure case indeed. But this is still simple to defend against in the reduction scheme.
    - 5y ago
barosl 5y ago
I think it was a mistake to put hashCode (and to an extent, equals) to all objects by default. It makes Objects bloated, and because of that, those who will never be put to a hash table also need to provide their own hashCode implementations, causing problems like the one mentioned in the article. There should have been a separate, dedicated "Hashable" interface. Strangely, C# shares the same caveat. Is there any benefit to making objects hashable by default?
- deleted 5y ago
  [deleted]
- cogman10 5y ago
  I'm not sure what you mean by bloat. Adding methods doesn't really affect individual object size, just class size. However, actual code weight (rarely) really impacts anything. In the case of Java/C#, hashcode and equals are optional anyways. So if you don't override them, there's no extra space consumed.
  - titzer 5y ago
    The storage of the identity hash code takes ~4 bytes in the object header, and that is independent of whether the method is overridden or not. It's explained in the article.
    - usrusr 5y ago
      But assuming that the other bit in those 4 bytes is required and there isn't some other place available where you could sneak it in, those ~4 bytes would still be allocated (for that one other bit) and only take less memory under some compression scheme. And chances are that even if you did get by without that bit (or found another place for it) you'd in many cases spend far more memory on workarounds for stuff where the creator was too stingy for implementing "IHashable" but you actually need it
      - titzer 5y ago
jollybean 5y ago
They use int instead of long which means if you start to group objects together in any magnitude you will get collisions fairly quickly. Any large HashTable in Java starts to yield the problem of duplicate keys, it's just a weird situation, like you can 99.999% trust something ... but can't ever fully trust it so that over time, you're guaranteed to have something wrong. This problem exhibits itself again under the hood in the JNI API when you have to identify objects in another domain i.e. C++. It's not a 'Quirk' it's basically a big mistake. The ability to uniquely identify objects is so important in so many ways. Sometimes I wish every few versions of Java they would skip the reverse compatibility and make some needed changes.
- jillesvangurp 5y ago
  Hashcode is not used for identity and is explicitly not intended for this and never was. The whole point of this article is that the modern default implementation does not even rely on object identity anymore (it used to). Java has object identity of course. Most good equals implementations rely on that to figure out if the object is being compared to itself before running more expensive operations do field by field comparison. Collisions are a good thing actually if you are implementing a hash table. Otherwise you end up with one bucket per object; which does not scale very well. The reason hashcode can be overridden is so you can have some control over these collisions if you need to.
  - jollybean 5y ago
    It should be. If every object had a 64 bit id, that was guaranteed to be unique, it would make so many things, so much easier and practical. That we're 25 years into this and there is still ambiguity is not helpful. I'll bet they could do that and have nice entropy in the id's and hashtable performance.
- alboy 5y ago
  >Any large HashTable in Java starts to yield the problem of duplicate keys, it's just a weird situation, like you can 99.999% trust something ... but can't ever fully trust it so that over time, you're guaranteed to have something wrong. hashCode() is a prehash function the outputs of which need to be mapped further to the (typically much smaller) number of buckets in a hash table of certain size (which would depend on the number of objects currently in the table), those "duplicate keys" are not a problem, they're how hash tables work in any language. Objects' hashcodes are used to find the relevant bucket, then this bucket is properly examined using equals(). HashMap and Hashtable are backed by arrays which have the max size of Integer.MAX_VALUE (minus some change) in JVM anyway, so those would need to be indexed by an int. I hope this helps to overcome the trust issues you have with Java data structures.

101 points by fniephaus 5y ago

matheusmoreira 5y ago

Love to read about these implementation details!

xxs 5y ago
There is a caveat the article doesn't mention, it's not possible to use both synchronized/lock elision and System.identityHashCode. The 4bytes in the object header are either used for the hashCode or the threadId(not java.lang.Thread.getId()), holding the monitor. +2 control bits. Also the stuff has not changed for the past... 14y or so. It's pretty old news.
- _old_dude_ 5y ago
  It's changing now https://wiki.openjdk.java.net/display/lilliput https://wiki.openjdk.java.net/display/lilliput
- eMGm4D0zgUAVXc7 5y ago
  Can you clarify what is not possible or provide a link please? I haven't heard of this, and don't understand what you said well enough to google it myself.
  - xxs 5y ago
    That's an article[0] from Dave Dice (a quick search for "biased lock java hashCode header) Edit: Found a copy[1] of the early Cliff Click's blog... For whatever reasons google doesn't have it listed (so I typed the url. cliffc.org is empty as well.. Other than that Java's hotspot source is available too. [0]: https://blogs.oracle.com/dave/biased-locking-in-hotspot https://blogs.oracle.com/dave/biased-locking-in-hotspot [1]: https://www.h2o.ai/blog/biased-locking/ https://www.h2o.ai/blog/biased-locking/
    - eMGm4D0zgUAVXc7 5y ago
      Thanks! So am I correctly understanding this as: Using identityHashCode() does not prevent locks from working, it merely prevents the performance optimization of biased locking (which Java 15 disables by default anyway)?
      - xxs 5y ago
        Something like that. The biased locking is an overall a software fix for a hardware shortcoming, notably CAS being slow (and need for a fence on the read part, but that's pretty much free on the most of the hardware nowadays). Lack of biased locking could be quite detrimental to CHM wide use. OTOH it'd mean a smaller header/memory footprint, which is nice. If you are interested in the Java internals Cliff Click's (who is the original hotspot architect) insights of a decade ago will worth your while.

teknopaul 5y ago

"It is a frequent source of bugs to change the object in such a way that its hashCode changes after it was used" (citation needed) I have never seen that. 20 years in the game. I can't remember ever having seen anyone use a mutable object for a hashmap key.

xxs 5y ago
>I have never seen that. 20 years in the game. I have seen that a bit too many times, it's pretty terrible. People debug and print HashMap contents, and complain the thing is broken... as get(Object) just returns null, finding an empty bucket. I guess, you have been a bit more lucky than I was. Definitely seen too many mutable keys.
teknopaul 5y ago
to be honest I can't bring to mimd any code that changes a value without recalling put(), code that does that would smell so bad you would spot it by the @author
mumblemumble 5y ago
It's all private code, so I can't give you a citation, but I've often helped junior devs with bugs due to this. The most common way to get there starts with creating a "bean" object. And then, since it's a bean, it has mutable getters and setters. On everything, because that's just the standard way that people are (or at least were) taught to do these things in Java. And then you ask your IDE to give you equals and hashCode implementations, and yeah sure whatever just use all the fields. And then, later on, you need some sort of lookup table that cross-references the data modeled by this bean with some outside source of information. So of course that's a HashMap. And then you go through your objects and update them all based on that information. Maybe you just edit the description or the lastUsed field, who knows. All sorts of possibilities here. In any case, there's your bug.
- cogman10 5y ago
  I've seen it as well. Usually it takes the form of "I added object x to a HashSet, then while processing things I update a field in object x used in the hashcode. Object x no longer appears in the set".

MauranKilom 5y ago

I don't see how > "Not suprisingly, [...] global counters [...] are poorly distributed as well." is true. I mean, yes, they are not uniformly distributed, but that was never the requirement. As the article itself states, the desired property is that "the values for distinct objects are more or less distinct". With a global counter, you get maximally distinct hash codes. More distinct than any of the other approaches (and not less than any user-implemented function), at least until 2^31 object allocations. Yes, after 2^31 objects you will get repeated values, but that is trivially the case for any pattern of assigning 31 bit hash codes to distinct objects (and any of the pseudo-random approaches will get birthday-paradoxed much sooner, and much harder). The only case where this could matter is in an adversarial scenario where someone is trying to DoS your hash map with crafted inputs. But according to the article itself, it would take 4+ minutes (120 ns * 2^31) of only allocating objects for each global counter wrapping. If an adversary can reliably achieve that already, what's the point in slowing down a hash map by an epsilon every four minutes?

nlitened 5y ago
> the values for distinct objects are more or less distinct I think these words of author understate the requirement of good distribution of hash codes. As far as I understand, ideally the hash codes for different objects should be as distinct as practically possible, so that they are often put into separate buckets of a hash table. Consecutively allocated objects will have almost all bits of their addresses equal.
- MauranKilom 5y ago
  I wouldn't trust any hash table where a hash function yielding consecutive integers would inherently lead to bad behavior. Can you tell me a popular hash-to-bucket reduction that performs badly for this case? I will concede that there are plenty of schemes where insufficient entropy in lower bits causes problems. Combining those with the global counter hash and e.g. only inserting every 64th allocated object could be a failure case indeed. But this is still simple to defend against in the reduction scheme.
  - 5y ago

barosl 5y ago

I think it was a mistake to put hashCode (and to an extent, equals) to all objects by default. It makes Objects bloated, and because of that, those who will never be put to a hash table also need to provide their own hashCode implementations, causing problems like the one mentioned in the article. There should have been a separate, dedicated "Hashable" interface. Strangely, C# shares the same caveat. Is there any benefit to making objects hashable by default?

deleted 5y ago
[deleted]
cogman10 5y ago
I'm not sure what you mean by bloat. Adding methods doesn't really affect individual object size, just class size. However, actual code weight (rarely) really impacts anything. In the case of Java/C#, hashcode and equals are optional anyways. So if you don't override them, there's no extra space consumed.
- titzer 5y ago
  The storage of the identity hash code takes ~4 bytes in the object header, and that is independent of whether the method is overridden or not. It's explained in the article.
  - usrusr 5y ago
    But assuming that the other bit in those 4 bytes is required and there isn't some other place available where you could sneak it in, those ~4 bytes would still be allocated (for that one other bit) and only take less memory under some compression scheme. And chances are that even if you did get by without that bit (or found another place for it) you'd in many cases spend far more memory on workarounds for stuff where the creator was too stingy for implementing "IHashable" but you actually need it
    - titzer 5y ago

jollybean 5y ago

They use int instead of long which means if you start to group objects together in any magnitude you will get collisions fairly quickly. Any large HashTable in Java starts to yield the problem of duplicate keys, it's just a weird situation, like you can 99.999% trust something ... but can't ever fully trust it so that over time, you're guaranteed to have something wrong. This problem exhibits itself again under the hood in the JNI API when you have to identify objects in another domain i.e. C++. It's not a 'Quirk' it's basically a big mistake. The ability to uniquely identify objects is so important in so many ways. Sometimes I wish every few versions of Java they would skip the reverse compatibility and make some needed changes.

jillesvangurp 5y ago
Hashcode is not used for identity and is explicitly not intended for this and never was. The whole point of this article is that the modern default implementation does not even rely on object identity anymore (it used to). Java has object identity of course. Most good equals implementations rely on that to figure out if the object is being compared to itself before running more expensive operations do field by field comparison. Collisions are a good thing actually if you are implementing a hash table. Otherwise you end up with one bucket per object; which does not scale very well. The reason hashcode can be overridden is so you can have some control over these collisions if you need to.
- jollybean 5y ago
  It should be. If every object had a 64 bit id, that was guaranteed to be unique, it would make so many things, so much easier and practical. That we're 25 years into this and there is still ambiguity is not helpful. I'll bet they could do that and have nice entropy in the id's and hashtable performance.
alboy 5y ago
>Any large HashTable in Java starts to yield the problem of duplicate keys, it's just a weird situation, like you can 99.999% trust something ... but can't ever fully trust it so that over time, you're guaranteed to have something wrong. hashCode() is a prehash function the outputs of which need to be mapped further to the (typically much smaller) number of buckets in a hash table of certain size (which would depend on the number of objects currently in the table), those "duplicate keys" are not a problem, they're how hash tables work in any language. Objects' hashcodes are used to find the relevant bucket, then this bucket is properly examined using equals(). HashMap and Hashtable are backed by arrays which have the max size of Integer.MAX_VALUE (minus some change) in JVM anyway, so those would need to be indexed by an int. I hope this helps to overcome the trust issues you have with Java data structures.