On Thu, Apr 25, 2013 at 08:04:01PM +0200, Thomas Rast wrote: > And probing lookups happen a lot: some simple instrumentation shows > that 'git rev-list --all --objects' on my git.git, > > * 19.4M objects are accessed in lookup_object and grow_object_hash > combined, while > > * the linear probing loops in lookup_object and insert_obj_hash run a > total of 9.4M times. > > So we take a slightly different approach, and trade some memory for > better cache locality. Namely, we change the hash table slots to > contain > > struct object *obj; > unsigned long sha1prefix; I think this is a clever idea, though I do worry about the extra memory use (it's not all _that_ much in the grand scheme, but it works against the cache locality benefit). I just posted (but forgot to cc you) a patch that takes a different approach: to actually move the likely candidate to the front of the collision change. The patch is here: http://article.gmane.org/gmane.comp.version-control.git/223139 It does a bit better than the numbers you have here: > I get a decent speedup, for example using git.git as a test > repository: > > Test before after > --------------------------------------------------------------------------------- > 0001.1: rev-list --all 0.42(0.40+0.01) 0.41(0.39+0.01) -1.5%** > 0001.2: rev-list --all --objects 2.40(2.37+0.03) 2.28(2.25+0.03) -5.0%*** > --------------------------------------------------------------------------------- > > And even more in linux.git: > > --------------------------------------------------------------------------------- > 0001.1: rev-list --all 3.31(3.19+0.12) 3.21(3.09+0.11) -2.9%** > 0001.2: rev-list --all --objects 27.99(27.70+0.26) 25.99(25.71+0.25) -7.1%*** > --------------------------------------------------------------------------------- It _might_ still be advantageous to do your patch on top, but I suspect it will diminish the returns from your patch (since the point of it is to probe less far down the chain on average). > I expected the big win to be in grow_object_hash(), but perf says that > 'git rev-list --all --objects' spends a whopping 33.6% of its time in > lookup_object(), and this change gets that down to 30.0%. I'm not surprised. I spent some time trying to optimize grow_object_hash and realized that it doesn't make much difference. The killer in "rev-list --objects --all" is that we hit the same tree entry objects over and over. Another avenue I'd like to explore is actually doing a tree-diff from the last processed commit, since we should need to examine only the changed entries. I suspect it won't be a big benefit, though, because even though the tree diff can happen in O(# of entries), we are trying to beat doing an O(1) hash for each entry. So it's the same algorithmic complexity, and it is hard to beat a few hashcmp() calls. We'll see. -Peff -- To unsubscribe from this list: send the line "unsubscribe git" in the body of a message to majordomo@xxxxxxxxxxxxxxx More majordomo info at http://vger.kernel.org/majordomo-info.html