Bug 1439855 - Fast lookup for BinAST string constants, shared among parsers;r=arai
☠☠ backed out by 7e193e0b8744 ☠ ☠
authorDavid Teller <dteller@mozilla.com>
Thu, 05 Apr 2018 14:31:39 +0200
changeset 467426 16a32f1eddb24a7df4273cb00165ab973b0fd87b
parent 467425 00aa64418797b8117a67c8f1d67d388231ec9624
child 467427 f5acf9dfb9ad6bffd7a48b87f470b57efa0e2e29
push id9165
push userasasaki@mozilla.com
push dateThu, 26 Apr 2018 21:04:54 +0000
treeherdermozilla-beta@064c3804de2e [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersarai
bugs1439855
milestone61.0a1
first release with
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
last release without
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
Bug 1439855 - Fast lookup for BinAST string constants, shared among parsers;r=arai BinAST parsers need to perform frequent lookup for string values, e.g. once for each `let`, `var`, `const`, `+`, `-`, `instanceof` (string enums), as well as a number of startup lookups for string values such as "LiteralNullExpression", etc. (ast table) This patch introduces zero-copy lookup tables for both of these. These tables are shared among instances of parsers in a JSRuntime. MozReview-Commit-ID: 75BasAxLoha
js/src/frontend/BinSourceRuntimeSupport.h
js/src/frontend/BinToken.cpp
js/src/vm/Runtime.h
new file mode 100644
--- /dev/null
+++ b/js/src/frontend/BinSourceRuntimeSupport.h
@@ -0,0 +1,87 @@
+/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
+ * vim: set ts=8 sts=4 et sw=4 tw=99:
+ * This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
+
+#ifndef frontend_BinSourceSupport_h
+#define frontend_BinSourceSupport_h
+
+#include "mozilla/HashFunctions.h"
+#include "mozilla/Maybe.h"
+
+#include "jsapi.h"
+
+#include "frontend/BinToken.h"
+
+#include "js/HashTable.h"
+#include "js/Result.h"
+
+namespace js {
+
+// Support for parsing JS Binary ASTs.
+struct BinaryASTSupport {
+    using BinVariant  = js::frontend::BinVariant;
+    using BinField = js::frontend::BinField;
+    using BinKind  = js::frontend::BinKind;
+
+    // A structure designed to perform fast char* + length lookup
+    // without copies.
+    struct CharSlice {
+        const char* start_;
+        uint32_t byteLen_;
+        CharSlice(const CharSlice& other)
+            : start_(other.start_)
+            , byteLen_(other.byteLen_)
+        {  }
+        CharSlice(const char* start, const uint32_t byteLen)
+            : start_(start)
+            , byteLen_(byteLen)
+        { }
+        const char* begin() const {
+            return start_;
+        }
+        const char* end() const {
+            return start_ + byteLen_;
+        }
+#ifdef DEBUG
+        void dump() const {
+            for (auto c: *this)
+                fprintf(stderr, "%c", c);
+
+            fprintf(stderr, " (%d)", byteLen_);
+        }
+#endif // DEBUG
+
+        typedef const CharSlice Lookup;
+        static js::HashNumber hash(Lookup l) {
+            return mozilla::HashString(l.start_, l.byteLen_);
+        }
+        static bool match(const Lookup key, Lookup lookup) {
+            if (key.byteLen_ != lookup.byteLen_)
+                return false;
+            return strncmp(key.start_, lookup.start_, key.byteLen_) == 0;
+        }
+    };
+
+    JS::Result<mozilla::Maybe<BinVariant>>  binVariant(JSContext*, const CharSlice);
+    JS::Result<mozilla::Maybe<BinField>> binField(JSContext*, const CharSlice);
+    JS::Result<mozilla::Maybe<BinKind>>  binKind(JSContext*,  const CharSlice);
+
+  private:
+    // A HashMap that can be queried without copies from a CharSlice key.
+    // Initialized on first call. Keys are CharSlices into static strings.
+    using BinKindMap = js::HashMap<const CharSlice, BinKind, CharSlice, js::SystemAllocPolicy>;
+    BinKindMap binKindMap_;
+
+    using BinFieldMap = js::HashMap<const CharSlice, BinField, CharSlice, js::SystemAllocPolicy>;
+    BinFieldMap binFieldMap_;
+
+    using BinVariantMap = js::HashMap<const CharSlice, BinVariant, CharSlice, js::SystemAllocPolicy>;
+    BinVariantMap binVariantMap_;
+
+};
+
+} // namespace js
+
+#endif // frontend_BinSourceSupport_h
--- a/js/src/frontend/BinToken.cpp
+++ b/js/src/frontend/BinToken.cpp
@@ -1,35 +1,126 @@
 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
  * vim: set ts=8 sts=4 et sw=4 tw=99:
  * This Source Code Form is subject to the terms of the Mozilla Public
  * License, v. 2.0. If a copy of the MPL was not distributed with this
  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
 
 #include "frontend/BinToken.h"
 
+#include "jsapi.h"
+
+#include "mozilla/Maybe.h"
+
+#include "frontend/BinSourceRuntimeSupport.h"
+#include "frontend/TokenStream.h"
+#include "gc/Zone.h"
+
 #include <sys/types.h>
 
 namespace js {
 namespace frontend {
 
-const char* BINKIND_DESCRIPTIONS[] = {
-#define WITH_KIND(_, SPEC_NAME) #SPEC_NAME,
-    FOR_EACH_BIN_KIND(WITH_KIND)
-#undef WITH_KIND
+const BinaryASTSupport::CharSlice BINKIND_DESCRIPTIONS[] = {
+#define WITH_VARIANT(_, SPEC_NAME) BinaryASTSupport::CharSlice(SPEC_NAME, sizeof(SPEC_NAME) - 1),
+    FOR_EACH_BIN_KIND(WITH_VARIANT)
+#undef WITH_VARIANT
+};
+
+const BinaryASTSupport::CharSlice BINFIELD_DESCRIPTIONS[] = {
+#define WITH_VARIANT(_, SPEC_NAME) BinaryASTSupport::CharSlice(SPEC_NAME, sizeof(SPEC_NAME) - 1),
+    FOR_EACH_BIN_FIELD(WITH_VARIANT)
+#undef WITH_VARIANT
+};
+
+const BinaryASTSupport::CharSlice BINVARIANT_DESCRIPTIONS[] = {
+#define WITH_VARIANT(_, SPEC_NAME) BinaryASTSupport::CharSlice(SPEC_NAME, sizeof(SPEC_NAME) - 1),
+    FOR_EACH_BIN_VARIANT(WITH_VARIANT)
+#undef WITH_VARIANT
 };
 
-const char* BINFIELD_DESCRIPTIONS[] = {
-    #define WITH_FIELD(_, SPEC_NAME) #SPEC_NAME,
-        FOR_EACH_BIN_FIELD(WITH_FIELD)
-    #undef WITH_FIELD
-};
+const BinaryASTSupport::CharSlice&
+getBinKind(const BinKind& variant)
+{
+    return BINKIND_DESCRIPTIONS[static_cast<size_t>(variant)];
+}
 
-const char* describeBinKind(const BinKind& kind) {
-    return BINKIND_DESCRIPTIONS[static_cast<size_t>(kind)];
+const BinaryASTSupport::CharSlice&
+getBinVariant(const BinVariant& variant)
+{
+    return BINVARIANT_DESCRIPTIONS[static_cast<size_t>(variant)];
 }
 
-const char* describeBinField(const BinField& field) {
-    return BINFIELD_DESCRIPTIONS[static_cast<size_t>(field)];
+const BinaryASTSupport::CharSlice&
+getBinField(const BinField& variant)
+{
+    return BINFIELD_DESCRIPTIONS[static_cast<size_t>(variant)];
+}
+
+const char* describeBinKind(const BinKind& variant)
+{
+    return getBinKind(variant).begin();
+}
+
+const char* describeBinField(const BinField& variant)
+{
+    return getBinField(variant).begin();
+}
+
+const char* describeBinVariant(const BinVariant& variant)
+{
+    return getBinVariant(variant).begin();
 }
 
 } // namespace frontend
+
+
+JS::Result<mozilla::Maybe<js::frontend::BinKind>>
+BinaryASTSupport::binKind(JSContext* cx, const CharSlice key)
+{
+    if (!binKindMap_.initialized()) {
+        // Initialize lazily.
+        if (!binKindMap_.init(frontend::BINKIND_LIMIT))
+            return cx->alreadyReportedError();
+
+        for (size_t i = 0; i < frontend::BINKIND_LIMIT; ++i) {
+            const BinKind variant = static_cast<BinKind>(i);
+            const CharSlice& key = getBinKind(variant);
+            auto ptr = binKindMap_.lookupForAdd(key);
+            MOZ_ASSERT(!ptr);
+            if (!binKindMap_.add(ptr, key, variant))
+                return cx->alreadyReportedError();
+        }
+    }
+
+    auto ptr = binKindMap_.lookup(key);
+    if (!ptr)
+        return Result<mozilla::Maybe<BinKind>>(mozilla::Nothing());
+
+    return mozilla::Some(ptr->value());
+}
+
+JS::Result<mozilla::Maybe<js::frontend::BinVariant>>
+BinaryASTSupport::binVariant(JSContext* cx, const CharSlice key) {
+    if (!binVariantMap_.initialized()) {
+        // Initialize lazily.
+        if (!binVariantMap_.init(frontend::BINVARIANT_LIMIT))
+            return cx->alreadyReportedError();
+
+        for (size_t i = 0; i < frontend::BINVARIANT_LIMIT; ++i) {
+            const BinVariant variant = static_cast<BinVariant>(i);
+            const CharSlice& key = getBinVariant(variant);
+            auto ptr = binVariantMap_.lookupForAdd(key);
+            MOZ_ASSERT(!ptr);
+            if (!binVariantMap_.add(ptr, key, variant))
+                return cx->alreadyReportedError();
+        }
+    }
+
+
+    auto ptr = binVariantMap_.lookup(key);
+    if (!ptr)
+        return Result<mozilla::Maybe<BinVariant>>(mozilla::Nothing());
+
+    return mozilla::Some(ptr->value());
+}
+
 } // namespace js
--- a/js/src/vm/Runtime.h
+++ b/js/src/vm/Runtime.h
@@ -19,16 +19,17 @@
 #include "mozilla/ThreadLocal.h"
 #include "mozilla/Vector.h"
 
 #include <setjmp.h>
 
 #include "builtin/AtomicsObject.h"
 #include "builtin/intl/SharedIntlData.h"
 #include "builtin/Promise.h"
+#include "frontend/BinSourceRuntimeSupport.h"
 #include "frontend/NameCollections.h"
 #include "gc/GCRuntime.h"
 #include "gc/Tracer.h"
 #include "irregexp/RegExpStack.h"
 #include "js/Debug.h"
 #include "js/GCVector.h"
 #include "js/HashTable.h"
 #ifdef DEBUG
@@ -935,16 +936,25 @@ struct JSRuntime : public js::MallocProv
     js::RuntimeCaches& caches() { return caches_.ref(); }
 
     // List of all the live wasm::Instances in the runtime. Equal to the union
     // of all instances registered in all JSCompartments. Accessed from watchdog
     // threads for purposes of wasm::InterruptRunningCode().
     js::ExclusiveData<js::wasm::InstanceVector> wasmInstances;
 
   public:
+#if defined(JS_BUILD_BINAST)
+    js::BinaryASTSupport& binast() {
+        return binast_;
+    }
+  private:
+    js::BinaryASTSupport binast_;
+#endif // defined(JS_BUILD_BINAST)
+
+  public:
 #if defined(NIGHTLY_BUILD)
     // Support for informing the embedding of any error thrown.
     // This mechanism is designed to let the embedding
     // log/report/fail in case certain errors are thrown
     // (e.g. SyntaxError, ReferenceError or TypeError
     // in critical code).
     struct ErrorInterceptionSupport {
         ErrorInterceptionSupport()