Merge "tp: dbv2: define finalized StorageOverlay functions"
diff --git a/BUILD b/BUILD
index cfc4829..81affad 100644
--- a/BUILD
+++ b/BUILD
@@ -1289,7 +1289,6 @@
"src/trace_processor/db/storage/numeric_storage.h",
"src/trace_processor/db/storage/storage.cc",
"src/trace_processor/db/storage/storage.h",
- "src/trace_processor/db/storage/storage_variants.h",
"src/trace_processor/db/storage/types.h",
],
)
diff --git a/src/trace_processor/db/null_overlay.cc b/src/trace_processor/db/null_overlay.cc
index db8c572..71b38f4 100644
--- a/src/trace_processor/db/null_overlay.cc
+++ b/src/trace_processor/db/null_overlay.cc
@@ -16,8 +16,6 @@
#include "src/trace_processor/db/null_overlay.h"
-#include "src/trace_processor/db/storage/storage_variants.h"
-
namespace perfetto {
namespace trace_processor {
namespace overlays {
diff --git a/src/trace_processor/db/storage/BUILD.gn b/src/trace_processor/db/storage/BUILD.gn
index b3fc3cf..81d3b5f 100644
--- a/src/trace_processor/db/storage/BUILD.gn
+++ b/src/trace_processor/db/storage/BUILD.gn
@@ -20,7 +20,6 @@
"numeric_storage.h",
"storage.cc",
"storage.h",
- "storage_variants.h",
"types.h",
]
deps = [
diff --git a/src/trace_processor/db/storage/numeric_storage.cc b/src/trace_processor/db/storage/numeric_storage.cc
index 81d40ac..eb1dd08 100644
--- a/src/trace_processor/db/storage/numeric_storage.cc
+++ b/src/trace_processor/db/storage/numeric_storage.cc
@@ -16,65 +16,347 @@
*/
#include "src/trace_processor/db/storage/numeric_storage.h"
-
-#include <variant>
+#include "src/trace_processor/containers/bit_vector.h"
+#include "src/trace_processor/containers/row_map.h"
+#include "src/trace_processor/db/storage/types.h"
namespace perfetto {
namespace trace_processor {
namespace storage {
-
namespace {
-// Templated part of FastPathComparison.
+// All viable numeric values for ColumnTypes.
+using NumericValue = std::variant<uint32_t, int32_t, int64_t, double_t>;
+
+// Using the fact that binary operators in std are operators() of classes, we
+// can wrap those classes in variants and use them for std::visit in
+// SerialComparators. This helps prevent excess templating and switches.
template <typename T>
-inline void TypedFastPathComparison(std::optional<NumericValue> val,
- FilterOp op,
- const T* start,
- uint32_t num_elements,
- BitVector::Builder& builder) {
- if (!val) {
- builder.Skip(num_elements);
- return;
+using FilterOpVariant = std::variant<std::greater<T>,
+ std::greater_equal<T>,
+ std::less<T>,
+ std::less_equal<T>,
+ std::equal_to<T>,
+ std::not_equal_to<T>>;
+
+// Based on SqlValue and ColumnType, casts SqlValue to proper type, returns
+// std::nullopt if SqlValue can't be cast and should be considered invalid for
+// comparison.
+inline std::optional<NumericValue> GetNumericTypeVariant(ColumnType type,
+ SqlValue val) {
+ if (val.is_null())
+ return std::nullopt;
+
+ switch (type) {
+ case ColumnType::kDouble:
+ return val.AsDouble();
+ case ColumnType::kInt64:
+ return val.AsLong();
+ case ColumnType::kInt32:
+ if (val.AsLong() > std::numeric_limits<int32_t>::max() ||
+ val.AsLong() < std::numeric_limits<int32_t>::min())
+ return std::nullopt;
+ return static_cast<int32_t>(val.AsLong());
+ case ColumnType::kUint32:
+ if (val.AsLong() > std::numeric_limits<uint32_t>::max() ||
+ val.AsLong() < std::numeric_limits<uint32_t>::min())
+ return std::nullopt;
+ return static_cast<uint32_t>(val.AsLong());
+ case ColumnType::kString:
+ case ColumnType::kDummy:
+ case ColumnType::kId:
+ return std::nullopt;
}
- std::visit(
- [val, start, num_elements, &builder](auto comparator) {
- T typed_val = std::get<T>(*val);
- for (uint32_t i = 0; i < num_elements; i += BitVector::kBitsInWord) {
- uint64_t word = 0;
- // This part should be optimised by SIMD and is expected to be fast.
- for (uint32_t k = 0; k < BitVector::kBitsInWord; ++k) {
- bool comp_result = comparator(start[i + k], typed_val);
- word |= static_cast<uint64_t>(comp_result) << k;
- }
- builder.AppendWord(word);
- }
- },
- GetFilterOpVariant<T>(op));
+ PERFETTO_FATAL("For GCC");
}
-// Templated part of SlowPathComparison.
+// Fetch std binary comparator class based on FilterOp. Can be used in
+// std::visit for comparison.
template <typename T>
-inline void TypedSlowPathComparison(std::optional<NumericValue> val,
- FilterOp op,
- const T* start,
- uint32_t num_elements,
- BitVector::Builder& builder) {
- if (!val) {
- builder.Skip(num_elements);
- return;
+inline FilterOpVariant<T> GetFilterOpVariant(FilterOp op) {
+ switch (op) {
+ case FilterOp::kEq:
+ return FilterOpVariant<T>(std::equal_to<T>());
+ case FilterOp::kNe:
+ return FilterOpVariant<T>(std::not_equal_to<T>());
+ case FilterOp::kGe:
+ return FilterOpVariant<T>(std::greater_equal<T>());
+ case FilterOp::kGt:
+ return FilterOpVariant<T>(std::greater<T>());
+ case FilterOp::kLe:
+ return FilterOpVariant<T>(std::less_equal<T>());
+ case FilterOp::kLt:
+ return FilterOpVariant<T>(std::less<T>());
+ case FilterOp::kGlob:
+ case FilterOp::kIsNotNull:
+ case FilterOp::kIsNull:
+ PERFETTO_FATAL("Not a valid operation on numeric type.");
}
- std::visit(
- [val, start, num_elements, &builder](auto comparator) {
- T typed_val = std::get<T>(*val);
- for (uint32_t i = 0; i < num_elements; ++i) {
- builder.Append(comparator(start[i], typed_val));
- }
+ PERFETTO_FATAL("For GCC");
+}
+
+uint32_t LowerBoundIntrinsic(const void* data,
+ NumericValue val,
+ RowMap::Range search_range) {
+ return std::visit(
+ [data, search_range](auto val_data) {
+ using T = decltype(val_data);
+ const T* typed_start = static_cast<const T*>(data);
+ auto lower = std::lower_bound(typed_start + search_range.start,
+ typed_start + search_range.end, val_data);
+ return static_cast<uint32_t>(std::distance(typed_start, lower));
},
- GetFilterOpVariant<T>(op));
+ val);
+}
+
+uint32_t UpperBoundIntrinsic(const void* data,
+ NumericValue val,
+ RowMap::Range search_range) {
+ return std::visit(
+ [data, search_range](auto val_data) {
+ using T = decltype(val_data);
+ const T* typed_start = static_cast<const T*>(data);
+ auto upper = std::upper_bound(typed_start + search_range.start,
+ typed_start + search_range.end, val_data);
+ return static_cast<uint32_t>(std::distance(typed_start, upper));
+ },
+ val);
+}
+
+uint32_t LowerBoundExtrinsic(const void* data,
+ NumericValue val,
+ uint32_t* indices,
+ uint32_t indices_count) {
+ return std::visit(
+ [data, indices, indices_count](auto val_data) {
+ using T = decltype(val_data);
+ const T* typed_start = static_cast<const T*>(data);
+ auto lower =
+ std::lower_bound(indices, indices + indices_count, val_data,
+ [typed_start](uint32_t index, T val) {
+ return typed_start[index] < val;
+ });
+ return static_cast<uint32_t>(std::distance(indices, lower));
+ },
+ val);
+}
+
+uint32_t UpperBoundExtrinsic(const void* data,
+ NumericValue val,
+ uint32_t* indices,
+ uint32_t indices_count) {
+ return std::visit(
+ [data, indices, indices_count](auto val_data) {
+ using T = decltype(val_data);
+ const T* typed_start = static_cast<const T*>(data);
+ auto upper =
+ std::upper_bound(indices, indices + indices_count, val_data,
+ [typed_start](T val, uint32_t index) {
+ return val < typed_start[index];
+ });
+ return static_cast<uint32_t>(std::distance(indices, upper));
+ },
+ val);
+}
+
+template <typename T, typename Comparator>
+void TypedLinearSearch(T typed_val,
+ const T* start,
+ Comparator comparator,
+ BitVector::Builder& builder) {
+ // Slow path: we compare <64 elements and append to get us to a word
+ // boundary.
+ const T* ptr = start;
+ uint32_t front_elements = builder.BitsUntilWordBoundaryOrFull();
+ for (uint32_t i = 0; i < front_elements; ++i) {
+ builder.Append(comparator(ptr[i], typed_val));
+ }
+ ptr += front_elements;
+
+ // Fast path: we compare as many groups of 64 elements as we can.
+ // This should be very easy for the compiler to auto-vectorize.
+ uint32_t fast_path_elements = builder.BitsInCompleteWordsUntilFull();
+ for (uint32_t i = 0; i < fast_path_elements; i += BitVector::kBitsInWord) {
+ uint64_t word = 0;
+ // This part should be optimised by SIMD and is expected to be fast.
+ for (uint32_t k = 0; k < BitVector::kBitsInWord; ++k) {
+ bool comp_result = comparator(start[i + k], typed_val);
+ word |= static_cast<uint64_t>(comp_result) << k;
+ }
+ builder.AppendWord(word);
+ }
+ ptr += fast_path_elements;
+
+ // Slow path: we compare <64 elements and append to fill the Builder.
+ uint32_t back_elements = builder.BitsUntilFull();
+ for (uint32_t i = 0; i < back_elements; ++i) {
+ builder.Append(comparator(ptr[i], typed_val));
+ }
+}
+
+template <typename T, typename Comparator>
+void TypedIndexSearch(T typed_val,
+ const T* start,
+ uint32_t* indices,
+ Comparator comparator,
+ BitVector::Builder& builder) {
+ // Slow path: we compare <64 elements and append to get us to a word
+ // boundary.
+ const T* ptr = start;
+ uint32_t front_elements = builder.BitsUntilWordBoundaryOrFull();
+ for (uint32_t i = 0; i < front_elements; ++i) {
+ builder.Append(comparator(ptr[indices[i]], typed_val));
+ }
+ ptr += front_elements;
+
+ // Fast path: we compare as many groups of 64 elements as we can.
+ // This should be very easy for the compiler to auto-vectorize.
+ uint32_t fast_path_elements = builder.BitsInCompleteWordsUntilFull();
+ for (uint32_t i = 0; i < fast_path_elements; i += BitVector::kBitsInWord) {
+ uint64_t word = 0;
+ // This part should be optimised by SIMD and is expected to be fast.
+ for (uint32_t k = 0; k < BitVector::kBitsInWord; ++k) {
+ bool comp_result = comparator(start[indices[i + k]], typed_val);
+ word |= static_cast<uint64_t>(comp_result) << k;
+ }
+ builder.AppendWord(word);
+ }
+ ptr += fast_path_elements;
+
+ // Slow path: we compare <64 elements and append to fill the Builder.
+ uint32_t back_elements = builder.BitsUntilFull();
+ for (uint32_t i = 0; i < back_elements; ++i) {
+ builder.Append(comparator(ptr[indices[i]], typed_val));
+ }
}
} // namespace
+BitVector NumericStorage::LinearSearch(FilterOp op,
+ SqlValue sql_val,
+ RowMap::Range range) const {
+ std::optional<NumericValue> val = GetNumericTypeVariant(type_, sql_val);
+ if (op == FilterOp::kIsNotNull)
+ return BitVector(size(), true);
+
+ if (!val.has_value() || op == FilterOp::kIsNull || op == FilterOp::kGlob)
+ return BitVector();
+
+ BitVector::Builder builder(range.end);
+ builder.Skip(range.start);
+ std::visit(
+ [this, range, op, &builder](auto val) {
+ using T = decltype(val);
+ auto* start = static_cast<const T*>(data_) + range.start;
+ std::visit(
+ [start, val, &builder](auto comparator) {
+ TypedLinearSearch(val, start, comparator, builder);
+ },
+ GetFilterOpVariant<T>(op));
+ },
+ *val);
+ return std::move(builder).Build();
+}
+
+BitVector NumericStorage::IndexSearch(FilterOp op,
+ SqlValue sql_val,
+ uint32_t* indices,
+ uint32_t indices_count) const {
+ std::optional<NumericValue> val = GetNumericTypeVariant(type_, sql_val);
+ if (op == FilterOp::kIsNotNull)
+ return BitVector(size(), true);
+
+ if (!val.has_value() || op == FilterOp::kIsNull || op == FilterOp::kGlob)
+ return BitVector();
+
+ BitVector::Builder builder(indices_count);
+ std::visit(
+ [this, indices, op, &builder](auto val) {
+ using T = decltype(val);
+ auto* start = static_cast<const T*>(data_);
+ std::visit(
+ [start, indices, val, &builder](auto comparator) {
+ TypedIndexSearch(val, start, indices, comparator, builder);
+ },
+ GetFilterOpVariant<T>(op));
+ },
+ *val);
+ return std::move(builder).Build();
+}
+
+RowMap::Range NumericStorage::BinarySearchIntrinsic(
+ FilterOp op,
+ SqlValue sql_val,
+ RowMap::Range search_range) const {
+ std::optional<NumericValue> val = GetNumericTypeVariant(type_, sql_val);
+ if (op == FilterOp::kIsNotNull)
+ return RowMap::Range(0, size());
+
+ if (!val.has_value() || op == FilterOp::kIsNull || op == FilterOp::kGlob)
+ return RowMap::Range();
+
+ switch (op) {
+ case FilterOp::kEq:
+ return RowMap::Range(LowerBoundIntrinsic(data_, *val, search_range),
+ UpperBoundIntrinsic(data_, *val, search_range));
+ case FilterOp::kLe:
+ return RowMap::Range(0, UpperBoundIntrinsic(data_, *val, search_range));
+ case FilterOp::kLt:
+ return RowMap::Range(0, LowerBoundIntrinsic(data_, *val, search_range));
+ case FilterOp::kGe:
+ return RowMap::Range(LowerBoundIntrinsic(data_, *val, search_range),
+ size_);
+ case FilterOp::kGt:
+ return RowMap::Range(UpperBoundIntrinsic(data_, *val, search_range),
+ size_);
+ case FilterOp::kNe:
+ case FilterOp::kIsNull:
+ case FilterOp::kIsNotNull:
+ case FilterOp::kGlob:
+ return RowMap::Range();
+ }
+ return RowMap::Range();
+}
+
+RowMap::Range NumericStorage::BinarySearchExtrinsic(
+ FilterOp op,
+ SqlValue sql_val,
+ uint32_t* indices,
+ uint32_t indices_count) const {
+ std::optional<NumericValue> val = GetNumericTypeVariant(type_, sql_val);
+
+ if (op == FilterOp::kIsNotNull)
+ return RowMap::Range(0, size());
+
+ if (!val.has_value() || op == FilterOp::kIsNull || op == FilterOp::kGlob)
+ return RowMap::Range();
+
+ switch (op) {
+ case FilterOp::kEq:
+ return RowMap::Range(
+ LowerBoundExtrinsic(data_, *val, indices, indices_count),
+ UpperBoundExtrinsic(data_, *val, indices, indices_count));
+ case FilterOp::kLe:
+ return RowMap::Range(
+ 0, UpperBoundExtrinsic(data_, *val, indices, indices_count));
+ case FilterOp::kLt:
+ return RowMap::Range(
+ 0, LowerBoundExtrinsic(data_, *val, indices, indices_count));
+ case FilterOp::kGe:
+ return RowMap::Range(
+ LowerBoundExtrinsic(data_, *val, indices, indices_count), size_);
+ case FilterOp::kGt:
+ return RowMap::Range(
+ UpperBoundExtrinsic(data_, *val, indices, indices_count), size_);
+ case FilterOp::kNe:
+ case FilterOp::kIsNull:
+ case FilterOp::kIsNotNull:
+ case FilterOp::kGlob:
+ return RowMap::Range();
+ }
+ return RowMap::Range();
+}
+
void NumericStorage::StableSort(uint32_t* rows, uint32_t rows_size) const {
NumericValue val = *GetNumericTypeVariant(type_, SqlValue::Long(0));
std::visit(
@@ -93,184 +375,6 @@
void NumericStorage::Sort(uint32_t*, uint32_t) const {}
-// Responsible for invoking templated version of FastPathComparison.
-void NumericStorage::LinearSearchAligned(FilterOp op,
- SqlValue sql_val,
- uint32_t offset,
- uint32_t num_elements,
- BitVector::Builder& builder) const {
- PERFETTO_DCHECK(num_elements % BitVector::kBitsInWord == 0);
- std::optional<NumericValue> val = GetNumericTypeVariant(type_, sql_val);
-
- // If the value is invalid we should just ignore those elements.
- if (!val.has_value() || op == FilterOp::kIsNotNull ||
- op == FilterOp::kIsNull || op == FilterOp::kGlob) {
- builder.Skip(num_elements);
- return;
- }
- std::visit(
- [this, op, offset, num_elements, &builder](auto num_val) {
- using T = decltype(num_val);
- auto* typed_start = static_cast<const T*>(data_) + offset;
- TypedFastPathComparison(num_val, op, typed_start, num_elements,
- builder);
- },
- *val);
-}
-
-// Responsible for invoking templated version of SlowPathComparison.
-void NumericStorage::LinearSearchUnaligned(FilterOp op,
- SqlValue sql_val,
- uint32_t offset,
- uint32_t num_elements,
- BitVector::Builder& builder) const {
- std::optional<NumericValue> val = GetNumericTypeVariant(type_, sql_val);
-
- // If the value is invalid we should just ignore those elements.
- if (!val.has_value() || op == FilterOp::kIsNotNull ||
- op == FilterOp::kIsNull || op == FilterOp::kGlob) {
- builder.Skip(num_elements);
- return;
- }
-
- std::visit(
- [this, op, offset, num_elements, &builder](auto val) {
- using T = decltype(val);
- auto* typed_start = static_cast<const T*>(data_) + offset;
- TypedSlowPathComparison(val, op, typed_start, num_elements, builder);
- },
- *val);
-}
-
-uint32_t NumericStorage::UpperBoundIndex(NumericValue val,
- Range search_range) const {
- return std::visit(
- [this, search_range](auto val_data) {
- using T = decltype(val_data);
- const T* typed_start = static_cast<const T*>(data_);
- auto upper = std::upper_bound(typed_start + search_range.start,
- typed_start + search_range.end, val_data);
- return static_cast<uint32_t>(std::distance(typed_start, upper));
- },
- val);
-}
-
-// As we don't template those functions, we need to use std::visitor to type
-// `start`, hence this wrapping.
-uint32_t NumericStorage::LowerBoundIndex(NumericValue val,
- Range search_range) const {
- return std::visit(
- [this, search_range](auto val_data) {
- using T = decltype(val_data);
- const T* typed_start = static_cast<const T*>(data_);
- auto lower = std::lower_bound(typed_start + search_range.start,
- typed_start + search_range.end, val_data);
- return static_cast<uint32_t>(std::distance(typed_start, lower));
- },
- val);
-}
-
-std::optional<Range> NumericStorage::BinarySearch(FilterOp op,
- SqlValue sql_val,
- Range search_range) const {
- std::optional<NumericValue> val = GetNumericTypeVariant(type_, sql_val);
- if (op == FilterOp::kIsNotNull)
- return Range(0, size());
-
- if (!val)
- return std::nullopt;
-
- switch (op) {
- case FilterOp::kEq:
- return Range(LowerBoundIndex(*val, search_range),
- UpperBoundIndex(*val, search_range));
- case FilterOp::kLe:
- return Range(0, UpperBoundIndex(*val, search_range));
- case FilterOp::kLt:
- return Range(0, LowerBoundIndex(*val, search_range));
- case FilterOp::kGe:
- return Range(LowerBoundIndex(*val, search_range), size_);
- case FilterOp::kGt:
- return Range(UpperBoundIndex(*val, search_range), size_);
- case FilterOp::kNe:
- case FilterOp::kIsNull:
- case FilterOp::kIsNotNull:
- case FilterOp::kGlob:
- return std::nullopt;
- }
- return std::nullopt;
-}
-
-uint32_t NumericStorage::UpperBoundIndex(NumericValue val,
- uint32_t* order,
- Range search_range) const {
- return std::visit(
- [this, order, search_range](auto val_data) {
- using T = decltype(val_data);
- const T* typed_start = static_cast<const T*>(data_);
- auto upper = std::upper_bound(order + search_range.start,
- order + search_range.end, val_data,
- [typed_start](T val, uint32_t index) {
- return val < *(typed_start + index);
- });
- return static_cast<uint32_t>(std::distance(order, upper));
- },
- val);
-}
-
-// As we don't template those functions, we need to use std::visitor to type
-// `start`, hence this wrapping.
-uint32_t NumericStorage::LowerBoundIndex(NumericValue val,
- uint32_t* order,
- Range search_range) const {
- return std::visit(
- [this, order, search_range](auto val_data) {
- using T = decltype(val_data);
- const T* typed_start = static_cast<const T*>(data_);
- auto lower = std::lower_bound(order + search_range.start,
- order + search_range.end, val_data,
- [typed_start](uint32_t index, T val) {
- return *(typed_start + index) < val;
- });
- return static_cast<uint32_t>(std::distance(order, lower));
- },
- val);
-}
-
-std::optional<Range> NumericStorage::BinarySearchWithIndex(
- FilterOp op,
- SqlValue sql_val,
- uint32_t* order,
- Range search_range) const {
- std::optional<NumericValue> val = GetNumericTypeVariant(type_, sql_val);
-
- if (op == FilterOp::kIsNotNull)
- return Range(0, size());
-
- if (!val.has_value())
- return std::nullopt;
-
- switch (op) {
- case FilterOp::kEq:
- return Range(LowerBoundIndex(*val, order, search_range),
- UpperBoundIndex(*val, order, search_range));
- case FilterOp::kLe:
- return Range(0, UpperBoundIndex(*val, order, search_range));
- case FilterOp::kLt:
- return Range(0, LowerBoundIndex(*val, order, search_range));
- case FilterOp::kGe:
- return Range(LowerBoundIndex(*val, order, search_range), size_);
- case FilterOp::kGt:
- return Range(UpperBoundIndex(*val, order, search_range), size_);
- case FilterOp::kNe:
- case FilterOp::kIsNull:
- case FilterOp::kIsNotNull:
- case FilterOp::kGlob:
- return std::nullopt;
- }
- return std::nullopt;
-}
-
} // namespace storage
} // namespace trace_processor
} // namespace perfetto
diff --git a/src/trace_processor/db/storage/numeric_storage.h b/src/trace_processor/db/storage/numeric_storage.h
index a926447..ab802de 100644
--- a/src/trace_processor/db/storage/numeric_storage.h
+++ b/src/trace_processor/db/storage/numeric_storage.h
@@ -19,12 +19,13 @@
#include <variant>
#include "src/trace_processor/db/storage/storage.h"
-#include "src/trace_processor/db/storage/storage_variants.h"
+#include "src/trace_processor/db/storage/types.h"
namespace perfetto {
namespace trace_processor {
namespace storage {
+// Storage for all numeric type data (i.e. doubles, int32, int64, uint32).
class NumericStorage : public Storage {
public:
NumericStorage(void* data, uint32_t size, ColumnType type)
@@ -34,53 +35,31 @@
void Sort(uint32_t* rows, uint32_t rows_size) const override;
- void LinearSearchAligned(FilterOp op,
- SqlValue val,
- uint32_t offset,
- uint32_t num_elements,
- BitVector::Builder& builder) const override;
+ BitVector LinearSearch(FilterOp op,
+ SqlValue val,
+ RowMap::Range) const override;
- void LinearSearchUnaligned(FilterOp op,
- SqlValue val,
- uint32_t offset,
- uint32_t num_elements,
- BitVector::Builder& builder) const override;
+ BitVector IndexSearch(FilterOp op,
+ SqlValue value,
+ uint32_t* indices,
+ uint32_t indices_count) const override;
- std::optional<Range> BinarySearch(FilterOp op,
- SqlValue val,
- Range search_range) const override;
+ RowMap::Range BinarySearchIntrinsic(
+ FilterOp op,
+ SqlValue val,
+ RowMap::Range search_range) const override;
- std::optional<Range> BinarySearchWithIndex(FilterOp op,
- SqlValue val,
- uint32_t* order,
- Range search_range) const override;
+ RowMap::Range BinarySearchExtrinsic(FilterOp op,
+ SqlValue val,
+ uint32_t* indices,
+ uint32_t indices_count) const override;
uint32_t size() const override { return size_; }
private:
- // As we don't template those functions, we need to use std::visitor to type
- // `start`, hence this wrapping.
- uint32_t UpperBoundIndex(NumericValue val, Range search_range) const;
-
- // As we don't template those functions, we need to use std::visitor to type
- // `start`, hence this wrapping.
- uint32_t LowerBoundIndex(NumericValue val, Range search_range) const;
-
- // As we don't template those functions, we need to use std::visitor to type
- // `start`, hence this wrapping.
- uint32_t UpperBoundIndex(NumericValue val,
- uint32_t* order,
- Range search_range) const;
-
- // As we don't template those functions, we need to use std::visitor to type
- // `start`, hence this wrapping.
- uint32_t LowerBoundIndex(NumericValue val,
- uint32_t* order,
- Range search_range) const;
-
- const ColumnType type_;
- const void* data_;
- const uint32_t size_;
+ const ColumnType type_ = ColumnType::kDummy;
+ const void* data_ = nullptr;
+ const uint32_t size_ = 0;
};
} // namespace storage
diff --git a/src/trace_processor/db/storage/storage.h b/src/trace_processor/db/storage/storage.h
index 23aa84d..1021723 100644
--- a/src/trace_processor/db/storage/storage.h
+++ b/src/trace_processor/db/storage/storage.h
@@ -17,6 +17,7 @@
#define SRC_TRACE_PROCESSOR_DB_STORAGE_STORAGE_H_
#include "perfetto/trace_processor/basic_types.h"
+#include "src/trace_processor/containers/bit_vector.h"
#include "src/trace_processor/containers/row_map.h"
#include "src/trace_processor/db/storage/types.h"
@@ -24,55 +25,64 @@
namespace trace_processor {
namespace storage {
-using Range = RowMap::Range;
-
-// Most base column interpreting layer - responsible for implementing searches
-// and sorting.
+// Backing storage for columnar tables.
class Storage {
public:
virtual ~Storage();
- // Changes the vector of indices to represent the sorted (stable sort) state
- // of the column.
- virtual void StableSort(uint32_t* rows, uint32_t rows_size) const = 0;
+ // Searches for elements which match |op| and |value| between |range.start|
+ // and |range.end|.
+ //
+ // Returns a BitVector of size |range.end| with the position of the 1s
+ // representing the positions which matched and 0s otherwise. The first
+ // |range.start| number of elements will be zero.
+ virtual BitVector LinearSearch(FilterOp op,
+ SqlValue value,
+ RowMap::Range range) const = 0;
- // Changes the vector of indices to represent the sorted (not stable) state of
- // the column.
+ // Searches for elements which match |op| and |value| at the positions given
+ // by |indices| array.
+ //
+ // Returns a BitVector of size |indices_count| with the position of the 1s
+ // representing the positions which matched and 0s otherwise.
+ virtual BitVector IndexSearch(FilterOp op,
+ SqlValue value,
+ uint32_t* indices,
+ uint32_t indices_count) const = 0;
+
+ // Binary searches for elements which match |op| and |value| between
+ // |range.start_index| and |range.end_index|.
+ //
+ // Returns a range, indexing the storage, where all elements in that range
+ // match the constraint.
+ //
+ // Note: the caller *must* know that the elements in this storage are sorted;
+ // it is an error to call this method otherwise.
+ virtual RowMap::Range BinarySearchIntrinsic(FilterOp op,
+ SqlValue value,
+ RowMap::Range range) const = 0;
+
+ // Binary searches for elements which match |op| and |value| only considering
+ // the elements in |indices|.
+ //
+ // Returns a sub-Range of Range[0, indices_count) which indicates the
+ // positions of elements in |indices| which match.
+ //
+ // Note: the caller *must* known that the elements in storage will be sorted
+ // by the elements in |indices|; it is undefined behaviour to call this method
+ // otherwise.
+ virtual RowMap::Range BinarySearchExtrinsic(FilterOp op,
+ SqlValue value,
+ uint32_t* indices,
+ uint32_t indices_count) const = 0;
+
+ // Sorts |rows| in ascending order with the comparator:
+ // data[rows[a]] < data[rows[b]].
virtual void Sort(uint32_t* rows, uint32_t rows_size) const = 0;
- // Efficiently compares series of |num_elements| of data from |data_start| to
- // comparator value and appends results to BitVector::Builder. Should be used
- // where possible
- virtual void LinearSearchAligned(FilterOp op,
- SqlValue value,
- uint32_t offset,
- uint32_t compare_elements_count,
- BitVector::Builder&) const = 0;
-
- // Inefficiently compares series of |num_elements| of data from |data_start|
- // to comparator value and appends results to BitVector::Builder. Should be
- // avoided if possible, with `LinearSearchAligned` used instead.
- virtual void LinearSearchUnaligned(FilterOp op,
- SqlValue value,
- uint32_t offset,
- uint32_t compare_elements_count,
- BitVector::Builder&) const = 0;
-
- // Compares sorted (asc) series data in |range| with comparator value. Should
- // be used where possible. Returns the Range of indices which match the
- // constraint.
- virtual std::optional<Range> BinarySearch(FilterOp op,
- SqlValue value,
- Range search_range) const = 0;
-
- // Compares sorted (asc) with |order| vector series in |range| with comparator
- // value. Should be used where possible. Returns the Range of indices
- // inside |order| vector which match the constraint.
- virtual std::optional<Range> BinarySearchWithIndex(
- FilterOp op,
- SqlValue value,
- uint32_t* order,
- Range search_range) const = 0;
+ // Stable sorts |rows| in ascending order with the comparator:
+ // data[rows[a]] < data[rows[b]].
+ virtual void StableSort(uint32_t* rows, uint32_t rows_size) const = 0;
// Number of elements in stored data.
virtual uint32_t size() const = 0;
diff --git a/src/trace_processor/db/storage/storage_unittest.cc b/src/trace_processor/db/storage/storage_unittest.cc
index 0f7904c..6d737b9 100644
--- a/src/trace_processor/db/storage/storage_unittest.cc
+++ b/src/trace_processor/db/storage/storage_unittest.cc
@@ -17,14 +17,16 @@
#include <numeric>
#include "src/trace_processor/db/storage/numeric_storage.h"
+
#include "test/gtest_and_gmock.h"
namespace perfetto {
namespace trace_processor {
namespace storage {
-
namespace {
+using Range = RowMap::Range;
+
TEST(NumericStorageUnittest, StableSortTrivial) {
std::vector<uint32_t> data_vec{0, 1, 2, 0, 1, 2, 0, 1, 2};
std::vector<uint32_t> out = {0, 1, 2, 3, 4, 5, 6, 7, 8};
@@ -49,42 +51,12 @@
ASSERT_EQ(out, stable_out);
}
-TEST(NumericStorageUnittest, CompareSlow) {
- uint32_t size = 10;
- std::vector<uint32_t> data_vec(size);
- std::iota(data_vec.begin(), data_vec.end(), 0);
- NumericStorage storage(data_vec.data(), size, ColumnType::kUint32);
- BitVector::Builder builder(size);
- storage.LinearSearchUnaligned(FilterOp::kGe, SqlValue::Long(5), 0, size,
- builder);
- BitVector bv = std::move(builder).Build();
-
- ASSERT_EQ(bv.CountSetBits(), 5u);
- ASSERT_EQ(bv.IndexOfNthSet(0), 5u);
-}
-
-TEST(NumericStorageUnittest, CompareSlowLarge) {
- uint32_t size = 1025;
- std::vector<uint32_t> data_vec(size);
- std::iota(data_vec.begin(), data_vec.end(), 0);
- NumericStorage storage(data_vec.data(), size, ColumnType::kUint32);
- BitVector::Builder builder(size);
- storage.LinearSearchUnaligned(FilterOp::kGe, SqlValue::Long(5), 0, size,
- builder);
- BitVector bv = std::move(builder).Build();
-
- ASSERT_EQ(bv.CountSetBits(), 1020u);
- ASSERT_EQ(bv.IndexOfNthSet(0), 5u);
-}
-
TEST(NumericStorageUnittest, CompareFast) {
std::vector<uint32_t> data_vec(128);
std::iota(data_vec.begin(), data_vec.end(), 0);
NumericStorage storage(data_vec.data(), 128, ColumnType::kUint32);
- BitVector::Builder builder(128);
- storage.LinearSearchAligned(FilterOp::kGe, SqlValue::Long(100), 0, 128,
- builder);
- BitVector bv = std::move(builder).Build();
+ BitVector bv =
+ storage.LinearSearch(FilterOp::kGe, SqlValue::Long(100), Range(0, 128));
ASSERT_EQ(bv.CountSetBits(), 28u);
ASSERT_EQ(bv.IndexOfNthSet(0), 100u);
@@ -94,12 +66,12 @@
std::vector<uint32_t> data_vec(128);
std::iota(data_vec.begin(), data_vec.end(), 0);
NumericStorage storage(data_vec.data(), 128, ColumnType::kUint32);
- std::optional<Range> range =
- storage.BinarySearch(FilterOp::kGe, SqlValue::Long(100), Range(0, 128));
+ Range range = storage.BinarySearchIntrinsic(
+ FilterOp::kGe, SqlValue::Long(100), Range(0, 128));
- ASSERT_EQ(range->size(), 28u);
- ASSERT_EQ(range->start, 100u);
- ASSERT_EQ(range->end, 128u);
+ ASSERT_EQ(range.size(), 28u);
+ ASSERT_EQ(range.start, 100u);
+ ASSERT_EQ(range.end, 128u);
}
TEST(NumericStorageUnittest, CompareSortedIndexesGreaterEqual) {
@@ -108,8 +80,8 @@
NumericStorage storage(data_vec.data(), 10, ColumnType::kUint32);
- std::optional<Range> range = storage.BinarySearchWithIndex(
- FilterOp::kGe, SqlValue::Long(60), sorted_order.data(), Range(0, 10));
+ std::optional<Range> range = storage.BinarySearchExtrinsic(
+ FilterOp::kGe, SqlValue::Long(60), sorted_order.data(), 10);
ASSERT_EQ(range->size(), 4u);
ASSERT_EQ(range->start, 6u);
@@ -122,8 +94,8 @@
NumericStorage storage(data_vec.data(), 10, ColumnType::kUint32);
- std::optional<Range> range = storage.BinarySearchWithIndex(
- FilterOp::kLt, SqlValue::Long(60), sorted_order.data(), Range(0, 10));
+ std::optional<Range> range = storage.BinarySearchExtrinsic(
+ FilterOp::kLt, SqlValue::Long(60), sorted_order.data(), 10);
ASSERT_EQ(range->size(), 6u);
ASSERT_EQ(range->start, 0u);
@@ -136,8 +108,8 @@
NumericStorage storage(data_vec.data(), 10, ColumnType::kUint32);
- std::optional<Range> range = storage.BinarySearchWithIndex(
- FilterOp::kEq, SqlValue::Long(60), sorted_order.data(), Range(0, 10));
+ std::optional<Range> range = storage.BinarySearchExtrinsic(
+ FilterOp::kEq, SqlValue::Long(60), sorted_order.data(), 10);
ASSERT_EQ(range->size(), 1u);
ASSERT_EQ(range->start, 6u);
diff --git a/src/trace_processor/db/storage/storage_variants.h b/src/trace_processor/db/storage/storage_variants.h
deleted file mode 100644
index 799301c..0000000
--- a/src/trace_processor/db/storage/storage_variants.h
+++ /dev/null
@@ -1,107 +0,0 @@
-/*
- * Copyright (C) 2023 The Android Open Source Project
- *
- * Licensed under the Apache License, Version 2.0 (the "License");
- * you may not use this file except in compliance with the License.
- * You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-#ifndef SRC_TRACE_PROCESSOR_DB_STORAGE_STORAGE_VARIANTS_H_
-#define SRC_TRACE_PROCESSOR_DB_STORAGE_STORAGE_VARIANTS_H_
-
-#include <variant>
-
-#include "src/trace_processor/db/storage/types.h"
-
-namespace perfetto {
-namespace trace_processor {
-namespace storage {
-
-// All viable numeric values for ColumnTypes.
-using NumericValue = std::variant<uint32_t, int32_t, int64_t, double_t>;
-
-// Using the fact that binary operators in std are operators() of classes, we
-// can wrap those classes in variants and use them for std::visit in
-// SerialComparators. This helps prevent excess templating and switches.
-template <typename T>
-using FilterOpVariant = std::variant<std::greater<T>,
- std::greater_equal<T>,
- std::less<T>,
- std::less_equal<T>,
- std::equal_to<T>,
- std::not_equal_to<T>>;
-
-// Based on SqlValue and ColumnType, casts SqlValue to proper type, returns
-// std::nullopt if SqlValue can't be cast and should be considered invalid for
-// comparison.
-inline std::optional<NumericValue> GetNumericTypeVariant(ColumnType type,
- SqlValue val) {
- if (val.is_null())
- return std::nullopt;
-
- switch (type) {
- case ColumnType::kDouble:
- return val.AsDouble();
- case ColumnType::kInt64:
- return val.AsLong();
- case ColumnType::kInt32:
- if (val.AsLong() > std::numeric_limits<int32_t>::max() ||
- val.AsLong() < std::numeric_limits<int32_t>::min())
- return std::nullopt;
- return static_cast<int32_t>(val.AsLong());
- case ColumnType::kUint32:
- if (val.AsLong() > std::numeric_limits<uint32_t>::max() ||
- val.AsLong() < std::numeric_limits<uint32_t>::min())
- return std::nullopt;
- return static_cast<uint32_t>(val.AsLong());
- case ColumnType::kString:
- case ColumnType::kDummy:
- case ColumnType::kId:
- return std::nullopt;
- }
- PERFETTO_FATAL("For GCC");
-}
-
-// Based on SqlValue and ColumnType, casts SqlValue to proper type, returns
-// std::nullopt if SqlValue can't be cast and should be considered invalid for
-// comparison.
-inline std::optional<NumericValue> GetNumericTypeVariant(ColumnType type) {
- return GetNumericTypeVariant(type, SqlValue::Long(0));
-}
-
-// Fetch std binary comparator class based on FilterOp. Can be used in
-// std::visit for comparison.
-template <typename T>
-inline FilterOpVariant<T> GetFilterOpVariant(FilterOp op) {
- switch (op) {
- case FilterOp::kEq:
- return FilterOpVariant<T>(std::equal_to<T>());
- case FilterOp::kNe:
- return FilterOpVariant<T>(std::not_equal_to<T>());
- case FilterOp::kGe:
- return FilterOpVariant<T>(std::greater_equal<T>());
- case FilterOp::kGt:
- return FilterOpVariant<T>(std::greater<T>());
- case FilterOp::kLe:
- return FilterOpVariant<T>(std::less_equal<T>());
- case FilterOp::kLt:
- return FilterOpVariant<T>(std::less<T>());
- case FilterOp::kGlob:
- case FilterOp::kIsNotNull:
- case FilterOp::kIsNull:
- PERFETTO_FATAL("Not a valid operation on numeric type.");
- }
- PERFETTO_FATAL("For GCC");
-}
-
-} // namespace storage
-} // namespace trace_processor
-} // namespace perfetto
-#endif // SRC_TRACE_PROCESSOR_DB_STORAGE_STORAGE_VARIANTS_H_
