41 using Row = std::pair<const std::string, Value>;
42 struct ResidentProbe {
44 std::uint64_t* comparisons;
46 struct ResidentKeyLess {
47 using is_transparent = void;
48 bool operator()(std::string_view a, std::string_view b)
const noexcept {
return a < b; }
49 bool operator()(
const ResidentProbe& a, std::string_view b)
const noexcept {
53 bool operator()(std::string_view a,
const ResidentProbe& b)
const noexcept {
60 using ResidentKeys = std::map<std::string_view, Offset, ResidentKeyLess>;
62 std::shared_ptr<Row> owner;
63 typename ResidentKeys::iterator
key;
65 using Residents = std::map<Offset, ResidentRow>;
69 using Held = std::map<Offset, std::shared_ptr<Row>>;
89 return resident_.size() * (
sizeof(
typename Residents::value_type) + 4 *
sizeof(
void*)
90 +
sizeof(
typename ResidentKeys::value_type) + 4 *
sizeof(
void*) + 2 *
sizeof(
void*))
91 + held_.size() * (
sizeof(
typename Held::value_type) + 4 *
sizeof(
void*));
94 template<
bool Const,
bool Sorted = false,
bool Insertion = false>
97 using Owner = std::conditional_t<Const, const DiskResidentIdTable, DiskResidentIdTable>;
98 Owner* owner_ =
nullptr;
100 std::shared_ptr<Row> row_;
102 Iterator(Owner* owner, Offset at, std::shared_ptr<Row> row) noexcept
103 : owner_(owner), at_(at), row_(std::move(row)) {}
108 using reference = std::conditional_t<Const, const Row&, Row&>;
109 using pointer = std::conditional_t<Const, const Row*, Row*>;
112 ++owner_->work_.iterated_rows;
116 ++owner_->work_.iterated_rows;
120 ++owner_->work_.iterated_rows;
121 if constexpr (Sorted) {
122 const auto next = owner_->index_.next_sorted(at_);
124 owner_->spill_implicitly();
126 if (at_ != 0) row_ = owner_->load(at_);
127 }
else if constexpr (Insertion) {
130 const auto next = owner_->resident_.upper_bound(at_);
131 at_ = next == owner_->resident_.end() ? 0 : next->first;
132 row_ = at_ == 0 ? nullptr : next->second.owner;
134 auto next = owner_->resident_.lower_bound(at_);
135 if (next == owner_->resident_.begin()) {
141 row_ = next->second.owner;
146 Iterator
operator++(
int) {
auto old = *
this; ++*
this;
return old; }
148 return owner_ == other.owner_ && at_ == other.at_;
150 bool operator!=(
const Iterator& other)
const noexcept {
return !(*
this == other); }
162 template<
bool Const>
class ResidentIterator {
164 using Owner = std::conditional_t<Const, const DiskResidentIdTable, DiskResidentIdTable>;
165 Owner* owner_ =
nullptr;
166 typename Residents::const_iterator at_{};
167 std::shared_ptr<Row> row_;
168 ResidentIterator(Owner* owner,
typename Residents::const_iterator at) noexcept
169 : owner_(owner), at_(at),
170 row_(at == owner->resident_.end() ?
nullptr : at->second.owner) {}
175 using reference = std::conditional_t<Const, const Row&, Row&>;
176 using pointer = std::conditional_t<Const, const Row*, Row*>;
179 ++owner_->work_.resident_rows_visited;
183 ++owner_->work_.resident_rows_visited;
188 row_ = at_ == owner_->resident_.end() ? nullptr : at_->second.owner;
191 ResidentIterator
operator++(
int)
noexcept {
auto old = *
this; ++*
this;
return old; }
192 bool operator==(
const ResidentIterator& other)
const noexcept {
193 return owner_ == other.owner_ && (!owner_ || at_ == other.at_);
195 bool operator!=(
const ResidentIterator& other)
const noexcept {
return !(*
this == other); }
201 template<
bool Const>
class HeldIterator {
203 using Owner = std::conditional_t<Const, const DiskResidentIdTable, DiskResidentIdTable>;
204 Owner* owner_ =
nullptr;
205 typename Held::const_iterator at_{};
207 std::shared_ptr<Row> row_;
208 HeldIterator(Owner* owner,
typename Held::const_iterator at) noexcept
209 : owner_(owner), at_(at),
210 offset_(at == owner->held_.end() ? 0 : at->first),
211 row_(at == owner->held_.end() ?
nullptr : at->second) {}
216 using reference = std::conditional_t<Const, const Row&, Row&>;
217 using pointer = std::conditional_t<Const, const Row*, Row*>;
220 ++owner_->work_.held_rows_visited;
224 ++owner_->work_.held_rows_visited;
229 offset_ = at_ == owner_->held_.end() ? 0 : at_->first;
230 row_ = at_ == owner_->held_.end() ? nullptr : at_->second;
233 HeldIterator
operator++(
int)
noexcept {
auto old = *
this; ++*
this;
return old; }
235 return owner_ == other.owner_ && (!owner_ || at_ == other.at_);
237 bool operator!=(
const HeldIterator& other)
const noexcept {
return !(*
this == other); }
268 if (
this != &other) {
270 index_ = std::move(other.index_);
271 resident_ = std::move(other.resident_);
272 resident_by_key_ = std::move(other.resident_by_key_);
273 held_ = std::move(other.held_);
274 work_ = std::exchange(other.work_, {});
275 spill_threshold_ = std::exchange(other.spill_threshold_, kSpillFloor);
276 spill_interval_ = std::exchange(other.spill_interval_, kSpillFloor);
277 calls_since_spill_ = std::exchange(other.calls_since_spill_, 0);
278 fixture_spill_interval_ = std::exchange(other.fixture_spill_interval_, 0);
279 fixture_spill_predicate_ = std::exchange(other.fixture_spill_predicate_,
nullptr);
280 other.resident_by_key_.clear();
281 other.resident_.clear();
289 void set_directory(
const std::string& directory) { index_.set_directory(directory); }
291 index_.bind_scratch(slab,
resource);
297 index_.require_insert(
key);
298 if (!index_.bounded_cohorts())
return;
300 if (found ==
end() || found->second.spillable()) require_live_growth(1);
303 index_.require_inserts(std::forward<Enumerate>(enumerate));
304 if (!index_.bounded_cohorts())
return;
305 std::size_t ordinal = 0, extra = 0;
306 enumerate([&](
const std::string&
key) {
307 const auto current = ordinal++;
309 if (found !=
end() && !found->second.spillable())
return;
310 bool repeated =
false;
311 std::size_t prior = 0;
312 enumerate([&](
const std::string& other) {
313 if (prior++ < current && other ==
key) repeated =
true;
320 require_live_growth(extra);
324 resident_by_key_.clear();
328 spill_threshold_ = spill_interval_ = kSpillFloor;
329 calls_since_spill_ = 0;
332 std::uint64_t
size() const noexcept {
return index_.size(); }
334 std::size_t
held_size() const noexcept {
return held_.size(); }
340 return Range<ResidentIterator<false>>{
341 {
this, resident_.begin()}, {
this, resident_.end()}};
344 return Range<ResidentIterator<true>>{
345 {
this, resident_.begin()}, {
this, resident_.end()}};
349 return Range<HeldIterator<false>>{{
this, held_.begin()}, {
this, held_.end()}};
353 return Range<HeldIterator<true>>{{
this, held_.begin()}, {
this, held_.end()}};
358 assert(row.owner_ ==
this && row.row_);
361 template<
bool Const>
void refresh_held(
const HeldIterator<Const>& row)
const {
362 assert(row.owner_ ==
this && row.row_);
368 auto next = held_.begin();
369 for (
const auto& row : resident_) {
370 if (!is_held(row.second.owner->second, 0))
continue;
371 if (next == held_.end() || next->first != row.first
372 || next->second != row.second.owner)
return false;
375 return next == held_.end();
378 std::size_t total = 0;
379 for (
const auto& row : resident_) total += row.second.owner->second.opened.size();
383 const auto at = resident_.begin();
385 at == resident_.end() ? nullptr : at->second.owner};
386 return Range<KeyIterator<insertion_iterator>>{
387 KeyIterator<insertion_iterator>(first),
391 const auto at = index_.first_sorted();
392 return Range<sorted_iterator>{{
this, at, at ? load(at) :
nullptr}, {
this, 0, {}}};
395 const auto at = index_.first_sorted();
396 return Range<const_sorted_iterator>{{
this, at, at ? load(at) :
nullptr}, {
this, 0, {}}};
400 for (
auto at = index_.first_inserted(); at != 0; at = index_.next_inserted(at))
401 visit(index_.key(at));
406 for (
auto at = index_.first_sorted(); at != 0; at = index_.next_sorted(at))
407 visit(index_.key(at));
411 const auto at = index_.find(
key);
412 return at ?
iterator{
this, *at, load(*at)} :
end();
416 const auto at = index_.find(
key);
422 const auto at = resident_by_key_.find(ResidentProbe{
key, &work_.find_resident_probes});
423 if (at == resident_by_key_.end())
return end();
424 const auto row = resident_.find(at->second);
425 return {
this, row->first, row->second.owner};
428 const auto at = resident_by_key_.find(ResidentProbe{
key, &work_.find_resident_probes});
429 if (at == resident_by_key_.end())
return end();
430 const auto row = resident_.find(at->second);
431 return {
this, row->first, row->second.owner};
436 index_.require_insert(
key);
437 std::size_t extra = 0;
438 if (index_.bounded_cohorts() && !
value.spillable() && !index_.find(
key)) {
440 require_live_growth(extra);
442 spill_before_admission(extra);
444 const auto placed = index_.insert(
key,
value.retired_record());
445 if (!placed.second)
return {{
this, placed.first, load(placed.first)},
false};
446 auto row = std::make_shared<Row>(
key, std::move(
value));
447 insert_resident(placed.first, row);
448 return {{
this, placed.first, std::move(row)},
true};
451 for (
auto at = resident_.begin(); at != resident_.end();) {
452 ++work_.rows_visited_by_spill;
453 if (at->second.owner.use_count() == 1 && at->second.owner->second.spillable()
454 && (fixture_spill_predicate_ ==
nullptr
455 || fixture_spill_predicate_(at->second.owner->first))
457 index_.set(at->first, at->second.owner->second.retired_record());
458 ++work_.rows_spilled;
459 assert(held_.find(at->first) == held_.end());
460 resident_by_key_.erase(at->second.key);
461 at = resident_.erase(at);
464 const auto count = resident_.size();
465 const auto maximum = std::numeric_limits<std::size_t>::max();
466 spill_threshold_ = std::max(kSpillFloor, count > maximum / 2 ? maximum : count * 2);
467 spill_interval_ = std::max(kSpillFloor, count);
468 calls_since_spill_ = 0;
475 const auto interval = fixture_spill_interval_ ? fixture_spill_interval_ : spill_interval_;
476 if (++calls_since_spill_ >= interval || resident_.size() >= spill_threshold_)
spill();
481 fixture_spill_interval_ = calls;
486 fixture_spill_predicate_ = predicate;
490 void require_live_growth(std::size_t extra)
const {
499 std::size_t live = 0;
500 for (
const auto& row : resident_) {
502 if (!row.second.owner->second.spillable()) ++live;
508 void spill_before_admission(std::size_t extra)
const {
512 void insert_resident(Offset at,
const std::shared_ptr<Row>& row)
const {
515 const auto key = std::string_view(row->first);
516 const auto indexed = resident_by_key_.emplace(
key, at);
518 resident_.emplace(at, ResidentRow{row, indexed.first});
519 if (is_held(row->second, 0)) held_.emplace(at, row);
522 resident_by_key_.erase(indexed.first);
528 static auto is_held(
const T&
value,
int)
noexcept ->
decltype(
value.held()) {
533 static bool is_held(
const Value&,
long)
noexcept {
return false; }
538 void refresh_held(Offset at,
const std::shared_ptr<Row>& row)
const {
539 const auto found = held_.lower_bound(at);
540 if (is_held(row->second, 0)) {
541 if (found == held_.end() || found->first != at) held_.emplace_hint(found, at, row);
542 }
else if (found != held_.end() && found->first == at) {
549 template<
class T = Value>
550 auto restore_record(
const typename T::Record& record,
int)
const
551 ->
decltype(T::restore_record(record,
bool{})) {
552 return T::restore_record(record, index_.arena_backed());
554 Value restore_record(
const typename Value::Record& record,
long)
const {
555 return Value::restore_record(record);
557 template<
bool Const,
class Owner>
559 const auto at = owner->resident_.rbegin();
560 return {owner, at == owner->resident_.rend() ? 0 : at->first,
561 at == owner->resident_.rend() ? nullptr : at->second.owner};
563 std::shared_ptr<Row> load(Offset at)
const {
564 const auto found = resident_.find(at);
565 if (found != resident_.end())
return found->second.owner;
566 auto value = restore_record(index_.get(at), 0);
567 const std::size_t extra =
value.spillable() ? 0 : 1;
568 require_live_growth(extra);
569 spill_before_admission(extra);
570 auto row = std::make_shared<Row>(index_.key(at), std::move(
value));
571 insert_resident(at, row);
572 ++work_.rows_restored;
575 static constexpr std::size_t kSpillFloor = 64;
576 mutable Index index_;
577 mutable Residents resident_;
578 mutable ResidentKeys resident_by_key_;
581 mutable std::size_t spill_threshold_ = kSpillFloor, spill_interval_ = kSpillFloor;
582 mutable std::size_t calls_since_spill_ = 0;
583 std::size_t fixture_spill_interval_ = 0;
584 bool (*fixture_spill_predicate_)(
const std::string&) =
nullptr;
bool bounded_cohorts() const noexcept
bool operator==(const HeldIterator &other) const noexcept
std::conditional_t< Const, const Row *, Row * > pointer
std::conditional_t< Const, const Row &, Row & > reference
friend class DiskResidentIdTable
std::ptrdiff_t difference_type
bool operator!=(const HeldIterator &other) const noexcept
pointer operator->() const noexcept
HeldIterator operator++(int) noexcept
reference operator*() const noexcept
HeldIterator & operator++() noexcept
std::forward_iterator_tag iterator_category
std::conditional_t< Const, const Row *, Row * > pointer
std::forward_iterator_tag iterator_category
friend class DiskResidentIdTable
reference operator*() const noexcept
bool operator==(const Iterator &other) const noexcept
bool operator!=(const Iterator &other) const noexcept
std::ptrdiff_t difference_type
pointer operator->() const noexcept
std::conditional_t< Const, const Row &, Row & > reference
bool operator==(const KeyIterator &other) const noexcept
KeyIterator & operator++()
bool operator!=(const KeyIterator &other) const noexcept
std::forward_iterator_tag iterator_category
std::ptrdiff_t difference_type
const std::string * pointer
pointer operator->() const noexcept
KeyIterator operator++(int)
reference operator*() const noexcept
const std::string & reference
ResidentIterator()=default
pointer operator->() const noexcept
reference operator*() const noexcept
bool operator==(const ResidentIterator &other) const noexcept
std::forward_iterator_tag iterator_category
friend class DiskResidentIdTable
ResidentIterator & operator++() noexcept
ResidentIterator operator++(int) noexcept
std::conditional_t< Const, const Row &, Row & > reference
std::ptrdiff_t difference_type
std::conditional_t< Const, const Row *, Row * > pointer
bool operator!=(const ResidentIterator &other) const noexcept
std::uint64_t size() const noexcept
std::size_t resident_opened_slot_count() const noexcept
Iterator< false > iterator
auto resident_rows() const noexcept
void require_inserts(Enumerate &&enumerate) const
void set_store(ScratchStore store) noexcept
const_iterator find_resident(const std::string &key) const noexcept
std::size_t resident_size() const noexcept
void require_insert(const std::string &key) const
void for_each_id(F &&visit) const
Iterator< true > const_iterator
void for_each_sorted_id(F &&visit) const
void fixture_implicit_spill_interval(std::size_t calls) noexcept
DiskResidentIdTable & operator=(DiskResidentIdTable &&other) noexcept
auto resident_rows() noexcept
const_iterator find(const std::string &key) const
auto resident_ids() const noexcept
bool held_rows_exact() const noexcept
iterator find(const std::string &key)
void refresh_held(const iterator &row) const
void spill_implicitly() const
std::pair< iterator, bool > emplace(const std::string &key, Value value)
void refresh_held(const HeldIterator< Const > &row) const
DiskResidentIdTable & operator=(const DiskResidentIdTable &)=delete
std::size_t held_size() const noexcept
iterator find_resident(const std::string &key) noexcept
DiskResidentIdTable()=default
const_iterator end() const noexcept
void bind_scratch(const std::shared_ptr< ScratchSlab > &slab, ScratchResource resource)
DiskResidentIdTable(DiskResidentIdTable &&other) noexcept
const WorkCounters & work_counters() const noexcept
static constexpr std::size_t resident_row_bytes() noexcept
auto held_rows() noexcept
void set_directory(const std::string &directory)
Iterator< true, true > const_sorted_iterator
DiskResidentIdTable(const DiskResidentIdTable &)=delete
std::size_t resident_directory_heap_estimate() const noexcept
Iterator< false, true > sorted_iterator
const_iterator begin() const noexcept
auto held_rows() const noexcept
iterator begin() noexcept
void fixture_spill_predicate(bool(*predicate)(const std::string &)) noexcept
Iterator< true, false, true > insertion_iterator
constexpr std::size_t kMaxResidentCohorts
std::string scratch_resident_cohort_limit_message(std::uint64_t limit)
std::uint64_t iterated_rows
std::uint64_t find_resident_probes
std::uint64_t rows_visited_by_spill
std::uint64_t rows_visited_by_capacity
std::uint64_t held_rows_visited
std::uint64_t rows_restored
std::uint64_t resident_rows_visited
std::uint64_t rows_spilled