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

references-by-popularity: get a handle on memory usage #56918

Merged
merged 2 commits into from Mar 6, 2019

Conversation

grahamc
Copy link
Member

@grahamc grahamc commented Mar 5, 2019

Motivation for this change

On very large graphs (~15k paths in this case) which have substantially sized subgraphs which are referred to many times, it is possible for the current code to OOM at the subgraph calculation phase:

image

This PR adds memoization to the subgraph calculation, allowing the algorithm to complete even on very large graphs within a reasonable time.

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 nox --run "nox-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.

On very large graphs (14k+ paths), we'd end up with a massive in
memory tree of mostly duplication.

We can safely cache trees and point back to them later, saving
memory.
@shlevy shlevy merged commit 5d3fd36 into NixOS:master Mar 6, 2019
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

3 participants