From: nobu@... Date: 2019-03-04T11:52:56+00:00 Subject: [ruby-core:91660] [Ruby trunk Bug#15625] Module#name performance has exponential-time worst case by aliased constants Issue #15625 has been updated by nobu (Nobuyoshi Nakada). Subject changed from Module#name performance has exponential-time worst case to Module#name performance has exponential-time worst case by aliased constants File bug-15625.patch added Of course it is possible to check duplicated paths to refine worst cases, but it is a trade-off for usual case; no aliased constants. ### trunk | user| system| total| real ------+----------:|----------:|----------:|-----------: before| 2.117049| 0.003000| 2.120049|( 2.123071) a9 | 5.685656| 0.006082| 5.691738|( 5.697850) a10 | 9.309634| 0.013036| 9.322670|( 9.336729) a11 | 16.784519| 0.049488| 16.834007|( 16.883028) ### patched | user| system| total| real ------+----------:|----------:|----------:|-----------: before| 3.161939| 0.055769| 3.217708|( 3.223522) a9 | 3.317957| 0.046668| 3.364625|( 3.369195) a10 | 3.316404| 0.045762| 3.362166|( 3.366455) a11 | 3.321730| 0.048193| 3.369923|( 3.374927) ---------------------------------------- Bug #15625: Module#name performance has exponential-time worst case by aliased constants https://bugs.ruby-lang.org/issues/15625#change-76922 * 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/ Unsubscribe: