[RFC] Add fast path for strcoll and strcasecmp

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

Hi,

Now when I looked to strcoll improvement I recalled that strcoll(_l) and
strcasecmp could be made faster by following approach. We find first
position where strings differ and we will likely decide how they differ
by looking at few bytes. 

For that we need to do two things. First is to determine where character
containing differing byte starts. That is easy to do for single byte
encodings, UTF and prefix-free encodings in general. Then we need to
decide if decision can be made by characters alone. For that we need to
autogenerate new weigth table for each locale. It is basically primary
weigth table but ignored characters and characters that are part of
sequences get zero. If safe weigths are equal or one is zero then we
call original function.

A strcasecmp works in same way with appropriate collation table.

To determine performance gain I made a simple incorrect implementation
where I ignored calculating safe weigths. Another optimization is to use
strcmp_l optimized assembly which is easy to derive from strcmp by
returning index instead how these characters differ.

A sample implementation is here, comments?


#include <locale.h>
#include <xlocale.h>
#include <string.h>
#include <stdlib.h>

static size_t 
strcmp_l (const char *a, const char *b)
{
 size_t size = 0;
 while (a[size] != b[size] && a[size] != '\000')
   size++;
 return size;
}

char safe_characters[256];

int (*rewind_weigth_p)(const char *);


int rewind_weigth(const char *p)
{
  return safe_characters[(unsigned char) *p];
}

static void __attribute__ ((constructor)) init ()
{
  int i;
  rewind_weigth_p = rewind_weigth;
  for (i=0; i < 256; i++)
    safe_characters[i] = i + 1;
}


int strcoll (const char *a, const char *b)
{
  size_t dif = strcmp_l (a, b);

  if (a[dif] == '\000')
    return 0;

  int a_weigth = rewind_weigth_p (a + dif);

  int b_weigth = rewind_weigth_p (b + dif);

  if (a_weigth && b_weigth && a_weigth != b_weigth)
    return a_weigth - b_weigth;
  else
    return strcoll_l (a, b, newlocale (LC_ALL, setlocale(LC_ALL, NULL), (locale_t) 0));
}