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

[Noah Goldstein <goldstein.w.n@gmail.com>]

On Thu, May 5, 2022 at 10:26 AM Alexander Monakov <amonakov@ispras.ru> wrote:
>
> 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:

Oh wow. Must have 'looked at it' before it reloaded.
I'm sorry!
>
> .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.
>
Okay that makes sense and indeed results in a substantial improvement.

Totally happy with going with your version.

Think there is still some benefit to the unrolled version because

1) It's less eager about hitting the LSD on newer processors
(but that's really only an issue for strings > ~24 characters).

2) It bottlenecks less hard on `p6` because the `imul` goes `p0`
and the branches are distributed between `p0` and `p6` instead of
always on `p6`.

3) It still saves a few uops (although imul vs `add + shl` isn't really
a meaningful save).

Either way it will be an improvement.

Little benchmark: https://godbolt.org/z/G6PvW4eTr

Generally see hash2 winning the most.

> Alexander