Perf: full-model traversal (IFC105/IFC106) visited-set is O(n^2); plus gaps and a bug in IVS-879

[jmecosta]

Summary

While profiling the engine in-process (in-memory parser) on a 54 MB IFC model against IFC106 (Resource entities should be referenced by rooted entity — identical logic to IFC105), the rule took ~128 s, almost entirely in two framework-level issues that affect every rule. I see IVS-879_Improve_Performance_of_ifc-gherkin-rules already targets part of this, so this issue is to (a) share the profiling data, (b) flag two gaps and one bug in that branch, and (c) point out the biggest win it doesn't yet touch. Happy to send PRs for any/all of these.

Profile (cProfile, sorted by self time)

Step-level timing for IFC106 on the 54 MB model, before vs. after the fixes below:

Step	Before	After
Given a traversal over the full model …	57.4 s	17.9 s
Given an entity instance	5.7 s	5.6 s
Given [its entity type] is not 'IfcRoot' …	42.1 s	19.6 s
Then it must be referenced by … IfcRoot …	13.9 s	9.4 s
rule total	128.1 s	59.7 s (2.1×)

Top self-time before: numpy._unique_hash 24.0 s, then ~12 s across inspect._signature_from_function / inspect.getargs / compile. Both vanish after the changes; outputs are byte-identical (24,863 outcomes).

---

1. model_traversal.py — visited set is O(n²) (not addressed by IVS-879)

features/steps/steps/model_traversal.py#L80 uses misc.ContiguousSet as the visited set for the full-model traversal. ContiguousSet.commit() runs np.union1d(self._arr, pend_arr) over the entire growing array on every batch (misc.py#L303) — effectively O(n²/batch). On this model that's the 24 s of numpy._unique_hash and the dominant cost of the 57 s traversal step.

The traversal only needs membership (inst.id() not in context.visited_instances), so a plain set[int] is O(1) per op. Swapping it took the traversal step 57 s → 18 s, identical results:

    visited = set()

    def visit(inst):
        inst_id = inst.id()
        if inst_id in visited:
            return
        visited.add(inst_id)
        ...
    for inst in context.model.by_type(entity_name):
        visit(inst)
    context.visited_instances = visited   # drop visited.commit()

(Also lets you drop the now-unused path accumulation in visit.) If ContiguousSet is kept elsewhere for the rocksdb/lazy path, this single call site can still use a plain set — it's membership-only.

2. IVS-879 signature cache misses the inspect.getargs sites

