Re: [PATCH 1/2] obj_hash: convert to a critbit tree

On Wed, Sep 14, 2016 at 05:52:06PM -0700, Stefan Beller wrote: > > So finding "1011" involves traversing the trie: down the "1" > > side, then the "0" side, and then check that the rest > > matches "11". > > So we stop building a tree as soon as we hit a unique data > element (i.e. if we stick

Re: [PATCH 1/2] obj_hash: convert to a critbit tree

On Wed, Sep 14, 2016 at 4:56 PM, Jeff King wrote: > For operations that traverse the whole reachability graph, > like "rev-list --objects", the obj_hash in object.c shows up > as a hotspot. We basically have to do "nr_commits * > size_of_tree" hash lookups, because each tree we

[PATCH 1/2] obj_hash: convert to a critbit tree

For operations that traverse the whole reachability graph, like "rev-list --objects", the obj_hash in object.c shows up as a hotspot. We basically have to do "nr_commits * size_of_tree" hash lookups, because each tree we look at, we need to say "have we seen this sha1 yet?" (it's a little more