From: Austin Ziegler Date: 2019-08-23T10:22:18-04:00 Subject: [ruby-core:94501] Re: [Ruby master Feature#16119] Optimize Array#flatten and flatten! for already flattened arrays --===============1090576597== Content-Type: multipart/alternative; boundary="000000000000990d950590c98909" --000000000000990d950590c98909 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable `Array(input).flatten` does not do the same thing as `[input].flatten`, though: ```ruby 10:21:38 >> input =3D {a: :b} =3D> {:a=3D>:b} 10:21:45 >> Array(input).flatten =3D> [:a, :b] 10:21:54 >> [input].flatten =3D> [{:a=3D>:b}] ``` On Fri, Aug 23, 2019 at 3:41 AM wrote: > Issue #16119 has been updated by Hanmac (Hans Mackowiak). > > > i see in your patch that you not only check for `Array` but for `to_ary` > too, which is nice > > > @shevegen : > > instead of `[input]` i would use `Array(input)` that doesn't create an > extra array if input is already one > > ---------------------------------------- > Feature #16119: Optimize Array#flatten and flatten! for already flattened > arrays > https://bugs.ruby-lang.org/issues/16119#change-80933 > > * Author: dylants (Dylan Thacker-Smith) > * Status: Open > * Priority: Normal > * Assignee: > * 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.flatte= n! > 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 nesti= ng > and a hash table to prevent infinite recursion, all of which can be avoid= ed > in the simple case of an already flattened array. > > ## Solution > > Iterate over the array to find the first nested array. If no nested arra= y > 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 =3D 100000 > > def report(x, name) > x.report(name) do > N.times do > yield > end > end > end > > arrays =3D { > 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) > > > -- > https://bugs.ruby-lang.org/ > > Unsubscribe: > > --=20 Austin Ziegler =E2=80=A2 halostatue@gmail.com =E2=80=A2 austin@halostatue.c= a http://www.halostatue.ca/ =E2=80=A2 http://twitter.com/halostatue --000000000000990d950590c98909 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
`Array(input).flatten` does not do the sa= me thing as `[input].flatten`, though:

```ruby
10:21:38 >> input =3D {a: :b}
=3D> {:a=3D>:b}
10:21:45 >> Array(input).flatten
=3D> [:a, :b]<= /div>
10:21:54 >> [input].flatten
=3D> [{:a=3D>:b= }]
```

On Fri, Aug 23, 2019 at 3:41 AM <hanmac@gmx.de> wrote:
Issue #16119 has been updated by Hanmac (Hans Mackowiak).


i see in your patch that you not only check for `Array` but for `to_ary` to= o, which is nice


@shevegen :

instead of `[input]` i would use `Array(input)` that doesn't create an = extra array if input is already one

----------------------------------------
Feature #16119: Optimize Array#flatten and flatten! for already flattened a= rrays
https://bugs.ruby-lang.org/issues/16119#change-8= 0933

* Author: dylants (Dylan Thacker-Smith)
* Status: Open
* Priority: Normal
* Assignee:
* Target version:
----------------------------------------
## Problem

When doing an object profile from stackprof, I noticed object allocations b= eing made from `Array#flatten!` which was unlike other in-place methods lik= e `Array#uniq!` and `Array#compact!`.=C2=A0 In this case, I wanted to optim= ize for the array already being flattened and found that `ary.flatten! if a= ry.any?(Array)` was significantly faster.=C2=A0 The code confirmed my suspi= cion 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 al= ready flattened array.

## Solution

Iterate over the array to find the first nested array.=C2=A0 If no nested a= rray is found, then `flatten!` just returns `nil` without creating addition= al objects and `flatten` returns a shared copy of the original array.=C2=A0= 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 =3D 100000

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

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

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

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

```
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2= =A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0user=C2=A0 =C2=A0 =C2=A0system=C2=A0 = =C2=A0 =C2=A0 total=C2=A0 =C2=A0 =C2=A0 =C2=A0 real
small_flat_ary.flatten!=C2=A0 =C2=A0 0.082001=C2=A0 =C2=A00.000294=C2=A0 = =C2=A00.082295 (=C2=A0 0.082685)
small_flat_ary.flatten=C2=A0 =C2=A0 =C2=A00.078655=C2=A0 =C2=A00.000211=C2= =A0 =C2=A00.078866 (=C2=A0 0.079176)
large_flat_ary.flatten!=C2=A0 =C2=A0 0.552551=C2=A0 =C2=A00.001643=C2=A0 = =C2=A00.554194 (=C2=A0 0.556166)
large_flat_ary.flatten=C2=A0 =C2=A0 =C2=A00.551520=C2=A0 =C2=A00.001327=C2= =A0 =C2=A00.552847 (=C2=A0 0.554091)
small_pairs_ary.flatten!=C2=A0 =C2=A00.100073=C2=A0 =C2=A00.000302=C2=A0 = =C2=A00.100375 (=C2=A0 0.100687)
small_pairs_ary.flatten=C2=A0 =C2=A0 0.109440=C2=A0 =C2=A00.000232=C2=A0 = =C2=A00.109672 (=C2=A0 0.109850)
large_pairs_ary.flatten!=C2=A0 =C2=A01.021200=C2=A0 =C2=A00.001650=C2=A0 = =C2=A01.022850 (=C2=A0 1.024227)
large_pairs_ary.flatten=C2=A0 =C2=A0 1.049046=C2=A0 =C2=A00.002938=C2=A0 = =C2=A01.051984 (=C2=A0 1.055228)
```

results with the attached patch

```
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2= =A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0user=C2=A0 =C2=A0 =C2=A0system=C2=A0 = =C2=A0 =C2=A0 total=C2=A0 =C2=A0 =C2=A0 =C2=A0 real
small_flat_ary.flatten!=C2=A0 =C2=A0 0.034868=C2=A0 =C2=A00.000150=C2=A0 = =C2=A00.035018 (=C2=A0 0.035180)
small_flat_ary.flatten=C2=A0 =C2=A0 =C2=A00.040504=C2=A0 =C2=A00.000148=C2= =A0 =C2=A00.040652 (=C2=A0 0.040914)
large_flat_ary.flatten!=C2=A0 =C2=A0 0.458273=C2=A0 =C2=A00.000786=C2=A0 = =C2=A00.459059 (=C2=A0 0.460005)
large_flat_ary.flatten=C2=A0 =C2=A0 =C2=A00.453846=C2=A0 =C2=A00.000833=C2= =A0 =C2=A00.454679 (=C2=A0 0.455324)
small_pairs_ary.flatten!=C2=A0 =C2=A00.055211=C2=A0 =C2=A00.000205=C2=A0 = =C2=A00.055416 (=C2=A0 0.055673)
small_pairs_ary.flatten=C2=A0 =C2=A0 0.060157=C2=A0 =C2=A00.000226=C2=A0 = =C2=A00.060383 (=C2=A0 0.060540)
large_pairs_ary.flatten!=C2=A0 =C2=A00.901698=C2=A0 =C2=A00.001650=C2=A0 = =C2=A00.903348 (=C2=A0 0.905246)
large_pairs_ary.flatten=C2=A0 =C2=A0 0.917180=C2=A0 =C2=A00.001370=C2=A0 = =C2=A00.918550 (=C2=A0 0.920008)
```

---Files--------------------------------
0001-Optimize-Array-flatten-and-flatten-for-already-fl.diff.txt (2.79 KB)

--
https://bugs.ruby-lang.org/

Unsubscribe: <mailto:ruby-core-request@ruby-lang.org?subject=3Dunsubscribe= >
<http://lists.ruby-lang.org/cgi-bin/m= ailman/options/ruby-core>


--
Austin Ziegler =E2=80=A2 halostatue@gmail.com =E2=80=A2 austin@halostatue.ca
http://www.ha= lostatue.ca/ =E2=80=A2 http://twitter.com/halostatue
--000000000000990d950590c98909-- --===============1090576597== Content-Type: text/plain; charset="us-ascii" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit Content-Disposition: inline Unsubscribe: --===============1090576597==--