nixpkgs-lib-profiling/README.md

# 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