Bug 1317936 part 1 - Add hash code to atoms. r=jonco,jorendorff a=gchang
authorJan de Mooij <jdemooij@mozilla.com>
Thu, 24 Nov 2016 13:39:04 +0100
changeset 352683 69b1f1cd3ae87ab25419813e20bbc0dead2a10e7
parent 352682 fbb6f22204acbf6491847eb1448f7b934c1d351d
child 352684 ea3f6566462f1ea5127d94168838153867f23385
push id6795
push userjlund@mozilla.com
push dateMon, 23 Jan 2017 14:19:46 +0000
treeherdermozilla-esr52@76101b503191 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersjonco, jorendorff, gchang
bugs1317936
milestone52.0a2
Bug 1317936 part 1 - Add hash code to atoms. r=jonco,jorendorff a=gchang
js/src/builtin/MapObject.cpp
js/src/gc/Allocator.cpp
js/src/gc/Heap.h
js/src/jit-test/tests/heap-analysis/byteSize-of-string.js
js/src/jit/VMFunctions.cpp
js/src/jsatom.cpp
js/src/jsatominlines.h
js/src/jscompartment.cpp
js/src/jscompartment.h
js/src/jsgc.cpp
js/src/jsgc.h
js/src/vm/Runtime.cpp
js/src/vm/String-inl.h
js/src/vm/String.cpp
js/src/vm/String.h
--- a/js/src/builtin/MapObject.cpp
+++ b/js/src/builtin/MapObject.cpp
@@ -59,23 +59,31 @@ HashableValue::setValue(JSContext* cx, H
         value = v;
     }
 
     MOZ_ASSERT(value.isUndefined() || value.isNull() || value.isBoolean() || value.isNumber() ||
                value.isString() || value.isSymbol() || value.isObject());
     return true;
 }
 
-HashNumber
-HashableValue::hash() const
+static HashNumber
+HashValue(const Value& v)
 {
     // HashableValue::setValue normalizes values so that the SameValue relation
     // on HashableValues is the same as the == relationship on
     // value.data.asBits.
-    return value.asRawBits();
+    if (v.isString())
+        return v.toString()->asAtom().hash();
+    return v.asRawBits();
+}
+
+HashNumber
+HashableValue::hash() const
+{
+    return HashValue(value);
 }
 
 bool
 HashableValue::operator==(const HashableValue& other) const
 {
     // Two HashableValues are equal if they have equal bits.
     bool b = (value.asRawBits() == other.value.asRawBits());
 
@@ -371,17 +379,17 @@ MapObject::mark(JSTracer* trc, JSObject*
             MarkKey(r, r.front().key, trc);
             TraceEdge(trc, &r.front().value, "value");
         }
     }
 }
 
 struct js::UnbarrieredHashPolicy {
     typedef Value Lookup;
-    static HashNumber hash(const Lookup& v) { return v.asRawBits(); }
+    static HashNumber hash(const Lookup& v) { return HashValue(v); }
     static bool match(const Value& k, const Lookup& l) { return k == l; }
     static bool isEmpty(const Value& v) { return v.isMagic(JS_HASH_KEY_EMPTY); }
     static void makeEmpty(Value* vp) { vp->setMagic(JS_HASH_KEY_EMPTY); }
 };
 
 using NurseryKeysVector = Vector<JSObject*, 0, SystemAllocPolicy>;
 
 template <typename TableObject>
