On 23.11.2015 23:14, William A Rowe Jr wrote: > L1 cache and other direct effects of cpu internal optimization. Just what I was thinking. Attached is the same program with one more pair of functions added (and an easy way to add more "candidates" to the main-driver). I changed the FOR-loop define to obtain repeatable results:
# Test 1 -- equal strings: foreach m ( 0 1 2 ) foreach? ./strncasecmp $m 100000000 aaaaaaaaa AAAAAAAAA 7 foreach? end string.h (nb=100000000, len=7) time = 6.975845 : res = 0 optimized (nb=100000000, len=7) time = 1.492197 : res = 0 'A' - 'a' (nb=100000000, len=7) time = 1.787807 : res = 0 # Test 2 -- immediately-different strings foreach m ( 0 1 2 ) foreach? ./strncasecmp $m 100000000 aaaaaaaaa xAAAAAAAA 7 foreach? end string.h (nb=100000000, len=7) time = 2.527727 : res = -23 optimized (nb=100000000, len=7) time = 0.406867 : res = -23 'A' - 'a' (nb=100000000, len=7) time = 0.440320 : res = -23 # Test 3 -- strings different at the very end foreach m ( 0 1 2 ) foreach? ./strncasecmp $m 100000000 aaaaaaaaa AAAAAAAAx 0 foreach? end string.h (nb=100000000, len=0) time = 9.629660 : res = -23 optimized (nb=100000000, len=0) time = 1.387208 : res = -23 'A' - 'a' (nb=100000000, len=0) time = 1.754683 : res = -23 The new pair (method 2) does not use the static table, which is likely to benefit from CPU-cache unfairly in repetitive benchmarks. It is slower than the table-using method 1 functions. But the two pairs might be comparable -- or even faster -- in real life. -mi
#include <sys/types.h> #include <sys/time.h> #include <sys/resource.h> #define gettimeofday(X) gettimeofday(X, NULL) #include <stdint.h> #include <stdio.h> #include <stdlib.h> #include <string.h> #include <sysexits.h> #include <limits.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_strcasecmp(const char *s1, const char *s2) { const unsigned char *ps1 = (const unsigned char *) s1; const unsigned char *ps2 = (const unsigned char *) s2; while (*ps1 == *ps2 || ucharmap[*ps1] == ucharmap[*ps2]) { if (*ps1 == '\0') { return (0); } ++ps1; ++ps2; } return (ucharmap[*ps1] - ucharmap[*ps2]); } int ap_strncasecmp(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 (*ps1 == *ps2 || ucharmap[*ps1] != ucharmap[*ps2]) { return (ucharmap[*ps1] - ucharmap[*ps2]); } if (*ps1 == '\0') { break; } ++ps1; ++ps2; } return (0); } int mi_strcasecmp(const char *s1, const char *s2) { const unsigned char *ps1 = (const unsigned char *) s1; const unsigned char *ps2 = (const unsigned char *) s2; for (;;) { int diff = *ps1 - *ps2; switch (diff) { case 0: break; case 'A' - 'a': if (*ps1 <= 'Z' && *ps1 >= 'A') break; return 1; case 'a' - 'A': if (*ps2 <= 'Z' && *ps2 >= 'A') break; return -1; default: /* Do, what tolower() would've done */ if (*ps1 <= 'z' && *ps1 >= 'a') diff -= ('a' - 'A'); if (*ps2 <= 'z' && *ps2 >= 'a') diff += ('a' - 'A'); return diff; } if (*ps1 == '\0') { break; } ++ps1; ++ps2; } return (0); } int mi_strncasecmp(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--) { int diff = *ps1 - *ps2; switch (diff) { case 0: break; case 'A' - 'a': if (*ps1 <= 'Z' && *ps1 >= 'A') break; return 1; case 'a' - 'A': if (*ps2 <= 'Z' && *ps2 >= 'A') break; return -1; default: /* Do, what tolower() would've done */ if (*ps1 <= 'z' && *ps1 >= 'a') diff -= ('a' - 'A'); if (*ps2 <= 'z' && *ps2 >= 'a') diff += ('a' - 'A'); return diff; } if (*ps1 == '\0') { break; } ++ps1; ++ps2; } 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++) int main(int argc, char *argv[]) { int64_t diff; struct rusage rus, rue; int i, len, nb, method; int res = 0; struct { const char *label; int (*cmp)(const char *, const char *); int (*ncmp)(const char *, const char *, size_t); } methods[] = { { "string.h", strcasecmp, strncasecmp }, { "optimized", ap_strcasecmp, ap_strncasecmp }, { "'A' - 'a'", mi_strcasecmp, mi_strncasecmp } }; if (argc < 6) { fprintf(stderr, "%s <0=std ; 1=optimized> <nb iter> S1 S2 <nb char to compare or 0>\n", PROG); return EX_USAGE; } len = atoi(LEN); nb = atoi(NB); method = atoi(METHOD); if (method < 0 || method >= sizeof(methods)/sizeof(methods[0])) { fprintf(stderr, "Invalid method requested (``%s''?)\n", METHOD); return EX_USAGE; } printf("%s (nb=%d, len=%d)\n", methods[method].label, nb, len); getrusage(RUSAGE_SELF, &rus); if (len == 0) { FOR { res |= methods[method].cmp(S1, S2); } } else { FOR { res |= methods[method].ncmp(S1, S2, len); } } getrusage(RUSAGE_SELF, &rue); diff = (int64_t)rue.ru_utime.tv_sec * 1000000L + rue.ru_utime.tv_usec; diff -= (int64_t)rus.ru_utime.tv_sec * 1000000L + rus.ru_utime.tv_usec; /* really use the result of the function */ printf("time = %lld.%.6lld : res = %d\n", (long long)diff / 1000000L, (long long)diff % 1000000L, res); return 0; }