The branch adds _SIGNATURE_CACHE / get_cached_signature(fn) for the apply_operation site (#L170) — nice. But three other per-call introspection sites remain uncached and run per-instance:

• validation_handling.py#L133 — 'inst' not in inspect.getargs(fn.__code__).args
• #L247 / #L249 — 'path' / 'npath' in inspect.getargs(fn.__code__).args

These together were ~half of the ~12 s introspection cost. A small memoized helper covers all sites (signature + getargs), keyed on fn / fn.__code__:

@functools.lru_cache(maxsize=None)
def _fn_accepts_param(fn, name):
    try: return name in inspect.signature(fn).parameters
    except (TypeError, ValueError): return False

@functools.lru_cache(maxsize=None)
def _code_accepts_arg(code, name):
    try: return name in inspect.getargs(code).args
    except (TypeError, ValueError): return False

3. Bug in IVS-879's ContiguousSet.commit()

The branch's rewrite of commit() assigns the result of numpy.ndarray.sort(), which sorts in place and returns None:

# IVS-879 version
self._arr = pend_arr.sort()                                  # -> None
...
self._arr = np.unique(np.concatenate((self._arr, pend_arr))).sort()  # -> None

After the first commit self._arr is None, which will break subsequent _in_array / __contains__. np.unique(...) already returns sorted, so:

if self._arr.size == 0:
    self._arr = np.sort(pend_arr)            # or np.unique(pend_arr)
else:
    self._arr = np.unique(np.concatenate((self._arr, pend_arr)))

(Note: even fixed, commit() per batch is still O(n log n) over the whole array; for the membership-only visited use in #1, a plain set avoids this entirely.)

---

Repro / notes

• Profiled with the in-memory parser; absolute numbers differ under rocksdb, but the algorithmic issues are mode-independent.
• I have clean patches for Create ci.yml #1 and say hello ...  #2 (and the Feature: IfcSweptDiskSolidPolygonal Informal Proposition #3 fix) ready to send as PRs — just let me know whether you'd prefer them against main or folded into IVS-879.

[jmecosta]

this was generated by claude, by i did validate the outcome. really speeds up the all analysis

[jmecosta]

0001-cache-step-introspection.patch
0002-visited-set-perf.patch

[jmecosta]

0003-cache-attribute-matrix.patch

Third finding (same theme): OJP001 re-globs resources/** + re-parses CSVs per instance

Profiling a ~700 MB model, OJP001 was the slowest rule by ~2× (~1374 s vs the next ~560 s). Root cause is the same "constant work done per instance" pattern as above.

The second Then of OJP001 — thens/attributes.py#L10, "The {entity} attribute must point to the {other_entity} of the container element established with {relationship} relationship" — calls system.load_attribute_matrix(...) twice on every invocation:

def step_impl(context, inst, entity, other_entity, relationship):
    related_attr_matrix, relating_attr_matrix = system.load_attribute_matrix(
        "related_entity_attributes.csv"), system.load_attribute_matrix("relating_entity_attributes.csv")

and load_attribute_matrix (utils/system.py#L24) does a recursive glob('resources/**', recursive=True) + CSV open/parse, uncached:

def get_abs_path(rel_path):
    ...
    return glob.glob(os.path.join(parent_path, rel_path), recursive=True)[0]   # full FS walk

def load_attribute_matrix(table, base_folder="resources/**/"):
    return get_csv(get_abs_path(f"{base_folder}{table}"), return_type='dict')[0]  # open + parse

Since OJP001's activation set is every IfcElement (narrowed to aggregated children), that's two filesystem tree-walks + two CSV parses per aggregated element. givens/relationships.py already loads its matrices once at module level, so only this Then pays the per-instance cost.

Measured: one uncached glob+parse ≈ 1.55 ms; cached ≈ 0.045 µs. On a 78 MB model OJP001's PlacementRelTo Then processed ~8k elements ⇒ ~25 s of pure glob+CSV there; it dropped to 53 ms after caching, and load_attribute_matrix/get_abs_path/get_csv/glob no longer appear in the profile. On the 700 MB model this was a large part of OJP001's runtime.

Fix — memoize the loader (CSVs are static and read-only at the call sites)

import functools

@functools.lru_cache(maxsize=None)
def get_abs_path(rel_path): ...

@functools.lru_cache(maxsize=None)
def load_attribute_matrix(table, base_folder="resources/**/"):
    return get_csv(get_abs_path(f"{base_folder}{table}"), return_type='dict')[0]

(Optionally also hoist the two loads in attributes.py to module level like relationships.py — belt-and-braces; the cache alone fixes every caller.) No behaviour change (identical outcomes). Happy to roll this into the same PR/branch as the other fixes here.

[aothms]

Thanks. The contiguous array is there for a reason. In large models that care be many instances active at the same time across the layers of stack values created after every gherkin step execution. These objects are large (SWIG C++ backed instances). So they are compressed into a sorted array to minimize the object size even an integer would have in as a gc'ed, typed individual python object.

The union1d on commit is indeed problematic. I think the most plausible way forward is to pick an existing library such as https://pypi.org/project/roaringbitmap/

Re the other parts of the non-main branch, likely valid, will need to take a more in-depth look, but this is no longer necessary if we stop rolling our own and use for ex. the existing lib referenced above.

OJP001 re-globs resources/** + re-parses CSVs per instance

These are indeed things I have also addressed in the past. Apparently missed some.

In short: Pull requests welcome. Performance is of interest of us, but the most important is to eliminate memory usage spikes so that we can have concurrent runs without swapping.

[jmecosta]

Yes memory is quite problematic. I have done some Harness around it to spin process execution per rule. Have achieved quite good gains if we know ahead what are the most expensive rules. But memory is at the moment the bottleneck to run things in parallel. I can probably profile it abit next week - if have the list of the most heavy rules

[jmecosta]

Thanks @aothms — sent the two clean ones against main:

• perf: memoize per-step signature/arg introspection #528 — memoize the per-step inspect.signature / inspect.getargs (the ~12 s introspection cost; independent of the stack-value structure).
• perf: cache attribute-matrix loader (OJP001 per-instance glob+CSV) #529 — cache load_attribute_matrix (the OJP001 per-instance glob('resources/**') + CSV parse).

Both are no-behaviour-change (byte-identical outcomes).

On the visited-set: makes sense, I'll hold that one. Agreed that swapping the hand-rolled ContiguousSet for an existing compressed-int-set lib (e.g. roaringbitmap) is the better direction than reverting to a plain set() — it keeps the memory win while removing the union1d-on-commit cost. Happy to help test/benchmark against the large models once you have picked the approach.