- Revision
- 205819
- Author
- sbar...@apple.com
- Date
- 2016-09-12 14:04:25 -0700 (Mon, 12 Sep 2016)
Log Message
MapHash should do constant folding when it has a constant argument and its legal to hash that value
https://bugs.webkit.org/show_bug.cgi?id=161639
Reviewed by Filip Pizlo.
JSTests:
* microbenchmarks/map-constant-key.js: Added.
(assert):
(test):
(foo):
Source/_javascript_Core:
We now constant fold the MapHash node. We're careful to not resolve
ropes from the compiler thread, and to only hash strings if they're
not too large. The microbenchmark I added runs about 12% faster with
this patch.
* dfg/DFGAbstractInterpreterInlines.h:
(JSC::DFG::AbstractInterpreter<AbstractStateType>::executeEffects):
* runtime/HashMapImpl.h:
(JSC::wangsInt64Hash):
(JSC::jsMapHash):
(JSC::concurrentJSMapHash):
Source/WTF:
This patch adds a concurrentHash method to StringImpl. It's
probably safe to get the actual hash while being racy, however,
it's simpler and more future proof to not have to worry about
that and to just compute it on demand. Users of this API should
be aware that it's doing non-trivial work. Currently, the only
user is JSC's JIT compilers, and they only ask for hashes for small-ish
strings.
* wtf/text/StringImpl.h:
* wtf/text/StringStatics.cpp:
(WTF::StringImpl::concurrentHash):
Modified Paths
Added Paths
Diff
Modified: trunk/JSTests/ChangeLog (205818 => 205819)
--- trunk/JSTests/ChangeLog 2016-09-12 19:50:50 UTC (rev 205818)
+++ trunk/JSTests/ChangeLog 2016-09-12 21:04:25 UTC (rev 205819)
@@ -1,3 +1,15 @@
+2016-09-12 Saam Barati <sbar...@apple.com>
+
+ MapHash should do constant folding when it has a constant argument and its legal to hash that value
+ https://bugs.webkit.org/show_bug.cgi?id=161639
+
+ Reviewed by Filip Pizlo.
+
+ * microbenchmarks/map-constant-key.js: Added.
+ (assert):
+ (test):
+ (foo):
+
2016-09-12 Michael Saboff <msab...@apple.com>
JSC test timeout: ChakraCore.yaml/ChakraCore/test/Bugs/bug56026_trycatch.js.default
Added: trunk/JSTests/microbenchmarks/map-constant-key.js (0 => 205819)
--- trunk/JSTests/microbenchmarks/map-constant-key.js (rev 0)
+++ trunk/JSTests/microbenchmarks/map-constant-key.js 2016-09-12 21:04:25 UTC (rev 205819)
@@ -0,0 +1,49 @@
+function assert(b) {
+ if (!b)
+ throw new Error("Bad assertion")
+}
+noInline(assert);
+function test(map, key, value) {
+ let loadValue = eval(`${Math.random()}; let k = key; (function getValue() { return map.get(k); });`);
+ noInline(loadValue);
+ for (let i = 0; i < 1000000; i++) {
+ assert(loadValue() === value);
+ }
+}
+
+let reallyLongString = "";
+for (let i = 0; i < 60000; i++) {
+ reallyLongString += "i";
+}
+reallyLongString.toString();
+
+let keys = [
+ "foo",
+ "fdashfdsahfdashfdsh",
+ "rope" + "string",
+ reallyLongString,
+ 259243,
+ 1238231.2138321,
+ -92138.328,
+ {foo: 25},
+ Symbol("Hello world"),
+ true,
+ false,
+ undefined,
+ null,
+ NaN,
+ -0,
+ function foo() {}
+];
+
+let start = Date.now();
+let map = new Map;
+let i = 0;
+for (let key of keys) {
+ let value = {i: i++};
+ map.set(key, value);
+ test(map, key, value);
+}
+const verbose = false;
+if (verbose)
+ print(Date.now() - start);
Modified: trunk/Source/_javascript_Core/ChangeLog (205818 => 205819)
--- trunk/Source/_javascript_Core/ChangeLog 2016-09-12 19:50:50 UTC (rev 205818)
+++ trunk/Source/_javascript_Core/ChangeLog 2016-09-12 21:04:25 UTC (rev 205819)
@@ -1,3 +1,22 @@
+2016-09-12 Saam Barati <sbar...@apple.com>
+
+ MapHash should do constant folding when it has a constant argument and its legal to hash that value
+ https://bugs.webkit.org/show_bug.cgi?id=161639
+
+ Reviewed by Filip Pizlo.
+
+ We now constant fold the MapHash node. We're careful to not resolve
+ ropes from the compiler thread, and to only hash strings if they're
+ not too large. The microbenchmark I added runs about 12% faster with
+ this patch.
+
+ * dfg/DFGAbstractInterpreterInlines.h:
+ (JSC::DFG::AbstractInterpreter<AbstractStateType>::executeEffects):
+ * runtime/HashMapImpl.h:
+ (JSC::wangsInt64Hash):
+ (JSC::jsMapHash):
+ (JSC::concurrentJSMapHash):
+
2016-09-11 Filip Pizlo <fpi...@apple.com>
DFG::forAllKilledOperands() could use a faster bitvector scan in the same-inline-stack fast path
Modified: trunk/Source/_javascript_Core/dfg/DFGAbstractInterpreterInlines.h (205818 => 205819)
--- trunk/Source/_javascript_Core/dfg/DFGAbstractInterpreterInlines.h 2016-09-12 19:50:50 UTC (rev 205818)
+++ trunk/Source/_javascript_Core/dfg/DFGAbstractInterpreterInlines.h 2016-09-12 21:04:25 UTC (rev 205819)
@@ -32,6 +32,7 @@
#include "DFGAbstractInterpreter.h"
#include "GetByIdStatus.h"
#include "GetterSetter.h"
+#include "HashMapImpl.h"
#include "JITOperations.h"
#include "MathCommon.h"
#include "Operations.h"
@@ -977,9 +978,20 @@
break;
}
- case MapHash:
+ case MapHash: {
+ if (JSValue key = forNode(node->child1()).value()) {
+ if (Optional<uint32_t> hash = concurrentJSMapHash(key)) {
+ // Although C++ code uses uint32_t for the hash, the closest type in DFG IR is Int32
+ // and that's what MapHash returns. So, we have to cast to int32_t to avoid large
+ // unsigned values becoming doubles. This casting between signed and unsigned
+ // happens in the assembly code we emit when we don't constant fold this node.
+ setConstant(node, jsNumber(static_cast<int32_t>(*hash)));
+ break;
+ }
+ }
forNode(node).setType(SpecInt32Only);
break;
+ }
case LoadFromJSMapBucket:
forNode(node).makeHeapTop();
Modified: trunk/Source/_javascript_Core/runtime/HashMapImpl.h (205818 => 205819)
--- trunk/Source/_javascript_Core/runtime/HashMapImpl.h 2016-09-12 19:50:50 UTC (rev 205818)
+++ trunk/Source/_javascript_Core/runtime/HashMapImpl.h 2016-09-12 21:04:25 UTC (rev 205819)
@@ -194,6 +194,19 @@
return key;
}
+static ALWAYS_INLINE uint32_t wangsInt64Hash(uint64_t key)
+{
+ key += ~(key << 32);
+ key ^= (key >> 22);
+ key += ~(key << 13);
+ key ^= (key >> 8);
+ key += (key << 3);
+ key ^= (key >> 15);
+ key += ~(key << 27);
+ key ^= (key >> 31);
+ return static_cast<unsigned>(key);
+}
+
ALWAYS_INLINE uint32_t jsMapHash(ExecState* exec, VM& vm, JSValue value)
{
ASSERT_WITH_MESSAGE(normalizeMapKey(value) == value, "We expect normalized values flowing into this function.");
@@ -208,21 +221,27 @@
return wtfString.impl()->hash();
}
- auto wangsInt64Hash = [] (uint64_t key) -> uint32_t {
- key += ~(key << 32);
- key ^= (key >> 22);
- key += ~(key << 13);
- key ^= (key >> 8);
- key += (key << 3);
- key ^= (key >> 15);
- key += ~(key << 27);
- key ^= (key >> 31);
- return static_cast<unsigned>(key);
- };
uint64_t rawValue = JSValue::encode(value);
return wangsInt64Hash(rawValue);
}
+ALWAYS_INLINE Optional<uint32_t> concurrentJSMapHash(JSValue key)
+{
+ key = normalizeMapKey(key);
+ if (key.isString()) {
+ JSString* string = asString(key);
+ if (string->length() > 10 * 1024)
+ return Nullopt;
+ const StringImpl* impl = string->tryGetValueImpl();
+ if (!impl)
+ return Nullopt;
+ return impl->concurrentHash();
+ }
+
+ uint64_t rawValue = JSValue::encode(key);
+ return wangsInt64Hash(rawValue);
+}
+
template <typename HashMapBucketType>
class HashMapImpl : public JSCell {
typedef JSCell Base;
Modified: trunk/Source/WTF/ChangeLog (205818 => 205819)
--- trunk/Source/WTF/ChangeLog 2016-09-12 19:50:50 UTC (rev 205818)
+++ trunk/Source/WTF/ChangeLog 2016-09-12 21:04:25 UTC (rev 205819)
@@ -1,3 +1,22 @@
+2016-09-12 Saam Barati <sbar...@apple.com>
+
+ MapHash should do constant folding when it has a constant argument and its legal to hash that value
+ https://bugs.webkit.org/show_bug.cgi?id=161639
+
+ Reviewed by Filip Pizlo.
+
+ This patch adds a concurrentHash method to StringImpl. It's
+ probably safe to get the actual hash while being racy, however,
+ it's simpler and more future proof to not have to worry about
+ that and to just compute it on demand. Users of this API should
+ be aware that it's doing non-trivial work. Currently, the only
+ user is JSC's JIT compilers, and they only ask for hashes for small-ish
+ strings.
+
+ * wtf/text/StringImpl.h:
+ * wtf/text/StringStatics.cpp:
+ (WTF::StringImpl::concurrentHash):
+
2016-09-11 Filip Pizlo <fpi...@apple.com>
DFG::forAllKilledOperands() could use a faster bitvector scan in the same-inline-stack fast path
Modified: trunk/Source/WTF/wtf/text/StringImpl.h (205818 => 205819)
--- trunk/Source/WTF/wtf/text/StringImpl.h 2016-09-12 19:50:50 UTC (rev 205818)
+++ trunk/Source/WTF/wtf/text/StringImpl.h 2016-09-12 21:04:25 UTC (rev 205819)
@@ -553,6 +553,8 @@
return hashSlowCase();
}
+ WTF_EXPORT_PRIVATE unsigned concurrentHash() const;
+
unsigned symbolAwareHash() const
{
if (isSymbol())
Modified: trunk/Source/WTF/wtf/text/StringStatics.cpp (205818 => 205819)
--- trunk/Source/WTF/wtf/text/StringStatics.cpp 2016-09-12 19:50:50 UTC (rev 205818)
+++ trunk/Source/WTF/wtf/text/StringStatics.cpp 2016-09-12 21:04:25 UTC (rev 205819)
@@ -82,6 +82,17 @@
return existingHash();
}
+unsigned StringImpl::concurrentHash() const
+{
+ unsigned hash;
+ if (is8Bit())
+ hash = StringHasher::computeHashAndMaskTop8Bits(m_data8, m_length);
+ else
+ hash = StringHasher::computeHashAndMaskTop8Bits(m_data16, m_length);
+ ASSERT(((hash << s_flagCount) >> s_flagCount) == hash);
+ return hash;
+}
+
void AtomicString::init()
{
static bool initialized;
