未初始化的局部变量是否是最快的随机数生成器？

Question

我知道未初始化的本地变量是未定义行为(UB)，而且该值可能具有陷阱表示法，这可能会影响后续操作，但有时我只想使用随机数进行视觉呈现，并且不会在程序的其他部分进一步使用它们，例如，在视觉效果中使用随机颜色设置某些内容，例如：

void updateEffect(){
    for(int i=0;i<1000;i++){
        int r;
        int g;
        int b;
        star[i].setColor(r%255,g%255,b%255);
        bool isVisible;
        star[i].setVisible(isVisible);
    }
}

它难道比那个更快吗？

void updateEffect(){
    for(int i=0;i<1000;i++){
        star[i].setColor(rand()%255,rand()%255,rand()%255);
        star[i].setVisible(rand()%2==0?true:false);
    }
}

并且比其他随机数生成器更快吗？

- ggrr

---

这是一个完全合理的问题。事实上，在实践中，未初始化的值可能有点随机。它们并不特别，而且这也是未定义行为，并不会因为提出这个问题而变得更糟。 - geometrian

@imallett：当然。这是一个好问题，至少在过去的时候，旧的Z80（Amstrad / ZX Spectrum）游戏使用它的程序作为设置地形的数据。因此，这甚至有先例。现在不能这样做了。现代操作系统夺走了所有的乐趣。 - Bathsheba

问题的核心在于它并不是随机的。 - john

实际上，存在一个未初始化的变量被用作随机值的例子，可以参考Debian RNG灾难（在这篇文章中的示例4）。 - PaperBirdMaster

实际上 - 相信我，我在各种架构上都做了很多调试 - 您的解决方案可能会做两件事情：要么读取未初始化的寄存器，要么读取未初始化的内存。虽然“未初始化”在某种程度上意味着随机性，但实际上它很可能包含以下内容：a) _零_，b) _重复或一致的值_（在读取曾经用于数字媒体的内存的情况下），或者c) _具有有限值集的一致垃圾_（在读取曾经用于编码数字数据的内存的情况下）。这些都不是真正的熵源。 - mg30rg

Answer 1

正如其他人指出的那样，这是未定义行为（UB）。

在实践中，它（可能）实际上（有点）有效。在x86[-64]体系结构上从未初始化的寄存器读取确实会产生垃圾结果，并且可能不会产生任何破坏（例如Itanium，其中寄存器可以标记为无效，因此读取会传播错误，例如NaN）。

然而有两个主要问题：

1. 它不会特别随机。 在这种情况下，您正在从堆栈中读取，因此将获得先前存在的内容。 这可能是有效随机的、完全结构化的、您十分钟前输入的密码或您祖母的饼干食谱。

2. 这是差（大写'B'）的惯例，让诸如此类的东西潜入您的代码中。 从技术上讲，编译器可以每次读取未定义变量时插入reformat_hdd();。 它不会，但您仍然不应该这样做。 不要做不安全的事情。 您做出的例外越少，您就越安全免受意外错误所有时间。

UB的更紧迫问题是，它使整个程序的行为未定义。 现代编译器可以使用此功能省略大量代码，甚至返回到过去。 与UB玩耍就像维多利亚工程师拆卸活的核反应堆一样。 有无数的事情会出错，你可能不会知道一半的基本原理或已实现的技术。它可能是可以的，但您仍然不应该让它发生。请查看其他详细答案。

此外，我会解雇你。

- imallett

---

Itanium寄存器可以包含NaT（非元素），实际上是一个“未初始化的寄存器”。在Itanium平台上，如果您在没有向寄存器写入值时从中读取，则可能会导致程序中止（请在此处阅读更多：http://blogs.msdn.com/b/oldnewthing/archive/2004/01/19/60162.aspx）。因此，读取未初始化的值为什么会导致未定义的行为有很好的理由。这也可能是Itanium不太受欢迎的原因之一 :) - tbleher

我非常反对“它有一些作用”的观念。即使今天它是真的，但它随时可能因更积极的编译器而改变。编译器可以用unreachable()替换任何读取，并删除你的程序的一半。这在实践中确实会发生。我相信在某些Linux发行版中，这种行为完全抵消了RNG；这个问题中大多数答案似乎都假设未初始化的值像一个值一样运作，这是错误的。 - usr

