Repository navigation
git_submodule_lookup is O(N) w.r.t. number of submodules #3756
Description
causing many operations, such as git_rebase_init (which results in calls to git_submodule_lookup several times for each submodule) to be O(N^2).
On a 3.1Ghz MBP with SSD, for example, a single call to git_submodule_lookup in a repository with 4,000 submodules takes over 20ms.
I am very happy to work on this myself and submit a patch, but I wanted to open a discussion and get advice on how to proceed. One suggestion: allow an option to configure a repository to cache this information on first submodule access.
Activity
bpeabody commentedon Apr 26, 2016
Also,
git_submodule_statusis very slow as it updates the submodules head status every time; this method is called several times for each submodule during, e.g. agit_rebase_init.bpeabody commentedon Apr 26, 2016
Also, the
all_submodulesfunction insubmodules.cis itself O(N^2) as it searches the.gitmodulesentries, linearly, for each submodule.bpeabody commentedon Apr 26, 2016
I have a preliminary patch I am working on (pending permission from my employer) that adds:
git_submodule_cache_allandgit_submodule_clear_cachemethods that when called causegit_submodule_lookupto return values from a cache that loads once in O(N) time.git_submodule_statusskips updating submodule head/index state.all_submodulesso that a single map of names is loaded in O(N) time from the.gitmodulesfile.bpeabody commentedon Apr 26, 2016
The changes make
git_rebase_inittake around 250ms on my laptop, down from about 3 minutes, for a repo with 4,000 submodules. I can upload this sample repo if anyone wants to play with it.carlosmn commentedon Apr 27, 2016
The submodule code does assume you're going to be using just a few. I'm not sure about adding a brand new cache, but one thing that we can do to avoid parsing the file multiple times is keep a
git_configin the repository to represent the.gitmodulesfile and take a snapshot of that inopen_gitmodules()(or initialize that the first time). The read part of the config code can already avoid parsing a file if its contents haven't changed. It would read in the contents of the file to determine that it hasn't changed, but it would keep the already-parsed version in memory when creating the snapshots.bpeabody commentedon Apr 27, 2016
I can see how the brand new submodule cache might not be the most desirable fix. The solution you're proposing with
.gitmodulescaching sounds better, but it's still going to leave most operations too slow for me.Beyond the O(N^2) issue with the
.gitmodulesfile, bothgit_submodule_statusand (I think)git_submodule_lookupare bottlenecked ongit_repository_head_tree, which takes close to a millisecond; when it's called several times per submodule duringgit_rebase_init, it can be a big performance hit.I think, more philosophically, I am also generally assuming that you will only have a few submodules open at any given time. If you have 4,000 submodules checked out locally, I think it's reasonable for
git_rebaseto be a little slow (though I would still expect the time to scale linearly). Maybe a better solution (in addition to the caching of the data in.gitmodules) would be to optimize the behavior some functions to be more efficient in dealing with submodules that aren't checked out, such asgit_submodule_status,git_submodule_lookup.bpeabody commentedon Apr 27, 2016
many-submodules.tar.gz
If you want to play around with a repo having lots of submodules, I've uploaded one here with about 4,000. You can see that just the
git_rebase_initofmasterontofootakes minutes right now, even though no submodules are actually checked out and the rebase is a fast-forward.ethomson commentedon May 26, 2016
@bpeabody You mentioned that you were waiting on permission from your employer, is this something that they granted? Is this a project you are still tackling?
bpeabody commentedon May 26, 2016
Yes, I have permission to contribute, and even better, the project I'm using this for has been approved and officially open-sourced: https://github.com/twosigma/git-meta.
I hope to get back to this issue next week and contribute an initial patch along the lines of the suggestion from @carlosmn; I don't think that will be entirely sufficient but it will be a good start and we can work from there.
bpeabody commentedon May 26, 2016
By "not entirely sufficient", I mean that the suggestion will address the O(N) issue, but that there would still remain prohibitively high constant factors associated with opening submodules.