How to efficiently concatenate multiple arrays in Ruby?

Question

I just wanted to concatenate multiple arrays in Ruby and couldn't find a satisfying way to do so.

Example input:

foo = [1, 2, 3]
bar = [4, 5, 6]
baz = [7, 8, 9]

Expected result: (without modifying the existing arrays)

[1, 2, 3, 4, 5, 6, 7, 8, 9]

My actual arrays are much larger, so I'm interested in an efficient solution. There may also be more than three arrays, so a short syntax is preferred.

What I have tried so far

foo + bar + baz is the obvious one, it's concise and clear. But it is evaluated as (foo + bar) + baz. In other words: it creates an intermediate array [1, 2, 3, 4, 5, 6] that is thrown away after the whole operation. As noted in the documentation:

repeated use of += on arrays can be quite inefficient
[*foo, *bar, *baz] basically inlines the elements which is not very efficient for large arrays, either. It also looks more like a hack to me.
[foo, bar, baz].flatten(1) seems to be even worse than the above, performance wise.
[].concat(foo).concat(bar).concat(baz) is the fastest, but it looks cumbersome and it needs multiple method invocations.

Shouldn't there be a simple class method for such a basic task? Something like:

Array.concat(foo, bar, baz)

Am I missing something obvious?

Have you tried `flatten!` - it doesn't create as many intermediary arrays as `flatten` so should have better performance. — ReggieB, Nov 09 '16 at 15:35
What do you mean by *"basically inlines the elements which is not very efficient for large arrays"*? — ndnenkov, Nov 09 '16 at 15:37
Why `[].concat(foo).concat(bar).concat(baz)` and not `foo.concat(bar).concat(baz)`? — Ursus, Nov 09 '16 at 15:40
@Ursus `(foo + bar).concat(baz)` would work, but it's asymmetric – IMO, the code should not imply that `baz` is any different from `foo` or `bar`. — Stefan, Nov 09 '16 at 15:44
@ndn doesn't `*` convert the array elements to an argument list? It sounds to me like I am creating a (potentially) huge array literal. — Stefan, Nov 09 '16 at 15:46
Try `foo.push(*bar).push(*baz)`. Well, it's asymmetric as well but it could be fast. — Ursus, Nov 09 '16 at 15:50
The pretty way to do it is `[foo, bar, baz].inject(:+)`. But that just runs += on each element. More efficient might be `[foo, bar, baz].inject(:<<).flatten`, but this will morph `foo`. — moveson, Nov 09 '16 at 15:52
@Stefan, we can only speculate what `*` actually does under the hood. It seems like a good candidate to me (supposedly no additional arrays created). We should benchmark it. — ndnenkov, Nov 09 '16 at 15:56
Do you actually need an `Array` or a mere `Enumerable` would suffice? If so, you could build an enumerator that would yield elements of these collections in order as if they were a flat array. Memory consumption would be next to nothing compared to anything building an actual array. — D-side, Nov 09 '16 at 16:03
@D-side those are arrays and I would like to take advantage of that. An enumerator would have to traverse the arrays via `each` which is probably much slower. — Stefan, Nov 09 '16 at 16:06
@Stefan you'd gain a near-instantaneous build time with little additional memory consumption at the cost of slower traversal, yeah. Your call. — D-side, Nov 09 '16 at 16:11
@AlexGolubenko well, it mutates `foo` at least. There already is an answer with this approach. — D-side, Nov 09 '16 at 16:13
@D-side The approach that you can see in the response adds 2 steps as opposed to my. I mean in `foo.concat(bar).concat(baz)` there are only two steps when `Array.new.concat(foo).concat(bar).concat(baz)` - is 4. — Oleksandr Holubenko, Nov 09 '16 at 16:19
@AlexGolubenko ...and mutates `foo`, which is against the expected result. — D-side, Nov 09 '16 at 16:21
@AlexGolubenko, `[foo, bar, baz].inject([],:concat)` does not mutate `foo`. — Cary Swoveland, Nov 09 '16 at 17:54
Stefan, rather than constructing an array `arr`, what about creating a simple method `m(i, *arrays)` which returns the value of (what would be) `arr` at offset `i`. Would that work for your app? — Cary Swoveland, Nov 09 '16 at 18:08
@CarySwoveland yes, I know, I just missed Stefans expected result about `without modifying the existing array`, I was write about `Array.new` so I know that it's didn't mutate foo :) Anyway, thanks for your answer:) — Oleksandr Holubenko, Nov 09 '16 at 18:18
The number of comments suggest the question isn't well defined. "satisfying" means different things to different people. Do you want CPU efficiency? Memory efficiency? Code efficiency? I'd say pick one of the criteria and go with it, or benchmark them a bunch and pick based on the best average time. I agree there should be a class method that is used to concat. We should be free to call it and always know it's the best because it has the criteria built-in to determine what to do. — the Tin Man, Nov 09 '16 at 22:35
@theTinMan you're right, "satisfying" is subjective. But I don't think that there is much of a space–time trade off here. Creating a destination array with the required size and copying the arrays into it is probably both, CPU and memory efficient. — Stefan, Nov 10 '16 at 10:56
@CarySwoveland good idea, but I have to pass the array to another method. In my specific case, I will probably just use `+` and ignore the inefficiency. But in general, I find the lack of a "proper" (i.e. memory-efficient, blazing-fast, low-level) class method quite disappointing. — Stefan, Nov 10 '16 at 11:06

