From 67bd84251222099aae542e3871955824499f514b Mon Sep 17 00:00:00 2001
From: Thomas Lively <tlively@google.com>
Date: Wed, 4 Sep 2024 18:17:59 -0700
Subject: [NFC] Use Index instead of size_t in topological sort util (#6903)

This saves memory and could in principle improve performance, although a
quick experiment with 30 samples on ReorderGlobals did not yield a
statistically significant improvement. At any rate, using Index is more
consistent with other parts of the code base.
---
 test/gtest/topological-orders.cpp | 36 ++++++++++++++++++------------------
 1 file changed, 18 insertions(+), 18 deletions(-)

(limited to 'test')

diff --git a/test/gtest/topological-orders.cpp b/test/gtest/topological-orders.cpp
index 078b8dd5f..67c56cbdb 100644
--- a/test/gtest/topological-orders.cpp
+++ b/test/gtest/topological-orders.cpp
@@ -23,7 +23,7 @@
 
 using namespace wasm;
 
-using Graph = std::vector<std::vector<size_t>>;
+using Graph = TopologicalSort::Graph;
 
 TEST(TopologicalSortTest, Empty) {
   Graph graph;
@@ -36,7 +36,7 @@ TEST(TopologicalSortTest, Singleton) {
   TopologicalOrders orders(graph);
   auto it = orders.begin();
   ASSERT_NE(it, orders.end());
-  EXPECT_EQ(*it, std::vector<size_t>{0});
+  EXPECT_EQ(*it, std::vector<Index>{0});
   ++it;
   EXPECT_EQ(it, orders.end());
 }
@@ -44,8 +44,8 @@ TEST(TopologicalSortTest, Singleton) {
 TEST(TopologicalSortTest, Permutations) {
   Graph graph(3);
   TopologicalOrders orders(graph);
-  std::set<std::vector<size_t>> results(orders.begin(), orders.end());
-  std::set<std::vector<size_t>> expected{
+  std::set<std::vector<Index>> results(orders.begin(), orders.end());
+  std::set<std::vector<Index>> expected{
     {0, 1, 2},
     {0, 2, 1},
     {1, 0, 2},
@@ -57,14 +57,14 @@ TEST(TopologicalSortTest, Permutations) {
 }
 
 TEST(TopologicalSortTest, Chain) {
-  constexpr size_t n = 10;
+  constexpr Index n = 10;
   Graph graph(n);
-  for (size_t i = 1; i < n; ++i) {
+  for (Index i = 1; i < n; ++i) {
     graph[i].push_back(i - 1);
   }
   TopologicalOrders orders(graph);
-  std::set<std::vector<size_t>> results(orders.begin(), orders.end());
-  std::set<std::vector<size_t>> expected{{9, 8, 7, 6, 5, 4, 3, 2, 1, 0}};
+  std::set<std::vector<Index>> results(orders.begin(), orders.end());
+  std::set<std::vector<Index>> expected{{9, 8, 7, 6, 5, 4, 3, 2, 1, 0}};
   EXPECT_EQ(results, expected);
 }
 
@@ -73,8 +73,8 @@ TEST(TopologicalSortTest, TwoChains) {
   graph[0].push_back(2);
   graph[1].push_back(3);
   TopologicalOrders orders(graph);
-  std::set<std::vector<size_t>> results(orders.begin(), orders.end());
-  std::set<std::vector<size_t>> expected{
+  std::set<std::vector<Index>> results(orders.begin(), orders.end());
+  std::set<std::vector<Index>> expected{
     {0, 1, 2, 3},
     {0, 1, 3, 2},
     {0, 2, 1, 3},
@@ -92,8 +92,8 @@ TEST(TopologicalSortTest, Diamond) {
   graph[1].push_back(3);
   graph[2].push_back(3);
   TopologicalOrders orders(graph);
-  std::set<std::vector<size_t>> results(orders.begin(), orders.end());
-  std::set<std::vector<size_t>> expected{
+  std::set<std::vector<Index>> results(orders.begin(), orders.end());
+  std::set<std::vector<Index>> expected{
     {0, 1, 2, 3},
     {0, 2, 1, 3},
   };
@@ -112,12 +112,12 @@ TEST(MinTopologicalSortTest, SortStrings) {
 
 TEST(MinTopologicalSortTest, EmptyMinSort) {
   Graph graph(0);
-  EXPECT_EQ(TopologicalSort::minSort<>(graph), std::vector<size_t>{});
+  EXPECT_EQ(TopologicalSort::minSort<>(graph), std::vector<Index>{});
 }
 
 TEST(MinTopologicalSortTest, UnconstrainedMinSort) {
   Graph graph(3);
-  std::vector<size_t> expected{0, 1, 2};
+  std::vector<Index> expected{0, 1, 2};
   EXPECT_EQ(TopologicalSort::minSort(graph), expected);
 }
 
@@ -125,7 +125,7 @@ TEST(MinTopologicalSortTest, ReversedMinSort) {
   Graph graph(3);
   graph[2].push_back(1);
   graph[1].push_back(0);
-  std::vector<size_t> expected{2, 1, 0};
+  std::vector<Index> expected{2, 1, 0};
   EXPECT_EQ(TopologicalSort::minSort(graph), expected);
 }
 
@@ -133,7 +133,7 @@ TEST(MinTopologicalSortTest, OneBeforeZeroMinSort) {
   Graph graph(3);
   graph[1].push_back(0);
   // 2 last because it is greater than 1 and 0
-  std::vector<size_t> expected{1, 0, 2};
+  std::vector<Index> expected{1, 0, 2};
   EXPECT_EQ(TopologicalSort::minSort(graph), expected);
 }
 
@@ -141,7 +141,7 @@ TEST(MinTopologicalSortTest, TwoBeforeOneMinSort) {
   Graph graph(3);
   graph[2].push_back(1);
   // 0 first because it is less than 2 and 1
-  std::vector<size_t> expected{0, 2, 1};
+  std::vector<Index> expected{0, 2, 1};
   EXPECT_EQ(TopologicalSort::minSort(graph), expected);
 }
 
@@ -149,6 +149,6 @@ TEST(MinTopologicalSortTest, TwoBeforeZeroMinSort) {
   Graph graph(3);
   graph[2].push_back(0);
   // 1 first because it is less than 2 and zero is not eligible.
-  std::vector<size_t> expected{1, 2, 0};
+  std::vector<Index> expected{1, 2, 0};
   EXPECT_EQ(TopologicalSort::minSort(graph), expected);
 }
-- 
cgit v1.2.3