From 34667957f40e3b2f29cacbb3b699c933b9e5ed67 Mon Sep 17 00:00:00 2001
From: Arthur Chui <arthur.chui@gmail.com>
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(-)
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