Генерация случайных чисел в Linux и Windows

А вы там, часом /dev/random читаете? Тогда попробуйте /dev/urandom, если, конечно, важна именно скорость.

$ cat /dev/urandom |pipebench >/dev/null Summary: Piped 41.51 MB in 00h00m22.82s: 1.81 MB/second

мне не кажется что это медленно

/dev/random конечно медленнее, но оттуда имеет смысл брать только один из seed для генерации ключей и прочего. А на тривиальную генерацию хватает urandom

> Заметил, что в линуксе сей процесс происходит намного медленне, чем в винде

Что вообще подразумевается под "генератором случайных чисел ОСи"? "генератора случайных чисел независимо от языка программирования"? Какие конкретно генераторы сравнивались? И каким образом происходило сравнение? А-то заявление выглядит бредово. Код в студию.

Да я понимаю, что первое сообщение немного странное получилось. :) Просто дело в том, что несколько раз приходилось писать небольшие программки, в которых производительность очень сильно зависила от генерации случайных чисел. В итоге получалось, что под виртуальной машиной с виндой они работали примерно в 2 раза быстрее, чем на основной системе с линуксом. Опытным путём установил, что всё дело в собственно генерации. Подобное наблюдалось со стандартным C'шным rand(), с Qt'шным потоко-безопасным qrand() и с D'шным собственным движком. Стало любопытно, в чём же дело. :)

Конкретный код пока, к сожалению, привести не могу, ибо там будет очень много мусора, не касающегося темы. Сейчас как раз пытаюсь создать минимально-воспроизводимый пример.

pid процесса самое лучше случайное число.

Вильфред, ты задолбал с этим 4.2.

сама ты 4.2

> сей процесс

какой "сей процесс"? Существует множество генераторов случайных чисел

т.е. D'шный генератор случайных чисел под виндой работает в два раза быстрее?

std.random не читает из /dev/[u]random

> несколько раз приходилось писать небольшие программки, в которых производительность очень сильно зависила от генерации случайных чисел

Сильно зависела в каком смысле? Зависела от результата работы генератора или именно "тормозила" в процессе генерации числа? Там, кстати, нечему тормозить вообще, ибо простенькие конгруэнтные генераторы (по крайней мере rand() и qrand()). Причем независимо от системы.

> Сейчас как раз пытаюсь создать минимально-воспроизводимый пример.

Приводи код - вместе посмеемся.

> Приводи код - вместе посмеемся.

Ну смейтесь. ;)
У меня под линуксом 2-2,5 секунды, под виндой - 200мс.
Подсчёт процентов идёт для проверки равномерности распределения.

#include <QTime>
#include <iostream>
//
int main()
{
QTime timer;
timer.start();

int freq[5];
memset(&freq, 0, 5 * sizeof(int));

qsrand(QTime::currentTime().msecsTo(QTime()));

const long count = 10000000;
for (long i = 0; i < count; ++i)
++freq[qrand() % 5];

for (int i = 0; i < 5; ++i)
std::cout << (double)freq[i] / count * 100 << '\n';

std::cout << timer.elapsed() << '\n';
}

Вариант на D.
Linux - 600ms, Windows - 250ms.

import std.date, std.random, std.stdio;

void main()
{
auto time = getUTCtime();

int[5] freq;

Random gen;
gen.seed(unpredictableSeed());
auto rand = UniformDistribution!(int)(0, 5);

invariant long count = 10_000_000;
foreach (i; 0 .. count)
++freq[rand.next(gen)];

foreach(i; freq)
writeln(cast(double)(i) / count * 100);

writeln(getUTCtime() - time);
}

ИМХО ты просто мудак. Без обид.

А обосновать, что именно тебе показалось в коде мудаческим? Если что - сам посмеюсь.

C:\Projects\test>type rand.c
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <time.h>

