Skip to content

Commit d398279

Browse files
luisleo526claude
andcommitted
Merge pull request 756 (keep sparse placement inserts amortized O(1))
Merges the head b948ce3 of the branch perf/placement-storage into the branch that already holds pull request 751. The merge is a plain merge commit: no rebase, no conflict resolution. Co-Authored-By: Claude Sonnet 5.5 <[email protected]>
2 parents 37cf309 + b948ce3 commit d398279

6 files changed

Lines changed: 600 additions & 28 deletions

File tree

‎ci/cr150-source-sites.json‎

Lines changed: 36 additions & 11 deletions
Original file line numberDiff line numberDiff line change
@@ -30413,17 +30413,6 @@
3041330413
"spelling": "old_ . emplace ( . . . )",
3041430414
"ordinal": 1
3041530415
},
30416-
{
30417-
"file": "src/source/pine_adapter.cpp",
30418-
"symbol": "window_",
30419-
"scope": [
30420-
":: pineforge :: source :: detail :: PositionTailDiagnostics :: pineforge :: source :: detail :: PositionTailNoDiagnostics namespace pineforge :: source #1",
30421-
"void PlacementTable :: place ( std :: uint64_t incarnation , std :: unique_ptr < PlacementSnapshot > node ) #1"
30422-
],
30423-
"cls": "grow",
30424-
"spelling": "window_ . resize ( . . . )",
30425-
"ordinal": 1
30426-
},
3042730416
{
3042830417
"file": "src/source/pine_adapter.cpp",
3042930418
"symbol": "erased_foreign_ids_",
@@ -40604,6 +40593,20 @@
4060440593
"spelling": "rows . reserve ( . . . )",
4060540594
"ordinal": 1
4060640595
},
40596+
{
40597+
"file": "src/source/pine_adapter.cpp",
40598+
"symbol": "old_",
40599+
"scope": [
40600+
"namespace pineforge :: source #7",
40601+
"void PlacementTable :: prepare_place ( std :: uint64_t incarnation ) #1",
40602+
"else #1",
40603+
"if ( window_rows_ ! = 0 && ! dense ) #1",
40604+
"+ + slot ) #1"
40605+
],
40606+
"cls": "grow",
40607+
"spelling": "old_ . emplace_back ( . . . )",
40608+
"ordinal": 1
40609+
},
4060740610
{
4060840611
"file": "src/source/pine_adapter.cpp",
4060940612
"symbol": "index",
@@ -40858,6 +40861,28 @@
4085840861
"spelling": "next = . . .",
4085940862
"ordinal": 1
4086040863
},
40864+
{
40865+
"file": "src/source/pine_adapter.cpp",
40866+
"symbol": "window_",
40867+
"scope": [
40868+
"namespace pineforge :: source #9",
40869+
"void PlacementTable :: grow_window ( std :: size_t index ) #1"
40870+
],
40871+
"cls": "grow",
40872+
"spelling": "window_ . resize ( . . . )",
40873+
"ordinal": 1
40874+
},
40875+
{
40876+
"file": "src/source/pine_adapter.cpp",
40877+
"symbol": "old_",
40878+
"scope": [
40879+
"namespace pineforge :: source #9",
40880+
"void PlacementTable :: place_old ( std :: uint64_t incarnation , std :: unique_ptr < PlacementSnapshot > node ) #1"
40881+
],
40882+
"cls": "grow",
40883+
"spelling": "old_ . emplace ( . . . )",
40884+
"ordinal": 1
40885+
},
4086140886
{
4086240887
"file": "src/source/pine_aux_security.cpp",
4086340888
"symbol": "aux_security_bars_",

‎include/pineforge/source/pine_adapter.hpp‎

Lines changed: 8 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -691,7 +691,7 @@ class PlacementTable {
691691
head_ = 0;
692692
base_ = 1;
693693
window_rows_ = 0;
694-
old_.clear();
694+
old_.clear(); reset_storage_work();
695695
size_ = 0;
696696
high_water_ = 0;
697697
erased_rows_ = 0; visited_slots_ = 0;
@@ -911,14 +911,14 @@ private: friend class PineExecutionAdapter; bool exit_sequences_certified() cons
911911
}
912912

913913
PlacementSnapshot* locate(std::uint64_t incarnation) const noexcept {
914-
if (incarnation >= base_) {
914+
if (!old_only_ && incarnation >= base_) {
915915
const std::uint64_t offset = incarnation - base_;
916916
if (offset < window_.size() - head_)
917917
return window_[head_ + static_cast<std::size_t>(offset)].get();
918918
return nullptr;
919919
}
920920
const auto found = std::lower_bound(old_.begin(), old_.end(), incarnation,
921-
[](const auto& entry, std::uint64_t key) { return entry.first < key; });
921+
[this](const auto& entry, std::uint64_t key) { ++lookup_work_; return entry.first < key; });
922922
return found != old_.end() && found->first == incarnation ? found->second.get()
923923
: nullptr;
924924
}
@@ -939,20 +939,20 @@ private: friend class PineExecutionAdapter; bool exit_sequences_certified() cons
939939
return {0, nullptr};
940940
}
941941

