commit 6052d41d5137c5d1e3421355c68168ab3d5a93fb
author Ben Clayton <bclayton@google.com> Fri Apr 23 18:21:34 2021 +0000
committer Commit Bot service account <commit-bot@chromium.org> Fri Apr 23 18:21:34 2021 +0000
tree e577523aed6f153eaa0c7e29e5859353b8306993
parent b205b872ae84bf42b9063490c65a9404526c347c

sem::Alias::type_name(): Optimize complexity

Precalculate the type_name to reduce complexity from O(N²) to O(N).

Fixed: chromium:1199700
Fixed: chromium:1200936
Change-Id: Ifd16508ace42d4a686f06d58121cc106842df7d3
Reviewed-on: https://dawn-review.googlesource.com/c/tint/+/48691
Commit-Queue: Ben Clayton <bclayton@google.com>
Reviewed-by: Antonio Maiorano <amaiorano@google.com>

src/ast/alias.cc

diff --git a/src/ast/alias.cc b/src/ast/alias.cc
index 80e5957..a3b6a2c 100644
--- a/src/ast/alias.cc
+++ b/src/ast/alias.cc
@@ -25,7 +25,10 @@
              const Source& source,
              const Symbol& sym,
              Type* subtype)
-    : Base(program_id, source), symbol_(sym), subtype_(subtype) {
+    : Base(program_id, source),
+      symbol_(sym),
+      subtype_(subtype),
+      type_name_("__alias_" + sym.to_str() + subtype->type_name()) {
   TINT_ASSERT(subtype_);
 }
 
@@ -34,7 +37,7 @@
 Alias::~Alias() = default;
 
 std::string Alias::type_name() const {
-  return "__alias_" + symbol_.to_str() + subtype_->type_name();
+  return type_name_;
 }
 
 std::string Alias::FriendlyName(const SymbolTable& symbols) const {

src/ast/alias.h

diff --git a/src/ast/alias.h b/src/ast/alias.h
index d95387d..5f94ec6 100644
--- a/src/ast/alias.h
+++ b/src/ast/alias.h
@@ -60,6 +60,7 @@
  private:
   Symbol const symbol_;
   Type* const subtype_;
+  std::string const type_name_;
 };
 
 }  // namespace ast

src/ast/alias_test.cc

diff --git a/src/ast/alias_test.cc b/src/ast/alias_test.cc
index ae36314..3699aaf 100644
--- a/src/ast/alias_test.cc
+++ b/src/ast/alias_test.cc
@@ -57,6 +57,19 @@
   EXPECT_FALSE(ty->Is<Vector>());
 }
 
+// Check for linear-time evaluation of Alias::type_name().
+// If type_name() is non-linear, this test should noticeably stall.
+// See: crbug.com/1200936
+TEST_F(AstAliasTest, TypeName_LinearTime) {
+  Type* type = ty.i32();
+  for (int i = 0; i < 1024; i++) {
+    type = create<Alias>(Symbols().New(), type);
+  }
+  for (int i = 0; i < 16384; i++) {
+    type->type_name();
+  }
+}
+
 TEST_F(AstAliasTest, TypeName) {
   auto* at = create<Alias>(Sym("Particle"), create<I32>());
   EXPECT_EQ(at->type_name(), "__alias_$1__i32");

src/sem/alias_type.cc

diff --git a/src/sem/alias_type.cc b/src/sem/alias_type.cc
index d40001c..8e5e750 100644
--- a/src/sem/alias_type.cc
+++ b/src/sem/alias_type.cc
@@ -22,7 +22,9 @@
 namespace sem {
 
 Alias::Alias(const Symbol& sym, const Type* subtype)
-    : symbol_(sym), subtype_(subtype) {
+    : symbol_(sym),
+      subtype_(subtype),
+      type_name_("__alias_" + sym.to_str() + subtype->type_name()) {
   TINT_ASSERT(subtype_);
 }
 
@@ -31,7 +33,7 @@
 Alias::~Alias() = default;
 
 std::string Alias::type_name() const {
-  return "__alias_" + symbol_.to_str() + subtype_->type_name();
+  return type_name_;
 }
 
 std::string Alias::FriendlyName(const SymbolTable& symbols) const {

src/sem/alias_type.h

diff --git a/src/sem/alias_type.h b/src/sem/alias_type.h
index e4544e0..75ffe0a 100644
--- a/src/sem/alias_type.h
+++ b/src/sem/alias_type.h
@@ -54,7 +54,8 @@
 
  private:
   Symbol const symbol_;
-  const Type* const subtype_;
+  Type const* const subtype_;
+  std::string const type_name_;
 };
 
 }  // namespace sem

src/sem/alias_type_test.cc

diff --git a/src/sem/alias_type_test.cc b/src/sem/alias_type_test.cc
index 05bb852..62b96a1 100644
--- a/src/sem/alias_type_test.cc
+++ b/src/sem/alias_type_test.cc
@@ -46,6 +46,19 @@
   EXPECT_FALSE(ty->Is<Vector>());
 }
 
+// Check for linear-time evaluation of Alias::type_name().
+// If type_name() is non-linear, this test should noticeably stall.
+// See: crbug.com/1200936
+TEST_F(AliasTest, TypeName_LinearTime) {
+  Type* type = ty.i32();
+  for (int i = 0; i < 1024; i++) {
+    type = create<Alias>(Symbols().New(), type);
+  }
+  for (int i = 0; i < 16384; i++) {
+    type->type_name();
+  }
+}
+
 TEST_F(AliasTest, TypeName) {
   auto* at = create<Alias>(Sym("Particle"), ty.i32());
   EXPECT_EQ(at->type_name(), "__alias_$1__i32");