Max · Accepted Answer · 2016-11-09T15:54:10.603

33

If you've already determined that multiple concatenation is the fastest method, you can write it nicer using reduce:

[foo, bar, baz].reduce([], :concat)

edited Nov 09 '16 at 15:54

answered Nov 09 '16 at 15:52

Max

21,123
5
49
71

2

How about `[foo, bar, baz].reduce(&:concat)` – ReggieB Nov 09 '16 at 16:59
4

@ReggieB that would use `foo` as the initial "memo", thus modifying it. – Stefan Nov 09 '16 at 17:09
2

Any objections to `[foo,bar,baz].flat_map(&:itself)`? Seems to be essentially the same performance wise (occasionally faster) – engineersmnky Nov 09 '16 at 20:53
5

@engineersmnky it is effectively the same – `flat_map` calls `concat` if the argument is an array. I find `.reduce([], :concat)` easier to understand than `.flat_map(&:itself)`. – Stefan Nov 10 '16 at 13:10
@engineersmnky it is effectively the same – `flat_map` calls `concat` if the argument is an array. I find `.flat_map(&:itself)` easier to understand than `.reduce([], :concat)`. – Cary Swoveland Feb 19 '20 at 18:24
@engineersmnky it is effectively the same – `flat_map` calls `concat` if the argument is an array. I find `.flat_map(&:itself)` easier to understand than `.reduce([], :concat]`. – Dave Newton May 08 '23 at 15:39
1

@engineersmnky I dunno; just seems like that's what we're supposed to do here :D This is the weirdest thing. – Dave Newton May 08 '23 at 15:40

Stefan · Answer 2 · 2016-11-10T13:18:42.547

I've created another benchmark, comparing +, concat and a custom C extension with a variable number of arrays.

Result

the C extension was always fastest and roughly 2-3x faster than concat
plus is getting really slow if you concatenate many arrays

Conclusion

Although "2-3x" sounds like a huge improvement, it's just a few milliseconds in absolute terms. I was expecting a bigger difference by not having to resize the array, but this is apparently not a huge factor.

IMO, concat is a decent performer and I see no urgent need for a C extension.

My test arrays contain nil values. Other elements don't seem to produce different results (in relative terms).

I didn't include flat_map, because it is equivalent to concat.

Concatenating 3 arrays of size 100 (10000 times)
                 user     system      total        real
plus         0.020000   0.000000   0.020000 (  0.027927)
concat       0.020000   0.010000   0.030000 (  0.033204)
c_extension  0.010000   0.010000   0.020000 (  0.010727)

Concatenating 10 arrays of size 100 (10000 times)
                 user     system      total        real
plus         0.110000   0.070000   0.180000 (  0.180417)
concat       0.050000   0.020000   0.070000 (  0.065299)
c_extension  0.010000   0.010000   0.020000 (  0.025475)

Concatenating 10 arrays of size 1000 (10000 times)
                 user     system      total        real
plus         0.690000   0.560000   1.250000 (  1.252319)
concat       0.180000   0.130000   0.310000 (  0.303365)
c_extension  0.120000   0.120000   0.240000 (  0.248589)

plus is excluded from the following results

Concatenating 10 arrays of size 100000 (100 times)
                 user     system      total        real
concat       0.220000   0.340000   0.560000 (  0.568730)
c_extension  0.130000   0.150000   0.280000 (  0.281354)

Concatenating 100 arrays of size 10000 (100 times)
                 user     system      total        real
concat       0.210000   0.320000   0.530000 (  0.519030)
c_extension  0.160000   0.140000   0.300000 (  0.304751)

Concatenating 1000 arrays of size 1000 (100 times)
                 user     system      total        real
concat       0.240000   0.330000   0.570000 (  0.563511)
c_extension  0.150000   0.120000   0.270000 (  0.283546)

Concatenating 10000 arrays of size 100 (100 times)
                 user     system      total        real
concat       0.330000   0.310000   0.640000 (  0.643987)
c_extension  0.170000   0.120000   0.290000 (  0.286489)

