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=-2.8 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_PASS shortcircuit=no autolearn=no 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 DEFC720248 for ; Mon, 4 Mar 2019 13:13:59 +0000 (UTC) Received: from neon.ruby-lang.org (localhost [IPv6:::1]) by neon.ruby-lang.org (Postfix) with ESMTP id ED22A121C41; Mon, 4 Mar 2019 22:13:54 +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 0EAC7121C03 for ; Mon, 4 Mar 2019 22:13:46 +0900 (JST) Received: by filter0074p3iad2.sendgrid.net with SMTP id filter0074p3iad2-13276-5C7D2483-2D 2019-03-04 13:13:39.745422675 +0000 UTC m=+307799.988850737 Received: from herokuapp.com (unknown [18.208.174.211]) by ismtpd0001p1iad1.sendgrid.net (SG) with ESMTP id ZugoaGFaRTucr8BV39gLiw for ; Mon, 04 Mar 2019 13:13:39.621 +0000 (UTC) Date: Mon, 04 Mar 2019 13:13:40 +0000 (UTC) From: eregontp@gmail.com Message-ID: References: Mime-Version: 1.0 X-Redmine-MailingListIntegration-Message-Ids: 67111 X-Redmine-Project: ruby-trunk X-Redmine-Issue-Id: 15625 X-Redmine-Issue-Author: nelhage X-Redmine-Sender: Eregon 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?KippOI8ZHtTweq7XfQzW93937kJ4QNWwSBuHnaMEcr2EONHVczI+u34Mpaj7Lw?= =?us-ascii?Q?yT63TFPz7kjMI422U+qAsM5PHtuuc3rqGaADpns?= =?us-ascii?Q?37AYjClDR7lpGDGs06oGkU5bogeir2v7LWZtKBl?= =?us-ascii?Q?nslU92MQxbuSk=2FPVa7wk+xtxMLWqQkyD7=2FJQinR?= =?us-ascii?Q?1o2x7kj9PZlxgMHDZH77xp4kOhfds7c0k9w=3D=3D?= To: ruby-core@ruby-lang.org X-ML-Name: ruby-core X-Mail-Count: 91661 Subject: [ruby-core:91661] [Ruby trunk Bug#15625] Module#name performance has exponential-time worst case by aliased constants 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 #15625 has been updated by Eregon (Benoit Daloze). Why is such a search performed every time? Is it not enough to cache the name in the Module instance (since it keeps the name even after the constant is removed anyway) ? Also, I think naming can be done proactively when assigning constants, instead of a lazy search (that's what TruffleRuby does). ---------------------------------------- Bug #15625: Module#name performance has exponential-time worst case by aliased constants https://bugs.ruby-lang.org/issues/15625#change-76923 * Author: nelhage (Nelson Elhage) * Status: Open * Priority: Normal * Assignee: * Target version: * ruby -v: ruby 2.6.1p33 (2019-01-30 revision 66950) [x86_64-darwin18] * Backport: 2.4: UNKNOWN, 2.5: UNKNOWN, 2.6: UNKNOWN ---------------------------------------- It's well-known (c.f #11119) that `Module#name` has poor performance on anonymous classes, due to searching the entire constant namespace of the VM. However, we recently discovered that it's even worse than that. In the presence of aliased constants (e.g. `module M; end; Alias = M`), the `find_class_path` method actually searches every *path* to a given module (e.g. it will visit that module under both the `M` and `Alias` names). This can lead to exponential-time behavior in cases of repeated aliases. See the attached test case, where performance gets twice as slow with every additional layer of aliasing: On my laptop: ``` user system total real before 2.183899 0.012151 2.196050 ( 2.355187) user system total real a19 5.614596 0.024394 5.638990 ( 5.702878) user system total real a10 9.204399 0.052817 9.257216 ( 9.391010) user system total real a11 16.184035 0.060854 16.244889 ( 16.561101) ``` Our house style makes extensive use of aliases as an import-like mechanism to provide short names within a given scope. We discovered this bug while exploring an actual performance problem -- this is not just a theoretical report. ---Files-------------------------------- classname.rb (854 Bytes) bug-15625.patch (1.38 KB) -- https://bugs.ruby-lang.org/