This is the mail archive of the
mailing list for the glibc project.
[RFC] Add fast path for strcoll and strcasecmp
- From: OndÅej BÃlka <neleai at seznam dot cz>
- To: libc-alpha at sourceware dot org
- Cc: leonhard dot holz at web dot de
- Date: Sun, 23 Nov 2014 22:47:18 +0100
- Subject: [RFC] Add fast path for strcoll and strcasecmp
- Authentication-results: sourceware.org; auth=none
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));