Concatenating 100000 arrays of size 10 (100 times)
                 user     system      total        real
concat       1.300000   0.340000   1.640000 (  1.648687)
c_extension  0.310000   0.150000   0.460000 (  0.458214)

Test code:

require 'benchmark'

values = [
  # small
  { count: 3,      size: 100,    n: 10000 },
  { count: 10,     size: 100,    n: 10000 },
  { count: 10,     size: 1000,   n: 10000 },
  # large
  { count: 10,      size: 100000, n: 100 },
  { count: 100,     size: 10000,  n: 100 },
  { count: 1000,    size: 1000,   n: 100 },
  { count: 10000,   size: 100,    n: 100 },
  { count: 100000,  size: 10,     n: 100 }
]

values.each_with_index do |h, i|
  count, size, n = h.values_at(:count, :size, :n)
  arrays = Array.new(count) { Array.new(size) }

  puts
  puts "Concatenating #{count} arrays of size #{size} (#{n} times)"
  Benchmark.bm(10) do |r|
    r.report('plus')        { n.times { arrays.reduce(:+) } } if i < 3
    r.report('concat')      { n.times { arrays.reduce([], :concat) } }
    r.report('c_extension') { n.times { Array.concat(*arrays) } }
  end
end

C extension: (a patch actually, I've added this to Ruby's array.c)

VALUE
rb_ary_s_concat(int argc, VALUE *argv, VALUE klass)
{
  VALUE ary;
  long len = 0, i;
  for (i=0; i<argc; i++) {
    argv[i] = to_ary(argv[i]);
    len += RARRAY_LEN(argv[i]);
  }
  ary = rb_ary_new2(len);
  long beg = 0;
  for (i=0; i<argc; i++) {
    ary_memcpy(ary, beg, RARRAY_LEN(argv[i]), RARRAY_CONST_PTR(argv[i]));
    beg += RARRAY_LEN(argv[i]);
  }
  ARY_SET_LEN(ary, len);
  return ary;
}

You have to register this method in Init_Array via:

rb_define_singleton_method(rb_cArray, "concat", rb_ary_s_concat, -1);

Thnx for the patch, I suppose you need to recompile everything after that ? I'm on windows with the Ruby installer so I'll have to pass I guess — peter, Nov 10 '16 at 13:28
@peter yes, you have to recompile Ruby to get it working. I couldn't find a way to write a simple extension because the implementation relies on functions and macros that are only available in `array.c` — Stefan, Nov 10 '16 at 13:31
posted my question about MRI<>jRuby here http://stackoverflow.com/questions/40529208/performance-difference-between-mri-ruby-and-jruby — peter, Nov 10 '16 at 13:56
I re-ran this without the C extension, using counts of 3, 10 and 20, over arrays of size 5, 10 and 20, using the Mac system ruby (2.3.7) and v2.7.0. What I found was concat is almost always faster on v2.3.7 and plus could get quite slow as the numbers get bigger, but the speed of plus got much better for 2.7, it was about equal between plus and concat until the arrays get above 10 in number - regardless of the size of the array - that's when plus starts to break down. — ian, Feb 28 '21 at 14:50

peter · Answer 3 · 2016-11-10T12:42:31.457

Did some benchmarks and simple + is the most efficient. So i would suggest to neglect the intermediate creation of an array.

You could add a new method concat_all to Array like this, but you would have to take into account mixed and multi-dimensional arrays also.

class Array
  def concat_all 
    self.reduce([], :+)
  end
end
[a, b, c].concat_all # a huge array
[a, b, c].concat_all.length #300000

Here my benchmarks

require 'Benchmark'
N = 1000

class Array
  def concat_all 
    self.reduce([], :+)
  end
  def concat_all2
    # just a quick test with fixed numbers for the fill method Stephan proposes but in Ruby itself
    d = Array.new(300_000)
    d[0..99999] = self[0]
    d[100_000..199999] = self[1]
    d[200_000..299999] = self[2]
    d
  end
  def concat_all3
    self.flatten
  end
end

# small arrays
a = (1..10).to_a
b = (11..20).to_a
c = (21..30).to_a

Benchmark.bm do |r|
  r.report('plus       ')  { N.times { a + b + c }}
  r.report('concat     ') { N.times { [].concat(a).concat(b).concat(c) }}
  r.report('push       ') { N.times { [].push(*a).push(*b).push(*c) }}
  r.report('<<         ') { N.times { ([] << a << b << c).flatten}}
  r.report('splash     ') { N.times {[*a, *b, *c]} }
  r.report('concat_all ')  { N.times { [a, b, c].concat_all }}
  r.report('concat_all3')  { N.times { [a, b, c].concat_all3 }}
  r.report('flat_map   ') { N.times {[a, b, c].flat_map(&:itself)} }
