[V8] Object Shapes & Inline Caching

Benchmark:

import {createBenchmark} from './benchmark';

const ARRAY_SIZE = 10000;
const array1 = [];  // {value,prop_0}, {value,prop_0}, {value,prop_0}, {value,prop_0},
const array2 = [];  // {value,prop_0}, {value,prop_1}, {value,prop_0}, {value,prop_1},
const array3 = [];  // {value,prop_0}, {value,prop_1}, {value,prop_2}, {value,prop_0},
const array4 = [];  // {value,prop_0}, {value,prop_1}, {value,prop_2}, {value,prop_3},
const array5 = [];
const array6 = [];
const array7 = [];
const array10 = [];
const array100 = [];
const array1000 = [];
const array10000 = [];

for (let i = 0; i < ARRAY_SIZE; i++) {
  array1.push({value: 0, [uniqueName(i, 1)]: false});
  array2.push({value: 0, [uniqueName(i, 2)]: false});
  array3.push({value: 0, [uniqueName(i, 3)]: false});
  array4.push({value: 0, [uniqueName(i, 4)]: false});
  array5.push({value: 0, [uniqueName(i, 5)]: false});
  array6.push({value: 0, [uniqueName(i, 6)]: false});
  array7.push({value: 0, [uniqueName(i, 7)]: false});
  array10.push({value: 0, [uniqueName(i, 10)]: false});
  array100.push({value: 0, [uniqueName(i, 100)]: false});
  array1000.push({value: 0, [uniqueName(i, 1000)]: false});
  array10000.push({value: 0, [uniqueName(i, 10000)]: false});
}
function uniqueName(index: number, shapesCount: number): string {
  return 'prop_' + (index % shapesCount);
}

(function doBenchmarks(benchmark) {
  let sum = 0;
  (function benchmark1(array, timer) {
    while (timer()) {
      for (let i = 0; i < array.length; i++) {
        sum += array[i].value;
      }
    }
  })(array1, benchmark('1'));

  (function benchmark2(array, timer) {
    while (timer()) {
      for (let i = 0; i < array.length; i++) {
        sum += array[i].value;
      }
    }
  })(array2, benchmark('2'));

  (function benchmark3(array, timer) {
    while (timer()) {
      for (let i = 0; i < array.length; i++) {
        sum += array[i].value;
      }
    }
  })(array3, benchmark('3'));

  (function benchmark4(array, timer) {
    while (timer()) {
      for (let i = 0; i < array.length; i++) {
        sum += array[i].value;
      }
    }
  })(array4, benchmark('4'));

  (function benchmark5(array, timer) {
    while (timer()) {
      for (let i = 0; i < array.length; i++) {
        sum += array[i].value;
      }
    }
  })(array5, benchmark('5'));

  (function benchmark6(array, timer) {
    while (timer()) {
      for (let i = 0; i < array.length; i++) {
        sum += array[i].value;
      }
    }
  })(array6, benchmark('6'));

  (function benchmark7(array, timer) {
    while (timer()) {
      for (let i = 0; i < array.length; i++) {
        sum += array[i].value;
      }
    }
  })(array7, benchmark('7'));

  (function benchmark10(array, timer) {
    while (timer()) {
      for (let i = 0; i < array.length; i++) {
        sum += array[i].value;
      }
    }
  })(array10, benchmark('10'));

  (function benchmark100(array, timer) {
    while (timer()) {
      for (let i = 0; i < array.length; i++) {
        sum += array[i].value;
      }
    }
  })(array100, benchmark('100'));

  (function benchmark1000(array, timer) {
    while (timer()) {
      for (let i = 0; i < array.length; i++) {
        sum += array[i].value;
      }
    }
  })(array1000, benchmark('1000'));

  (function benchmark10000(array, timer) {
    while (timer()) {
      for (let i = 0; i < array.length; i++) {
        sum += array[i].value;
      }
    }
  })(array10000, benchmark('10000'));

  benchmark.report();
})(createBenchmark('example3'));

All we did in benchmark function is create branch of array, for each array, the number array1, array2 means how many object shape inside array:

const array1 = [];  // {value,prop_0}, {value,prop_0}, {value,prop_0}, {value,prop_0},
const array2 = [];  // {value,prop_0}, {value,prop_1}, {value,prop_0}, {value,prop_1},
const array3 = [];  // {value,prop_0}, {value,prop_1}, {value,prop_2}, {value,prop_0},
const array4 = [];  // {value,prop_0}, {value,prop_1}, {value,prop_2}, {value,prop_3},

This is the result of benchmark:

Somehow we can see that the first array1runs 13.589us, but array10000runs 75071.458us, there is 55 times difference.

What's going on? why is so?

As we can see that each array has different shape, but the value of props are the same. So why the object shape has such big impact of the performance?

We can see that No4 & 5 is one big jump of number

also, 1000 & 10000 is another huge jump, what's the reason behind it?

Hidden class