“我会开除你”这句话听起来相当愚蠢，如果遵循良好的实践，这种错误应该在代码审查中被发现并讨论，以后不应再犯。既然我们正在使用正确的警告标志，那么这个问题肯定会被发现吧？ - Shafik Yaghmour

@Michael 实际上是这样的。如果程序在任何一点上存在未定义行为，编译器可以对您的程序进行优化，从而影响调用该未定义行为之前的代码。有各种文章和演示可以展示这种优化的惊人效果。这里有一个非常好的例子：http://blogs.msdn.com/b/oldnewthing/archive/2014/06/27/10537746.aspx（其中包括标准中提到的如果程序中的任何路径调用UB，则所有赌注都作废的部分）。 - Tom Tanner

这个回答让人产生的感觉好像是“在理论上调用未定义行为是有问题的，但在实践中它不会对你造成太大的伤害”。这是错误的。从会导致未定义行为的表达式收集熵可能会（而且很可能会）导致之前收集的所有熵都丢失。这是一个严重的危险。 - Theodoros Chatzigiannakis

Answer 2

让我明确地说: 我们的程序绝不会调用未定义的行为。这是永远都不好的想法，没有例外。有极少数情况下可以违反此规则;例如，如果您是实现offsetof库的实现者。如果您的情况属于这种例外情况，那么您可能已经知道了。在这种情况下，我们知道使用未初始化的自动变量是未定义的行为。

编译器对未定义行为的优化变得非常激进，我们可以找到许多未定义行为导致安全漏洞的案例。最著名的案例可能是Linux内核空指针检查删除，我在我的C++编译错误回答中提到，其中编译器围绕未定义行为进行的优化将一个有限循环变成了无限循环。

我们可以阅读CERT的《危险的优化和因果关系的丧失》(视频)，其中提到：

越来越多的编译器编写者正在利用 C 和 C++ 编程语言中的未定义行为来改善优化。

经常情况下，这些优化会干扰开发人员对其源代码进行因果分析的能力，也就是分析下游结果对先前结果的依赖关系。

因此，这些优化正在消除软件中的因果关系，并增加软件故障、缺陷和漏洞的概率。

具体来说，关于不确定值，C标准defect report 451: Instability of uninitialized automatic variables提供了一些有趣的阅读材料。尽管它尚未得到解决，但引入了“摇晃值”这个概念，意味着一个值的不确定性可能会在程序中传播，并且在程序的不同点上可能具有不同的不确定值。

我不知道任何此类情况发生的例子，但目前我们不能排除这种可能。 真实例子，而非你期望的结果 你不太可能得到随机值。编译器可以优化掉整个循环。例如，对于这个简化的情况：

void updateEffect(int  arr[20]){
    for(int i=0;i<20;i++){
        int r ;    
        arr[i] = r ;
    }
}

clang优化了它（在实际演示中查看）：

updateEffect(int*):                     # @updateEffect(int*)
    retq

或者像这个修改后的情况一样，得到全零：

void updateEffect(int  arr[20]){
    for(int i=0;i<20;i++){
        int r ;    
        arr[i] = r%255 ;
    }
}

现场查看

updateEffect(int*):                     # @updateEffect(int*)
    xorps   %xmm0, %xmm0
    movups  %xmm0, 64(%rdi)
    movups  %xmm0, 48(%rdi)
    movups  %xmm0, 32(%rdi)
    movups  %xmm0, 16(%rdi)
    movups  %xmm0, (%rdi)
    retq

这两种情况都是未定义行为的完全可接受形式。

注意，如果我们在Itanium上，可能会出现陷阱值:

[...]如果寄存器恰好保存着特殊的非某物值， 读取该寄存器会触发陷阱，除了一些指令[...]

其他重要说明

有趣的是，在UB Canaries项目中，gcc和clang之间关于未初始化内存利用未定义行为程度的差异值得注意。文章指出(我强调):

当然，我们需要完全清楚地知道，任何这样的期望与语言标准无关，而与特定编译器所做的事情有关，这要么是因为该编译器的提供者不愿利用该UB，要么只是因为他们还没有利用它。当没有来自编译器提供者的真正保证时，我们喜欢说尚未利用的UB是定时炸弹：它们正在等待下个月或明年在编译器变得更加激进时爆炸。

正如Matthieu M.指出的那样，每个C程序员都应该了解的未定义行为 #2/3 对这个问题也是相关的。它说，除其他事项外（我强调）：