int main(int argc, char *argv[])
{
int i = 0;
int count = 10000000;
double timer = (double)clock() / CLOCKS_PER_SEC;
int freq[5];
memset(freq, 0, 5 * sizeof(int));

srand(time(NULL));

for (; i < count; ++i)
++freq[rand() % 5];

for (i = 0; i < 5; ++i)
printf("%F\n", (double)freq[i] / count * 100);

timer = (double)clock() / CLOCKS_PER_SEC - timer;
printf("Time elapsed: %G\n", timer);

return 0;
}
C:\Projects\test>gcc -o rand_gcc.exe rand.c
rand.c:26:2: warning: no newline at end of file

C:\Projects\test>rand_gcc.exe





Time elapsed: 0.281

C:\Projects\test>g++ -o rand_g++.exe rand.c
rand.c:26:2: warning: no newline at end of file

C:\Projects\test>rand_g++.exe





Time elapsed: 0.281

C:\Projects\test>ver

Microsoft Windows XP [Версия 5.1.2600]

C:\Projects\test>

serge@darkstar:~$ cat rand.c
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <time.h>

int main(int argc, char *argv[])
{
int i = 0;
int count = 10000000;
double timer = (double)clock() / CLOCKS_PER_SEC;
int freq[5];

memset(freq, 0, 5 * sizeof(int));

srand(time(NULL));

for (; i < count; ++i)
++freq[rand() % 5];

for (i = 0; i < 5; ++i)
printf("%F\n", (double)freq[i] / count * 100);

timer = (double)clock() / CLOCKS_PER_SEC - timer;
printf("Time elapsed: %G\n", timer);

return 0;
}
serge@darkstar:~$ gcc -o rand_gcc ./rand.c
serge@darkstar:~$ time ./rand_gcc
19.981130
19.994970
20.017090
19.994350
20.012460
Time elapsed: 0.82

real 0m0.826s
user 0m0.824s
sys 0m0.000s
serge@darkstar:~$

чуть не забыл. оффтопик на iC2D T5600 1800MHz а Линупс на iP4D 1400MHz

qrand медленный. Используй rand_r():

#include <QTime>
#include <QDebug>

#include <cstdlib>
#include <ctime>

int main()
{
    QTime timer;
    const long count = 10000000;
    int freq[5] = { 0 };

    uint *s = new uint;
    *s = (uint)time(0);

    timer.start();

    for (long i = 0; i < count; ++i)
        ++freq[rand_r(s) % 5];

    qDebug() << timer.elapsed();

    delete s;
}

Благодарю за совет. Разница стала не такой большой, но она есть - 500мс линукса против 200мс виртуальной машины. Всё равно что-то здесь не так. :)

$ ./qrand
200

$ cat /proc/cpuinfo | grep 'model name'
model name : AMD Sempron(tm) Processor 2800+

Занятно...
$ cat /proc/cpuinfo | grep 'model name'
model name : Intel(R) Pentium(R) 4 CPU 2.80GHz
model name : Intel(R) Pentium(R) 4 CPU 2.80GHz

За такое

    uint *s = new uint;
    *s = (uint)time(0);

....

    delete s;


руки отрывать надо

> Собственно, кто-нибудь знает точно в чём причина такого поведения?

Используются разные RNG, что тут гадать? Прицепите к своему софту релазицию какого-нибудь известного RNG, например, Mersenne twister, будет одинаково.

почему?

> Вариант на D.

Среднее после 3-х запусков.

WinXP - 365

Gentoo Linux - 395

Там системные вызовы - только getpid и time в unpredictableSeed.

Исходник:

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <time.h>

int main(int argc, char *argv[])
{
  int i = 0;
  int count = 10000000;
  double timer = (double)clock() / CLOCKS_PER_SEC;
  int freq[5];
  memset(freq, 0, 5 * sizeof(int));
  
  srand(time(NULL));

  for (; i < count; ++i)
    ++freq[rand() % 5];

  for (i = 0; i < 5; ++i)
    printf("%F\n", (double)freq[i] / count * 100);

  timer = (double)clock() / CLOCKS_PER_SEC - timer;
  printf("Time elapsed: %G\n", timer);

  return 0;
}

