3 ms·

Given https://shipilev.net/jvm/anatomy-quarks/26-identity-hash-code/ https://shipilev.net/jvm/anatomy-quarks/26-identity-hash-cod...: > For identity hash code,

by derefr 4y ago

Given https://shipilev.net/jvm/anatomy-quarks/26-identity-hash-code/ https://shipilev.net/jvm/anatomy-quarks/26-identity-hash-cod...: > For identity hash code, there is no guarantee there are fields to compute the hash code from, and even if we have some, then it is unknown how stable those fields actually are. Consider java.lang.Object that does not have fields: what’s its hash code? Two allocated Object-s are pretty much the mirrors of each other: they have the same metadata, they have the same (that is, empty) contents. The only distinct thing about them is their allocated address, but even then there are two troubles. First, addresses have very low entropy, especially coming from a bump-ptr allocator like most Java GCs employ, so it is not well distributed. Second, GC moves the objects, so address is not idempotent. Returning a constant value is a no-go from performance standpoint. How else could identity hashcodes be implemented? Is it just impossible to put a WebAssembly GC base-object as a key into a map?

titzer 4y ago
The idea is that if your language has an identity hash code for every object, the language runtime can just add a field in the Wasm struct for it. There's nothing special about that field; it could be an 8-bit, 16-bit, 32-bit field, etc. For the lock inflation logic and so on, you can make a "tagged pointer" in Wasm GC by using the i31ref type, so you could do something like have only the identity hash code by default, but "inflate" to a (boxed) indirection with an additional monitor dynamically. But the Wasm engine just treats it all as regular fields. The overall idea is the Wasm GC gives you the mechanisms by which you can implement your specific language's needs, hopefully as efficiently as a native VM could.
- moonchild 4y ago
  One proposed strategy (https://wiki.openjdk.org/display/lilliput#Main-Hashcode https://wiki.openjdk.org/display/lilliput#Main-Hashcode) for dealing with hashes is to compute them lazily, taking advantage of the fact that most objects are never hashed: initially use the object's address, but also set a flag on the object when it is first hashed; when the gc next moves the object, it adds an extra field in which the original address is cached. Another strategy, used by sbcl, is to rehash identity hash tables after each gc cycle. How could I implement either of these with wasm?
  - derefr 4y ago
    > when the gc next moves the object, it adds an extra field in which the original address is cached. Under this scheme, if I allocate object A at address 0, then GC-move it to address 100 (such that it caches that it was "originally at" address 0); and then, with object A still alive, I allocate object B at address 0... then don't objects A and B both now have 0 as their identity hashcode? (I'm guessing the answer here is "this only works with generational GC, and the GC generation sequence-number is an implicit part of the stateless-address hashcodes and an explicit part of the cached-in-member hashcodes")
    - kaba0 4y ago
      Moving GCs usually copy the object to a new region, and redirect accesses to the old one to the new region. These regions are often used as generations, but they could just be two halves of the heap that flip between active and inactive state.

by derefr 4y ago

titzer 4y ago

The idea is that if your language has an identity hash code for every object, the language runtime can just add a field in the Wasm struct for it. There's nothing special about that field; it could be an 8-bit, 16-bit, 32-bit field, etc. For the lock inflation logic and so on, you can make a "tagged pointer" in Wasm GC by using the i31ref type, so you could do something like have only the identity hash code by default, but "inflate" to a (boxed) indirection with an additional monitor dynamically. But the Wasm engine just treats it all as regular fields. The overall idea is the Wasm GC gives you the mechanisms by which you can implement your specific language's needs, hopefully as efficiently as a native VM could.

moonchild 4y ago
One proposed strategy (https://wiki.openjdk.org/display/lilliput#Main-Hashcode https://wiki.openjdk.org/display/lilliput#Main-Hashcode) for dealing with hashes is to compute them lazily, taking advantage of the fact that most objects are never hashed: initially use the object's address, but also set a flag on the object when it is first hashed; when the gc next moves the object, it adds an extra field in which the original address is cached. Another strategy, used by sbcl, is to rehash identity hash tables after each gc cycle. How could I implement either of these with wasm?
- derefr 4y ago
  > when the gc next moves the object, it adds an extra field in which the original address is cached. Under this scheme, if I allocate object A at address 0, then GC-move it to address 100 (such that it caches that it was "originally at" address 0); and then, with object A still alive, I allocate object B at address 0... then don't objects A and B both now have 0 as their identity hashcode? (I'm guessing the answer here is "this only works with generational GC, and the GC generation sequence-number is an implicit part of the stateless-address hashcodes and an explicit part of the cached-in-member hashcodes")
  - kaba0 4y ago
    Moving GCs usually copy the object to a new region, and redirect accesses to the old one to the new region. These regions are often used as generations, but they could just be two halves of the heap that flip between active and inactive state.