Skip to content

getItemsOfCategories is O(items × regexes) per call — category index makes repeated calls faster #248

Description

@rihokirss

Summary

getItemsOfCategories tests every regex against every item's category on every call:

for (let index = 0; index < this._model.categoriesLength(); index++) {
  const currentCategory = this._model.categories(index);
  ...
  for (const categoryRegex of categories) {
    if (categoryRegex.test(currentCategory)) { ... }
  }
}

That is O(items × regexes) per call. Callers tend to invoke it repeatedly (e.g. once per filter/query), so on large models this becomes a fixed ~1 s tax per call.

Measurements (real IFC-derived fragments model, 43 MB, ~1.5M items, 23 categories)

With a lazily built category → localIds Map over the immutable flatbuffer data (keyed by buffer identity so it rebuilds if the buffer is regenerated), regexes are tested once per distinct category name instead of once per item:

Query Current Indexed (first call) Indexed (repeat)
/^IFCPROPERTYSET$/i 770 ms 841 ms 10 ms
/TYPE$/i 755 ms 1 ms 0.9 ms
/^IFCFLOWSEGMENT$/i, /^IFCFLOWTERMINAL$/i 791 ms 0 ms 0.3 ms
/^IFC/i (all 23 categories) 1132 ms 124 ms 123 ms

Results verified byte-identical (including result key order and id order); edit-request handling (created/updated/deleted items) unchanged. Memory cost of the index is roughly one number per item plus the category strings (~10–20 MB on this model).

Design question before a PR

I have a working, tested branch ready (perf/category-index). One open question: the VirtualPropertiesController constructor already iterates all items and stores each item's category in the _items map, so the index could alternatively be built there (or derived from _items) instead of lazily on first use. Happy to open the PR with whichever placement you prefer.

Related to #245 / #246 — same profiling session on real-world models where bulk property queries were the bottleneck.

Activity

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions