Complexity
Overview
Conventions:
- O(foo + bar) - likely most expensive first; but we include bar anyway because it’s not systematic
- fs - size of files in the pristine repository
- fn - number of files in the pristine repository
- ms, ns - size of patches in various repos
- m, n - number patches in various repos
| complexity | notes | |
|---|---|---|
| lazy fetching repo | O(fs + fn) | fetch just the pristine files packs will bring this down to O(fs) |
| fetching repo | O(ns + n + fs + fn) | fetch each patch file separately too packs will bring this down to O(ns + fs) |
| getting ready for darcs pull | TODO | |
| diffing working and recorded | TODO | |
| basic merging without conflicts | O(m n) | commute m patches on one side past n on other [merging] |
| minimal context | O(n^2) | given patches (X1..XN P), any X_n patch you commute out has to go through X_n+m that P depends on [min-context] |
| conflicts | TODO |
Notes
- fetching: fs and ns matter because of time to copy a file, fn and n matter because of latency
- min-context: http://lists.osuosl.org/pipermail/darcs-users/2012-March/026406.html