2.7 KiB
nixpkgs lib profiling
This is a repository for profiling nixpkgs lib functions. The goal is to create alternative implementations of functions that might have different time/space complexity characteristics, and measure if they are faster despite potential overhead.
I am personally especially interested in functions that rely on some type of fold
and accumulates a collection (either a list or an attrset). Because the lists and attrsets
will be reallocated on every iteration (this is only a suspicion, I have not verified this),
the time complexity of these functions might be O(n^2) while they really could've been O(n).
For functions like mergeAttrsList, this has been somewhat mitigated by folding with a binary
merge function, reducing the time complexity to O(n log n). But I'm hoping to find a more general
solution that could be applied to other functions as well, without too much overhead.
Some interesting builtins
| Name | Expected complexity | Comment |
|---|---|---|
hasAttr |
O(1) | this is the only real kind of lookup table we have with low overhead. I need to verify that it is actually amortized O(1) |
catAttrs |
O(n) | filter-like, [attrs] -> Attrs. Can remove many items at once, as well as convert from list to attrs |
concatMap |
O(n * f) | could this be used with attr lookups to fix the O(n^2) fold collection resizing problem? |
concatLists |
O(n) | could this be used with attr lookups to fix the O(n^2) fold collection resizing problem? |
foldl' |
O(n * f) | could be used to implement tail recursion |
filter |
O(n * f) | could potentially remove many items at once without realloc? |
genList |
O(n * f) | can seemingly allocate an arbitrarily sized list? |
intersectAttrs |
O(n log m) (known) | could be used as a shorthand for binary merge? |
listToAttrs |
O(n) | could potentially remove many items at once without realloc? |
partition |
O(n * f) | could potentially remove many items at once without realloc? |
genericClosure |
O(n * f) | We might be able to use this functions uniqueness checking for something, and then use catAttrs on the result |
evaluation speed measurement
For now, I'm using this:
# Alternatively drop NIX_COUNT_CALLS if too verbose
NIX_SHOW_STATS=1 NIX_COUNT_CALLS=1 nix eval .#sometest
Could alternatively create something with
nix eval --trace-function-calls .#sometest 2>function-trace.txt
source: https://discourse.nixos.org/t/nix-flamegraph-or-profiling-tool/33333