Project

General

Profile

Actions

Bug #15625

closed

Module#name performance has exponential-time worst case by aliased constants

Added by nelhage (Nelson Elhage) about 5 years ago. Updated over 4 years ago.

Status:
Closed
Assignee:
-
Target version:
-
ruby -v:
ruby 2.6.1p33 (2019-01-30 revision 66950) [x86_64-darwin18]
[ruby-core:91632]

Description

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) classname.rb nelhage (Nelson Elhage), 02/27/2019 05:35 PM
bug-15625.patch (1.38 KB) bug-15625.patch nobu (Nobuyoshi Nakada), 03/04/2019 11:52 AM
Actions

Also available in: Atom PDF

Like0
Like0Like0Like0Like0Like0