Show 38 quoted lines
> * Jonathan Nieder <jrnieder@gmail.com> wrote:
>
> > Hi,
> >
> > A side note for amusement.
> >
> > Erik Faye-Lund wrote:
> >
> > > --- a/cache.h
> > > +++ b/cache.h
> > > @@ -681,13 +681,17 @@ extern char *sha1_pack_name(const unsigned char *sha1);
> > > extern char *sha1_pack_index_name(const unsigned char *sha1);
> > > extern const char *find_unique_abbrev(const unsigned char *sha1, int);
> > > extern const unsigned char null_sha1[20];
> > > -static inline int is_null_sha1(const unsigned char *sha1)
> > > +static inline int hashcmp(const unsigned char *sha1, const unsigned char *sha2)
> > > {
> > > - return !memcmp(sha1, null_sha1, 20);
> > > + /* early out for fast mis-match */
> > > + if (*sha1 != *sha2)
> > > + return *sha1 - *sha2;
> > > +
> > > + return memcmp(sha1 + 1, sha2 + 1, 19);
> > > }
> >
> > On the off-chance that sha1 and sha2 are nicely aligned, a more
> > redundant
> >
> > if (*sha1 != *sha2)
> > return *sha1 - *sha2;
> >
> > return memcmp(sha1, sha2, 20);
> >
> > would take advantage of that (yes, this is just superstition, but it
> > somehow seems comforting anyway).
>
> Your variant also makes the code slightly more compact as the sha1+1 and sha2+1
> addresses do not have to be computed. I'll re-test and resend this variant.Seems to perform measurably worse:
#
# Open-coded loop:
#
Performance counter stats for './git gc' (10 runs):
2358.560100 task-clock # 0.763 CPUs utilized ( +- 0.06% )
1,870 context-switches # 0.001 M/sec ( +- 3.09% )
170 CPU-migrations # 0.000 M/sec ( +- 3.54% )
38,230 page-faults # 0.016 M/sec ( +- 0.03% )
7,513,529,543 cycles # 3.186 GHz ( +- 0.06% )
1,634,103,128 stalled-cycles # 21.75% of all cycles are idle ( +- 0.28% )
11,068,971,207 instructions # 1.47 insns per cycle
# 0.15 stalled cycles per insn ( +- 0.04% )
2,487,656,519 branches # 1054.735 M/sec ( +- 0.03% )
59,233,604 branch-misses # 2.38% of all branches ( +- 0.09% ) 3.092183093 seconds time elapsed ( +- 3.49% )
#
# Front test + memcmp:
#
Performance counter stats for './git gc' (10 runs):
2723.468639 task-clock # 0.833 CPUs utilized ( +- 0.22% )
1,751 context-switches # 0.001 M/sec ( +- 2.02% )
167 CPU-migrations # 0.000 M/sec ( +- 1.23% )
38,230 page-faults # 0.014 M/sec ( +- 0.03% )
8,684,682,538 cycles # 3.189 GHz ( +- 0.21% )
2,062,906,208 stalled-cycles # 23.75% of all cycles are idle ( +- 0.60% )
9,019,624,641 instructions # 1.04 insns per cycle
# 0.23 stalled cycles per insn ( +- 0.04% )
1,771,179,402 branches # 650.340 M/sec ( +- 0.04% )
75,026,810 branch-misses # 4.24% of all branches ( +- 0.04% ) 3.271415104 seconds time elapsed ( +- 1.97% )
So i think the open-coded loop variant i posted is faster.
The key observation is that there's two cases that matter to performance:
- the hashes are different: in this case the front test catches 99% of the cases
- the hashes are *equal*: in this case the open-coded loop performs better than the memcmp
My patch addresses both cases.
Thanks,
Ingo