重要且令人恐惧的是，基于未定义行为的几乎任何优化都可能在将来的任何时候开始触发有缺陷的代码。内联、循环展开、内存提升和其他优化将不断改善，它们存在的一个重要原因是暴露上述优化的次要优化。

对我来说，这是非常不令人满意的，部分原因是编译器最终会被指责，但也因为这意味着大量的 C 代码是等待爆炸的地雷。 为了完整起见，我应该提到实现可以选择使未定义行为变得明确定义，例如gcc 允许通过联合进行类型游戏，而在 C++ 中似乎是未定义行为。如果是这种情况，实现应该记录下来，通常这不会是可移植的。

- Shafik Yaghmour

---

+(int)(PI/3) 用于编译器输出示例；一个现实生活中的UB例子就是，呃，UB。 - user719662

充分利用UB曾经是优秀黑客的标志。这一传统已经延续了大约50年甚至更久。不幸的是，由于坏人的存在，现在计算机需要尽量减少UB的影响。在90年代，当操作系统无法有效保护用户免受自身错误影响时，我非常喜欢研究如何通过UB机器码或端口读写等方式实现酷炫的功能。 - sfdcfox

@sfdcfox 如果你是在机器码/汇编语言中进行操作，那么它就不是未定义的行为（可能是非常规的行为）。 - Caleth

如果你有特定的汇编代码，请使用它，不要编写不符合规范的C代码。这样，每个人都会知道你正在使用特定的非可移植技巧。而且，并不是那些“坏人”禁止你使用未定义行为（UB），而是英特尔等芯片制造商在其芯片上施展了他们的技巧。 - Caleth

@500-内部服务器错误，因为它们可能不容易被检测到，或者在一般情况下根本无法被检测到，因此没有办法禁止它们。这与违反语法不同，后者可以被检测到。我们还有“格式错误”和“格式错误但无需诊断”，通常将可能在理论上被检测到的程序与在理论上无法可靠检测的程序分开。 - Shafik Yaghmour

Answer 3

不行，这是很糟糕的。

在C和C++中，使用未初始化变量的行为是未定义的，而且这种方案很可能没有令人满意的统计特性。

如果你想要一个“快速而简单”的随机数生成器，那么rand()是你最好的选择。它的实现只涉及乘法、加法和取模操作。

我所知道的最快的生成器需要你使用 uint32_t 作为伪随机变量 I 的类型，然后使用

I = 1664525 * I + 1013904223

来生成连续的值。你可以选择任何你喜欢的初始值I（称为“种子”）。显然，你可以直接把代码嵌入到程序中。无符号类型的标准保证的环绕行为充当了取模操作。（这些数值常量是由杰出的科学程序员 Donald Knuth 精心挑选的。）

- Bathsheba

---

你提供的“线性同余”生成器适用于简单应用，但只适用于非加密的应用。它的行为可以被预测。例如，可以参考唐纳德·克努斯本人撰写的文章《解密线性同余加密》（IEEE信息理论杂志第31卷）。 - Jay

与未初始化的变量相比，这是一种更好的解决方案。 - Mike McMahon

在我看来，rand()已经不适合使用了，应该完全废弃。现在你可以下载自由许可和远比rand()优秀的随机数生成器（例如Mersenne Twister），它们几乎同样快速且非常容易使用，所以真的没有必要继续使用高度有缺陷的rand()。 - Jack Aidley

rand()还有一个可怕的问题：它使用一种叫做内部线程锁的东西，会严重拖慢你的代码。至少，有一个可重入版本。如果你使用C++11，随机API提供了你需要的一切。 - Marwan Burelle

虽然 rand() 必须被种子化（否则它看起来不太随机）。由于通常使用时间作为种子，因此您还需要在其中进行系统调用。但在几乎任何情况下，性能仍然非常可接受（而且种子化只需要一次）。 - Kat

公正地说，他并没有问这是否是一个好的随机数生成器。他问的是它是否快速。嗯，是的，它很可能是最快的。但结果将不会非常随机。 - jcoder

Answer 4

好问题!

未定义并不意味着是随机的。想一想，在全局未初始化变量中得到的值是由系统或您/其他正在运行的应用程序留下的。取决于系统对不再使用的内存执行何种操作，和/或系统和应用程序生成哪些类型的值，您可能会得到：

1. 始终相同。
2. 是一组小值之一。
3. 在一个或多个小范围内获取值。
4. 从16/32/64位系统上指针中看到许多值可被2/4/8整除
5. ......

