Bug #17483: Array#insert is pathologically slow

• Status: Rejected
• Assignee: -
• Target version: -
• ruby -v: ruby 2.6.6p146 (2020-03-31 revision 67876) [x86_64-darwin19]
• Backport: 2.5: UNKNOWN, 2.6: UNKNOWN, 2.7: UNKNOWN

[djberg96 (Daniel Berger)]

I ran some generic Array method benchmarks:

https://github.com/djberg96/berger_spec/blob/ruby23/bench/core/bench_array.rb (comment out nitems first)

https://github.com/djberg96/berger_spec/blob/ruby23/bench/core/Array/bench_insert.rb

What I noticed is that all of these complete in a fraction of a second, except Array#insert, which takes about 6-8 seconds on my Mac desktop.

Is this unavoidable?

[mame (Yusuke Endoh)]

• Status changed from Open to Rejected

In short, it is unavoidable.

Currently, an array is internally represented as consecutive memory area. Adding new elements into the middle of an array requires reallocation of the array, which takes O(n). Therefore, calling Array#insert n times takes O(n^2 ). Theoretically, by replacing the internal data structure with a tree or somthing, the order can be improved to O(n log n), but it will make other (more commonly used) operations slow.