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

[Alexander Monakov <amonakov@ispras.ru>]

On Tue, 10 May 2022, Noah Goldstein wrote:

> Unroll slightly and enforce good instruction scheduling. This improves
> performance on out-of-order machines. Note the unrolling allows
> for pipelined multiplies which helps a bit, but most of the gain
> is from enforcing better instruction scheduling for more ILP.
> Unrolling further started to induce slowdowns for sizes [0, 4]
> but can help the loop so if larger sizes are the target further
> unrolling can be beneficial.
> 
> Results for _dl_new_hash
> Benchmarked on Tigerlake: 11th Gen Intel(R) Core(TM) i7-1165G7 @ 2.80GHz

It seems benchmark figures are unchanged from the first iteration of this
patch, did the revision not affect them?

(more comments below)

> --- a/elf/dl-new-hash.h
> +++ b/elf/dl-new-hash.h
> @@ -20,15 +20,55 @@
>  #define _DL_NEW_HASH_H 1
>  
>  #include <stdint.h>
> +/* For __glibc_unlikely.  */
> +#include <sys/cdefs.h>
>  
>  static inline uint32_t
>  __attribute__ ((unused))
> -_dl_new_hash (const char *s)
> +_dl_new_hash (const char *signed_s)

This is technically inaccurate (whether plain 'char' is signed depends on the
target), so if you're revising this further I'd suggest to change this too to
e.g. 'str'.

>  {
> -  uint32_t h = 5381;
> -  for (unsigned char c = *s; c != '\0'; c = *++s)
> -    h = h * 33 + c;
> -  return h;

I think it would be nice to retain this loop as a comment to indicate what this
function is supposed to implement.

> +  const unsigned char *s = (const unsigned char *) signed_s;
> +  unsigned int h = 5381;
> +  unsigned int c0, c1;
> +  for (;;)
> +    {
> +      c0 = (unsigned int) *s;

Surprised to see an explicit cast where plain assignment with implicit type
conversion is doing the obvious thing. Is it really necessary?

> +      /* Unlikely length zero string so evens will be slightly less
> +	 common.  */

I had trouble understanding this comment. I'd suggest dropping it or rephrasing
like 'Since hashed string is normally not empty, this is unlikely on the first
iteration of the loop'.

> +      if (__glibc_unlikely (c0 == 0))
> +	{
> +	  return h;
> +	}

Braces look unnecessary.

> +
> +      c1 = (unsigned int) *(s + 1);

Again unnecessary explicit cast here (c1 = s[1] might be easier to read).
Alternatively, you could use 'c1 = *s++' here and above and drop explicit
s += 2 below, I expect resulting assembly to be the same.

> +      if (c1 == 0)
> +	{
> +	  c0 += h;
> +	  /* Ideal instruction scheduling is:
> +	     c0 += h;
> +	     h *= 32;
> +	     h += c0;
> +	     The asm statement ensures the compiler can't mess that up.  */

The main concern here is preventing reassociation from 'h = h*32 + (c0 + h)'
to 'h = (h*32 + h) + c0', not scheduling. We're using an empty asm to break
up a sequence of additions.

Also note that this leads to a return, so only saves a couple cycles once per
call, not inside the loop.

> +	  asm("" : "+r"(h) : "r"(c0));
> +	  h = h * 32 + c0;
> +      return h;

Wrong indentation here.

> +	}
> +
> +      /* Ideal instruction scheduling is:
> +	 c1 += c0;
> +	 h *= 33 * 33;
> +	 c0 *= 32;
> +	 c1 += c0;
> +	 h  += c1;
> +	 The asm statements ensures the compiler can't mess that up.  */

As above, we are placing empty asms mainly as reassociation barriers.

> +      c1 += c0;
> +      asm("" : "+r"(c1), "+r"(c0));
> +      h *= 33 * 33;
> +      c1 += c0 * 32;
> +      asm("" : "+r"(c1));
> +      h += c1;
> +      s += 2;
> +    }
>  }

Alexander