[RFC] Add fast path for strcoll and strcasecmp

[Leonhard Holz]

Hi Ondřej,

as far as I understood, the current strcoll implementation scans both 
strings for collation sequences and compares the weights of them, 
whereby a collation sequence can be multiple bytes long. So whatever 
strcmp_l returns as index, you would need a general way of finding the 
start of the collation sequence this index is in. Unfortunately I cannot 
tell if or how this can be done.

BTW I have implemented a benchmark for strcoll that is not-yet-pushed 
because I didn't manage to patch the bench-tests Makefile to generate 
additionally needed locales 
(https://sourceware.org/ml/libc-alpha/2014-10/msg00431.html).

Leonhard

Am 23.11.2014 22:47, schrieb Ondřej Bílka:
> 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));
> }
>