From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.2 (2018-09-13) on dcvr.yhbt.net X-Spam-Level: X-Spam-ASN: AS4713 221.184.0.0/13 X-Spam-Status: No, score=-3.9 required=3.0 tests=BAYES_00, HEADER_FROM_DIFFERENT_DOMAINS,MAILING_LIST_MULTI,RCVD_IN_DNSWL_MED, SPF_HELO_NONE,SPF_PASS shortcircuit=no autolearn=ham autolearn_force=no version=3.4.2 Received: from neon.ruby-lang.org (neon.ruby-lang.org [221.186.184.75]) by dcvr.yhbt.net (Postfix) with ESMTP id 517981F463 for ; Fri, 27 Sep 2019 03:42:57 +0000 (UTC) Received: from neon.ruby-lang.org (localhost [IPv6:::1]) by neon.ruby-lang.org (Postfix) with ESMTP id 7C25F120A7D; Fri, 27 Sep 2019 12:42:47 +0900 (JST) Received: from o1678948x4.outbound-mail.sendgrid.net (o1678948x4.outbound-mail.sendgrid.net [167.89.48.4]) by neon.ruby-lang.org (Postfix) with ESMTPS id 3F425120880 for ; Fri, 27 Sep 2019 12:42:45 +0900 (JST) Received: by filter0186p3mdw1.sendgrid.net with SMTP id filter0186p3mdw1-25793-5D8D8537-24 2019-09-27 03:42:47.592082352 +0000 UTC m=+284687.356907853 Received: from herokuapp.com (unknown [3.91.96.212]) by ismtpd0073p1iad2.sendgrid.net (SG) with ESMTP id 30uE1ZkiTmS7aUMc6NUi6Q for ; Fri, 27 Sep 2019 03:42:47.546 +0000 (UTC) Date: Fri, 27 Sep 2019 03:42:47 +0000 (UTC) From: dylan.smith@shopify.com Message-ID: References: Mime-Version: 1.0 X-Redmine-MailingListIntegration-Message-Ids: 70679 X-Redmine-Project: ruby-trunk X-Redmine-Issue-Id: 16119 X-Redmine-Issue-Author: dylants X-Redmine-Issue-Assignee: nobu X-Redmine-Sender: dylants X-Mailer: Redmine X-Redmine-Host: bugs.ruby-lang.org X-Redmine-Site: Ruby Issue Tracking System X-Auto-Response-Suppress: All Auto-Submitted: auto-generated X-SG-EID: =?us-ascii?Q?dye2b5k+s5R=2FP40aJKRU6ni9RfYjcVEz=2FzZF8dlJcyecSJoFDQZex2ZdmywhIz?= =?us-ascii?Q?KCG869FTeoeZZBmm74dasS8PeuzfTpe1aYqUb5E?= =?us-ascii?Q?W93ztrEalHp7TO4f2MyQOJ0oErgHI5fV+89EVVe?= =?us-ascii?Q?KrJknL35fSvTJQQ8vKj4F+ORCivwTi51Rvbz3US?= =?us-ascii?Q?22fFnDYTPbu+YxteRYXc=2FTmArWLHmwzDjEw=3D=3D?= To: ruby-core@ruby-lang.org X-ML-Name: ruby-core X-Mail-Count: 95124 Subject: [ruby-core:95124] [Ruby master Feature#16119] Optimize Array#flatten and flatten! for already flattened arrays X-BeenThere: ruby-core@ruby-lang.org X-Mailman-Version: 2.1.15 Precedence: list Reply-To: Ruby developers List-Id: Ruby developers List-Unsubscribe: , List-Post: List-Help: List-Subscribe: , Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable Errors-To: ruby-core-bounces@ruby-lang.org Sender: "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 a= ctually test with a flat array. It looks like the performance for arrays s= tarting 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/ru= by/ruby/pull/2495 with a rebase of my patch that resolves the merge conflic= t. That PR also has an updated benchmark that uses the benchmark driver ya= ml 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 unfl= attened 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=E9) 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 prac= tice): 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 retur= n early. ---------------------------------------- Feature #16119: Optimize Array#flatten and flatten! for already flattened a= rrays 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 b= eing made from `Array#flatten!` which was unlike other in-place methods lik= e `Array#uniq!` and `Array#compact!`. In this case, I wanted to optimize f= or the array already being flattened and found that `ary.flatten! if ary.an= y?(Array)` was significantly faster. The code confirmed my suspicion that = `ary.flatten!` was almost equivalent to `ary.replace(ary.flatten)` in imple= mentation. The object allocations I noticed were from a temporary result ar= ray, a stack array to handle nesting and a hash table to prevent infinite r= ecursion, all of which can be avoided in the simple case of an already flat= tened 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 ob= jects and `flatten` returns a shared copy of the original array. If a nest= ed 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 f= d20b32130) [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: