Another implementation of mapAttrsToList

In nixpkgs, mapAttrsToList is implemented as follows:

f: attrs: map (name: f name attrs.${name}) (attrNames attrs)

Here is another implementation::

f: attrs: attrValues (mapAttrs (name: value: f name value) attrs)

This implementation avoids redundant lookups of elements in attrs and should theoretically be faster. Can anyone test this?

1 Like

You can shorten this to:

f: attrs: attrValues (mapAttrs f attrs)

I’m not sure where the redundant lookup is that you mean.

In nixpkgs’ version attrs.${name} looks up the value for each entry in the attrset.
In your version, mapAttrs does the same — it would not be able to provide the value: argument otherwise.

Maybe you mean only the case in which the value is not used in f? Nix probably does not force evaluation of attrs.${name} in that situation either, so both versions are probably equivalent or very similar. Let’s find out…


Benchmarks

Huge Attrset

Nixpkgs Version

let
  lib = (import <nixpkgs> {}).lib;
  data = lib.genAttrs (lib.genList toString 1000000) (i: {a = i; b = i;});
in
  lib.mapAttrsToList (k: v: {inherit k;}) data
❯ hyperfine --warmup 2 'nix eval --json -f foo.nix > /dev/null'
Benchmark 1: nix eval --json -f foo.nix > /dev/null
  Time (mean ± σ):      5.035 s ±  1.992 s    [User: 2.750 s, System: 0.350 s]
  Range (min … max):    3.144 s …  7.089 s    10 runs

Your Version

let
  lib = (import <nixpkgs> {}).lib;
  data = lib.genAttrs (lib.genList toString 1000000) (i: {a = i; b = i;});
  mapAttrsToList = f: attrs: builtins.attrValues (builtins.mapAttrs f attrs);
in
  mapAttrsToList (k: v: {inherit k;}) data
❯ hyperfine --warmup 2 'nix eval --json -f foo.nix > /dev/null'
Benchmark 1: nix eval --json -f foo.nix > /dev/null
  Time (mean ± σ):      5.015 s ±  1.855 s    [User: 2.866 s, System: 0.341 s]
  Range (min … max):    3.250 s …  7.000 s    10 runs

Many small attrsets

Nixpkgs Version

let
  lib = (import <nixpkgs> {}).lib;
  data = map (i: {a = toString i; b = toString i;}) (lib.genList toString 1000000);
in
  map (lib.mapAttrsToList (k: v: {inherit k;})) data
❯ hyperfine --warmup 2 'nix eval --json -f foo.nix > /dev/null'
Benchmark 1: nix eval --json -f foo.nix > /dev/null
  Time (mean ± σ):      5.149 s ±  1.561 s    [User: 3.055 s, System: 0.529 s]
  Range (min … max):    3.644 s …  6.934 s    10 runs

Your Version

let
  lib = (import <nixpkgs> {}).lib;
  data = map (i: {a = toString i; b = toString i;}) (lib.genList toString 1000000);
  mapAttrsToList = f: attrs: builtins.attrValues (builtins.mapAttrs f attrs);
in
  map (mapAttrsToList (k: v: {inherit k;})) data
❯ hyperfine --warmup 2 'nix eval --json -f foo.nix > /dev/null'
Benchmark 1: nix eval --json -f foo.nix > /dev/null
  Time (mean ± σ):      4.985 s ±  1.431 s    [User: 3.081 s, System: 0.529 s]
  Range (min … max):    3.643 s …  6.643 s    10 runs

The differences don’t seem significant. My guess is both versions are optimized into equivalent code.

3 Likes

You’re right — there’s no need to wrap the function in a lambda again before passing it to mapAttrs.
This implementation is not only simpler than the one used in nixpkgs, but it also aligns better with the name.
In this form, mapAttrsToList is truly a wrapper around mapAttrs.

mapAttrs is a built-in function, and its implementation can be found here: nix/src/libexpr/primops.cc at 2ec13032864c966679beb9a95dcb1f48644ab8c9 · NixOS/nix · GitHub

Compared to the original implementation, mapAttrs doesn’t actually require an additional lookup using the attribute name.

mapAttrs does not do a lookup immediately, but if f uses the value: argument, it has to be looked up eventually. My point was that the thunk attrs.${name}, if unused in f, is likely not forced, and therefore incurs very minimal overhead. No idea if that’s actually true though, it’s just a guess.

In my benchmark above, I did not use the value in f. Let’s try and see what happens if we do.


Huge attrset

Nixpkgs Version

let
  lib = (import <nixpkgs> {}).lib;
  data = lib.genAttrs (lib.genList toString 1000000) (i: {a = i; b = i;});
in
  lib.mapAttrsToList (k: v: {inherit k v;}) data
❯ hyperfine --warmup 2 'nix eval --json -f foo.nix > /dev/null'
Benchmark 1: nix eval --json -f foo.nix > /dev/null
  Time (mean ± σ):     10.231 s ±  0.059 s    [User: 4.931 s, System: 0.593 s]
  Range (min … max):   10.160 s … 10.335 s    10 runs

Your Version

let
  lib = (import <nixpkgs> {}).lib;
  data = lib.genAttrs (lib.genList toString 1000000) (i: {a = i; b = i;});
  mapAttrsToList = f: attrs: builtins.attrValues (builtins.mapAttrs f attrs);
in
  mapAttrsToList (k: v: {inherit k v;}) data
❯ hyperfine --warmup 2 'nix eval --json -f foo.nix > /dev/null'
Benchmark 1: nix eval --json -f foo.nix > /dev/null
  Time (mean ± σ):      8.106 s ±  2.543 s    [User: 4.557 s, System: 0.573 s]
  Range (min … max):    5.147 s … 10.259 s    10 runs

Many small attrsets

Nixpkgs Version

let
  lib = (import <nixpkgs> {}).lib;
  data = map (i: {a = toString i; b = toString i;}) (lib.genList toString 1000000);
in
  map (lib.mapAttrsToList (k: v: {inherit k v;})) data
❯ hyperfine --warmup 2 'nix eval --json -f foo.nix > /dev/null'
Benchmark 1: nix eval --json -f foo.nix > /dev/null
  Time (mean ± σ):     10.229 s ±  0.100 s    [User: 4.961 s, System: 0.715 s]
  Range (min … max):   10.078 s … 10.459 s    10 runs

Your Version

let
  lib = (import <nixpkgs> {}).lib;
  data = map (i: {a = toString i; b = toString i;}) (lib.genList toString 1000000);
  mapAttrsToList = f: attrs: builtins.attrValues (builtins.mapAttrs f attrs);
in
  map (mapAttrsToList (k: v: {inherit k v;})) data
❯ hyperfine --warmup 2 'nix eval --json -f foo.nix > /dev/null'
Benchmark 1: nix eval --json -f foo.nix > /dev/null
  Time (mean ± σ):     10.050 s ±  0.639 s    [User: 4.657 s, System: 0.704 s]
  Range (min … max):    8.245 s … 10.388 s    10 runs

Hm, this shows higher variance but I’m not sure this is a conclusive benchmark. Maybe it really does one less lookup and the benchmark is just too small. To really be able to tell what is going on, someone who understands the Nix code base better than me should probably look into the implementation of mapAttrs, attrValues, and .${name}.

3 Likes

I created a Pull Request for this: https://github.com/NixOS/nixpkgs/pull/402855