Bug 883154 - Add runtime wide cache for compiled lazy scripts, r=billm.
authorBrian Hackett <bhackett1024@gmail.com>
Sun, 23 Jun 2013 20:37:42 -0600
changeset 136215 a0dfe6abef73
parent 136214 9661a68f0bff
child 136216 d3f627a6273e
push id24867
push useremorley@mozilla.com
push dateMon, 24 Jun 2013 12:35:17 +0000
treeherdermozilla-central@7edda78eca8b [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersbillm
bugs883154
milestone24.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 883154 - Add runtime wide cache for compiled lazy scripts, r=billm.
js/src/ds/FixedSizeHash.h
js/src/frontend/BytecodeEmitter.cpp
js/src/jscntxt.h
js/src/jsfun.cpp
js/src/jsscript.cpp
js/src/jsscript.h
new file mode 100644
--- /dev/null
+++ b/js/src/ds/FixedSizeHash.h
@@ -0,0 +1,127 @@
+/* -*- 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 jsfixedsizehash_h_
+#define jsfixedsizehash_h_
+
+#include "LifoAlloc.h"
+
+namespace js {
+
+/*
+ * Class representing a hash set with fixed capacity, with newer entries
+ * evicting older entries. Each entry has several hashes and can be stored in
+ * different buckets, with the choice of which to evict on insertion being
+ * managed via LRU. For tables with a relatively small size, using different
+ * hashes increases utilization and makes it less likely that entries will keep
+ * evicting each other due to wanting to use the same bucket.
+ *
+ * T indicates the type of hash elements, HashPolicy must have the following
+ * contents:
+ *
+ * Lookup - As for HashMap / HashSet.
+ *
+ * bool match(T, Lookup) - As for HashMap / HashSet.
+ *
+ * NumHashes - Number of different hashes generated for each entry.
+ *
+ * void hash(Lookup, HashNumber[NumHashes]) - Compute all hashes for an entry.
+ *
+ * void clear(T *) - Clear an entry, such that isCleared() holds afterwards.
+ *
+ * bool isCleared(T) - Test whether an entry has been cleared.
+ */
+template <class T, class HashPolicy, size_t Capacity>
+class FixedSizeHashSet
+{
+    T entries[Capacity];
+    uint32_t lastOperations[Capacity];
+    uint32_t numOperations;
+
+    static const size_t NumHashes = HashPolicy::NumHashes;
+
+  public:
+    typedef typename HashPolicy::Lookup Lookup;
+
+    FixedSizeHashSet()
+      : entries(), lastOperations(), numOperations(0)
+    {
+        JS_STATIC_ASSERT(Capacity > 0);
+        JS_ASSERT(HashPolicy::isCleared(entries[0]));
+    }
+
+    bool lookup(const Lookup &lookup, T *pentry)
+    {
+        size_t bucket;
+        if (lookupReference(lookup, &bucket)) {
+            *pentry = entries[bucket];
+            lastOperations[bucket] = numOperations++;
+            return true;
+        }
+        return false;
+    }
+
+    void insert(const Lookup &lookup, const T &entry)
+    {
+        size_t buckets[NumHashes];
+        getBuckets(lookup, buckets);
+
+        size_t min = buckets[0];
+        for (size_t i = 0; i < NumHashes; i++) {
+            const T &entry = entries[buckets[i]];
+            if (HashPolicy::isCleared(entry)) {
+                entries[buckets[i]] = entry;
+                lastOperations[buckets[i]] = numOperations++;
+                return;
+            }
+            if (i && lastOperations[min] > lastOperations[buckets[i]])
+                min = buckets[i];
+        }
+
+        entries[min] = entry;
+        lastOperations[min] = numOperations++;
+    }
+
+    template <typename S>
+    void remove(const S &s)
+    {
+        size_t bucket;
+        if (lookupReference(s, &bucket))
+            HashPolicy::clear(&entries[bucket]);
+    }
+
+  private:
+    template <typename S>
+    bool lookupReference(const S &s, size_t *pbucket)
+    {
+        size_t buckets[NumHashes];
+        getBuckets(s, buckets);
+
+        for (size_t i = 0; i < NumHashes; i++) {
+            const T &entry = entries[buckets[i]];
+            if (!HashPolicy::isCleared(entry) && HashPolicy::match(entry, s)) {
+                *pbucket = buckets[i];
+                return true;
+            }
+        }
+
+        return false;
+    }
+
+    template <typename S>
+    void getBuckets(const S &s, size_t buckets[NumHashes])
+    {
+        HashNumber hashes[NumHashes];
+        HashPolicy::hash(s, hashes);
+
+        for (size_t i = 0; i < NumHashes; i++)
+            buckets[i] = hashes[i] % Capacity;
+    }
+};
+
+}  /* namespace js */
+
+#endif /* jsfixedsizehash_h_ */
--- a/js/src/frontend/BytecodeEmitter.cpp
+++ b/js/src/frontend/BytecodeEmitter.cpp
@@ -2568,17 +2568,17 @@ frontend::EmitFunctionScript(JSContext *
      * shenanigans.
      */
     bool runOnce = bce->parent &&
         bce->parent->emittingRunOnceLambda &&
         !funbox->argumentsHasLocalBinding() &&
         !funbox->isGenerator();
     if (runOnce) {
         bce->switchToProlog();
-        if (!Emit1(cx, bce, JSOP_RUNONCE) < 0)
+        if (Emit1(cx, bce, JSOP_RUNONCE) < 0)
             return false;
         bce->switchToMain();
     }
 
     if (!EmitTree(cx, bce, body))
         return false;
 
     /*
--- a/js/src/jscntxt.h
+++ b/js/src/jscntxt.h
@@ -17,16 +17,17 @@
 
 #include "jsapi.h"
 #include "jsfriendapi.h"
 #include "jsprvtd.h"
 #include "jsatom.h"
 #include "jsclist.h"
 #include "jsgc.h"
 
+#include "ds/FixedSizeHash.h"
 #include "ds/LifoAlloc.h"
 #include "frontend/ParseMaps.h"
 #include "gc/Nursery.h"
 #include "gc/Statistics.h"
 #include "gc/StoreBuffer.h"
 #include "js/HashTable.h"
 #include "js/Vector.h"
 #include "vm/DateTime.h"
@@ -239,16 +240,43 @@ struct EvalCacheHashPolicy
     typedef EvalCacheLookup Lookup;
 
     static HashNumber hash(const Lookup &l);
     static bool match(const EvalCacheEntry &entry, const EvalCacheLookup &l);
 };
 
 typedef HashSet<EvalCacheEntry, EvalCacheHashPolicy, SystemAllocPolicy> EvalCache;
 
+struct LazyScriptHashPolicy
+{
+    struct Lookup {
+        JSContext *cx;
+        LazyScript *lazy;
+
+        Lookup(JSContext *cx, LazyScript *lazy)
+          : cx(cx), lazy(lazy)
+        {}
+    };
+
+    static const size_t NumHashes = 3;
+
+    static void hash(const Lookup &lookup, HashNumber hashes[NumHashes]);
+    static bool match(JSScript *script, const Lookup &lookup);
+
+    // Alternate methods for use when removing scripts from the hash without an
+    // explicit LazyScript lookup.
+    static void hash(JSScript *script, HashNumber hashes[NumHashes]);
+    static bool match(JSScript *script, JSScript *lookup) { return script == lookup; }
+
+    static void clear(JSScript **pscript) { *pscript = NULL; }
+    static bool isCleared(JSScript *script) { return !script; }
+};
+
+typedef FixedSizeHashSet<JSScript *, LazyScriptHashPolicy, 769> LazyScriptCache;
+
 class PropertyIteratorObject;
 
 class NativeIterCache
 {
     static const size_t SIZE = size_t(1) << 8;
 
     /* Cached native iterators. */
     PropertyIteratorObject *data[SIZE];
@@ -1255,16 +1283,17 @@ struct JSRuntime : public JS::shadow::Ru
         return mathCache_ ? mathCache_ : createMathCache(cx);
     }
 
     js::GSNCache        gsnCache;
     js::NewObjectCache  newObjectCache;
     js::NativeIterCache nativeIterCache;
     js::SourceDataCache sourceDataCache;
     js::EvalCache       evalCache;
