Reimplement Maps and Sets in JS

src/collection.js

 // Copyright 2012 the V8 project authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 "use strict";
 
 // This file relies on the fact that the following declaration has been made
 // in runtime.js:
 // var $Array = global.Array;
 
 var $Set = global.Set;
 var $Map = global.Map;
 
 
+// Used by harmony-templates.js
+var $MapGet;
+var $MapSet;
+
+
+(function() {
+  "use strict";

[arv (Not doing code reviews), 2015/03/30 18:55:22]

This extra use strict is not need (it also does no harm)

[adamk, 2015/03/30 22:31:50]

Isn't this in fact the only one that _does_ have an effect? I thought we
concatenated all the bits of builtin JS together and so the "use strict" at the
top of each file was a lie.

+
+
+  function HashToEntry(table, hash, numBuckets) {
+    var bucket = ORDERED_HASH_TABLE_HASH_TO_BUCKET(hash, numBuckets);
+    return ORDERED_HASH_TABLE_BUCKET_AT(table, bucket);
+  }
+  %SetInlineBuiltinFlag(HashToEntry);
+
+
+  function SetFindEntry(table, numBuckets, key, hash) {
+    var keyIsNaN = IS_NUMBER(key) && NUMBER_IS_NAN(key);
+    for (var entry = HashToEntry(table, hash, numBuckets);
+         entry !== NOT_FOUND;
+         entry = ORDERED_HASH_SET_CHAIN_AT(table, entry, numBuckets)) {
+      var candidate = ORDERED_HASH_SET_KEY_AT(table, entry, numBuckets);
+      if (key === candidate) {
+        return entry;
+      }
+      if (keyIsNaN && IS_NUMBER(candidate) && NUMBER_IS_NAN(candidate)) {
+        return entry;
+      }
+    }
+    return NOT_FOUND;
+  }
+  %SetInlineBuiltinFlag(SetFindEntry);
+
+
+  function MapFindEntry(table, numBuckets, key, hash) {
+    var keyIsNaN = IS_NUMBER(key) && NUMBER_IS_NAN(key);
+    for (var entry = HashToEntry(table, hash, numBuckets);
+         entry !== NOT_FOUND;
+         entry = ORDERED_HASH_MAP_CHAIN_AT(table, entry, numBuckets)) {
+      var candidate = ORDERED_HASH_MAP_KEY_AT(table, entry, numBuckets);
+      if (key === candidate) {
+        return entry;
+      }
+      if (keyIsNaN && IS_NUMBER(candidate) && NUMBER_IS_NAN(candidate)) {

[arv (Not doing code reviews), 2015/03/30 18:55:22]

IS_NUMBER(x) && NUMBER_IS_NAN(x)

is repeated in a few places. Maybe we can introduce a new macro for this?

[adamk, 2015/03/30 22:31:50]

Happy to do that in a followup, these aren't the only places where this shows
up.

+        return entry;
+      }
+    }
+    return NOT_FOUND;
+  }
+  %SetInlineBuiltinFlag(MapFindEntry);
+
+
+  function ComputeIntegerHash(key, seed) {
+    var hash = key;
+    hash = hash ^ seed;
+    hash = ~hash + (hash << 15);  // hash = (hash << 15) - hash - 1;
+    hash = hash ^ (hash >>> 12);
+    hash = hash + (hash << 2);
+    hash = hash ^ (hash >>> 4);
+    hash = (hash * 2057) | 0;  // hash = (hash + (hash << 3)) + (hash << 11);
+    hash = hash ^ (hash >>> 16);
+    return hash;
+  }
+  %SetInlineBuiltinFlag(ComputeIntegerHash);
+
+
+  function GetHash(key) {
+    if (%_IsSmi(key)) {
+      return ComputeIntegerHash(key, 0);
+    }
+    if (IS_STRING(key)) {
+      var field = %_StringGetRawHashField(key);
+      if ((field & 1 /* Name::kHashNotComputedMask */) === 0) {
+        return (field >>> 2 /* Name::kHashShift */);

[arv (Not doing code reviews), 2015/03/30 18:55:22]

skip parens here

[adamk, 2015/03/30 22:31:50]

Done.

+      }
+    }
+    return %GenericHash(key);
+  }
+  %SetInlineBuiltinFlag(GetHash);
+
+
 // -------------------------------------------------------------------
 // Harmony Set
 
 function SetConstructor(iterable) {
   if (!%_IsConstructCall()) {
     throw MakeTypeError('constructor_not_function', ['Set']);
   }
 
   %_SetInitialize(this);
 
   if (!IS_NULL_OR_UNDEFINED(iterable)) {
     var adder = this.add;
     if (!IS_SPEC_FUNCTION(adder)) {
       throw MakeTypeError('property_not_function', ['add', this]);
     }
 
     for (var value of iterable) {
       %_CallFunction(this, value, adder);
     }
   }
 }
 
 
-function SetAddJS(key) {
+function SetAdd(key) {
   if (!IS_SET(this)) {
     throw MakeTypeError('incompatible_method_receiver',
                         ['Set.prototype.add', this]);
   }
   // Normalize -0 to +0 as required by the spec.
   // Even though we use SameValueZero as the comparison for the keys we don't
   // want to ever store -0 as the key since the key is directly exposed when
   // doing iteration.
-  if (key === 0) {
+  if (IS_NUMBER(key) && key === 0) {

[arv (Not doing code reviews), 2015/03/25 11:17:01]

Is this a bug in crankshaft?

[Toon Verwaest, 2015/03/30 12:55:42]

Why is this necessary?

[adamk, 2015/03/30 18:44:53]

It's not necessary for correctness, but it does help performance on the String
case. However I'd be OK with leaving it out of this patch.

[arv (Not doing code reviews), 2015/03/30 18:55:22]

This needs a comment and preferably a bug number.

[adamk, 2015/03/30 22:31:50]

Removed this in the latest version, the perf differences (now?) seem to be in
the noise. It's possible this causes a mostly-harmless deopt when running the
benchmark.

     key = 0;
   }
-  return %_SetAdd(this, key);
+  var table = %_JSCollectionGetTable(this);
+  var numBuckets = ORDERED_HASH_TABLE_BUCKET_COUNT(table);
+  var hash = GetHash(key);
+  if (SetFindEntry(table, numBuckets, key, hash) !== NOT_FOUND) return this;
+
+  var nof = ORDERED_HASH_TABLE_ELEMENT_COUNT(table);
+  var nod = ORDERED_HASH_TABLE_DELETED_COUNT(table);
+  var capacity = numBuckets << 1;
+  if ((nof + nod) >= capacity) {
+    // Need to grow, bail out to runtime.
+    %SetGrow(this);
+    // Re-load state from the grown backing store.
+    table = %_JSCollectionGetTable(this);
+    numBuckets = ORDERED_HASH_TABLE_BUCKET_COUNT(table);
+    nof = ORDERED_HASH_TABLE_ELEMENT_COUNT(table);
+    nod = ORDERED_HASH_TABLE_DELETED_COUNT(table);
+  }
+  var entry = nof + nod;
+  var index = ORDERED_HASH_SET_ENTRY_TO_INDEX(entry, numBuckets);
+  var bucket = ORDERED_HASH_TABLE_HASH_TO_BUCKET(hash, numBuckets);
+  var chainEntry = ORDERED_HASH_TABLE_BUCKET_AT(table, bucket);
+  ORDERED_HASH_TABLE_SET_BUCKET_AT(table, bucket, entry);
+  ORDERED_HASH_TABLE_SET_ELEMENT_COUNT(table, nof + 1);
+  FIXED_ARRAY_SET(table, index, key);
+  FIXED_ARRAY_SET_SMI(table, index + 1, chainEntry);
+  return this;
 }
 
 
-function SetHasJS(key) {
+function SetHas(key) {
   if (!IS_SET(this)) {
     throw MakeTypeError('incompatible_method_receiver',
                         ['Set.prototype.has', this]);
   }
-  return %_SetHas(this, key);
+  var table = %_JSCollectionGetTable(this);
+  var numBuckets = ORDERED_HASH_TABLE_BUCKET_COUNT(table);
+  var hash = GetHash(key);
+  return SetFindEntry(table, numBuckets, key, hash) !== NOT_FOUND;
 }
 
 
-function SetDeleteJS(key) {
+function SetDelete(key) {
   if (!IS_SET(this)) {
     throw MakeTypeError('incompatible_method_receiver',
                         ['Set.prototype.delete', this]);
   }
-  return %_SetDelete(this, key);
+  var table = %_JSCollectionGetTable(this);
+  var numBuckets = ORDERED_HASH_TABLE_BUCKET_COUNT(table);
+  var hash = GetHash(key);
+  var entry = SetFindEntry(table, numBuckets, key, hash);
+  if (entry === NOT_FOUND) return false;
+
+  var nof = ORDERED_HASH_TABLE_ELEMENT_COUNT(table) - 1;
+  var nod = ORDERED_HASH_TABLE_DELETED_COUNT(table) + 1;
+  var index = ORDERED_HASH_SET_ENTRY_TO_INDEX(entry, numBuckets);
+  FIXED_ARRAY_SET(table, index, %_TheHole());
+  ORDERED_HASH_TABLE_SET_ELEMENT_COUNT(table, nof);
+  ORDERED_HASH_TABLE_SET_DELETED_COUNT(table, nod);
+  if (nof < (numBuckets >>> 1)) %SetShrink(this);
+  return true;
 }
 
 
-function SetGetSizeJS() {
+function SetGetSize() {
   if (!IS_SET(this)) {
     throw MakeTypeError('incompatible_method_receiver',
                         ['Set.prototype.size', this]);
   }
-  return %_SetGetSize(this);
+  var table = %_JSCollectionGetTable(this);
+  return ORDERED_HASH_TABLE_ELEMENT_COUNT(table);
 }
 
 
 function SetClearJS() {
   if (!IS_SET(this)) {
     throw MakeTypeError('incompatible_method_receiver',
                         ['Set.prototype.clear', this]);
   }
   %_SetClear(this);
 }
@@ skipping 35 matching lines @@
 
   %SetCode($Set, SetConstructor);
   %FunctionSetPrototype($Set, new $Object());
   %AddNamedProperty($Set.prototype, "constructor", $Set, DONT_ENUM);
   %AddNamedProperty(
       $Set.prototype, symbolToStringTag, "Set", DONT_ENUM | READ_ONLY);
 
   %FunctionSetLength(SetForEach, 1);
 
   // Set up the non-enumerable functions on the Set prototype object.
-  InstallGetter($Set.prototype, "size", SetGetSizeJS);
+  InstallGetter($Set.prototype, "size", SetGetSize);
   InstallFunctions($Set.prototype, DONT_ENUM, $Array(
-    "add", SetAddJS,
-    "has", SetHasJS,
-    "delete", SetDeleteJS,
+    "add", SetAdd,
+    "has", SetHas,
+    "delete", SetDelete,
     "clear", SetClearJS,
     "forEach", SetForEach
   ));
 }
 
 SetUpSet();
 
 
 // -------------------------------------------------------------------
 // Harmony Map
@@ skipping 14 matching lines @@
     for (var nextItem of iterable) {
       if (!IS_SPEC_OBJECT(nextItem)) {
         throw MakeTypeError('iterator_value_not_an_object', [nextItem]);
       }
       %_CallFunction(this, nextItem[0], nextItem[1], adder);
     }
   }
 }
 
 
-function MapGetJS(key) {
+function MapGet(key) {
   if (!IS_MAP(this)) {
     throw MakeTypeError('incompatible_method_receiver',
                         ['Map.prototype.get', this]);
   }
-  return %_MapGet(this, key);
+  var table = %_JSCollectionGetTable(this);
+  var numBuckets = ORDERED_HASH_TABLE_BUCKET_COUNT(table);
+  var hash = GetHash(key);
+  var entry = MapFindEntry(table, numBuckets, key, hash);
+  if (entry === NOT_FOUND) return UNDEFINED;
+  return ORDERED_HASH_MAP_VALUE_AT(table, entry, numBuckets);
 }
 
 
-function MapSetJS(key, value) {
+function MapSet(key, value) {
   if (!IS_MAP(this)) {
     throw MakeTypeError('incompatible_method_receiver',
                         ['Map.prototype.set', this]);
   }
   // Normalize -0 to +0 as required by the spec.
   // Even though we use SameValueZero as the comparison for the keys we don't
   // want to ever store -0 as the key since the key is directly exposed when
   // doing iteration.
-  if (key === 0) {
+  if (IS_NUMBER(key) && key === 0) {
     key = 0;
   }
-  return %_MapSet(this, key, value);
+
+  var table = %_JSCollectionGetTable(this);
+  var numBuckets = ORDERED_HASH_TABLE_BUCKET_COUNT(table);
+  var hash = GetHash(key);
+  var entry = MapFindEntry(table, numBuckets, key, hash);
+  if (entry !== NOT_FOUND) {
+    var existingIndex = ORDERED_HASH_MAP_ENTRY_TO_INDEX(entry, numBuckets);
+    FIXED_ARRAY_SET(table, existingIndex + 1, value);
+    return this;
+  }
+
+  var nof = ORDERED_HASH_TABLE_ELEMENT_COUNT(table);
+  var nod = ORDERED_HASH_TABLE_DELETED_COUNT(table);
+  var capacity = numBuckets << 1;
+  if ((nof + nod) >= capacity) {
+    // Need to grow, bail out to runtime.
+    %MapGrow(this);
+    // Re-load state from the grown backing store.
+    table = %_JSCollectionGetTable(this);
+    numBuckets = ORDERED_HASH_TABLE_BUCKET_COUNT(table);
+    nof = ORDERED_HASH_TABLE_ELEMENT_COUNT(table);
+    nod = ORDERED_HASH_TABLE_DELETED_COUNT(table);
+  }
+  entry = nof + nod;
+  var index = ORDERED_HASH_MAP_ENTRY_TO_INDEX(entry, numBuckets);
+  var bucket = ORDERED_HASH_TABLE_HASH_TO_BUCKET(hash, numBuckets);
+  var chainEntry = ORDERED_HASH_TABLE_BUCKET_AT(table, bucket);
+  ORDERED_HASH_TABLE_SET_BUCKET_AT(table, bucket, entry);
+  ORDERED_HASH_TABLE_SET_ELEMENT_COUNT(table, nof + 1);
+  FIXED_ARRAY_SET(table, index, key);
+  FIXED_ARRAY_SET(table, index + 1, value);
+  FIXED_ARRAY_SET(table, index + 2, chainEntry);
+  return this;
 }
 
 
-function MapHasJS(key) {
+function MapHas(key) {
   if (!IS_MAP(this)) {
     throw MakeTypeError('incompatible_method_receiver',
                         ['Map.prototype.has', this]);
   }
-  return %_MapHas(this, key);
+  var table = %_JSCollectionGetTable(this);
+  var numBuckets = ORDERED_HASH_TABLE_BUCKET_COUNT(table);
+  var hash = GetHash(key);
+  return MapFindEntry(table, numBuckets, key, hash) !== NOT_FOUND;
 }
 
 
-function MapDeleteJS(key) {
+function MapDelete(key) {
   if (!IS_MAP(this)) {
     throw MakeTypeError('incompatible_method_receiver',
                         ['Map.prototype.delete', this]);
   }
-  return %_MapDelete(this, key);
+  var table = %_JSCollectionGetTable(this);
+  var numBuckets = ORDERED_HASH_TABLE_BUCKET_COUNT(table);
+  var hash = GetHash(key);
+  var entry = MapFindEntry(table, numBuckets, key, hash);
+  if (entry === NOT_FOUND) return false;
+
+  var nof = ORDERED_HASH_TABLE_ELEMENT_COUNT(table) - 1;
+  var nod = ORDERED_HASH_TABLE_DELETED_COUNT(table) + 1;
+  var index = ORDERED_HASH_MAP_ENTRY_TO_INDEX(entry, numBuckets);
+  FIXED_ARRAY_SET(table, index, %_TheHole());
+  FIXED_ARRAY_SET(table, index + 1, %_TheHole());
+  ORDERED_HASH_TABLE_SET_ELEMENT_COUNT(table, nof);
+  ORDERED_HASH_TABLE_SET_DELETED_COUNT(table, nod);
+  if (nof < (numBuckets >>> 1)) %MapShrink(this);
+  return true;
 }
 
 
-function MapGetSizeJS() {
+function MapGetSize() {
   if (!IS_MAP(this)) {
     throw MakeTypeError('incompatible_method_receiver',
                         ['Map.prototype.size', this]);
   }
-  return %_MapGetSize(this);
+  var table = %_JSCollectionGetTable(this);
+  return ORDERED_HASH_TABLE_ELEMENT_COUNT(table);
 }
 
 
 function MapClearJS() {
   if (!IS_MAP(this)) {
     throw MakeTypeError('incompatible_method_receiver',
                         ['Map.prototype.clear', this]);
   }
   %_MapClear(this);
 }
@@ skipping 33 matching lines @@
 
   %SetCode($Map, MapConstructor);
   %FunctionSetPrototype($Map, new $Object());
   %AddNamedProperty($Map.prototype, "constructor", $Map, DONT_ENUM);
   %AddNamedProperty(
       $Map.prototype, symbolToStringTag, "Map", DONT_ENUM | READ_ONLY);
 
   %FunctionSetLength(MapForEach, 1);
 
   // Set up the non-enumerable functions on the Map prototype object.
-  InstallGetter($Map.prototype, "size", MapGetSizeJS);
+  InstallGetter($Map.prototype, "size", MapGetSize);
   InstallFunctions($Map.prototype, DONT_ENUM, $Array(
-    "get", MapGetJS,
-    "set", MapSetJS,
-    "has", MapHasJS,
-    "delete", MapDeleteJS,
+    "get", MapGet,
+    "set", MapSet,
+    "has", MapHas,
+    "delete", MapDelete,
     "clear", MapClearJS,
     "forEach", MapForEach
   ));
+
+  $MapGet = MapGet;

[adamk, 2015/03/25 16:13:36]

This is where I copy MapGet into the global scope.

+  $MapSet = MapSet;
 }
 
 SetUpMap();
+
+})();