9 ms·

> In V8, the hash code is just a random number, independent of the object value. Therefore, we can’t recompute it, meaning we must store it. That's the most in

> In V8, the hash code is just a random number, independent of the object value. Therefore, we can’t recompute it, meaning we must store it. That's the most interesting point in the entire article, and there's no explanation associated. Why are they using random numbers for the hash code?

euroclydon 9y ago
I think it’s because they don’t want to call a hash(v) function on a heterogeneous set of values.
chatmasta 9y ago
Also wondering this. I found a comment on StackOverflow from 2015 [0] that might offer some insight: > "It's probably worth mentioning that V8 goes to great lengths to avoid using a hash table for object properties whenever possible, preferring to compile known property references into direct index references rather than run-time hash lookups for performance reasons (though this is only possible sometimes - depends upon the code)." Since this blog posts mentions they store the hash code as a property of the object, that might imply they are using "direct index references" instead of computing the hash at runtime. It does seem like a couple layers of indirection, though. This is way outside my expertise, so I would love to hear some more comments on this. [0] https://stackoverflow.com/a/30695791/7252597 https://stackoverflow.com/a/30695791/7252597
- deleted 9y ago
  [deleted]
- gnode 9y ago
  The hash cannot be computed, because it's not really a hash at all. In JavaScript's Map and Set, Objects are considered equivalent if they are the same object instance, not if their contents are the same. So really the "hash" is a unique tag. I believe the object's memory location can not be used, as the object may be relocated, and/or a different object stored at the same location at a later time.
  - chatmasta 9y ago
    So where does it store the map to lookup id of the object to its memory location?
    - gnode 9y ago
      That would be stored in the Map / Set object.
chrisseaton 9y ago
What would you use other than a random number? The memory address of the object? Well that may not be well distributed and it possibly leaks information.
- phpnode 9y ago
  Also means they can't move the object without more bookkeeping
- eloff 9y ago
  I would use the memory address, if the GC is a non-moving collector. With a good hash function it should be fine. However, given most GCs are moving, including V8s, I can see why they chose the implementation they did.
blauditore 9y ago
Is it even still a hash code/table in that case, technically? I thought the whole point of a hash table was the hash function "randomly" but reproducably assigning a position to items. This way, it's more some indexed storage with randomized positions.
- chrisseaton 9y ago
  It's an identity hash function. It's a hash of some arbitrary representation of the identity of the object.
- Tarean 9y ago
  Can't use the object content since that can change. So you need a unique identifier. Memory position can't be used because the gc moves objects around. Random number it is.
  - twic 9y ago
    It's pretty much like using a surrogate key in a database.
  - danbruc 9y ago
    Can't use the object content since that can change. It is not uncommon to use the state of an object to derive the hash code. It of course puts the burden to ensure that objects do not change in undesired ways while they are required to yield a stable hash code, for example while used as a key in a hash table, onto the developer. One common solution is to restrict the hash code calculation to immutable parts of the state, for example an ID. The advantage of deriving the hash code from the state is that you can use the hash code to speed up object equality tests, i.e. if the hash codes of two objects do not match, they can not be equal.
- DougBTX 9y ago
  > assigning a position I think what you're asking is "this getHashCode function always returns a random number within a large range, but a hash table has a small set of positions, so isn't this more like a sparse array rather than a hash table?" The answer is that the "hash code" is indeed not the final position, instead it is the input to a function to compute the final position. So, lets say a hash table has 100 positions, then the hash table implementation will essentially do: var position = object.getHashCode() % 100; which converts the random number from getHashCode into a position within the hash table. Since the final "positions" are ints 0-99, the actual underlying storage would look a lot like a 100 element array. > This way, it's more some indexed storage with randomized positions. Summing up, basically yes, you could think of a hash table as indexed storage, where the positions are "randomised" by a modulus on the number of positions. Of course the "random" bit happens when the object hash code is generated, the rest is deterministic. In real life it looks like the minimum number of positions is at least 1022, and that number can change as entries get added to the hash table, but that's the gist of it.
rurban 9y ago
That's the usual approach for advanced object systems with a copying garbage collector. I do the very same. The class pointer is not unique because it might change, so just a random unique id is stored, with 0 reserved as unknown. The lookup could be done per hash, but mostly it's just praying. Similar for symbols and unmutable strings, the id's just need to be unique. In this case it's just the class.
esnard 9y ago
There were several exploits against different languages (PHP, Python, Node) which allowed denial of service attacks by abusing the hash function to craft a special hash table where all elements have the same key. Randomizing the hash function makes it unpredictible to an attacker.
- ninkendo 9y ago
  I think you’re skipping the most contentious point which is that if it’s random it’s not a hash function any more. It’s more of just a unique ID each object has, and calling it a hash any more is misleading.
  - chrisseaton 9y ago
    These are identity hash maps, so they need an identity hash function. That's pretty conventional terminology, used by for example Java, Ruby, ...
    - ninkendo 9y ago
      I suppose you're right, I never really thought of an "identity hash" as being a thing, but if it's commonly accepted nomenclature then there you go.
      - deleted 9y ago
        [deleted]
    - onli 9y ago
      If it is a random number it is not an identity hash function. It is just a position. And in my terminology this makes no sense here, as you normally hash the id/content of the thing you want to store, which is not happening if you return something unrelated to the object. What am I missing? Edit: https://github.com/multiformats/multihash/issues/13 https://github.com/multiformats/multihash/issues/13 suggests this is a replacement for using the content of the object, which is not available, to replace the step of hashing something. Is that it? Then it would be a replacement for a replacement of a hash, and not a hash anymore.
phpnode 9y ago
They only need a unique id for the object, they can't hash based on the object contents because those can change and because two objects with exactly the same properties are not equal in JS: assert({} === {}); // throws
- infogulch 9y ago
  But couldn't the hash be based on the object pointer or something?
  - sushibowl 9y ago
    Doesn't work because the GC moves objects around in memory
  - tzahola 9y ago
    No, because the GC is free to move objects around to compact the heap.
  - phpnode 9y ago
    No, for reasons others have said, but they can use the pointer to deal with collisions
MaxBarraclough 9y ago
You might enjoy this blog post exploring the surprisingly deep (and interesting) rabbit-hole of Java's Object#hashCode() method. https://srvaroa.github.io/jvm/java/openjdk/biased-locking/2017/01/30/hashCode.html https://srvaroa.github.io/jvm/java/openjdk/biased-locking/20...
- twic 9y ago
  > Zing uses a different solution to keep it consistent despite object relocations, in which they delay storing the id. hash until the object relocates. At that point, it’s stored in a “pre-header” IIRC, that's an old David Bacon invention [1]: > For non-moving collectors such as mark-and-sweep, the system can define the default hash code of an object to be its address, or more generally, a function thereof. For moving collectors, we can use the tri-state encoding technique from Bacon et al. [7] (also developed independently by Agesen and used in the Sun EVM), where the states of an object are unhashed, hashed, and hashed-and-moved. For the first two states, the hash code of the object is the address. When the collector moves an object whose state is hashed, it changes its state to hashed-and-moved and copies the old address to the end of the new version of the object. If space is available, the system can encode hash code state in two bits in the object header . [1] See section 3.3 in http://www.research.ibm.com/people/d/dgrove/papers/ecoop02.pdf15 http://www.research.ibm.com/people/d/dgrove/papers/ecoop02.p...
chubot 9y ago
Yeah I don't understand this. How can this possibly work for programs like this: var s1 = readWholeFile('file.txt') var s2 = readWholeFile('file.txt') // now s1 and s2 are different strings, but with the same content assert(s1 == s2) assert(s1 is not s2) var d = {} d[s1] = 'xyz' print(d[s2]) # should print xyz. However if s1 and s2 really have random hash codes how does this work? Is there a difference between "strings" and "objects" in v8? Mutable objects have one hash codes based on IDENTITY, whereas strings have a different hashing strategy based on VALUE? I didn't see that in the blog post. This seems to be an abuse of the term "hash code"? In Python, you can't hash (some) mutable objects: mylist = [] d = {} d[mylist] = 1 Traceback (most recent call last): File "<stdin>", line 1, in <module> TypeError: unhashable type: 'list'
- tlb 9y ago
  As you suspected, the random ID is just for objects and arrays, which are mapped by identity rather than contents. Strings are hashed by content. (You can't do it by address, since everything is movable by the garbage collector. With a non-copying collector, you could just use the address.)
  - chubot 9y ago
    OK I guess that makes sense... I find it odd that such a random number is called a "hash code". I guess because it's an implementation detail and not exposed to the user? When I think of user-facing hash tables, I think that the keys must respect object equality (and sometimes equality can be implemented with identity, for singletons). But I guess JavaScript has no concept of user-definable hash functions for objects, like Python and Java do? So this is purely an implementation detail? You can extend my example to something like: var s1 = readWholeFile('file.txt') var s2 = readWholeFile('file.txt') var array1 = [0, s1] var array2 = [0, s2] var d = {} d[array1] = 'xyz' print(d[array2]) Hm I just tried this and I noticed that JavaScript decays the array1 key to a string!!! That is really bad. But I guess there is some logic to it, because hashing with mutable keys isn't exposed to the user. Because it doesn't make sense! But in many languages, if array1 and array2 are hashable, then they should retrieve the same value, even though they are not identical objects. So their hash codes can't be random numbers -- they should be derived from their values. Overall I find this whole discussion pretty confusing :)

