- Revision
- 246115
- Author
- [email protected]
- Date
- 2019-06-05 10:40:21 -0700 (Wed, 05 Jun 2019)
Log Message
[WHLSL] checkDuplicateFunctions() should not be O(n^2)
https://bugs.webkit.org/show_bug.cgi?id=198155
<rdar://problem/51288811>
Reviewed by Myles Maxfield.
Originally, we filed this bug because we thought checkDuplicateFunctions()
would take on the order of hundreds of milliseconds when using the
full standard library. However, I was never able to reproduce that phase
taking that long. I was seeing it take 3.5-4ms. Anyways, it makes sense
to make this phase not be O(N^2), since the number of functions is a user
controlled value. I am now seeing ~2.5ms to run this phase against the
full standard library. On a microbenchmark I checked against, where there
were 100,000 unique functions, this pass runs twice as fast as it used
to, now taking 450ms instead of 900ms.
* Modules/webgpu/WHLSL/AST/WHLSLArrayReferenceType.h:
(WebCore::WHLSL::AST::ArrayReferenceType::ArrayReferenceType):
* Modules/webgpu/WHLSL/AST/WHLSLArrayType.h:
* Modules/webgpu/WHLSL/AST/WHLSLPointerType.h:
(WebCore::WHLSL::AST::PointerType::PointerType):
* Modules/webgpu/WHLSL/AST/WHLSLReferenceType.h:
* Modules/webgpu/WHLSL/AST/WHLSLTypeReference.h:
* Modules/webgpu/WHLSL/AST/WHLSLUnnamedType.h:
* Modules/webgpu/WHLSL/WHLSLCheckDuplicateFunctions.cpp:
(WebCore::WHLSL::DuplicateFunctionKey::DuplicateFunctionKey):
(WebCore::WHLSL::DuplicateFunctionKey::isEmptyValue const):
(WebCore::WHLSL::DuplicateFunctionKey::isHashTableDeletedValue const):
(WebCore::WHLSL::DuplicateFunctionKey::hash const):
(WebCore::WHLSL::DuplicateFunctionKey::operator== const):
(WebCore::WHLSL::DuplicateFunctionKey::Hash::hash):
(WebCore::WHLSL::DuplicateFunctionKey::Hash::equal):
(WebCore::WHLSL::DuplicateFunctionKey::Traits::isEmptyValue):
(WebCore::WHLSL::checkDuplicateFunctions):
Modified Paths
Diff
Modified: trunk/Source/WebCore/ChangeLog (246114 => 246115)
--- trunk/Source/WebCore/ChangeLog 2019-06-05 17:34:20 UTC (rev 246114)
+++ trunk/Source/WebCore/ChangeLog 2019-06-05 17:40:21 UTC (rev 246115)
@@ -1,3 +1,40 @@
+2019-06-05 Saam Barati <[email protected]>
+
+ [WHLSL] checkDuplicateFunctions() should not be O(n^2)
+ https://bugs.webkit.org/show_bug.cgi?id=198155
+ <rdar://problem/51288811>
+
+ Reviewed by Myles Maxfield.
+
+ Originally, we filed this bug because we thought checkDuplicateFunctions()
+ would take on the order of hundreds of milliseconds when using the
+ full standard library. However, I was never able to reproduce that phase
+ taking that long. I was seeing it take 3.5-4ms. Anyways, it makes sense
+ to make this phase not be O(N^2), since the number of functions is a user
+ controlled value. I am now seeing ~2.5ms to run this phase against the
+ full standard library. On a microbenchmark I checked against, where there
+ were 100,000 unique functions, this pass runs twice as fast as it used
+ to, now taking 450ms instead of 900ms.
+
+ * Modules/webgpu/WHLSL/AST/WHLSLArrayReferenceType.h:
+ (WebCore::WHLSL::AST::ArrayReferenceType::ArrayReferenceType):
+ * Modules/webgpu/WHLSL/AST/WHLSLArrayType.h:
+ * Modules/webgpu/WHLSL/AST/WHLSLPointerType.h:
+ (WebCore::WHLSL::AST::PointerType::PointerType):
+ * Modules/webgpu/WHLSL/AST/WHLSLReferenceType.h:
+ * Modules/webgpu/WHLSL/AST/WHLSLTypeReference.h:
+ * Modules/webgpu/WHLSL/AST/WHLSLUnnamedType.h:
+ * Modules/webgpu/WHLSL/WHLSLCheckDuplicateFunctions.cpp:
+ (WebCore::WHLSL::DuplicateFunctionKey::DuplicateFunctionKey):
+ (WebCore::WHLSL::DuplicateFunctionKey::isEmptyValue const):
+ (WebCore::WHLSL::DuplicateFunctionKey::isHashTableDeletedValue const):
+ (WebCore::WHLSL::DuplicateFunctionKey::hash const):
+ (WebCore::WHLSL::DuplicateFunctionKey::operator== const):
+ (WebCore::WHLSL::DuplicateFunctionKey::Hash::hash):
+ (WebCore::WHLSL::DuplicateFunctionKey::Hash::equal):
+ (WebCore::WHLSL::DuplicateFunctionKey::Traits::isEmptyValue):
+ (WebCore::WHLSL::checkDuplicateFunctions):
+
2019-06-05 Zalan Bujtas <[email protected]>
[LFC][IFC] LineLayout::placeInlineItems should not apply float contraint.
Modified: trunk/Source/WebCore/Modules/webgpu/WHLSL/AST/WHLSLArrayReferenceType.h (246114 => 246115)
--- trunk/Source/WebCore/Modules/webgpu/WHLSL/AST/WHLSLArrayReferenceType.h 2019-06-05 17:34:20 UTC (rev 246114)
+++ trunk/Source/WebCore/Modules/webgpu/WHLSL/AST/WHLSLArrayReferenceType.h 2019-06-05 17:40:21 UTC (rev 246115)
@@ -39,9 +39,10 @@
namespace AST {
class ArrayReferenceType : public ReferenceType {
+ using Base = ReferenceType;
public:
ArrayReferenceType(Lexer::Token&& origin, AddressSpace addressSpace, UniqueRef<UnnamedType>&& elementType)
- : ReferenceType(WTFMove(origin), addressSpace, WTFMove(elementType))
+ : Base(WTFMove(origin), addressSpace, WTFMove(elementType))
{
}
@@ -57,6 +58,11 @@
return makeUniqueRef<ArrayReferenceType>(Lexer::Token(origin()), addressSpace(), elementType().clone());
}
+ unsigned hash() const override
+ {
+ return this->Base::hash() ^ StringHasher::computeLiteralHash("array");
+ }
+
private:
};
Modified: trunk/Source/WebCore/Modules/webgpu/WHLSL/AST/WHLSLArrayType.h (246114 => 246115)
--- trunk/Source/WebCore/Modules/webgpu/WHLSL/AST/WHLSLArrayType.h 2019-06-05 17:34:20 UTC (rev 246114)
+++ trunk/Source/WebCore/Modules/webgpu/WHLSL/AST/WHLSLArrayType.h 2019-06-05 17:40:21 UTC (rev 246115)
@@ -64,6 +64,11 @@
return makeUniqueRef<ArrayType>(Lexer::Token(origin()), m_elementType->clone(), m_numElements);
}
+ unsigned hash() const override
+ {
+ return WTF::IntHash<unsigned>::hash(m_numElements) ^ m_elementType->hash();
+ }
+
private:
UniqueRef<UnnamedType> m_elementType;
unsigned m_numElements;
Modified: trunk/Source/WebCore/Modules/webgpu/WHLSL/AST/WHLSLPointerType.h (246114 => 246115)
--- trunk/Source/WebCore/Modules/webgpu/WHLSL/AST/WHLSLPointerType.h 2019-06-05 17:34:20 UTC (rev 246114)
+++ trunk/Source/WebCore/Modules/webgpu/WHLSL/AST/WHLSLPointerType.h 2019-06-05 17:40:21 UTC (rev 246115)
@@ -39,9 +39,10 @@
namespace AST {
class PointerType : public ReferenceType {
+ using Base = ReferenceType;
public:
PointerType(Lexer::Token&& origin, AddressSpace addressSpace, UniqueRef<UnnamedType> elementType)
- : ReferenceType(WTFMove(origin), addressSpace, WTFMove(elementType))
+ : Base(WTFMove(origin), addressSpace, WTFMove(elementType))
{
}
@@ -57,6 +58,11 @@
return makeUniqueRef<PointerType>(Lexer::Token(origin()), addressSpace(), elementType().clone());
}
+ unsigned hash() const override
+ {
+ return this->Base::hash() ^ StringHasher::computeLiteralHash("pointer");
+ }
+
private:
};
Modified: trunk/Source/WebCore/Modules/webgpu/WHLSL/AST/WHLSLReferenceType.h (246114 => 246115)
--- trunk/Source/WebCore/Modules/webgpu/WHLSL/AST/WHLSLReferenceType.h 2019-06-05 17:34:20 UTC (rev 246114)
+++ trunk/Source/WebCore/Modules/webgpu/WHLSL/AST/WHLSLReferenceType.h 2019-06-05 17:40:21 UTC (rev 246115)
@@ -59,6 +59,11 @@
const UnnamedType& elementType() const { return m_elementType; }
UnnamedType& elementType() { return m_elementType; }
+ unsigned hash() const override
+ {
+ return ~m_elementType->hash();
+ }
+
private:
AddressSpace m_addressSpace;
UniqueRef<UnnamedType> m_elementType;
Modified: trunk/Source/WebCore/Modules/webgpu/WHLSL/AST/WHLSLTypeReference.h (246114 => 246115)
--- trunk/Source/WebCore/Modules/webgpu/WHLSL/AST/WHLSLTypeReference.h 2019-06-05 17:34:20 UTC (rev 246114)
+++ trunk/Source/WebCore/Modules/webgpu/WHLSL/AST/WHLSLTypeReference.h 2019-06-05 17:40:21 UTC (rev 246115)
@@ -99,6 +99,14 @@
return cloneTypeReference();
}
+ unsigned hash() const override
+ {
+ // Currently, we only use this function after the name resolver runs.
+ // Relying on having a resolved type simplifies this implementation.
+ ASSERT(m_resolvedType);
+ return WTF::PtrHash<const Type*>::hash(&unifyNode());
+ }
+
private:
String m_name;
TypeArguments m_typeArguments;
Modified: trunk/Source/WebCore/Modules/webgpu/WHLSL/AST/WHLSLUnnamedType.h (246114 => 246115)
--- trunk/Source/WebCore/Modules/webgpu/WHLSL/AST/WHLSLUnnamedType.h 2019-06-05 17:34:20 UTC (rev 246114)
+++ trunk/Source/WebCore/Modules/webgpu/WHLSL/AST/WHLSLUnnamedType.h 2019-06-05 17:40:21 UTC (rev 246115)
@@ -63,6 +63,8 @@
virtual UniqueRef<UnnamedType> clone() const = 0;
+ virtual unsigned hash() const = 0;
+
const Lexer::Token& origin() const { return m_origin; }
private:
Modified: trunk/Source/WebCore/Modules/webgpu/WHLSL/WHLSLCheckDuplicateFunctions.cpp (246114 => 246115)
--- trunk/Source/WebCore/Modules/webgpu/WHLSL/WHLSLCheckDuplicateFunctions.cpp 2019-06-05 17:34:20 UTC (rev 246114)
+++ trunk/Source/WebCore/Modules/webgpu/WHLSL/WHLSLCheckDuplicateFunctions.cpp 2019-06-05 17:40:21 UTC (rev 246115)
@@ -32,56 +32,95 @@
#include "WHLSLArrayType.h"
#include "WHLSLInferTypes.h"
#include "WHLSLTypeReference.h"
+#include <wtf/HashSet.h>
+#include <wtf/HashTraits.h>
namespace WebCore {
namespace WHLSL {
-bool checkDuplicateFunctions(const Program& program)
-{
- Vector<std::reference_wrapper<const AST::FunctionDeclaration>> functions;
- for (auto& functionDefinition : program.functionDefinitions())
- functions.append(functionDefinition);
- for (auto& nativeFunctionDeclaration : program.nativeFunctionDeclarations())
- functions.append(nativeFunctionDeclaration);
+class DuplicateFunctionKey {
+public:
+ DuplicateFunctionKey() = default;
+ DuplicateFunctionKey(WTF::HashTableDeletedValueType)
+ {
+ m_function = bitwise_cast<AST::FunctionDeclaration*>(static_cast<uintptr_t>(1));
+ }
- std::sort(functions.begin(), functions.end(), [](const AST::FunctionDeclaration& a, const AST::FunctionDeclaration& b) -> bool {
- if (a.name().length() < b.name().length())
- return true;
- if (a.name().length() > b.name().length())
+ DuplicateFunctionKey(const AST::FunctionDeclaration& function)
+ : m_function(&function)
+ { }
+
+ bool isEmptyValue() const { return !m_function; }
+ bool isHashTableDeletedValue() const { return m_function == bitwise_cast<AST::FunctionDeclaration*>(static_cast<uintptr_t>(1)); }
+
+ unsigned hash() const
+ {
+ unsigned hash = IntHash<size_t>::hash(m_function->parameters().size());
+ hash ^= m_function->name().hash();
+ for (size_t i = 0; i < m_function->parameters().size(); ++i)
+ hash ^= m_function->parameters()[i]->type().value()->hash();
+
+ if (m_function->isCast())
+ hash ^= m_function->type().hash();
+
+ return hash;
+ }
+
+ bool operator==(const DuplicateFunctionKey& other) const
+ {
+ if (m_function->parameters().size() != other.m_function->parameters().size())
return false;
- for (unsigned i = 0; i < a.name().length(); ++i) {
- if (a.name()[i] < b.name()[i])
- return true;
- if (a.name()[i] > b.name()[i])
+
+ if (m_function->name() != other.m_function->name())
+ return false;
+
+ ASSERT(m_function->isCast() == other.m_function->isCast());
+
+ for (size_t i = 0; i < m_function->parameters().size(); ++i) {
+ if (!matches(*m_function->parameters()[i]->type(), *other.m_function->parameters()[i]->type()))
return false;
}
+
+ if (!m_function->isCast())
+ return true;
+
+ if (matches(m_function->type(), other.m_function->type()))
+ return true;
+
return false;
- });
- for (size_t i = 0; i < functions.size(); ++i) {
- for (size_t j = i + 1; j < functions.size(); ++j) {
- if (functions[i].get().name() != functions[j].get().name())
- break;
- if (is<AST::NativeFunctionDeclaration>(functions[i].get()) && is<AST::NativeFunctionDeclaration>(functions[j].get()))
- continue;
- if (functions[i].get().parameters().size() != functions[j].get().parameters().size())
- continue;
- if (functions[i].get().isCast() && !matches(functions[i].get().type(), functions[j].get().type()))
- continue;
- bool same = true;
- for (size_t k = 0; k < functions[i].get().parameters().size(); ++k) {
- if (!matches(*functions[i].get().parameters()[k]->type(), *functions[j].get().parameters()[k]->type())) {
- same = false;
- break;
- }
- }
- if (same)
- return false;
+ }
+
+ struct Hash {
+ static unsigned hash(const DuplicateFunctionKey& key)
+ {
+ return key.hash();
}
-
- if (functions[i].get().name() == "operator&[]" && functions[i].get().parameters().size() == 2
- && is<AST::ArrayReferenceType>(static_cast<const AST::UnnamedType&>(*functions[i].get().parameters()[0]->type()))) {
- auto& type = static_cast<const AST::UnnamedType&>(*functions[i].get().parameters()[1]->type());
+
+ static bool equal(const DuplicateFunctionKey& a, const DuplicateFunctionKey& b)
+ {
+ return a == b;
+ }
+
+ static const bool safeToCompareToEmptyOrDeleted = false;
+ static const bool emptyValueIsZero = true;
+ };
+
+ struct Traits : public WTF::SimpleClassHashTraits<DuplicateFunctionKey> {
+ static const bool hasIsEmptyValueFunction = true;
+ static bool isEmptyValue(const DuplicateFunctionKey& key) { return key.isEmptyValue(); }
+ };
+
+private:
+ const AST::FunctionDeclaration* m_function { nullptr };
+};
+
+bool checkDuplicateFunctions(const Program& program)
+{
+ auto passesStaticChecks = [&] (const AST::FunctionDeclaration& function) {
+ if (function.name() == "operator&[]" && function.parameters().size() == 2
+ && is<AST::ArrayReferenceType>(static_cast<const AST::UnnamedType&>(*function.parameters()[0]->type()))) {
+ auto& type = static_cast<const AST::UnnamedType&>(*function.parameters()[1]->type());
if (is<AST::TypeReference>(type)) {
// FIXME: https://bugs.webkit.org/show_bug.cgi?id=198161 Shouldn't we already know whether the types have been resolved by now?
if (auto* resolvedType = downcast<AST::TypeReference>(type).maybeResolvedType()) {
@@ -92,17 +131,44 @@
}
}
}
- } else if (functions[i].get().name() == "operator.length" && functions[i].get().parameters().size() == 1
- && (is<AST::ArrayReferenceType>(static_cast<const AST::UnnamedType&>(*functions[i].get().parameters()[0]->type()))
- || is<AST::ArrayType>(static_cast<const AST::UnnamedType&>(*functions[i].get().parameters()[0]->type()))))
+ } else if (function.name() == "operator.length" && function.parameters().size() == 1
+ && (is<AST::ArrayReferenceType>(static_cast<const AST::UnnamedType&>(*function.parameters()[0]->type()))
+ || is<AST::ArrayType>(static_cast<const AST::UnnamedType&>(*function.parameters()[0]->type()))))
return false;
- else if (functions[i].get().name() == "operator=="
- && functions[i].get().parameters().size() == 2
- && is<AST::ReferenceType>(static_cast<const AST::UnnamedType&>(*functions[i].get().parameters()[0]->type()))
- && is<AST::ReferenceType>(static_cast<const AST::UnnamedType&>(*functions[i].get().parameters()[1]->type()))
- && matches(*functions[i].get().parameters()[0]->type(), *functions[i].get().parameters()[1]->type()))
+ else if (function.name() == "operator=="
+ && function.parameters().size() == 2
+ && is<AST::ReferenceType>(static_cast<const AST::UnnamedType&>(*function.parameters()[0]->type()))
+ && is<AST::ReferenceType>(static_cast<const AST::UnnamedType&>(*function.parameters()[1]->type()))
+ && matches(*function.parameters()[0]->type(), *function.parameters()[1]->type()))
return false;
+
+ return true;
+ };
+
+ HashSet<DuplicateFunctionKey, DuplicateFunctionKey::Hash, DuplicateFunctionKey::Traits> functions;
+
+ auto add = [&] (const AST::FunctionDeclaration& function) {
+ auto addResult = functions.add(DuplicateFunctionKey { function });
+ if (!addResult.isNewEntry)
+ return false;
+ return passesStaticChecks(function);
+ };
+
+ for (auto& functionDefinition : program.functionDefinitions()) {
+ if (!add(functionDefinition.get()))
+ return false;
}
+
+ for (auto& nativeFunctionDeclaration : program.nativeFunctionDeclarations()) {
+ // Native function declarations are never equal to each other. So we don't need
+ // to add them to the set, because they can't collide with each other. Instead, we
+ // just check that no user-defined function is a duplicate.
+ ASSERT(passesStaticChecks(nativeFunctionDeclaration.get()));
+ if (functions.contains(DuplicateFunctionKey { nativeFunctionDeclaration.get() }))
+ return false;
+ ASSERT(add(nativeFunctionDeclaration.get()));
+ }
+
return true;
}
