J05: Systems capstone: immutable spatial queries with verified parallel reads

Prerequisites and observable goals#

Level: Fully developed specialization capstone. A focused engine-relevant subsystem, not a commercial MMO architecture.

Purpose and exact query contract#

Given a fixed collection of two-dimensional point entities with unique unsigned 32-bit IDs, return all IDs whose coordinates lie inside an axis-aligned box, including its boundary. Results must be sorted by ID. Entity coordinates are finite and bounded in absolute value by $10^6$; there are at most $10^6$ entities. Query bounds are finite, ordered, and bounded in absolute value by $2\times10^6$. Cell size is finite and lies in $[0.01,10^6]$.

These explicit limits keep conversions and iteration ranges inside a defined teaching domain. A production engine may need different ranges, integer coordinates, hierarchical indexes, or world partitioning. Do not silently remove the limits and assume the proof still covers overflow or resource use. The project stores points, not extended shapes; collision detection between arbitrary meshes is outside its specification.

Build an immutable spatial snapshot owning its entities and bucket index. Queries do not mutate it. A batch-query function may execute independent queries in parallel, returning results in the same order as input boxes. The caller must keep the snapshot and query inputs alive and unmodified until the batch returns. The exercise is a standalone project; it changes no production codebase.

Architecture and representation#

Map coordinate $(x,y)$ to cell

Use an unordered map from integer cell pairs to vectors of entity indices. The owning entity vector stores each point once. Bucket values refer to stable indices rather than pointers into a vector that might later reallocate. Because construction completes before publication and there is no mutation afterward, those indices remain meaningful during queries.

Negative coordinates require floor, not truncation toward zero. For $s=10$, $x=-0.1$ belongs to cell $-1$, while $x=0.1$ belongs to cell $0$. Using an integer cast directly would put both into zero and can break cell-range reasoning at boundaries. The reference computes floor before converting within the explicit numeric bounds.

The grid is a schematic with unit cells. The query’s upper-right cell may contain points outside the exact box, so bucket membership is only a candidate filter. Every candidate must still pass the inclusive coordinate comparisons.

Correctness argument and fallback#

For any point inside an ordered query box, monotonicity of floor with positive cell size places its cell coordinate between the cells of the corresponding lower and upper bounds. Therefore iterating every integer cell in that rectangle visits the point’s bucket. The exact containment test then accepts it. Conversely, every emitted point passes the exact comparisons, so there are no false positive IDs in the final result. Unique input IDs and one bucket assignment per entity prevent duplicate output from normal cell iteration; sorting supplies the deterministic output contract.

A very large box over a sparse world may intersect enormous numbers of empty cells. The reference estimates the rectangular cell count and falls back to a brute-force scan when it exceeds four times the entity count, with a minimum budget of one. It compares $n_x$ to $\text{budget}/n_y$ rather than multiplying potentially large counts. Under the validated ranges, $n_y$ is positive and coordinate differences remain representable. This fallback is a resource-bound design choice, not a theorem that four is optimal.

Worst-case query work can still be linear in all entities plus output sorting. Hash-table operations have expected, not universal constant-time performance. A dense cluster in one bucket gives little filtering benefit. Report both candidates examined and hits returned so an impressive time does not hide a workload that became easier for unrelated reasons.

Parallel ownership and exception handling#

Allocate the result vector to its final size before launching workers. An atomic counter assigns each query index to at most one worker. Each worker reads the same immutable index and writes only its assigned result element. The vector structure is not resized while workers run. This gives disjoint output ownership; it is not a license to mutate arbitrary shared containers concurrently.

The atomic counter uses relaxed ordering because its job is unique index allocation, not publication of mutable entity data. Construction and thread start establish the needed input visibility, and joining workers precedes reading final results. If a query throws, a protected exception pointer records the first failure and an atomic stop flag discourages additional work. All started threads are joined before the exception is rethrown. The stop flag is a best-effort early exit, not cancellation of already executing queries.

A batch function that returned while workers still referenced local vectors would violate lifetimes even if every individual query were mathematically correct. A function that resized results concurrently would also invalidate the disjoint-element argument. This is why ownership, memory model, and algorithmic correctness must be explained together.

Milestones and acceptance criteria#

First implement brute-force inclusive queries and validate inputs. Next build the grid buckets and compare every query with brute force on small deterministic cases. Add negative coordinates, points exactly on each boundary, empty input, duplicate IDs, invalid boxes, and a huge-box fallback. Then compare generated queries and implement parallel batching only after serial correctness is established. Finally benchmark fixed workloads with output validation outside the timed query regions.

