Move hash code from hidden string to a private symbol

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.
 
+var $gethash;

[adamk, 2015/05/21 19:11:32]

Rename to $getHash

[Erik Corry, 2015/05/22 06:20:24]

Done.

+var $getexistinghash;

[adamk, 2015/05/21 19:11:32]

and $getExistingHash

[Erik Corry, 2015/05/22 06:20:24]

Done.

+
 (function(global, shared, exports) {
 
 "use strict";
 
 %CheckIsBootstrapping();
 
 var GlobalMap = global.Map;
 var GlobalObject = global.Object;
 var GlobalSet = global.Set;
 
 // -------------------------------------------------------------------
 
 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 entry = HashToEntry(table, hash, numBuckets);
+  if (entry === NOT_FOUND) return entry;
+  var candidate = ORDERED_HASH_SET_KEY_AT(table, entry, numBuckets);
+  if (key === candidate) return entry;
   var keyIsNaN = $numberIsNaN(key);
-  for (var entry = HashToEntry(table, hash, numBuckets);

[adamk, 2015/05/21 19:11:32]

Why did this get rewritten as a while loop? From my inspection the only
difference I see is extra calls to KEY_AT and extra comparisons.

[Erik Corry, 2015/05/21 20:19:01]

The idea is to avoid testing the key for Nan-ness in the case where the first
probe fails or hits.

-       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;
-    }
+  while (true) {
     if (keyIsNaN && $numberIsNaN(candidate)) {
       return entry;
     }
+    entry = ORDERED_HASH_SET_CHAIN_AT(table, entry, numBuckets);
+    if (entry === NOT_FOUND) return entry;
+    candidate = ORDERED_HASH_SET_KEY_AT(table, entry, numBuckets);
+    if (key === candidate) return entry;
   }
   return NOT_FOUND;
 }
 %SetInlineBuiltinFlag(SetFindEntry);
 
 
 function MapFindEntry(table, numBuckets, key, hash) {
+  var entry = HashToEntry(table, hash, numBuckets);
+  if (entry === NOT_FOUND) return entry;
+  var candidate = ORDERED_HASH_MAP_KEY_AT(table, entry, numBuckets);
+  if (key === candidate) return entry;
   var keyIsNaN = $numberIsNaN(key);
-  for (var entry = HashToEntry(table, hash, numBuckets);

[adamk, 2015/05/21 19:11:32]

Same question down here.

[Erik Corry, 2015/05/21 20:19:01]

Same answer :-)

-       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;
-    }
+  while (true) {
     if (keyIsNaN && $numberIsNaN(candidate)) {
       return entry;
     }
+    entry = ORDERED_HASH_MAP_CHAIN_AT(table, entry, numBuckets);
+    if (entry === NOT_FOUND) return entry;
+    candidate = ORDERED_HASH_MAP_KEY_AT(table, entry, numBuckets);
+    if (key === candidate) 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;
+  return hash & 0x3fffffff;

[adamk, 2015/05/21 19:11:32]

Why the extra &? This used to be equivalent to ComputeIntegerHash() in utils.h.

[Erik Corry, 2015/05/22 06:20:24]

To make sure it's always a Smi.  I changed ComputeIntegerHash to match.

 }
 %SetInlineBuiltinFlag(ComputeIntegerHash);
 
+var hash_code_symbol = GLOBAL_PRIVATE("hash_code_symbol");

[adamk, 2015/05/21 19:11:32]

Please use JS style here ("hashCodeSymbol").

[Erik Corry, 2015/05/22 06:20:24]

Done.

 
-function GetHash(key) {
+function GetExistingHash(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 */;
     }
+  } else if (IS_SPEC_OBJECT(key) && !%_IsJSProxy(key) && !IS_GLOBAL(key)) {
+    var hash = GET_PRIVATE(key, hash_code_symbol);
+    return hash;
   }
   return %GenericHash(key);

[adamk, 2015/05/21 19:11:32]

%GenericHash calls GetOrCreateHash, which seems wrong for this case. Maybe add a
new runtime function that calls GetHash() instead (though maybe we don't care
much about this case).

[Erik Corry, 2015/05/21 20:19:02]

I think we don't care much about this case, it's only proxies.  And symbols, but
they should be born with a hash code (and it would be nice to handle them above
in the string clause, which would then be a name clause).

 }
