[ruby-core:95037] [Ruby master Feature#16119] Optimize Array#flatten and flatten! for already flattened arrays

[lourens@bearmetal.eu]

Issue #16119 has been updated by methodmissing (Lourens Naudé).

File 0001-Let-empty-arrays-being-flattened-not-alloc-additiona.patch added

nobu (Nobuyoshi Nakada) wrote:
> This patch unrolls the `while`-loop for the already flatten head and seems reasonable.
> But I could get only insignificant result, and a worse result for an unflattened array.
> 
> ```yaml
> # array_flatten.yml
> prelude: |
>   ary = (0...100).to_a.push([101, 102])
>   ary2 = 10.times.map {|i| (i..(i+9)).to_a}
> 
> benchmark:
>   flatten!: ary.flatten!
>   flatten: ary.flatten
>   flatten2: ary2.flatten
> loop_count: 1000000
> ```
> ```
>             benchmark/array_flatten.yml 
> Calculating -------------------------------------
>                      compare-ruby  built-ruby 
>             flatten!     220.944k    223.612k i/s -      1.000M times in 4.526028s 4.472037s
>              flatten     216.457k    210.651k i/s -      1.000M times in 4.619859s 4.747182s
>             flatten2     182.447k    166.501k i/s -      1.000M times in 5.481056s 6.005954s
> 
> Comparison:
>                          flatten!
>           built-ruby:    223611.7 i/s 
>         compare-ruby:    220944.3 i/s - 1.01x  slower
> 
>                           flatten
>         compare-ruby:    216456.8 i/s 
>           built-ruby:    210651.3 i/s - 1.03x  slower
> 
>                          flatten2
>         compare-ruby:    182446.6 i/s 
>           built-ruby:    166501.4 i/s - 1.10x  slower
> ```

Attached is a patch for early return and preventing additional allocs for the empty array case (however not very sure how often that happens in practice):

```
prelude: |
  ary = []

benchmark:
  flatten!: ary.flatten!
  flatten: ary.flatten
loop_count: 1000000
```

```
lourens@CarbonX1:~/src/ruby/ruby$ /usr/local/bin/ruby --disable=gems -rrubygems -I./benchmark/lib ./benchmark/benchmark-driver/exe/benchmark-driver             --executables="compare-ruby::~/src/ruby/trunk/ruby --disable=gems -I.ext/common --disable-gem"             --executables="built-ruby::./miniruby -I./lib -I. -I.ext/common  -r./prelude --disable-gem" -v --repeat-count=24 $HOME/src/array_flatten.yml
compare-ruby: ruby 2.7.0dev (2019-09-22T17:21:54Z master 142efba93e) [x86_64-linux]
built-ruby: ruby 2.7.0dev (2019-09-22T18:10:18Z opt-flatten-empty-.. ae17889e1e) [x86_64-linux]
Calculating -------------------------------------
                     compare-ruby  built-ruby 
            flatten!       6.234M     31.453M i/s -      1.000M times in 0.160418s 0.031794s
             flatten       6.271M     31.324M i/s -      1.000M times in 0.159468s 0.031924s

Comparison:
                         flatten!
          built-ruby:  31452589.1 i/s 
        compare-ruby:   6233726.0 i/s - 5.05x  slower

                          flatten
          built-ruby:  31324068.7 i/s 
        compare-ruby:   6270832.4 i/s - 5.00x  slower
```


----------------------------------------
Feature #16119: Optimize Array#flatten and flatten! for already flattened arrays
https://bugs.ruby-lang.org/issues/16119#change-81668

* Author: dylants (Dylan Thacker-Smith)
* Status: Assigned
* Priority: Normal
* Assignee: nobu (Nobuyoshi Nakada)
* Target version: 
----------------------------------------
## Problem

When doing an object profile from stackprof, I noticed object allocations being made from `Array#flatten!` which was unlike other in-place methods like `Array#uniq!` and `Array#compact!`.  In this case, I wanted to optimize for the array already being flattened and found that `ary.flatten! if ary.any?(Array)` was significantly faster.  The code confirmed my suspicion that `ary.flatten!` was almost equivalent to `ary.replace(ary.flatten)` in implementation. The object allocations I noticed were from a temporary result array, a stack array to handle nesting and a hash table to prevent infinite recursion, all of which can be avoided in the simple case of an already flattened array.

## Solution

Iterate over the array to find the first nested array.  If no nested array is found, then `flatten!` just returns `nil` without creating additional objects and `flatten` returns a shared copy of the original array.  If a nested array is found, then it creates and initializes the temporary objects to resume with the existing algorithm for flattening the array.

## Benchmark

```ruby
require 'benchmark'

N = 100000

def report(x, name)
  x.report(name) do
    N.times do
      yield
    end
  end
end

arrays = {
  small_flat_ary: 5.times.to_a,
  large_flat_ary: 100.times.to_a,
  small_pairs_ary: [[1, 2]] * 5,
  large_pairs_ary: [[1, 2]] * 100,
}

Benchmark.bmbm do |x|
  arrays.each do |name, ary|
    report(x, "#{name}.flatten!") do
      ary.flatten!
    end
    report(x, "#{name}.flatten") do
      ary.flatten
    end
  end
end
```

results on the latest master (`ruby 2.7.0dev (2019-08-22T14:10:55Z master fd20b32130) [x86_64-darwin18]`)

```
                               user     system      total        real
small_flat_ary.flatten!    0.082001   0.000294   0.082295 (  0.082685)
small_flat_ary.flatten     0.078655   0.000211   0.078866 (  0.079176)
large_flat_ary.flatten!    0.552551   0.001643   0.554194 (  0.556166)
large_flat_ary.flatten     0.551520   0.001327   0.552847 (  0.554091)
small_pairs_ary.flatten!   0.100073   0.000302   0.100375 (  0.100687)
small_pairs_ary.flatten    0.109440   0.000232   0.109672 (  0.109850)
large_pairs_ary.flatten!   1.021200   0.001650   1.022850 (  1.024227)
large_pairs_ary.flatten    1.049046   0.002938   1.051984 (  1.055228)
```

results with the attached patch

```
                               user     system      total        real
small_flat_ary.flatten!    0.034868   0.000150   0.035018 (  0.035180)
small_flat_ary.flatten     0.040504   0.000148   0.040652 (  0.040914)
large_flat_ary.flatten!    0.458273   0.000786   0.459059 (  0.460005)
large_flat_ary.flatten     0.453846   0.000833   0.454679 (  0.455324)
small_pairs_ary.flatten!   0.055211   0.000205   0.055416 (  0.055673)
small_pairs_ary.flatten    0.060157   0.000226   0.060383 (  0.060540)
large_pairs_ary.flatten!   0.901698   0.001650   0.903348 (  0.905246)
large_pairs_ary.flatten    0.917180   0.001370   0.918550 (  0.920008)
```

---Files--------------------------------
0001-Optimize-Array-flatten-and-flatten-for-already-fl.diff.txt (2.79 KB)
0001-Let-empty-arrays-being-flattened-not-alloc-additiona.patch (791 Bytes)


-- 
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>