--- a/js/src/gc/Allocator.cpp
+++ b/js/src/gc/Allocator.cpp
@@ -186,22 +186,25 @@ bool
 GCRuntime::checkAllocatorState(JSContext* cx, AllocKind kind)
 {
     if (allowGC) {
         if (!gcIfNeededPerAllocation(cx))
             return false;
     }
 
 #if defined(JS_GC_ZEAL) || defined(DEBUG)
-    MOZ_ASSERT_IF(rt->isAtomsCompartment(cx->compartment()),
-                  kind == AllocKind::STRING ||
-                  kind == AllocKind::FAT_INLINE_STRING ||
+    MOZ_ASSERT_IF(cx->compartment()->isAtomsCompartment(),
+                  kind == AllocKind::ATOM ||
+                  kind == AllocKind::FAT_INLINE_ATOM ||
                   kind == AllocKind::SYMBOL ||
                   kind == AllocKind::JITCODE ||
                   kind == AllocKind::SCOPE);
+    MOZ_ASSERT_IF(!cx->compartment()->isAtomsCompartment(),
+                  kind != AllocKind::ATOM &&
+                  kind != AllocKind::FAT_INLINE_ATOM);
     MOZ_ASSERT(!rt->isHeapBusy());
     MOZ_ASSERT(isAllocAllowed());
 #endif
 
     // Crash if we perform a GC action when it is not safe.
     if (allowGC && !rt->mainThread.suppressGC)
         rt->gc.verifyIsSafeToGC();
 
--- a/js/src/gc/Heap.h
+++ b/js/src/gc/Heap.h
@@ -105,16 +105,18 @@ enum class AllocKind {
     LAZY_SCRIPT,
     SHAPE,
     ACCESSOR_SHAPE,
     BASE_SHAPE,
     OBJECT_GROUP,
     FAT_INLINE_STRING,
     STRING,
     EXTERNAL_STRING,
+    FAT_INLINE_ATOM,
+    ATOM,
     SYMBOL,
     JITCODE,
     SCOPE,
     LIMIT,
     LAST = LIMIT - 1
 };
 
 // Macro to enumerate the different allocation kinds supplying information about
@@ -142,16 +144,18 @@ enum class AllocKind {
     D(LAZY_SCRIPT,         LazyScript,  js::LazyScript,    js::LazyScript) \
     D(SHAPE,               Shape,       js::Shape,         js::Shape) \
     D(ACCESSOR_SHAPE,      Shape,       js::AccessorShape, js::AccessorShape) \
     D(BASE_SHAPE,          BaseShape,   js::BaseShape,     js::BaseShape) \
     D(OBJECT_GROUP,        ObjectGroup, js::ObjectGroup,   js::ObjectGroup) \
     D(FAT_INLINE_STRING,   String,      JSFatInlineString, JSFatInlineString) \
     D(STRING,              String,      JSString,          JSString) \
     D(EXTERNAL_STRING,     String,      JSExternalString,  JSExternalString) \
+    D(FAT_INLINE_ATOM,     String,      js::FatInlineAtom, js::FatInlineAtom) \
+    D(ATOM,                String,      js::NormalAtom,    js::NormalAtom) \
     D(SYMBOL,              Symbol,      JS::Symbol,        JS::Symbol) \
     D(JITCODE,             JitCode,     js::jit::JitCode,  js::jit::JitCode) \
     D(SCOPE,               Scope,       js::Scope,         js::Scope)
 
 #define FOR_EACH_ALLOCKIND(D) \
     FOR_EACH_OBJECT_ALLOCKIND(D) \
     FOR_EACH_NONOBJECT_ALLOCKIND(D)
 
--- a/js/src/jit-test/tests/heap-analysis/byteSize-of-string.js
+++ b/js/src/jit-test/tests/heap-analysis/byteSize-of-string.js
@@ -39,46 +39,48 @@ function tByteSize(obj) {
 // representation       Latin-1   char16_t      Latin-1   char16_t    label
 // ========================================================================
 // JSExternalString            (cannot be tested in shell)            -
 // JSThinInlineString   7         3             15        7           T
 // JSFatInlineString    23        11            23        11          F
 // JSExtensibleString          - limited by available memory -        X
 // JSUndependedString          - same as JSExtensibleString -
 
+// Note that atoms are 8 bytes larger than non-atoms, to store the atom's hash code.
+
 // Latin-1
-assertEq(tByteSize(""),                                                 s(16, 24)); // T, T
-assertEq(tByteSize("1"),                                                s(16, 24)); // T, T
-assertEq(tByteSize("1234567"),                                          s(16, 24)); // T, T
-assertEq(tByteSize("12345678"),                                         s(32, 24)); // F, T
-assertEq(tByteSize("123456789.12345"),                                  s(32, 24)); // F, T
-assertEq(tByteSize("123456789.123456"),                                 s(32, 32)); // F, F
-assertEq(tByteSize("123456789.123456789.123"),                          s(32, 32)); // F, F
-assertEq(tByteSize("123456789.123456789.1234"),                         s(48, 56)); // X, X
-assertEq(tByteSize("123456789.123456789.123456789.1"),                  s(48, 56)); // X, X
-assertEq(tByteSize("123456789.123456789.123456789.12"),                 s(64, 72)); // X, X
+assertEq(tByteSize(""),                                                 s(24, 32)); // T, T
+assertEq(tByteSize("1"),                                                s(24, 32)); // T, T
+assertEq(tByteSize("1234567"),                                          s(24, 32)); // T, T
+assertEq(tByteSize("12345678"),                                         s(40, 32)); // F, T
+assertEq(tByteSize("123456789.12345"),                                  s(40, 32)); // F, T
+assertEq(tByteSize("123456789.123456"),                                 s(40, 40)); // F, F
+assertEq(tByteSize("123456789.123456789.123"),                          s(40, 40)); // F, F
+assertEq(tByteSize("123456789.123456789.1234"),                         s(56, 64)); // X, X
+assertEq(tByteSize("123456789.123456789.123456789.1"),                  s(56, 64)); // X, X
+assertEq(tByteSize("123456789.123456789.123456789.12"),                 s(72, 80)); // X, X
 
 // Inline char16_t atoms.
 // "Impassionate gods have never seen the red that is the Tatsuta River."
 //   - Ariwara no Narihira
-assertEq(tByteSize("千"),						s(16, 24)); // T, T
-assertEq(tByteSize("千早"),    						s(16, 24)); // T, T
-assertEq(tByteSize("千早ぶ"),    					s(16, 24)); // T, T
-assertEq(tByteSize("千早ぶる"),    					s(32, 24)); // F, T
-assertEq(tByteSize("千早ぶる神"),    					s(32, 24)); // F, T
-assertEq(tByteSize("千早ぶる神代"),					s(32, 24)); // F, T
-assertEq(tByteSize("千早ぶる神代も"),					s(32, 24)); // F, T
-assertEq(tByteSize("千早ぶる神代もき"),					s(32, 32)); // F, F
-assertEq(tByteSize("千早ぶる神代もきかず龍"),				s(32, 32)); // F, F
-assertEq(tByteSize("千早ぶる神代もきかず龍田"),    			s(48, 56)); // X, X
-assertEq(tByteSize("千早ぶる神代もきかず龍田川 か"),    			s(48, 56)); // X, X
-assertEq(tByteSize("千早ぶる神代もきかず龍田川 から"),    			s(64, 72)); // X, X
-assertEq(tByteSize("千早ぶる神代もきかず龍田川 からくれなゐに水く"),    	s(64, 72)); // X, X
-assertEq(tByteSize("千早ぶる神代もきかず龍田川 からくれなゐに水くく"),    	s(80, 88)); // X, X
-assertEq(tByteSize("千早ぶる神代もきかず龍田川 からくれなゐに水くくるとは"),	s(80, 88)); // X, X
+assertEq(tByteSize("千"),						s(24, 32)); // T, T
+assertEq(tByteSize("千早"),    						s(24, 32)); // T, T
+assertEq(tByteSize("千早ぶ"),    					s(24, 32)); // T, T
+assertEq(tByteSize("千早ぶる"),    					s(40, 32)); // F, T
+assertEq(tByteSize("千早ぶる神"),    					s(40, 32)); // F, T
+assertEq(tByteSize("千早ぶる神代"),					s(40, 32)); // F, T
+assertEq(tByteSize("千早ぶる神代も"),					s(40, 32)); // F, T
+assertEq(tByteSize("千早ぶる神代もき"),					s(40, 40)); // F, F
+assertEq(tByteSize("千早ぶる神代もきかず龍"),				s(40, 40)); // F, F
+assertEq(tByteSize("千早ぶる神代もきかず龍田"),    			s(56, 64)); // X, X
+assertEq(tByteSize("千早ぶる神代もきかず龍田川 か"),    			s(56, 64)); // X, X
+assertEq(tByteSize("千早ぶる神代もきかず龍田川 から"),    			s(72, 80)); // X, X
+assertEq(tByteSize("千早ぶる神代もきかず龍田川 からくれなゐに水く"),    	s(72, 80)); // X, X
+assertEq(tByteSize("千早ぶる神代もきかず龍田川 からくれなゐに水くく"),    	s(88, 96)); // X, X
+assertEq(tByteSize("千早ぶる神代もきかず龍田川 からくれなゐに水くくるとは"),	s(88, 96)); // X, X
 
 // A Latin-1 rope. This changes size when flattened.
 // "In a village of La Mancha, the name of which I have no desire to call to mind"
 //   - Miguel de Cervantes, Don Quixote
 var fragment8 = "En un lugar de la Mancha, de cuyo nombre no quiero acordarme"; // 60 characters
 var rope8 = fragment8;
 for (var i = 0; i < 10; i++) // 1024 repetitions
   rope8 = rope8 + rope8;
--- a/js/src/jit/VMFunctions.cpp
+++ b/js/src/jit/VMFunctions.cpp
@@ -1216,24 +1216,28 @@ AssertValidStringPtr(JSContext* cx, JSSt
         MOZ_ASSERT(str->zone()->isAtomsZone());
     else
         MOZ_ASSERT(str->zone() == cx->zone());
 
     MOZ_ASSERT(str->isAligned());
     MOZ_ASSERT(str->length() <= JSString::MAX_LENGTH);
 
     gc::AllocKind kind = str->getAllocKind();
-    if (str->isFatInline())
-        MOZ_ASSERT(kind == gc::AllocKind::FAT_INLINE_STRING);
-    else if (str->isExternal())
+    if (str->isFatInline()) {
+        MOZ_ASSERT(kind == gc::AllocKind::FAT_INLINE_STRING ||
+                   kind == gc::AllocKind::FAT_INLINE_ATOM);
+    } else if (str->isExternal()) {
         MOZ_ASSERT(kind == gc::AllocKind::EXTERNAL_STRING);
-    else if (str->isAtom() || str->isFlat())
+    } else if (str->isAtom()) {
+        MOZ_ASSERT(kind == gc::AllocKind::ATOM);
+    } else if (str->isFlat()) {
         MOZ_ASSERT(kind == gc::AllocKind::STRING || kind == gc::AllocKind::FAT_INLINE_STRING);
-    else
+    } else {
         MOZ_ASSERT(kind == gc::AllocKind::STRING);
+    }
 #endif
 }
 
 void
 AssertValidSymbolPtr(JSContext* cx, JS::Symbol* sym)
 {
     // We can't closely inspect symbols from another runtime.
     if (sym->runtimeFromAnyThread() != cx->runtime()) {
--- a/js/src/jsatom.cpp
+++ b/js/src/jsatom.cpp
@@ -345,17 +345,18 @@ AtomizeAndCopyChars(ExclusiveContext* cx
     if (!flat) {
         // Grudgingly forgo last-ditch GC. The alternative would be to release
         // the lock, manually GC here, and retry from the top. If you fix this,
         // please also fix or comment the similar case in Symbol::new_.
         ReportOutOfMemory(cx);
         return nullptr;
     }
 
-    JSAtom* atom = flat->morphAtomizedStringIntoAtom();
+    JSAtom* atom = flat->morphAtomizedStringIntoAtom(lookup.hash);
+    MOZ_ASSERT(atom->hash() == lookup.hash);
 
     // We have held the lock since looking up p, and the operations we've done
     // since then can't GC; therefore the atoms table has not been modified and
     // p is still valid.
     if (!atoms.add(p, AtomStateEntry(atom, bool(pin)))) {
         ReportOutOfMemory(cx); /* SystemAllocPolicy does not report OOM. */
         return nullptr;
     }
--- a/js/src/jsatominlines.h
+++ b/js/src/jsatominlines.h
@@ -151,32 +151,33 @@ IdToString(JSContext* cx, jsid id)
 
     return str->ensureFlat(cx);
 }
 
 inline
 AtomHasher::Lookup::Lookup(const JSAtom* atom)
   : isLatin1(atom->hasLatin1Chars()), length(atom->length()), atom(atom)
 {
+    hash = atom->hash();
     if (isLatin1) {
         latin1Chars = atom->latin1Chars(nogc);
-        hash = mozilla::HashString(latin1Chars, length);
+        MOZ_ASSERT(mozilla::HashString(latin1Chars, length) == hash);
     } else {
         twoByteChars = atom->twoByteChars(nogc);
-        hash = mozilla::HashString(twoByteChars, length);
+        MOZ_ASSERT(mozilla::HashString(twoByteChars, length) == hash);
     }
 }
 
 inline bool
 AtomHasher::match(const AtomStateEntry& entry, const Lookup& lookup)
 {
     JSAtom* key = entry.asPtrUnbarriered();
     if (lookup.atom)
         return lookup.atom == key;
-    if (key->length() != lookup.length)
+    if (key->length() != lookup.length || key->hash() != lookup.hash)
         return false;
 
     if (key->hasLatin1Chars()) {
         const Latin1Char* keyChars = key->latin1Chars(lookup.nogc);
         if (lookup.isLatin1)
             return mozilla::PodEqual(keyChars, lookup.latin1Chars, lookup.length);
         return EqualChars(keyChars, lookup.twoByteChars, lookup.length);
     }
--- a/js/src/jscompartment.cpp
+++ b/js/src/jscompartment.cpp
@@ -45,16 +45,17 @@ using mozilla::PodArrayZero;
 
 JSCompartment::JSCompartment(Zone* zone, const JS::CompartmentOptions& options = JS::CompartmentOptions())
   : creationOptions_(options.creationOptions()),
     behaviors_(options.behaviors()),
     zone_(zone),
     runtime_(zone->runtimeFromMainThread()),
     principals_(nullptr),
     isSystem_(false),
+    isAtomsCompartment_(false),
     isSelfHosting(false),
     marked(true),
     warnedAboutExprClosure(false),
     warnedAboutForEach(false),
 #ifdef DEBUG
     firedOnNewGlobalObject(false),
 #endif
     global_(nullptr),
--- a/js/src/jscompartment.h
+++ b/js/src/jscompartment.h
@@ -332,26 +332,35 @@ struct JSCompartment
         // to a group to which we do not belong anymore. For another thing,
         // we use `isSystem()` as part of the key to map compartments
         // to a `PerformanceGroup`, so if we do not unlink now, this will
         // be too late once we have updated `isSystem_`.
         performanceMonitoring.unlink();
         isSystem_ = isSystem;
     }
 
+    bool isAtomsCompartment() const {
+        return isAtomsCompartment_;
+    }
+    void setIsAtomsCompartment() {
+        isAtomsCompartment_ = true;
+    }
+
     // Used to approximate non-content code when reporting telemetry.
     inline bool isProbablySystemOrAddonCode() const {
         if (creationOptions_.addonIdOrNull())
             return true;
 
         return isSystem_;
     }
   private:
     JSPrincipals*                principals_;
     bool                         isSystem_;
+    bool                         isAtomsCompartment_;
+
   public:
     bool                         isSelfHosting;
     bool                         marked;
     bool                         warnedAboutExprClosure;
     bool                         warnedAboutForEach;
 
 #ifdef DEBUG
     bool                         firedOnNewGlobalObject;
--- a/js/src/jsgc.cpp
+++ b/js/src/jsgc.cpp
@@ -360,16 +360,18 @@ static const FinalizePhase BackgroundFin
         gcstats::PHASE_SWEEP_SCOPE, {
             AllocKind::SCOPE
         }
     },
     {
         gcstats::PHASE_SWEEP_STRING, {
             AllocKind::FAT_INLINE_STRING,
             AllocKind::STRING,
+            AllocKind::FAT_INLINE_ATOM,
+            AllocKind::ATOM,
             AllocKind::SYMBOL
         }
     },
     {
         gcstats::PHASE_SWEEP_SHAPE, {
             AllocKind::SHAPE,
             AllocKind::ACCESSOR_SHAPE,
             AllocKind::BASE_SHAPE,
@@ -1775,17 +1777,19 @@ static const AllocKind AllocKindsToReloc
     AllocKind::SCRIPT,
     AllocKind::LAZY_SCRIPT,
     AllocKind::SCOPE,
     AllocKind::SHAPE,
     AllocKind::ACCESSOR_SHAPE,
     AllocKind::BASE_SHAPE,
     AllocKind::FAT_INLINE_STRING,
     AllocKind::STRING,
-    AllocKind::EXTERNAL_STRING
+    AllocKind::EXTERNAL_STRING,
+    AllocKind::FAT_INLINE_ATOM,
+    AllocKind::ATOM
 };
 
 Arena*
 ArenaList::removeRemainingArenas(Arena** arenap)
 {
     // This is only ever called to remove arenas that are after the cursor, so
     // we don't need to update it.
 #ifdef DEBUG
--- a/js/src/jsgc.h
+++ b/js/src/jsgc.h
@@ -110,16 +110,18 @@ IsNurseryAllocable(AllocKind kind)
         false,     /* AllocKind::LAZY_SCRIPT */
         false,     /* AllocKind::SHAPE */
         false,     /* AllocKind::ACCESSOR_SHAPE */
         false,     /* AllocKind::BASE_SHAPE */
         false,     /* AllocKind::OBJECT_GROUP */
         false,     /* AllocKind::FAT_INLINE_STRING */
         false,     /* AllocKind::STRING */
         false,     /* AllocKind::EXTERNAL_STRING */
+        false,     /* AllocKind::FAT_INLINE_ATOM */
+        false,     /* AllocKind::ATOM */
         false,     /* AllocKind::SYMBOL */
         false,     /* AllocKind::JITCODE */
         false,     /* AllocKind::SCOPE */
     };
     JS_STATIC_ASSERT(JS_ARRAY_LENGTH(map) == size_t(AllocKind::LIMIT));
     return map[size_t(kind)];
 }
 
@@ -146,16 +148,18 @@ IsBackgroundFinalized(AllocKind kind)
         true,      /* AllocKind::LAZY_SCRIPT */
         true,      /* AllocKind::SHAPE */
         true,      /* AllocKind::ACCESSOR_SHAPE */
         true,      /* AllocKind::BASE_SHAPE */
         true,      /* AllocKind::OBJECT_GROUP */
         true,      /* AllocKind::FAT_INLINE_STRING */
         true,      /* AllocKind::STRING */
         false,     /* AllocKind::EXTERNAL_STRING */
+        true,      /* AllocKind::FAT_INLINE_ATOM */
+        true,      /* AllocKind::ATOM */
         true,      /* AllocKind::SYMBOL */
         false,     /* AllocKind::JITCODE */
         true,      /* AllocKind::SCOPE */
     };
     JS_STATIC_ASSERT(JS_ARRAY_LENGTH(map) == size_t(AllocKind::LIMIT));
     return map[size_t(kind)];
 }
 
--- a/js/src/vm/Runtime.cpp
+++ b/js/src/vm/Runtime.cpp
@@ -311,16 +311,17 @@ JSRuntime::init(uint32_t maxbytes, uint3
         return false;
 
     if (!gc.zones.append(atomsZone.get()))
         return false;
     if (!atomsZone->compartments.append(atomsCompartment.get()))
         return false;
 
     atomsCompartment->setIsSystem(true);
+    atomsCompartment->setIsAtomsCompartment();
 
     atomsZone.forget();
     this->atomsCompartment_ = atomsCompartment.forget();
 
     if (!symbolRegistry_.init())
         return false;
 
     if (!scriptDataTable_.init())
--- a/js/src/vm/String-inl.h
+++ b/js/src/vm/String-inl.h
@@ -8,16 +8,17 @@
 #define vm_String_inl_h
 
 #include "vm/String.h"
 
 #include "mozilla/PodOperations.h"
 #include "mozilla/Range.h"
 
 #include "jscntxt.h"
+#include "jscompartment.h"
 
 #include "gc/Allocator.h"
 #include "gc/Marking.h"
 
 namespace js {
 
 // Allocate a thin inline string if possible, and a fat inline string if not.
 template <AllowGC allowGC, typename CharT>
@@ -215,17 +216,21 @@ template <js::AllowGC allowGC, typename 
 MOZ_ALWAYS_INLINE JSFlatString*
 JSFlatString::new_(js::ExclusiveContext* cx, const CharT* chars, size_t length)
 {
     MOZ_ASSERT(chars[length] == CharT(0));
 
     if (!validateLength(cx, length))
         return nullptr;
 
-    JSFlatString* str = static_cast<JSFlatString*>(js::Allocate<JSString, allowGC>(cx));
+    JSFlatString* str;
+    if (cx->compartment()->isAtomsCompartment())
+        str = js::Allocate<js::NormalAtom, allowGC>(cx);
+    else
+        str = static_cast<JSFlatString*>(js::Allocate<JSString, allowGC>(cx));
     if (!str)
         return nullptr;
 
     str->init(chars, length);
     return str;
 }
 
 inline js::PropertyName*
@@ -242,23 +247,29 @@ JSFlatString::toPropertyName(JSContext* 
         return nullptr;
     return atom->asPropertyName();
 }
 
 template <js::AllowGC allowGC>
 MOZ_ALWAYS_INLINE JSThinInlineString*
 JSThinInlineString::new_(js::ExclusiveContext* cx)
 {
+    if (cx->compartment()->isAtomsCompartment())
+        return (JSThinInlineString*)(js::Allocate<js::NormalAtom, allowGC>(cx));
+
     return static_cast<JSThinInlineString*>(js::Allocate<JSString, allowGC>(cx));
 }
 
 template <js::AllowGC allowGC>
 MOZ_ALWAYS_INLINE JSFatInlineString*
 JSFatInlineString::new_(js::ExclusiveContext* cx)
 {
+    if (cx->compartment()->isAtomsCompartment())
+        return (JSFatInlineString*)(js::Allocate<js::FatInlineAtom, allowGC>(cx));
+
     return js::Allocate<JSFatInlineString, allowGC>(cx);
 }
 
 template<>
 MOZ_ALWAYS_INLINE JS::Latin1Char*
 JSThinInlineString::init<JS::Latin1Char>(size_t length)
 {
     MOZ_ASSERT(lengthFits<JS::Latin1Char>(length));
@@ -346,27 +357,29 @@ js::StaticStrings::getLength2(char16_t c
     return length2StaticTable[index];
 }
 
 MOZ_ALWAYS_INLINE void
 JSString::finalize(js::FreeOp* fop)
 {
     /* FatInline strings are in a different arena. */
     MOZ_ASSERT(getAllocKind() != js::gc::AllocKind::FAT_INLINE_STRING);
+    MOZ_ASSERT(getAllocKind() != js::gc::AllocKind::FAT_INLINE_ATOM);
 
     if (isFlat())
         asFlat().finalize(fop);
     else
         MOZ_ASSERT(isDependent() || isRope());
 }
 
 inline void
 JSFlatString::finalize(js::FreeOp* fop)
 {
     MOZ_ASSERT(getAllocKind() != js::gc::AllocKind::FAT_INLINE_STRING);
+    MOZ_ASSERT(getAllocKind() != js::gc::AllocKind::FAT_INLINE_ATOM);
 
     if (!isInline())
         fop->free_(nonInlineCharsRaw());
 }
 
 inline void
 JSFatInlineString::finalize(js::FreeOp* fop)
 {
@@ -376,16 +389,18 @@ JSFatInlineString::finalize(js::FreeOp* 
         fop->free_(nonInlineCharsRaw());
 }
 
 inline void
 JSAtom::finalize(js::FreeOp* fop)
 {
     MOZ_ASSERT(JSString::isAtom());
     MOZ_ASSERT(JSString::isFlat());
+    MOZ_ASSERT(getAllocKind() == js::gc::AllocKind::ATOM ||
+               getAllocKind() == js::gc::AllocKind::FAT_INLINE_ATOM);
 
     if (!isInline())
         fop->free_(nonInlineCharsRaw());
 }
 
 inline void
 JSExternalString::finalize(js::FreeOp* fop)
 {
--- a/js/src/vm/String.cpp
+++ b/js/src/vm/String.cpp
@@ -68,18 +68,22 @@ JSString::sizeOfExcludingThis(mozilla::M
     return flat.hasLatin1Chars()
            ? mallocSizeOf(flat.rawLatin1Chars())
            : mallocSizeOf(flat.rawTwoByteChars());
 }
 
 JS::ubi::Node::Size
 JS::ubi::Concrete<JSString>::size(mozilla::MallocSizeOf mallocSizeOf) const
 {
-    JSString &str = get();
-    size_t size = str.isFatInline() ? sizeof(JSFatInlineString) : sizeof(JSString);
+    JSString& str = get();
+    size_t size;
+    if (str.isAtom())
+        size = str.isFatInline() ? sizeof(js::FatInlineAtom) : sizeof(js::NormalAtom);
+    else
+        size = str.isFatInline() ? sizeof(JSFatInlineString) : sizeof(JSString);
 
     // We can't use mallocSizeof on things in the nursery. At the moment,
     // strings are never in the nursery, but that may change.
     MOZ_ASSERT(!IsInsideNursery(&str));
     size += str.sizeOfExcludingThis(mallocSizeOf);
 
     return size;
 }
@@ -814,25 +818,27 @@ StaticStrings::init(JSContext* cx)
 
     using Latin1Range = mozilla::Range<const Latin1Char>;
 
     for (uint32_t i = 0; i < UNIT_STATIC_LIMIT; i++) {
         Latin1Char buffer[] = { Latin1Char(i), '\0' };
         JSFlatString* s = NewInlineString<NoGC>(cx, Latin1Range(buffer, 1));
         if (!s)
             return false;
-        unitStaticTable[i] = s->morphAtomizedStringIntoPermanentAtom();
+        HashNumber hash = mozilla::HashString(buffer, 1);
+        unitStaticTable[i] = s->morphAtomizedStringIntoPermanentAtom(hash);
     }
 
     for (uint32_t i = 0; i < NUM_SMALL_CHARS * NUM_SMALL_CHARS; i++) {
         Latin1Char buffer[] = { FROM_SMALL_CHAR(i >> 6), FROM_SMALL_CHAR(i & 0x3F), '\0' };
         JSFlatString* s = NewInlineString<NoGC>(cx, Latin1Range(buffer, 2));
         if (!s)
             return false;
-        length2StaticTable[i] = s->morphAtomizedStringIntoPermanentAtom();
+        HashNumber hash = mozilla::HashString(buffer, 2);
+        length2StaticTable[i] = s->morphAtomizedStringIntoPermanentAtom(hash);
     }
 
     for (uint32_t i = 0; i < INT_STATIC_LIMIT; i++) {
         if (i < 10) {
             intStaticTable[i] = unitStaticTable[i + '0'];
         } else if (i < 100) {
             size_t index = ((size_t)TO_SMALL_CHAR((i / 10) + '0') << 6) +
                 TO_SMALL_CHAR((i % 10) + '0');
@@ -840,17 +846,18 @@ StaticStrings::init(JSContext* cx)
         } else {
             Latin1Char buffer[] = { Latin1Char('0' + (i / 100)),
                                     Latin1Char('0' + ((i / 10) % 10)),
                                     Latin1Char('0' + (i % 10)),
                                     '\0' };
             JSFlatString* s = NewInlineString<NoGC>(cx, Latin1Range(buffer, 3));
             if (!s)
                 return false;
-            intStaticTable[i] = s->morphAtomizedStringIntoPermanentAtom();
+            HashNumber hash = mozilla::HashString(buffer, 3);
+            intStaticTable[i] = s->morphAtomizedStringIntoPermanentAtom(hash);
         }
     }
 
     return true;
 }
 
 void
 StaticStrings::trace(JSTracer* trc)
@@ -1314,17 +1321,16 @@ template JSFlatString*
 NewStringCopyN<NoGC>(ExclusiveContext* cx, const char16_t* s, size_t n);
 
 template JSFlatString*
 NewStringCopyN<CanGC>(ExclusiveContext* cx, const Latin1Char* s, size_t n);
 
 template JSFlatString*
 NewStringCopyN<NoGC>(ExclusiveContext* cx, const Latin1Char* s, size_t n);
 
-
 template <js::AllowGC allowGC>
 JSFlatString*
 NewStringCopyUTF8N(JSContext* cx, const JS::UTF8Chars utf8)
 {
     JS::SmallestEncoding encoding = JS::FindSmallestEncoding(utf8);
     if (encoding == JS::SmallestEncoding::ASCII)
         return NewStringCopyN<allowGC>(cx, utf8.begin().get(), utf8.length());
 
--- a/js/src/vm/String.h
+++ b/js/src/vm/String.h
@@ -118,32 +118,35 @@ static const size_t UINT32_CHAR_BUFFER_L
  *  |  +-- JSUndependedString   original dependent base / -
  *  |  |
  *  |  +-- JSInlineString (abstract)    - / chars stored in header
  *  |      |
  *  |      +-- JSThinInlineString       - / header is normal
  *  |      |
  *  |      +-- JSFatInlineString        - / header is fat
  *  |
- * JSAtom                       - / string equality === pointer equality
+ * JSAtom (abstract)            - / string equality === pointer equality
+ *  |  |
+ *  |  +-- js::NormalAtom       - JSFlatString + atom hash code
+ *  |  |
+ *  |  +-- js::FatInlineAtom    - JSFatInlineString + atom hash code
  *  |
  * js::PropertyName             - / chars don't contain an index (uint32_t)
  *
  * Classes marked with (abstract) above are not literally C++ Abstract Base
  * Classes (since there are no virtual functions, pure or not, in this
  * hierarchy), but have the same meaning: there are no strings with this type as
  * its most-derived type.
  *
  * Atoms can additionally be permanent, i.e. unable to be collected, and can
  * be combined with other string types to create additional most-derived types
  * that satisfy the invariants of more than one of the abovementioned
- * most-derived types:
- *  - InlineAtom     = JSInlineString     + JSAtom (atom with inline chars, abstract)
- *  - ThinInlineAtom = JSThinInlineString + JSAtom (atom with inline chars)
- *  - FatInlineAtom  = JSFatInlineString  + JSAtom (atom with (more) inline chars)
+ * most-derived types. Furthermore, each atom stores a hash number (based on its
+ * chars). This hash number is used as key in the atoms table and when the atom
+ * is used as key in a JS Map/Set.
  *
  * Derived string types can be queried from ancestor types via isX() and
  * retrieved with asX() debug-only-checked casts.
  *
  * The ensureX() operations mutate 'this' in place to effectively the type to be
  * at least X (e.g., ensureLinear will change a JSRope to be a JSFlatString).
  */
 
@@ -764,24 +767,18 @@ class JSFlatString : public JSLinearStri
      * this method.
      */
     inline js::PropertyName* toPropertyName(JSContext* cx);
 
     /*
      * Once a JSFlatString sub-class has been added to the atom state, this
      * operation changes the string to the JSAtom type, in place.
      */
-    MOZ_ALWAYS_INLINE JSAtom* morphAtomizedStringIntoAtom() {
-        d.u1.flags |= ATOM_BIT;
-        return &asAtom();
-    }
-    MOZ_ALWAYS_INLINE JSAtom* morphAtomizedStringIntoPermanentAtom() {
-        d.u1.flags |= PERMANENT_ATOM_MASK;
-        return &asAtom();
-    }
+    MOZ_ALWAYS_INLINE JSAtom* morphAtomizedStringIntoAtom(js::HashNumber hash);
+    MOZ_ALWAYS_INLINE JSAtom* morphAtomizedStringIntoPermanentAtom(js::HashNumber hash);
 
     inline void finalize(js::FreeOp* fop);
 
 #ifdef DEBUG
     void dumpRepresentation(FILE* fp, int indent) const;
 #endif
 };
 
@@ -983,27 +980,107 @@ class JSAtom : public JSFlatString
     }
 
     // Transform this atom into a permanent atom. This is only done during
     // initialization of the runtime.
     MOZ_ALWAYS_INLINE void morphIntoPermanentAtom() {
         d.u1.flags |= PERMANENT_ATOM_MASK;
     }
 
+    inline js::HashNumber hash() const;
+    inline void initHash(js::HashNumber hash);
+
 #ifdef DEBUG
     void dump(FILE* fp);
     void dump();
 #endif
 };
 
 static_assert(sizeof(JSAtom) == sizeof(JSString),
               "string subclasses must be binary-compatible with JSString");
 
 namespace js {
 
+class NormalAtom : public JSAtom
+{
+  protected: // Silence Clang unused-field warning.
+    HashNumber hash_;
+    uint32_t padding_; // Ensure the size is a multiple of gc::CellSize.
+
+  public:
+    HashNumber hash() const {
+        return hash_;
+    }
+    void initHash(HashNumber hash) {
+        hash_ = hash;
+    }
+};
+
+static_assert(sizeof(NormalAtom) == sizeof(JSString) + sizeof(uint64_t),
+              "NormalAtom must have size of a string + HashNumber, "
+              "aligned to gc::CellSize");
+
+class FatInlineAtom : public JSAtom
+{
+  protected: // Silence Clang unused-field warning.
+    char inlineStorage_[sizeof(JSFatInlineString) - sizeof(JSString)];
+    HashNumber hash_;
+    uint32_t padding_; // Ensure the size is a multiple of gc::CellSize.
+
+  public:
+    HashNumber hash() const {
+        return hash_;
+    }
+    void initHash(HashNumber hash) {
+        hash_ = hash;
+    }
+};
+
+static_assert(sizeof(FatInlineAtom) == sizeof(JSFatInlineString) + sizeof(uint64_t),
+              "FatInlineAtom must have size of a fat inline string + HashNumber, "
+              "aligned to gc::CellSize");
+
+} // namespace js
+
+inline js::HashNumber
+JSAtom::hash() const
+{
+    if (isFatInline())
+        return static_cast<const js::FatInlineAtom*>(this)->hash();
+    return static_cast<const js::NormalAtom*>(this)->hash();
+}
+
+inline void
+JSAtom::initHash(js::HashNumber hash)
+{
+    if (isFatInline())
+        return static_cast<js::FatInlineAtom*>(this)->initHash(hash);
+    return static_cast<js::NormalAtom*>(this)->initHash(hash);
+}
+
+MOZ_ALWAYS_INLINE JSAtom*
+JSFlatString::morphAtomizedStringIntoAtom(js::HashNumber hash)
+{
+    d.u1.flags |= ATOM_BIT;
+    JSAtom* atom = &asAtom();
+    atom->initHash(hash);
+    return atom;
+}
+
+MOZ_ALWAYS_INLINE JSAtom*
+JSFlatString::morphAtomizedStringIntoPermanentAtom(js::HashNumber hash)
+{
+    d.u1.flags |= PERMANENT_ATOM_MASK;
+    JSAtom* atom = &asAtom();
+    atom->initHash(hash);
+    return atom;
+}
+
+namespace js {
+
 class StaticStrings
 {
   private:
     /* Bigger chars cannot be in a length-2 string. */
     static const size_t SMALL_CHAR_LIMIT    = 128U;
     static const size_t NUM_SMALL_CHARS     = 64U;
 
     JSAtom* length2StaticTable[NUM_SMALL_CHARS * NUM_SMALL_CHARS];