Re: [Patch, mips] Faster strcmp for mips

[OndÅej BÃlka <neleai at seznam dot cz>]

On Thu, Nov 14, 2013 at 01:23:41PM -0800, Steve Ellcey wrote:
> 
> I have created an optimized strcmp routine for MIPS and would like to check
> it in.  I verified it by running 'make check' and I also ran 'make bench'
> to check the performance.  This function is slightly slower then the current
> generic strcmp for strings that are not aligned, but much faster when strings
> are aligned because it will then load and compare either 2, 4, or 8 bytes at a
> time.
>
Problem is that aligned access could be only third of total calls. Also
around 90% calls need to check only first 16 bytes. These numbers differ
by application on x64 they are rule rather than exception. I collected
data of running gcc+gnuplot here:
http://kam.mff.cuni.cz/~ondra/benchmark_string/i7_ivy_bridge/strcmp_profile/results_gcc/result.html 

> This means it could be loading bytes beyond the end of the strings being
> compared but it looks like other architecture specific strcmp functions
> are also doing this optimization and the newlib version of strcmp also does
> this.
> 
Also unaligned case can be made faster with bit of extra effort.
How fast are unaligned loads on MIPS? They should be faster than
assembling value by shifts from two loads manualy which should be faster
than byte-by-byte checking.

What is most improtant for performance is handle first bytes quickly.
You need to check several alternatives, one is unroll checking of first
8-16 bytes. Second is to do a single vector check.

Then you need to implement a loop, what I did on x64 is align one
argument and load second as unaligned.

You need to precompute when a unaligned access would cross page boundary
and switch to byte-by-byte loop when that happens.

Here is modified code that I used to generate x64 implementation, I hope
it will be useful.

You need to change a TEST(a,b) to code that checks 8 bytes starting at a
and b. 

Also you may try to unroll these loops to do 16/32 bytes per iteration.

int
strcmp_new (char *a, char *b)
{
  int i;
  int or = (((unsigned long) a) | ((unsigned long) b)) & 4095;
  if (or <= 4096 - 8)
    {
      TEST (a, b);
    }
  else
    {
      for (i = 0; i < 8; i++)
	{
	  if (!a[i] || (a[i] - b[i]))
	    return a[i] - b[i];
	}
    }

  char *a_al = ALIGN_DOWN (a + 8, 8);
  int dif = a_al - a;
  a += dif;
  b += dif;
  unsigned long b_next = ((unsigned long) b) & (4096 - 1);
  unsigned long next_page = (4096 - b_next) / 8;

  while (1)
    {
      if (__builtin_expect (next_page-- == 0, 0))
	{
	  next_page = 4096 / 8;
	  next_page--;
	  for (i = 0; i < 8; i++)
	    {
	      if (!a[i] || (a[i] - b[i]))
		return a[i] - b[i];
	    }
	}
      TEST (a, b);
      a += 8;
      b += 8;
    }
}

Also here
> +  bx.v = x; by.v = y;
> +  if (bx.b.B0 - by.b.B0 != 0 || bx.b.B0 == 0)
> +    return bx.b.B0 - by.b.B0;
> +  if (bx.b.B1 - by.b.B1 != 0 || bx.b.B1 == 0)
> +    return bx.b.B1 - by.b.B1;
> +  if (bx.b.B2 - by.b.B2 != 0 || bx.b.B2 == 0)
> +    return bx.b.B2 - by.b.B2;
> +  if (bx.b.B3 - by.b.B3 != 0 || bx.b.B3 == 0)
> +    return bx.b.B3 - by.b.B3;
> +  if (bx.b.B4 - by.b.B4 != 0 || bx.b.B4 == 0)
> +    return bx.b.B4 - by.b.B4;
> +  if (bx.b.B5 - by.b.B5 != 0 || bx.b.B5 == 0)
> +    return bx.b.B5 - by.b.B5;
> +  if (bx.b.B6 - by.b.B6 != 0 || bx.b.B6 == 0)
> +    return bx.b.B6 - by.b.B6;
> +  return bx.b.B7 - by.b.B7;

There is alternative way to find answer without branching.
You need to compute a number that has nonzero i-th byte if i-th bytes of
x and y differ or they are 0. Then find first nonzero bit which can be
done quickly by CLZ instruction. 

This could be implemented as following

uint64_t bitmask = DETECTNULL8(x) | (x ^ y);
uint64_t bitfirst = bitmask ^ (bitmask - 1);
int pos = (ffsl(bitfirst) - 1) / 8;
return a[pos] - b[pos];