Skip to content

treewide: fold -> foldr #110742

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
Merged
merged 1 commit into from
Jul 27, 2021
Merged

treewide: fold -> foldr #110742

merged 1 commit into from
Jul 27, 2021
+26 −26

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.

Sorry, something went wrong.

@ofborg ofborg bot added 6.topic: nixos Issues or PRs affecting NixOS modules, or package usability issues specific to NixOS 6.topic: TeX Issues regarding texlive and TeX in general 8.has: documentation This PR adds or changes documentation 8.has: module (update) This PR changes an existing module in `nixos/` labels Jan 25, 2021
SuperSandro2000
SuperSandro2000 reviewed Jan 25, 2021
View reviewed changes
@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

@ofborg ofborg bot added 10.rebuild-darwin: 0 This PR does not cause any packages to rebuild on Darwin 10.rebuild-linux: 0 This PR does not cause any packages to rebuild on Linux labels Jan 25, 2021
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.

@siraben
treewide: fold -> foldr

Verified

This commit was signed with the committer’s verified signature.
holymonson Monson Shao
GPG key ID: 163271C707982C65
Verified
Learn about vigilant mode
1c2a2b0
@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

@Profpatsch Profpatsch

@edolstra edolstra

@infinisil infinisil

@nbp nbp

@peti peti

Assignees
No one assigned
Labels
6.topic: nixos Issues or PRs affecting NixOS modules, or package usability issues specific to NixOS 6.topic: TeX Issues regarding texlive and TeX in general 8.has: documentation This PR adds or changes documentation 8.has: module (update) This PR changes an existing module in `nixos/` 10.rebuild-darwin: 0 This PR does not cause any packages to rebuild on Darwin 10.rebuild-linux: 0 This PR does not cause any packages to rebuild on Linux
Projects
None yet
Milestone
No milestone
Development

Successfully merging this pull request may close these issues.

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