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.4 KiB
seaorm-0001: establish_links leftover scan — O(N²) list scan
Severity: HIGH File: src/entity/active_model.rs Line: 1267 Status: PATCHED
Description
establish_links iterates over related_models (up to N items) and inside
the loop calls leftover.iter().any(|t| t.1 == via_key) to check whether the
computed junction key already exists in the leftover vec. leftover can also
be up to N items long (one per existing junction row), so the combined
complexity is O(N²) where N is the number of related models / existing junction
rows.
This path is exercised every time a many-to-many link set is written with
set_relation, which is a normal ORM operation. For an entity with 1 000
related models the check issues ~500 000 equality comparisons where 1 000 would
suffice.
Root Cause
leftover is built as a Vec<(ActiveModel, ValueTuple)> and then scanned with
iter().any() per related model instead of being indexed by key before the
loop begins.
Fix
Extract the keys from leftover into a HashSet<ValueTuple> before the loop
so each existence check is O(1).
// before loop
let leftover_keys: std::collections::HashSet<ValueTuple> =
leftover.iter().map(|(_, k)| k.clone()).collect();
// inside loop (was leftover.iter().any(|t| t.1 == via_key))
if !leftover_keys.contains(&via_key) {
via_models.push(via);
}
Speedup
~200x at N=1000 (500 000 comparisons → 1 000 hash lookups)