If v8 rehashes when an object grows

Question

Say you have a change in an object that triggers a change in the size of the underlying array or data structure storing the hash values.

var x = { a: 1, b: 2, c: 3 }
// trigger a resize theoretically
x.d = 4
x.e = 5
x.f = 6

Say the underlying array for the hash looked like this in v8

[ 1, 3, 2, null, null ]

It created some extra space initially. But it wasn't quite enough so then it had to grow. There are two options.

It grows leaving the original values in there current place.
It grows and rehashes, moving the values to arbitrary new places.

So it would look like:

// (1) 1, 3, 2 stay where they are
[ 1, 3, 2, 6, 4, 5, null, null, null, null ]

// (2) 1, 3, 2 are moved
[ 6, 2, 5, 3, 4, 1, null, null, null, null ]

Wondering what v8 does in this situation. Also wondering what the heuristics are for the resizing (does it double the array size when it outgrows, etc.).

Wondering how the code in some program is implemented isn't a specific programming problem. It's more of a programmer's curiosity. — , Apr 24 '18 at 22:52
Why do you assume that the empty slots are at the end of the array? Hashes usually don't behave this way. And this is the reason why you cant leave old items in place, they *must* be relocated to their new position. So the two options are: rehashing in one bulk, or rehashing incrementally. May I ask why do you care about the implementation? — Tamas Hegedus, Apr 24 '18 at 22:54
The programming problem is how to create a hash efficiently (like v8 does). — Lance, Apr 24 '18 at 22:56
The thing is that there are no hashes at all - it's just an offset in memory for small objects. — Benjamin Gruenbaum, Apr 24 '18 at 22:57
Oh I thought the keys were hashed, so then the keys would be distributed over some array by the hashing function, then when the object grew with new keys, it would have to potentially rehash them all which seems slow but maybe not. — Lance, Apr 24 '18 at 22:59
@BenjaminGruenbaum e.g. https://stackoverflow.com/questions/48160436/how-v8-hashes-the-keys-in-a-hash-table — Lance, Apr 24 '18 at 23:01
A "how to" question like that is very broad, and "how someone wrote something in some program" isn't a specific programming problem. — , Apr 24 '18 at 23:04
V8 _does_ have a hash table - but it is not used in the case above. The answer you got there is correct - it only applies in dictionary mode though. Are you actually asking about https://github.com/v8/v8/blob/master/src/objects-inl.h#L1759-L1778 ? — Benjamin Gruenbaum, Apr 24 '18 at 23:06

Benjamin Gruenbaum · Accepted Answer · 2018-04-24T22:56:23.747

1

The V8 engine uses two object representations:

Dictionary mode - in which object are stored as key - value maps as a hash map.
Fast mode - in which objects are stored like structs, in which there is no computation involved in property access.

Fast mode is typically much faster for property access - but requires the object's structure to be known.

V8 will initially try to construct a template of what the object looks like called a "Hidden Class". The object will transform through hidden classes until V8 will give up and store the object as a slow property.

I go into this more in depth with the relevant code in "How does Bluebird's util.toFastProperties function make an object's properties “fast”? ".

As for your direct question the object would "fast assign" on those property assignments (on each such assignment) and migrate to a different map (copying the memory as needed).

edited Apr 24 '18 at 22:56

answered Apr 24 '18 at 22:53

Benjamin Gruenbaum

270,886
87
504
504

1

I'm not seeing how this is related to the question. – Apr 24 '18 at 22:55
@CrazyTrain I left a more direct answer at the end - though I maintain the description explains what V8 does in terms of changing objects as properties are added. – Benjamin Gruenbaum Apr 24 '18 at 22:57
In migrating to a different map, not sure yet if you are saying it rehashes the values (copying the memory as needed). – Lance Apr 24 '18 at 22:58
@CrazyTrain "how does V8 hash efficiently here?" - "It doesn't, objects aren't stored as hash maps at all in this case - it's a hidden class". – Benjamin Gruenbaum Apr 24 '18 at 22:58
@LancePollard there is no hashing at all - it's just an offset of memory access - like a struct in C. – Benjamin Gruenbaum Apr 24 '18 at 22:58
So from what I gather, a slow property is dictionary mode, and if they can create a [hidden class](https://stackoverflow.com/questions/48916642/hidden-classes-and-equivalence-between-object-vs-custom-constructor-v8) then they won't go into the slow mode. What I would like to know is how v8 then stores the fast mode objects, given that you have string keys like `{ foo: 10 }`. They must be hashed at some point (maybe in the hidden class definition) then maybe that maps to an index... Would love to know how that works. – Lance Apr 26 '18 at 13:21
@BenjaminGruenbaum follow-up question https://stackoverflow.com/questions/50044338/how-v8-stores-fast-objects – Lance Apr 26 '18 at 13:31
@LancePollard I've had a negative experience answering this question - so no thanks :) – Benjamin Gruenbaum Apr 26 '18 at 15:48
I'm sorry about that :/ – Lance Apr 26 '18 at 15:49

score 1 · Answer 2 · answered Apr 26 '18 at 13:06

V8 has published a detailed blogpost on how they store properties.

In the case of dictionary properties V8 (which would not be the case in your example) the underlying data structure is a hash map and thus the actual location in underlying array changes.

However, JavaScript demands that properties are iterated in insertion order. Hence, each dictionary currently keeps track of it's insertion position to iterate the entries in the proper order.

V8 keeps uses powers of 2 for the dictionary sizes and tries to keep them roughly 50% empty to avoid frequent hash collisions.

If v8 rehashes when an object grows

2 Answers2

Linked