I did some testing with different implémentations and my results show
that fastest one is:
int ap_casecmpstr_2(const char *s1, const char *s2)
{
size_t i;
const unsigned char *ps1 = (const unsigned char *) s1;
const unsigned char *ps2 = (const unsigned char *) s2;
for (i = 0; ; ++i) {
const int c1 = ps1[i];
const int c2 = ps2[i];
if (c1 != c2) {
return c1 - c2;
}
if (!c1) {
break;
}
}
return (0);
}
int ap_casecmpstrn_2(const char *s1, const char *s2, size_t n)
{
size_t i;
const unsigned char *ps1 = (const unsigned char *) s1;
const unsigned char *ps2 = (const unsigned char *) s2;
for (i = 0; i < n; ++i) {
const int c1 = ps1[i];
const int c2 = ps2[i];
if (c1 != c2) {
return c1 - c2;
}
if (!c1) {
break;
}
}
return (0);
}
Some samples (test program attached):
$ gcc -Wall -O2 newtest.c -o newtest -lrt
$ for i in `seq 0 2`; do
./newtest $i 150000000 \
xcxcxcxcxcxcxcxcxcxcwwwwwwwwwwaaaaaaaaaa \
xcxcxcxcxcxcxcxcxcxcwwwwwwwwwwaaaaaaaaaa \
0
done
- str[n]casecmp (nb=150000000, len=0)
time = 8.444547186 : res = 0
- ap_casecmpstr[n] (nb=150000000, len=0)
time = 8.299781468 : res = 0
- ap_casecmpstr[n] w/ index (nb=150000000, len=0)
time = 6.148787259 : res = 0
That's ~30% better.
$ gcc -Wall -Os newtest.c -o newtest -lrt
$ for i in `seq 0 2`; do
./newtest $i 150000000 \
xcxcxcxcxcxcxcxcxcxcwwwwwwwwwwaaaaaaaaaa \
xcxcxcxcxcxcxcxcxcxcwwwwwwwwwwaaaaaaaaaa \
0
done
- str[n]casecmp (nb=150000000, len=0)
time = 8.528311136 : res = 0
- ap_casecmpstr[n] (nb=150000000, len=0)
time = 10.150553381 : res = 0
- ap_casecmpstr[n] w/ index (nb=150000000, len=0)
time = 9.758638566 : res = 0
The string.h's str[n]casecmp beat us with -Os, still this new
implementation is better than the current one.
WDYT, should I commit these new versions?
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#include <time.h>
/*
* Provide our own known-fast implementation of str[n]casecmp()
* NOTE: ASCII only!
*/
static const unsigned char ucharmap[] = {
0x0, 0x1, 0x2, 0x3, 0x4, 0x5, 0x6, 0x7,
0x8, 0x9, 0xa, 0xb, 0xc, 0xd, 0xe, 0xf,
0x10, 0x11, 0x12, 0x13, 0x14, 0x15, 0x16, 0x17,
0x18, 0x19, 0x1a, 0x1b, 0x1c, 0x1d, 0x1e, 0x1f,
0x20, 0x21, 0x22, 0x23, 0x24, 0x25, 0x26, 0x27,
0x28, 0x29, 0x2a, 0x2b, 0x2c, 0x2d, 0x2e, 0x2f,
0x30, 0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 0x37,
0x38, 0x39, 0x3a, 0x3b, 0x3c, 0x3d, 0x3e, 0x3f,
0x40, 'a', 'b', 'c', 'd', 'e', 'f', 'g',
'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o',
'p', 'q', 'r', 's', 't', 'u', 'v', 'w',
'x', 'y', 'z', 0x5b, 0x5c, 0x5d, 0x5e, 0x5f,
0x60, 'a', 'b', 'c', 'd', 'e', 'f', 'g',
'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o',
'p', 'q', 'r', 's', 't', 'u', 'v', 'w',
'x', 'y', 'z', 0x7b, 0x7c, 0x7d, 0x7e, 0x7f,
0x80, 0x81, 0x82, 0x83, 0x84, 0x85, 0x86, 0x87,
0x88, 0x89, 0x8a, 0x8b, 0x8c, 0x8d, 0x8e, 0x8f,
0x90, 0x91, 0x92, 0x93, 0x94, 0x95, 0x96, 0x97,
0x98, 0x99, 0x9a, 0x9b, 0x9c, 0x9d, 0x9e, 0x9f,
0xa0, 0xa1, 0xa2, 0xa3, 0xa4, 0xa5, 0xa6, 0xa7,
0xa8, 0xa9, 0xaa, 0xab, 0xac, 0xad, 0xae, 0xaf,
0xb0, 0xb1, 0xb2, 0xb3, 0xb4, 0xb5, 0xb6, 0xb7,
0xb8, 0xb9, 0xba, 0xbb, 0xbc, 0xbd, 0xbe, 0xbf,
0xc0, 0xc1, 0xc2, 0xc3, 0xc4, 0xc5, 0xc6, 0xc7,
0xc8, 0xc9, 0xca, 0xcb, 0xcc, 0xcd, 0xce, 0xcf,
0xd0, 0xd1, 0xd2, 0xd3, 0xd4, 0xd5, 0xd6, 0xd7,
0xd8, 0xd9, 0xda, 0xdb, 0xdc, 0xdd, 0xde, 0xdf,
0xe0, 0xe1, 0xe2, 0xe3, 0xe4, 0xe5, 0xe6, 0xe7,
0xe8, 0xe9, 0xea, 0xeb, 0xec, 0xed, 0xee, 0xef,
0xf0, 0xf1, 0xf2, 0xf3, 0xf4, 0xf5, 0xf6, 0xf7,
0xf8, 0xf9, 0xfa, 0xfb, 0xfc, 0xfd, 0xfe, 0xff
};
int ap_casecmpstr(const char *s1, const char *s2)
{
const unsigned char *ps1 = (const unsigned char *) s1;
const unsigned char *ps2 = (const unsigned char *) s2;
while (ucharmap[*ps1] == ucharmap[*ps2++]) {
if (*ps1++ == '\0') {
return (0);
}
}
return (ucharmap[*ps1] - ucharmap[*--ps2]);
}
int ap_casecmpstrn(const char *s1, const char *s2, size_t n)
{
const unsigned char *ps1 = (const unsigned char *) s1;
const unsigned char *ps2 = (const unsigned char *) s2;
while (n--) {
if (ucharmap[*ps1] != ucharmap[*ps2++]) {
return (ucharmap[*ps1] - ucharmap[*--ps2]);
}
if (*ps1++ == '\0') {
break;
}
}
return (0);
}
int ap_casecmpstr_2(const char *s1, const char *s2)
{
size_t i;
const unsigned char *ps1 = (const unsigned char *) s1;
const unsigned char *ps2 = (const unsigned char *) s2;
for (i = 0; ; ++i) {
const int c1 = ps1[i];
const int c2 = ps2[i];
if (c1 != c2) {
return c1 - c2;
}
if (!c1) {
break;
}
}
return (0);
}
int ap_casecmpstrn_2(const char *s1, const char *s2, size_t n)
{
size_t i;
const unsigned char *ps1 = (const unsigned char *) s1;
const unsigned char *ps2 = (const unsigned char *) s2;
for (i = 0; i < n; ++i) {
const int c1 = ps1[i];
const int c2 = ps2[i];
if (c1 != c2) {
return c1 - c2;
}
if (!c1) {
break;
}
}
return (0);
}
#define PROG argv[0]
#define METHOD argv[1]
#define NB argv[2]
#define S1 argv[3]
#define S2 argv[4]
#define LEN argv[5]
/* The ++ are here to try to prevent some optimization done by gcc */
#define FOR for (i=0; i<nb; i++, (S1[0])++, (S2[0])++)
int main(int argc, char *argv[])
{
int64_t diff;
struct timespec tvs, tve;
int i, len, nb;
int res = 0;
if (argc < 6) {
printf("%s <0=std ; 1=optimized> <nb iter> S1 S2 <nb char to compare or 0>\n", PROG);
return 0;
}
len = atoi(LEN);
nb = atoi(NB);
if (*METHOD == '0') {
printf("- str[n]casecmp (nb=%d, len=%d)\n", nb, len);
clock_gettime(CLOCK_MONOTONIC, &tvs);
if (len == 0) {
FOR {
/* really use the result of the function */
res |= strcasecmp(S1, S2);
}
}
else {
FOR {
res |= strncasecmp(S1, S2, len);
}
}
clock_gettime(CLOCK_MONOTONIC, &tve);
}
else if (*METHOD == '1') {
printf("- ap_casecmpstr[n] (nb=%d, len=%d)\n", nb, len);
clock_gettime(CLOCK_MONOTONIC, &tvs);
if (len == 0) {
FOR {
res |= ap_casecmpstr(S1, S2);
}
}
else {
FOR {
res |= ap_casecmpstrn(S1, S2, len);
}
}
clock_gettime(CLOCK_MONOTONIC, &tve);
}
else if (*METHOD == '2') {
printf("- ap_casecmpstr[n] w/ index (nb=%d, len=%d)\n", nb, len);
clock_gettime(CLOCK_MONOTONIC, &tvs);
if (len == 0) {
FOR {
res |= ap_casecmpstr_2(S1, S2);
}
}
else {
FOR {
res |= ap_casecmpstrn_2(S1, S2, len);
}
}
clock_gettime(CLOCK_MONOTONIC, &tve);
}
diff = (int64_t)tve.tv_sec * 1000000000L + tve.tv_nsec;
diff -= (int64_t)tvs.tv_sec * 1000000000L + tvs.tv_nsec;
/* really use the result of the function */
printf("time = %lld.%.6lld : res = %d\n",
(long long)diff / 1000000000L,
(long long)diff % 1000000000L,
res);
return 0;
}
