You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
We currently have a vector as the data backing for the index' entries. This makes looking up an entry O(n) over the amount of entries, which can grow large. Using a hash table would allow us to do this in amortized O(1) time.
We would still need to have a sorted vector of entries for some operations, but we may be able to get away with generating that one on the fly rather than update it on each operation. There is a PR #1169 which did this for an older version of the structure, so we can't take it as-is.
We have a data structure git_sortedcache which is currently used by the refdb code but was made so we could use it for the index as well. We should rewrite that PR with the sorted cache as backing store.
The text was updated successfully, but these errors were encountered:
We currently have a vector as the data backing for the index' entries. This makes looking up an entry O(n) over the amount of entries, which can grow large. Using a hash table would allow us to do this in amortized O(1) time.
We would still need to have a sorted vector of entries for some operations, but we may be able to get away with generating that one on the fly rather than update it on each operation. There is a PR #1169 which did this for an older version of the structure, so we can't take it as-is.
We have a data structure
git_sortedcache
which is currently used by the refdb code but was made so we could use it for the index as well. We should rewrite that PR with the sorted cache as backing store.The text was updated successfully, but these errors were encountered: