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-Status: No, score=-3.1 required=3.0 tests=BAYES_00,DKIM_ADSP_CUSTOM_MED, FORGED_GMAIL_RCVD,FREEMAIL_FORGED_FROMDOMAIN,FREEMAIL_FROM, HEADER_FROM_DIFFERENT_DOMAINS,MAILING_LIST_MULTI,RCVD_IN_DNSWL_MED, SPF_HELO_NONE,SPF_PASS,UNPARSEABLE_RELAY 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 417E81F531 for ; Mon, 10 Aug 2020 12:27:57 +0000 (UTC) Received: from neon.ruby-lang.org (localhost [IPv6:::1]) by neon.ruby-lang.org (Postfix) with ESMTP id 1DD971209CC; Mon, 10 Aug 2020 21:27:24 +0900 (JST) Received: from xtrwkhkc.outbound-mail.sendgrid.net (xtrwkhkc.outbound-mail.sendgrid.net [167.89.16.28]) by neon.ruby-lang.org (Postfix) with ESMTPS id 4F85C1209C9 for ; Mon, 10 Aug 2020 21:27:21 +0900 (JST) Received: by filterdrecv-p3mdw1-7ff865655c-ppm4p with SMTP id filterdrecv-p3mdw1-7ff865655c-ppm4p-20-5F313D40-57 2020-08-10 12:27:44.819269304 +0000 UTC m=+1015889.952961761 Received: from herokuapp.com (unknown) by ismtpd0115p1mdw1.sendgrid.net (SG) with ESMTP id 60cuSIimS9WKyzAhV51XwQ for ; Mon, 10 Aug 2020 12:27:44.738 +0000 (UTC) Date: Mon, 10 Aug 2020 12:27:44 +0000 (UTC) From: andrey.samsonov@gmail.com Message-ID: References: Mime-Version: 1.0 X-Redmine-MailingListIntegration-Message-Ids: 75366 X-Redmine-Project: ruby-master X-Redmine-Issue-Tracker: Feature X-Redmine-Issue-Id: 17109 X-Redmine-Issue-Author: andrey.samsonov@gmail.com X-Redmine-Sender: andrey.samsonov@gmail.com 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?FHVhRKlnIypVzlrUGRuGIrasbc5naWVQw1cqYO02np2iJvVdauZ5l=2F2hbiOpYm?= =?us-ascii?Q?EADNbjndWUc72rkCSCnHnCYyYGg+9Y4CW=2FPikht?= =?us-ascii?Q?Z3ByR843cB7MKA8cqOQZJ9GTivUsymU8OSC6Bgi?= =?us-ascii?Q?y+CBi2QnRIDyY2l3aICATaB7iJ95OQzm2YHcvdj?= =?us-ascii?Q?HhsarnLLJnFgvDlQwua0KkgstslY51bGzmLfpYO?= =?us-ascii?Q?Yb38YtSWIcOj+x2Hw=3D?= To: ruby-core@ruby-lang.org X-ML-Name: ruby-core X-Mail-Count: 99540 Subject: [ruby-core:99540] [Ruby master Feature#17109] Eliminate the performance impact of operands' order in array's | and & 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 #17109 has been updated by andrey.samsonov@gmail.com (Andrey Samsonov). > > The order is preserved from the original array. My bad, I missed the comment. In this case, I think the optimisation is not worth a change in the spec. ---------------------------------------- Feature #17109: Eliminate the performance impact of operands' order in array's | and & https://bugs.ruby-lang.org/issues/17109#change-86999 * Author: andrey.samsonov@gmail.com (Andrey Samsonov) * Status: Open * Priority: Normal ---------------------------------------- When I do intersection (`a & b`) or union (`a | b`), usually the array in one position is more likely longer than the one in the other position. I always try to remember in what order I should write `a` and` b` for the best performance. The right answers for current implementation are `longer & shorter` and` longer | shorter`. [Here](https://github.com/kryzhovnik/ruby/commit/3b5923746792db5a73bc80a2cb9fe982d41a9fa3) I suggest to make it simpler and eliminate the difference. Sorry I don't know C. Though I suppose my solution might be too blunt and verbose, I hope it demonstrates the idea. make benchmark ITEM=array_union COMPARE_RUBY=~/.rbenv/versions/2.8.0-dev/bin/ruby | |compare-ruby|built-ruby| |:-------------------------|-----------:|---------:| |small-& | 4.315M| 4.228M| | | 1.02x| -| |small-intersection | 4.157M| 4.106M| | | 1.01x| -| |big-& | 107.258k| 132.051k| | | -| 1.23x| |big-intersection | 103.245k| 128.052k| | | -| 1.24x| |big-reverse-intersection | 96.544k| 159.201k| | | -| 1.65x| My own [test](https://gist.github.com/kryzhovnik/288953a5c89df10e2611668703a1511c) shows 20-30% perf improvement of Array#union. -- https://bugs.ruby-lang.org/