This repository was archived by the owner on Sep 11, 2020. It is now read-only.
This repository was archived by the owner on Sep 11, 2020. It is now read-only.
performance: difftree is sorting treeEntries but they might be already sorted #981
Open
Description
Rescuing this performance improvement proposal by @alcortesm:
A significant part of difftree execution time is spent in lexicographically sorting by name the treeEntries of every tree.
A couple of not very reliable sources mention treeEntries are already sorted lexicographically in every git tree.
If this is true, the performance of difftree can be improved by removing the sorting of the treeEntries.
- confirm that treeEntries are already lexicographically sorted in every tree
- confirm this has always been the case, this is, all valid packfiles have their entries sorted, no matter how old they are.
- add the sort assumption to noder.Children
- add the sorting code to fsnoder implementation
- remove the sorting code from difftree