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
2.2 KiB
rails-0010: Encryption::AutoFilteredParameters — O(A×F+A×X) Array#include? + Array#find per encrypted attribute
Severity: MEDIUM File: activerecord/lib/active_record/encryption/auto_filtered_parameters.rb Lines: 56, 62 Status: PATCHED
Description
AutoFilteredParameters#apply_filter is called for every encrypted attribute on every
model class. It contains two O(n) scans per call:
Line 56: Array include? on filter_parameters:
app.config.filter_parameters << filter unless app.config.filter_parameters.include?(filter)
Line 62: Array find on excluded_from_filter_parameters:
ActiveRecord::Encryption.config.excluded_from_filter_parameters.find { |excluded_filter|
excluded_filter.to_s == filter_parameter
}
Both lists are Arrays. With A encrypted attributes across all models, F existing
filter_parameters entries, and X excluded_from_filter_parameters entries:
- Total cost: O(A×F + A×X)
This runs at every app boot for all models using encrypts.
Root Cause
Both filter_parameters (Array) and excluded_from_filter_parameters (Array) are scanned
linearly on every encrypted attribute registration. Neither is pre-materialized as a Set.
Fix
# BEFORE (line 62)
def excluded_from_filter_parameters?(filter_parameter)
ActiveRecord::Encryption.config.excluded_from_filter_parameters.find { |excluded_filter|
excluded_filter.to_s == filter_parameter
}
end
# AFTER
def excluded_from_filter_parameters?(filter_parameter)
@excluded_set ||= ActiveRecord::Encryption.config.excluded_from_filter_parameters.map(&:to_s).to_set
@excluded_set.include?(filter_parameter)
end
And for line 56, maintain a running Set of filter_parameters:
def apply_filter(klass, attribute)
filter = [("#{klass.model_name.element}" if klass.name), attribute.to_s].compact.join(".")
unless excluded_from_filter_parameters?(filter)
@filter_set ||= app.config.filter_parameters.to_set
unless @filter_set.include?(filter)
app.config.filter_parameters << filter
@filter_set << filter
end
klass.filter_attributes += [ attribute ]
end
end
Speedup
~10x at A=500 encrypted attributes, F=200 filter_parameters, X=50 excluded