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.

Sign up for GitHub

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

Jump to bottom

treewide: fold -> foldr #110742

Merged
merged 1 commit into from Jul 27, 2021
Merged

treewide: fold -> foldr #110742

merged 1 commit into from Jul 27, 2021

Conversation

siraben
Copy link
Member

@siraben siraben commented Jan 25, 2021

Motivation for this change

@Profpatsch continue with the deprecation?

Things done
  • Tested using sandboxing (nix.useSandbox on NixOS, or option sandbox in nix.conf on non-NixOS linux)
  • 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 nixpkgs-review --run "nixpkgs-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)
  • Ensured that relevant documentation is up to date
  • Fits CONTRIBUTING.md.

SuperSandro2000
SuperSandro2000 reviewed Jan 25, 2021
View reviewed changes
lib/tests/misc.nix Outdated Show resolved Hide resolved
@siraben siraben force-pushed the deprecate-fold branch 2 times, most recently from cd79904 to ae9107a Compare January 25, 2021 08:40
@SuperSandro2000
Copy link
Member

I think you missed a file and ofborg complains about that.

@Profpatsch
Copy link
Member

The question here is whether foldr is the right use anyway. Usually you really want foldl', always, if you intend to use the result(s) of the fold.

@Profpatsch
Copy link
Member

foldr is only useful if you depend on the laziness property, and idk how much that even applies in nix, since lists are forcing their elements to whnf.

@siraben
Copy link
Member Author

siraben commented Jan 25, 2021

Ok so should I go through my changes and make them foldl' when the function is associative and the element an identity element? e.g.

-    fold and true (attrValues (zipAttrsWithNames (attrNames pattern) (n: values:
+    foldr and true (attrValues (zipAttrsWithNames (attrNames pattern) (n: values:

might as well be

-    fold and true (attrValues (zipAttrsWithNames (attrNames pattern) (n: values:
+    foldl' and true (attrValues (zipAttrsWithNames (attrNames pattern) (n: values:

@Profpatsch
Copy link
Member

foldl' and true

I’d argue that should use lib.all instead.

@siraben
Copy link
Member Author

siraben commented Jan 25, 2021

foldl' and true

I’d argue that should use lib.all instead.

Looks like we need an hlint equivalent for Nix! 😆

@Profpatsch
Copy link
Member

but anyway, the refactor shouldn’t introduce any behaviour changes

Profpatsch
Profpatsch approved these changes Jan 25, 2021
View reviewed changes
Copy link
Member

@Profpatsch Profpatsch left a comment

Choose a reason for hiding this comment

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

LGTM

Next up, somebody should go through uses of foldr to check whether we can gain memory or speed savings by using foldl' instead.

@Profpatsch
Copy link
Member

cc @infinisil @grahamc there might be easy memory/speed gains here

SuperSandro2000
SuperSandro2000 reviewed Jan 25, 2021
View reviewed changes
lib/default.nix Outdated
@@ -79,7 +79,7 @@ let
recursiveUpdate matchAttrs overrideExisting getOutput getBin
getLib getDev getMan chooseDevOutputs zipWithNames zip
recurseIntoAttrs dontRecurseIntoAttrs;
inherit (self.lists) singleton forEach foldr fold foldl foldl' imap0 imap1
inherit (self.lists) singleton forEach fold foldr foldl foldl' imap0 imap1
Copy link
Member

Choose a reason for hiding this comment

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

Is this supposed to just change the position of foldr?

Copy link
Member Author

Choose a reason for hiding this comment

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

Ah, good catch, I'll revert this.

@tomberek
Copy link
Contributor

tomberek commented Mar 3, 2021

running: NIX_SHOW_STATS=1 time nix-instantiate nixos/release-combined.nix -A nixos.tests.misc.x86_64-linux --dry-run

before 
{
  "cpuTime": 4.4831,
  "envs": {
    "number": 8040823,
    "elements": 9909621,
    "bytes": 207930136
  },
  "list": {
    "elements": 5932327,
    "bytes": 47458616,
    "concats": 193616
  },
  "values": {
    "number": 12971839,
    "bytes": 311324136
  },
  "symbols": {
    "number": 118285,
    "bytes": 4366233
  },
  "sets": {
    "number": 1158225,
    "bytes": 305840304,
    "elements": 12357271
  },
  "sizes": {
    "Env": 16,
    "Value": 24,
    "Bindings": 8,
    "Attr": 24
  },
  "nrOpUpdates": 441021,
  "nrOpUpdateValuesCopied": 8904098,
  "nrThunks": 8005723,
  "nrAvoided": 10451397,
  "nrLookups": 3357854,
  "nrPrimOpCalls": 4350366,
  "nrFunctionCalls": 7254051,
  "gc": {
    "heapSize": 621469696,
    "totalBytes": 1090436352
  }
}
after 
{
  "cpuTime": 4.45351,
  "envs": {
    "number": 8032348,
    "elements": 9892932,
    "bytes": 207661024
  },
  "list": {
    "elements": 5927432,
    "bytes": 47419456,
    "concats": 192848
  },
  "values": {
    "number": 12930424,
    "bytes": 310330176
  },
  "symbols": {
    "number": 118268,
    "bytes": 4429547
  },
  "sets": {
    "number": 1155028,
    "bytes": 300472592,
    "elements": 12134682
  },
  "sizes": {
    "Env": 16,
    "Value": 24,
    "Bindings": 8,
    "Attr": 24
  },
  "nrOpUpdates": 439018,
  "nrOpUpdateValuesCopied": 8709175,
  "nrThunks": 7971489,
  "nrAvoided": 10436936,
  "nrLookups": 3348099,
  "nrPrimOpCalls": 4344621,
  "nrFunctionCalls": 7246543,
  "gc": {
    "heapSize": 604692480,
    "totalBytes": 1083838032
  }
}

Most of the numbers improve <1%, and heapSize is reduced ~3%.

@siraben
Copy link
Member Author

siraben commented Mar 3, 2021

@tomberek that seems as expected, since the only gain here is saving the indirection from fold to foldr (as fold = foldr; in lists.nix).

What might be reasonable is going through the replacements and seeing where things definitely would be equivalent under foldl (that is, when the binary operation and the initial element form a monoid).

@siraben
Copy link
Member Author

siraben commented Mar 3, 2021

Next up, somebody should go through uses of foldr to check whether we can gain memory or speed savings by using foldl' instead.

perhaps should be done in a separate PR as suggested by @Profpatsch

@siraben siraben merged commit b63a54f into NixOS:master Jul 27, 2021
@siraben siraben deleted the deprecate-fold branch July 27, 2021 08:13
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Reviewers

@SuperSandro2000 SuperSandro2000 SuperSandro2000 left review comments

@Profpatsch Profpatsch Profpatsch approved these changes

@edolstra edolstra Awaiting requested review from edolstra

@infinisil infinisil Awaiting requested review from infinisil infinisil is a code owner

@nbp nbp Awaiting requested review from nbp

@peti peti Awaiting requested review from peti peti is a code owner

Assignees
No one assigned
Labels
6.topic: nixos 6.topic: TeX Issues regarding texlive and TeX in general 8.has: documentation 8.has: module (update) 10.rebuild-darwin: 0 10.rebuild-linux: 0
Projects
None yet
Milestone
No milestone
Development

Successfully merging this pull request may close these issues.

None yet
4 participants
@siraben @SuperSandro2000 @Profpatsch @tomberek