Skip to content

Instantly share code, notes, and snippets.

@JackyYin
Last active March 9, 2022 08:05
Show Gist options
  • Save JackyYin/1227d6df4ea979f25b34ad247a38ce10 to your computer and use it in GitHub Desktop.
Save JackyYin/1227d6df4ea979f25b34ad247a38ce10 to your computer and use it in GitHub Desktop.
Simple test for faster strlen implementation
#include <stdint.h>
#include <stddef.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
size_t strlen_simple(const char *str)
{
size_t i = 0;
while (str[i] != '\0') {
i++;
}
return i;
}
size_t strlen_check_8(const char *str)
{
// we want to make sure addr is in a 8 bytes boundary
const char *cstr;
for (cstr = str; ((uintptr_t)cstr & 7) != 0; cstr++) {
if (*cstr == '\0')
return cstr - str;
}
size_t len = cstr - str;
uint64_t n;
while (1) {
n = *((uint64_t *)&str[len]);
if ((n - 0x0101010101010101) & (~n) & 0x8080808080808080)
break;
len += 8;
}
/*
* check against NULL-termination position
* only available in little-endian machine
* */
/* if ((n & 0xff) == 0x00) */
/* return len; */
/* else if (((n >> 8) & 0xff) == 0x00) */
/* return len + 1; */
/* else if (((n >> 16) & 0xff) == 0x00) */
/* return len + 2; */
/* else if (((n >> 24) & 0xff) == 0x00) */
/* return len + 3; */
/* else if (((n >> 32) & 0xff) == 0x00) */
/* return len + 4; */
/* else if (((n >> 40) & 0xff) == 0x00) */
/* return len + 5; */
/* else if (((n >> 48) & 0xff) == 0x00) */
/* return len + 6; */
/* else if (((n >> 56) & 0xff) == 0x00) */
/* return len + 7; */
str = &str[len];
if (str[0] == '\0')
return len;
if (str[1] == '\0')
return len + 1;
if (str[2] == '\0')
return len + 2;
if (str[3] == '\0')
return len + 3;
if (str[4] == '\0')
return len + 4;
if (str[5] == '\0')
return len + 5;
if (str[6] == '\0')
return len + 6;
if (str[7] == '\0')
return len + 7;
}
int main(int argc, char **argv) {
char str[] = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa bbbbbbbbbbbbbbbbbbbbbb";
if (argc < 2) {
fprintf(stderr, "must provide fp ID 1 ~ 3\n");
exit(2);
}
size_t (*fp)(const char *);
switch (argv[1][0]) {
case '1':
fp = &strlen;
break;
case '2':
fp = &strlen_check_8;
break;
case '3':
fp = &strlen_simple;
break;
}
for (int i = 0; i < 0xfffffff; i++) {
fp(str);
}
}
@JackyYin
Copy link
Author

JackyYin commented Mar 8, 2022

Test environment:
Linux jackyyin-MacBookPro 5.13.0-30-generic #33~20.04.1-Ubuntu SMP Mon Feb 7 14:25:10 UTC 2022 x86_64 x86_64 x86_64 GNU/Linux

compile under O0:
./test 1 0.76s user 0.00s system 99% cpu 0.761 total
./test 2 8.38s user 0.00s system 99% cpu 8.383 total
./test 3 79.59s user 0.00s system 99% cpu 1:19.60 total

compile under O3:
./test 1 0.63s user 0.00s system 99% cpu 0.634 total
./test 2 3.61s user 0.00s system 99% cpu 3.607 total
./test 3 18.55s user 0.00s system 99% cpu 18.565 total

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment