From: "jablin (Johannes Abt)" <noreply@...>
Date: 2022-04-13T08:42:44+00:00
Subject: [ruby-core:108218] [Ruby master Bug#18692] Set += is O(n^2)

Issue #18692 has been reported by jablin (Johannes Abt).

----------------------------------------
Bug #18692: Set += is O(n^2)
https://bugs.ruby-lang.org/issues/18692

* Author: jablin (Johannes Abt)
* Status: Open
* Priority: Normal
* ruby -v: ruby 2.6.5p114 (2019-10-01 revision 67812) [x86_64-linux]
* Backport: 2.6: UNKNOWN, 2.7: UNKNOWN, 3.0: UNKNOWN, 3.1: UNKNOWN
----------------------------------------
`$ time ruby26 --disable=gems -r set -e 's = Set.new(); 1.upto(10_000).each { |n| s += [n] }'
real    0m1.346s
user    0m1.290s
sys     0m0.055s
`

Tree times the input size:

`$ time ruby26 --disable=gems -r set -e 's = Set.new(); 1.upto(30_000).each { |n| s += [n] }'

real    0m13.099s
user    0m12.443s
sys     0m0.642s
`

Tree times the input size is 9 to 10 times the runtime!


For comparsion, using the `<<` operator instead of `+=`:


`$ time ruby26 --disable=gems -r set -e 's = Set.new(); 1.upto(5_000_000).each { |n| s << n }'

real    0m1.472s
user    0m1.290s
sys     0m0.180s
`




-- 
https://bugs.ruby-lang.org/

Unsubscribe: <mailto:ruby-core-request@ruby-lang.org?subject=unsubscribe>
<http://lists.ruby-lang.org/cgi-bin/mailman/options/ruby-core>