This is the mail archive of the
mailing list for the glibc project.
Re: [RFC] Add fast path for strcoll and strcasecmp
- From: Leonhard Holz <leonhard dot holz at web dot de>
- To: libc-alpha at sourceware dot org
- Date: Sun, 23 Nov 2014 23:52:06 +0100
- Subject: Re: [RFC] Add fast path for strcoll and strcasecmp
- Authentication-results: sourceware.org; auth=none
- References: <20141123214718 dot GA28222 at domone>
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
Am 23.11.2014 22:47, schrieb OndÅej BÃlka:
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?
strcmp_l (const char *a, const char *b)
size_t size = 0;
while (a[size] != b[size] && a[size] != '\000')
int (*rewind_weigth_p)(const char *);
int rewind_weigth(const char *p)
return safe_characters[(unsigned char) *p];
static void __attribute__ ((constructor)) init ()
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')
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;
return strcoll_l (a, b, newlocale (LC_ALL, setlocale(LC_ALL, NULL), (locale_t) 0));