lib/modules: optimize byName

the foldl is equivalent to a zip with concat. list concatenation in nix
is an O(n) operation, which makes this operation extremely inefficient
when large numbers of modules are involved.

this change reduces the number of list elements by 7 million on the
system used to write this, total memory spent on lists by 58MB, and
total memory allocated on the GC heap by almost 100MB (with a similar
reduction in GC heap size). it's also slightly faster.

1 files changed, 5 insertions, 6 deletions

diff --git a/lib/modules.nix b/lib/modules.nix
index 573bf40e4b3..091c72e30aa 100644
--- a/lib/modules.nix
+++ b/lib/modules.nix
@@ -37,6 +37,7 @@ let
     toList
     types
     warnIf
+    zipAttrsWith
     ;
   inherit (lib.options)
     isOption
@@ -442,7 +443,8 @@ rec {
         }
       */
       byName = attr: f: modules:
-        foldl' (acc: module:
+        zipAttrsWith (n: concatLists)
+          (map (module:
               if !(builtins.isAttrs module.${attr}) then
                 throw ''
                   You're trying to declare a value of type `${builtins.typeOf module.${attr}}'
@@ -454,11 +456,8 @@ rec {
                   this option by e.g. referring to `man 5 configuration.nix'!
                 ''
               else
-                acc // (mapAttrs (n: v:
-                                   (acc.${n} or []) ++ f module v
-                                 ) module.${attr}
-                       )
-               ) {} modules;
+                mapAttrs (n: f module) module.${attr}
+              ) modules);
       # an attrset 'name' => list of submodules that declare ‘name’.
       declsByName = byName "options" (module: option:
           [{ inherit (module) _file; options = option; }]