Add deduplication logic to BitTableBuilder.
Test: test-art-host-gtest-stack_map_test
Test: test-art-host-gtest-bit_table_test
Change-Id: Ide5d38f6e9f111e0583ff7934f81b266b9d0d6ca
diff --git a/libartbase/base/bit_table.h b/libartbase/base/bit_table.h
index 54a2415..fbded27 100644
--- a/libartbase/base/bit_table.h
+++ b/libartbase/base/bit_table.h
@@ -160,17 +160,60 @@
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 @@
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 e6f0d53..f579440 100644
--- a/libartbase/base/bit_table_test.cc
+++ b/libartbase/base/bit_table_test.cc
@@ -142,4 +142,32 @@
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 4193981..44d7ebb 100644
--- a/libartbase/base/scoped_arena_containers.h
+++ b/libartbase/base/scoped_arena_containers.h
@@ -86,6 +86,14 @@
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 <>