LearnNewsExamplesServices
Frontmatter
id9076
titleperf: Implement O(1) Lookup Map for internalId
stateClosed
labels
aiperformancecore
assigneestobiu
createdAtFeb 9, 2026, 2:46 PM
updatedAtFeb 10, 2026, 2:09 AM
githubUrlhttps://github.com/neomjs/neo/issues/9076
authortobiu
commentsCount2
parentIssuenull
subIssues[]
subIssuesCompleted0
subIssuesTotal0
blockedBy[]
blocking[]
closedAtFeb 10, 2026, 2:09 AM

perf: Implement O(1) Lookup Map for internalId

Closed v12.0.0 aiperformancecore
tobiu
tobiu commented on Feb 9, 2026, 2:46 PM

Context: The recent adoption of internalId (#9070) introduced robust identity for Records and Raw Objects. However, resolving an item from its internalId currently relies on store.items.find(...), which is an O(N) operation. In large datasets (e.g. 100k rows), this kills performance for selection, navigation, and drag-and-drop operations that rely on reverse lookup.

Objective: Implement a secondary map (internalIdMap) in Neo.collection.Base to provide O(1) lookup for internalId (or any secondary key).

Architecture:

  1. Collection.Base:

    • Add trackInternalId config (or similar flag).
    • Add internalIdMap (Map).
    • Add getInternalKey(item) method (to be overridden).
    • Update splice (add/remove logic) to maintain internalIdMap in sync with the primary map.
    • Add getByInternalId(id) accessor.
  2. Store:

    • Enable tracking.
    • Override getInternalKey to return item[internalId].
  3. Refactor Consumers:

    • Update GridBody, TableBody, Helix, Gallery, SelectionModels to use store.getByInternalId(id) instead of store.items.find(...).

Result: Restores O(1) performance for all ID-based lookups in the framework.

tobiu added the ai label on Feb 9, 2026, 2:46 PM
tobiu added the performance label on Feb 9, 2026, 2:46 PM
tobiu added the core label on Feb 9, 2026, 2:46 PM
tobiu assigned to @tobiu on Feb 9, 2026, 2:46 PM
tobiu
tobiu Feb 9, 2026, 3:20 PM

Input from Gemini 3 Pro:

Architecture & Implementation Plan (Handoff)

Objective: Restore O(1) performance for internalId lookups. Currently, the framework relies on store.items.find(...) in critical paths (selection, navigation), which is O(N) and creates performance bottlenecks for large datasets.

Architectural Decision: We will implement Option A: Direct Reference Map. internalIdMap will map internalId -> Item Reference (either a Record instance or a Raw Data Object).

Implementation Plan:

  1. Enhance Neo.collection.Base:

    • Add trackInternalId: false (config).
    • Add internalIdMap: null (property, initialized if tracking is enabled).
    • Add getInternalKey(item) method (hook, default returns null).
    • Update splice and afterSetItems logic to:
      • Get the internal key via getInternalKey(item).
      • If valid, add to internalIdMap.
      • On remove, delete from internalIdMap.
    • Add getByInternalId(id) accessor method.
  2. Update Neo.data.Store:

    • Set trackInternalId: true by default.
    • Override getInternalKey(item) to return item[internalId] (using the symbol).
    • Turbo Mode Sync: In get(key) and getAt(index), when a Raw Object is hydrated into a Record:
      • Explicitly update internalIdMap to point to the new Record instance instead of the old Raw Object.
      • This ensures getByInternalId returns the correct reference used by the View.
  3. Refactor Consumers (Cleanup Phase):

    • Update Helix, Gallery, ComboBox, GridBody, TableBody, and SelectionModels.
    • Replace all instances of store.items.find(r => ... === id) with store.getByInternalId(id).
    • This will dramatically simplify the record resolution logic and restore performance.

Note: The internalId symbol is exported from src/core/ConfigSymbols.mjs. Use it to access the property safely.

tobiu referenced in commit 9531fcd - "perf: Implement O(1) Lookup Map for internalId (#9076)" on Feb 9, 2026, 4:31 PM
tobiu
tobiu Feb 9, 2026, 4:32 PM

Input from Gemini 3 Pro:

✦ I have implemented the O(1) internalIdMap lookup.

Summary of Changes:

  1. Core Framework (Neo.collection.Base & Neo.data.Store):

    • Implemented internalIdMap (Map) in Collection to track items by internalId.
    • Added trackInternalId config (defaults to false in Collection, true in Store).
    • Updated splice, filter, clear, and destroy to maintain the map.
    • Enhanced get(key) to automatically check internalIdMap if the key is not found in the primary map.
    • Updated Store to populate internalIdMap with Record instances upon hydration.
  2. Consumer Refactoring:

    • Refactored GridBody, TableBody, List, Gallery, Helix, and DragZone to use the optimized store.get() method.
    • Removed all O(N) fallback iterations (e.g., store.items.find(...)) in Selection Models and Components.
  3. Verification:

    • Created a new unit test: test/playwright/unit/collection/InternalId.spec.mjs.
    • Verified trackInternalId toggling, map population, record resolution, and cleanup on filter/splice/destroy.
    • All 8 tests passed.

The system now has O(1) performance for both Primary Key and Internal ID lookups.

tobiu closed this issue on Feb 10, 2026, 2:09 AM