快速 SSE 伪随机数生成器

引言

这是在测试数据生成过程中获得的知识的一种保存点。使用该代码的生成器比标准 C 库的随机函数更快，几乎在任何地方都能工作，并且不依赖于其他东西。

背景

这段代码是在测试数据生成器实现期间创建的。标准库太慢，而且没有依赖其他库的意愿。另一个意图是使代码能够跨平台编译。该代码将在任何支持 SSE/SIMD 的 CPU 上工作。它未在 RISC 或类似 ARM 的 CPU 上进行测试。

Using the Code

代码本身并不大或复杂

/* definition for RAND_MAX constant */
#include <stdlib.h>
/* random number storage */
static unsigned long long g_seed;

/**
 * Used to seed the generator
 * @param seed initializing "generator"
 */
void fast_srand(unsigned int seed)
{
    g_seed = seed;
}

/**
 * Compute a pseudo random integer. Output value in range [0, RAND_MAX]
 * @return pseudo random integer
 */
int fast_rand()
{
    g_seed = (214013*g_seed+2531011);
    return (g_seed>>32)&RAND_MAX;
}

这段代码并非完全是我写的。我在互联网上找到了它的主要思想。我尝试将这段代码与标准库函数（rand/random）进行比较，并尝试读取来自/dev/urandom的随机数据。

性能和随机性测试

有人要求我比较文章中生成器的性能和随机性，以及最常用的库生成器。

测试代码

我编写了一个测试代码

/* definition for RAND_MAX constant */
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define DEF_RANDOM_COUNT 10000
/* random number storage */
static unsigned long long g_seed;

/**
 * Used to seed the generator
 * @param seed initializing "generator"
 */
void fast_srand(unsigned int seed)
{
    g_seed = seed;
}

/**
 * Compute a pseudo random integer. Output value in range [0, RAND_MAX]
 * @return pseudo random integer
 */
int fast_rand()
{
    g_seed = (214013*g_seed+2531011);
    return (g_seed>>32)&RAND_MAX;
}
int cStrToInt(const char* sz)
{
    char* pEnd;
    if(sz==NULL)    {
        return 0;
    }
    return strtol(sz,&pEnd, 10);
}

int main(int argc, char* argv[])  {
    int i, n;
    int randomCount = DEF_RANDOM_COUNT;
    int randomType = 0;
    int dontPrint = 0;
    for(i=1; i<argc; i++)   {
        if(argv[i][0]=='-') {
            switch(argv[i][1])  {
                case 't':/* type */
                    if(i+1<argc)    {
                        randomType = cStrToInt(argv[++i]);
                    }
                    break;
                case 'c':
                    if(i+1<argc)    {
                        randomCount = cStrToInt(argv[++i]);
                    }
                    break;
                case 'p':
                    dontPrint = 1;
                    break;
            }
        }
        else    {
            randomCount = cStrToInt(argv[i]);
        }
    }
    if(randomCount<0)   {
        randomCount = DEF_RANDOM_COUNT;
    }
    switch(randomType)  {
        case 2:
            srandom(time(NULL));
            break;
        case 1:
            srand(time(NULL));
            break;
        default:
            fast_srand(time(NULL));
            break;
    }
    for(i=0; i<randomCount; i++)    {
        switch(randomType)  {
            case 2:
                n = random();
                break;
            case 1:
                n = rand();
                break;
            default:
                n = fast_rand();
                break;
        }
        if(dontPrint)   {
            continue;
        }
        printf("%d\n",fast_rand());
    }
}

我将测试代码保存为rndGenTest.c，并使用以下命令编译代码

gcc rndGenTest.c -o rndGenTest 

性能

在我的 Debian WSL 上的性能比较结果是（第一个结果为文章中的代码，第二个 - srand/rand，第三个 - srandom/random）

-bash $ time ./rndGenTest -p 10000000 ; time ./rndGenTest -p -t 1 10000000  ; time ./rndGenTest -p -t 2 10000000

real    0m0.034s
user    0m0.030s
sys     0m0.000s

real    0m0.071s
user    0m0.066s
sys     0m0.000s

real    0m0.057s
user    0m0.052s
sys     0m0.000s

随机性

我还对我的 Debian WSL 上的所有这些生成器进行了一个快速的随机性测试（第一个结果为文章中的代码，第二个 - srand/rand，第三个 - srandom/random）

-bash $ ./rndGenTest 1000000 | sort -u | wc -l ; ./rndGenTest -t 1 1000000 | sort -u | wc -l ; ./rndGenTest -t 2 1000000
 | sort -u | wc -l
999766
999762
999762

关注点

我对代码速度的比较结果感到非常惊讶。文章中的代码比库代码快两倍。我认为我可以找到解释为什么会发生这种情况，但是...

无论如何，文章中的生成器非常适合生成大型测试数据。

历史

• 2024年2月19日：初始文本
• 2024年2月20日：添加测试部分