您将获得的值完全取决于系统和/或应用程序留下的非随机值。因此，确实会有一些噪声（除非您的系统擦除不再使用的内存），但您将绘制的值池绝不会是随机的。

对于本地变量，情况会更糟，因为这些变量直接来自您自己程序的堆栈。在执行其他代码期间，您的程序实际上很有可能写入这些堆栈位置。我估计在这种情况下运气的机会非常低，而且您所做的“随机”代码更像是碰运气。

阅读有关随机性的信息。正如您将看到的，随机性是一种非常特定且难以获得的属性。认为只要取一些难以跟踪的东西（例如您的建议），就会得到随机值，这是一个常见的错误。

- meaning-matters

---

那还不算计算机编译器所做的所有优化，这些优化都会使那段代码变得面目全非。 - Deduplicator

在调试和发布版本中，你会得到不同的“随机性”。未定义意味着你做错了。 - Sql Surfer

好的。我会用“未定义”、“任意”和“随机”来缩写或概括。所有这些类型的“未知性”都有不同的属性。 - fche

全局变量保证具有定义的值，无论是否显式初始化。这在C++中是绝对正确的（https://en.cppreference.com/w/cpp/language/initialization），在C语言中也是如此（https://en.cppreference.com/w/c/language/initialization）。 - Brian Vandenberg

Answer 5

很多好的回答，但请允许我补充一个并强调一点，在确定性计算机中，没有任何东西是随机的。这对伪随机数生成器产生的数字和在栈中为C / C ++本地变量保留的区域中发现的“随机”数字都是正确的。

但是......有一个关键的区别。

良好的伪随机数生成器产生的数字具有使它们在统计意义上类似于真正的随机抽样的属性。例如，分布是均匀的。周期长度很长：在循环重复之前，您可以获得数百万个随机数字。序列不是自相关的：例如，如果您看生成的数字中的每2、3或27个数字，或者如果您查看特定数字，则不会开始出现奇怪的模式。

相比之下，在堆栈上留下的“随机”数字没有这些属性。它们的值及其表面上的随机性完全取决于程序的构造方式、编译方式以及编译器的优化方式。例如，以下是将您的想法作为独立程序的变体：

#include <stdio.h>

notrandom()
{
        int r, g, b;

        printf("R=%d, G=%d, B=%d", r&255, g&255, b&255);
}

int main(int argc, char *argv[])
{
        int i;
        for (i = 0; i < 10; i++)
        {
                notrandom();
                printf("\n");
        }

        return 0;
}

当我在Linux机器上使用GCC编译并运行此代码时，结果非常明显是确定性的:

R=0, G=19, B=0
R=130, G=16, B=255
R=130, G=16, B=255
R=130, G=16, B=255
R=130, G=16, B=255
R=130, G=16, B=255
R=130, G=16, B=255
R=130, G=16, B=255
R=130, G=16, B=255
R=130, G=16, B=255

如果你使用反汇编器查看编译后的代码，你可以详细地重构正在发生的事情。第一次调用 notrandom() 使用了之前该程序未使用过的堆栈区域; 谁知道那里有什么东西。但在调用 notrandom() 之后，会调用 printf()（GCC 编译器实际上将其优化为对 putchar() 的调用，但不要紧），这将覆盖堆栈。因此，在下一次和随后的调用 notrandom() 时，堆栈将包含来自执行 putchar() 的旧数据，并且由于始终使用相同的参数调用 putchar()，因此这些旧数据也始终相同。

因此，这种行为绝对没有任何随机性，而以这种方式获得的数字也没有很好编写的伪随机数生成器的任何理想特性。实际上，在大多数现实场景中，它们的值将是重复且高度相关的。

事实上，就像其他人一样，我也会认真考虑解雇试图将此想法作为“高性能 RNG”的人。

- Viktor Toth

---

“在确定性计算机中，没有任何随机性。”这并不完全正确。现代计算机包含各种传感器，可以让您产生真正的、不可预测的随机性，而无需单独的硬件生成器。在现代架构上，“/dev/random”的值通常是从这些硬件源播种的，并且实际上是“量子噪声”，即在物理意义上最好的真正不可预测的。 - Konrad Rudolph

