Add deduplication logic to BitTableBuilder.

Test: test-art-host-gtest-stack_map_test
Test: test-art-host-gtest-bit_table_test
Change-Id: Ide5d38f6e9f111e0583ff7934f81b266b9d0d6ca

3 files changed, 81 insertions, 1 deletions

diff --git a/libartbase/base/bit_table.h b/libartbase/base/bit_table.h
index 54a2415c0e..fbded2785c 100644
--- a/libartbase/base/bit_table.h
+++ b/libartbase/base/bit_table.h
@@ -160,17 +160,60 @@ class BitTableBuilder {
   static constexpr size_t kNumColumns = sizeof(T) / sizeof(uint32_t);
 
   explicit BitTableBuilder(ScopedArenaAllocator* allocator)
-      : rows_(allocator->Adapter(kArenaAllocBitTableBuilder)) {
+      : rows_(allocator->Adapter(kArenaAllocBitTableBuilder)),
+        dedup_(8, allocator->Adapter(kArenaAllocBitTableBuilder)) {
   }
 
   T& operator[](size_t row) { return rows_[row]; }
   const T& operator[](size_t row) const { return rows_[row]; }
   size_t size() const { return rows_.size(); }
 
+  // Append given value to the vector without de-duplication.
+  // This will not add the element to the dedup map to avoid its associated costs.
   void Add(T value) {
     rows_.push_back(value);
   }
 
+  // Append given list of values and return the index of the first value.
+  // If the exact same set of values was already added, return the old index.
+  uint32_t Dedup(T* values, size_t count = 1) {
+    FNVHash<MemoryRegion> hasher;
+    uint32_t hash = hasher(MemoryRegion(values, sizeof(T) * count));
+
+    // Check if we have already added identical set of values.
+    auto range = dedup_.equal_range(hash);
+    for (auto it = range.first; it != range.second; ++it) {
+      uint32_t index = it->second;
+      if (count <= size() - index &&
+          std::equal(values,
+                     values + count,
+                     &rows_[index],
+                     [](const T& lhs, const T& rhs) {
+                       return memcmp(&lhs, &rhs, sizeof(T)) == 0;
+                     })) {
+        return index;
+      }
+    }
+
+    // Add the set of values and add the index to the dedup map.
+    uint32_t index = size();
+    rows_.insert(rows_.end(), values, values + count);
+    dedup_.emplace(hash, index);
+    return index;
+  }
+
+  // Check if the table already contains given values starting at the given index.
+  bool RangeEquals(uint32_t index, T* values, size_t count = 1) {
+    DCHECK_LE(index, size());
+    DCHECK_LE(count, size() - index);
+    for (uint32_t i = 0; i < count; i++) {
+      if (memcmp(&values[i], &rows_[index + i], sizeof(T)) != 0) {
+        return false;
+      }
+    }
+    return true;
+  }
+
   ALWAYS_INLINE uint32_t Get(uint32_t row, uint32_t column) const {
     DCHECK_LT(row, size());
     DCHECK_LT(column, kNumColumns);
@@ -237,6 +280,7 @@ class BitTableBuilder {
 
  protected:
   ScopedArenaDeque<T> rows_;
+  ScopedArenaUnorderedMultimap<uint32_t, uint32_t> dedup_;  // Hash -> row index.
 };
 
 template<typename T>
diff --git a/libartbase/base/bit_table_test.cc b/libartbase/base/bit_table_test.cc
index e6f0d53541..f579440199 100644
--- a/libartbase/base/bit_table_test.cc
+++ b/libartbase/base/bit_table_test.cc
@@ -142,4 +142,32 @@ TEST(BitTableTest, TestBigTable) {
   EXPECT_EQ(32u, table.NumColumnBits(3));
 }
 
+TEST(BitTableTest, TestDedup) {
+  MallocArenaPool pool;
+  ArenaStack arena_stack(&pool);
+  ScopedArenaAllocator allocator(&arena_stack);
+
+  struct RowData {
+    uint32_t a;
+    uint32_t b;
+  };
+  BitTableBuilder<RowData> builder(&allocator);
+  RowData value0{1, 2};
+  RowData value1{3, 4};
+  RowData value2{56948505, 0};
+  RowData value3{67108869, 0};
+  FNVHash<MemoryRegion> hasher;
+  EXPECT_EQ(hasher(MemoryRegion(&value2, sizeof(RowData))),
+            hasher(MemoryRegion(&value3, sizeof(RowData))));  // Test hash collision.
+  EXPECT_EQ(0u, builder.Dedup(&value0));
+  EXPECT_EQ(1u, builder.Dedup(&value1));
+  EXPECT_EQ(2u, builder.Dedup(&value2));
+  EXPECT_EQ(3u, builder.Dedup(&value3));
+  EXPECT_EQ(0u, builder.Dedup(&value0));
+  EXPECT_EQ(1u, builder.Dedup(&value1));
+  EXPECT_EQ(2u, builder.Dedup(&value2));
+  EXPECT_EQ(3u, builder.Dedup(&value3));
+  EXPECT_EQ(4u, builder.size());
+}
+
 }  // namespace art
diff --git a/libartbase/base/scoped_arena_containers.h b/libartbase/base/scoped_arena_containers.h
index 41939816f5..44d7ebbc96 100644
--- a/libartbase/base/scoped_arena_containers.h
+++ b/libartbase/base/scoped_arena_containers.h
@@ -86,6 +86,14 @@ template <typename K, typename V, class Hash = std::hash<K>, class KeyEqual = st
 using ScopedArenaUnorderedMap =
     std::unordered_map<K, V, Hash, KeyEqual, ScopedArenaAllocatorAdapter<std::pair<const K, V>>>;
 
+template <typename K, typename V, class Hash = std::hash<K>, class KeyEqual = std::equal_to<K>>
+using ScopedArenaUnorderedMultimap =
+    std::unordered_multimap<K,
+                            V,
+                            Hash,
+                            KeyEqual,
+                            ScopedArenaAllocatorAdapter<std::pair<const K, V>>>;
+
 // Implementation details below.
 
 template <>