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 81D9A1F461 for ; Fri, 23 Aug 2019 15:38:14 +0000 (UTC) Received: from neon.ruby-lang.org (localhost [IPv6:::1]) by neon.ruby-lang.org (Postfix) with ESMTP id C4156120AAC; Sat, 24 Aug 2019 00:38:07 +0900 (JST) Received: from o1678916x28.outbound-mail.sendgrid.net (o1678916x28.outbound-mail.sendgrid.net [167.89.16.28]) by neon.ruby-lang.org (Postfix) with ESMTPS id C53F6120A9F for ; Sat, 24 Aug 2019 00:38:05 +0900 (JST) Received: by filter0008p3iad2.sendgrid.net with SMTP id filter0008p3iad2-8836-5D60085E-34 2019-08-23 15:38:06.785933669 +0000 UTC m=+59967.388416071 Received: from herokuapp.com (unknown [3.81.9.76]) by ismtpd0030p1iad2.sendgrid.net (SG) with ESMTP id JdLqCzkfQ6-PEwq_MrNUlw for ; Fri, 23 Aug 2019 15:38:06.773 +0000 (UTC) Date: Fri, 23 Aug 2019 15:38:06 +0000 (UTC) From: dylan.smith@shopify.com Message-ID: References: Mime-Version: 1.0 X-Redmine-MailingListIntegration-Message-Ids: 70055 X-Redmine-Project: ruby-trunk X-Redmine-Issue-Id: 16119 X-Redmine-Issue-Author: dylants 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=2FzZF8dlJcyevu2noetPm0Hp176ZTT4?= =?us-ascii?Q?twXnvqA04ABtglHRoRQnFuNdhOV17P6wDdhBDuC?= =?us-ascii?Q?o4f=2F6xEJ1oLnqOgAkH=2FjLxLhNAT0sLXG5p9gqr5?= =?us-ascii?Q?PeR1Z9x4iKeOAWSn2Y7QOBwFGOT0AlnUoxDdHkl?= =?us-ascii?Q?MUGGPtj99uCuzeVBDVxmiDRwyaf+3MjLvVQ=3D=3D?= To: ruby-core@ruby-lang.org X-ML-Name: ruby-core X-Mail-Count: 94506 Subject: [ruby-core:94506] [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="us-ascii" Content-Transfer-Encoding: 7bit Errors-To: ruby-core-bounces@ruby-lang.org Sender: "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/