Skip to content

Commit 075d86f

Browse files
committed
Keep sparse placement inserts amortized O(1)
Use the compaction density rule before moving a sparse incarnation window to ordered retained storage. Dense books retain direct slot access. Compare storage transitions and erased history against a fixed-seed map model. Measure placement work, lookup comparisons and removal shifts using input-dependent dense and sparse books. Ordered storage trades sparse-window allocation for logarithmic lookup. Removing a row shifts the vector's later rows, so repeated oldest-first removal can take quadratic total work. The work test measures this cost; the placement bound does not claim constant-time lookup or removal.
1 parent 164e6ca commit 075d86f

5 files changed

Lines changed: 564 additions & 17 deletions

File tree

‎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_]) {
@@ -29937,12 +29937,36 @@ void PlacementTable::prepare_place(std::uint64_t incarnation) {
2993729937
+ std::min(rows.capacity(), rows.max_size() - rows.capacity());
2993829938
rows.reserve(std::max(required, grown));
2993929939
};
29940+
if (old_only_) {
29941+
reserve(old_, old_.size() + 1U);
29942+
return;
29943+
}
2994029944
if (window_rows_ == 0 && (old_.empty() || incarnation > old_.back().first)) {
2994129945
reserve(window_, 1);
2994229946
} else if (incarnation < base_) {
2994329947
reserve(old_, old_.size() + 1);
2994429948
} else {
2994529949
const auto index = head_ + static_cast<std::size_t>(incarnation - base_);
29950+
constexpr std::size_t kDenseFloor = 64;
29951+
const auto span = std::max(window_.size() - head_,
29952+
static_cast<std::size_t>(incarnation - base_) + 1U);
29953+
const bool dense = span <= kDenseFloor || span <= 4U * window_rows_;
29954+
if (window_rows_ != 0 && !dense) {
29955+
reserve(old_, old_.size() + window_rows_ + 1U);
29956+
for (std::size_t slot = head_; slot < window_.size(); ++slot) {
29957+
if (!window_[slot]) continue;
29958+
old_.emplace_back(
29959+
base_ + static_cast<std::uint64_t>(slot - head_),
29960+
std::move(window_[slot]));
29961+
++placement_work_;
29962+
}
29963+
window_.clear();
29964+
head_ = 0;
29965+
window_rows_ = 0;
29966+
base_ = std::numeric_limits<std::uint64_t>::max();
29967+
old_only_ = true;
29968+
return;
29969+
}
2994629970
if (index >= window_.size()) reserve(window_, index + 1);
2994729971
}
2994829972
}
@@ -30545,3 +30569,45 @@ LookupIndexCounts probe_lookup_index(const NativeHostCache* cache) noexcept {
3054530569
}
3054630570

