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
1 KiB
1 KiB
rails-0003: Enumerable#excluding — O(N×E) elements Array#include? in reject loop
Severity: MEDIUM File: activesupport/lib/active_support/core_ext/enumerable.rb Line: ~35 (excluding method) Status: PATCHED
Description
Enumerable#excluding is implemented as:
reject { |element| elements.include?(element) }
where elements is an Array. The outer reject iterates N receiver elements; for each,
Array#include? scans the full E-element exclusion list — O(N×E) total.
This method is used in AR query builders, relation scoping, and test helpers, so the O(N×E) cost is paid frequently with real model collections.
Root Cause
elements is passed as a splat Array and used directly with Array#include? rather than
being materialized as a Set before the iteration begins.
Fix
# BEFORE
reject { |element| elements.include?(element) }
# AFTER
exclusion_set = elements.to_set
reject { |element| exclusion_set.include?(element) }
Speedup
~10x at N=5000 receiver, E=500 exclusions