Speed analysis of Feature and FeatureContainer data-structure.

[jessemorris]

Feature Iteration and Storage Benchmark

This follows an effort to improve the computation speed of the frontend feature tracking module. One small investigation into the (perhaps excessive) use of the Feature and associated FeatureContainer data-structures showed my over eager design has led to pretty significant overhead in several places. The following details the investigation.

Note: Written by Chat-GPT (free) and reviewed by myself.

Background / Initial Problem

The Dynamic SLAM feature-tracking pipeline performs a large number of operations over tracked image features. The existing FeatureContainer stores features in an std::unordered_map<TrackletId, Feature::Ptr>, with each feature accessed through a Feature class interface. This provides useful functionality and flexible lookup semantics, but it is potentially expensive for workloads that repeatedly iterate over many features.

The original question was whether this feature representation and iteration mechanism introduces a significant performance cost compared with a simpler, contiguous data representation such as a structure-of-arrays (SoA). This is particularly relevant for the visual tracking frontend, where feature data may be accessed multiple times per frame and where reducing per-feature overhead could contribute meaningfully to achieving the desired high processing rate.

These benchmarks were therefore designed to separate the cost of the existing container from the cost of the underlying feature representation. Two benchmark suites were used: FeatureIterationBenchmark compared the existing FeatureContainer directly against a simple SoA representation, while FeatureStorageBenchmark progressively replaced the expensive parts of the representation with simpler storage types.

---

Technical Background

The existing implementation has several sources of per-feature overhead. The primary container is an std::unordered_map, so iteration follows hash-table nodes rather than a contiguous array. Each map entry stores a Feature::Ptr, which introduces another pointer indirection before reaching the feature object. The Feature object itself contains its data behind the class implementation and exposes properties through accessor functions.

In contrast, an SoA stores each property in its own contiguous std::vector. For example, all x coordinates are stored next to one another, all y coordinates are stored next to one another, and so on. When an operation only needs a small subset of feature properties, this layout allows the CPU to traverse compact, contiguous memory with fewer cache misses and less pointer chasing.

A contiguous std::vector<Feature> removes the hash-table traversal and heap/pointer indirection, while retaining the existing Feature object and its interface. A std::vector<Feature::Ptr> removes the hash-table traversal but retains the pointer indirection. Comparing these four representations therefore gives a useful indication of where the observed overhead originates:

1. unordered_map<TrackletId, Feature::Ptr> — current implementation.
2. vector<Feature::Ptr> — removes hash-map traversal but retains pointers.
3. vector<Feature> — contiguous feature objects with the existing feature representation.
4. SoA — contiguous arrays containing only the required properties.

The important point is that the SoA comparison is not purely an AoS-versus-SoA comparison. The existing implementation combines a hash map, pointers/heap allocation, the Feature class representation, and its accessors. The benchmark is intended to quantify the practical cost of the complete representation used by the current pipeline.

---

FeatureIterationBenchmark Results

The first benchmark compared the existing FeatureContainer against a simple SoA representation. Across feature counts from 100 to 20,000, the results were approximately:

Number of features	FeatureContainer	SoA	Ratio
100	209.1 ns/feature	10.3 ns/feature	20.3×
500	210.1 ns/feature	9.93 ns/feature	21.2×
1,000	219.4 ns/feature	10.2 ns/feature	21.5×
5,000	222.6 ns/feature	10.35 ns/feature	21.5×
10,000	212.9 ns/feature	10.21 ns/feature	20.9×
20,000	213.8 ns/feature	10.16 ns/feature	21.0×

The important result is that the performance ratio remained approximately constant as the number of features increased. The current container required roughly 210–223 ns per feature, whereas the SoA required roughly 10 ns per feature.

For example, at 10,000 features, one complete traversal corresponds to approximately 2.13 ms for the existing container compared with approximately 0.10 ms for the SoA. This represents approximately 2 ms of additional cost for a single traversal of 10,000 features.

---

FeatureStorageBenchmark Results

