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.