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 $Object = global.Object;
 // var $Array = global.Array;
 
 var $Set = global.Set;
 var $Map = global.Map;
 
 
-// -------------------------------------------------------------------
-// Harmony Set
-
-function SetConstructor(iterable) {
-  if (!%_IsConstructCall()) {
-    throw MakeTypeError('constructor_not_function', ['Set']);
-  }
-
-  var iter, adder;
-
-  if (!IS_NULL_OR_UNDEFINED(iterable)) {
-    iter = GetIterator(iterable);
-    adder = this.add;
-    if (!IS_SPEC_FUNCTION(adder)) {
-      throw MakeTypeError('property_not_function', ['add', this]);
-    }
-  }
-
-  %_SetInitialize(this);
-
-  if (IS_UNDEFINED(iter)) return;
-
-  var next, done;
-  while (!(next = iter.next()).done) {
-    if (!IS_SPEC_OBJECT(next)) {
-      throw MakeTypeError('iterator_result_not_an_object', [next]);
-    }
-    %_CallFunction(this, next.value, adder);
-  }
-}
-
-
-function SetAddJS(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) {
-    key = 0;
-  }
-  return %_SetAdd(this, key);
-}
-
-
-function SetHasJS(key) {
-  if (!IS_SET(this)) {
-    throw MakeTypeError('incompatible_method_receiver',
-                        ['Set.prototype.has', this]);
-  }
-  return %_SetHas(this, key);
-}
-
-
-function SetDeleteJS(key) {
-  if (!IS_SET(this)) {
-    throw MakeTypeError('incompatible_method_receiver',
-                        ['Set.prototype.delete', this]);
-  }
-  return %_SetDelete(this, key);
-}
-
-
-function SetGetSizeJS() {
-  if (!IS_SET(this)) {
-    throw MakeTypeError('incompatible_method_receiver',
-                        ['Set.prototype.size', this]);
-  }
-  return %_SetGetSize(this);
-}
-
-
-function SetClearJS() {
-  if (!IS_SET(this)) {
-    throw MakeTypeError('incompatible_method_receiver',
-                        ['Set.prototype.clear', this]);
-  }
-  %_SetClear(this);
-}
-
-
-function SetForEach(f, receiver) {
-  if (!IS_SET(this)) {
-    throw MakeTypeError('incompatible_method_receiver',
-                        ['Set.prototype.forEach', this]);
-  }
-
-  if (!IS_SPEC_FUNCTION(f)) {
-    throw MakeTypeError('called_non_callable', [f]);
-  }
-  var needs_wrapper = false;
-  if (IS_NULL_OR_UNDEFINED(receiver)) {
-    receiver = %GetDefaultReceiver(f) || receiver;
-  } else {
-    needs_wrapper = SHOULD_CREATE_WRAPPER(f, receiver);
-  }
-
-  var iterator = new SetIterator(this, ITERATOR_KIND_VALUES);
-  var key;
-  var stepping = DEBUG_IS_ACTIVE && %DebugCallbackSupportsStepping(f);
-  var value_array = [UNDEFINED];
-  while (%SetIteratorNext(iterator, value_array)) {
-    if (stepping) %DebugPrepareStepInIfStepping(f);
-    key = value_array[0];
-    var new_receiver = needs_wrapper ? ToObject(receiver) : receiver;
-    %_CallFunction(new_receiver, key, key, this, f);
-  }
-}
-
-
-// -------------------------------------------------------------------
-
-function SetUpSet() {
-  %CheckIsBootstrapping();
-
-  %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);
-  InstallFunctions($Set.prototype, DONT_ENUM, $Array(
-    "add", SetAddJS,
-    "has", SetHasJS,
-    "delete", SetDeleteJS,
-    "clear", SetClearJS,
-    "forEach", SetForEach
-  ));
-}
-
-SetUpSet();
-
-
-// -------------------------------------------------------------------
-// Harmony Map
-
-function MapConstructor(iterable) {
-  if (!%_IsConstructCall()) {
-    throw MakeTypeError('constructor_not_function', ['Map']);
-  }
-
-  var iter, adder;
-
-  if (!IS_NULL_OR_UNDEFINED(iterable)) {
-    iter = GetIterator(iterable);
-    adder = this.set;
-    if (!IS_SPEC_FUNCTION(adder)) {
-      throw MakeTypeError('property_not_function', ['set', this]);
-    }
-  }
-
-  %_MapInitialize(this);
-
-  if (IS_UNDEFINED(iter)) return;
-
-  var next, done, nextItem;
-  while (!(next = iter.next()).done) {
-    if (!IS_SPEC_OBJECT(next)) {
-      throw MakeTypeError('iterator_result_not_an_object', [next]);
-    }
-    nextItem = next.value;
-    if (!IS_SPEC_OBJECT(nextItem)) {
-      throw MakeTypeError('iterator_value_not_an_object', [nextItem]);
-    }
-    %_CallFunction(this, nextItem[0], nextItem[1], adder);
-  }
-}
-
-
-function MapGetJS(key) {
-  if (!IS_MAP(this)) {
-    throw MakeTypeError('incompatible_method_receiver',
-                        ['Map.prototype.get', this]);
-  }
-  return %_MapGet(this, key);
-}
-
-
-function MapSetJS(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) {
-    key = 0;
-  }
-  return %_MapSet(this, key, value);
-}
-
-
-function MapHasJS(key) {
-  if (!IS_MAP(this)) {
-    throw MakeTypeError('incompatible_method_receiver',
-                        ['Map.prototype.has', this]);
-  }
-  return %_MapHas(this, key);
-}
-
-
-function MapDeleteJS(key) {
-  if (!IS_MAP(this)) {
-    throw MakeTypeError('incompatible_method_receiver',
-                        ['Map.prototype.delete', this]);
-  }
-  return %_MapDelete(this, key);
-}
-
-
-function MapGetSizeJS() {
-  if (!IS_MAP(this)) {
-    throw MakeTypeError('incompatible_method_receiver',
-                        ['Map.prototype.size', this]);
-  }
-  return %_MapGetSize(this);
-}
-
-
-function MapClearJS() {
-  if (!IS_MAP(this)) {
-    throw MakeTypeError('incompatible_method_receiver',
-                        ['Map.prototype.clear', this]);
-  }
-  %_MapClear(this);
-}
-
-
-function MapForEach(f, receiver) {
-  if (!IS_MAP(this)) {
-    throw MakeTypeError('incompatible_method_receiver',
-                        ['Map.prototype.forEach', this]);
-  }
-
-  if (!IS_SPEC_FUNCTION(f)) {
-    throw MakeTypeError('called_non_callable', [f]);
-  }
-  var needs_wrapper = false;
-  if (IS_NULL_OR_UNDEFINED(receiver)) {
-    receiver = %GetDefaultReceiver(f) || receiver;
-  } else {
-    needs_wrapper = SHOULD_CREATE_WRAPPER(f, receiver);
-  }
-
-  var iterator = new MapIterator(this, ITERATOR_KIND_ENTRIES);
-  var stepping = DEBUG_IS_ACTIVE && %DebugCallbackSupportsStepping(f);
-  var value_array = [UNDEFINED, UNDEFINED];
-  while (%MapIteratorNext(iterator, value_array)) {
-    if (stepping) %DebugPrepareStepInIfStepping(f);
-    var new_receiver = needs_wrapper ? ToObject(receiver) : receiver;
-    %_CallFunction(new_receiver, value_array[1], value_array[0], this, f);
-  }
-}
-
-
-// -------------------------------------------------------------------
-
-function SetUpMap() {
-  %CheckIsBootstrapping();
-
-  %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);
-  InstallFunctions($Map.prototype, DONT_ENUM, $Array(
-    "get", MapGetJS,
-    "set", MapSetJS,
-    "has", MapHasJS,
-    "delete", MapDeleteJS,
-    "clear", MapClearJS,
-    "forEach", MapForEach
-  ));
-}
-
-SetUpMap();
+(function() {
+  "use strict";
+
+
+  function HashToBucket(hash, numBuckets) {
+    return hash & (numBuckets - 1);
+  }
+  %SetInlineBuiltinFlag(HashToBucket);
+
+
+  function HashToEntry(table, hash, numBuckets) {
+    var bucket = HashToBucket(hash, numBuckets);
+    return %_FixedArrayGet(table, HASH_TABLE_START_INDEX + 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 = SET_CHAIN_AT(table, entry, numBuckets)) {
+      var candidate = SET_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/02/21 16:20:16]

Nice optimization to get around the NaN SameValueZero inefficiency.

[arv (Not doing code reviews), 2015/02/21 16:20:16]

Nice optimization to get around the NaN SameValueZero inefficiency.

+        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 = MAP_CHAIN_AT(table, entry, numBuckets)) {
+      var candidate = MAP_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(MapFindEntry);
+
+
+  function GetHash(key) {
+    if (%_IsSmi(key)) return %_SmiHash(key);
+    if (IS_STRING(key)) return %_StringHash(key);
+    return %GenericHash(key);
+  }
+  %SetInlineBuiltinFlag(GetHash);
+
+
+  // -------------------------------------------------------------------
+  // Harmony Set
+
+  function SetConstructor(iterable) {
+    if (!%_IsConstructCall()) {
+      throw MakeTypeError('constructor_not_function', ['Set']);
+    }
+
+    var iter, adder;
+
+    if (!IS_NULL_OR_UNDEFINED(iterable)) {
+      iter = GetIterator(iterable);
+      adder = this.add;
+      if (!IS_SPEC_FUNCTION(adder)) {
+        throw MakeTypeError('property_not_function', ['add', this]);
+      }
+    }
+
+    %_SetInitialize(this);
+
+    if (IS_UNDEFINED(iter)) return;
+
+    var next, done;
+    while (!(next = iter.next()).done) {
+      if (!IS_SPEC_OBJECT(next)) {
+        throw MakeTypeError('iterator_result_not_an_object', [next]);
+      }
+      %_CallFunction(this, next.value, adder);
+    }
+  }
+
+
+  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 (IS_NUMBER(key) && key === 0) {
+      key = 0;
+    }
+    var table = %_JSCollectionGetTable(this);
+    var numBuckets = %_FixedArrayGet(table, NUMBER_OF_BUCKETS_INDEX);
+    var hash = GetHash(key);
+    if (SetFindEntry(table, numBuckets, key, hash) !== NOT_FOUND) return this;
+
+    var nof = %_FixedArrayGet(table, NUMBER_OF_ELEMENTS_INDEX);
+    var nod = %_FixedArrayGet(table, NUMBER_OF_DELETED_ELEMENTS_INDEX);
+    var capacity = numBuckets << 1;
+    if ((nof + nod) >= capacity) {
+      // Need to grow, bail out to runtime.
+      %SetGrow(this);
+      // Re-enter...TODO(adamk) Fix this
+      return %_CallFunction(this, key, SetAdd);
+    }
+    var entry = nof + nod;
+    var index = SET_ENTRY_TO_INDEX(entry, numBuckets);
+    var bucket = HashToBucket(hash, numBuckets);
+    var chainEntry = %_FixedArrayGet(table, HASH_TABLE_START_INDEX + bucket);
+    %_FixedArraySet(table, HASH_TABLE_START_INDEX + bucket, entry);
+    %_FixedArraySet(table, index + SET_CHAIN_OFFSET, chainEntry);
+    %_FixedArraySet(table, NUMBER_OF_ELEMENTS_INDEX, nof + 1);
+    %_FixedArraySet(table, index, key);
+    return this;
+  }
+
+
+  function SetHas(key) {
+    if (!IS_SET(this)) {
+      throw MakeTypeError('incompatible_method_receiver',
+                          ['Set.prototype.has', this]);
+    }
+    var table = %_JSCollectionGetTable(this);
+    var numBuckets = %_FixedArrayGet(table, NUMBER_OF_BUCKETS_INDEX);
+    var hash = GetHash(key);
+    return SetFindEntry(table, numBuckets, key, hash) !== NOT_FOUND;
+  }
+
+
+  function SetDelete(key) {
+    if (!IS_SET(this)) {
+      throw MakeTypeError('incompatible_method_receiver',
+                          ['Set.prototype.delete', this]);
+    }
+    var table = %_JSCollectionGetTable(this);
+    var numBuckets = %_FixedArrayGet(table, NUMBER_OF_BUCKETS_INDEX);
+    var hash = GetHash(key);
+    var entry = SetFindEntry(table, numBuckets, key, hash);
+    if (entry === NOT_FOUND) return false;
+
+    var nof = %_FixedArrayGet(table, NUMBER_OF_ELEMENTS_INDEX) - 1;
+    var nod = %_FixedArrayGet(table, NUMBER_OF_DELETED_ELEMENTS_INDEX) + 1;
+    var index = SET_ENTRY_TO_INDEX(entry, numBuckets);
+    %_FixedArraySetTheHole(table, index);
+    %_FixedArraySet(table, NUMBER_OF_ELEMENTS_INDEX, nof);
+    %_FixedArraySet(table, NUMBER_OF_DELETED_ELEMENTS_INDEX, nod);
+    if (nof < (numBuckets >> 1)) %SetShrink(this);
+    return true;
+  }
+
+
+  function SetGetSize() {
+    if (!IS_SET(this)) {
+      throw MakeTypeError('incompatible_method_receiver',
+                          ['Set.prototype.size', this]);
+    }
+    var table = %_JSCollectionGetTable(this);
+    return %_FixedArrayGet(table, NUMBER_OF_ELEMENTS_INDEX);
+  }
+
+
+  function SetClearJS() {
+    if (!IS_SET(this)) {
+      throw MakeTypeError('incompatible_method_receiver',
+                          ['Set.prototype.clear', this]);
+    }
+    %_SetClear(this);
+  }
+
+
+  function SetForEach(f, receiver) {
+    if (!IS_SET(this)) {
+      throw MakeTypeError('incompatible_method_receiver',
+                          ['Set.prototype.forEach', this]);
+    }
+
+    if (!IS_SPEC_FUNCTION(f)) {
+      throw MakeTypeError('called_non_callable', [f]);
+    }
+    var needs_wrapper = false;
+    if (IS_NULL_OR_UNDEFINED(receiver)) {
+      receiver = %GetDefaultReceiver(f) || receiver;
+    } else {
+      needs_wrapper = SHOULD_CREATE_WRAPPER(f, receiver);
+    }
+
+    var iterator = new SetIterator(this, ITERATOR_KIND_VALUES);
+    var key;
+    var stepping = DEBUG_IS_ACTIVE && %DebugCallbackSupportsStepping(f);
+    var value_array = [UNDEFINED];
+    while (%SetIteratorNext(iterator, value_array)) {

[arv (Not doing code reviews), 2015/02/21 16:20:16]

This one can get much faster now that we have access to the underlying elements.
Lets revisit.

[adamk, 2015/02/23 18:43:34]

Yeah, there are definitely opportunities to speed up iterators too, but this
patch is already huge :)

+      if (stepping) %DebugPrepareStepInIfStepping(f);
+      key = value_array[0];
+      var new_receiver = needs_wrapper ? ToObject(receiver) : receiver;
+      %_CallFunction(new_receiver, key, key, this, f);
+    }
+  }
+
+
+  // -------------------------------------------------------------------
+
+  function SetUpSet() {
+    %CheckIsBootstrapping();
+
+    %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", SetGetSize);
+    InstallFunctions($Set.prototype, DONT_ENUM, $Array(
+      "add", SetAdd,
+      "has", SetHas,
+      "delete", SetDelete,
+      "clear", SetClearJS,
+      "forEach", SetForEach
+    ));
+  }
+
+  SetUpSet();
+
+
+  // -------------------------------------------------------------------
+  // Harmony Map
+
+  function MapConstructor(iterable) {
+    if (!%_IsConstructCall()) {
+      throw MakeTypeError('constructor_not_function', ['Map']);
+    }
+
+    var iter, adder;
+
+    if (!IS_NULL_OR_UNDEFINED(iterable)) {
+      iter = GetIterator(iterable);
+      adder = this.set;
+      if (!IS_SPEC_FUNCTION(adder)) {
+        throw MakeTypeError('property_not_function', ['set', this]);
+      }
+    }
+
+    %_MapInitialize(this);
+
+    if (IS_UNDEFINED(iter)) return;
+
+    var next, done, nextItem;
+    while (!(next = iter.next()).done) {
+      if (!IS_SPEC_OBJECT(next)) {
+        throw MakeTypeError('iterator_result_not_an_object', [next]);
+      }
+      nextItem = next.value;
+      if (!IS_SPEC_OBJECT(nextItem)) {
+        throw MakeTypeError('iterator_value_not_an_object', [nextItem]);
+      }
+      %_CallFunction(this, nextItem[0], nextItem[1], adder);
+    }
+  }
+
+
+  function MapGet(key) {
+    if (!IS_MAP(this)) {
+      throw MakeTypeError('incompatible_method_receiver',
+                          ['Map.prototype.get', this]);
+    }
+    var table = %_JSCollectionGetTable(this);
+    var numBuckets = %_FixedArrayGet(table, NUMBER_OF_BUCKETS_INDEX);
+    var hash = GetHash(key);
+    var entry = MapFindEntry(table, numBuckets, key, hash);
+    if (entry === NOT_FOUND) return UNDEFINED;
+    return MAP_VALUE_AT(table, entry, numBuckets);
+  }
+
+
+  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 (IS_NUMBER(key) && key === 0) {
+      key = 0;
+    }
+
+    var table = %_JSCollectionGetTable(this);
+    var numBuckets = %_FixedArrayGet(table, NUMBER_OF_BUCKETS_INDEX);
+    var hash = GetHash(key);
+    var entry = MapFindEntry(table, numBuckets, key, hash);
+    if (entry !== NOT_FOUND) {
+      var existingIndex = MAP_ENTRY_TO_INDEX(entry, numBuckets);
+      %_FixedArraySet(table, existingIndex + 1, value);
+      return this;
+    }
+
+    var nof = %_FixedArrayGet(table, NUMBER_OF_ELEMENTS_INDEX);
+    var nod = %_FixedArrayGet(table, NUMBER_OF_DELETED_ELEMENTS_INDEX);
+    var capacity = numBuckets << 1;
+    if ((nof + nod) >= capacity) {
+      // Need to grow, bail out to runtime.
+      %MapGrow(this);
+      // Re-enter...TODO(adamk) Fix this
+      return %_CallFunction(this, key, value, MapSet);
+    }
+    entry = nof + nod;
+    var index = MAP_ENTRY_TO_INDEX(entry, numBuckets);
+    var bucket = HashToBucket(hash, numBuckets);
+    var chainEntry = %_FixedArrayGet(table, HASH_TABLE_START_INDEX + bucket);
+    %_FixedArraySet(table, HASH_TABLE_START_INDEX + bucket, entry);
+    %_FixedArraySet(table, index + MAP_CHAIN_OFFSET, chainEntry);
+    %_FixedArraySet(table, NUMBER_OF_ELEMENTS_INDEX, nof + 1);
+    %_FixedArraySet(table, index, key);
+    %_FixedArraySet(table, index + 1, value);
+    return this;
+  }
+
+
+  function MapHas(key) {
+    if (!IS_MAP(this)) {
+      throw MakeTypeError('incompatible_method_receiver',
+                          ['Map.prototype.has', this]);
+    }
+    var table = %_JSCollectionGetTable(this);
+    var numBuckets = %_FixedArrayGet(table, NUMBER_OF_BUCKETS_INDEX);
+    var hash = GetHash(key);
+    return MapFindEntry(table, numBuckets, key, hash) !== NOT_FOUND;
+  }
+
+
+  function MapDelete(key) {
+    if (!IS_MAP(this)) {
+      throw MakeTypeError('incompatible_method_receiver',
+                          ['Map.prototype.delete', this]);
+    }
+    var table = %_JSCollectionGetTable(this);
+    var numBuckets = %_FixedArrayGet(table, NUMBER_OF_BUCKETS_INDEX);
+    var hash = GetHash(key);
+    var entry = MapFindEntry(table, numBuckets, key, hash);
+    if (entry === NOT_FOUND) return false;
+
+    var nof = %_FixedArrayGet(table, NUMBER_OF_ELEMENTS_INDEX) - 1;
+    var nod = %_FixedArrayGet(table, NUMBER_OF_DELETED_ELEMENTS_INDEX) + 1;
+    var index = MAP_ENTRY_TO_INDEX(entry, numBuckets);
+    %_FixedArraySetTheHole(table, index);
+    %_FixedArraySetTheHole(table, index + 1);
+    %_FixedArraySet(table, NUMBER_OF_ELEMENTS_INDEX, nof);
+    %_FixedArraySet(table, NUMBER_OF_DELETED_ELEMENTS_INDEX, nod);
+    if (nof < (numBuckets >> 1)) %MapShrink(this);
+    return true;
+  }
+
+
+  function MapGetSize() {
+    if (!IS_MAP(this)) {
+      throw MakeTypeError('incompatible_method_receiver',
+                          ['Map.prototype.size', this]);
+    }
+    var table = %_JSCollectionGetTable(this);
+    return %_FixedArrayGet(table, NUMBER_OF_ELEMENTS_INDEX);
+  }
+
+
+  function MapClearJS() {
+    if (!IS_MAP(this)) {
+      throw MakeTypeError('incompatible_method_receiver',
+                          ['Map.prototype.clear', this]);
+    }
+    %_MapClear(this);
+  }
+
+
+  function MapForEach(f, receiver) {
+    if (!IS_MAP(this)) {
+      throw MakeTypeError('incompatible_method_receiver',
+                          ['Map.prototype.forEach', this]);
+    }
+
+    if (!IS_SPEC_FUNCTION(f)) {
+      throw MakeTypeError('called_non_callable', [f]);
+    }
+    var needs_wrapper = false;
+    if (IS_NULL_OR_UNDEFINED(receiver)) {
+      receiver = %GetDefaultReceiver(f) || receiver;
+    } else {
+      needs_wrapper = SHOULD_CREATE_WRAPPER(f, receiver);
+    }
+
+    var iterator = new MapIterator(this, ITERATOR_KIND_ENTRIES);
+    var stepping = DEBUG_IS_ACTIVE && %DebugCallbackSupportsStepping(f);
+    var value_array = [UNDEFINED, UNDEFINED];
+    while (%MapIteratorNext(iterator, value_array)) {
+      if (stepping) %DebugPrepareStepInIfStepping(f);
+      var new_receiver = needs_wrapper ? ToObject(receiver) : receiver;
+      %_CallFunction(new_receiver, value_array[1], value_array[0], this, f);
+    }
+  }
+
+
+  // -------------------------------------------------------------------
+
+  function SetUpMap() {
+    %CheckIsBootstrapping();
+
+    %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", MapGetSize);
+    InstallFunctions($Map.prototype, DONT_ENUM, $Array(
+      "get", MapGet,
+      "set", MapSet,
+      "has", MapHas,
+      "delete", MapDelete,
+      "clear", MapClearJS,
+      "forEach", MapForEach
+    ));
+  }
+
+  SetUpMap();
+
+})();