The second benchmark was designed to determine whether this difference was primarily caused by the hash map, pointer indirection, or the Feature representation itself.

The results were:

Number of features	Map	vector<Feature::Ptr>	vector<Feature>	SoA
100	174.6 ns	165.5 ns	148.6 ns	9.83 ns
500	175.6 ns	164.3 ns	147.9 ns	9.78 ns
1,000	174.1 ns	165.0 ns	148.9 ns	9.86 ns
5,000	174.6 ns	164.8 ns	148.4 ns	9.79 ns
10,000	176.1 ns	169.4 ns	150.1 ns	9.89 ns
20,000	178.0 ns	168.2 ns	150.1 ns	9.83 ns

The results show a clear progression as the storage representation becomes simpler.

Replacing the unordered_map with a vector<Feature::Ptr> reduced the measured cost from approximately 175 ns/feature to approximately 165–169 ns/feature. This is only around a 5–6% reduction, indicating that hash-map traversal is not the dominant source of the overhead in this particular benchmark.

Replacing the pointer vector with a vector<Feature> reduced the cost further to approximately 148–150 ns/feature. This suggests that pointer indirection and the associated non-contiguous placement of individual Feature objects contribute additional overhead.

However, the largest difference remains between vector<Feature> and the SoA representation. The contiguous Feature representation still costs approximately 15× more per feature than the SoA. This indicates that the structure and access pattern of the Feature object itself are a substantial part of the measured cost when compared with a representation containing only the small set of scalar properties required by the benchmark.

---

Interpretation

The benchmarks indicate that the large performance difference is not primarily caused by std::unordered_map. Moving from the map to a vector of feature pointers produced only a relatively small improvement.

The results instead suggest that several smaller costs accumulate in the current representation, including pointer indirection, the memory layout of the Feature object, and accessing properties through the existing feature abstraction. The SoA benefits from having exactly the required data in compact, contiguous arrays, which is particularly favourable for sequential CPU processing and cache utilisation.

The approximately 21× difference observed in the first benchmark should therefore not be interpreted as saying that "SoA is 21× faster than AoS" in general. It is more accurately described as the measured difference between the current FeatureContainer implementation and the simplified SoA representation used in this benchmark.

The benchmark also shows that the performance characteristics are stable over the tested range. There was little change in ns/feature between 100 and 20,000 features, suggesting that the dominant cost is approximately linear in the number of features and that the relative overhead is not caused by a particular large-data threshold within this range.

---

Relevance to Dynamic SLAM / Feature Tracking

These results are useful for the current optimisation work because feature tracking is typically dominated by operations that repeatedly access feature properties such as keypoints, track IDs, object IDs, ages, and inlier status. If the same collection of features is traversed many times during a frame, the per-feature overhead can accumulate.

For example, using the FeatureIterationBenchmark result at 10,000 features, the measured difference between the current representation and the SoA was approximately 2.0 ms for one traversal. If an equivalent feature traversal were performed five times in a frame, the corresponding difference would be roughly 10 ms; ten such traversals would be roughly 20 ms. These numbers are illustrative extrapolations rather than measurements of the complete pipeline.

This makes the result potentially significant for a high-frequency visual tracking pipeline. At 20 Hz, the total frame budget is 50 ms, so several milliseconds spent repeatedly traversing feature data can become a meaningful fraction of the available budget.

However, these benchmarks do not by themselves establish that the entire feature system should be rewritten as an SoA. The benchmark isolates storage and iteration costs rather than measuring the complete tracking pipeline. The current Feature abstraction may also provide functionality that is valuable for correctness, maintainability, and different access patterns. In addition, the benchmark only measures the particular operations included in these tests.

The results therefore provide evidence that feature storage and iteration are worth considering as an optimisation target, especially if profiling shows that these operations occur repeatedly in the tracking frontend. They do not, on their own, justify replacing the current representation everywhere.

---

Conclusions

The benchmarks demonstrate that the current feature representation has measurable per-feature overhead compared with a compact SoA representation.