(() => {
  interface Person {
    name: string;
    age: number;
  }

  type HiddenClass = any[];
  //const person: Person = { name: "Jack", age: 32 };
  const person_hc_0 = [null, "name", "age"];
  const person: [HiddenClass, ...any] = [person_hc_0, "Jack", 32];

  // console.log("Name:", person.name, "age:", person.age);
  const person_HC = person[0];
  const person_name = person[person_HC.indexOf("name")];
  const person_age = person[person_HC.indexOf("age")];
  console.log("Name:", person_name, "age:", person_age);
})();

When we try to access object prop, VM will create hidden class, and get hash index of the prop, in order to read the value.

Now let's analysis the follow code:

(() => {
  interface Person {
    name: string;
    age: number;
  }

  const people: Person[] = [
    { name: "Jack", age: 32 },
    { name: "Mary", age: 30 },
  ];

  let avgAge: number = 0;

  for (let i = 0; i < people.length; i++) {
    avgAge += people[i].age;
  }

  avgAge /= people.length;

  console.log("Average age:", avgAge);
})();

When we try to sum up age in the for loop, what is actually happening in VM

Inline cache

(() => {
  interface Person {
    name: string;
    age: number;
  }

  type HiddenClass = any[];

  const person_HC_0 = [null, "name", "age"];
  // const people: Person[] = [
  //   { name: "Jack", age: 32 },
  //   { name: "Mary", age: 30 },
  // ];
  const people: [HiddenClass, ...any][] = [
    [person_HC_0, "Jack", 32],
    [person_HC_0, "Mary", 30],
  ];

  let avgAge: number = 0;

  for (let i = 0; i < people.length; i++) {
    // avgAge += people[i].age;
    const person = people[i];
    const person_HC = person[0];
    const person_age = person[person_HC.indexOf("age")];
    avgAge += person_age;
  }

  avgAge /= people.length;

  console.log("Average age:", avgAge);
})();

For this code, compiler will always see the same inline cache, therefore the performance it good.

For the following code:

(() => {
  interface Person {
    name: string;
    age: number;
  }

  type HiddenClass = any[];

  const person_HC_0 = [null, "name", "age"];
  const person_HC_1 = [null, "name", "age", "school"];
  const person_HC_2 = [null, "age", "name"];
  // const people: Person[] = [
  //   { name: "Jack", age: 32 },
  //   { name: "Mary", age: 30, school: 'MIT'},
  //   { age: 31, name: "Jain"},
  // ];
  const people: [HiddenClass, ...any][] = [
    [person_HC_0, "Jack", 32],
    [person_HC_1, "Mary", 30, "MIT"],
    [person_HC_2, 30, "Jain"],
  ];

  let avgAge: number = 0;

  for (let i = 0; i < people.length; i++) {
    // avgAge += people[i].age;
    const person = people[i];
    const person_HC = person[0];
    const person_age = person[person_HC.indexOf("age")];
    avgAge += person_age;
  }

  avgAge /= people.length;

  console.log("Average age:", avgAge);
})();

Although we have three different hidden class, but everytime we only use one of the hidden class, so the performance is also good.

Now if inside for loop, everytime we use a different hidden class as following:

(() => {
  interface Person {
    name: string;
    age: number;
  }

  type HiddenClass = any[];

  const person_HC_0 = [null, "name", "age"];
  const person_HC_1 = [null, "name", "age", "school"];
  const person_HC_2 = [null, "age", "name"];
  // const people: Person[] = [
  //   { name: "Jack", age: 32 },
  //   { name: "Mary", age: 30, school: 'MIT'},
  //   { age: 31, name: "Jain"},
  // ];
  const people: [HiddenClass, ...any][] = [
    [person_HC_0, "Jack", 32],
    [person_HC_1, "Mary", 30, "MIT"],
    [person_HC_2, 30, "Jain"],
  ];

  let avgAge: number = 0;

  for (let i = 0; i < people.length; i++) {
    // avgAge += people[i].age;
    const person = people[i];
    const person_HC = person[0];
    const person_age =
      person[
        person_HC == person_HC_0
          ? 2
          : person_HC == person_HC_1
          ? 2
          : person_HC == person_HC_2
          ? 1
          : person_HC.indexOf("age")
      ];
    avgAge += person_age;
  }

  avgAge /= people.length;

  console.log("Average age:", avgAge);
})();

You can see the lookup condiiton here:

      person[
        person_HC == person_HC_0
          ? 2
          : person_HC == person_HC_1
          ? 2
          : person_HC == person_HC_2
          ? 1
          : person_HC.indexOf("age")
      ];

It turn out that compiler willing to do this up to 4 times. That's why up to 4 times, it was fast, but the 5th, it becomes slow.

But why 1000 & 10000 has such big differece?

It is because, then doing prop lookup person_HC.indexOf("age"), VM using has map, the lenght is upto 1024, if it's over this length, then no optimization can be done.