####
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