Changeset 247339 in webkit

Timestamp:

Jul 10, 2019 6:18:14 PM (5 years ago)

Author:

rmorisset@apple.com

Message:

[WHLSL] The recursion checker should not have quadratic complexity
​https://bugs.webkit.org/show_bug.cgi?id=199688

Reviewed by Saam Barati.

I fix it by using two different hash sets, tracking which functions we have started visiting, and which we have finished visiting.
The difference are those that are currently "on the stack", and calling any of those is an error.
As a bonus, I also overrode visit(Program&), so that we only bother visiting function definitions.

On whlsl-compute.html ran 5 times, this patch reduces the time spent in the recursion checker from 26ms to 12ms.
It is likely to be a much bigger win on larger programs (since it took the complexity from quadratic to linear).

No new tests as there is no intended functional change.

• Modules/webgpu/WHLSL/WHLSLRecursionChecker.cpp:

Location:

trunk/Source/WebCore

Files:

• ChangeLog (modified) (1 diff)
• Modules/webgpu/WHLSL/WHLSLRecursionChecker.cpp (modified) (3 diffs)

trunk/Source/WebCore/ChangeLog

@@ +1 @@
+2019-07-10  Robin Morisset  <rmorisset@apple.com>
+
+        [WHLSL] The recursion checker should not have quadratic complexity
+        https://bugs.webkit.org/show_bug.cgi?id=199688
+
+        Reviewed by Saam Barati.
+
+        I fix it by using two different hash sets, tracking which functions we have started visiting, and which we have finished visiting.
+        The difference are those that are currently "on the stack", and calling any of those is an error.
+        As a bonus, I also overrode visit(Program&), so that we only bother visiting function definitions.
+
+        On whlsl-compute.html ran 5 times, this patch reduces the time spent in the recursion checker from 26ms to 12ms.
+        It is likely to be a much bigger win on larger programs (since it took the complexity from quadratic to linear).
+
+        No new tests as there is no intended functional change.
+
+        * Modules/webgpu/WHLSL/WHLSLRecursionChecker.cpp:
+
 2019-07-10  Sihui Liu  <sihui_liu@apple.com>
 

trunk/Source/WebCore/Modules/webgpu/WHLSL/WHLSLRecursionChecker.cpp

@@ -41 +41 @@
 class RecursionChecker : public Visitor {
 private:
+    void visit(Program& program) override
+    {
+        for (auto& functionDefinition : program.functionDefinitions())
+            checkErrorAndVisit(functionDefinition);
+    }
+
     void visit(AST::FunctionDefinition& functionDefinition) override
     {
-        auto addResult = m_visitingSet.add(&functionDefinition);
+        if (m_finishedVisiting.contains(&functionDefinition))
+            return;
+
+        auto addResult = m_startedVisiting.add(&functionDefinition);
         if (!addResult.isNewEntry) {
             setError();
@@ -50 +59 @@
 
         Visitor::visit(functionDefinition);
-        if (error())
-            return;
 
-        auto success = m_visitingSet.remove(&functionDefinition);
-        ASSERT_UNUSED(success, success);
+        {
+            auto addResult = m_finishedVisiting.add(&functionDefinition);
+            ASSERT_UNUSED(addResult, addResult.isNewEntry);
+        }
     }
 
@@ -64 +73 @@
     }
 
-    HashSet<AST::FunctionDefinition*> m_visitingSet;
+    HashSet<AST::FunctionDefinition*> m_startedVisiting;
+    HashSet<AST::FunctionDefinition*> m_finishedVisiting;
 };