这个更快的 `strlen` 有多危险？

Question

这个更快的 `strlen` 有多危险？

11

strlen是一个相当简单的函数，很明显计算的时间复杂度为O(n)。但是，我见过一些处理多个字符的方法。请参考这里的示例5或这里的方法。这些方法的基本原理是通过将char const*缓冲区重新解释为uint32_t const*缓冲区，然后每次检查四个字节。

就我个人而言，我的直觉是这是一种等待段错误发生的情况，因为我可能会引用有效内存之外的三个字节。但是，这种解决方案似乎一直存在，并且对我来说很奇怪，为什么如此明显存在问题的东西经过了时间的考验还能存在。

我认为这包含了两个UB：

潜在的在有效内存之外引用
潜在的未对齐指针引用

(_{^{请注意，这里不存在别名问题；有人可能认为uint32_t被假定为与不兼容类型的别名，并且在strlen之后运行的代码（例如可能更改字符串的代码）可能会按顺序运行，但事实证明char是严格别名的明确例外}}）。

但是，在实践中失败的可能性有多大？最少需要在字符串文字数据部分之后有3字节填充，malloc需要4字节或更大的对齐（实际上在大多数系统上都是这样），并且malloc需要分配3个额外的字节。还有与别名相关的其他标准。这对于编译器实现来说非常好，因为它们创建自己的环境，但是现代硬件上用户代码有多频繁地符合这些条件？

- imallett

似乎这没什么问题（但我会相信库函数；或者尽可能避免使用strlen()函数） - wildplasser

请记住，未定义行为仍然可以由实现进行定义。 - user253751

1

顺便提一下：看看libc实现。它们并不简单（就像这个）并且会处理平台之间的差异。另外：进行一些代码分析。如果strlen()是限制因素，那么你正在做一些错误的事情，以我个人的意见。 - wildplasser

我不认为任何一种4字节的strlen()方法会更快。首先，据我所知，test和cmp是任何架构中最昂贵的操作之一，而且你没有在它们上面省一点。你还添加了很多不是特别必要的操作，只是为了一次性复制4个字节的内存到一个本地变量中，这也是完全没有意义的。请记住，L1和L2缓存都参与其中，所以这并不像你从某些慢速媒体缓冲字符串一样。 - Havenard

1

@Havenard：您可以将展开的情况下的测试组合起来。例如，第一个源使用#define hasNulByte(x) ((x - 0x01010101) & ~x & 0x80808080)在uint32_t上，这相当于第二个示例中更加暴力的方式。 - geometrian

1

有一件事情你可以做得比任何你能想到的strlen()实现更快。你只需要简单地跟踪你的字符串长度即可。 - Havenard

4个回答

3

(1) 这种情况确实可能发生。没有什么能阻止你在已分配页面的末尾附近对一个字符串进行 strlen，这可能会导致访问超出已分配内存的末尾并造成程序崩溃。正如你所指出的，这可以通过填充所有的分配来缓解，但是这样做需要任何库都做同样的事情。更糟糕的是，你必须安排链接器和操作系统始终添加这个填充（记住操作系统在某个静态内存缓冲区中传递 argv[]）。这样做的开销不值得。

(2) 这种情况也确实会发生。早期版本的 ARM 处理器在非对齐访问时生成数据异常，这会导致程序因总线错误而死亡（或者如果你运行裸机，则停止 CPU），或者强制通过内核处理非对齐访问的非常昂贵的陷阱。这些早期的 ARM 芯片仍然广泛用于较旧的手机和嵌入式设备中。后期的 ARM 处理器合成多字访问以处理非对齐访问，但这将导致整体性能变慢，因为你基本上要加倍执行所需的内存加载。

许多当前（“现代”）的 PIC 和嵌入式微处理器缺乏处理非对齐访问的逻辑，当给定非对齐地址时可能会表现出不可预测甚至荒谬的行为（我个人见过一些芯片只会屏蔽底部位，这将产生错误的结果，还有一些芯片在进行非对齐访问时将只提供垃圾结果）。

因此，在任何应该具有可移植性的情况下使用这种代码都是极其危险的。请，请不要使用这段代码；使用 libc 中的 strlen。它通常会更快（针对你的平台进行了优化），并且会使你的代码具有可移植性。你最不想看到的是你的代码在某些情况下（接近分配末尾的字符串）或某些新处理器上突然而意外地出现问题。

- nneonneo

虽然我同意没有负责任的程序员会想使用这样的东西，但我怀疑称其为“极其危险”可能有些夸张。 - Steve Summit

我不同意。一个带有一系列不寻常限制的函数（如对齐输入，不能太靠近分配的末尾），并且在某些平台上可能会默默地崩溃，这正是“荒谬危险”的定义。当然，速度很好，通常也是必要的，但如果你追求速度，至少使用汇编语言，这样你的代码就不具备可移植性，这是显而易见的。 - nneonneo

1

更不用说在某些平台上，未对齐的访问惩罚非常严重，以至于这段代码可能比朴素方法慢得多！ - nneonneo

1

一些平台在软件中处理未对齐的访问（例如ARM9）。我没有进行基准测试，但如果它不比朴素解决方案慢得多，我会非常惊讶。 - Iskar Jarak

@nneonneo：我并不是在为这种技术辩护，但我敢打赌，即使在高负载的生产代码中使用它数年，也不会导致崩溃，所以它不符合我对“极其危险”的定义——但我仍然不建议使用！（未对齐的输入惩罚也不是问题，因为“快速strlen”代码可以检查它并在字边界上同步自己，尽管启动速度较慢，这将破坏大多数短字符串的性能。） - Steve Summit

1

唐纳德·克努斯(Donald Knuth)是一位编写了3卷巧妙算法的人，他说：“过早优化是万恶之源”。

strlen()被广泛使用，因此它应该快速。根据wildplasser的评论，“我会相信库函数”，你为什么认为库函数按字节工作？或者很慢吗？

标题可能让人们觉得你建议的代码比标准系统库strlen()更快，但我认为你的意思是它比天真的strlen()更快，不过这种方式可能并没有被使用。

我编译了一个简单的C程序，并在我的64位系统上查看了使用GNU的glibc函数。我看到的代码非常复杂，从寄存器宽度而不是每次一个字节的角度来看，看起来非常快。我看到的strlen()代码是用汇编语言编写的，所以如果这是编译后的C代码，可能就会有垃圾指令。我看到的是rtld-strlen.S。这段代码还展开了循环，以减少循环中的开销。

在认为你可以更好地完成strlen之前，你应该查看那段代码，或者针对你特定的架构和寄存器大小查看相应的代码。

如果你确实编写了自己的strlen，请将其与现有实现进行基准测试。

显然，如果使用系统提供的strlen，则它很可能是正确的，你不必担心由于代码优化而导致的无效内存引用。

- rocky

我喜欢你指出标准实现并不像OP所假设的那样朴素，而是通过检查编译的汇编代码提供证据。 - Patrick Roberts

0

我同意这是一种不太优美的技术，但我认为它大部分时间都能正常工作。只有当字符串恰好位于数据（或堆栈）段的末尾时才会出现段错误。绝大多数字符串（无论是静态分配还是动态分配）都不会出现这种情况。

但你说得对，要保证它正常工作，你需要确保所有字符串都以某种方式填充，并且你列出的垫片清单看起来很合适。

如果对齐是一个问题，你可以在快速strlen实现中解决这个问题；你不必四处奔波地尝试对齐所有字符串。

（但当然，如果你的问题是你花费了太多时间扫描字符串，正确的解决方法不是拼命尝试使字符串扫描更快，而是通过调整事物使你不必首先扫描那么多字符串...）

- Steve Summit

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Kaz · Accepted Answer

这种技术是有效的，如果您调用我们的C库strlen，则无法避免使用它。例如，如果该库是GNU C库的最新版本（至少对于某些目标），它将执行相同的操作。

使其正常工作的关键是确保指针对齐。如果指针对齐，则操作肯定会读取字符串结尾之外的内容，但不会读取相邻页面的内容。如果空终止字节在页面结束的一字之内，则最后一个字将被访问而不会触及随后的页面。

这在C中显然不是定义良好的行为，因此在从一个编译器移植到另一个编译器时需要进行仔细的验证。这也会触发超出边界访问检测器（如Valgrind）的误报。

为了解决Glibc的问题，必须对Valgrind进行修补。如果没有这些修补程序，您将获得诸如以下烦扰错误：

==13669== Invalid read of size 8
==13669==    at 0x411D6D7: __wcslen_sse2 (wcslen-sse2.S:59)
==13669==    by 0x806923F: length_str (lib.c:2410)
==13669==    by 0x807E61A: string_out_put_string (stream.c:997)
==13669==    by 0x8075853: obj_pprint (lib.c:7103)
==13669==    by 0x8084318: vformat (stream.c:2033)
==13669==    by 0x8081599: format (stream.c:2100)
==13669==    by 0x408F4D2: (below main) (libc-start.c:226)
==13669==  Address 0x43bcaf8 is 56 bytes inside a block of size 60 alloc'd
==13669==    at 0x402BE68: malloc (in /usr/lib/valgrind/vgpreload_memcheck-x86-linux.so)
==13669==    by 0x8063C4F: chk_malloc (lib.c:1763)
==13669==    by 0x806CD79: sub_str (lib.c:2653)
==13669==    by 0x804A7E2: sysroot_helper (txr.c:233)
==13669==    by 0x408F4D2: (below main) (libc-start.c:226)

Glibc使用SSE指令以8字节为一组计算（而不是的宽度4字节）。

这样做，它会在60字节的块中访问偏移量为56的位置。然而，请注意，此访问永远不会跨越页面边界：该地址可被8整除。

如果您使用汇编语言，您无需对这种技术再三考虑。

实际上，在我所使用的一些优化音频编解码器（针对ARM）中，该技术被广泛使用，并且具有许多手写的汇编语言与Neon指令集。

当我在集成这些编解码器的代码上运行Valgrind时，我注意到了这一点，并联系了供应商。他们解释说这只是一个无害的循环优化技巧；我研究了汇编语言并确信他们是正确的。