+%SetInlineBuiltinFlag(GetExistingHash);
+
+
+function GetHash(key) {
+  var hash = GetExistingHash(key);
+  if (IS_UNDEFINED(hash)) {
+    if (IS_GLOBAL(key)) {

[adamk, 2015/05/21 19:11:32]

I think this branch is currently unreachable due to the above.

[Erik Corry, 2015/05/21 20:19:02]

Good point.

I think a better solution would be for global objects to be born with a hash
code, and it should always be 1 (or 42).  That way we don't have to keep track
of them specially, and that would give us back our 5% on the weak maps.

+      return %GenericHash(key);
+    }
+    hash = $intrandom() | 0;
+    if (hash === 0) hash = 1;
+    SET_PRIVATE(key, hash_code_symbol, hash);
+  }
+  return hash;
+}
 %SetInlineBuiltinFlag(GetHash);
 
 
 // -------------------------------------------------------------------
 // Harmony Set
 
 function SetConstructor(iterable) {
   if (!%_IsConstructCall()) {
     throw MakeTypeError(kConstructorNotFunction, "Set");
   }
@@ skipping 52 matching lines @@
   return this;
 }
 
 
 function SetHas(key) {
   if (!IS_SET(this)) {
     throw MakeTypeError(kIncompatibleMethodReceiver, 'Set.prototype.has', this);
   }
   var table = %_JSCollectionGetTable(this);
   var numBuckets = ORDERED_HASH_TABLE_BUCKET_COUNT(table);
-  var hash = GetHash(key);
+  var hash = GetExistingHash(key);
+  if (IS_UNDEFINED(hash)) return false;
   return SetFindEntry(table, numBuckets, key, hash) !== NOT_FOUND;
 }
 
 
 function SetDelete(key) {
   if (!IS_SET(this)) {
     throw MakeTypeError(kIncompatibleMethodReceiver,
                         'Set.prototype.delete', this);
   }
   var table = %_JSCollectionGetTable(this);
   var numBuckets = ORDERED_HASH_TABLE_BUCKET_COUNT(table);
-  var hash = GetHash(key);
+  var hash = GetExistingHash(key);
+  if (IS_UNDEFINED(hash)) return false;
   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);
@@ skipping 94 matching lines @@
 }
 
 
 function MapGet(key) {
   if (!IS_MAP(this)) {
     throw MakeTypeError(kIncompatibleMethodReceiver,
                         'Map.prototype.get', this);
   }
   var table = %_JSCollectionGetTable(this);
   var numBuckets = ORDERED_HASH_TABLE_BUCKET_COUNT(table);
-  var hash = GetHash(key);
+  var hash = GetExistingHash(key);
+  if (IS_UNDEFINED(hash)) return UNDEFINED;
   var entry = MapFindEntry(table, numBuckets, key, hash);
   if (entry === NOT_FOUND) return UNDEFINED;
   return ORDERED_HASH_MAP_VALUE_AT(table, entry, numBuckets);
 }
 
 
 function MapSet(key, value) {
   if (!IS_MAP(this)) {
     throw MakeTypeError(kIncompatibleMethodReceiver,
                         'Map.prototype.set', this);
@@ skipping 134 matching lines @@
 $installGetter(GlobalMap.prototype, "size", MapGetSize);
 $installFunctions(GlobalMap.prototype, DONT_ENUM, [
   "get", MapGet,
   "set", MapSet,
   "has", MapHas,
   "delete", MapDelete,
   "clear", MapClearJS,
   "forEach", MapForEach
 ]);
 
+// Expose to the global scope.
+$gethash = GetHash;
+$getexistinghash = GetExistingHash;
+
 })