* [ruby-core:94487] [Ruby master Feature#16119] Optimize Array#flatten and flatten! for already flattened arrays
[not found] <redmine.issue-16119.20190822235825@ruby-lang.org>
@ 2019-08-22 23:58 ` dylan.smith
2019-08-23 2:02 ` [ruby-core:94492] " duerst
` (8 subsequent siblings)
9 siblings, 0 replies; 11+ messages in thread
From: dylan.smith @ 2019-08-22 23:58 UTC (permalink / raw)
To: ruby-core
Issue #16119 has been reported by dylants (Dylan Thacker-Smith).
----------------------------------------
Feature #16119: Optimize Array#flatten and flatten! for already flattened arrays
https://bugs.ruby-lang.org/issues/16119
* 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.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)
--
https://bugs.ruby-lang.org/
^ permalink raw reply [flat|nested] 11+ messages in thread* [ruby-core:94492] [Ruby master Feature#16119] Optimize Array#flatten and flatten! for already flattened arrays
[not found] <redmine.issue-16119.20190822235825@ruby-lang.org>
2019-08-22 23:58 ` [ruby-core:94487] [Ruby master Feature#16119] Optimize Array#flatten and flatten! for already flattened arrays dylan.smith
@ 2019-08-23 2:02 ` duerst
2019-08-23 6:31 ` [ruby-core:94497] " shevegen
` (7 subsequent siblings)
9 siblings, 0 replies; 11+ messages in thread
From: duerst @ 2019-08-23 2:02 UTC (permalink / raw)
To: ruby-core
Issue #16119 has been updated by duerst (Martin Dürst).
I was afraid that this would be an optimization for flat arrays, but increase time for nested arrays. But that's not the case, because at the bottom, there will be flat arrays, and flattening these will be faster.
However, I expect this to be slower on arrays that are 'almost flat', i.e.
```
almost_flat_ary = 100.times.to_a + [1, 2]
```
Putting the nested array at the end will make sure all elements of the big array are checked, only to discover that actual flattening work is needed. The time needed for checking will not be offset by the allocation savings on the small array at the end.
Still I think that in general, this should be faster, and so it should be worth accepting this patch.
----------------------------------------
Feature #16119: Optimize Array#flatten and flatten! for already flattened arrays
https://bugs.ruby-lang.org/issues/16119#change-80927
* 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.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)
--
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>
^ permalink raw reply [flat|nested] 11+ messages in thread* [ruby-core:94497] [Ruby master Feature#16119] Optimize Array#flatten and flatten! for already flattened arrays
[not found] <redmine.issue-16119.20190822235825@ruby-lang.org>
2019-08-22 23:58 ` [ruby-core:94487] [Ruby master Feature#16119] Optimize Array#flatten and flatten! for already flattened arrays dylan.smith
2019-08-23 2:02 ` [ruby-core:94492] " duerst
@ 2019-08-23 6:31 ` shevegen
2019-08-23 7:41 ` [ruby-core:94498] " hanmac
` (6 subsequent siblings)
9 siblings, 0 replies; 11+ messages in thread
From: shevegen @ 2019-08-23 6:31 UTC (permalink / raw)
To: ruby-core
Issue #16119 has been updated by shevegen (Robert A. Heiler).
I use .flatten and .flatten! quite a lot in my ruby code, often setting the
initial input from ARGV but also from other sources, such as used from other
ruby classes, w hen I need to have an array - often something like:
def foobar(input)
new_value = [input].flatten.compact
Or something like that. If this patch indeed improves this then that would
be quite nice to have.
----------------------------------------
Feature #16119: Optimize Array#flatten and flatten! for already flattened arrays
https://bugs.ruby-lang.org/issues/16119#change-80932
* 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.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)
--
https://bugs.ruby-lang.org/
^ permalink raw reply [flat|nested] 11+ messages in thread* [ruby-core:94498] [Ruby master Feature#16119] Optimize Array#flatten and flatten! for already flattened arrays
[not found] <redmine.issue-16119.20190822235825@ruby-lang.org>
` (2 preceding siblings ...)
2019-08-23 6:31 ` [ruby-core:94497] " shevegen
@ 2019-08-23 7:41 ` hanmac
2019-08-23 14:22 ` [ruby-core:94501] " Austin Ziegler
2019-08-23 15:32 ` [ruby-core:94504] " dylan.smith
` (5 subsequent siblings)
9 siblings, 1 reply; 11+ messages in thread
From: hanmac @ 2019-08-23 7:41 UTC (permalink / raw)
To: ruby-core
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.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)
--
https://bugs.ruby-lang.org/
^ permalink raw reply [flat|nested] 11+ messages in thread* [ruby-core:94501] Re: [Ruby master Feature#16119] Optimize Array#flatten and flatten! for already flattened arrays
2019-08-23 7:41 ` [ruby-core:94498] " hanmac
@ 2019-08-23 14:22 ` Austin Ziegler
0 siblings, 0 replies; 11+ messages in thread
From: Austin Ziegler @ 2019-08-23 14:22 UTC (permalink / raw)
To: Ruby developers
[-- Attachment #1.1: Type: text/plain, Size: 4628 bytes --]
`Array(input).flatten` does not do the same thing as `[input].flatten`,
though:
```ruby
10:21:38 >> input = {a: :b}
=> {:a=>:b}
10:21:45 >> Array(input).flatten
=> [:a, :b]
10:21:54 >> [input].flatten
=> [{:a=>: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`
> 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.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)
>
>
> --
> 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>
>
--
Austin Ziegler • halostatue@gmail.com • austin@halostatue.ca
http://www.halostatue.ca/ • http://twitter.com/halostatue
[-- Attachment #1.2: Type: text/html, Size: 6162 bytes --]
[-- Attachment #2: Type: text/plain, Size: 0 bytes --]
^ permalink raw reply [flat|nested] 11+ messages in thread
* [ruby-core:94504] [Ruby master Feature#16119] Optimize Array#flatten and flatten! for already flattened arrays
[not found] <redmine.issue-16119.20190822235825@ruby-lang.org>
` (3 preceding siblings ...)
2019-08-23 7:41 ` [ruby-core:94498] " hanmac
@ 2019-08-23 15:32 ` dylan.smith
2019-08-23 15:38 ` [ruby-core:94506] " dylan.smith
` (4 subsequent siblings)
9 siblings, 0 replies; 11+ messages in thread
From: dylan.smith @ 2019-08-23 15:32 UTC (permalink / raw)
To: ruby-core
Issue #16119 has been updated by dylants (Dylan Thacker-Smith).
duerst (Martin Dürst) wrote:
> However, I expect this to be slower on arrays that are 'almost flat', i.e.
> ```
> almost_flat_ary = 100.times.to_a + [1, 2]
> ```
> Putting the nested array at the end will make sure all elements of the big array are checked, only to discover that actual flattening work is needed. The time needed for checking will not be offset by the allocation savings on the small array at the end.
The optimization handles this case by doing a quick `ary_memcpy` of everything up to the first nested array to avoid redundantly rechecking if those preceding elements were an array.
I benchmarked it by replacing `arrays` and `Benchmark.bmbm` in my above bechmark script with
```ruby
ary = 100.times.to_a.push([101, 102])
Benchmark.bmbm do |x|
report(x, "flatten!") do
ary.flatten!
end
report(x, "flatten") do
ary.flatten
end
end
```
and got the following results on master
```
user system total real
flatten! 0.577976 0.002275 0.580251 ( 0.582700)
flatten 0.542454 0.001994 0.544448 ( 0.546523)
```
and the following results with this patch
```
user system total real
flatten! 0.420922 0.001052 0.421974 ( 0.422957)
flatten 0.430728 0.001173 0.431901 ( 0.433274)
```
so I actually noticed improved performance for arrays with a large flat prefix.
----------------------------------------
Feature #16119: Optimize Array#flatten and flatten! for already flattened arrays
https://bugs.ruby-lang.org/issues/16119#change-80938
* 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.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)
--
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>
^ permalink raw reply [flat|nested] 11+ messages in thread* [ruby-core:94506] [Ruby master Feature#16119] Optimize Array#flatten and flatten! for already flattened arrays
[not found] <redmine.issue-16119.20190822235825@ruby-lang.org>
` (4 preceding siblings ...)
2019-08-23 15:32 ` [ruby-core:94504] " dylan.smith
@ 2019-08-23 15:38 ` dylan.smith
2019-09-19 8:31 ` [ruby-core:94984] " mame
` (3 subsequent siblings)
9 siblings, 0 replies; 11+ messages in thread
From: dylan.smith @ 2019-08-23 15:38 UTC (permalink / raw)
To: ruby-core
Issue #16119 has been updated by dylants (Dylan Thacker-Smith).
Hanmac (Hans Mackowiak) wrote:
> i see in your patch that you not only check for `Array` but for `to_ary` too, which is nice
Right, but that is just preserving the current behaviour. So the `ary.flatten! if ary.any?(Array)` workaround could actually be a breaking change if the given array had elements that responded to `to_ary` other than `Array`.
----------------------------------------
Feature #16119: Optimize Array#flatten and flatten! for already flattened arrays
https://bugs.ruby-lang.org/issues/16119#change-80940
* 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.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)
--
https://bugs.ruby-lang.org/
^ permalink raw reply [flat|nested] 11+ messages in thread* [ruby-core:94984] [Ruby master Feature#16119] Optimize Array#flatten and flatten! for already flattened arrays
[not found] <redmine.issue-16119.20190822235825@ruby-lang.org>
` (5 preceding siblings ...)
2019-08-23 15:38 ` [ruby-core:94506] " dylan.smith
@ 2019-09-19 8:31 ` mame
2019-09-20 0:19 ` [ruby-core:94994] " nobu
` (2 subsequent siblings)
9 siblings, 0 replies; 11+ messages in thread
From: mame @ 2019-09-19 8:31 UTC (permalink / raw)
To: ruby-core
Issue #16119 has been updated by mame (Yusuke Endoh).
Assignee set to nobu (Nobuyoshi Nakada)
Status changed from Open to Assigned
@nobu Could you please review this?
----------------------------------------
Feature #16119: Optimize Array#flatten and flatten! for already flattened arrays
https://bugs.ruby-lang.org/issues/16119#change-81603
* 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)
--
https://bugs.ruby-lang.org/
^ permalink raw reply [flat|nested] 11+ messages in thread* [ruby-core:94994] [Ruby master Feature#16119] Optimize Array#flatten and flatten! for already flattened arrays
[not found] <redmine.issue-16119.20190822235825@ruby-lang.org>
` (6 preceding siblings ...)
2019-09-19 8:31 ` [ruby-core:94984] " mame
@ 2019-09-20 0:19 ` nobu
2019-09-22 18:29 ` [ruby-core:95037] " lourens
2019-09-27 3:42 ` [ruby-core:95124] " dylan.smith
9 siblings, 0 replies; 11+ messages in thread
From: nobu @ 2019-09-20 0:19 UTC (permalink / raw)
To: ruby-core
Issue #16119 has been updated by nobu (Nobuyoshi Nakada).
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
```
----------------------------------------
Feature #16119: Optimize Array#flatten and flatten! for already flattened arrays
https://bugs.ruby-lang.org/issues/16119#change-81622
* 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)
--
https://bugs.ruby-lang.org/
^ permalink raw reply [flat|nested] 11+ messages in thread* [ruby-core:95037] [Ruby master Feature#16119] Optimize Array#flatten and flatten! for already flattened arrays
[not found] <redmine.issue-16119.20190822235825@ruby-lang.org>
` (7 preceding siblings ...)
2019-09-20 0:19 ` [ruby-core:94994] " nobu
@ 2019-09-22 18:29 ` lourens
2019-09-27 3:42 ` [ruby-core:95124] " dylan.smith
9 siblings, 0 replies; 11+ messages in thread
From: lourens @ 2019-09-22 18:29 UTC (permalink / raw)
To: ruby-core
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>
^ permalink raw reply [flat|nested] 11+ messages in thread* [ruby-core:95124] [Ruby master Feature#16119] Optimize Array#flatten and flatten! for already flattened arrays
[not found] <redmine.issue-16119.20190822235825@ruby-lang.org>
` (8 preceding siblings ...)
2019-09-22 18:29 ` [ruby-core:95037] " lourens
@ 2019-09-27 3:42 ` dylan.smith
9 siblings, 0 replies; 11+ messages in thread
From: dylan.smith @ 2019-09-27 3:42 UTC (permalink / raw)
To: ruby-core
Issue #16119 has been updated by dylants (Dylan Thacker-Smith).
It looks like I made a mistake in my benchmarking of non-flattened arrays, since flatten! from the first iteration would cause further iterations to actually test with a flat array. It looks like the performance for arrays starting with a nested array are about the same with and without my patch.
The attached patch has a merge conflict. I've opened https://github.com/ruby/ruby/pull/2495 with a rebase of my patch that resolves the merge conflict. That PR also has an updated benchmark that uses the benchmark driver yaml format and includes the results from running that benchmark.
nobu (Nobuyoshi Nakada) wrote:
> But I could get only insignificant result, and a worse result for an unflattened array.
It looks like nobu's benchmark/array_flatten.yml has the same problem with the non-flat arrays being mutated and affecting following iterations. That explains the improvement I am seeing locally with your benchmark, although I don't know why my results differ from what you posted
```
Comparison:
flatten!
built-ruby: 246214.2 i/s
compare-ruby: 193998.4 i/s - 1.27x slower
flatten
built-ruby: 214275.0 i/s
compare-ruby: 188818.6 i/s - 1.13x slower
flatten2
built-ruby: 159840.8 i/s
compare-ruby: 159546.4 i/s - 1.00x slower
```
where only the last one actually benchmarks an unflattened array properly.
methodmissing (Lourens Naudé) wrote:
> 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):
There is no need to special case the empty array case. My patch would just treat it as a flat array, so would still avoid extra allocations and return early.
----------------------------------------
Feature #16119: Optimize Array#flatten and flatten! for already flattened arrays
https://bugs.ruby-lang.org/issues/16119#change-81758
* 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>
^ permalink raw reply [flat|nested] 11+ messages in thread