⚠ Archived content — this site is no longer maintained.   Current WebKit documentation is at docs.webkit.org.

Changeset 246115 in webkit


Ignore:
Timestamp:
Jun 5, 2019, 10:40:21 AM (7 years ago)
Author:
sbarati@apple.com
Message:

[WHLSL] checkDuplicateFunctions() should not be O(n2)
​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(N2), 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):

Location:
trunk/Source/WebCore
Files:
8 edited

Legend:

Unmodified
Added
Removed

  • trunk/Source/WebCore/ChangeLog

    r246114 r246115  
     12019-06-05  Saam Barati  <sbarati@apple.com>
     2
     3        [WHLSL] checkDuplicateFunctions() should not be O(n^2)
     4        https://bugs.webkit.org/show_bug.cgi?id=198155
     5        <rdar://problem/51288811>
     6
     7        Reviewed by Myles Maxfield.
     8
     9        Originally, we filed this bug because we thought checkDuplicateFunctions()
     10        would take on the order of hundreds of milliseconds when using the
     11        full standard library. However, I was never able to reproduce that phase
     12        taking that long. I was seeing it take 3.5-4ms. Anyways, it makes sense
     13        to make this phase not be O(N^2), since the number of functions is a user
     14        controlled value. I am now seeing ~2.5ms to run this phase against the
     15        full standard library. On a microbenchmark I checked against, where there
     16        were 100,000 unique functions, this pass runs twice as fast as it used
     17        to, now taking 450ms instead of 900ms.
     18
     19        * Modules/webgpu/WHLSL/AST/WHLSLArrayReferenceType.h:
     20        (WebCore::WHLSL::AST::ArrayReferenceType::ArrayReferenceType):
     21        * Modules/webgpu/WHLSL/AST/WHLSLArrayType.h:
     22        * Modules/webgpu/WHLSL/AST/WHLSLPointerType.h:
     23        (WebCore::WHLSL::AST::PointerType::PointerType):
     24        * Modules/webgpu/WHLSL/AST/WHLSLReferenceType.h:
     25        * Modules/webgpu/WHLSL/AST/WHLSLTypeReference.h:
     26        * Modules/webgpu/WHLSL/AST/WHLSLUnnamedType.h:
     27        * Modules/webgpu/WHLSL/WHLSLCheckDuplicateFunctions.cpp:
     28        (WebCore::WHLSL::DuplicateFunctionKey::DuplicateFunctionKey):
     29        (WebCore::WHLSL::DuplicateFunctionKey::isEmptyValue const):
     30        (WebCore::WHLSL::DuplicateFunctionKey::isHashTableDeletedValue const):
     31        (WebCore::WHLSL::DuplicateFunctionKey::hash const):
     32        (WebCore::WHLSL::DuplicateFunctionKey::operator== const):
     33        (WebCore::WHLSL::DuplicateFunctionKey::Hash::hash):
     34        (WebCore::WHLSL::DuplicateFunctionKey::Hash::equal):
     35        (WebCore::WHLSL::DuplicateFunctionKey::Traits::isEmptyValue):
     36        (WebCore::WHLSL::checkDuplicateFunctions):
     37
    1382019-06-05  Zalan Bujtas  <zalan@apple.com>
    239

  • trunk/Source/WebCore/Modules/webgpu/WHLSL/AST/WHLSLArrayReferenceType.h

    r239844 r246115  
    4040
    4141class ArrayReferenceType : public ReferenceType {
     42    using Base = ReferenceType;
    4243public:
    4344    ArrayReferenceType(Lexer::Token&& origin, AddressSpace addressSpace, UniqueRef<UnnamedType>&& elementType)
    44         : ReferenceType(WTFMove(origin), addressSpace, WTFMove(elementType))
     45        : Base(WTFMove(origin), addressSpace, WTFMove(elementType))
    4546    {
    4647    }
    … …  
    5859    }
    5960
     61    unsigned hash() const override
     62    {
     63        return this->Base::hash() ^ StringHasher::computeLiteralHash("array");
     64    }
     65
    6066private:
    6167};

  • trunk/Source/WebCore/Modules/webgpu/WHLSL/AST/WHLSLArrayType.h

    r239930 r246115  
    6565    }
    6666
     67    unsigned hash() const override
     68    {
     69        return WTF::IntHash<unsigned>::hash(m_numElements) ^ m_elementType->hash();
     70    }
     71
    6772private:
    6873    UniqueRef<UnnamedType> m_elementType;

  • trunk/Source/WebCore/Modules/webgpu/WHLSL/AST/WHLSLPointerType.h

    r239844 r246115  
    4040
    4141class PointerType : public ReferenceType {
     42    using Base = ReferenceType;
    4243public:
    4344    PointerType(Lexer::Token&& origin, AddressSpace addressSpace, UniqueRef<UnnamedType> elementType)
    44         : ReferenceType(WTFMove(origin), addressSpace, WTFMove(elementType))
     45        : Base(WTFMove(origin), addressSpace, WTFMove(elementType))
    4546    {
    4647    }
    … …  
    5859    }
    5960
     61    unsigned hash() const override
     62    {
     63        return this->Base::hash() ^ StringHasher::computeLiteralHash("pointer");
     64    }
     65
    6066private:
    6167};

  • trunk/Source/WebCore/Modules/webgpu/WHLSL/AST/WHLSLReferenceType.h

    r239930 r246115  
    6060    UnnamedType& elementType() { return m_elementType; }
    6161
     62    unsigned hash() const override
     63    {
     64        return ~m_elementType->hash();
     65    }
     66
    6267private:
    6368    AddressSpace m_addressSpace;

  • trunk/Source/WebCore/Modules/webgpu/WHLSL/AST/WHLSLTypeReference.h

    r245680 r246115  
    100100    }
    101101
     102    unsigned hash() const override
     103    {
     104        // Currently, we only use this function after the name resolver runs.
     105        // Relying on having a resolved type simplifies this implementation.
     106        ASSERT(m_resolvedType);
     107        return WTF::PtrHash<const Type*>::hash(&unifyNode());
     108    }
     109
    102110private:
    103111    String m_name;

  • trunk/Source/WebCore/Modules/webgpu/WHLSL/AST/WHLSLUnnamedType.h

    r239844 r246115  
    6464    virtual UniqueRef<UnnamedType> clone() const = 0;
    6565
     66    virtual unsigned hash() const = 0;
     67
    6668    const Lexer::Token& origin() const { return m_origin; }
    6769

  • trunk/Source/WebCore/Modules/webgpu/WHLSL/WHLSLCheckDuplicateFunctions.cpp

    r245680 r246115  
    3333#include "WHLSLInferTypes.h"
    3434#include "WHLSLTypeReference.h"
     35#include <wtf/HashSet.h>
     36#include <wtf/HashTraits.h>
    3537
    3638namespace WebCore {
    … …  
    3840namespace WHLSL {
    3941
     42class DuplicateFunctionKey {
     43public:
     44    DuplicateFunctionKey() = default;
     45    DuplicateFunctionKey(WTF::HashTableDeletedValueType)
     46    {
     47        m_function = bitwise_cast<AST::FunctionDeclaration*>(static_cast<uintptr_t>(1));
     48    }
     49
     50    DuplicateFunctionKey(const AST::FunctionDeclaration& function)
     51        : m_function(&function)
     52    { }
     53
     54    bool isEmptyValue() const { return !m_function; }
     55    bool isHashTableDeletedValue() const { return m_function == bitwise_cast<AST::FunctionDeclaration*>(static_cast<uintptr_t>(1)); }
     56
     57    unsigned hash() const
     58    {
     59        unsigned hash = IntHash<size_t>::hash(m_function->parameters().size());
     60        hash ^= m_function->name().hash();
     61        for (size_t i = 0; i < m_function->parameters().size(); ++i)
     62            hash ^= m_function->parameters()[i]->type().value()->hash();
     63
     64        if (m_function->isCast())
     65            hash ^= m_function->type().hash();
     66
     67        return hash;
     68    }
     69
     70    bool operator==(const DuplicateFunctionKey& other) const
     71    {
     72        if (m_function->parameters().size() != other.m_function->parameters().size())
     73            return false;
     74
     75        if (m_function->name() != other.m_function->name())
     76            return false;
     77
     78        ASSERT(m_function->isCast() == other.m_function->isCast());
     79
     80        for (size_t i = 0; i < m_function->parameters().size(); ++i) {
     81            if (!matches(*m_function->parameters()[i]->type(), *other.m_function->parameters()[i]->type()))
     82                return false;
     83        }
     84
     85        if (!m_function->isCast())
     86            return true;
     87
     88        if (matches(m_function->type(), other.m_function->type()))
     89            return true;
     90
     91        return false;
     92    }
     93
     94    struct Hash {
     95        static unsigned hash(const DuplicateFunctionKey& key)
     96        {
     97            return key.hash();
     98        }
     99
     100        static bool equal(const DuplicateFunctionKey& a, const DuplicateFunctionKey& b)
     101        {
     102            return a == b;
     103        }
     104
     105        static const bool safeToCompareToEmptyOrDeleted = false;
     106        static const bool emptyValueIsZero = true;
     107    };
     108
     109    struct Traits : public WTF::SimpleClassHashTraits<DuplicateFunctionKey> {
     110        static const bool hasIsEmptyValueFunction = true;
     111        static bool isEmptyValue(const DuplicateFunctionKey& key) { return key.isEmptyValue(); }
     112    };
     113
     114private:
     115    const AST::FunctionDeclaration* m_function { nullptr };
     116};
     117
    40118bool checkDuplicateFunctions(const Program& program)
    41119{
    42     Vector<std::reference_wrapper<const AST::FunctionDeclaration>> functions;
    43     for (auto& functionDefinition : program.functionDefinitions())
    44         functions.append(functionDefinition);
    45     for (auto& nativeFunctionDeclaration : program.nativeFunctionDeclarations())
    46         functions.append(nativeFunctionDeclaration);
    47 
    48     std::sort(functions.begin(), functions.end(), [](const AST::FunctionDeclaration& a, const AST::FunctionDeclaration& b) -> bool {
    49         if (a.name().length() < b.name().length())
    50             return true;
    51         if (a.name().length() > b.name().length())
    52             return false;
    53         for (unsigned i = 0; i < a.name().length(); ++i) {
    54             if (a.name()[i] < b.name()[i])
    55                 return true;
    56             if (a.name()[i] > b.name()[i])
    57                 return false;
    58         }
    59         return false;
    60     });
    61     for (size_t i = 0; i < functions.size(); ++i) {
    62         for (size_t j = i + 1; j < functions.size(); ++j) {
    63             if (functions[i].get().name() != functions[j].get().name())
    64                 break;
    65             if (is<AST::NativeFunctionDeclaration>(functions[i].get()) && is<AST::NativeFunctionDeclaration>(functions[j].get()))
    66                 continue;
    67             if (functions[i].get().parameters().size() != functions[j].get().parameters().size())
    68                 continue;
    69             if (functions[i].get().isCast() && !matches(functions[i].get().type(), functions[j].get().type()))
    70                 continue;
    71             bool same = true;
    72             for (size_t k = 0; k < functions[i].get().parameters().size(); ++k) {
    73                 if (!matches(*functions[i].get().parameters()[k]->type(), *functions[j].get().parameters()[k]->type())) {
    74                     same = false;
    75                     break;
    76                 }
    77             }
    78             if (same)
    79                 return false;
    80         }
    81        
    82         if (functions[i].get().name() == "operator&[]" && functions[i].get().parameters().size() == 2
    83             && is<AST::ArrayReferenceType>(static_cast<const AST::UnnamedType&>(*functions[i].get().parameters()[0]->type()))) {
    84             auto& type = static_cast<const AST::UnnamedType&>(*functions[i].get().parameters()[1]->type());
     120    auto passesStaticChecks = [&] (const AST::FunctionDeclaration& function) {
     121        if (function.name() == "operator&[]" && function.parameters().size() == 2
     122            && is<AST::ArrayReferenceType>(static_cast<const AST::UnnamedType&>(*function.parameters()[0]->type()))) {
     123            auto& type = static_cast<const AST::UnnamedType&>(*function.parameters()[1]->type());
    85124            if (is<AST::TypeReference>(type)) {
    86125                // FIXME: https://bugs.webkit.org/show_bug.cgi?id=198161 Shouldn't we already know whether the types have been resolved by now?
    … …  
    93132                }
    94133            }
    95         } else if (functions[i].get().name() == "operator.length" && functions[i].get().parameters().size() == 1
    96             && (is<AST::ArrayReferenceType>(static_cast<const AST::UnnamedType&>(*functions[i].get().parameters()[0]->type()))
    97             || is<AST::ArrayType>(static_cast<const AST::UnnamedType&>(*functions[i].get().parameters()[0]->type()))))
     134        } else if (function.name() == "operator.length" && function.parameters().size() == 1
     135            && (is<AST::ArrayReferenceType>(static_cast<const AST::UnnamedType&>(*function.parameters()[0]->type()))
     136            || is<AST::ArrayType>(static_cast<const AST::UnnamedType&>(*function.parameters()[0]->type()))))
    98137            return false;
    99         else if (functions[i].get().name() == "operator=="
    100             && functions[i].get().parameters().size() == 2
    101             && is<AST::ReferenceType>(static_cast<const AST::UnnamedType&>(*functions[i].get().parameters()[0]->type()))
    102             && is<AST::ReferenceType>(static_cast<const AST::UnnamedType&>(*functions[i].get().parameters()[1]->type()))
    103             && matches(*functions[i].get().parameters()[0]->type(), *functions[i].get().parameters()[1]->type()))
     138        else if (function.name() == "operator=="
     139            && function.parameters().size() == 2
     140            && is<AST::ReferenceType>(static_cast<const AST::UnnamedType&>(*function.parameters()[0]->type()))
     141            && is<AST::ReferenceType>(static_cast<const AST::UnnamedType&>(*function.parameters()[1]->type()))
     142            && matches(*function.parameters()[0]->type(), *function.parameters()[1]->type()))
     143            return false;
     144
     145        return true;
     146    };
     147
     148    HashSet<DuplicateFunctionKey, DuplicateFunctionKey::Hash, DuplicateFunctionKey::Traits> functions;
     149
     150    auto add = [&] (const AST::FunctionDeclaration& function) {
     151        auto addResult = functions.add(DuplicateFunctionKey { function });
     152        if (!addResult.isNewEntry)
     153            return false;
     154        return passesStaticChecks(function);
     155    };
     156
     157    for (auto& functionDefinition : program.functionDefinitions()) {
     158        if (!add(functionDefinition.get()))
    104159            return false;
    105160    }
     161
     162    for (auto& nativeFunctionDeclaration : program.nativeFunctionDeclarations()) {
     163        // Native function declarations are never equal to each other. So we don't need
     164        // to add them to the set, because they can't collide with each other. Instead, we
     165        // just check that no user-defined function is a duplicate.
     166        ASSERT(passesStaticChecks(nativeFunctionDeclaration.get()));
     167        if (functions.contains(DuplicateFunctionKey { nativeFunctionDeclaration.get() }))
     168            return false;
     169        ASSERT(add(nativeFunctionDeclaration.get()));
     170    }
     171
    106172    return true;
    107173}
Note: See TracChangeset for help on using the changeset viewer.