但这不是一个确定性计算机，对吧？现在你要依赖于环境输入。无论如何，这使我们远远超出了传统伪随机数生成器与未初始化内存中的“随机”位之间的讨论。此外...看看/dev/random的描述，就能够欣赏到实现者们为确保随机数具有密码学安全性所付出的努力...正是因为输入源不是纯粹的、不相关的量子噪声，而是潜在高度相关的传感器读数，只有很小程度的随机性。它也相当慢。 - Viktor Toth

Answer 6

未定义行为意味着编译器的作者可以忽略问题，因为无论发生什么，程序员都没有权利抱怨。

理论上，在进入未定义区域时任何事情都可能发生（包括恶魔从你的鼻子飞走），但通常意味着编译器作者不会关心局部变量的值将是堆栈内存中此时所在位置的任何内容。

这也意味着通常内容将是“奇怪”的，但是固定的或稍微随机的或者变量，但有明显的模式（例如每次迭代增加的值）。

当然，您不能指望它成为一个合适的随机生成器。

- 6502

Answer 7

未定义行为是未定义的。这并不意味着你会得到一个未定义的值，而是意味着程序可以做任何事情，同时仍然满足语言规范。

一个好的优化编译器应该采取

void updateEffect(){
    for(int i=0;i<1000;i++){
        int r;
        int g;
        int b;
        star[i].setColor(r%255,g%255,b%255);
        bool isVisible;
        star[i].setVisible(isVisible);
    }
}

并将其编译为noop。这肯定比任何替代方案都要快。它的缺点是它不会做任何事情，但这就是未定义行为的缺点。

- Martijn

---

很多事情取决于编译器的目的是帮助程序员生成符合领域要求的可执行文件，还是旨在生成最“高效”的可执行文件，其行为与C标准的最低要求一致，而不考虑这种行为是否有任何有用的目的。对于前者的目标，让代码使用一些任意的初始值r，g，b，或者在实际可行的情况下触发调试器陷阱，比将代码转换为nop更有用。至于后者的目标... - supercat

一个最佳的编译器应该确定会导致上述方法执行的输入，并且消除任何只有在收到这样的输入时才相关的代码。 - supercat

@supercat 或者它的目的可能是为了在符合标准的同时生成高效的可执行文件，同时帮助程序员找到不需要符合标准的地方。编译器可以通过发出比标准要求更多的诊断信息来满足这种妥协性目的，例如GCC的“-Wall -Wextra”。 - Damian Yerrick

值未定义并不意味着周围代码的行为未定义。没有编译器应该无操作该函数。两个函数调用，无论它们接收什么输入，都必须被调用；第一个必须使用0到255之间的三个数字进行调用，第二个必须使用true或false值进行调用。“良好的优化编译器”可以将函数参数优化为任意静态值，完全摆脱变量，但这是它所能做到的（除非函数本身可以在某些输入上减少为noops）。 - Dewi Morgan

@DewiMorgan - 由于被调用的函数属于“设置此参数”类型，当输入与参数的当前值相同时，它们几乎肯定会简化为noops，编译器可以自由地假设这种情况。 - Jules

值未定义并不意味着周围代码的行为未定义。在C和C++中都是如此。如果您不喜欢这一点，请使用其他语言。 - Ben Voigt

Answer 8

由于安全原因，分配给程序的新内存必须被清理，否则信息可能会被利用并且密码可能会从一个应用程序泄漏到另一个应用程序中。只有在您重复使用内存时，才会得到不同于 0 的值。而且很可能，在堆栈上，先前的值是固定的，因为该内存的先前使用是固定的。

- Arne

Answer 9

虽然还没有提到，但调用未定义行为的代码路径允许编译器做任何它想做的事情，例如：

void updateEffect(){}

这肯定比你正确的循环快，而且由于未定义行为，它是完全符合规范的。

- Caleth

Answer 10

你的代码示例可能不会像你期望的那样运行。虽然从技术上讲，每次循环都会重新创建r、g和b值的局部变量，但实际上它们在堆栈上占用的是完全相同的内存空间。因此，每次迭代不会重新随机化，你最终会为1000个颜色分配相同的3个值，而与r、g和b各自的随机性和初始值无关。

确实，如果它确实起作用，我会非常好奇是什么重新随机化了它。我能想到的唯一可能是一个插入到该堆栈顶部的交替中断，这种情况极不可能发生。或者是内部优化将它们保留为寄存器变量而不是真正的内存位置，在循环后面进一步重复使用寄存器，尤其是如果设置可见性函数特别富于寄存器。但依旧远非随机。

- Jos