From: jean.boussier@gmail.com
To: ruby-core@ruby-lang.org
Subject: [ruby-core:92779] [Ruby trunk Bug#15625] Module#name performance has exponential-time worst case by aliased constants
Date: Wed, 22 May 2019 09:29:19 +0000 (UTC) [thread overview]
Message-ID: <redmine.journal-78144.20190522092918.c1d9c79fba44a531@ruby-lang.org> (raw)
In-Reply-To: redmine.issue-15625.20190227173636@ruby-lang.org
Issue #15625 has been updated by byroot (Jean Boussier).
This was fixed in https://bugs.ruby-lang.org/issues/15765
----------------------------------------
Bug #15625: Module#name performance has exponential-time worst case by aliased constants
https://bugs.ruby-lang.org/issues/15625#change-78144
* 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/
prev parent reply other threads:[~2019-05-22 9:29 UTC|newest]
Thread overview: 5+ messages / expand[flat|nested] mbox.gz Atom feed top
[not found] <redmine.issue-15625.20190227173636@ruby-lang.org>
2019-02-27 17:36 ` [ruby-core:91632] [Ruby trunk Bug#15625] Module#name performance has exponential-time worst case nelhage
2019-02-27 20:11 ` [ruby-core:91633] " shevegen
2019-03-04 11:52 ` [ruby-core:91660] [Ruby trunk Bug#15625] Module#name performance has exponential-time worst case by aliased constants nobu
2019-03-04 13:13 ` [ruby-core:91661] " eregontp
2019-05-22 9:29 ` jean.boussier [this message]
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-list from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
List information: https://www.ruby-lang.org/en/community/mailing-lists/
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=redmine.journal-78144.20190522092918.c1d9c79fba44a531@ruby-lang.org \
--to=ruby-core@ruby-lang.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).