strlen

1. strlen

1. strlen

1.1. faster strlen

正常的 strlen 需要针对每一个 byte 去 load & check null, 优化后版本大致是这样的:

#include <assert.h>
#include <stdio.h>
#include <string.h>
#include <sys/time.h>

/* 检测 int w 是否包含 `\0`, 例如 0xab00cdef */
unsigned int check_null(int w) {
    unsigned int mask = 0x7f7f7f7f;
    return ~(((w & mask) + mask) | mask);
}

int strlen_fast(char* start) {
    char* data = start;

    /* 跳过开头不对齐的部分, 因为 load word 时不对齐可能失败 (MIPS) 或性能下降
     * (x86, riscv) */
    while ((int)data & (sizeof(int) - 1)) {
        /* mis-aligned */
        if (*data == 0) {
            return data - start;
        }
        data++;
    }

    /* 以 word 为单位检查是否有 `\0`, 所以理论上有 4x 的性能提升 */
    while (!check_null(*((int*)(data)))) {
        data += 4;
    }

    /* 最后检查一下 `\0` 具体在 word 的哪个位置 */
    if (data[0] == 0) {
        return data - start;
    }
    if (data[1] == 0) {
        return data - start + 1;
    }
    if (data[2] == 0) {
        return data - start + 2;
    }
    if (data[3] == 0) {
        return data - start + 3;
    }
    /* unreachable */
}

int strlen_slow(char* start) {
    char* data = start;
    while (*(data++) != 0)
        ;
    return data - start - 1;
}

char* get_string(int n) {
    char ret[n + 1];
    memset(ret, 'a', n);
    ret[n] = 0;
    return strdup(ret);
}

#define timeit(prog)                                             \
    do {                                                         \
        struct timeval t1, t2;                                   \
        gettimeofday(&t1, 0);                                    \
        prog;                                                    \
        gettimeofday(&t2, 0);                                    \
        double elapsedTime = (t2.tv_sec - t1.tv_sec) * 1000.0 +  \
                             (t2.tv_usec - t1.tv_usec) / 1000.0; \
        printf("%f ms.\n", elapsedTime);                         \
    } while (0);

#define N 10000
int main(int argc, char* argv[]) {
    char* strings[N];
    for (int i = 0; i < N; i++) {
        strings[i] = get_string(i);
    }

    timeit(for (int i = 0; i < N; i++) { assert(strlen(strings[i]) == i); });

    timeit(
        for (int i = 0; i < N; i++) { assert(strlen_fast(strings[i]) == i); });

    timeit(
        for (int i = 0; i < N; i++) { assert(strlen_slow(strings[i]) == i); });
    return 0;
}

3.688000 ms.
8.572000 ms.
20.297000 ms.

1.2. check_null

check_null 用来检查一个 int 是否包含 0, 例如 0xab00cdef, 0x00abcdef 这种情况.

unsigned int check_null(int w) {
    unsigned int mask = 0x7f7f7f7f;
    return ~(((w & mask) + mask) | mask);
}

大致的思想是:

设置 mask 为 0x7f7f7f7f, 即每个 byte 为 b01111111, 最高位为 0.
假设 data 对应的某一个 byte 不是 0 (低 7 位包含 1)
计算 w = data & mask, 因为 data 包含 1, 所以 w 包含 1
计算 w = w + mask, 因为 w 低 7 位包含 1, 所以 w + mask 会产生进位, 导致 w 最高位变为 1
计算 w = ~(w|mask), 结果 w 为 0

所以 check_null 返回 0 表示一个 int 不包含 0

1.3. GCC O2 的一个 `bug`?

在实现上碰到一个问题:

当 check_null 中的类型使用 int (而不是 unsigned int) 时, 用 `-O2` 编译时, check_null 看起来被直接忽略掉了…

~~原因可能是: gcc 进行代码优化时认为 check_null 结果不可能是 0. 因为计算 int 加法~~ ~~`((w & mask) + mask)` 时,理论上结果不可能是负数, 即最高位不可能为 1, 所以 (((w &~~ ~~mask) + mask) | mask) 不可能全 1, 所以最终结果不可能为 0.~~

~~实际上, 涉及 bitwise 操作时, 最好用 unsigned.~~

这个问题的 root cause 参考 bitwise constant propagation

Backlinks

Retargeting GCC To RISC-V (Retargeting GCC To RISC-V > newlib/glibc > 某些可以优化的函数): - strlen

bitwise constant propagation (GCC Constant Propagation > bitwise constant propagation > example): 以 strlen 为例,