#include <array>
#include <memory>
+#include "rocksdb/rocksdb_namespace.h"
#include "util/math128.h"
namespace ROCKSDB_NAMESPACE {
// only some small fixed number of columns (typically k=3) to 1 for each
// row of C, with remaining entries implicitly 0. This is implemented as
// three hash functions over [0,m), and S can be implemented as a vector
-// vector of b-bit values. Now, a query only involves looking up k rows
+// of b-bit values. Now, a query only involves looking up k rows
// (values) in S and computing their bitwise XOR. Additionally, this
// construction can use a linear time algorithm called "peeling" for
// finding a solution in many cases of one existing, but peeling
// (m/n) than is required with Gaussian elimination.
//
// Recommended reading:
-// "Peeling Close to the Orientability Threshold – Spatial Coupling in
+// "Peeling Close to the Orientability Threshold - Spatial Coupling in
// Hashing-Based Data Structures" by Stefan Walzer
//
// ######################################################################
// // slot index i.
// void Prefetch(Index i) const;
//
-// // Returns a pointer to CoeffRow for slot index i.
-// CoeffRow* CoeffRowPtr(Index i);
-//
-// // Returns a pointer to ResultRow for slot index i. (Gaussian row
-// // operations involve both side of the equation.)
-// ResultRow* ResultRowPtr(Index i);
+// // Load or store CoeffRow and ResultRow for slot index i.
+// // (Gaussian row operations involve both sides of the equation.)
+// // Bool `for_back_subst` indicates that customizing values for
+// // unconstrained solution rows (cr == 0) is allowed.
+// void LoadRow(Index i, CoeffRow *cr, ResultRow *rr, bool for_back_subst)
+// const;
+// void StoreRow(Index i, CoeffRow cr, ResultRow rr);
//
// // Returns the number of columns that can start an r-sequence of
// // coefficients, which is the number of slots minus r (kCoeffBits)
typename BandingStorage::CoeffRow cr, BacktrackStorage *bts,
typename BandingStorage::Index *backtrack_pos) {
using CoeffRow = typename BandingStorage::CoeffRow;
+ using ResultRow = typename BandingStorage::ResultRow;
using Index = typename BandingStorage::Index;
Index i = start;
for (;;) {
assert((cr & 1) == 1);
- CoeffRow other = *(bs->CoeffRowPtr(i));
- if (other == 0) {
- *(bs->CoeffRowPtr(i)) = cr;
- *(bs->ResultRowPtr(i)) = rr;
+ CoeffRow cr_at_i;
+ ResultRow rr_at_i;
+ bs->LoadRow(i, &cr_at_i, &rr_at_i, /* for_back_subst */ false);
+ if (cr_at_i == 0) {
+ bs->StoreRow(i, cr, rr);
bts->BacktrackPut(*backtrack_pos, i);
++*backtrack_pos;
return true;
}
- assert((other & 1) == 1);
+ assert((cr_at_i & 1) == 1);
// Gaussian row reduction
- cr ^= other;
- rr ^= *(bs->ResultRowPtr(i));
+ cr ^= cr_at_i;
+ rr ^= rr_at_i;
if (cr == 0) {
// Inconsistency or (less likely) redundancy
break;
while (backtrack_pos > 0) {
--backtrack_pos;
Index i = bts->BacktrackGet(backtrack_pos);
- *(bs->CoeffRowPtr(i)) = 0;
- // Not strictly required, but is required for good FP rate on
- // inputs that might have been backtracked out. (We don't want
- // anything we've backtracked on to leak into final result, as
- // that might not be "harmless".)
- *(bs->ResultRowPtr(i)) = 0;
+ // Clearing the ResultRow is not strictly required, but is required
+ // for good FP rate on inputs that might have been backtracked out.
+ // (We don't want anything we've backtracked on to leak into final
+ // result, as that might not be "harmless".)
+ bs->StoreRow(i, 0, 0);
}
}
return false;
for (Index i = num_slots; i > 0;) {
--i;
- CoeffRow cr = *const_cast<BandingStorage &>(bs).CoeffRowPtr(i);
- ResultRow rr = *const_cast<BandingStorage &>(bs).ResultRowPtr(i);
+ CoeffRow cr;
+ ResultRow rr;
+ bs.LoadRow(i, &cr, &rr, /* for_back_subst */ true);
// solution row
ResultRow sr = 0;
for (Index j = 0; j < kResultBits; ++j) {
for (Index i = start_slot + kCoeffBits; i > start_slot;) {
--i;
- CoeffRow cr = *const_cast<BandingStorage &>(bs).CoeffRowPtr(i);
- ResultRow rr = *const_cast<BandingStorage &>(bs).ResultRowPtr(i);
+ CoeffRow cr;
+ ResultRow rr;
+ bs.LoadRow(i, &cr, &rr, /* for_back_subst */ true);
for (Index j = 0; j < num_columns; ++j) {
// Compute next solution bit at row i, column j (see derivation below)
CoeffRow tmp = state[j] << 1;
std::unique_ptr<CoeffRow[]> state{new CoeffRow[num_columns]()};
Index block = num_blocks;
- Index segment = num_segments;
+ Index segment_num = num_segments;
while (block > upper_start_block) {
--block;
BackSubstBlock(state.get(), num_columns, bs, block * kCoeffBits);
- segment -= num_columns;
+ segment_num -= num_columns;
for (Index i = 0; i < num_columns; ++i) {
- iss->StoreSegment(segment + i, state[i]);
+ iss->StoreSegment(segment_num + i, state[i]);
}
}
// Now (if applicable), region using lower number of columns
while (block > 0) {
--block;
BackSubstBlock(state.get(), num_columns, bs, block * kCoeffBits);
- segment -= num_columns;
+ segment_num -= num_columns;
for (Index i = 0; i < num_columns; ++i) {
- iss->StoreSegment(segment + i, state[i]);
+ iss->StoreSegment(segment_num + i, state[i]);
}
}
// Verify everything processed
assert(block == 0);
- assert(segment == 0);
+ assert(segment_num == 0);
}
-// General PHSF query a key from InterleavedSolutionStorage.
+// Prefetch memory for a key in InterleavedSolutionStorage.
template <typename InterleavedSolutionStorage, typename PhsfQueryHasher>
-typename InterleavedSolutionStorage::ResultRow InterleavedPhsfQuery(
+inline void InterleavedPrepareQuery(
const typename PhsfQueryHasher::Key &key, const PhsfQueryHasher &hasher,
- const InterleavedSolutionStorage &iss) {
+ const InterleavedSolutionStorage &iss,
+ typename PhsfQueryHasher::Hash *saved_hash,
+ typename InterleavedSolutionStorage::Index *saved_segment_num,
+ typename InterleavedSolutionStorage::Index *saved_num_columns,
+ typename InterleavedSolutionStorage::Index *saved_start_bit) {
using Hash = typename PhsfQueryHasher::Hash;
-
using CoeffRow = typename InterleavedSolutionStorage::CoeffRow;
using Index = typename InterleavedSolutionStorage::Index;
- using ResultRow = typename InterleavedSolutionStorage::ResultRow;
static_assert(sizeof(Index) == sizeof(typename PhsfQueryHasher::Index),
"must be same");
- static_assert(sizeof(CoeffRow) == sizeof(typename PhsfQueryHasher::CoeffRow),
- "must be same");
-
- constexpr auto kCoeffBits = static_cast<Index>(sizeof(CoeffRow) * 8U);
const Hash hash = hasher.GetHash(key);
const Index start_slot = hasher.GetStart(hash, iss.GetNumStarts());
+ constexpr auto kCoeffBits = static_cast<Index>(sizeof(CoeffRow) * 8U);
+
const Index upper_start_block = iss.GetUpperStartBlock();
Index num_columns = iss.GetUpperNumColumns();
Index start_block_num = start_slot / kCoeffBits;
- Index segment = start_block_num * num_columns -
- std::min(start_block_num, upper_start_block);
+ Index segment_num = start_block_num * num_columns -
+ std::min(start_block_num, upper_start_block);
// Change to lower num columns if applicable.
// (This should not compile to a conditional branch.)
num_columns -= (start_block_num < upper_start_block) ? 1 : 0;
- const CoeffRow cr = hasher.GetCoeffRow(hash);
Index start_bit = start_slot % kCoeffBits;
+ Index segment_count = num_columns + (start_bit == 0 ? 0 : num_columns);
+
+ iss.PrefetchSegmentRange(segment_num, segment_num + segment_count);
+
+ *saved_hash = hash;
+ *saved_segment_num = segment_num;
+ *saved_num_columns = num_columns;
+ *saved_start_bit = start_bit;
+}
+
+// General PHSF query from InterleavedSolutionStorage, using data for
+// the query key from InterleavedPrepareQuery
+template <typename InterleavedSolutionStorage, typename PhsfQueryHasher>
+inline typename InterleavedSolutionStorage::ResultRow InterleavedPhsfQuery(
+ typename PhsfQueryHasher::Hash hash,
+ typename InterleavedSolutionStorage::Index segment_num,
+ typename InterleavedSolutionStorage::Index num_columns,
+ typename InterleavedSolutionStorage::Index start_bit,
+ const PhsfQueryHasher &hasher, const InterleavedSolutionStorage &iss) {
+ using CoeffRow = typename InterleavedSolutionStorage::CoeffRow;
+ using Index = typename InterleavedSolutionStorage::Index;
+ using ResultRow = typename InterleavedSolutionStorage::ResultRow;
+
+ static_assert(sizeof(Index) == sizeof(typename PhsfQueryHasher::Index),
+ "must be same");
+ static_assert(sizeof(CoeffRow) == sizeof(typename PhsfQueryHasher::CoeffRow),
+ "must be same");
+
+ constexpr auto kCoeffBits = static_cast<Index>(sizeof(CoeffRow) * 8U);
+
+ const CoeffRow cr = hasher.GetCoeffRow(hash);
+
ResultRow sr = 0;
- const CoeffRow cr_left = cr << start_bit;
+ const CoeffRow cr_left = cr << static_cast<unsigned>(start_bit);
for (Index i = 0; i < num_columns; ++i) {
- sr ^= BitParity(iss.LoadSegment(segment + i) & cr_left) << i;
+ sr ^= BitParity(iss.LoadSegment(segment_num + i) & cr_left) << i;
}
if (start_bit > 0) {
- segment += num_columns;
- const CoeffRow cr_right = cr >> (kCoeffBits - start_bit);
+ segment_num += num_columns;
+ const CoeffRow cr_right =
+ cr >> static_cast<unsigned>(kCoeffBits - start_bit);
for (Index i = 0; i < num_columns; ++i) {
- sr ^= BitParity(iss.LoadSegment(segment + i) & cr_right) << i;
+ sr ^= BitParity(iss.LoadSegment(segment_num + i) & cr_right) << i;
}
}
// Filter query a key from InterleavedFilterQuery.
template <typename InterleavedSolutionStorage, typename FilterQueryHasher>
-bool InterleavedFilterQuery(const typename FilterQueryHasher::Key &key,
- const FilterQueryHasher &hasher,
- const InterleavedSolutionStorage &iss) {
- // BEGIN mostly copied from InterleavedPhsfQuery
- using Hash = typename FilterQueryHasher::Hash;
-
+inline bool InterleavedFilterQuery(
+ typename FilterQueryHasher::Hash hash,
+ typename InterleavedSolutionStorage::Index segment_num,
+ typename InterleavedSolutionStorage::Index num_columns,
+ typename InterleavedSolutionStorage::Index start_bit,
+ const FilterQueryHasher &hasher, const InterleavedSolutionStorage &iss) {
using CoeffRow = typename InterleavedSolutionStorage::CoeffRow;
using Index = typename InterleavedSolutionStorage::Index;
using ResultRow = typename InterleavedSolutionStorage::ResultRow;
constexpr auto kCoeffBits = static_cast<Index>(sizeof(CoeffRow) * 8U);
- const Hash hash = hasher.GetHash(key);
- const Index start_slot = hasher.GetStart(hash, iss.GetNumStarts());
-
- const Index upper_start_block = iss.GetUpperStartBlock();
- Index num_columns = iss.GetUpperNumColumns();
- Index start_block_num = start_slot / kCoeffBits;
- Index segment = start_block_num * num_columns -
- std::min(start_block_num, upper_start_block);
- // Change to lower num columns if applicable.
- // (This should not compile to a conditional branch.)
- num_columns -= (start_block_num < upper_start_block) ? 1 : 0;
-
const CoeffRow cr = hasher.GetCoeffRow(hash);
- Index start_bit = start_slot % kCoeffBits;
- // END mostly copied from InterleavedPhsfQuery.
-
const ResultRow expected = hasher.GetResultRowFromHash(hash);
// TODO: consider optimizations such as
- // * mask fetched values and shift cr, rather than shifting fetched values
// * get rid of start_bit == 0 condition with careful fetching & shifting
if (start_bit == 0) {
for (Index i = 0; i < num_columns; ++i) {
- if (BitParity(iss.LoadSegment(segment + i) & cr) !=
+ if (BitParity(iss.LoadSegment(segment_num + i) & cr) !=
(static_cast<int>(expected >> i) & 1)) {
return false;
}
}
} else {
+ const CoeffRow cr_left = cr << static_cast<unsigned>(start_bit);
+ const CoeffRow cr_right =
+ cr >> static_cast<unsigned>(kCoeffBits - start_bit);
+
for (Index i = 0; i < num_columns; ++i) {
- CoeffRow soln_col =
- (iss.LoadSegment(segment + i) >> static_cast<unsigned>(start_bit)) |
- (iss.LoadSegment(segment + num_columns + i)
- << static_cast<unsigned>(kCoeffBits - start_bit));
- if (BitParity(soln_col & cr) != (static_cast<int>(expected >> i) & 1)) {
+ CoeffRow soln_data =
+ (iss.LoadSegment(segment_num + i) & cr_left) ^
+ (iss.LoadSegment(segment_num + num_columns + i) & cr_right);
+ if (BitParity(soln_data) != (static_cast<int>(expected >> i) & 1)) {
return false;
}
}
projects / ceph.git / blobdiff