euroclydon 9y ago

I think it’s because they don’t want to call a hash(v) function on a heterogeneous set of values.

chatmasta 9y ago

Also wondering this. I found a comment on StackOverflow from 2015 [0] that might offer some insight: > "It's probably worth mentioning that V8 goes to great lengths to avoid using a hash table for object properties whenever possible, preferring to compile known property references into direct index references rather than run-time hash lookups for performance reasons (though this is only possible sometimes - depends upon the code)." Since this blog posts mentions they store the hash code as a property of the object, that might imply they are using "direct index references" instead of computing the hash at runtime. It does seem like a couple layers of indirection, though. This is way outside my expertise, so I would love to hear some more comments on this. [0] https://stackoverflow.com/a/30695791/7252597 https://stackoverflow.com/a/30695791/7252597

deleted 9y ago
[deleted]
gnode 9y ago
The hash cannot be computed, because it's not really a hash at all. In JavaScript's Map and Set, Objects are considered equivalent if they are the same object instance, not if their contents are the same. So really the "hash" is a unique tag. I believe the object's memory location can not be used, as the object may be relocated, and/or a different object stored at the same location at a later time.
- chatmasta 9y ago
  So where does it store the map to lookup id of the object to its memory location?
  - gnode 9y ago
    That would be stored in the Map / Set object.

chrisseaton 9y ago

What would you use other than a random number? The memory address of the object? Well that may not be well distributed and it possibly leaks information.

phpnode 9y ago
Also means they can't move the object without more bookkeeping
eloff 9y ago
I would use the memory address, if the GC is a non-moving collector. With a good hash function it should be fine. However, given most GCs are moving, including V8s, I can see why they chose the implementation they did.

blauditore 9y ago

Is it even still a hash code/table in that case, technically? I thought the whole point of a hash table was the hash function "randomly" but reproducably assigning a position to items. This way, it's more some indexed storage with randomized positions.

chrisseaton 9y ago
It's an identity hash function. It's a hash of some arbitrary representation of the identity of the object.
Tarean 9y ago
Can't use the object content since that can change. So you need a unique identifier. Memory position can't be used because the gc moves objects around. Random number it is.
- twic 9y ago
  It's pretty much like using a surrogate key in a database.
- danbruc 9y ago
  Can't use the object content since that can change. It is not uncommon to use the state of an object to derive the hash code. It of course puts the burden to ensure that objects do not change in undesired ways while they are required to yield a stable hash code, for example while used as a key in a hash table, onto the developer. One common solution is to restrict the hash code calculation to immutable parts of the state, for example an ID. The advantage of deriving the hash code from the state is that you can use the hash code to speed up object equality tests, i.e. if the hash codes of two objects do not match, they can not be equal.
DougBTX 9y ago
> assigning a position I think what you're asking is "this getHashCode function always returns a random number within a large range, but a hash table has a small set of positions, so isn't this more like a sparse array rather than a hash table?" The answer is that the "hash code" is indeed not the final position, instead it is the input to a function to compute the final position. So, lets say a hash table has 100 positions, then the hash table implementation will essentially do: var position = object.getHashCode() % 100; which converts the random number from getHashCode into a position within the hash table. Since the final "positions" are ints 0-99, the actual underlying storage would look a lot like a 100 element array. > This way, it's more some indexed storage with randomized positions. Summing up, basically yes, you could think of a hash table as indexed storage, where the positions are "randomised" by a modulus on the number of positions. Of course the "random" bit happens when the object hash code is generated, the rest is deterministic. In real life it looks like the minimum number of positions is at least 1022, and that number can change as entries get added to the hash table, but that's the gist of it.

rurban 9y ago

That's the usual approach for advanced object systems with a copying garbage collector. I do the very same. The class pointer is not unique because it might change, so just a random unique id is stored, with 0 reserved as unknown. The lookup could be done per hash, but mostly it's just praying. Similar for symbols and unmutable strings, the id's just need to be unique. In this case it's just the class.

esnard 9y ago

There were several exploits against different languages (PHP, Python, Node) which allowed denial of service attacks by abusing the hash function to craft a special hash table where all elements have the same key. Randomizing the hash function makes it unpredictible to an attacker.

