Voroztsov Artem wrote:
> I encountered problem with Array#flatten slowness (it can be much
> faster if no argument is given) while solving current QUIZ (see
> ruby-talk mail list).
> 
> Sorry if the issue is already solved in HEAD revision. I have not checked it.
> I just searched though bugs and did not find anything related to
> 'flatten' slowness.
...
> So, 'flatten' time  grows  quadratically while 'flatten2' time -- linearly.

I get similar results for JRuby (JRuby results are repeated to allow for 
JIT time). I've included 1.8.6 and 1.9 numbers as well:

JRuby trunk:
                           user     system      total        real
Input 1 flatten       5.012000   0.000000   5.012000 (  5.011000)
Input 1 flatten2      0.341000   0.000000   0.341000 (  0.341000)
Input 2 flatten       4.896000   0.000000   4.896000 (  4.896000)
Input 2 flatten2      0.034000   0.000000   0.034000 (  0.034000)
Input 1 flatten       4.991000   0.000000   4.991000 (  4.992000)
Input 1 flatten2      0.016000   0.000000   0.016000 (  0.016000)
Input 2 flatten       4.894000   0.000000   4.894000 (  4.893000)
Input 2 flatten2      0.010000   0.000000   0.010000 (  0.010000)
Input 1 flatten       5.087000   0.000000   5.087000 (  5.087000)
Input 1 flatten2      0.018000   0.000000   0.018000 (  0.018000)
Input 2 flatten       5.265000   0.000000   5.265000 (  5.265000)
Input 2 flatten2      0.011000   0.000000   0.011000 (  0.010000)
Input 1 flatten       4.931000   0.000000   4.931000 (  4.931000)
Input 1 flatten2      0.015000   0.000000   0.015000 (  0.015000)
Input 2 flatten       4.905000   0.000000   4.905000 (  4.906000)
Input 2 flatten2      0.011000   0.000000   0.011000 (  0.011000)
Input 1 flatten       4.973000   0.000000   4.973000 (  4.974000)
Input 1 flatten2      0.016000   0.000000   0.016000 (  0.016000)
Input 2 flatten       5.017000   0.000000   5.017000 (  5.017000)
Input 2 flatten2      0.010000   0.000000   0.010000 (  0.010000)

Ruby 1.8.6:
                           user     system      total        real
Input 1 flatten       5.200000   0.020000   5.220000 (  5.227376)
Input 1 flatten2      0.030000   0.000000   0.030000 (  0.030006)
Input 2 flatten       5.140000   0.020000   5.160000 (  5.167915)
Input 2 flatten2      0.030000   0.000000   0.030000 (  0.034440)

Ruby 1.9 trunk:
                           user     system      total        real
Input 1 flatten       4.880000   0.020000   4.900000 (  4.920001)
Input 1 flatten2      0.010000   0.000000   0.010000 (  0.015031)
Input 2 flatten       4.830000   0.020000   4.850000 (  4.872646)
Input 2 flatten2      0.020000   0.000000   0.020000 (  0.015244)

JRuby's Array implementation is largely a port of MRI's, so I'm sure we 
just have the same quadratic implementation. Voroztsov, do you have an 
explanation for why the current implementation is quadratic? Other than 
the ordering issue Ryan pointed out, is there any functional difference?

- Charlie