Tests: Introduce a HashTable benchmark for "table thrashing"

Thrashing is what I call the situations where a table is mostly filled
with deleted markers, causing an increase in size (at least temporarily)
when a simple re-hash would be enough to get rid of those. This happens
when a hash table (especially with many elements) has a lot of deletes
and re-inserts done to it, which is what this benchmark does.

1 files changed, 18 insertions, 0 deletions

diff --git a/Tests/AK/TestHashTable.cpp b/Tests/AK/TestHashTable.cpp
index a521763e23..2e3ddc5582 100644
--- a/Tests/AK/TestHashTable.cpp
+++ b/Tests/AK/TestHashTable.cpp
@@ -234,3 +234,21 @@ TEST_CASE(capacity_leak)
     }
     EXPECT(table.capacity() < 100u);
 }
+
+// Inserting and removing a bunch of elements will "thrash" the table, leading to a lot of "deleted" markers.
+BENCHMARK_CASE(benchmark_thrashing)
+{
+    HashTable<int> table;
+    // Ensure that there needs to be some copying when rehashing.
+    table.set(3);
+    table.set(7);
+    table.set(11);
+    table.set(13);
+    for (int i = 0; i < 10'000; ++i) {
+        table.set(-i);
+    }
+    for (int i = 0; i < 10'000'000; ++i) {
+        table.set(i);
+        table.remove(i);
+    }
+}