Skip to content

perf: remove quadratic explicit-category overflow ordering in JS and Python #161

Closed

Description

@spboyer

Parent

#160

Validated finding

At a794557384adcc3293a77043f6b9aff1c33d152c, JS packages/flint-js/src/core/filter-overflow.ts:266 filters the explicit order with uniqueValues.includes(value). Python packages/flint-py/flint/core/filter_overflow.py:193 performs the corresponding repeated list membership check. Matching K ordered values against K categories therefore performs quadratic work before retaining even a small viewport.

Revalidated 2026-11-11 using the real exported filterOverflow / filter_overflow, one distinct string category per row, an explicit JSON ordering containing every category, and an x budget of 25. Python three-run baseline times: 1,000 categories = 4.34/4.29/4.14 ms; 10,000 = 412.99/402.87/399.27 ms. JS exploratory 10,000-category medians varied from 113 to 165 ms; the same fixture without explicit ordering was approximately 1.8 ms. Different sort modes are scaling diagnostics, not an A/B optimization result.

Environment: shared Linux host, two visible CPUs, Node v26.12.1, Python 3.12.3. Upstream issue listings and all 21 open PR titles were checked on 2026-11-11; no equivalent work was found.

Proposed scope

Replace repeated membership scans with invocation-local indexed membership where equality semantics are preserved. Avoid persistent caches. Keep the change limited to explicit-category overflow ordering in JS and Python.

Acceptance criteria

  • Preserve exact category order, duplicate explicit-order entries, descending behavior, missing categories, primitive equality behavior, retained rows, warnings, and viewport metadata.
  • Include mixed primitive and empty/missing-category cases; account for Python's existing equality semantics instead of assuming JS parity.
  • Provide at least three interleaved baseline/change rounds at 1k/5k/10k categories with timing and allocation or peak-memory evidence. Compare identical fixtures and outputs.
  • Add focused tests in the existing overflow test files and run related suites.
  • Keep public APIs and observable behavior unchanged; open one focused PR and do not merge it.

Activity

  1. Chenglong-MS commented on Nov 15, 2026

    @Chenglong-MS
    Contributor

    Fixed by #167 (merged into dev): explicit-order membership is a set lookup in JS and Python. Ships in 1.0.2.

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