3

As a follow-up question to the answer to If v8 rehashes when an object grows, I am wondering how v8 actually stores "fast" objects.

From the answer:

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.

Then I asked if v8 rehashes when an object grows, and the answer was:

there is no hashing at all - it's just an offset of memory access - like a struct in C.

(for fast mode objects)

It also mentions:

objects aren't stored as hash maps at all in this case - it's a hidden class

So to summarize, even though you change the object properties, it is still structured so that there is a hidden class:

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

Based on the answer, v8 doesn't actually use a hashtable to store the values because it instead uses a hidden class. So the question is, how does v8 actually store the values as a hidden class struct. What does the hidden class do, how is it structured, how does it work. When you later in your code do var d = 'd'; x[d] (just to make it dynamic), how does it know where the value for d is without hashing the d property as a string to get the index (theoretically). How does it find the memory address of the struct from the key.

Lance
  • 75,200
  • 93
  • 289
  • 503
  • Each time you modify the structure of the object, new hidden class will be created. Lets say we have const obj = {val:1}; Then hidden class will be created. If you do obj.val = 2, nothing will change. But if you do obj.newProp = "", then new hidden class will be created. That's why important to keep objects more less stable to reduce number of the hidden classes and help V8 deal with them. – Drag13 Apr 26 '18 at 13:37
  • @Vitalii I understand that part :) I don't understand how it's actually implemented to find the memory address of the keyed value though. – Lance Apr 26 '18 at 13:38
  • Do you mean: how to access hidden class having the plane object without any map and hashes? – Drag13 Apr 26 '18 at 13:41
  • No, I mean when you do `var d = 'd'; x[d]`, what happens under the hood. How does the C code interpret that code. That is, how does it find the value. The answer says the hidden class is a struct, so you can just jump to that place in memory. But how does it go from `var d = 'd'; x[d]` to the struct's place in memory. – Lance Apr 26 '18 at 13:44
  • @LancePollard i think it's more like a search in a linked list than a hash map – Bergi Apr 26 '18 at 13:45
  • 1
    Have a look at https://mrale.ph/blog/2012/06/03/explaining-js-vms-in-js-inline-caches.html and https://mrale.ph/blog/2015/01/11/whats-up-with-monomorphism.html – Bergi Apr 26 '18 at 13:52

1 Answers1

0

there is no hashing at all - it's just an offset of memory access - like a struct in C.

A struct in C is a continuously block of data. The properties are stored at a fixed offset away from the struct pointer.

For example in

type Foo struct {
  x int32
  y int32
}

If the memory address of foo is m, the memory address of foo.x and foo.y will be m+4, m+8, respectively. Hashtable is not needed here.

V8 maps foo.x to a fixed offset at compile time.

For dynamic properties access the above does not apply.

golopot
  • 10,726
  • 6
  • 37
  • 51