The main observations are:

• The current FeatureContainer is approximately 20–22× slower per feature than the tested SoA in the first iteration benchmark.
• At 10,000 features, this corresponds to approximately 2.0 ms of additional cost for one traversal in the benchmark.
• Replacing the unordered_map with vector<Feature::Ptr> only reduced the cost by approximately 5–6%, suggesting that the hash map is not the dominant bottleneck.
• Replacing vector<Feature::Ptr> with vector<Feature> reduced the cost further, showing that pointer indirection and object placement contribute measurable overhead.
• The SoA remained around 9.8 ns/feature, compared with approximately 150 ns/feature for vector<Feature>, showing that the feature object's representation/access pattern is also important.
• The measured per-feature costs were largely stable from 100 to 20,000 features, indicating consistent scaling over the tested range.

Overall, the results provide a strong indication that a more data-oriented feature representation could be beneficial for performance-critical sections of the Dynamic SLAM frontend. The next step should be to benchmark the specific feature-access patterns used by the actual tracking pipeline and determine whether an SoA or a hybrid representation can reduce runtime without unnecessarily complicating the rest of the system.

[jessemorris]

After some design work we have settled on the need for two different requirements:

1. Tracking: all features together → must be contiguous and OpenCV-friendly.
2. Geometry: grouped/filtering by object → wants fast per-object iteration and removal.

The following is a summary of the file design, aided once again by Chat-GPT (free)

NOTE: while the design will not change some of the internal feature properties may change in the future as the API is still under development.

FeatureBlockContainer

FeatureBlockContainer provides a contiguous, cache-friendly representation of feature tracks while retaining convenient per-object access.

The design uses a structure-of-arrays (SoA) representation as the underlying storage, with each object's features occupying a contiguous block within every array. Lightweight BlockView objects provide zero-copy access to individual object blocks when required.

The key design goal is to support both:

• Global SoA access for operations that process all features together.
• Per-object block access when an algorithm operates on a particular object.

This avoids maintaining separate feature containers for each object and avoids copying data when switching between global and per-object processing.

---

Design

The container owns a single contiguous set of feature arrays:

FeatureBlockContainer
│
├── points
├── previous_points
├── ids
├── object_ids
├── status
└── errors

Each object is assigned a contiguous range in every array.

For example, suppose the container contains three objects:

Object 10 → 3 features
Object 20 → 2 features
Object 30 → 4 features

The physical layout is:

                Contiguous feature storage

index:      0   1   2 | 3   4 | 5   6   7   8
           ────────────┼───────┼────────────────
object:       10       |  20   |       30
           ────────────┼───────┼────────────────

points:    [10][10][10]|[20][20]|[30][30][30][30]
prev:      [10][10][10]|[20][20]|[30][30][30][30]
ids:       [10][10][10]|[20][20]|[30][30][30][30]
status:    [10][10][10]|[20][20]|[30][30][30][30]
errors:    [10][10][10]|[20][20]|[30][30][30][30]

The container stores the layout internally:

BlockLayout
┌───────────┬───────┬─────┐
│ object_id │ begin │ end │
├───────────┼───────┼─────┤
│    10     │   0   │  3  │
│    20     │   3   │  5  │
│    30     │   5   │  9  │
└───────────┴───────┴─────┘

The caller only needs to specify the logical block dimensions:

FeatureBlockContainer features({
    {10, 3},
    {20, 2},
    {30, 4}
});

The physical offsets are calculated and managed internally.

---

Why Contiguous Blocks?

The feature tracker frequently processes all features together. Keeping each field in a contiguous array provides efficient sequential access:

for (size_t i = 0; i < features.size(); ++i)
{
    features.points[i] = ...;
    features.previous_points[i] = ...;
    features.ids[i] = ...;
}

This gives the hot global-processing path a simple SoA representation:

points       → [P0][P1][P2][P3][P4]...
previous     → [P0][P1][P2][P3][P4]...
ids          → [I0][I1][I2][I3][I4]...
status       → [S0][S1][S2][S3][S4]...
errors       → [E0][E1][E2][E3][E4]...

