Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

lib: improve the implementation of the unique function #59369

Merged
merged 1 commit into from Apr 15, 2019

Conversation

Ekleog
Copy link
Member

@Ekleog Ekleog commented Apr 12, 2019

Motivation for this change

http://gsc.io/graph.unstable.svg

Things done
  • Tested using sandboxing (nix.useSandbox on NixOS, or option sandbox in nix.conf on non-NixOS)
  • Built on platform(s)
    • NixOS
    • macOS
    • other Linux distributions
  • Tested via one or more NixOS test(s) if existing and applicable for the change (look inside nixos/tests)
  • Tested compilation of all pkgs that depend on this change using nix-shell -p nix-review --run "nix-review wip"
  • Tested execution of all binary files (usually in ./result/bin/)
  • Determined the impact on package closure size (by running nix path-info -S before and after)
  • Assured whether relevant documentation is up to date
  • Fits CONTRIBUTING.md.

@grahamc
Copy link
Member

grahamc commented Apr 12, 2019

stat before after Δ Δ%
cpuTime 135.2 132.897 🡖 2.303 -1.70%
envs-bytes 3,563,057,008 3,417,282,480 🡖 145,774,528 -4.09%
envs-elements 183,953,876 177,627,124 🡖 6,326,752 -3.44%
envs-number 130,714,125 124,766,593 🡖 5,947,532 -4.55%
gc-heapSize 12,104,687,616 11,433,721,856 🡖 670,965,760 -5.54%
gc-totalBytes 24,191,819,392 23,468,008,832 🡖 723,810,560 -2.99%
list-bytes 1,659,372,128 1,635,598,944 🡖 23,773,184 -1.43%
list-concats 7,194,150 6,988,658 🡖 205,492 -2.86%
list-elements 207,421,516 204,449,868 🡖 2,971,648 -1.43%
nrAvoided 177,840,681 170,493,166 🡖 7,347,515 -4.13%
nrFunctionCalls 115,193,164 109,822,957 🡖 5,370,207 -4.66%
nrLookups 75,292,052 75,275,349 🡖 16,703 -0.02%
nrOpUpdateValuesCopied 208,834,564 208,814,478 🡖 20,086 -0.01%
nrOpUpdates 11,883,339 11,881,928 🡖 1,411 -0.01%
nrPrimOpCalls 85,571,252 80,373,629 🡖 5,197,623 -6.07%
nrThunks 173,325,665 167,655,588 🡖 5,670,077 -3.27%
sets-bytes 7,134,676,648 7,133,945,368 🡖 731,280 -0.01%
sets-elements 288,174,680 288,145,266 🡖 29,414 -0.01%
sets-number 27,310,541 27,307,373 🡖 3,168 -0.01%
sizes-Attr 24 24 0
sizes-Bindings 8 8 0
sizes-Env 16 16 0
sizes-Value 24 24 0
symbols-bytes 16,324,262 16,324,250 🡖 12 -0.00%
symbols-number 372,918 372,917 🡖 1 -0.00%
values-bytes 6,250,904,880 5,869,027,296 🡖 381,877,584 -6.11%
values-number 260,454,370 244,542,804 🡖 15,911,566 -6.11%

@grahamc
Copy link
Member

grahamc commented Apr 12, 2019

@NeQuissimus
Copy link
Member

Nice!

@edolstra
Copy link
Member

The real question about unique is: why does it exist at all? The previous incarnation of this function (uniqueList) was moved to the lib/deprecated.nix ghetto exactly because we don't want people to use O(n^2) functions in Nixpkgs...

Copy link
Member

@lheckemann lheckemann left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Change LGTM, but as @edolstra says maybe we don't want this function at all… So I'm going to have a look at where it's used.

  • lib/types.nix: merging enum types. Could probably be left out, at the cost of making enum type checks more expensive in probably rare cases?
  • pkgs/top-level/python-packages.nix: in requiredPythonModules, which seems to be a rather odd way of computing a closure on python package dependencies. Used transitively in lots of places maybe?
  • pkgs/top-level/lua-packages.nix: in requiredLuaModules which seems to be a copy-paste of the python thing.
  • nixos/modules/tasks/network-interfaces.nix: for something I don't quite understand (what's the difference between a WLAN interface and a WLAN device?)
  • pkgs/build-support/fetchdocker/default.nix: getting each layer only once or something? This could probably be moved to build time?
  • pkgs/misc/vim-plugins/vim-utils.nix: computing the transitive dependency closure of a plugin
  • pkgs/games/factorio/utils.nix: more transitive dependency closure stuff
  • pkgs/stdenv/generic/make-derivation.nix: for impure host deps
  • pkgs/development/java-modules/build-maven-package.nix: looks like more transitive dependency closure stuff
  • pkgs/development/beam-modules/build-rebar3.nix: removing duplicates from propagatedBuildInputs
  • nixos/modules/services/networking/firewall.nix: for normalising lists of ports. In this case it's sorted as well so the uniqueness check could be simplified.
  • nixos/modules/services/x11/gdk-pixbuf.nix: unique-ing the packages to generate a loader cache for. Could be done with sorting and moved to build time AFAICT.
  • nixos/modules/tasks/filesystems/zfs.nix: getting the list of pools without duplicates from the list of filesystems. Generates some bash code directly from these. Could maybe be moved to build time, but it's a bit more complicated since these values are used in multiple places.
  • nixos/modules/services/hardware/udev.nix: removing duplicates for udev packages for making the combined udev rule package. Could probably be moved to build time cheaply.
  • nixos/modules/services/misc/mesos-slave.nix: could be moved into a build-time or runtime script.
  • pkgs/build-support/rust/build-rust-crate/default.nix: dependency closure stuff
  • pkgs/servers/sip/freeswitch/default.nix: buildInputs uniqueness. Not necessary I think?
  • pkgs/applications/video/kodi/plugins.nix: dependency closure stuff
  • pkgs/tools/networking/envoy/default.nix: getting multiple relevant outputs of some package but not the same one multiple times
  • pkgs/applications/networking/cluster/terraform/default.nix: dependency closure stuff
  • pkgs/applications/science/math/sage/sage-with-env.nix: dependency closure stuff

I may have overlooked one or two cases. I'm also not sure how useful this list is… But hey, at least we have it now :p

@grahamc
Copy link
Member

grahamc commented Apr 14, 2019

@GrahamcOfBorg eval

@edolstra edolstra merged commit 9f5ba91 into NixOS:master Apr 15, 2019
@grahamc grahamc mentioned this pull request Apr 24, 2019
10 tasks
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

Successfully merging this pull request may close these issues.

None yet

6 participants