The C++ tests include 500 generated entities and 400 generated boxes, exact boundary cases, duplicate-ID rejection, fallback behavior, and parallel/serial comparison. Release assertions are explicitly enabled. The same three C++ test programs were run under address and undefined-behavior sanitizers; no ThreadSanitizer run or formal concurrent proof checker is claimed.

Complete solutions: J05#

Compare the first step where your work differs. A corrected answer is not yet an independent success.

Open every solution

#pragma once
#include <algorithm>
#include <atomic>
#include <cmath>
#include <cstddef>
#include <cstdint>
#include <exception>
#include <limits>
#include <mutex>
#include <stdexcept>
#include <thread>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

namespace learning {
struct Entity { std::uint32_t id; double x, y; };
struct Box { double left, bottom, right, top; };
struct Result {
    std::vector<std::uint32_t> ids;
    std::size_t candidates = 0, buckets_probed = 0;
    bool fallback = false;
};
struct Cell {
    std::int64_t x, y;
    bool operator==(const Cell&) const = default;
};
struct CellHash {
    std::size_t operator()(Cell c) const noexcept {
        const auto a = std::hash<std::int64_t>{}(c.x);
        const auto b = std::hash<std::int64_t>{}(c.y);
        return a ^ (b + std::size_t{0x9e3779b9U} + (a << 6) + (a >> 2));
    }
};
class SpatialIndex {
    std::vector<Entity> entities_;
    double cell_size_;
    std::unordered_map<Cell, std::vector<std::size_t>, CellHash> cells_;
    [[nodiscard]] Cell cell(double x, double y) const {
        return {static_cast<std::int64_t>(std::floor(x / cell_size_)),
                static_cast<std::int64_t>(std::floor(y / cell_size_))};
    }
    static bool contains(const Box& b, const Entity& e) {
        return e.x >= b.left && e.x <= b.right &&
               e.y >= b.bottom && e.y <= b.top;
    }
public:
    static void validate_box(const Box& b) {
        for (double x : {b.left, b.bottom, b.right, b.top})
            if (!std::isfinite(x) || std::abs(x) > 2'000'000.)
                throw std::invalid_argument("query outside finite teaching domain");
        if (b.left > b.right || b.bottom > b.top)
            throw std::invalid_argument("inverted bounds");
    }
    explicit SpatialIndex(std::vector<Entity> entities, double cell_size)
        : entities_(std::move(entities)), cell_size_(cell_size) {
        if (!std::isfinite(cell_size) || cell_size < .01 || cell_size > 1'000'000.)
            throw std::invalid_argument("cell size outside [0.01,1000000]");
        if (entities_.size() > 1'000'000)
            throw std::length_error("entity budget exceeded");
        std::unordered_set<std::uint32_t> ids;
        for (std::size_t i = 0; i < entities_.size(); ++i) {
            const auto& e = entities_[i];
            if (!std::isfinite(e.x) || !std::isfinite(e.y) ||
                std::abs(e.x) > 1'000'000. || std::abs(e.y) > 1'000'000.)
                throw std::invalid_argument("entity outside finite teaching domain");
            if (!ids.insert(e.id).second)
                throw std::invalid_argument("duplicate entity ID");
            cells_[cell(e.x, e.y)].push_back(i);
        }
    }
    [[nodiscard]] Result brute(const Box& box) const {
        validate_box(box);
        Result result;
        result.candidates = entities_.size();
        result.fallback = true;
        for (const auto& e : entities_)
            if (contains(box, e)) result.ids.push_back(e.id);
        std::sort(result.ids.begin(), result.ids.end());
        return result;
    }
    [[nodiscard]] Result query(const Box& box) const {
        validate_box(box);
        const Cell lo = cell(box.left, box.bottom);
        const Cell hi = cell(box.right, box.top);
        const auto nx = static_cast<std::uint64_t>(hi.x - lo.x + 1);
        const auto ny = static_cast<std::uint64_t>(hi.y - lo.y + 1);
        const auto budget = std::max<std::uint64_t>(1, 4 * entities_.size());
        if (nx > budget / ny) return brute(box); // avoid enormous empty-cell scans
        Result result;
        for (auto x = lo.x; x <= hi.x; ++x) {
            for (auto y = lo.y; y <= hi.y; ++y) {
                ++result.buckets_probed;
                const auto it = cells_.find({x, y});
                if (it == cells_.end()) continue;
                for (auto i : it->second) {
                    ++result.candidates;
                    if (contains(box, entities_[i])) result.ids.push_back(entities_[i].id);
                }
            }
        }
        std::sort(result.ids.begin(), result.ids.end());
        return result;
    }
};

// A read-only snapshot; distinct workers write distinct result elements.
inline std::vector<Result> parallel_query(const SpatialIndex& index,
                                         const std::vector<Box>& boxes,
                                         unsigned workers) {
    if (workers < 1 || workers > 32) throw std::invalid_argument("workers in [1,32]");
    for (const auto& box : boxes) SpatialIndex::validate_box(box);
    std::vector<Result> results(boxes.size());
    std::atomic<std::size_t> next{0};
    std::atomic<bool> stop{false};
    std::exception_ptr failure;
    std::mutex failure_mutex;
    std::vector<std::jthread> threads;
    for (unsigned w = 0; w < workers; ++w) {
        threads.emplace_back([&] {
            try {
                while (!stop.load(std::memory_order_relaxed)) {
                    const auto i = next.fetch_add(1, std::memory_order_relaxed);
                    if (i >= boxes.size()) break;
                    results[i] = index.query(boxes[i]);
                }
            } catch (...) {
                std::lock_guard lock(failure_mutex);
                if (!failure) failure = std::current_exception();
                stop.store(true, std::memory_order_relaxed);
            }
        });
    }
    threads.clear(); // jthread destruction joins; results are observed afterward
    if (failure) std::rethrow_exception(failure);
    return results;
}
} // namespace learning

