Search code examples
c++prototypev8

How are hidden classes in the V8 engine implemented?

So, I have read up on the public Wiki for the V8 engine extensively, and I get the concept of how the hidden classes look up properties. v8 design elements

However, what I don't get really is how this is faster than a hash table.

v8 drawing

According to this, its saying that the properties are stored in different offsets, but for each offset you have to check if its the correct property. So does mean you have to iterate through all properties, at the worst case scenario, to get the right offset for the property you want?

Since hashtables are constant time lookups, wouldn't they be faster than this usually?

Solution

  • It seems that your question is answered through some combination of here, here, and here.

    Briefly, based on my understanding of those links:

    Hashtables are slower than constant-time lookups, so V8 uses the latter when possible, but falls back to the former if objects become too complicated to handle well using hidden classes.

    A linear scan is also obviously bad, but it seems to me that V8 tries to optimize the code to alleviate this problem with the data structure, through a technique called inline caching: when your code attempts to access obj.prop repeatedly, V8 eventually decides to just dynamically patch the generated code such that the property access becomes a constant-time lookup at a given offset.
    Of course, if the expected class type is wrong, then it has to fall back and try a slow lookup.
    function CompileNamedLoadFastProperty(klass, key) on this page tries to explain:

    function CompileNamedLoadFastProperty(klass, key) {
  // Key is known to be constant (named load). Specialize index.
  var index = klass.getIndex(key);

  function KeyedLoadFastProperty(t, k, ic) {
    if (t.klass !== klass) {
      // Expected klass does not match. Can't use cached index.
      // Fall through to the runtime system.
      return NAMED_LOAD_MISS(t, k, ic);
    }
    return t.properties[index];  // Veni. Vidi. Vici.
  }

  return KeyedLoadFastProperty;
}

function NAMED_LOAD_MISS(t, k, ic) {
  var v = LOAD(t, k);
  if (t.klass.kind === "fast") {
    // Create a load stub that is specialized for a fixed class and key k and
    // loads property from a fixed offset.
    var stub = CompileNamedLoadFastProperty(t.klass, k);
    PatchIC("LOAD", ic, stub);
  }
  return v;
}