1// Copyright 2016 the V8 project authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4
5function ObjectWithKeys(count, keyOffset = 0, keyGen) {
6  var body = "";
7  for (var i = 0; i < count; i++) {
8    var key = keyGen(i + keyOffset);
9    if (typeof key === "string") {
10      body += `this.${key} = 0\n`;
11    } else {
12      body += `this[${key}] = 0\n`;
13    }
14  }
15  var f = new Function(body);
16  return new f();
17}
18
19function ObjectWithProperties(count, keyOffset) {
20  return ObjectWithKeys(count, keyOffset, (key) => "key" + key );
21}
22
23function ObjectWithElements(count, keyOffset) {
24  return ObjectWithKeys(count, keyOffset, (key) => key );
25}
26
27function ObjectWithMixedKeys(count, keyOffset) {
28  return ObjectWithKeys(count, keyOffset, (key) => {
29    if (key % 2 == 0) return (key / 2);
30    return "key" + ((key - 1)  / 2);
31  });
32}
33
34// Create an object with #depth prototypes each having #keys properties
35// generated by given keyGen.
36function ObjectWithProtoKeys(depth, keys, cacheable,
37                             keyGen = ObjectWithProperties) {
38  var o = keyGen(keys);
39  var current = o;
40  var keyOffset = 0;
41  for (var i = 0; i < depth; i++) {
42    keyOffset += keys;
43    current.__proto__ = keyGen(keys, keyOffset);
44    current = current.__proto__;
45  }
46  if (cacheable === false) {
47    // Add an empty proxy at the prototype chain to make caching properties
48    // impossible.
49    current.__proto__ = new Proxy({}, {});
50  }
51  return o;
52}
53
54
55function HoleyIntArray(size) {
56  var array = new Array(size);
57  for (var i = 0; i < size; i += 3) {
58    array[i] = i;
59  }
60  return array
61}
62
63function IntArray(size) {
64  var array = new Array(size);
65  for (var i = 0; i < size; i++) {
66    array[i] = i;
67  }
68  return array;
69}
70
71// Switch object's properties and elements to dictionary mode.
72function MakeDictionaryMode(obj) {
73  obj.foo = 0;
74  delete obj.foo;
75  obj[1e9] = 0;
76  return obj;
77}
78
79function Internalize(s) {
80  return Object.keys({[s]:0})[0];
81}
82
83function Deinternalize(s) {
84  return [...s].join("");
85}
86
87// ============================================================================
88
89const QUERY_INTERNALIZED_PROP = "INTERN-prop";
90const QUERY_DEINTERNALIZED_PROP = "DEINTERN-prop";
91const QUERY_NON_EXISTING_INTERNALIZED_PROP = "NE-INTERN-prop";
92const QUERY_NON_EXISTING_DEINTERNALIZED_PROP = "NE-DEINTERN-prop";
93const QUERY_ELEMENT = "el";
94const QUERY_ELEMENT_AS_STRING = "el-str";
95const QUERY_NON_EXISTING_ELEMENT = "NE-el";
96
97const OBJ_MODE_FAST = "fast";
98const OBJ_MODE_SLOW = "slow";
99
100var TestQueries = [
101  QUERY_INTERNALIZED_PROP,
102  QUERY_DEINTERNALIZED_PROP,
103  QUERY_NON_EXISTING_INTERNALIZED_PROP,
104  QUERY_NON_EXISTING_DEINTERNALIZED_PROP,
105  QUERY_ELEMENT,
106  QUERY_ELEMENT_AS_STRING,
107  QUERY_NON_EXISTING_ELEMENT,
108];
109
110const QUERIES_PER_OBJECT_NUMBER = 10;
111
112// Leave only every "count"th keys.
113function FilterKeys(keys, count) {
114  var len = keys.length;
115  if (len < count) throw new Error("Keys array is too short: " + len);
116  var step = len / count;
117  if (step == 0) throw new Error("Bad count specified: " + count);
118  return keys.filter((element, index) => index % step == 0);
119}
120
121
122function MakeKeyQueries(keys, query_kind) {
123  var properties = keys.filter((element) => isNaN(Number(element)));
124  var elements = keys.filter((element) => !isNaN(Number(element)));
125
126  properties = FilterKeys(properties, QUERIES_PER_OBJECT_NUMBER);
127  elements = FilterKeys(elements, QUERIES_PER_OBJECT_NUMBER);
128
129  switch (query_kind) {
130    case QUERY_INTERNALIZED_PROP:
131      return properties;
132
133    case QUERY_DEINTERNALIZED_PROP:
134      return properties.map(Deinternalize);
135
136    case QUERY_NON_EXISTING_INTERNALIZED_PROP:
137    case QUERY_NON_EXISTING_DEINTERNALIZED_PROP:
138      var non_existing = [];
139      for (var i = 0; i < QUERIES_PER_OBJECT_NUMBER; i++) {
140        non_existing.push("non-existing" + i);
141      }
142      if (query_kind == QUERY_NON_EXISTING_INTERNALIZED_PROP) {
143        return non_existing.map(Internalize);
144      } else {
145        return non_existing.map(Deinternalize);
146      }
147
148    case QUERY_ELEMENT:
149      return elements.map(Number);
150
151    case QUERY_ELEMENT_AS_STRING:
152      return elements.map(String);
153
154    case QUERY_NON_EXISTING_ELEMENT:
155      var non_existing = [];
156      for (var i = 0; i < QUERIES_PER_OBJECT_NUMBER; i++) {
157        non_existing.push(1200 + 100*i);
158      }
159      return non_existing;
160
161    default:
162      throw new Error("Bad query_kind: " + query_kind);
163  }
164}
165
166
167var TestData = [];
168
169[true, false].forEach((cachable) => {
170  [OBJ_MODE_FAST, OBJ_MODE_SLOW].forEach((obj_mode) => {
171    var proto_mode = cachable ? "" : "-with-slow-proto";
172    var name = `${obj_mode}-obj${proto_mode}`;
173    var objects = [];
174    [10, 50, 100, 200, 500].forEach((prop_count) => {
175      // Create object with prop_count properties and prop_count elements.
176      obj = ObjectWithProtoKeys(5, prop_count * 2, cachable,
177                                ObjectWithMixedKeys);
178      if (obj_mode == OBJ_MODE_SLOW) {
179        obj = MakeDictionaryMode(obj);
180      }
181      objects.push(obj);
182    });
183    TestData.push({name, objects});
184  });
185});
186
187
188// ============================================================================
189
190function CreateTestFunction(template, object, keys) {
191  // Force a new function for each test-object to avoid side-effects due to ICs.
192  var text = "// random comment " + Math.random() + "\n" +
193             template(object, keys);
194  var func = new Function("object", "keys", text);
195  return () => func(object, keys);
196}
197
198function CombineTestFunctions(tests) {
199  return () => {
200    for (var i = 0; i < tests.length; i++ ) {
201      tests[i]();
202    }
203  };
204}
205
206var TestFunctions = [
207  {
208    name: "in",
209    // Query all keys.
210    keys: (object) => Object.keys(object),
211    template: (object, keys) => {
212      var lines = [
213        `var result = true;`,
214        `for (var i = 0; i < keys.length; i++) {`,
215        `  var key = keys[i];`,
216        `  result = (key in object) && result;`,
217        `}`,
218        `return result;`,
219      ];
220      return lines.join("\n");
221    },
222  },
223  {
224    name: "Object.hasOwnProperty",
225    // Query only own keys.
226    keys: (object) => Object.getOwnPropertyNames(object),
227    template: (object, keys) => {
228      var lines = [
229        `var result = true;`,
230        `for (var i = 0; i < keys.length; i++) {`,
231        `  var key = keys[i];`,
232        `  result = object.hasOwnProperty(key) && result;`,
233        `}`,
234        `return result;`,
235      ];
236      return lines.join("\n");
237    },
238  },
239];
240
241
242// ============================================================================
243// Create the benchmark suites. We create a suite for each pair of the test
244// functions above and query kind. Each suite contains benchmarks for each
245// object type.
246var Benchmarks = [];
247
248for (var test_function_desc of TestFunctions) {
249  var test_function_name = test_function_desc.name;
250
251  for (var query_kind of TestQueries) {
252    var benchmarks = [];
253    var suit_name = test_function_name + "--" + query_kind;
254    for (var test_data of TestData) {
255      var name = suit_name + "--" + test_data.name;
256
257      var tests = [];
258      for (var object of test_data.objects) {
259        var keys = test_function_desc.keys(object);
260        keys = MakeKeyQueries(keys, query_kind);
261
262        var test = CreateTestFunction(test_function_desc.template, object,
263                                      keys);
264        tests.push(test);
265      }
266      var run_function = CombineTestFunctions(tests);
267      var benchmark = new Benchmark(name, false, false, 0, run_function);
268      benchmarks.push(benchmark);
269    }
270    Benchmarks.push(new BenchmarkSuite(suit_name, [100], benchmarks));
271  }
272}
273
274// ============================================================================
275