slots and Array-Backed Vertex Storage

The memory a geofence index occupies is dominated by one decision made early and rarely revisited: how a polygon’s vertices are stored. A ring held as a Python list of (lon, lat) tuples is 118 bytes per vertex — a list slot, a tuple header, two float objects, and the pointer chasing that comes with them — against 16 bytes for two float64 arrays. At 1.2 million polygons averaging 96 vertices that is the difference between 13.6 GB and 1.8 GB, and the layout change makes the containment kernel three times faster as a side effect. This page sits under memory footprint of streaming polygon indexes within Spatial Indexing for Real-Time Checks.

Concept and specification #

Three costs compound in the object-per-vertex layout. The header cost: every Python object carries 16 bytes of reference count and type pointer before any data. The indirection cost: a list of tuples of floats is three pointer hops from the list to a coordinate. The locality cost: consecutive vertices are separate heap allocations that may be anywhere, so walking a ring is a walk through scattered cache lines.

A structure-of-arrays layout removes all three at once. One float64 array holds every x coordinate of every ring in the index, another holds every y, and a polygon is a (offset, count) pair into them. Vertices of one ring are contiguous, so a ring walk is a linear scan that the prefetcher handles perfectly.

The last row’s 16 bytes per vertex is the floor — two doubles and nothing else — and the per-ring NumPy row shows why the shared arena matters beyond the arithmetic: a NumPy array per ring carries a ~96-byte object header each, which at 1.2 million rings is another 115 MB and, more importantly, breaks contiguity between rings so a batch covering several polygons touches several distant allocations.

The Python-object side has its own multiplier. A per-fence metadata object with __dict__ costs 152 bytes before its fields; the same class with __slots__ costs 56.

$$\text{total}=n_{\text{fences}}\cdot s_{\text{meta}}+n_{\text{vertices}}\cdot s_{\text{vertex}}$$

At 1.2 M fences and 115 M vertices, moving $s_{\text{meta}}$ from 152 to 56 saves 115 MB and moving $s_{\text{vertex}}$ from 118 to 16 saves 11.7 GB — a useful reminder about where to spend effort.

Step-by-step implementation #

1. Put the coordinates in one shared arena and reference it by offset.

from __future__ import annotations
from dataclasses import dataclass
import numpy as np

class VertexArena:
    """Every ring's coordinates, contiguous, in two arrays."""

    __slots__ = ("xs", "ys", "_n")

    def __init__(self, capacity: int) -> None:
        self.xs = np.empty(capacity, dtype=np.float64)
        self.ys = np.empty(capacity, dtype=np.float64)
        self._n = 0

    def append_ring(self, xs: np.ndarray, ys: np.ndarray) -> tuple[int, int]:
        n = xs.size
        if self._n + n > self.xs.size:
            self._grow(max(self.xs.size * 2, self._n + n))
        off = self._n
        self.xs[off:off + n] = xs
        self.ys[off:off + n] = ys
        self._n += n
        return off, n

    def _grow(self, capacity: int) -> None:
        self.xs = np.resize(self.xs, capacity)
        self.ys = np.resize(self.ys, capacity)

@dataclass(slots=True, frozen=True)
class FenceRef:
    """56 bytes: no __dict__, no per-ring array objects."""
    fence_id: int
    offset: int
    count: int
    minx: float
    miny: float
    maxx: float
    maxy: float

2. Write the kernel against slices, not objects. A containment test that takes (xs, ys, offset, count) reads a contiguous run and vectorises naturally.

def contains(arena: VertexArena, ref: FenceRef, px: float, py: float) -> bool:
    """Vectorised ray casting over a contiguous vertex run."""
    if px < ref.minx or px > ref.maxx or py < ref.miny or py > ref.maxy:
        return False
    x = arena.xs[ref.offset:ref.offset + ref.count]
    y = arena.ys[ref.offset:ref.offset + ref.count]
    x2 = np.roll(x, -1)
    y2 = np.roll(y, -1)
    straddles = (y > py) != (y2 > py)
    with np.errstate(divide="ignore", invalid="ignore"):
        xint = x + (py - y) * (x2 - x) / (y2 - y)
    return bool(np.count_nonzero(straddles & (px < xint)) & 1)

3. Use __slots__ on every per-fence and per-pair class. It is a one-line change with no behavioural cost beyond losing dynamic attributes, and dynamic attributes on a hot data class are a bug rather than a feature.

4. Store the interior rings in the same arena. A polygon with holes gets several (offset, count) pairs; keeping them adjacent means a containment test that must check holes touches the same cache lines it already loaded.

5. Compact on rewrite, not on delete. Deleting a fence leaves a hole in the arena; reclaiming it immediately means moving everything after it and invalidating every offset. Mark the range free, reuse it for a ring of the same size or smaller, and compact during the periodic full rebuild that the snapshot cadence already schedules.

6. Keep the arena’s dtype at float64. float32 halves the memory and costs about 1.1 m of positional precision at temperate latitudes in degrees — comparable to the fence-authoring precision and therefore not obviously safe. Where memory demands it, store local metre coordinates in float32, which gives millimetre precision over a 40 km frame, rather than degrees.

Benchmark and verification #

Measured on 1.2M polygons, 96 vertices mean, 115M vertices total:

The second row is the instructive disappointment: __slots__ alone saves 0.7% here, because the per-fence metadata objects were never the problem — the vertices were. __slots__ is worth applying everywhere and is not the memory fix; it becomes significant only on the per-pair structures discussed in boundary hysteresis, where the object count is large and each object is small.

The cache-miss column explains the speed. Four misses per containment test against 41 is the whole of the 3.1× improvement — the arithmetic is identical, and the difference is entirely how far the CPU has to reach for the next vertex. That is also why the P99 improves more than the P50: the tail was dominated by tests against large polygons whose scattered vertices missed repeatedly.

Verify memory with tracemalloc and RSS together, because they answer different questions: tracemalloc attributes Python-level allocation and will show the arena as a handful of large blocks, while RSS reveals the fragmentation that a growing arena can cause. A gap between them that widens over hours means the arena is being resized repeatedly, which is a capacity-planning fix rather than a layout one.

Failure modes and edge cases #

The last row is a real cost in the code above and worth being explicit about, because the implementation is written for clarity rather than for the hot path. np.roll allocates a new array per call, so the vectorised kernel as written allocates twice per containment test — precisely the churn the arena allocation discipline exists to remove. The production form either stores each ring with its first vertex repeated at the end, so the “next vertex” is simply the following element, or indexes with an explicit wrap. Repeating the first vertex costs 16 bytes per ring and removes both allocations.

One more caution about the shared arena: it makes every fence’s geometry reachable from one object, so a leaked reference to the arena keeps the whole index alive. Under the copy-on-write publication described in copy-on-write snapshots for lock-free fence reads, that is exactly the intended behaviour — a reader holding a snapshot holds its arena — but it means a leaked snapshot costs gigabytes rather than megabytes, which raises the stakes on the live-version alerting that page recommends.

Related #

• Memory Footprint of Streaming Polygon Indexes — the parent topic and the wider footprint model.
• Object Pooling for Polygon Vertex Buffers — reusing buffers once the layout is flat.
• Arena Allocation for Per-Event Spatial Scratch — the same idea applied to per-event temporaries.