[Bugfix] EntityCollection iterator is O(n²) due to index-based list traversal #159

New issue

Closed

opened 2025-12-28 05:00:53 +00:00 by john · 0 comments

john commented

2025-12-28 05:00:53 +00:00

Owner

Summary

The EntityCollection iterator (UIEntityCollectionIter::next) has O(n²) complexity due to restarting list traversal from the beginning on each __next__ call. This causes a 60× slowdown compared to converting to a Python list first.

Benchmark Evidence (commit `fcc0376`)

Method	Time (2,000 entities)	Rate
`list(grid.entities)` then iterate	0.23ms	8.5M/sec
`for e in grid.entities` directly	13.6ms	147k/sec

Root Causes

Problem 1: O(n²) List Traversal (Critical)

// UIGrid.cpp:2135-2136
auto l_begin = (*vec).begin();
std::advance(l_begin, self->index-1);  // O(index) for linked list!

Each call to next() starts from begin() and advances index steps. For N entities:

Total pointer hops: 1 + 2 + 3 + ... + N = N(N+1)/2
For 2,000 entities: 2,001,000 pointer chases

Problem 2: Per-Element Python Object Allocation

// UIGrid.cpp:2146-2150
auto type = (PyTypeObject*)PyObject_GetAttrString(McRFPy_API::mcrf_module, "Entity");
auto o = (PyUIEntityObject*)type->tp_alloc(type, 0);

Each iteration performs:

Dictionary lookup to find "Entity" type (~50-100ns)
Heap allocation for PyUIEntityObject (~100-200ns)
Atomic refcount increment for shared_ptr copy (~20ns)

Problem 3: No Persistent Iterator State

The iterator stores only an index, not the actual list iterator position:

// UIGrid.h - current iterator state
Py_ssize_t index;
std::shared_ptr<std::list<std::shared_ptr<UIEntity>>> data;

Proposed Fixes

Fix 1: Store Actual List Iterator (Critical)

// Change iterator state to store actual iterators:
std::list<std::shared_ptr<UIEntity>>::iterator current;
std::list<std::shared_ptr<UIEntity>>::iterator end;

// Then next() becomes O(1):
PyObject* UIEntityCollectionIter::next(PyUIEntityCollectionIterObject* self) {
    if (self->current == self->end) {
        PyErr_SetNone(PyExc_StopIteration);
        return NULL;
    }
    auto target = *self->current;
    ++self->current;  // O(1) increment
    // ... create/return Python object
}

Expected improvement: O(n²) → O(n), ~60× faster

Fix 2: Cache Entity Type Lookup

// Cache at module init or as static:
static PyTypeObject* cached_entity_type = nullptr;
if (!cached_entity_type) {
    cached_entity_type = (PyTypeObject*)PyObject_GetAttrString(...);
}

Expected improvement: ~5-10%

Fix 3: Object Pool for PyUIEntityObject (Optional)

Maintain a freelist for entity wrapper objects to avoid repeated heap allocation.

Expected improvement: ~20-30%

Impact

After Fix 1, EntityCollection iteration should match or approach list() performance (~0.3ms for 2,000 entities instead of 13.6ms).

This directly impacts:

Any Python code iterating over grid.entities
AI systems checking entity states
Game logic processing all entities per frame

#115 SpatialHash Implementation (benefits from fast iteration)
#117 Memory Pool for Entities (related memory optimization)

## Summary The `EntityCollection` iterator (`UIEntityCollectionIter::next`) has O(n²) complexity due to restarting list traversal from the beginning on each `__next__` call. This causes a **60× slowdown** compared to converting to a Python list first. ## Benchmark Evidence (commit fcc0376) | Method | Time (2,000 entities) | Rate | |--------|----------------------|------| | `list(grid.entities)` then iterate | 0.23ms | 8.5M/sec | | `for e in grid.entities` directly | 13.6ms | 147k/sec | ## Root Causes ### Problem 1: O(n²) List Traversal (Critical) ```cpp // UIGrid.cpp:2135-2136 auto l_begin = (*vec).begin(); std::advance(l_begin, self->index-1); // O(index) for linked list! ``` Each call to `next()` starts from `begin()` and advances `index` steps. For N entities: - Total pointer hops: 1 + 2 + 3 + ... + N = N(N+1)/2 - For 2,000 entities: **2,001,000 pointer chases** ### Problem 2: Per-Element Python Object Allocation ```cpp // UIGrid.cpp:2146-2150 auto type = (PyTypeObject*)PyObject_GetAttrString(McRFPy_API::mcrf_module, "Entity"); auto o = (PyUIEntityObject*)type->tp_alloc(type, 0); ``` Each iteration performs: 1. Dictionary lookup to find "Entity" type (~50-100ns) 2. Heap allocation for PyUIEntityObject (~100-200ns) 3. Atomic refcount increment for shared_ptr copy (~20ns) ### Problem 3: No Persistent Iterator State The iterator stores only an index, not the actual list iterator position: ```cpp // UIGrid.h - current iterator state Py_ssize_t index; std::shared_ptr<std::list<std::shared_ptr<UIEntity>>> data; ``` ## Proposed Fixes ### Fix 1: Store Actual List Iterator (Critical) ```cpp // Change iterator state to store actual iterators: std::list<std::shared_ptr<UIEntity>>::iterator current; std::list<std::shared_ptr<UIEntity>>::iterator end; // Then next() becomes O(1): PyObject* UIEntityCollectionIter::next(PyUIEntityCollectionIterObject* self) { if (self->current == self->end) { PyErr_SetNone(PyExc_StopIteration); return NULL; } auto target = *self->current; ++self->current; // O(1) increment // ... create/return Python object } ``` **Expected improvement**: O(n²) → O(n), ~60× faster ### Fix 2: Cache Entity Type Lookup ```cpp // Cache at module init or as static: static PyTypeObject* cached_entity_type = nullptr; if (!cached_entity_type) { cached_entity_type = (PyTypeObject*)PyObject_GetAttrString(...); } ``` **Expected improvement**: ~5-10% ### Fix 3: Object Pool for PyUIEntityObject (Optional) Maintain a freelist for entity wrapper objects to avoid repeated heap allocation. **Expected improvement**: ~20-30% ## Impact After Fix 1, EntityCollection iteration should match or approach `list()` performance (~0.3ms for 2,000 entities instead of 13.6ms). This directly impacts: - Any Python code iterating over `grid.entities` - AI systems checking entity states - Game logic processing all entities per frame ## Related Issues - #115 SpatialHash Implementation (benefits from fast iteration) - #117 Memory Pool for Entities (related memory optimization)