From 34667957f40e3b2f29cacbb3b699c933b9e5ed67 Mon Sep 17 00:00:00 2001 From: Arthur Chui Date: Mon, 24 Jul 2017 22:36:29 -0700 Subject: Use hash lookup for deleting existing associations from `target` MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit `Array#delete` searches for all occurrences in the `target` array. When performing `dependent: :destroy` in active_record/associations/collection_association, the loop becomes O(N^2). It is particularly slow when destroying large amount of associations (e.g. 10K records). Either `Hash` or `Set` can optimize the loop to O(N). `Hash` is slightly faster in this simple usage. ```ruby class Dummy; end num = 10_000 test1a = num.times.map { Dummy.new }; nil test1b = test1a.dup test2a = num.times.map { Dummy.new }; nil test2b = test2a.dup Benchmark.ips do |x| x.config(stats: :bootstrap, confidence: 95) x.report("hash") do hash = test1a.group_by { |r| r } test1b.select! { |r| !hash[r] } end x.report("array") do test2a.each { |r| test2b.delete(r) } end x.compare! end ``` ``` Calculating ------------------------------------- hash 11.000 i/100ms array 1.000 i/100ms ------------------------------------------------- hash 114.586 (±16.6%) i/s - 561.000 array 1.710k (±10.3%) i/s - 8.377k Comparison: array: 1710.4 i/s hash: 114.6 i/s - 14.93x slower ``` --- activerecord/lib/active_record/associations/collection_association.rb | 3 ++- 1 file changed, 2 insertions(+), 1 deletion(-) (limited to 'activerecord/lib') diff --git a/activerecord/lib/active_record/associations/collection_association.rb b/activerecord/lib/active_record/associations/collection_association.rb index ed2e6d1ae4..65ef9f617a 100644 --- a/activerecord/lib/active_record/associations/collection_association.rb +++ b/activerecord/lib/active_record/associations/collection_association.rb @@ -392,7 +392,8 @@ module ActiveRecord records.each { |record| callback(:before_remove, record) } delete_records(existing_records, method) if existing_records.any? - records.each { |record| target.delete(record) } + hashed_records = records.group_by { |record| record } + target.select! { |record| !hashed_records[record] } records.each { |record| callback(:after_remove, record) } end -- cgit v1.2.3