There are no per-feature heap allocations or pointer indirections.

This is particularly useful for operations such as:

• feature tracking
• status/error updates
• feature filtering
• geometric processing
• bulk feature compaction
• operations implemented over contiguous OpenCV arrays

---

Block Views

Although the global SoA representation is efficient for many operations, some algorithms naturally operate on one object at a time.

For example:

auto object = features.objectView(object_id);

A BlockView represents the object's existing memory rather than creating another container.

Conceptually:

FeatureBlockContainer

points:
┌────┬────┬────┬────┬────┬────┬────┬────┬────┐
│ 10 │ 10 │ 10 │ 20 │ 20 │ 30 │ 30 │ 30 │ 30 │
└────┴────┴────┴────┴────┴────┴────┴────┴────┘
                ▲
                │
                │ BlockView(20)
                │
                └───────────────┐
                                ▼
                           ┌────┬────┐
                           │ 20 │ 20 │
                           └────┴────┘

The view contains the block's layout and a pointer to the owning container.

It does not own or copy the feature data.

---

Zero-Copy Access

Accessing a block therefore requires no allocation or data movement:

auto object = features.objectView(20);

cv::Point2f* points = object.points();
cv::Point2f* previous = object.previousPoints();

These pointers point directly into the container's SoA arrays:

BlockView
   │
   ├── points ────────────────┐
   ├── previous_points ───────┤
   ├── ids ───────────────────┤
   ├── status ────────────────┤
   └── errors ────────────────┘
                               │
                               ▼
                    FeatureBlockContainer

For example:

object.points()[0]

is effectively accessing:

features.points[block.begin]

while:

object.points()[i]

accesses:

features.points[block.begin + i]

The view therefore provides the convenience of object-level indexing without sacrificing the underlying contiguous storage.

---

OpenCV Integration

The contiguous cv::Point2f blocks can also be wrapped directly by cv::Mat.

For example:

auto object = features.objectView(object_id);

cv::Mat points = object.pointsMat();
cv::Mat previous = object.previousPointsMat();

The resulting matrix is only an OpenCV header pointing at the existing memory:

FeatureBlockContainer
       │
       │ owns memory
       ▼
┌─────────────────────────────┐
│ points vector               │
│                             │
│ [P0][P1][P2][P3][P4]...     │
└──────────────┬──────────────┘
               │
               │ no copy
               ▼
        ┌─────────────┐
        │   cv::Mat   │
        │ rows = N    │
        │ cols = 1    │
        │ CV_32FC2    │
        └─────────────┘

This allows existing OpenCV algorithms to operate directly on an object's features:

auto object = features.objectView(object_id);

cv::Mat previous = object.previousPointsMat();
cv::Mat current = object.pointsMat();

cv::Mat H = cv::findHomography(
    previous,
    current,
    cv::RANSAC);

No intermediate std::vector<cv::Point2f> is required.

The same underlying feature storage can therefore be used by both custom pointer-based code and OpenCV APIs.

---

Global vs. Block Access

The container does not force every operation through BlockView.

Operations that naturally process the entire feature set can access the global arrays directly:

for (size_t i = 0; i < features.size(); ++i)
{
    auto& point = features.points[i];
    auto& id = features.ids[i];

    ...
}

Operations that are object-specific can use:

auto object = features.objectView(object_id);

for (size_t i = 0; i < object.size(); ++i)
{
    auto& point = object.points()[i];

    ...
}

Both paths access the same physical memory.

                     FeatureBlockContainer
                              │
             ┌────────────────┴────────────────┐
             │                                 │
             ▼                                 ▼
       Global SoA access                 BlockView access
             │                                 │
             │                                 │
             ▼                                 ▼
     all features                       one object
     contiguous                         contiguous
     memory                             sub-range
             │                                 │
             └──────────────┬──────────────────┘
                            ▼
                     same underlying data

