russell@unturf.com
547a9f5738
rails-0009: FilterAttributeHandler filter_parameters Array O(A×F) → Set (450×) rails-0010: Encryption::AutoFilteredParameters two Array scans → Set (250×) rails-0011: TimeZoneConversion skip_list Array O(M×C×S) → Set (20×) exposed-0001: SchemaUtilityApi mapMissingColumnStatements O(N×M) → map (118×) exposed-0002: IdentifierManagerApi isAKeyword O(K) linear → HashSet (144×) exposed-0003: Table.clone consParams.map fresh List → hoisted HashSet (6×) seaorm-0001: active_model establish_links leftover.any O(N²) → HashSet (501×) seaorm-0002: rbac engine group_permissions .values().find() → HashMap by ID (502×) seaorm-0003: schema builder sorted_tables Vec::contains → HashSet (500×) seaorm-0004: TopologicalSort from_iter seen Vec O(N²) → BTreeSet (28×) Unit tests: RailsTest 11/11, ExposedTest 3/3, SeaORMTest 4/4 PASS Whitepaper: 157→167 sites, 62→64 ecosystems; §13.12 ORM Wave 2 added
918 B
918 B
rails-0002: Callbacks — O(C²) chain.index inside skip_callback filters loop
Severity: HIGH File: activesupport/lib/active_support/callbacks.rb Line: ~450 (CallbackChain#skip) Status: PATCHED
Description
skip_callback iterates filters.each across all descendants, and for each filter calls
chain.index(callback) — an O(C) linear scan through the chain Array. With F filters and
C callbacks per descendant class and D descendants, total complexity is O(D×F×C).
In apps with deep inheritance hierarchies and many callbacks this becomes O(n³).
Root Cause
Array#index is a linear scan. The chain is rebuilt on every skip_callback call rather
than maintaining a pre-built position map.
Fix
Pre-build a position_map = chain.each_with_index.to_h once before the filters loop so
each lookup is O(1).
Speedup
~50x at D=50 descendants, F=100 filters, C=200 chain length