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

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);
    }
}

并且还比其他随机数发生器更快？

Answer 1

正如其他人所说,这是未定义的行为(UB).

在实践中,它(可能)实际上(有点)工作.从x86 [-64]架构上的未初始化寄存器读取确实会产生垃圾结果,并且可能不会做任何坏事(与例如Itanium相反,其中寄存器可以被标记为无效,因此读取传播错误,如NaN).

但有两个主要问题:

1. 它不会特别随机. 在这种情况下,你正在从堆栈中读取,所以你将获得之前的任何东西.这可能是有效的随机,完全结构化,十分钟前输入的密码,或祖母的cookie配方.

2. 让(像''''''''''''''''''''''''''''''''''''''''' 从技术上讲,reformat_hdd();每次读取未定义的变量时,编译器都可以插入.它不会,但你不应该这样做.不要做不安全的事情.你所做的例外越少,就越安全意外失误所有的时间.

   UB更紧迫的问题是它使整个程序的行为未定义.现代编译器可以使用它来消除大量代码,甚至可以追溯到时间.与UB一起玩就像维多利亚时代的工程师正在拆除现场核反应堆.有很多事情要出错,你可能不会知道一半的基本原则或实施技术.它可能没问题,但你仍然不应该让它发生.看看其他很好的答案细节.

而且,我会解雇你.

Answer 2

让我说清楚一点:我们不会在程序中调用未定义的行为.从来没有一个好主意.这条规则很少有例外; 例如,如果您是实现offsetof的库实现者.如果您的案件属于这种例外情况,您可能已经知道了.在这种情况下,我们知道使用未初始化的自动变量是未定义的行为.

编译器对未定义行为的优化变得非常积极,我们可以发现许多未定义行为导致安全漏洞的情况.最臭名昭着的案例可能是我在回答C++编译bug时提到的Linux内核空指针检查删除？围绕未定义行为的编译器优化将有限循环变为无限循环.

我们可以阅读CERT的危险优化和因果关系丢失(视频),其中包括:

编译器编写者越来越多地利用C和C++编程语言中未定义的行为来改进优化.

通常,这些优化会干扰开发人员对其源代码执行因果分析的能力,即分析下游结果对先前结果的依赖性.

因此,这些优化消除了软件中的因果关系,并增加了软件故障,缺陷和漏洞的可能性.

特别是对于不确定值,C标准缺陷报告451:未初始化自动变量的不稳定性使得一些有趣的读数.它还没有得到解决,但引入了摇摆值的概念,这意味着值的不确定性可能通过程序传播,并且在程序的不同点可能具有不同的不确定值.

我不知道发生这种情况的任何例子,但在这一点上我们不能排除它.

真实的例子,而不是你期望的结果

您不太可能获得随机值.编译器可以完全优化离开循环.例如,通过这个简化的案例:

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也与此问题相关.它说除其他外(强调我的):

我们意识到,和可怕的是,几乎所有 被触发基于未定义行为可以开始优化对bug的代码在将来的任何时间.内联,循环展开,内存促销和其他优化将继续变得更好,并且他们存在的重要部分原因是暴露上述二次优化.

对我来说,这是非常不满意的,部分是因为编译器不可避免地最终受到指责,但也因为它意味着巨大的C代码是等待爆炸的地雷.

为了完整起见,我应该提一下,实现可以选择明确定义未定义的行为,例如gcc允许通过联合进行类型惩罚,而在C++中这似乎是未定义的行为.如果是这种情况,实现应该记录它,这通常是不可移植的.

Answer 3

不,这太可怕了.

使用未初始化变量的行为在C和C++中都是未定义的,并且这种方案不太可能具有理想的统计属性.

如果你想要一个"快速而肮脏"的随机数发生器,那么这rand()是你最好的选择.在其实现中,它所做的只是乘法,加法和模数.

我所知道的最快的生成器要求你使用a uint32_t作为伪随机变量的类型I,并使用

I = 1664525 * I + 1013904223

生成连续的值.您可以选择任何您喜欢的初始值I(称为种子).显然你可以编写内联代码.无符号类型的标准保证环绕充当模数.(数字常数由杰出的科学程序员Donald Knuth亲自挑选.)

Answer 4

好问题!

未定义并不意味着它是随机的.想一想,您在全局未初始化变量中获得的值是由系统或您/其他应用程序运行的.根据系统对不再使用的内存和/或系统和应用程序生成的值的不同,您可能会得到:

1. 总是一样.
2. 是一小组价值观之一.
3. 获取一个或多个小范围内的值.
4. 从16/32/64位系统上的指针查看2/4/8可分割的许多值
5. ...

您将获得的值完全取决于系统和/或应用程序留下的非随机值.所以,确实会有一些噪音(除非你的系统不再使用内存),但你所绘制的价值池绝不是随机的.

局部变量的情况变得更糟,因为它们直接来自您自己程序的堆栈.您的程序很可能在执行其他代码期间实际编写这些堆栈位置.我估计在这种情况下运气的可能性非常低,你做的"随机"代码改变试试这个运气.

阅读随机性.正如您将看到的随机性是一个非常具体且难以获得的属性.这是一个常见的错误,认为如果你只是采取一些难以追踪的东西(比如你的建议),你会得到一个随机值.

Answer 5

许多好的答案,但允许我添加另一个,并强调在确定性计算机中,没有任何东西是随机的.这对于伪RNG产生的数字和在堆栈上为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"的人.

Answer 6

未定义的行为意味着编译器的作者可以自由地忽略这个问题,因为程序员永远无权抱怨发生的任何事情.

虽然从理论上讲,当进入UB土地时,任何事情都可能发生(包括从你的鼻子飞出的守护进程)通常意味着编译器作者根本不关心,对于局部变量,该值将是此时堆栈内存中的任何内容.

这也意味着内容通常是"奇怪的"但是固定的或稍微随机的或可变的但具有明显的明显模式(例如,在每次迭代时增加值).

当然,你不能指望它是一个像样的随机发电机.

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.这肯定比任何替代方案都快.它的缺点是它不会做任何事情,但这是未定义行为的缺点.

Answer 8

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

Answer 9

尚未提及,但允许调用未定义行为的代码路径可以执行编译器所需的任何操作,例如

void updateEffect(){}

这肯定比你正确的循环更快,因为UB,完全符合要求.

Answer 10

您的特定代码示例可能无法满足您的期望.虽然从技术上讲,循环的每次迭代都会重新创建r,g和b值的局部变量,但实际上它是堆栈上完全相同的内存空间.因此,每次迭代都不会重新随机化,并且最终会为1000种颜色中的每种颜色分配相同的3个值,无论r,g和b的单独和最初是多么随机.

事实上,如果确实有效,我会非常好奇它是什么让它重新随机化.我唯一能想到的就是一个交错的中断,它堆叠在堆栈顶上,极不可能.也许内部优化将那些保持为寄存器变量而不是真正的存储器位置,其中寄存器在循环中进一步向下使用,也可以做到这一点,特别是如果集合可见性函数特别是寄存器饥饿.仍然,远非随机.

Answer 11

因为这里的大多数人都提到了未定义的行为.未定义也意味着您可以获得一些有效的整数值(幸运的是),在这种情况下,这将更快(因为没有进行rand函数调用).但实际上并没有使用它.我相信这会产生可怕的结果,因为运气不会一直伴随着你.

Answer 12

特别糟糕!坏习惯,结果不好.考虑:

A_Function_that_use_a_lot_the_Stack();
updateEffect();

如果函数A_Function_that_use_a_lot_the_Stack()始终进行相同的初始化,则会使堆栈上的数据相同.这些数据就是我们所说的updateEffect():永远是同样的价值!.

Answer 13

我进行了一个非常简单的测试,它根本不是随机的.

#include <stdio.h>

int main() {

    int a;
    printf("%d\n", a);
    return 0;
}

每次我运行该程序时,它都会打印相同的数字(32767在我的情况下) - 你不能比那更随意.这可能是堆栈中剩余的运行时库中的启动代码.由于每次程序运行时它都使用相同的启动代码,并且在运行之间程序中没有其他任何变化,因此结果完全一致.

Answer 14

您需要定义"随机"的含义.一个明智的定义涉及你得到的价值应该没有多少相关性.这是你可以测量的东西.以可控,可重复的方式实现也并非易事.所以未定义的行为肯定不是你想要的.

Answer 15

在某些情况下,可以使用"unsigned char*"类型安全地读取未初始化的内存[例如,从中返回的缓冲区malloc].代码可以读取这样的内存,而不必担心编译器会将因果关系抛到窗口之外,并且有时为代码准备内存可能包含的内容可能比确保未读取未初始化数据更有效(一个常见的例子是使用memcpy部分初始化的缓冲区而不是离散地复制包含有意义数据的所有元素.

然而,即使在这种情况下,也应该总是假设如果字节的任何组合将特别无理取闹,那么读取它将总是产生该字节模式(并且如果某个模式在生产中是无理取闹的,但在开发中不是,那么在代码处于生产状态之前,模式不会出现.

读取未初始化的内存可能是嵌入式系统中随机生成策略的一部分,在嵌入式系统中可以确保自上次系统上电以来,内存从未使用基本上非随机的内容编写,并且如果制造用于存储器的过程使其电源接通状态以半随机方式变化.代码应该工作,即使所有设备总是产生相同的数据,但是在例如一组节点每个都需要尽可能快地选择任意唯一ID的情况下,具有"非常随机"的生成器,其给予一半节点相同的初始值ID可能比没有任何初始随机源更好.

Answer 16

正如其他人所说,它会很快,但不是随机的.

大多数编译器会为局部变量做的是在堆栈中为它们占用一些空间,但不要把它设置为任何东西(标准说它们不需要,所以为什么要减慢你生成的代码？).

在这种情况下,您将获得的值将取决于之前在堆栈上的内容 - 如果您在此之前调用一个具有一百个本地char变量的函数全部设置为'Q'然后在之后调用您的函数返回,然后你可能会发现你的"随机"值的行为就好像你把memset()它们全都变成'Q'一样.

重要的是,对于尝试使用它的示例函数,每次读取它们时这些值都不会改变,它们每次都会相同.因此,您将获得100颗星,所有颜色和可见度都相同.

此外,没有任何说明编译器不应该初始化这些值 - 所以未来的编译器可能会这样做.

一般来说:坏主意,不要这样做.(就像很多"聪明"的代码级优化真的...)