快速 strlen 函数与别名规则

Question

我发现 this "fast strlen function" 实现：

// for x86 only
size_t my_strlen(const char *s) {
    size_t len = 0;
    for(;;) {
        unsigned x = *(unsigned*)s;
        if((x & 0xFF) == 0) return len;
        if((x & 0xFF00) == 0) return len + 1;
        if((x & 0xFF0000) == 0) return len + 2;
        if((x & 0xFF000000) == 0) return len + 3;
        s += 4, len += 4;
    }
}

此处使用的优化技术显然很简单：通过自然 CPU 字读取内存（代码较旧并假定 x32 CPU），而不是简单的字节。

但此代码违反了别名规则，因此导致未定义的行为，编译器可以自由优化这些行为（使代码更快，但不正确）。

我现在也看到它不可移植，因为它与小端字节序有关。

或者我完全错了，上面的代码是正确的？ C 是否正确？对于 C++？

Answer 1

这是个坏主意，会让你的表现更差。现代编译器提供的标准 strlen 函数已经高度优化，并且会比上面的更好。例如，在支持 SSE 的 CPU 上（即几乎所有的 CPU），它已经使用 SSE/AVX 指令对空终止符进行矢量化搜索，并且会像上面那样一次考虑超过 4 个字节，而更少与比较相关的指令，以及更少的可能被错误预测的分支。

Answer 2

这是非常糟糕的代码。甚至代码的作者也警告说：

如果不可读的内存页位于字符串末尾之后，此函数将崩溃。 防止这种情况的最简单方法是在字符串末尾分配 3 个额外的字节。
双字可能未对齐，但 x86 架构允许访问未对齐的数据。对于小字符串，对齐比未对齐读取的惩罚花费更多时间。
代码不可移植：如果您使用64位处理器，您将不得不添加另外4个条件。对于大端架构，条件的顺序应该颠倒。

即使这没有违反别名规则，但让编码人员完成 my_strlen 工作的负担是完全不合理的。已经多次声明 strlen 已经超越了普通编码人员可以完成的任何事情。

但是对于 C++ 应该做一个额外的声明：Bjarne Stroustrup, the creator of C++, in the last page of chapter 4 in his book："The C++ Programming Language" 说：

Prefer strings over C-style strings

您会发现获取 string 的大小比查找 C 字符串的大小更高效。

编辑：

在 you say you are working with StaticallyBufferedString 中旨在解决 string 的 "pooling memory model" 导致：

多线程上下文中不必要的堆锁
来自实时大小控制的碎片

我想推荐 C++17 的 string_view which like all of C++17 was constructed with multi-threading in mind. It provides the functionality of a string backed by heap and constexpr friendly C-Strings. You can even get a jump start on learning about it with namespace experimental: http://en.cppreference.com/w/cpp/experimental/basic_string_view 与您花在 StaticallyBufferedStrings 上的时间不同，您获得的知识将完全可移植并适用于您将来所做的任何 C++ 工作！

Answer 3

所写的功能既不是最优的也不是可移植的。话虽如此，C89 的作者包含了一些写得不好的规则，如果严格解释这些规则，C89 将成为比许多平台上存在的早期 C 方言更不强大的语言。该规则的既定目的是避免要求 C 编译器给出如下代码：

float *fp;
int i;

int foo(void)
{
  i++;
  *fp=1.0f;
  return i;
}

不必悲观地假设写入 *fp 可能会影响 i 尽管完全没有任何迹象表明 int 类型的东西可能会影响受到影响。在编写 C89 时，出于各种目的（包括分块优化）使用类型双关的代码很普遍，但大多数此类代码都会向编译器明确指示将要发生别名。通常，如果一个对象将在两次 "normal" 访问之间被外部类型指针修改，则在两次正常访问之间将发生以下一种或两种情况：

对象的地址将被占用。
指针将从对象的类型转换为另一种类型。

除了使用指针访问对象的明显情况它的精确类型，该标准主要确定它不会的情况很明显编译器应该假定别名是可能的（例如在一个 "int" 和一个 "unsigned*" 类型的指针，或者介于任何东西和指针之间 "char*" 类型）。鉴于理由，我认为作者打算专注于确保编译器编写者处理存在的情况没有理由期待别名，但认为他们不需要讲述了如何识别明显可能发生的情况。

分块优化在编译器上是安全的 address-of 和 casting 运算符暗示可能存在跨类型别名，前提是执行转换产生的指针的所有使用在使用非强制转换指针进行下一次访问之前——大多数人的要求分块代码通常会满足。不幸的是，没有标准对于 "sane-compiler C"，而 gcc 使用的事实是标准不要求编译器处理明显的别名情况忽略它们的理由。

不过，分块优化带来的性能优势可能会超过 -fno-strict-aliasing 的性能成本，特别是如果代码使用 restrict 适当的限定符。有几种情况，主要是涉及全局变量，其中 restrict 不足以启用有用的优化；这些可以通过限制的别名模式来处理分析静态或自动持续时间的对象（如基本原理的例子）但是 gcc 没有提供这样的模式。

顺便说一句，我不确定现代 x86 处理器的指令时序如何，但在某些 ARM 变体上，编译器有机会从类似以下内容生成最佳长字符串代码：

uint32_t x01000000 = 0x01000000;
uint64_t *search(uint64_t *p)
{
  uint64_t n;
  uint32_t a,b;
  uint32_t v = x01000000; // See note
  do
  {
    n=*p++;
    a=(uint32_t)n;
    b=n>>32;
    if (a >= v  || (a << 8) >= v || (a << 16) >= v || (a << 24) >= v ||
        b >= v  || (b << 8) >= v || (b << 16) >= v || (b << 24) >= v) return p;
  } while(1);      
}

找出哪个比较导致循环跳出会花费额外的时间，但将此类考虑因素排除在循环之外可能会使循环本身更有效率。

许多 ARM 处理器都有一条指令可以将移位后的值与寄存器进行比较；编译器有时需要一点帮助才能意识到 0x01000000 应该保存在寄存器中（存在与常量比较的指令，但是不包括被比较的寄存器的 "free" 移位），但在帮助下他们可以找到与移位比较。我还没有找到说服编译器为 ARM7-TDMI 生成最佳代码的方法，这相当于：

search:
    mov    r1,#0x010000000
lp:
    ldrmia r0,{r2,r3}
    cmp    r1,r2
    cmplt  r1,r2,asl #8
    cmplt  r1,r2,asl #16
    cmplt  r1,r2,asl #24
    cmplt  r1,r3
    cmplt  r1,r3,asl #8
    cmplt  r1,r3,asl #16
    cmplt  r1,r3,asl #24
    blt    lp
    bx     lr

每八个字节需要 15 个周期；它可以调整为每 16 个字节需要 25 个周期。一个单独处理八个字节的循环需要 42 个周期；展开为 16 个字节将是 82 个周期。我见过编译器为基于 uint64_t 的代码生成的最佳循环是 22 个循环，用于 8 个字节——几乎是最佳代码的一半，但仍然是使用字节的版本的两倍。

快速 strlen 函数与别名规则

Fast strlen function vs aliasing rules

c

c++

type-conversion

strict-aliasing

strlen