ninkendo 9y ago
I think you’re skipping the most contentious point which is that if it’s random it’s not a hash function any more. It’s more of just a unique ID each object has, and calling it a hash any more is misleading.
- chrisseaton 9y ago
  These are identity hash maps, so they need an identity hash function. That's pretty conventional terminology, used by for example Java, Ruby, ...
  - ninkendo 9y ago
    I suppose you're right, I never really thought of an "identity hash" as being a thing, but if it's commonly accepted nomenclature then there you go.
    - deleted 9y ago
      [deleted]
  - onli 9y ago
    If it is a random number it is not an identity hash function. It is just a position. And in my terminology this makes no sense here, as you normally hash the id/content of the thing you want to store, which is not happening if you return something unrelated to the object. What am I missing? Edit: https://github.com/multiformats/multihash/issues/13 https://github.com/multiformats/multihash/issues/13 suggests this is a replacement for using the content of the object, which is not available, to replace the step of hashing something. Is that it? Then it would be a replacement for a replacement of a hash, and not a hash anymore.

phpnode 9y ago

They only need a unique id for the object, they can't hash based on the object contents because those can change and because two objects with exactly the same properties are not equal in JS: assert({} === {}); // throws

infogulch 9y ago
But couldn't the hash be based on the object pointer or something?
- sushibowl 9y ago
  Doesn't work because the GC moves objects around in memory
- tzahola 9y ago
  No, because the GC is free to move objects around to compact the heap.
- phpnode 9y ago
  No, for reasons others have said, but they can use the pointer to deal with collisions

MaxBarraclough 9y ago

You might enjoy this blog post exploring the surprisingly deep (and interesting) rabbit-hole of Java's Object#hashCode() method. https://srvaroa.github.io/jvm/java/openjdk/biased-locking/2017/01/30/hashCode.html https://srvaroa.github.io/jvm/java/openjdk/biased-locking/20...

twic 9y ago
> Zing uses a different solution to keep it consistent despite object relocations, in which they delay storing the id. hash until the object relocates. At that point, it’s stored in a “pre-header” IIRC, that's an old David Bacon invention [1]: > For non-moving collectors such as mark-and-sweep, the system can define the default hash code of an object to be its address, or more generally, a function thereof. For moving collectors, we can use the tri-state encoding technique from Bacon et al. [7] (also developed independently by Agesen and used in the Sun EVM), where the states of an object are unhashed, hashed, and hashed-and-moved. For the first two states, the hash code of the object is the address. When the collector moves an object whose state is hashed, it changes its state to hashed-and-moved and copies the old address to the end of the new version of the object. If space is available, the system can encode hash code state in two bits in the object header . [1] See section 3.3 in http://www.research.ibm.com/people/d/dgrove/papers/ecoop02.pdf15 http://www.research.ibm.com/people/d/dgrove/papers/ecoop02.p...

chubot 9y ago

Yeah I don't understand this. How can this possibly work for programs like this: var s1 = readWholeFile('file.txt') var s2 = readWholeFile('file.txt') // now s1 and s2 are different strings, but with the same content assert(s1 == s2) assert(s1 is not s2) var d = {} d[s1] = 'xyz' print(d[s2]) # should print xyz. However if s1 and s2 really have random hash codes how does this work? Is there a difference between "strings" and "objects" in v8? Mutable objects have one hash codes based on IDENTITY, whereas strings have a different hashing strategy based on VALUE? I didn't see that in the blog post. This seems to be an abuse of the term "hash code"? In Python, you can't hash (some) mutable objects: mylist = [] d = {} d[mylist] = 1 Traceback (most recent call last): File "<stdin>", line 1, in <module> TypeError: unhashable type: 'list'

tlb 9y ago
As you suspected, the random ID is just for objects and arrays, which are mapped by identity rather than contents. Strings are hashed by content. (You can't do it by address, since everything is movable by the garbage collector. With a non-copying collector, you could just use the address.)
- chubot 9y ago
  OK I guess that makes sense... I find it odd that such a random number is called a "hash code". I guess because it's an implementation detail and not exposed to the user? When I think of user-facing hash tables, I think that the keys must respect object equality (and sometimes equality can be implemented with identity, for singletons). But I guess JavaScript has no concept of user-definable hash functions for objects, like Python and Java do? So this is purely an implementation detail? You can extend my example to something like: var s1 = readWholeFile('file.txt') var s2 = readWholeFile('file.txt') var array1 = [0, s1] var array2 = [0, s2] var d = {} d[array1] = 'xyz' print(d[array2]) Hm I just tried this and I noticed that JavaScript decays the array1 key to a string!!! That is really bad. But I guess there is some logic to it, because hashing with mutable keys isn't exposed to the user. Because it doesn't make sense! But in many languages, if array1 and array2 are hashable, then they should retrieve the same value, even though they are not identical objects. So their hash codes can't be random numbers -- they should be derived from their values. Overall I find this whole discussion pretty confusing :)