3054730571
} // namespace pineforge::source::detail
30572+
30573+
namespace pineforge::source {
30574+
30575+
// Storage policy and work counters are derived observers, outside broker
30576+
// state. Keep these bodies after the adapter's cited implementation regions.
30577+
void PlacementTable::reset_storage_work() noexcept {
30578+
old_only_ = false;
30579+
placement_work_ = 0;
30580+
lookup_work_ = 0;
30581+
removal_work_ = 0;
30582+
}
30583+
30584+
void PlacementTable::grow_window(std::size_t index) {
30585+
placement_work_ += static_cast<std::uint64_t>(index + 1U - window_.size());
30586+
window_.resize(index + 1U);
30587+
}
30588+
30589+
void PlacementTable::place_old(std::uint64_t incarnation,
30590+
std::unique_ptr<PlacementSnapshot> node) {
30591+
// Monotone incarnations append; an earlier incarnation still uses the
30592+
// same sorted representation and shifts only the rows above it.
30593+
const auto at = old_.empty() || incarnation > old_.back().first
30594+
? old_.end()
30595+
: std::lower_bound(old_.begin(), old_.end(), incarnation,
30596+
[this](const auto& entry, std::uint64_t key) {
30597+
++lookup_work_;
30598+
return entry.first < key;
30599+
});
30600+
placement_work_ += static_cast<std::uint64_t>(old_.end() - at) + 1U;
30601+
old_.emplace(at, incarnation, std::move(node));
30602+
}
30603+
30604+
bool PlacementTable::compact_old() noexcept {
30605+
if (!old_only_) return false;
30606+
if (old_.empty()) {
30607+
old_only_ = false;
30608+
base_ = high_water_ + 1U;
30609+
}
30610+
return true;
30611+
}
30612+
30613+
} // 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)
Lines changed: 196 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,196 @@
1+
#include <pineforge/source/pine_adapter.hpp>
2+
3+
#include <cstddef>
4+
#include <cstdint>
5+
#include <cstdio>
6+
#include <stdexcept>
7+
#include <string>
8+
#include <vector>
9+
10+
namespace {
11+
using namespace pineforge;
12+
using source::PlacementSnapshot;
13+
using source::PlacementTable;
14+
15+
struct PlacementWorkTag {
16+
using type = std::uint64_t PlacementTable::*;
17+
friend type access(PlacementWorkTag);
18+
};
19+
20+
struct LookupWorkTag {
21+
using type = std::uint64_t PlacementTable::*;
22+
friend type access(LookupWorkTag);
23+
};
24+
25+
struct RemovalWorkTag {
26+
using type = std::uint64_t PlacementTable::*;
27+
friend type access(RemovalWorkTag);
28+
};
29+
30+
struct OldOnlyTag {
31+
using type = bool PlacementTable::*;
32+
friend type access(OldOnlyTag);
33+
};
34+
35+
template<class Tag, typename Tag::type Member>
36+
struct PrivateAccess {
37+
friend typename Tag::type access(Tag) { return Member; }
38+
};
39+
40+
template struct PrivateAccess<PlacementWorkTag, &PlacementTable::placement_work_>;
41+
template struct PrivateAccess<LookupWorkTag, &PlacementTable::lookup_work_>;
42+
template struct PrivateAccess<RemovalWorkTag, &PlacementTable::removal_work_>;
43+
template struct PrivateAccess<OldOnlyTag, &PlacementTable::old_only_>;
44+
45+
struct Result {
46+
std::size_t live = 0;
47+
std::uint64_t work = 0;
48+
};
49+
50+
void require(bool condition, const std::string& message) {
51+
if (!condition) throw std::runtime_error(message);
52+
}
53+
54+
PlacementSnapshot resting_limit(std::size_t serial) {
55+
PlacementSnapshot row;
56+
row.family = source::PineOrderFamily::Order;
57+
row.source_id = "resting-book";
58+
row.comment = "never-fill-" + std::to_string(serial);
59+
row.requested_qty = 1.0;
60+
row.is_long = true;
61+
row.opening = true;
62+
row.exit_levels.limit = 1.0;
63+
row.command_sequence = static_cast<std::uint64_t>(serial + 1);
64+
return row;
65+
}
66+
67+
std::uint64_t incarnation_for(std::size_t serial) {
68+
// The native handle space can contain gaps when other accepted commands
69+
// share a run. The gap grows with the input serial without using a
70+
// population-specific literal.
71+
const auto stride = serial / 100U + 1U;
72+
return 1U + static_cast<std::uint64_t>(serial) * stride;
73+
}
74+
75+
Result place_book(std::size_t count) {
76+
PlacementTable table;
77+
for (std::size_t serial = 0; serial < count; ++serial) {
78+
const auto incarnation = incarnation_for(serial);
79+
const auto inserted = table.try_emplace(incarnation, resting_limit(serial));
80+
require(inserted.second, "every never-fill limit placement has a fresh incarnation");
81+
}
82+
83+
require(table.size() == count,
84+
"live placement count follows the input: " + std::to_string(count));
85+
std::uint64_t previous = 0;
86+
std::size_t visited = 0;
87+
table.visit_rows([&](std::uint64_t incarnation, const PlacementSnapshot& row) {
88+
require(incarnation > previous, "placement rows remain incarnation ordered");
89+
require(row.family == source::PineOrderFamily::Order
90+
&& row.exit_levels.limit == 1.0
91+
&& row.comment == "never-fill-" + std::to_string(visited),
92+
"each input limit remains a distinct never-fill order");
93+
previous = incarnation;
94+
++visited;
95+
return false;
96+
});
97+
require(visited == count, "every live order is present after placement");
98+
99+
const auto work = table.*access(PlacementWorkTag{});
100+
std::printf("placement-order N=%zu live=%zu work=%llu per_order=%.3f\n",
101+
count, table.size(), static_cast<unsigned long long>(work),
102+
static_cast<double>(work) / static_cast<double>(count));
103+
return {table.size(), work};
104+
}
105+
106+
void density_and_access_work(std::size_t count, bool sparse) {
107+
PlacementTable table;
108+
table.fixture_use_memory_auxiliary_tables();
109+
const std::uint64_t stride = sparse ? count + 1U : 1U;
110+
const auto key = [&](std::size_t serial) { return 1U + serial * stride; };
111+
for (std::size_t serial = 0; serial != count; ++serial) {
112+
require(table.try_emplace(key(serial), resting_limit(serial)).second,
113+
"density input must contain distinct rows");
114+
require((table.*access(OldOnlyTag{})) == (sparse && serial != 0),
115+
"only a sparse book should enter ordered storage");
116+
}
117+
118+
// One comparison is counted at each binary-search predicate evaluation.
119+
// The bound comes from the input population, rather than a pinned result.
120+
std::uint64_t comparison_bound = 1;
121+
for (auto remaining = count; remaining > 1; remaining /= 2U) ++comparison_bound;
122+
const auto before_lookup = table.*access(LookupWorkTag{});
123+
const PlacementTable& rows = table;
124+
for (std::size_t serial = 0; serial != count; ++serial) {
125+
const auto found = rows.find(key(serial));
126+
require(found != rows.end() && found->second.comment == resting_limit(serial).comment,
127+
"lookup must return the input row");
128+
require(rows.contains(key(serial)), "contains must find every input row");
129+
require(rows.at(key(serial)).command_sequence == serial + 1U,
130+
"at must return the input sequence");
131+
}
132+
const auto lookup_work = (table.*access(LookupWorkTag{})) - before_lookup;
133+
require(sparse ? lookup_work >= 3U * count : lookup_work == 0,
134+
"ordered lookup comparisons must be measured; dense lookup stays direct");
135+
require(lookup_work <= 3U * count * comparison_bound, "lookup exceeds binary-search bound");
136+
137+
const auto before_removal = table.*access(RemovalWorkTag{});
138+
const auto before_search = table.*access(LookupWorkTag{});
139+
const auto retired = count / 2U;
140+
std::uint64_t expected_removal_work = 0;
141+
for (std::size_t serial = 0; serial != retired; ++serial) {
142+
// Erasing the oldest row shifts every remaining vector element.
143+
// Count the removed element too; a dense slot removal costs one.
144+
expected_removal_work += sparse ? count - serial : 1U;
145+
require(table.erase(key(serial)), "oldest-half removal must succeed");
146+
}
147+
const auto removal_work = (table.*access(RemovalWorkTag{})) - before_removal;
148+
const auto removal_search = (table.*access(LookupWorkTag{})) - before_search;
149+
require(removal_work == expected_removal_work, "removal did not count actual shifted rows");
150+
require(sparse ? removal_search >= 2U * retired : removal_search == 0,
151+
"removal must measure its locate and take searches");
152+
require(removal_search <= 2U * retired * comparison_bound,
153+
"removal search exceeds binary-search bound");
154+
require(table.size() == count - retired && table.erased_rows() == retired,
155+
"removal must preserve the requested live and retired populations");
156+
for (std::size_t serial = 0; serial != count; ++serial)
157+
require(rows.contains(key(serial)) == (serial >= retired),
158+
"converted removal changed the wrong row");
159+
std::printf("placement-access N=%zu sparse=%u lookup=%llu removal_search=%llu removal=%llu\n",
160+
count, static_cast<unsigned>(sparse),
161+
static_cast<unsigned long long>(lookup_work),
162+
static_cast<unsigned long long>(removal_search),
163+
static_cast<unsigned long long>(removal_work));
164+
}
165+
} // namespace
166+
167+
int main() {
168+
try {
169+
for (const auto count : {258U, 516U, 1032U}) {
170+
density_and_access_work(count, false);
171+
density_and_access_work(count, true);
172+
}
173+
const std::vector<std::size_t> sizes{1000, 5000, 20000};
174+
std::vector<Result> results;
175+
results.reserve(sizes.size());
176+
for (const auto count : sizes) results.push_back(place_book(count));
177+
178+
for (std::size_t index = 0; index < results.size(); ++index)
179+
require(results[index].live == sizes[index],
180+
"the measured population is not the requested population");
181+
182+
for (std::size_t index = 1; index < results.size(); ++index) {
183+
// The work per placement may vary by a constant representation
184+
// transition, but it cannot rise with the live book.
185+
require(results[index].work * sizes[0]
186+
<= results[0].work * sizes[index] * 2U,
187+
"placement work per order grows with the live order book");
188+
require(results[index].work <= sizes[index] * 4U,
189+
"placement work exceeds a constant amortised bound");
190+
}
191+
return 0;
192+
} catch (const std::exception& error) {
193+
std::fprintf(stderr, "test_placement_order_scaling: %s\n", error.what());
194+
return 1;
195+
}
196+
}

0 commit comments

Comments
 (0)