Re: [PATCH v3 6/6] elf: Optimize _dl_new_hash in dl-new-hash.h

[Alexander Monakov <amonakov@ispras.ru>]

On Thu, 5 May 2022, Noah Goldstein wrote:

> > The following variant of the original loop avoids those issues and
> > should run close to 2 cycles per iteration on most CPUs:
> >
> > static uint32_t
> > _dl_new_hash (const char *s)
> > {
> >   uint32_t h = 5381, c;
> >   const unsigned char *us = (const void *)s;
> >   while ((c = *us++))
> >     {
> >       c += h;
> >       asm("" : "+r"(h) : "r"(c));
> >       h = h * 32 + c;
> >     }
> >   return h;
> > }
> >
> 
> I'm not sure what you are getting at with the asm(). It seems the
> produce the exact
> same assembly:
> https://godbolt.org/z/93qGMaTTE

They are definitely not the same even via your link. Loop body of dl_new_hash0:

.L3:
(a)	addl    %eax, %edx
	addq    $1, %rcx
(b)	sall    $5, %eax
(c)	addl    %edx, %eax
	movzbl  -1(%rcx), %edx
	testl   %edx, %edx
	jne     .L3

and of dl_new_hash1:

.L9:
(A)	movl    %r8d, %eax
	addq    $1, %rcx
(B)	sall    $5, %eax
(C)	addl    %edx, %eax
	movzbl  -1(%rcx), %edx
(D)	addl    %eax, %r8d
	testl   %edx, %edx
	jne     .L9

(in fact even the instruction count is not the same, 7 vs 8)

In the first loop, (a) and (b) are independent, (c) depends on them both, and
on the next iteration (a) and (b) take the result of (c) from the previous. Thus
the dependencies are 2 cycles for one iteration.

In the second loop, (B) depends on (A), (C) depends on (B), (D) depends on (C),
and on the next iteration (A) depends on (D) from the previous. Thus four
instructions form a dependency chain of 3 or 4 cycles depending if move
elimination happens or not.

In any case, if you benchmark them both you should see the difference.

Alexander