end

#large arrays
a = (1..100_000).to_a
b = (100_001..200_000).to_a
c = (200_001..300_000).to_a

Benchmark.bm do |r|
  r.report('plus       ')  { N.times { a + b + c }}
  r.report('concat     ') { N.times { [].concat(a).concat(b).concat(c) }}
  r.report('push       ') { N.times { [].push(*a).push(*b).push(*c) }}
  r.report('<<         ') { N.times { ([] << a << b << c).flatten}}
  r.report('splash     ') { N.times {[*a, *b, *c]} }
  r.report('concat_all ')  { N.times { [a, b, c].concat_all }}
  r.report('concat_all2')  { N.times { [a, b, c].concat_all2 }}
  r.report('concat_all3')  { N.times { [a, b, c].concat_all3 }}
  r.report('flat_map   ') { N.times {[a, b, c].flat_map(&:itself)} }
end

And here the results

# results for small arrays
       user     system      total        real
plus         0.000000   0.000000   0.000000 (  0.000416)
concat       0.000000   0.000000   0.000000 (  0.000592)
push         0.000000   0.000000   0.000000 (  0.000441)
<<           0.000000   0.000000   0.000000 (  0.003387)
splash       0.000000   0.000000   0.000000 (  0.000789)
concat_all   0.000000   0.000000   0.000000 (  0.001480)
concat_all3  0.016000   0.000000   0.016000 (  0.003496)
flat_map     0.000000   0.000000   0.000000 (  0.001036)

# results for big arrays
       user     system      total        real
plus         0.686000   0.671000   1.357000 (  1.351171)
concat       0.890000   0.733000   1.623000 (  1.630155)
push         1.466000   0.624000   2.090000 (  2.092684)
<<          23.837000   1.045000  24.882000 ( 24.885238)
splash       1.029000   1.264000   2.293000 (  2.332560)
concat_all   0.687000   0.967000   1.654000 (  1.709321)
concat_all2  0.936000   0.780000   1.716000 (  1.730428)
concat_all3 24.242000   0.998000  25.240000 ( 25.278264)
flat_map     0.780000   0.765000   1.545000 (  1.551654)

The `Array.concat` class method I was thinking of would create a destination array with the correct size and then copy each array to the appropriate location within the destination array. This can probably only be achieved in C. — Stefan, Nov 09 '16 at 17:48
Just tried it – a C implementation would be twice as fast as `plus`. Maybe I should file a feature request ... — Stefan, Nov 09 '16 at 17:56
@Stefan interesting, could you do it with FFI ? see http://stackoverflow.com/questions/29389334/how-do-i-handle-ruby-arrays-in-ruby-ffi-gem I tried this fill existing array method approach in Ruby itself but it is slower. For small arrays push is fastest, then concat, then + but speed is only going to matter with large arrays and/or large number of arrays. You could do a check in concat_all for the array size first and then choose the method to use. You would also need a way to handle mixed and multi-dimensiona arrays. — peter, Nov 09 '16 at 20:54
peter, could you add `[a,b,c].flat_map(&:itself)` to your benchmark? — Cary Swoveland, Nov 09 '16 at 20:55
@CarySwoveland this seems to be more performant on a regular basis I posted it as a comment on the above (great minds and all that) but in that case the reduction posted in the other answer should also be added — engineersmnky, Nov 09 '16 at 21:03
Stefan, my C is a bit rusty, but I assume you used memcpy(). Correct? — Cary Swoveland, Nov 09 '16 at 21:07
added some other methods including the flat_map for cary and with both small and big arrays, seems that all methods that use flatten are a lot slower — peter, Nov 09 '16 at 21:11
"large" is not definitive try this with a million per array and see the performance difference there. The only 2 that seem to compete in this space are flat_map and reduce. I'm not asking for benchmarks just give it a shot :) — engineersmnky, Nov 10 '16 at 00:19
@engineersmnky I tried it until the push method had stack level too deep at 30 milion and even with this size the + methos was fastest by far, indeed followed by flat_map but it is clear that one must do his own benchmarks with real data and hardware before making a decision — peter, Nov 10 '16 at 12:50
@engineersmnky tried it with jruby and with the 30M and concat is the winner here, on plead more to do your own benchmarks in your situation But the results are surprising in another way: MRI outclasses Jruby by far.. I think I'm gonna ask a question about that — peter, Nov 10 '16 at 13:07
@CarySwoveland I've posted an "answer" including my C code and another benchmark. — Stefan, Nov 10 '16 at 13:15

How to efficiently concatenate multiple arrays in Ruby?

What I have tried so far

3 Answers3

Result

Conclusion

Linked