[WHLSL] The recursion checker should not have quadratic complexity
authorrmorisset@apple.com <rmorisset@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Thu, 11 Jul 2019 01:18:14 +0000 (01:18 +0000)
committerrmorisset@apple.com <rmorisset@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Thu, 11 Jul 2019 01:18:14 +0000 (01:18 +0000)
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:

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@247339 268f45cc-cd09-0410-ab3c-d52691b4dbfc

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

index 8c3cb20..406889e 100644 (file)
@@ -1,3 +1,21 @@
+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>
 
         Crash at WebCore::IDBServer::MemoryObjectStoreCursor::incrementReverseIterator
index a25fca7..6af88fe 100644 (file)
@@ -40,20 +40,29 @@ namespace WHLSL {
 // Makes sure there is no function recursion.
 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();
             return;
         }
 
         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);
+        }
     }
 
     void visit(AST::CallExpression& callExpression) override
@@ -63,7 +72,8 @@ private:
             checkErrorAndVisit(downcast<AST::FunctionDefinition>(callExpression.function()));
     }
 
-    HashSet<AST::FunctionDefinition*> m_visitingSet;
+    HashSet<AST::FunctionDefinition*> m_startedVisiting;
+    HashSet<AST::FunctionDefinition*> m_finishedVisiting;
 };
 
 bool checkRecursion(Program& program)