942-
void place(std::uint64_t incarnation, std::unique_ptr<PlacementSnapshot> node);
942+
void place(std::uint64_t incarnation, std::unique_ptr<PlacementSnapshot> node); void place_old(std::uint64_t, std::unique_ptr<PlacementSnapshot>);
943943
std::unique_ptr<PlacementSnapshot> take(std::uint64_t incarnation) noexcept;
944-
void remember_erased(const PlacementSnapshot& row); void prepare_place(std::uint64_t incarnation);
944+
void remember_erased(const PlacementSnapshot& row); void prepare_place(std::uint64_t incarnation); void grow_window(std::size_t); bool compact_old() noexcept; void reset_storage_work() noexcept;
945945
void change_sequences(std::uint64_t, const PlacementSnapshot*, const PlacementSnapshot*);
946946
// window_[head_ + i] holds incarnation base_ + i, or null; old_ holds the
947947
// rows below base_, ascending.
948948
std::vector<std::unique_ptr<PlacementSnapshot>> window_;
949949
std::size_t head_ = 0;
950950
std::uint64_t base_ = 1;
951951
std::size_t window_rows_ = 0;
952-
std::vector<std::pair<std::uint64_t, std::unique_ptr<PlacementSnapshot>>> old_;
953-
std::size_t size_ = 0;
952+
std::vector<std::pair<std::uint64_t, std::unique_ptr<PlacementSnapshot>>> old_; bool old_only_ = false;
953+
std::size_t size_ = 0; std::uint64_t placement_work_ = 0, removal_work_ = 0;
954954
std::uint64_t high_water_ = 0;
955-
std::uint64_t erased_rows_ = 0; mutable std::uint64_t visited_slots_ = 0;
955+
std::uint64_t erased_rows_ = 0; mutable std::uint64_t visited_slots_ = 0, lookup_work_ = 0;
956956
std::uint64_t erased_digest_ = kFoldBasis;
957957
mutable std::shared_ptr<SequenceIndex> sequence_index_; mutable std::uint64_t sequence_queries_ = 0, sequence_rows_ = 0;
958958
// Physical policy only; the derived backing remains lazy and rebuildable.

‎src/source/pine_adapter.cpp‎

Lines changed: 75 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -897,7 +897,7 @@ PoocCloseFillViewSwitches& pooc_close_fill_view_switches() noexcept {
897897
} // namespace detail
898898

