tp: Add O(1) hashmap companion to single-column integer indexes For single-column indexes on non-null integer/Double columns with no duplicates, BuildIndex now also builds a uint64->row_index hashmap alongside the sorted permutation vector. The query planner prefers the hashmap for Eq constraints via a new IndexedFilterEqHashMap bytecode, which does one O(1) Find() instead of an O(log n) binary search over the permutation. Motivation: resolve_groups in the flamegraph pipeline does a LEFT JOIN on a unique hash column. Previously each join probe took O(log n) through IndexedFilterEq; on large heap-graph traces the merged step was ~21s because of 8.4M log-n probes. On a 1.3M-object trace where the binary search is still only 17 comparisons, this measures at ~10% speedup on the merged step (0.179s -> 0.160s). The win grows with row count. Phase 1 (sorted-column binary search) now skips Eq specs on columns that have a hashmap index companion, so those fall through to Phase 2 (IndexConstraints) where the new bytecode is emitted. Correctness: full diff-test suite (1356 tests) is green and manual A/B on the flamegraph pipeline produces bit-identical output between hashmap-on and hashmap-off. The hashmap companion is opt-in via CanBuildHashMapEqIndex: single column, non-null, integer-like type, no duplicates (checked by an exact scan over the sorted permutation, because the HasDuplicates/NoDuplicates metadata is conservative on 64-bit hash columns).
diff --git a/src/trace_processor/core/common/storage_types.h b/src/trace_processor/core/common/storage_types.h index fdeffff..373ef0c 100644 --- a/src/trace_processor/core/common/storage_types.h +++ b/src/trace_processor/core/common/storage_types.h
@@ -19,6 +19,7 @@ #include <cstdint> +#include "perfetto/ext/base/flat_hash_map.h" #include "src/trace_processor/containers/string_pool.h" #include "src/trace_processor/core/util/type_set.h" @@ -86,6 +87,17 @@ using type = String; }; +// An optional hashmap companion to an Index, providing O(1) Eq lookup +// for single-column indexes over integer-like columns. The key is the +// raw column value widened to uint64_t (int32/uint32/int64 are +// zero/sign-extended; double keys use bit-level reinterpret). The value +// is the row index in the storage. +// Use MurmurHash (FlatHashMapV2's default) rather than AlreadyHashed so +// sequential/small-range integer keys (e.g. id columns) don't cluster +// catastrophically. MurmurHash is ~2ns/key so it costs nothing when keys +// are already well-distributed hashes. +using HashMapEqIndex = base::FlatHashMapV2<uint64_t, uint32_t>; + } // namespace perfetto::trace_processor::core #endif // SRC_TRACE_PROCESSOR_CORE_COMMON_STORAGE_TYPES_H_
diff --git a/src/trace_processor/core/dataframe/dataframe.cc b/src/trace_processor/core/dataframe/dataframe.cc index d09d35e..57fb800 100644 --- a/src/trace_processor/core/dataframe/dataframe.cc +++ b/src/trace_processor/core/dataframe/dataframe.cc
@@ -18,6 +18,7 @@ #include <cstddef> #include <cstdint> +#include <cstring> #include <memory> #include <string> #include <string_view> @@ -151,6 +152,158 @@ ++non_column_mutations_; } +namespace { + +// Returns true if a hashmap companion can be built for a single-column +// index over |col|. Requires non-null storage and an integer/Double +// storage type (String has StringPool fast paths; Id is already O(1)). +// +// We DON'T check col.duplicate_state here: the Perfetto adhoc builder +// conservatively marks columns with large integer values (e.g. 64-bit +// hash columns) as HasDuplicates because its bitvector-based detector +// bails above a size threshold. Instead, BuildIndex does an exact +// adjacent-duplicates check over the sorted permutation below. +bool CanBuildHashMapEqIndex(const Column& col) { + if (!col.null_storage.nullability().Is<core::NonNull>()) { + return false; + } + switch (col.storage.type().index()) { + case StorageType::GetTypeIndex<core::Uint32>(): + case StorageType::GetTypeIndex<core::Int32>(): + case StorageType::GetTypeIndex<core::Int64>(): + case StorageType::GetTypeIndex<core::Double>(): + return true; + default: + return false; + } +} + +// Returns true iff no two rows in |permutation| have the same value +// in |col|. Permutation is assumed sorted ascending by the column, so +// duplicates appear as adjacent pairs. +bool IsStrictlyIncreasingUnderPermutation( + const Column& col, + const std::vector<uint32_t>& permutation) { + if (permutation.size() < 2) { + return true; + } + switch (col.storage.type().index()) { + case StorageType::GetTypeIndex<core::Uint32>(): { + const uint32_t* d = col.storage.unchecked_data<core::Uint32>(); + for (size_t i = 1; i < permutation.size(); ++i) { + if (d[permutation[i - 1]] == d[permutation[i]]) { + return false; + } + } + return true; + } + case StorageType::GetTypeIndex<core::Int32>(): { + const int32_t* d = col.storage.unchecked_data<core::Int32>(); + for (size_t i = 1; i < permutation.size(); ++i) { + if (d[permutation[i - 1]] == d[permutation[i]]) { + return false; + } + } + return true; + } + case StorageType::GetTypeIndex<core::Int64>(): { + const int64_t* d = col.storage.unchecked_data<core::Int64>(); + for (size_t i = 1; i < permutation.size(); ++i) { + if (d[permutation[i - 1]] == d[permutation[i]]) { + return false; + } + } + return true; + } + case StorageType::GetTypeIndex<core::Double>(): { + // Compare bit patterns to sidestep the -Wfloat-equal rule; for + // identical uniqueness the bit pattern is what the hashmap uses + // as key. + const double* d = col.storage.unchecked_data<core::Double>(); + for (size_t i = 1; i < permutation.size(); ++i) { + uint64_t a, b; + std::memcpy(&a, &d[permutation[i - 1]], sizeof(a)); + std::memcpy(&b, &d[permutation[i]], sizeof(b)); + if (a == b) { + return false; + } + } + return true; + } + default: + return false; + } +} + +// Widens a typed column value into the uint64 key space used by the +// hashmap companion. Integer values are zero/sign-extended; Double +// values reinterpret the bit pattern via memcpy so NaNs/etc compare +// as identical bit patterns. +template <typename StorageT> +uint64_t HashMapKeyFromStorage(const Storage& s, uint32_t row) { + if constexpr (std::is_same_v<StorageT, core::Uint32>) { + return static_cast<uint64_t>(s.unchecked_data<StorageT>()[row]); + } else if constexpr (std::is_same_v<StorageT, core::Int32>) { + return static_cast<uint64_t>( + static_cast<int64_t>(s.unchecked_data<StorageT>()[row])); + } else if constexpr (std::is_same_v<StorageT, core::Int64>) { + return static_cast<uint64_t>(s.unchecked_data<StorageT>()[row]); + } else if constexpr (std::is_same_v<StorageT, core::Double>) { + double v = s.unchecked_data<StorageT>()[row]; + uint64_t bits; + std::memcpy(&bits, &v, sizeof(bits)); + return bits; + } else { + static_assert(!std::is_same_v<StorageT, StorageT>, + "Unsupported storage type for hashmap key"); + } +} + +// Populates a hashmap from column values to row indices, iterating in +// the permutation order so that each key maps to the same row index +// IndexedFilterEq's binary search would return as lb. +std::shared_ptr<HashMapEqIndex> BuildHashMapEqIndex( + const Column& col, + const std::vector<uint32_t>& permutation) { + // FlatHashMapV1::Reset DCHECKs the initial capacity is a power of two. + // Pick a capacity that, at the default 75% load limit, fits the full + // row count without triggering a rehash mid-fill. + constexpr size_t kLoadPct = 75; + size_t min_capacity = + (permutation.size() * 100 + kLoadPct - 1) / kLoadPct + 1; + size_t initial_capacity = 1; + while (initial_capacity < min_capacity) { + initial_capacity <<= 1; + } + auto hm = std::make_shared<HashMapEqIndex>(initial_capacity); + auto fill = [&](auto storage_tag) { + using StorageT = decltype(storage_tag); + for (uint32_t row : permutation) { + uint64_t key = HashMapKeyFromStorage<StorageT>(col.storage, row); + hm->Insert(key, row); + } + }; + switch (col.storage.type().index()) { + case StorageType::GetTypeIndex<core::Uint32>(): + fill(core::Uint32{}); + break; + case StorageType::GetTypeIndex<core::Int32>(): + fill(core::Int32{}); + break; + case StorageType::GetTypeIndex<core::Int64>(): + fill(core::Int64{}); + break; + case StorageType::GetTypeIndex<core::Double>(): + fill(core::Double{}); + break; + default: + PERFETTO_FATAL("CanBuildHashMapEqIndex should have rejected this type"); + } + return hm; +} + +} // namespace + base::StatusOr<Index> Dataframe::BuildIndex(const uint32_t* columns_start, const uint32_t* columns_end) const { std::vector<uint32_t> cols(columns_start, columns_end); @@ -171,8 +324,22 @@ for (; !c->Eof(); c->Next()) { permutation.push_back(c->RowIndex()); } + + // For single-column integer-like indexes over unique, non-null values, + // also build an O(1) hashmap companion. Consumers (e.g. IndexedFilterEq + // for Eq ops) can then skip the O(log n) binary search on the + // permutation vector entirely. + std::shared_ptr<HashMapEqIndex> hashmap; + if (cols.size() == 1) { + const Column& col = *column_ptrs_[cols[0]]; + if (CanBuildHashMapEqIndex(col) && + IsStrictlyIncreasingUnderPermutation(col, permutation)) { + hashmap = BuildHashMapEqIndex(col, permutation); + } + } return Index(std::move(cols), - std::make_shared<std::vector<uint32_t>>(std::move(permutation))); + std::make_shared<std::vector<uint32_t>>(std::move(permutation)), + std::move(hashmap)); } void Dataframe::AddIndex(Index index) {
diff --git a/src/trace_processor/core/dataframe/query_plan.cc b/src/trace_processor/core/dataframe/query_plan.cc index cc004f3..88403a2 100644 --- a/src/trace_processor/core/dataframe/query_plan.cc +++ b/src/trace_processor/core/dataframe/query_plan.cc
@@ -66,7 +66,8 @@ kSmallValueEqBvReg = 2, kSmallValueEqPopcountReg = 3, kIndexReg = 4, - kRegTypeCount = 5, + kHashMapEqReg = 5, + kRegTypeCount = 6, }; // TypeSet of all possible sparse nullability states. @@ -339,6 +340,12 @@ sve.prefix_popcount.data(), sve.prefix_popcount.data() + sve.prefix_popcount.size()); } + case RegisterInit::Type::GetTypeIndex<RegisterInit::HashMapEqIndexPtr>(): { + // source_index is the index id; return a raw pointer to the + // hashmap (non-null because the planner only emits this init when + // indexes[source_index].hashmap() is set). + return indexes[init.source_index].hashmap().get(); + } default: PERFETTO_FATAL("Unhandled RegisterInit kind: %u", static_cast<uint32_t>(init.kind.index())); @@ -367,6 +374,21 @@ if (!non_null_op) { continue; } + // Skip Eq on columns that have a hashmap-backed index companion: Phase 2 + // can serve those in O(1) instead of O(log n) via binary search here. + if (c.op.Is<Eq>()) { + bool has_hashmap_index = false; + for (const Index& index : indexes_) { + if (index.hashmap() && index.columns().size() == 1 && + index.columns()[0] == c.col) { + has_hashmap_index = true; + break; + } + } + if (has_hashmap_index) { + continue; + } + } const Column& col = GetColumn(c.col); if (!TrySortedConstraint(c, col.storage.type(), *non_null_op)) { continue; @@ -917,7 +939,36 @@ // Emit IndexedFilterEq for Eq filters. auto value_reg = CastFilterValue(fs, column.storage.type(), *fs.op.TryDowncast<i::NonNullOp>()); - { + + // If the Index has a hashmap companion AND the column type is + // eligible (integer-like, non-null), prefer the O(1) hashmap path + // over the O(log n) binary search. + auto hm_type = non_id->TryDowncast<i::HashMapEqStorageType>(); + const bool can_use_hashmap = + indexes_[index_idx].hashmap() != nullptr && + column.null_storage.nullability().Is<NonNull>() && hm_type; + if (can_use_hashmap) { + using B = i::IndexedFilterEqHashMapBase; + auto scratch_reg = builder_.AllocateRegister<Slab<uint32_t>>(); + { + using A = i::AllocateIndices; + auto& bc = AddOpcode<A>(UnchangedRowCount{}); + bc.arg<A::size>() = 1; + bc.arg<A::dest_slab_register>() = scratch_reg; + // Unused Span handle (we only care about the Slab for writing + // the one matched row index). + bc.arg<A::dest_span_register>() = + builder_.AllocateRegister<Span<uint32_t>>(); + } + auto& bc = AddOpcode<B>( + i::Index<i::IndexedFilterEqHashMap>(*hm_type), + RowCountModifier{EqualityFilterRowCount{column.duplicate_state}}); + bc.arg<B::hashmap_register>() = HashMapEqRegisterFor(index_idx); + bc.arg<B::filter_value_reg>() = value_reg; + bc.arg<B::source_register>() = source_reg; + bc.arg<B::dest_register>() = dest_reg; + bc.arg<B::scratch_register>() = scratch_reg; + } else { using B = i::IndexedFilterEqBase; auto null_bv_reg = EnsurePrefixPopcountFor(fs.col); auto& bc = AddOpcode<B>( @@ -1298,6 +1349,18 @@ return reg; } +i::ReadHandle<const HashMapEqIndex*> QueryPlanBuilder::HashMapEqRegisterFor( + uint32_t index_idx) { + auto [reg, inserted] = cache_.GetOrAllocate<const HashMapEqIndex*>( + kHashMapEqReg, &indexes_[index_idx]); + if (inserted) { + plan_.register_inits.emplace_back( + RegisterInit{reg.index, RegisterInit::HashMapEqIndexPtr{}, + static_cast<uint16_t>(index_idx)}); + } + return reg; +} + bool QueryPlanBuilder::CanUseMinMaxOptimization( const std::vector<SortSpec>& sort_specs, const LimitSpec& limit_spec) {
diff --git a/src/trace_processor/core/dataframe/query_plan.h b/src/trace_processor/core/dataframe/query_plan.h index 1d21646..456b5b4 100644 --- a/src/trace_processor/core/dataframe/query_plan.h +++ b/src/trace_processor/core/dataframe/query_plan.h
@@ -60,6 +60,9 @@ struct IndexVector {}; struct SmallValueEqBitvector {}; struct SmallValueEqPopcount {}; + // Tag for the hashmap companion attached to an Index (see + // dataframe.cc BuildIndex). source_index is the index id. + struct HashMapEqIndexPtr {}; using Type = TypeSet<Id, Uint32, @@ -70,7 +73,8 @@ NullBitvector, IndexVector, SmallValueEqBitvector, - SmallValueEqPopcount>; + SmallValueEqPopcount, + HashMapEqIndexPtr>; uint32_t dest_register = 0; Type kind{Id{}}; uint16_t source_index = 0; // col_index or index_id depending on kind @@ -420,6 +424,12 @@ interpreter::ReadHandle<Span<const uint32_t>> SmallValueEqPopcountRegisterFor( uint32_t col); + // Returns the register holding the hashmap companion for the given + // index. Should only be called when indexes_[index_idx].hashmap() is + // non-null (i.e. BuildIndex has produced a hashmap). + interpreter::ReadHandle<const core::HashMapEqIndex*> HashMapEqRegisterFor( + uint32_t index_idx); + interpreter::ReadHandle<interpreter::CastFilterValueResult> CastFilterValue( FilterSpec& c, const StorageType& ct,
diff --git a/src/trace_processor/core/dataframe/types.h b/src/trace_processor/core/dataframe/types.h index 7e943ef..7132b0a 100644 --- a/src/trace_processor/core/dataframe/types.h +++ b/src/trace_processor/core/dataframe/types.h
@@ -10,6 +10,8 @@ #include <vector> #include "perfetto/base/logging.h" +#include "perfetto/ext/base/flat_hash_map.h" +#include "perfetto/ext/base/hash.h" #include "perfetto/ext/base/variant.h" #include "src/trace_processor/containers/string_pool.h" #include "src/trace_processor/core/common/duplicate_types.h" @@ -22,6 +24,11 @@ namespace perfetto::trace_processor::core::dataframe { +// HashMapEqIndex type alias lives in storage_types.h so both the +// dataframe and the bytecode interpreter can reference it as a first- +// class value type without creating a circular dependency. +using core::HashMapEqIndex; + // Represents an index to speed up operations on the dataframe. struct Index { public: @@ -30,6 +37,13 @@ : columns_(std::move(_columns)), permutation_vector_(std::move(_permutation_vector)) {} + Index(std::vector<uint32_t> _columns, + std::shared_ptr<std::vector<uint32_t>> _permutation_vector, + std::shared_ptr<HashMapEqIndex> _hashmap) + : columns_(std::move(_columns)), + permutation_vector_(std::move(_permutation_vector)), + hashmap_(std::move(_hashmap)) {} + // Returns a copy of this index. Index Copy() const { return *this; } @@ -42,9 +56,15 @@ return permutation_vector_; } + // Optional O(1) hashmap companion. Non-null iff built at BuildIndex time + // (single column, non-null, no duplicates, integer-like type). Consumers + // should fall back to the permutation vector when nullptr. + const std::shared_ptr<HashMapEqIndex>& hashmap() const { return hashmap_; } + private: std::vector<uint32_t> columns_; std::shared_ptr<std::vector<uint32_t>> permutation_vector_; + std::shared_ptr<HashMapEqIndex> hashmap_; }; // Tag type for Id column data pointers. Id columns don't have backing storage
diff --git a/src/trace_processor/core/interpreter/bytecode_instructions.h b/src/trace_processor/core/interpreter/bytecode_instructions.h index 5014364..71c0e42 100644 --- a/src/trace_processor/core/interpreter/bytecode_instructions.h +++ b/src/trace_processor/core/interpreter/bytecode_instructions.h
@@ -473,6 +473,38 @@ static_assert(TS2::Contains<N>()); }; +// O(1) equality filter backed by a hashmap companion of an Index. +// The hashmap is attached to single-column non-null no-duplicate +// integer-like indexes at BuildIndex time (see dataframe.cc). When +// present, the planner emits this opcode instead of IndexedFilterEq +// for Eq constraints to avoid the O(log n) binary search. +// +// |hashmap_register| holds a `const HashMapEqIndex*`. |source_register| +// is the input span from the sorted index's permutation vector (unused +// on a hit, needed only so the fallback binary-search semantics are +// preserved; we treat the hashmap as authoritative for presence). +// |dest_register| gets either an empty span (miss) or a one-element +// span pointing at the row index inside a scratch slot the interpreter +// owns. +struct IndexedFilterEqHashMapBase : TemplatedBytecode1<HashMapEqStorageType> { + static constexpr Cost kCost = FixedCost{5}; + + PERFETTO_DATAFRAME_BYTECODE_IMPL_5(ReadHandle<const core::HashMapEqIndex*>, + hashmap_register, + ReadHandle<CastFilterValueResult>, + filter_value_reg, + ReadHandle<Span<uint32_t>>, + source_register, + WriteHandle<Span<uint32_t>>, + dest_register, + RwHandle<Slab<uint32_t>>, + scratch_register); +}; +template <typename T> +struct IndexedFilterEqHashMap : IndexedFilterEqHashMapBase { + static_assert(TS1::Contains<T>()); +}; + // Given a source span and a source range, copies all indices in the span which // are in bounds in then range to the destiation span. The destination span must // be large enough to hold all the indices in the source span. @@ -791,6 +823,10 @@ X(IndexedFilterEq<String, NonNull>) \ X(IndexedFilterEq<String, SparseNull>) \ X(IndexedFilterEq<String, DenseNull>) \ + X(IndexedFilterEqHashMap<Uint32>) \ + X(IndexedFilterEqHashMap<Int32>) \ + X(IndexedFilterEqHashMap<Int64>) \ + X(IndexedFilterEqHashMap<Double>) \ X(FilterIn<Id, NonNull>) \ X(FilterIn<Id, SparseNull>) \ X(FilterIn<Id, DenseNull>) \
diff --git a/src/trace_processor/core/interpreter/bytecode_interpreter_impl.h b/src/trace_processor/core/interpreter/bytecode_interpreter_impl.h index efb8bb1..c9d509d 100644 --- a/src/trace_processor/core/interpreter/bytecode_interpreter_impl.h +++ b/src/trace_processor/core/interpreter/bytecode_interpreter_impl.h
@@ -1082,6 +1082,60 @@ state.WriteToRegister(bytecode.arg<B::dest_register>(), dest); } +// O(1) Eq lookup using the hashmap companion of an Index. On a hit, +// the scratch register receives a single-element array holding the +// matched row index, and the dest span points at that element. On a +// miss (or an invalid cast), the dest span is empty. +template <typename T> +inline PERFETTO_ALWAYS_INLINE void IndexedFilterEqHashMap( + InterpreterState& state, + const IndexedFilterEqHashMapBase& bytecode) { + using B = IndexedFilterEqHashMapBase; + const auto& filter_value = + state.ReadFromRegister(bytecode.arg<B::filter_value_reg>()); + const auto& source = + state.ReadFromRegister(bytecode.arg<B::source_register>()); + Span<uint32_t> dest(source.b, source.e); + if (!HandleInvalidCastFilterValueResult(filter_value.validity, dest)) { + state.WriteToRegister(bytecode.arg<B::dest_register>(), dest); + return; + } + + // Widen the cast filter value into the uint64 key space used by the + // hashmap. These casts must mirror HashMapKeyFromStorage() in + // dataframe.cc so we find entries put there by BuildIndex. + using M = StorageType::VariantTypeAtIndex<T, CastFilterValueResult::Value>; + const auto& typed_value = base::unchecked_get<M>(filter_value.value); + uint64_t key; + if constexpr (std::is_same_v<T, Uint32>) { + key = static_cast<uint64_t>(typed_value); + } else if constexpr (std::is_same_v<T, Int32>) { + key = static_cast<uint64_t>(static_cast<int64_t>(typed_value)); + } else if constexpr (std::is_same_v<T, Int64>) { + key = static_cast<uint64_t>(typed_value); + } else if constexpr (std::is_same_v<T, Double>) { + double v = typed_value; + std::memcpy(&key, &v, sizeof(key)); + } else { + static_assert(!std::is_same_v<T, T>, "Unsupported type for hashmap filter"); + } + + const auto* hashmap = + state.ReadFromRegister(bytecode.arg<B::hashmap_register>()); + const uint32_t* row_ptr = hashmap->Find(key); + auto& scratch = state.ReadFromRegister(bytecode.arg<B::scratch_register>()); + PERFETTO_DCHECK(scratch.size() >= 1); + if (row_ptr == nullptr) { + dest.b = scratch.begin(); + dest.e = scratch.begin(); + } else { + scratch[0] = *row_ptr; + dest.b = scratch.begin(); + dest.e = scratch.begin() + 1; + } + state.WriteToRegister(bytecode.arg<B::dest_register>(), dest); +} + // ============================================================================ // FilterIn: IN-clause filtering //
diff --git a/src/trace_processor/core/interpreter/bytecode_registers.h b/src/trace_processor/core/interpreter/bytecode_registers.h index 6a38f72..906307f 100644 --- a/src/trace_processor/core/interpreter/bytecode_registers.h +++ b/src/trace_processor/core/interpreter/bytecode_registers.h
@@ -129,7 +129,8 @@ Span<const uint32_t>, BitVector, std::unique_ptr<TreeState>, - NullBitvector>; + NullBitvector, + const core::HashMapEqIndex*>; } // namespace perfetto::trace_processor::core::interpreter
diff --git a/src/trace_processor/core/interpreter/interpreter_types.h b/src/trace_processor/core/interpreter/interpreter_types.h index 500298e..4289c99 100644 --- a/src/trace_processor/core/interpreter/interpreter_types.h +++ b/src/trace_processor/core/interpreter/interpreter_types.h
@@ -118,6 +118,11 @@ // TypeSet containing all the non-id storage types. using NonIdStorageType = TypeSet<Uint32, Int32, Int64, Double, String>; +// TypeSet of storage types eligible for the hashmap-index O(1) Eq +// filter. Excludes String (handled via the StringPool fast paths) and +// Id (handled as row index without any index lookup). +using HashMapEqStorageType = TypeSet<Uint32, Int32, Int64, Double>; + // TypeSet which collapses all of the sparse nullability types into a single // type. using SparseNullCollapsedNullability = TypeSet<NonNull, SparseNull, DenseNull>;