+    js::LazyScriptCache lazyScriptCache;
 
     /* State used by jsdtoa.cpp. */
     DtoaState           *dtoaState;
 
     js::DateTimeInfo    dateTimeInfo;
 
     js::ConservativeGCData conservativeGC;
 
--- a/js/src/jsfun.cpp
+++ b/js/src/jsfun.cpp
@@ -1044,53 +1044,108 @@ JSFunction::getBoundFunctionArgumentCoun
     return getSlot(JSSLOT_BOUND_FUNCTION_ARGS_COUNT).toPrivateUint32();
 }
 
 /* static */ bool
 JSFunction::createScriptForLazilyInterpretedFunction(JSContext *cx, HandleFunction fun)
 {
     JS_ASSERT(fun->isInterpretedLazy());
 
-    if (LazyScript *lazy = fun->lazyScriptOrNull()) {
-        /* Trigger a pre barrier on the lazy script being overwritten. */
+    LazyScript *lazy = fun->lazyScriptOrNull();
+    if (lazy) {
+        // Trigger a pre barrier on the lazy script being overwritten.
         if (cx->zone()->needsBarrier())
             LazyScript::writeBarrierPre(lazy);
 
+        // Suppress GC when lazily compiling functions, to preserve source
+        // character buffers.
+        AutoSuppressGC suppressGC(cx);
+
         fun->flags &= ~INTERPRETED_LAZY;
         fun->flags |= INTERPRETED;
 
-        if (JSScript *script = lazy->maybeScript()) {
+        JSScript *script = lazy->maybeScript();
+
+        if (script) {
             fun->initScript(script);
             return true;
         }
 
         fun->initScript(NULL);
 
+        // Lazy script caching is only supported for leaf functions. If a
+        // script with inner functions was returned by the cache, those inner
+        // functions would be delazified when deep cloning the script, even if
+        // they have never executed.
+        //
+        // Additionally, the lazy script cache is not used during incremental
+        // GCs, to avoid resurrecting dead scripts after incremental sweeping
+        // has started.
+        if (!lazy->numInnerFunctions() && !JS::IsIncrementalGCInProgress(cx->runtime())) {
+            LazyScriptCache::Lookup lookup(cx, lazy);
+            cx->runtime()->lazyScriptCache.lookup(lookup, &script);
+        }
+
+        if (script) {
+            RootedObject enclosingScope(cx, lazy->enclosingScope());
+            RootedScript scriptRoot(cx, script);
+            RootedScript clonedScript(cx, CloneScript(cx, enclosingScope, fun, scriptRoot));
+            if (!clonedScript) {
+                fun->initLazyScript(lazy);
+                return false;
+            }
+
+            // The cloned script will have reused the origin principals and
+            // filename from the original script, which may differ.
+            clonedScript->originPrincipals = lazy->originPrincipals();
+            clonedScript->setSourceObject(lazy->sourceObject());
+
+            fun->initAtom(script->function()->displayAtom());
+            fun->initScript(clonedScript);
+            clonedScript->setFunction(fun);
+
+            CallNewScriptHook(cx, clonedScript, fun);
+
+            lazy->initScript(clonedScript);
+            return true;
+        }
+
         JS_ASSERT(lazy->source()->hasSourceData());
 
-        /*
-         * GC must be suppressed for the remainder of the lazy parse, as any
-         * GC activity may destroy the characters.
-         */
-        AutoSuppressGC suppressGC(cx);
-
-        /* Lazily parsed script. */
+        // Parse and compile the script from source.
         const jschar *chars = lazy->source()->chars(cx);
-        if (!chars)
+        if (!chars) {
+            fun->initLazyScript(lazy);
             return false;
+        }
 
         const jschar *lazyStart = chars + lazy->begin();
         size_t lazyLength = lazy->end() - lazy->begin();
 
         if (!frontend::CompileLazyFunction(cx, fun, lazy, lazyStart, lazyLength)) {
             fun->initLazyScript(lazy);
             return false;
         }
 
-        lazy->initScript(fun->nonLazyScript());
+        script = fun->nonLazyScript();
+
+        // Try to insert the newly compiled script into the lazy script cache.
+        if (!lazy->numInnerFunctions()) {
+            // A script's starting column isn't set by the bytecode emitter, so
+            // specify this from the lazy script so that if an identical lazy
+            // script is encountered later a match can be determined.
+            script->column = lazy->column();
+
+            LazyScriptCache::Lookup lookup(cx, lazy);
+            cx->runtime()->lazyScriptCache.insert(lookup, script);
+        }
+
+        // Remember the compiled script on the lazy script itself, in case
+        // there are clones of the function still pointing to the lazy script.
+        lazy->initScript(script);
         return true;
     }
 
     /* Lazily cloned self hosted script. */
     JSFunctionSpec *fs = static_cast<JSFunctionSpec *>(fun->getExtendedSlot(0).toPrivate());
     RootedAtom funAtom(cx, Atomize(cx, fs->selfHostedName, strlen(fs->selfHostedName)));
     if (!funAtom)
         return false;
--- a/js/src/jsscript.cpp
+++ b/js/src/jsscript.cpp
@@ -784,16 +784,22 @@ js::XDRScript(XDRState<mode> *xdr, Handl
 template bool
 js::XDRScript(XDRState<XDR_ENCODE> *, HandleObject, HandleScript, HandleFunction,
               MutableHandleScript);
 
 template bool
 js::XDRScript(XDRState<XDR_DECODE> *, HandleObject, HandleScript, HandleFunction,
               MutableHandleScript);
 
+void
+JSScript::setSourceObject(js::ScriptSourceObject *object)
+{
+    sourceObject_ = object;
+}
+
 js::ScriptSourceObject *
 JSScript::sourceObject() const
 {
     return &sourceObject_->as<ScriptSourceObject>();
 }
 
 bool
 JSScript::initScriptCounts(JSContext *cx)
@@ -2047,16 +2053,18 @@ JSScript::finalize(FreeOp *fop)
 
     destroyScriptCounts(fop);
     destroyDebugScript(fop);
 
     if (data) {
         JS_POISON(data, 0xdb, computedSizeOfData());
         fop->free_(data);
     }
+
+    fop->runtime()->lazyScriptCache.remove(this);
 }
 
 static const uint32_t GSN_CACHE_THRESHOLD = 100;
 static const uint32_t GSN_CACHE_MAP_INIT_SIZE = 20;
 
 void
 GSNCache::purge()
 {
@@ -3042,8 +3050,78 @@ JSScript::updateBaselineOrIonRaw()
         baselineOrIonRaw = baseline->method()->raw();
         baselineOrIonSkipArgCheck = baseline->method()->raw();
     } else {
         baselineOrIonRaw = NULL;
         baselineOrIonSkipArgCheck = NULL;
     }
 #endif
 }
+
+static inline void
+LazyScriptHash(uint32_t lineno, uint32_t column, uint32_t begin, uint32_t end,
+               HashNumber hashes[3])
+{
+    HashNumber hash = lineno;
+    hash = JS_ROTATE_LEFT32(hash, 4) ^ column;
+    hash = JS_ROTATE_LEFT32(hash, 4) ^ begin;
+    hash = JS_ROTATE_LEFT32(hash, 4) ^ end;
+
+    hashes[0] = hash;
+    hashes[1] = JS_ROTATE_LEFT32(hashes[0], 4) ^ begin;
+    hashes[2] = JS_ROTATE_LEFT32(hashes[1], 4) ^ end;
+}
+
+void
+LazyScriptHashPolicy::hash(const Lookup &lookup, HashNumber hashes[3])
+{
+    LazyScript *lazy = lookup.lazy;
+    LazyScriptHash(lazy->lineno(), lazy->column(), lazy->begin(), lazy->end(), hashes);
+}
+
+void
+LazyScriptHashPolicy::hash(JSScript *script, HashNumber hashes[3])
+{
+    LazyScriptHash(script->lineno, script->column, script->sourceStart, script->sourceEnd, hashes);
+}
+
+bool
+LazyScriptHashPolicy::match(JSScript *script, const Lookup &lookup)
+{
+    JSContext *cx = lookup.cx;
+    LazyScript *lazy = lookup.lazy;
+
+    // To be a match, the script and lazy script need to have the same line
+    // and column and to be at the same position within their respective
+    // source blobs, and to have the same source contents and version.
+    //
+    // While the surrounding code in the source may differ, this is
+    // sufficient to ensure that compiling the lazy script will yield an
+    // identical result to compiling the original script.
+    //
+    // Note that the filenames and origin principals of the lazy script and
+    // original script can differ. If there is a match, these will be fixed
+    // up in the resulting clone by the caller.
+
+    if (script->lineno != lazy->lineno() ||
+        script->column != lazy->column() ||
+        script->getVersion() != lazy->version() ||
+        script->sourceStart != lazy->begin() ||
+        script->sourceEnd != lazy->end())
+    {
+        return false;
+    }
+
+    // GC activity may destroy the character pointers being compared below.
+    AutoSuppressGC suppress(cx);
+
+    const jschar *scriptChars = script->scriptSource()->chars(cx);
+    if (!scriptChars)
+        return false;
+
+    const jschar *lazyChars = lazy->source()->chars(cx);
+    if (!lazyChars)
+        return false;
+
+    size_t begin = script->sourceStart;
+    size_t length = script->sourceEnd - begin;
+    return !memcmp(scriptChars + begin, lazyChars + begin, length);
+}
--- a/js/src/jsscript.h
+++ b/js/src/jsscript.h
@@ -449,31 +449,31 @@ class JSScript : public js::gc::Cell
     // 32-bit fields.
 
   public:
     uint32_t        length;     /* length of code vector */
 
     uint32_t        dataSize;   /* size of the used part of the data array */
 
     uint32_t        lineno;     /* base line number of script */
+    uint32_t        column;     /* base column of script, optionally set */
 
     uint32_t        mainOffset; /* offset of main entry point from code, after
                                    predef'ing prolog */
 
     uint32_t        natoms;     /* length of atoms array */
 
     /* Range of characters in scriptSource which contains this script's source. */
     uint32_t        sourceStart;
     uint32_t        sourceEnd;
 
   private:
     uint32_t        useCount;   /* Number of times the script has been called
                                  * or has had backedges taken. Reset if the
                                  * script's JIT code is forcibly discarded. */
-    uint32_t        PADDING32;
 
 #ifdef DEBUG
     // Unique identifier within the compartment for this script, used for
     // printing analysis information.
     uint32_t        id_;
   private:
     uint32_t        idpad;
 #endif
@@ -755,16 +755,17 @@ class JSScript : public js::gc::Cell
 
     JSFunction *originalFunction() const;
     void setOriginalFunctionObject(JSObject *fun);
 
     JSFlatString *sourceData(JSContext *cx);
 
     static bool loadSource(JSContext *cx, js::HandleScript scr, bool *worked);
 
+    void setSourceObject(js::ScriptSourceObject *object);
     js::ScriptSourceObject *sourceObject() const;
     js::ScriptSource *scriptSource() const { return sourceObject()->source(); }
     const char *filename() const { return scriptSource()->filename(); }
 
   public:
 
     /* Return whether this script was compiled for 'eval' */
     bool isForEval() { return isCachedEval || isActiveEval; }