Pathological slowdown in Array#insert

Details

  • Type: Bug Bug
  • Status: Closed Closed
  • Priority: Minor Minor
  • Resolution: Not A Bug
  • Affects Version/s: JRuby 1.1.1
  • Fix Version/s: None
  • Component/s: Performance
  • Labels:
    None
  • Environment:
    ruby 1.8.5 (2007-11-25 rev 4842) [i386-jruby1.1b1], OS X 10.4.11

Description

Like MRI, JRuby's Array#insert method becomes very slow with high numbers of iterations. Below is a snippet, which is also included as part of the bench_array.rb program in ruby_test:

require "benchmark"

MAX = 200000

Benchmark.bm(35) do |x|
   x.report("Array#insert"){
      array = [1,2,3,4]
      MAX.times{ array.insert(2, "a", "b") }
   }
end

Activity

Ascending order - Click to sort in descending order
Hide
Permalink
Marcin Mielzynski added a comment -

Yeah, we need a bit different approach than MRI takes here, there's still room for improvement in Array (especially for this case). But remember, we don't have realloc in java.

Show
Marcin Mielzynski added a comment - Yeah, we need a bit different approach than MRI takes here, there's still room for improvement in Array (especially for this case). But remember, we don't have realloc in java.
Hide
Permalink
Marcin Mielzynski added a comment -

With -XX:+UseParallelGC jruby is 2x faster than 1.9 for 100000.times{ array.insert(2, "a", "b") }.

Show
Marcin Mielzynski added a comment - With -XX:+UseParallelGC jruby is 2x faster than 1.9 for 100000.times{ array.insert(2, "a", "b") }.
Hide
Permalink
Charles Oliver Nutter added a comment -

This is simply an artifact of how arrays are grown. We grow at roughly the same rate as MRI, which means we have to expand and copy every time the array needs to be larger. When this is done thousands of times, we generate a lot of garbage and have to do a lot of copying. Because we don't have realloc, the best we can do is hope that Java's GC and arraycopy will keep up. For the moment, it appears that they do; we're slightly faster than 1.8.

Show
Charles Oliver Nutter added a comment - This is simply an artifact of how arrays are grown. We grow at roughly the same rate as MRI, which means we have to expand and copy every time the array needs to be larger. When this is done thousands of times, we generate a lot of garbage and have to do a lot of copying. Because we don't have realloc, the best we can do is hope that Java's GC and arraycopy will keep up. For the moment, it appears that they do; we're slightly faster than 1.8.

People

  • Assignee:
    Charles Oliver Nutter
    Reporter:
    Daniel Berger
Vote (0)
Watch (3)

Dates

  • Created:
    Updated:
    Resolved: