From: nobu@... Date: 2019-09-20T00:19:49+00:00 Subject: [ruby-core:94994] [Ruby master Feature#16119] Optimize Array#flatten and flatten! for already flattened arrays 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/ Unsubscribe: