commit 4a92a3c904d6a4ce477b077281ce178305f551c1
author Ben Clayton <bclayton@google.com> Mon Jul 18 20:50:02 2022 +0000
committer Dawn LUCI CQ <dawn-scoped@luci-project-accounts.iam.gserviceaccount.com> Mon Jul 18 20:50:02 2022 +0000
tree 44d4c0be2f51eb2e345c65394f4d3047761f77c3
parent 8d73198aca5f1a83283068298c9bfd79640ca36b

tint: Optimize sem node lookup

Add a 'NodeID' to each ast::Node which is the sequentially allocated
index of the node. Use this in sem::Info to map the AST node to the
semantic node, instead of using a std::unordered_map.

Optimised very hot code by entirely eliminating map lookups, and
dramatically reducing cache misses (lookups are usually sequentually
ordered).

Timings running
'webgpu:shader,execution,expression,call,builtin,atan2:f32:inputSource="const";vectorize="_undef_"'
with dawn/node, using SwiftShader:

    Without change: 3.22647107s
    With change:    3.10578879s

Bug: tint:1613
Change-Id: I22ec48d933b2e5f9da04494bff4e979e6f7b1982
Reviewed-on: https://dawn-review.googlesource.com/c/dawn/+/96140
Commit-Queue: Ben Clayton <bclayton@google.com>
Kokoro: Kokoro <noreply+kokoro@google.com>
Reviewed-by: Dan Sinclair <dsinclair@chromium.org>

src/tint/program_builder.h

diff --git a/src/tint/program_builder.h b/src/tint/program_builder.h
index 9a4f7ca..c6b163f 100644
--- a/src/tint/program_builder.h
+++ b/src/tint/program_builder.h
@@ -299,6 +299,16 @@
     /// information
     bool IsValid() const;
 
+    /// @returns the last allocated (numerically highest) AST node identifier.
+    ast::NodeID LastAllocatedNodeID() const { return last_ast_node_id_; }
+
+    /// @returns the next sequentially unique node identifier.
+    ast::NodeID AllocateNodeID() {
+        auto out = ast::NodeID{last_ast_node_id_.value + 1};
+        last_ast_node_id_ = out;
+        return out;
+    }
+
     /// Creates a new ast::Node owned by the ProgramBuilder. When the
     /// ProgramBuilder is destructed, the ast::Node will also be destructed.
     /// @param source the Source of the node
@@ -307,7 +317,7 @@
     template <typename T, typename... ARGS>
     traits::EnableIfIsType<T, ast::Node>* create(const Source& source, ARGS&&... args) {
         AssertNotMoved();
-        return ast_nodes_.Create<T>(id_, source, std::forward<ARGS>(args)...);
+        return ast_nodes_.Create<T>(id_, AllocateNodeID(), source, std::forward<ARGS>(args)...);
     }
 
     /// Creates a new ast::Node owned by the ProgramBuilder, injecting the current
@@ -319,7 +329,7 @@
     template <typename T>
     traits::EnableIfIsType<T, ast::Node>* create() {
         AssertNotMoved();
-        return ast_nodes_.Create<T>(id_, source_);
+        return ast_nodes_.Create<T>(id_, AllocateNodeID(), source_);
     }
 
     /// Creates a new ast::Node owned by the ProgramBuilder, injecting the current
@@ -337,7 +347,7 @@
                      T>*
     create(ARG0&& arg0, ARGS&&... args) {
         AssertNotMoved();
-        return ast_nodes_.Create<T>(id_, source_, std::forward<ARG0>(arg0),
+        return ast_nodes_.Create<T>(id_, AllocateNodeID(), source_, std::forward<ARG0>(arg0),
                                     std::forward<ARGS>(args)...);
     }
 
@@ -2665,7 +2675,8 @@
     /// @param validation the validation to disable
     /// @returns the disable validation attribute pointer
     const ast::DisableValidationAttribute* Disable(ast::DisabledValidation validation) {
-        return ASTNodes().Create<ast::DisableValidationAttribute>(ID(), validation);
+        return ASTNodes().Create<ast::DisableValidationAttribute>(ID(), AllocateNodeID(),
+                                                                  validation);
     }
 
     /// Sets the current builder source to `src`
@@ -2774,6 +2785,7 @@
 
   private:
     ProgramID id_;
+    ast::NodeID last_ast_node_id_ = ast::NodeID{static_cast<decltype(ast::NodeID::value)>(0) - 1};
     sem::Manager types_;
     ASTNodeAllocator ast_nodes_;
     SemNodeAllocator sem_nodes_;