Вчера я ответить не мог, потому что у меня не было компилятора для винды. Специально не поленился скачать Visual Studio 2008 Express Edition.
Так что теперь в винде имеем версию мелкософтового компилятора из указанной студии, релизный проект с дефолтными настройками. Получилось вот что:

20.010390
19.990280
20.002410
20.008230
19.988690
Time elapsed: 0.269

--

Что имеем в линуксе:

$ gcc -O0 rndtest.c -o rnd
$ ./rnd
20.003850
19.998760
20.005490
19.981410
20.010490
Time elapsed: 0.18

Так что большой разницы (причем у меня получилась разница в пользу линукса) я не увидел. Этого и следовало ожидать.

$ cat /proc/cpuinfo | grep 'model name'
model name	: Intel(R) Core(TM)2 Duo CPU     T9300  @ 2.50GHz
model name	: Intel(R) Core(TM)2 Duo CPU     T9300  @ 2.50GHz

Что интересно, qt'шная версия твоего кода показала у меня такой результат:
$ ./rndqt 
20.0046
19.9907
19.973
20.0152
20.0165
Time elapsed: 0.368

Хотя тут (http://doc.trolltech.com/4.2/qtglobal.html#qrand) написано, что qrand() есть "Thread-safe version of the standard C++ rand() function".

int qrand()
{
#if defined(Q_OS_UNIX) && !defined(QT_NO_THREAD)
    SeedStorageType *pseed = randTLS()->localData();
    if (!pseed) {
        randTLS()->setLocalData(pseed = new SeedStorageType);
        *pseed = 1;
    }
    return rand_r(pseed);
#else
    // On Windows srand() and rand() already use Thread-Local-Storage
    // to store the seed between calls
    return rand();
#endif
}

Так будет слегка понятнее:

#  if defined(Q_OS_INTEGRITY)
typedef long SeedStorageType;
#  else
typedef uint SeedStorageType;
#  endif

typedef QThreadStorage<SeedStorageType *> SeedStorage;
Q_GLOBAL_STATIC(SeedStorage, randTLS)  // Thread Local Storage for seed value

void qsrand(uint seed)
{
#if defined(Q_OS_UNIX) && !defined(QT_NO_THREAD)
    SeedStorageType *pseed = randTLS()->localData();
    if (!pseed)
        randTLS()->setLocalData(pseed = new SeedStorageType);
    *pseed = seed;
#else
    // On Windows srand() and rand() already use Thread-Local-Storage
    // to store the seed between calls
    srand(seed);
#endif
}


И про QThreadStorage, localData() по сути вот это:

void **QThreadStorageData::get() const
{
    QThreadData *data = QThreadData::current();
    if (!data) {
        qWarning("QThreadStorage::get: QThreadStorage can only be used with threads started with QThread");
        return 0;
    }
    QMap<int, void *>::iterator it = data->tls.find(id);
    DEBUG_MSG("QThreadStorageData: Returning storage %d, data %p, for thread %p",
          id,
          it != data->tls.end() ? it.value() : 0,
          data->thread);
    return it != data->tls.end() && it.value() != 0 ? &it.value() : 0;
}

отправил вопрос экспертам
тем временем можно посмотреть на
http://root.cern.ch/root/htmldoc/TRandom.html
там 4 разных генераратора + unuran

anonymous (*) (06.10.2008 10:06:34) ответил

http://www.kernel.org/doc/Documentation/hw_random.txt
http://packages.ubuntu.com/ru/hardy/rng-tools

Благодарю всех ответивших и заинтересовавшихся. Теперь точно знаю, что дело в каких-то особенностях моей системы, так что буду копать дальше в этом направлении.