This is the main advantage of the design: the representation is optimized for the common global case without making object-level algorithms expensive or awkward.

---

Memory Ownership

FeatureBlockContainer owns all feature memory.

The caller does not need to know where an object is physically stored.

For example:

FeatureBlockContainer features({
    {10, 100},
    {20, 50},
    {30, 200}
});

The container determines:

Object 10 → [0,   100)
Object 20 → [100, 150)
Object 30 → [150, 350)

The caller only knows:

object 10 has 100 features
object 20 has  50 features
object 30 has 200 features

This separation keeps physical memory management internal to the container.

---

Immutable Layout

The container's layout is determined when it is constructed.

This means the container knows:

object ID
    ↓
block
    ↓
[begin, end)

while the feature values themselves remain mutable.

For example, this is valid:

auto object = features.objectView(20);

object.points()[0] = cv::Point2f(100.0f, 50.0f);

The layout remains unchanged:

Object 20 → [100, 150)

while the data within that range can be modified.

This makes the memory layout predictable and allows BlockView to remain a lightweight representation of an existing range.

---

Construction

The preferred construction path is to specify the logical dimensions first:

FeatureBlockContainer features({
    {1, 100},
    {7, 50},
    {12, 75}
});

The container then:

1. validates object IDs
2. calculates the contiguous block layout
3. allocates each SoA array once
4. generates the corresponding object_ids
5. stores the block metadata

Result:

points          ────────────────┐
previous_points ────────────────┤
ids             ────────────────┤
object_ids      ────────────────┤── total = 225
status          ────────────────┤
errors          ────────────────┘

block_layout:
    1  → [0,   100)
    7  → [100, 150)
    12 → [150, 225)

Feature data can then be populated through the corresponding block view.

---

Merging

Containers can also be merged while maintaining the same contiguous representation.

For example:

Container A                 Container B

Object 10: 100 features     Object 10: 20 features
Object 20: 50 features      Object 30: 40 features

becomes:

Merged container

Object 10: 120 features
Object 20:  50 features
Object 30:  40 features

The resulting memory remains contiguous:

[ Object 10 ][ Object 20 ][ Object 30 ]

The merge performs the required copies once into the new container rather than introducing nested containers or fragmented allocations.

---

Performance

The design is intended to keep the abstraction cost of BlockView negligible compared with direct access to the underlying SoA storage.

The current performance measurements use N=10000 features.

Global SoA vs. BlockView

N=10000 | SoA=3.80771 ns/feature | ObjectView=3.95644 ns/feature | Overhead=3.90596%

The BlockView abstraction adds approximately 3.9% overhead relative to direct SoA access.

Per-object iteration

N=10000 | Direct ranges=3.78821 ns/feature | ObjectView=3.86047 ns/feature | Overhead=1.90752%

When iterating over features object-by-object, BlockView adds approximately 1.9% overhead compared with directly iterating over the corresponding memory ranges.

The results show that the object-level abstraction introduces only a small relative cost while providing convenient access to contiguous per-object feature blocks.

The absolute benchmark values will naturally depend on compiler optimisation, CPU architecture, and benchmark configuration. The important result is the small relative overhead between direct memory access and the BlockView abstraction.

---

Design Summary

FeatureBlockContainer is built around three principles:

1. One contiguous SoA representation

All features are stored in contiguous arrays:

points
previous_points
ids
object_ids
status
errors

This provides efficient global iteration and avoids per-feature allocations and pointer chasing.

2. Contiguous blocks per object

Each object's features occupy one contiguous range:

[ Object A ][ Object B ][ Object C ][ Object D ]

The physical layout is owned by the container.

3. Zero-copy block views

BlockView provides lightweight access to one of these ranges:

Global SoA
     │
     ├── global algorithms
     │
     └── BlockView
            │
            └── object-specific algorithms

Both access paths operate on the same memory.

The result is a representation that supports high-performance global feature processing, efficient per-object processing, and zero-copy interoperability with OpenCV, without maintaining separate feature storage for every object.