c - C中memset函数的复杂性

Question

我和一些朋友讨论了一段代码，我们讨论了在 C 中使用 memset 函数，如果我们初始化一个大小为 N 的数组，这个函数的 Big-O 表示法的顺序是什么？

Answer 1

在您可以直接访问页表并且它们以分层方式存储的系统上，memset可以O(log n)通过将整个虚拟地址映射替换为对填充给定字节值的单个页面的写时复制引用来实现. 但是请注意，如果您将来要对对象进行任何修改，则正常O(n)成本memset将推迟到页面错误，以便在修改页面时实例化页面的单独副本。

Answer 2

您询问了复杂性，但您可能打算询问性能。

复杂性，用符号 O(n) 表示，是一个与算法中的操作数量如何随着问题规模的增长而增长有关的概念。O(n) 意味着必须执行一些与输入大小成比例的步骤。它没有说这个比例是多少。memset 是 O(n)。O(n ² ) 意味着必须执行与 n ²成比例的一些步骤。memset 不是 O(n ² )，因为设置 2n 字节所需的工作量仅为 n 字节的两倍，而不是一般工作量的四倍。

您可能对 memset 的性能更感兴趣，因为 memset 的库版本的执行速度比您可能编写的 C 版本快得多。

库版本执行得更快，因为它使用专门的指令。大多数常见的现代处理器都有指令，允许它们在一条指令中将 16 个字节写入内存。库实现者用汇编语言或类似语言编写了 memset 之类的关键函数，因此他们可以访问所有这些指令。

当你用 C 语言编写时，编译器很难利用这些指令。例如，指向您正在设置的内存的指针可能未与 16 字节的倍数对齐。memset 作者将编写测试指针的代码，并针对每种情况分支到不同的代码，目标是单独设置一些字节，然后使指针对齐，这样他们就可以使用存储 16 字节的快速指令时间。这只是库实现者在编写 memset 之类的例程时要处理的许多复杂问题之一。

由于这些复杂性，编译器不能轻易地将 memset 的 C 实现转化为专家编写的快速代码。当编译器在 C 代码中看到一次写入一个字节的循环时，它通常会生成一次写入一个字节的汇编语言。优化器变得越来越聪明，但复杂性限制了他们被允许做的事情以及在不生成大量代码来处理可能很少发生的情况的情况下他们可以做的事情。

Answer 3

一些 C 库提供memset(). 除非您的编译器进行自动矢量化和循环展开，否则您的for循环将比矢量化慢得多memset()。向量化与否，memset()受内存带宽的限制，最小时间与数组大小除以内存带宽成正比，即它是一个 O(n) 操作，因为内存带宽是恒定的。

在 NUMA 机器上 memsetting 非常大的数组可以被线程化以实现 NUMA 节点数量级的加速。有关一些基准，请参阅此答案。

Answer 4

复杂度为 O(n)。这是基本的东西。