Build and test commands#

cmake -S . -B build -DCMAKE_BUILD_TYPE=Release
cmake --build build --parallel 2
ctest --test-dir build --output-on-failure
./build/spatial_benchmark

On multi-configuration generators, choose the corresponding Release configuration and executable path as described in the README. The commands were executed on Linux with GCC 14.2.0 and CMake 3.31.6; Windows/MSVC instructions are provided but were not executed here.

Observed benchmark, not a universal speed claim#

The reference benchmark used 20,000 uniformly generated entities in a square region, 1,000 fixed-size query boxes, seed 20260905, cell size 20, one warm-up, and five alternating-order repetitions. It validated indexed results against brute force before accepting the timing comparison. The recorded build time was $2.59269$ ms; median indexed query-batch time was $0.410511$ ms and median brute-force batch time was $63.5201$ ms. Across the query set, 8,025 candidates were examined and 1,964 hits returned.

This is approximately a $154.7$-fold query-batch speedup for this particular sparse, selective, single-threaded workload. Build time is excluded from both query timings and must be amortized only when the application actually reuses the snapshot. A clustered distribution, giant query, frequent rebuild, tiny entity set, different compiler, or loaded machine can change the result dramatically. Parallel batching was correctness-tested but no parallel speedup is claimed from this benchmark.

The comparison’s main mechanism is reduced candidate work, not a mysterious property of hashing. Brute force examines every entity for every query, while the grid visits nearby buckets and exact-tests a much smaller subset on this distribution. The fallback ensures that a huge box does not spend unbounded time probing empty cells, but its threshold is an implementation choice to tune with representative measurements.

Failure cases and debugging strategy#

Missing hits near negative coordinates suggest truncation instead of floor. Missing hits on the upper boundary suggest an exclusive comparison or an omitted high cell. Duplicate results suggest duplicated entities or repeated bucket visits. A crash after rebuilding suggests a lifetime violation involving readers of the old snapshot. A parallel-only discrepancy suggests shared mutation, output ownership, or insufficient joining; adding sleeps is not a correctness fix.

The immutable design trades update convenience for simple reader reasoning. A moving world can build a new snapshot and publish it through an ownership mechanism that keeps the old one alive for current readers. Incremental mutation, lock-free reclamation, generational handles, and spatial hierarchies are meaningful unassigned extensions, but they require new proofs and tests. Do not describe this capstone as already implementing those systems.

Capstone rubric and portfolio evidence#

Score each dimension from 0 to 3. Setup: the point, coordinate, inclusion, and lifetime contracts are explicit. Reasoning: candidate coverage, exact filtering, fallback bounds, and parallel ownership are defended. Implementation: validated input and failure paths match the public interface. Verification: deterministic boundaries, generated oracle comparison, release checks, and sanitizer evidence are reproducible. Communication: the report includes build commands, benchmark methodology, limitations, and the learner’s independent contribution.

A strong portfolio package includes a short design document, a one-command test path, a sample benchmark report with environment, and a section titled “What this does not prove.” That section should mention workload dependence, no production integration, no race-detector run, no real MMO load test, and no guarantee for arbitrary unbounded coordinates. These limitations make the evidence more useful to reviewers, not less.

Retention and readiness#

Retrieve C03 ownership, C06 expected/amortized distinctions, C09 locality, C10 joining and atomics, and C14 measurement. Completion means you can rebuild the subsystem from a specification, diagnose an unfamiliar boundary defect, and explain the benchmark without relying on the engine project name as evidence.