899899
// The retired-row compaction: the placement table's storage.
900-
void PlacementTable::place(std::uint64_t incarnation, std::unique_ptr<PlacementSnapshot> node) {
900+
void PlacementTable::place(std::uint64_t incarnation, std::unique_ptr<PlacementSnapshot> node) { if (old_only_) return place_old(incarnation, std::move(node));
901901
if (window_rows_ == 0 && (old_.empty() || incarnation > old_.back().first)) {
902902
// An empty window restarts at the new row, above every older row.
903903
window_.clear();
@@ -909,28 +909,28 @@ void PlacementTable::place(std::uint64_t incarnation, std::unique_ptr<PlacementS
909909
// window starts at, remembered only now): among the older rows.
910910
const auto at = std::lower_bound(old_.begin(), old_.end(), incarnation,
911911
[](const auto& entry, std::uint64_t key) { return entry.first < key; });
912-
old_.emplace(at, incarnation, std::move(node));
912+
placement_work_ += static_cast<std::uint64_t>(old_.end() - at) + 1U; old_.emplace(at, incarnation, std::move(node));
913913
return;
914914
}
915915
const auto index = head_ + static_cast<std::size_t>(incarnation - base_);
916-
if (index >= window_.size()) window_.resize(index + 1U);
917-
window_[index] = std::move(node);
916+
if (index >= window_.size()) grow_window(index);
917+
++placement_work_; window_[index] = std::move(node);
918918
++window_rows_;
919919
}
920920

921921
std::unique_ptr<PlacementSnapshot> PlacementTable::take(std::uint64_t incarnation) noexcept {
922-
if (incarnation >= base_) {
922+
if (!old_only_ && incarnation >= base_) {
923923
const std::uint64_t offset = incarnation - base_;
924924
if (offset >= window_.size() - head_) return nullptr;
925925
auto& slot = window_[head_ + static_cast<std::size_t>(offset)];
926-
if (slot) --window_rows_;
926+
if (slot) { --window_rows_; ++removal_work_; }
927927
return std::move(slot);
928928
}
929929
const auto found = std::lower_bound(old_.begin(), old_.end(), incarnation,
930-
[](const auto& entry, std::uint64_t key) { return entry.first < key; });
930+
[this](const auto& entry, std::uint64_t key) { ++lookup_work_; return entry.first < key; });
931931
if (found == old_.end() || found->first != incarnation) return nullptr;
932932
auto node = std::move(found->second);
933-
old_.erase(found);
933+
removal_work_ += static_cast<std::uint64_t>(old_.end() - found); old_.erase(found);
934934
return node;
935935
}
936936

@@ -952,7 +952,7 @@ void PlacementTable::remember_erased(const PlacementSnapshot& row) {
952952
sizeof row.command_sequence);
953953
}
954954

955-
void PlacementTable::compact() {
955+
void PlacementTable::compact() { if (compact_old()) return;
956956
constexpr std::size_t kDenseFloor = 64;
957957
for (;;) {
958958
while (head_ < window_.size() && !window_[head_]) {
@@ -29960,12 +29960,36 @@ void PlacementTable::prepare_place(std::uint64_t incarnation) {
2996029960
+ std::min(rows.capacity(), rows.max_size() - rows.capacity());
2996129961
rows.reserve(std::max(required, grown));
2996229962
};
29963+
if (old_only_) {
29964+
reserve(old_, old_.size() + 1U);
29965+
return;
29966+
}
2996329967
if (window_rows_ == 0 && (old_.empty() || incarnation > old_.back().first)) {
2996429968
reserve(window_, 1);
2996529969
} else if (incarnation < base_) {
2996629970
reserve(old_, old_.size() + 1);
2996729971
} else {
2996829972
const auto index = head_ + static_cast<std::size_t>(incarnation - base_);
29973+
constexpr std::size_t kDenseFloor = 64;
29974+
const auto span = std::max(window_.size() - head_,
29975+
static_cast<std::size_t>(incarnation - base_) + 1U);
29976+
const bool dense = span <= kDenseFloor || span <= 4U * window_rows_;
29977+
if (window_rows_ != 0 && !dense) {
29978+
reserve(old_, old_.size() + window_rows_ + 1U);
29979+
for (std::size_t slot = head_; slot < window_.size(); ++slot) {
29980+
if (!window_[slot]) continue;
29981+
old_.emplace_back(
29982+
base_ + static_cast<std::uint64_t>(slot - head_),
29983+
std::move(window_[slot]));
29984+
++placement_work_;
29985+
}
29986+
window_.clear();
29987+
head_ = 0;
29988+
window_rows_ = 0;
29989+
base_ = std::numeric_limits<std::uint64_t>::max();
29990+
old_only_ = true;
29991+
return;
29992+
}
2996929993
if (index >= window_.size()) reserve(window_, index + 1);
2997029994
}
2997129995
}
@@ -30568,3 +30592,45 @@ LookupIndexCounts probe_lookup_index(const NativeHostCache* cache) noexcept {
3056830592
}
3056930593

3057030594
} // namespace pineforge::source::detail
30595+
30596+
namespace pineforge::source {
30597+
30598+
// Storage policy and work counters are derived observers, outside broker
30599+
// state. Keep these bodies after the adapter's cited implementation regions.
30600+
void PlacementTable::reset_storage_work() noexcept {
30601+
old_only_ = false;
30602+
placement_work_ = 0;
30603+
lookup_work_ = 0;
30604+
removal_work_ = 0;
30605+
}
30606+
30607+
void PlacementTable::grow_window(std::size_t index) {
30608+
placement_work_ += static_cast<std::uint64_t>(index + 1U - window_.size());
30609+
window_.resize(index + 1U);
30610+
}
30611+
30612+
void PlacementTable::place_old(std::uint64_t incarnation,
30613+
std::unique_ptr<PlacementSnapshot> node) {
30614+
// Monotone incarnations append; an earlier incarnation still uses the
30615+
// same sorted representation and shifts only the rows above it.
30616+
const auto at = old_.empty() || incarnation > old_.back().first
30617+
? old_.end()
30618+
: std::lower_bound(old_.begin(), old_.end(), incarnation,
30619+
[this](const auto& entry, std::uint64_t key) {
30620+
++lookup_work_;
30621+
return entry.first < key;
30622+
});
30623+
placement_work_ += static_cast<std::uint64_t>(old_.end() - at) + 1U;
30624+
old_.emplace(at, incarnation, std::move(node));
30625+
}
30626+
30627+
bool PlacementTable::compact_old() noexcept {
30628+
if (!old_only_) return false;
30629+
if (old_.empty()) {
30630+
old_only_ = false;
30631+
base_ = high_water_ + 1U;
30632+
}
30633+
return true;
30634+
}
30635+
30636+
} // namespace pineforge::source
Lines changed: 5 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,5 @@
1+
# Placement storage: sparse placement work and representation equivalence.
2+
list(APPEND TEST_SOURCES test_placement_order_scaling)
3+
pineforge_add_unit_test(test_placement_order_scaling)
4+
list(APPEND TEST_SOURCES test_placement_table_differential)
5+
pineforge_add_unit_test(test_placement_table_differential)

0 commit comments

Comments
 (0)