Jaki jest najszybszy sposób na wygenerowanie pliku tekstowego 1 GB zawierającego losowe cyfry?

Próbowałem skryptu bash, ale utworzenie prostego pliku o rozmiarze 1 MB trwało zbyt długo. Myślę, że odpowiedź polega na użyciu /dev/randomlub /dev/urandom, ale inne posty tutaj pokazują tylko, jak dodawać wszelkiego rodzaju dane do pliku przy użyciu tych rzeczy, ale chcę dodać tylko liczby.

Czy istnieje więc polecenie, którego można użyć do utworzenia losowego pliku o rozmiarze 1 GB zawierającego tylko liczby od 0 do 9?

Edycja: Chcę, aby wynik był mniej więcej taki

0 1 4 7 ..... 9
8 7 5 8 ..... 8
....
....
8 7 5 3 ..... 3

Zakres wynosi od 0 do 9, co oznacza tylko cyfry 0, 1, 2, 3, 4, 5, 6, 7, 8 i 9. Potrzebuję też ich oddzielenia spacjami i 100 na linię, aż do nliczby linii. To coś, co mnie nie obchodzi, chcę, aby mój ostateczny rozmiar wynosił 1 GB.

Edycja: Używam Ubuntu 16.04 LTS

Jest to częściowo trafna odpowiedź ze względu na tytuł pytania.

Kiedy szukasz „najszybszego sposobu na ...” , odpowiedzią jest prawie zawsze jakieś specjalistyczne narzędzie. Te „odpowiedzi” pokazują jedno z takich narzędzi, abyś mógł eksperymentować.

To nie jest poważna odpowiedź, ponieważ nie powinieneś szukać specjalistycznych narzędzi do prac, które wykonujesz tylko raz lub bardzo rzadko. Widzisz, spędzasz więcej czasu na szukaniu narzędzi i poznawaniu ich, niż na robieniu różnych rzeczy. Powłoki i narzędzia takie jak bashi awknie są najszybsze, ale zwykle można napisać linijkę, aby osiągnąć zadanie, spędzając tylko kilka sekund. perlMożna również użyć lepszych języków skryptowych , chociaż krzywa uczenia się perljest bardzo stroma i waham się polecić ją do takich celów, ponieważ traumatyzują mnie okropne projekty Perla. pythonz drugiej strony jest nieco utrudniony ze względu na dość wolne operacje we / wy; jest to jednak problem tylko podczas filtrowania lub generowania gigabajtów danych.

W każdym razie następujący przykładowy program C89 (który wykorzystuje POSIX.1 dla zegara o wyższej dokładności tylko, jeśli jest dostępny) powinien osiągnąć szybkość generowania około 100 MB / s (testowany w systemie Linux na laptopie z procesorem Intel i5-4200U, przesyłając dane wyjściowe do /dev/null), używając całkiem dobrego generatora liczb pseudolosowych. (Dane wyjściowe powinny przejść wszystkie testy BigCruncha, z wyjątkiem testu MatrixRank, ponieważ kod używa xorshift64 * i metody wykluczania, aby uniknąć popychania cyfr).

decimal-digits.c:

#include <stdlib.h>
#include <stdint.h>
#include <string.h>
#include <locale.h>
#include <ctype.h>
#include <stdio.h>
#include <errno.h>
#include <time.h>

/* This program is licensed under the CC0 license,
       https://creativecommons.org/publicdomain/zero/1.0/
   In other words, this is dedicated to the public domain.
   There are no warranties either, so if something breaks,
   you only have yourself to blame.
*/

#if _POSIX_C_SOURCE-199309 >= 0
static uint64_t time_seed(void)
{
    struct timespec  ts;

    if (clock_gettime(CLOCK_REALTIME, &ts))
        return (uint64_t)time(NULL);

    return (uint64_t)ts.tv_sec
         ^ (((uint64_t)ts.tv_nsec) << 32);
}
#else
static uint64_t time_seed(void)
{
    return (uint64_t)time(NULL);
}
#endif

/* Preferred output I/O block size.
 * Currently, about 128k blocks yield
 * maximum I/O throughput on most devices.
 * Note that this is a heuristic value,
 * and may be increased in the future.
*/
#ifndef  IO_BLOCK_SIZE
#define  IO_BLOCK_SIZE  262144
#endif

/* This is the Xorshift* pseudo-random number generator.
 * See https://en.wikipedia.org/wiki/Xorshift#xorshift.2A
 * for details. This is an incredibly fast generator that
 * passes all but the MatrixRank test of the BigCrush
 * randomness test suite, with a period of 2^64-1.
 * Note that neither xorshift_state, nor the result of
 * this function, will ever be zero.
*/
static uint64_t xorshift_state;

static uint64_t xorshift_u64(void)
{
    xorshift_state ^= xorshift_state >> 12;
    xorshift_state ^= xorshift_state << 25;
    xorshift_state ^= xorshift_state >> 27;
    return xorshift_state * UINT64_C(2685821657736338717);
}

/* This function returns a number between (inclusive)
 * 0 and 999,999,999,999,999,999 using xorshift_u64()
 * above, using the exclusion method. Thus, there is
 * no bias in the results, and each digit should be
 * uniformly distributed in 0-9.
*/
static uint64_t quintillion(void)
{
    uint64_t result;

    do {
        result = xorshift_u64() & UINT64_C(1152921504606846975);
    } while (!result || result > UINT64_C(1000000000000000000));

    return result - UINT64_C(1);
}

/* This function returns a single uniformly random digit.
*/
static unsigned char digit(void)
{
    static uint64_t       digits_cache = 0;
    static unsigned char  digits_cached = 0;
    unsigned char         retval;

    if (!digits_cached) {
        digits_cache = quintillion();
        digits_cached = 17; /* We steal the first one! */
    } else
        digits_cached--;

    retval = digits_cache % (uint64_t)(10);
    digits_cache /= (uint64_t)(10);

    return retval;
}

static int parse_ulong(const char *src, unsigned long *to)
{
    const char   *end = src;
    unsigned long value;

    if (!src)
        return errno = EINVAL;

    errno = 0;
    value = strtoul(src, (char **)&end, 0);
    if (errno)
        return errno;

    if (end == src)
        return errno = EINVAL;
    while (*end)
        if (isspace(*end))
            end++;
        else
            return errno = EINVAL;

    if (to)
        *to = value;
    return 0;
}

int main(int argc, char *argv[])
{
    unsigned long lines, cols, line, col, seed;

    /* When parsing the command-line parameters,
     * use locale conventions. */
    setlocale(LC_ALL, "");

    /* Standard output should be fully buffered, if possible.
     * This only affects output speed, so we're not too worried
     * if this happens to fail. */
    (void)setvbuf(stdout, NULL, _IOFBF, (size_t)IO_BLOCK_SIZE);

    if (argc < 3 || argc > 4 || !strcmp(argv[1], "-h") || !strcmp(argv[1], "--help")) {
        fprintf(stderr, "\n");
        fprintf(stderr, "Usage: %s [ -h | --help ]\n", argv[0]);
        fprintf(stderr, "       %s COLS LINES [ SEED ]\n", argv[0]);
        fprintf(stderr, "\n");
        fprintf(stderr, "This program generates random decimal digits\n");
        fprintf(stderr, "0 - 9, separated by spaces, COLS per line,\n");
        fprintf(stderr, "LINES lines.  In total, COLS*LINES*2 bytes\n");
        fprintf(stderr, "will be used.\n");
        fprintf(stderr, "\n");
        fprintf(stderr, "SEED is the optional seed for the Xorshift64*\n");
        fprintf(stderr, "pseudo-random number generator used in this program.\n");
        fprintf(stderr, "If omitted, current time is used as the seed.\n");
        fprintf(stderr, "\n");
        return EXIT_SUCCESS;
    }

    if (parse_ulong(argv[1], &cols) || cols < 1UL) {
        fprintf(stderr, "%s: Invalid number of digits per line.\n", argv[1]);
        return EXIT_FAILURE;
    }
    if (parse_ulong(argv[2], &lines) || lines < 1UL) {
        fprintf(stderr, "%s: Invalid number of lines.\n", argv[2]);
        return EXIT_FAILURE;
    }

    if (argc > 3) {
        if (parse_ulong(argv[3], &seed)) {
            fprintf(stderr, "%s: Invalid Xorshift64* seed.\n", argv[3]);
            return EXIT_FAILURE;
        }
    } else
        seed = time_seed();

    /* Since zero seed is invalid, we map it to ~0. */
    xorshift_state = seed;
    if (!xorshift_state)
        xorshift_state = ~(uint64_t)0;

    /* Discard first 1000 values to make the initial values unpredictable. */
    for (col = 0; col < 1000; col++)
        xorshift_u64();

    for (line = 0UL; line < lines; line++) {
        fputc('0' + digit(), stdout);
        for (col = 1UL; col < cols; col++) {
            fputc(' ', stdout);
            fputc('0' + digit(), stdout);
        }
        fputc('\n', stdout);

        /* Check for write errors. */
        if (ferror(stdout))
            return EXIT_FAILURE;
    }

    return EXIT_SUCCESS;
}

Możemy uczynić to znacznie szybszym, jeśli przejdziemy do bufora linii i fwrite()raz, zamiast wypisywać każdą cyfrę na raz. Zauważ, że nadal utrzymujemy strumień w pełni buforowany, aby uniknąć zapisów częściowych (innych niż potęga dwóch), jeśli wyjście jest urządzeniem blokowym.

#include <stdlib.h>
#include <stdint.h>
#include <string.h>
#include <locale.h>
#include <ctype.h>
#include <stdio.h>
#include <errno.h>
#include <time.h>

#if _POSIX_C_SOURCE-199309 >= 0
static uint64_t time_seed(void)
{
    struct timespec  ts;

    if (clock_gettime(CLOCK_REALTIME, &ts))
        return (uint64_t)time(NULL);

    return (uint64_t)ts.tv_sec
         ^ (((uint64_t)ts.tv_nsec) << 32);
}
#else
static uint64_t time_seed(void)
{
    return (uint64_t)time(NULL);
}
#endif

/* Preferred output I/O block size.
 * Currently, about 128k blocks yield
 * maximum I/O throughput on most devices.
 * Note that this is a heuristic value,
 * and may be increased in the future.
*/
#ifndef  IO_BLOCK_SIZE
#define  IO_BLOCK_SIZE  262144
#endif

/* This is the Xorshift* pseudo-random number generator.
 * See https://en.wikipedia.org/wiki/Xorshift#xorshift.2A
 * for details. This is an incredibly fast generator that
 * passes all but the MatrixRank test of the BigCrush
 * randomness test suite, with a period of 2^64-1.
 * Note that neither xorshift_state, nor the result of
 * this function, will ever be zero.
*/
static uint64_t xorshift_state;

static uint64_t xorshift_u64(void)
{
    xorshift_state ^= xorshift_state >> 12;
    xorshift_state ^= xorshift_state << 25;
    xorshift_state ^= xorshift_state >> 27;
    return xorshift_state * UINT64_C(2685821657736338717);
}

/* This function returns a number between (inclusive)
 * 0 and 999,999,999,999,999,999 using xorshift_u64()
 * above, using the exclusion method. Thus, there is
 * no bias in the results, and each digit should be
 * uniformly distributed in 0-9.
*/
static uint64_t quintillion(void)
{
    uint64_t result;

    do {
        result = xorshift_u64() & UINT64_C(1152921504606846975);
    } while (!result || result > UINT64_C(1000000000000000000));

    return result - UINT64_C(1);
}

/* This function returns a single uniformly random digit.
*/
static unsigned char digit(void)
{
    static uint64_t       digits_cache = 0;
    static unsigned char  digits_cached = 0;
    unsigned char         retval;

    if (!digits_cached) {
        digits_cache = quintillion();
        digits_cached = 17; /* We steal the first one! */
    } else
        digits_cached--;

    retval = digits_cache % (uint64_t)(10);
    digits_cache /= (uint64_t)(10);

    return retval;
}

static int parse_ulong(const char *src, unsigned long *to)
{
    const char   *end = src;
    unsigned long value;

    if (!src)
        return errno = EINVAL;

    errno = 0;
    value = strtoul(src, (char **)&end, 0);
    if (errno)
        return errno;

    if (end == src)
        return errno = EINVAL;
    while (*end)
        if (isspace(*end))
            end++;
        else
            return errno = EINVAL;

    if (to)
        *to = value;
    return 0;
}

int main(int argc, char *argv[])
{
    unsigned long lines, cols, line, col, seed;
    char         *oneline;

    /* When parsing the command-line parameters,
     * use locale conventions. */
    setlocale(LC_ALL, "");

    /* Standard output should be fully buffered, if possible.
     * This only affects output speed, so we're not too worried
     * if this happens to fail. */
    (void)setvbuf(stdout, NULL, _IOFBF, (size_t)IO_BLOCK_SIZE);

    if (argc < 3 || argc > 4 || !strcmp(argv[1], "-h") || !strcmp(argv[1], "--help")) {
        fprintf(stderr, "\n");
        fprintf(stderr, "Usage: %s [ -h | --help ]\n", argv[0]);
        fprintf(stderr, "       %s COLS LINES [ SEED ]\n", argv[0]);
        fprintf(stderr, "\n");
        fprintf(stderr, "This program generates random decimal digits\n");
        fprintf(stderr, "0 - 9, separated by spaces, COLS per line,\n");
        fprintf(stderr, "LINES lines.  In total, COLS*LINES*2 bytes\n");
        fprintf(stderr, "will be used.\n");
        fprintf(stderr, "\n");
        fprintf(stderr, "SEED is the optional seed for the Xorshift64*\n");
        fprintf(stderr, "pseudo-random number generator used in this program.\n");
        fprintf(stderr, "If omitted, current time is used as the seed.\n");
        fprintf(stderr, "\n");
        return EXIT_SUCCESS;
    }

    if (parse_ulong(argv[1], &cols) || cols < 1UL) {
        fprintf(stderr, "%s: Invalid number of digits per line.\n", argv[1]);
        return EXIT_FAILURE;
    }
    if (parse_ulong(argv[2], &lines) || lines < 1UL) {
        fprintf(stderr, "%s: Invalid number of lines.\n", argv[2]);
        return EXIT_FAILURE;
    }

    if (argc > 3) {
        if (parse_ulong(argv[3], &seed)) {
            fprintf(stderr, "%s: Invalid Xorshift64* seed.\n", argv[3]);
            return EXIT_FAILURE;
        }
    } else
        seed = time_seed();

    /* Since zero seed is invalid, we map it to ~0. */
    xorshift_state = seed;
    if (!xorshift_state)
        xorshift_state = ~(uint64_t)0;

    /* Discard first 1000 values to make the initial values unpredictable. */
    for (col = 0; col < 1000; col++)
        xorshift_u64();

    /* Allocate memory for a full line. */
    oneline = malloc((size_t)(2 * cols + 1));
    if (!oneline) {
        fprintf(stderr, "Not enough memory for %lu column buffer.\n", cols);
        return EXIT_FAILURE;
    }

    /* Set spaces and terminating newline. */
    for (col = 0; col < cols; col++)
        oneline[2*col + 1] = ' ';
    oneline[2*cols-1] = '\n';

    /* Not needed, but in case a code modification treats it as a string. */
    oneline[2*cols] = '\0';

    for (line = 0UL; line < lines; line++) {
        for (col = 0UL; col < cols; col++)
            oneline[2*col] = digit();

        if (fwrite(oneline, 2*cols, 1, stdout) != 1)
            return EXIT_FAILURE; 
    }

    /* Check for write errors. */
    if (ferror(stdout))
        return EXIT_FAILURE;

    return EXIT_SUCCESS;
}

Uwaga: oba przykłady zostały zredagowane 18.11.2016, aby zapewnić równomierny rozkład cyfr (zero jest wykluczone; patrz np. Tutaj dla porównania i szczegółów na temat różnych generatorów liczb pseudolosowych).

Kompiluj za pomocą na przykład

gcc -Wall -O2 decimal-digits.c -o decimal-digits

i opcjonalnie zainstaluj system dla /usr/binużycia

sudo install -o root -g root -m 0755 decimal-digits /usr/bin

Pobiera liczbę cyfr na linię i liczbę linii. Ponieważ 1000000000 / 100 / 2 = 5000000(pięć milionów; całkowita liczba bajtów podzielona przez kolumny podzielone przez 2), możesz użyć

./decimal-digits 100 5000000 > digits.txt

aby wygenerować gigabajt wielkości digits.txtzgodnie z życzeniem OP.

Zauważ, że sam program jest napisany bardziej z myślą o czytelności niż o wydajności. Moim zamiarem nie jest pokazanie wydajności kodu - i tak użyłbym POSIX.1 i niskopoziomowych I / O, zamiast ogólnych interfejsów C - ale abyś mógł łatwo zobaczyć, jaki jest balans przy wysiłku w tworzeniu dedykowanych narzędzi w porównaniu do ich wydajności, w porównaniu do skryptów jednowierszowych lub skryptletów z krótką powłoką lub awk.

Używanie biblioteki GNU C, wywoływanie fputc()funkcji dla każdego wyniku znaków pociąga za sobą bardzo mały narzut (pośredniego wywołania funkcji lub warunków - FILEinterfejs jest w rzeczywistości dość złożony i wszechstronny, widzisz). W tym konkretnym laptopie Intel Core i5-4200U przekierowanie wyjścia do /dev/nullpierwszej wersji (fputc) zajmuje około 11 sekund, podczas gdy wersja liniowa zajmuje tylko 1,3 sekundy.

Często zdarza mi się pisać takie programy i generatory tylko dlatego, że lubię grać z ogromnymi zestawami danych. Jestem dziwny w ten sposób. Na przykład napisałem kiedyś program do drukowania wszystkich skończonych dodatnich wartości zmiennoprzecinkowych IEEE-754 do pliku tekstowego, z wystarczającą precyzją, aby uzyskać dokładnie taką samą wartość podczas analizowania. Plik miał rozmiar kilku gigabajtów (być może około 4G); nie ma tak wielu skończonych pozytywów, floatjak mogłoby się wydawać. Użyłem tego do porównania implementacji, które czytają i analizują takie dane.

W przypadku normalnych przypadków użycia, takich jak OP, skrypty powłoki i skryptlety oraz jednowierszowe są lepszym podejściem. Mniej czasu poświęconego na wykonanie całego zadania. (Z wyjątkiem sytuacji, gdy potrzebują innego pliku każdego dnia lub wiele osób potrzebuje innego pliku, w którym - w rzadkich przypadkach - dedykowane narzędzie, takie jak powyżej, może uzasadnić wysiłek.)

To:

 LC_ALL=C tr '\0-\377' \
             '[0*25][1*25][2*25][3*25][4*25][5*25][6*25][7*25][8*25][9*25][x*]' \
    < /dev/urandom |
    tr -d x |
    fold -w 1 |
    paste -sd "$(printf '%99s\\n')" - |
    head -c1G

(zakładając, headże implementacja obsługuje -c) wydaje się być dość szybki w moim systemie.

trtłumaczy cały zakres bajtów (od 0 do 255, od 0 do 0377 ósemkowo): 25 pierwszych bajtów jako 0, 25 następnych jako 1 ... a następnie 25 9 pozostałych (250 do 255) na „x”, które następnie odrzuć (z tr -d x), ponieważ chcemy równomiernego rozkładu (zakładając, że /dev/urandomma on sam rozkład równomierny), a więc nie podawać stronniczości niektórym cyfrom.

To daje jedną cyfrę na 97% bajtów /dev/urandom. fold -w 1sprawia, że ​​jest to jedna cyfra na linię. paste -sjest wywoływany z listą separatorów, która składa się z 99 znaków spacji i jednego znaku nowej linii, tak aby mieć 100 cyfr oddzielonych spacją w każdym wierszu.

head -c1Gotrzyma pierwszy GiB (2 ³⁰ ) tego. Pamiętaj, że ostatni wiersz zostanie obcięty i nie będzie ograniczony. Możesz obciąć do 2 ³⁰ -1 i ręcznie dodać brakującą nową linię lub obciąć do 10 ⁹ bajtów zamiast tego, co stanowi 50 milionów z tych 200 bajtów linii ( head -n 50000000uczyniłoby to również polecenie standardowe / przenośne).

Te czasy (uzyskane zshw systemie czterordzeniowym) wskazują, gdzie spędzany jest czas procesora:

LC_ALL=C tr '\0-\377'  < /dev/urandom  0.61s user 31.28s system 99% cpu 31.904 total
tr -d x  1.00s user 0.27s system 3% cpu 31.903 total
fold -w 1  14.93s user 0.48s system 48% cpu 31.902 total
paste -sd "$(printf '%99s\\n')" -  7.23s user 0.08s system 22% cpu 31.899 total
head -c1G > /dev/null  0.49s user 1.21s system 5% cpu 31.898 total

Pierwszy trto szyjka butelki, przez większość czasu spędzonego w jądrze (przypuszczam, że do generowania liczb losowych). Czas jest mniej więcej zgodny z szybkością, z której mogę uzyskać bajty /dev/uramdom(około 19 Mb / s, a tutaj produkujemy 2 bajty na każde 0,97 bajta / dev / urandom z prędkością 32 Mb / s). foldwydaje się spędzać nieuzasadnioną ilość czasu procesora (15s) po prostu na wstawianie znaku nowej linii po każdym bajcie, ale to nie wpływa na ogólny czas, ponieważ działa na innym procesorze w moim przypadku (dodanie -bopcji sprawia, że ​​jest to nieco więcej wydajna, dd cbs=1 conv=unblockwydaje się lepszą alternatywą).

Możesz zlikwidować head -c1Gi ogolić się na kilka sekund, ustawiając limit rozmiaru pliku ( limit filesize 1024mz zshlub ulimit -f "$((1024*1024))"z większością innych powłok (w tym zsh)) zamiast w podpowłoce.

Można to poprawić, jeśli wyodrębnimy 2 cyfry dla każdego bajtu, ale potrzebowalibyśmy do tego innego podejścia. Powyższe jest bardzo wydajne, ponieważ trpo prostu wyszukuje każdy bajt w 256-bajtowej tablicy. Nie można tego zrobić dla 2 bajtów jednocześnie, a użycie takich rzeczy do hexdump -e '1/1 "%02u"'obliczenia tekstowej reprezentacji bajtu przy użyciu bardziej złożonych algorytmów byłoby droższe niż samo generowanie liczb losowych. Mimo to, podobnie jak w moim przypadku, masz rdzenie procesora, których czas można zaoszczędzić, może jednak uda się wygolić kilka sekund:

Z:

< /dev/urandom LC_ALL=C tr '\0-\377' '\0-\143\0-\143[x*]' |
  tr -d x |
  hexdump -n250000000 -ve '500/1 "%02u" "\n"' |
  fold -w1 |
  paste -sd "$(printf '%99s\\n')" - > /dev/null

Rozumiem (zauważ jednak, że tutaj jest to 1 000 000 000 bajtów w przeciwieństwie do 1 073 741 824):

LC_ALL=C tr '\0-\377' '\0-\143\0-\143[x*]' < /dev/urandom  0.32s user 18.83s system 70% cpu 27.001 total
tr -d x  2.17s user 0.09s system 8% cpu 27.000 total
hexdump -n250000000 -ve '500/1 "%02u" "\n"'  26.79s user 0.17s system 99% cpu 27.000 total
fold -w1  14.42s user 0.67s system 55% cpu 27.000 total
paste -sd "$(printf '%99s\\n')" - > /dev/null  8.00s user 0.23s system 30% cpu 26.998 total

Więcej czasu procesora ogółem, ale lepiej rozdzielony między moje 4 rdzenie procesora, więc w rezultacie zajmuje mniej czasu zegara ściennego. Wąskie gardło jest teraz hexdump.

Jeśli użyjemy ddzamiast liniowego fold, możemy faktycznie zmniejszyć ilość pracy hexdumpdo zrobienia i poprawić równowagę pracy między procesorami:

< /dev/urandom LC_ALL=C tr '\0-\377' '\0-\143\0-\143[x*]' |
  tr -d x |
  hexdump -ve '"%02u"' |
  dd bs=50000 count=10000 iflag=fullblock status=none cbs=1 conv=unblock |
  paste -sd "$(printf '%99s\\n')" -

(tutaj zakładając GNU dddla swoich iflag=fullblocki status=none) co daje:

LC_ALL=C tr '\0-\377' '\0-\143\0-\143[x*]' < /dev/urandom  0.32s user 15.58s system 99% cpu 15.915 total
tr -d x  1.62s user 0.16s system 11% cpu 15.914 total
hexdump -ve '"%02u"'  10.90s user 0.32s system 70% cpu 15.911 total
dd bs=50000 count=10000 iflag=fullblock status=none cbs=1 conv=unblock  5.44s user 0.19s system 35% cpu 15.909 total
paste -sd "$(printf '%99s\\n')" - > /dev/null  5.50s user 0.30s system 36% cpu 15.905 total

Powrót do generowania liczb losowych jest wąskim gardłem.

Teraz, jak wskazał @OleTange, jeśli masz opensslnarzędzie, możesz użyć go, aby uzyskać szybszy (szczególnie na procesorach, które mają instrukcje AES) pseudolosowy generator bajtów.

</dev/zero openssl enc -aes-128-ctr -nosalt -pass file:/dev/urandom

w moim systemie wyrzuca 15 razy więcej bajtów na sekundę niż /dev/urandom. (Nie mogę wypowiedzieć się na temat tego, jak to się porównuje pod względem kryptograficznie bezpiecznego źródła losowości, jeśli dotyczy to twojego przypadku użycia).

</dev/zero openssl enc -aes-128-ctr -nosalt -pass file:/dev/urandom 2> /dev/null | 
  LC_ALL=C tr '\0-\377' '\0-\143\0-\143[x*]' |
  tr -d x |
  hexdump -ve '"%02u"' |
  dd bs=50000 count=10000 iflag=fullblock status=none cbs=1 conv=unblock |
  paste -sd "$(printf '%99s\\n')" -

Teraz daje:

openssl enc -aes-128-ctr -nosalt -pass file:/dev/urandom < /dev/zero 2>   1.13s user 0.16s system 12% cpu 10.174 total
LC_ALL=C tr '\0-\377' '\0-\143\0-\143[x*]'  0.56s user 0.20s system 7% cpu 10.173 total
tr -d x  2.50s user 0.10s system 25% cpu 10.172 total
hexdump -ve '"%02u"'  9.96s user 0.19s system 99% cpu 10.172 total
dd bs=50000 count=10000 iflag=fullblock status=none cbs=1 conv=unblock  4.38s user 0.20s system 45% cpu 10.171 total
paste -sd "$(printf '%99s\\n')" - > /dev/null

z powrotem do hexdumpwąskiego gardła.

Ponieważ nadal mam wolne procesory, mogę uruchomić 3 z nich hexdumprównolegle.

</dev/zero openssl enc -aes-128-ctr -nosalt -pass file:/dev/urandom 2> /dev/null | 
  LC_ALL=C tr '\0-\377' '\0-\143\0-\143[x*]' |
  tr -d x |
  (hexdump -ve '"%02u"' <&3 & hexdump -ve '"%02u"' <&3 & hexdump -ve '"%02u"') 3<&0 |
  dd bs=50000 count=10000 iflag=fullblock status=none cbs=1 conv=unblock |
  paste -sd "$(printf '%99s\\n')" -

( <&3jest to potrzebne dla powłok innych niż zshstdin poleceń zamknięcia na / dev / null, gdy są uruchomione w tle).

Teraz do 6,2 sekundy, a moje procesory prawie w pełni wykorzystane.

Jeśli masz shufdostępne (najnowsze GNU coreutils), możesz to zrobić:

time shuf -r -n $((512*1024*1024)) -i 0-9 | paste -sd "$(printf '%99s\\n')" -

Na mojej maszynie wirtualnej jest to teraz nieco wolniej niż odpowiedź Stéphane'a o współczynnik 3: 4.

Jeśli nie potrzebujesz losowości o bardzo wysokiej jakości, a wystarczająca jest prawie równomierna dystrybucja, możesz iść naprawdę szybko, szczególnie na nowoczesnym procesorze z wydajnymi wektorami całkowitymi SIMD, takimi jak x86 z SSE2 lub AVX2.

To jest jak odpowiedź @ NominalAnimal, ponieważ oboje mieliśmy ten sam pomysł, ale ręcznie wektoryzowaliśmy dla x86. (A przy liczbach losowych gorszej jakości, ale prawdopodobnie wystarczających do wielu przypadków użycia). Działa to około 15 lub 30 razy szybciej niż kod @ Nominal, przy ~ 13 GB / s wyjścia ASCII na Intel Haswell 2,5 GHz Procesor z AVX2. To wciąż mniej niż teoretyczna maksymalna przepustowość pamięci głównej (dwukanałowa pamięć DDR3-1600 wynosi około 25,6 GB / s), ale tak naprawdę zapisywałem czas do / dev / null, więc w rzeczywistości po prostu przepisałem bufor, który pozostaje gorący w pamięci podręcznej. Skylake powinien uruchomić ten sam kod znacznie szybciej niż Haswell (patrz na dole tej odpowiedzi).

Zakładając, że faktycznie masz wąskie gardło we / wy na dysku lub gdzieś to potokujesz, szybka implementacja oznacza, że ​​twój procesor nie musi nawet taktować się wyżej niż bezczynnie. Zużywa znacznie mniej energii całkowitej do uzyskania wyniku. (Żywotność baterii / ciepło / globalne ocieplenie.)

Jest to tak szybkie, że prawdopodobnie nie chcesz zapisywać go na dysku. Po prostu ponownie wygeneruj w razie potrzeby (z tego samego materiału siewnego, jeśli chcesz ponownie te same dane). Nawet jeśli chcesz go przesłać do wielowątkowego procesu, który może korzystać ze wszystkich procesorów, uruchomienie tego w celu przesłania danych do niego spowoduje pozostawienie go w pamięci podręcznej L3 (i pamięci podręcznej L2 na rdzeniu, który go napisał), i użyj tak bardzo mały czas procesora. (Należy jednak pamiętać, że /dev/nullprzesyłanie strumieniowe dodaje dużo narzutu w porównaniu do pisania . W Skylake i7-6700k, przesyłanie do wc -club innego programu, który tylko czyta + odrzuca dane wejściowe, jest około 8 razy wolniejsze niż zapisywanie do/dev/null i wykorzystuje tylko 70% Procesor, ale to wciąż 4,0 GB / s na procesorze 3,9 GHz.

Ponowne wygenerowanie jest szybsze niż ponowne odczytanie go nawet z szybkiego dysku SSD podłączonego przez PCIe, ale IDK, jeśli jest bardziej energooszczędny (multiplikator wektor-liczba jest nadal zajęty i prawdopodobnie jest dość energochłonny, podobnie jak inne AVX2 256 ALU wektorów). OTOH, nie wiem, ile czasu procesora czytającego z dysku zabrałoby coś, co maksymalizowało wszystkie rdzenie przetwarzające to wejście. Domyślam się, że przełącznik kontekstowy do ponownego generowania w porcjach 128k może być konkurencyjny w stosunku do uruchamiania kodu systemu plików / pagecache i przydzielania stron do odczytu danych z dysku. Oczywiście, jeśli jest już gorąco w pamięci podręcznej, to po prostu jest zapadający w pamięć. OTOH, piszemy już o tak szybkim jak memcpy! (która musi rozdzielić przepustowość pamięci głównej na odczyt i zapis). (Należy również pamiętać, że zapisywanie w pamięci, że „rep movsb(zoptymalizowany memcpy i memset w mikrokodzie, co pozwala uniknąć RFO, ponieważ Andy Glew zaimplementował go w P6 (Pentium Pro )).

Jak dotąd jest to tylko dowód koncepcji, a obsługa nowej linii jest tylko w przybliżeniu poprawna. Jest źle na końcach bufora power-of-2. Więcej czasu na rozwój. Jestem pewien, że mógłbym znaleźć bardziej skuteczny sposób wstawiania znaków nowej linii, który jest również dokładnie poprawny, z co najmniej tak niskim narzutem (w porównaniu do wypisywania tylko spacji). Myślę, że jest to około 10 do 20%. Interesuje mnie tylko to, jak szybko możemy uruchomić ten bieg, a nie faktyczna jego dopracowana wersja, więc zostawię tę część jako ćwiczenie dla czytelnika, z komentarzami opisującymi niektóre pomysły.

Na Haswell i5 z maksymalnym turbodoładowaniem 2,5 GHz, z pamięcią RAM DDR3-1600 MHz , czasowo generuje 100GiB, ale został zmniejszony. (Czasowo na cygwin64 na Win10 z gcc5.4 -O3 -march=native, pominięty, -funroll-loopsponieważ miałem dość czasu na uzyskanie przyzwoitego czasu na tym pożyczonym laptopie. Powinienem właśnie uruchomić Linuksa na USB).

pisanie do / dev / null, chyba że określono inaczej.

• James Hollis: (nie testowano)
• Nominalna wersja fwrite: ~ 2.21s
• to (SSE2): ~ 0,142 s (nieskalowane czasy = rzeczywiste = 14,222 s, użytkownik = 13,999 s, sys = 0,187 s).
• to (AVX-128): ~ 0.140s
• to (AVX2): ~ 0,073s (nieskalowane: real = 0m7,291s, użytkownik = 0m7,125s, sys = 0m0,155s).
• to (AVX2) przesyłanie cygwin do wc -cbufora o rozmiarze 128 kB: 0,32 s z procesorem 2,38 GHz (maks. dwurdzeniowe turbo). (nieskalowane czasy: real = 32.466s użytkownik = 11.468s sys = 41.092s, w tym zarówno to, jak i wc). Jednak tylko połowa danych została skopiowana, ponieważ mój głupi program zakłada, że ​​zapis zajmuje pełny bufor, nawet jeśli tak nie jest, a cygwin write () robi tylko 64k na wywołanie do potoku.

W przypadku SSE2 jest to około 15 razy szybsze niż kod skalarny @Nominal Animal. Dzięki AVX2 jest około 30 razy szybszy. Nie wypróbowałem wersji kodu Nominal, która po prostu używa write()zamiast tego fwrite(), ale przypuszczalnie dla dużych buforów stdio zwykle nie przeszkadza . Jeśli kopiuje dane, spowodowałoby to spowolnienie.

Czasy do wyprodukowania 1 GB danych na Core2Duo E6600 (Merom 2.4GHz, 32kB prywatny L1, 4MiB współdzielone pamięci podręczne L2), DDR2-533MHz w 64-bitowym Linuksie 4.2 (Ubuntu 15.10). Nadal używając rozmiaru bufora 128kiB do write (), nie zbadałem tego wymiaru.

pisanie do / dev / null, chyba że określono inaczej.

• (SSE2) to z obsługą nowej linii i 4 wektorami cyfr z każdego wektora losowych bajtów: 0,183 s (czas wykonania 100 GiB w 18,3 s, ale podobne wyniki dla przebiegów 1 GiB). 1,85 instrukcji na cykl.
• (SSE2) to, przesyłanie do wc -c: 0,593 s (nieskalowane: rzeczywiste = 59,266s użytkownik = 20,148s sys = 1m6,548s, w tym czas procesora wc). Taka sama liczba wywołań systemowych write () jak w przypadku cygwin, ale faktycznie przesyłanie wszystkich danych, ponieważ Linux obsługuje wszystkie 128k zapisu () do potoku.
• NominalAnimal jest fwrite()wersja (gcc5.2 -O3 -march=native), należy uruchomić z ./decdig 100 $((1024*1024*1024/200)) > /dev/null: 3.19s +/- 0,1%, przy 1,40 instrukcji na cykl. -funrollowe pętle zrobiły może małą różnicę. clang-3.8 -O3 -march=native: 3,42s +/- 0,1%
• Nominalny potok fwritedo wc -c: rzeczywisty = 3,980s użytkownik = 3,176s sys = 2,080s
• Wersja liniowa Jamesa Hollisa ( clang++-3.8 -O3 -march=native): 22,885s +/- 0,07%, z 0,84 instrukcjami na cykl. (g ++ 5.2 był nieco wolniejszy: 22,98s). Pisanie tylko jednej linii na raz prawdopodobnie bolało znacznie.
• Stéphane Chazelas tr < /dev/urandom | ...: real = 41.430s użytkownik = 26,832s sys = 40.120s. trprzez większość czasu zajmował się samym rdzeniem procesora, spędzając prawie cały czas w sterowniku jądra, generując losowe bajty i kopiując je do potoku. Drugi rdzeń na tym dwurdzeniowym komputerze działał przez resztę rurociągu.
• time LC_ALL=C head -c512M </dev/urandom >/dev/null: tzn. po prostu odczytuje tyle losowości bez orurowania: real = 35.018s użytkownik = 0.036s sys = 34.940s.
• Program perla Lưu Vĩnh Phúc (perl v5.20.2 z Ubuntu15.10)
  LANG=en_CA.UTF-8:: real = 4m32.634s użytkownik = 4m3.288s sys = 0m29.364.
  LC_ALL=C LANG=C: real = 4m18.637s użytkownik = 3m50.324s sys = 0m29.356s Wciąż bardzo powoli.

• (SSE2) to bez obsługi nowego wiersza i albo 3 lub 4 wektory cyfr z każdego wektora losowych bajtów (prawie dokładnie taka sama prędkość: dig3 = v%10krok dotyczy progu rentowności na tym CWU): 0,166 s (1,82 instrukcji na cykl) . Jest to w zasadzie dolna granica tego, do czego możemy się zbliżyć dzięki idealnie wydajnej obsłudze nowej linii.

• (SSE2) Stara wersja tego bez obsługi nowego wiersza, ale tylko jedna cyfra na element uint16_t przy użyciu v%10, 0,222 sekundy +/- 0,4%, 2,12 instrukcji na cykl. (Skompilowane z gcc5.2 -march=native -O3 -funroll-loops. Pętle Unroll pomagają w tym kodzie na tym sprzęcie. Nie używaj go na ślepo, szczególnie w przypadku dużych programów).
• (SSE2) Stara wersja tego, zapis do pliku (na RAID10f2 z 3 szybkich magnetycznych dysków twardych, niezbyt zoptymalizowanych do zapisu): ~ 4 sekundy. Mógłby pójść szybciej przez ulepszenie ustawień bufora we / wy jądra, aby pozwolić na znacznie więcej brudnych danych przed blokami write (). Czas „systemowy” wciąż wynosi ~ 1,0 sekundy, czyli znacznie więcej niż czas „użytkownika”. W tym starym systemie z powolną pamięcią RAM DDR2-533 jądro zapamiętuje dane do pamięci podręcznej i uruchamia funkcje XFS ~ 4x dłużej niż w mojej pętli, aby zapisywać je ponownie w buforze, który pozostaje gorący Pamięć podręczna.

Jak to jest zrobione

Szybki PRNG jest oczywiście niezbędny. xorshift128 + można wektoryzować, dzięki czemu masz dwa lub cztery 64-bitowe generatory równolegle w elementach wektora SIMD. Każdy krok tworzy pełny wektor losowych bajtów. ( Tutaj implementacja AVX2 256b z wbudowanymi procesorami Intela ). Wybrałem to w porównaniu z wyborem xorshift * Nominal, ponieważ 64-bitowe zwielokrotnienie liczb całkowitych wektorów jest możliwe tylko w SSE2 / AVX2 z technikami o zwiększonej precyzji .

Biorąc pod uwagę wektor losowych bajtów, możemy pokroić każdy 16-bitowy element na wiele cyfr dziesiętnych. Produkujemy wiele wektorów 16-bitowych elementów, z których każdy jest jedną cyfrą ASCII + spacją ASCII . Przechowujemy to bezpośrednio w naszym buforze wyjściowym.

Moja oryginalna wersja właśnie x / 6554pobierała jedną losową cyfrę z każdego elementu wektora uint16_t. Zawsze wynosi od 0 do 9 włącznie. Jest tendencyjny 9, ponieważ (2^16 -1 ) / 6554wynosi tylko 9.99923. (6554 = Ceil ((2 ^ 16-1) / 10), co zapewnia, że ​​iloraz jest zawsze <10.)

x/6554można obliczyć z jednym pomnożeniem przez stałą „magiczną” ( odwrotność stałego punktu ) i prawidłowe przesunięcie wyniku wysokiej połowy. To najlepszy przypadek dzielenia przez stałą; niektóre dzielniki wymagają więcej operacji, a podpisany podział wymaga dodatkowej pracy. x % 10ma podobny błąd i nie jest tak tani w obliczeniach. (wyjście asm gcc jest równoważne x - 10*(x/10), tj. dodatkowe zwielokrotnienie i odjęcie na górze podziału za pomocą modularnego odwrotności multiplikatywnej). Również najniższy bit xorshift128 + nie jest tak wysokiej jakości , więc dzielenie się, aby wziąć entropię z wysokich bitów, jest lepsze ( dla jakości, jak również prędkości) niż modulo, aby pobrać entropię z małych bitów.

Możemy jednak użyć więcej entropii w każdym uint16_t, patrząc na małe cyfry dziesiętne, takie jak digit()funkcja @ Nominal . Aby uzyskać maksymalną wydajność, postanowiłem wziąć 3 małe cyfry dziesiętne i x/6554, aby zapisać jeden PMULLW i PSUBW (i prawdopodobnie niektóre MOVDQA) w porównaniu z opcją wyższej jakości, biorąc 4 niskie cyfry dziesiętne. Niskie 3 cyfry dziesiętne mają nieznaczny wpływ na x / 6554, więc istnieje pewna korelacja między cyframi z tego samego elementu (separacja 8 lub 16 cyfr na wyjściu ASCII, w zależności od szerokości wektora).

Myślę, że gcc dzieli przez 100 i 1000, zamiast dłuższego łańcucha, który sukcesywnie dzieli się przez 10, więc prawdopodobnie nie skraca znacząco długości łańcucha zależności nie przenoszonej przez pętlę, który daje 4 wyniki z każdego wyjścia PRNG. port0 (mnożenie i przesuwanie wektora) jest wąskim gardłem ze względu na modułowe odwrotne multiplikacje i przesunięcia w xorshift +, więc zdecydowanie warto zapisać wielokrotność wektora.

xorshift + jest tak szybki, że nawet użycie tylko ~ 3,3 bitów losowości na każde 16 (tj. 20% wydajności) nie jest dużo wolniejsze niż dzielenie go na wiele cyfr dziesiętnych. Przybliżamy jedynie rozkład równomierny, ponieważ odpowiedź ta koncentruje się na szybkości, o ile jakość nie jest tak zła.

Wszelkie zachowania warunkowe utrzymujące zmienną liczbę elementów wymagałyby znacznie więcej pracy. (Ale może nadal być to nieco wydajne przy użyciu technik upakowywania po lewej stronie SIMD . Jednak staje się to mniej wydajne dla małych rozmiarów elementów; gigantyczne tabele wyszukiwania z maską losową nie są wykonalne i nie ma tasowania z przecinaniem linii AVX2 z mniejszym niż 32- elementy bitowe. Wersja PSHUFB 128b może nadal być w stanie wygenerować maskę w locie za pomocą BMI2 PEXT / PDEP, podobnie jak w przypadku AVX2 z większymi elementami , ale jest to trudne, ponieważ 64-bitowa liczba całkowita zawiera tylko 8 bajtów. Godbolt link w tej odpowiedzi znajduje się kod, który może działać w przypadku większej liczby elementów).

Jeśli opóźnienie RNG jest wąskim gardłem, moglibyśmy iść jeszcze szybciej, uruchamiając równolegle dwa wektory generatorów, naprzemiennie z których korzystamy. Kompilator nadal może łatwo przechowywać wszystko w rejestrach w rozwiniętej pętli, co pozwala na równoległe działanie dwóch łańcuchów zależności.

W obecnej wersji, dzieląc dane wyjściowe PRNG, faktycznie wąskie gardło w przepustowości portu 0, a nie w opóźnieniu PRNG, więc nie ma takiej potrzeby.

Kod: wersja AVX2

Pełna wersja z większą ilością komentarzy na temat eksploratora kompilatora Godbolt .

Niezbyt schludny, przepraszam, muszę iść spać i chcę to opublikować.

Aby uzyskać wersję SSE2, s/_mm256/_mm, s/256/128/, s/v16u/v8u/, i zmienić vector_size(32)do 16. Również zmienić przyrost nowej linii od 16 do 4 * 4 * 8. (Tak jak powiedziałem, kod jest nieporządny i nie jest dobrze skonfigurowany do kompilacji dwóch wersji. Nie planowałem początkowo tworzenia wersji AVX2, ale potem naprawdę chciałem przetestować procesor Haswell, do którego miałem dostęp.)

#include <immintrin.h>
#include <unistd.h>
#include <stdint.h>
#include <stdio.h>
//#include <string.h>

// This would work equally fast 128b or 256b at a time (AVX2):
// https://stackoverflow.com/questions/24001930/avx-sse-version-of-xorshift128
struct rngstate256 {
    __m256i state0;
    __m256i state1;
};

static inline __m256i xorshift128plus_avx2(struct rngstate256 *sp)
{
    __m256i s1 = sp->state0;
    const __m256i s0 = sp->state1;
    sp->state0 = s0;
    s1 = _mm256_xor_si256(s1, _mm256_slli_epi64(s1, 23));
    __m256i state1new = _mm256_xor_si256(_mm256_xor_si256(_mm256_xor_si256(s1, s0),
                            _mm256_srli_epi64(s1, 18)),
                      _mm256_srli_epi64(s0, 5));
    sp->state1 = state1new;
    return _mm256_add_epi64(state1new, s0);
}



// GNU C native vectors let us get the compiler to do stuff like %10 each element
typedef unsigned short v16u __attribute__((vector_size(32)));

__m256i* vec_store_digit_and_space(__m256i vec, __m256i *restrict p)
{
    v16u v = (v16u)vec;
    v16u ten = (v16u)_mm256_set1_epi16(10);

    v16u divisor = (v16u)_mm256_set1_epi16(6554);  // ceil((2^16-1) / 10.0)
    v16u div6554 = v / divisor;      // Basically the entropy from the upper two decimal digits: 0..65.
    // Probably some correlation with the modulo-based values, especially dig3, but we do this instead of
    // dig4 for more ILP and fewer instructions total.

    v16u dig1 = v % ten;
    v /= ten;
    v16u dig2 = v % ten;
    v /= ten;
    v16u dig3 = v % ten;
    //  dig4 would overlap much of the randomness that div6554 gets

    const v16u ascii_digitspace = (v16u)_mm256_set1_epi16( (' '<<8) | '0');

    v16u *vecbuf = (v16u*)p;
    vecbuf[0] = div6554 | ascii_digitspace;
    vecbuf[1] = dig1    | ascii_digitspace;
    vecbuf[2] = dig2    | ascii_digitspace;
    vecbuf[3] = dig3    | ascii_digitspace;
    return p + 4;  // always a constant number of full vectors
}


void random_decimal_fill_buffer(char *restrict buf, size_t len, struct rngstate256 *restrict rngstate)
{
    buf = __builtin_assume_aligned(buf, 32);

    // copy to a local so clang can keep state in register, even in the non-inline version
    // restrict works for gcc, but apparently clang still thinks that *buf might alias *rngstate
    struct rngstate256 rng_local = *rngstate;

    __m256i *restrict p = (__m256i*restrict)buf;
    __m256i *restrict endbuf = (__m256i*)(buf+len);
    static unsigned newline_pos = 0;
    do {
        __m256i rvec = xorshift128plus_avx2(&rng_local);
        p = vec_store_digit_and_space(rvec, p);  // stores multiple ASCII vectors from the entropy in rvec

#if 1
        // this is buggy at the end or start of a power-of-2 buffer:
        // usually there's a too-short line, sometimes a too-long line
        const unsigned ncols = 100;
        newline_pos += 4*16;
        if (newline_pos >= ncols) {
            newline_pos -= ncols;
            char *cur_pos = (char*)p;
            *(cur_pos - newline_pos*2 - 1) = '\n';
        }
#endif
        // Turning every 100th space into a newline.
        // 1) With an overlapping 1B store to a location selected by a counter.  A down-counter would be more efficient
        // 2) Or by using a different constant for ascii_digitspace to put a newline in one element

        // lcm(200, 16) is 400 bytes, so unrolling the loop enough to produce two full lines makes a pattern of full vectors repeat
        // lcm(200, 32) is 800 bytes
        // a power-of-2 buffer size doesn't hold a whole number of lines :/
        // I'm pretty sure this can be solved with low overhead, like maybe 10% at worst.
    } while(p <= endbuf-3);

    *rngstate = rng_local;
}



#define BUFFER_SIZE (128 * 1024)
const static size_t bufsz = BUFFER_SIZE;
__attribute__((aligned(64))) static char static_buf[BUFFER_SIZE];

int main(int argc, char *argv[])
{
    // TODO: choose a seed properly.  (Doesn't affect the speed)
    struct rngstate256 xorshift_state = {
      _mm256_set_epi64x(123, 456, 0x123, 0x456),
      _mm256_set_epi64x(789, 101112, 0x789, 0x101112)
    };

    for (int i=0; i < 1024ULL*1024*1024 / bufsz * 100; i++) {
        random_decimal_fill_buffer(static_buf, bufsz, &xorshift_state);
        size_t written = write(1, static_buf, bufsz);
        (void)written;
        //fprintf(stderr, "wrote %#lx of %#lx\n", written, bufsz);
    }

}

Kompiluj za pomocą gcc, clang lub ICC (lub mam nadzieję, że jakikolwiek inny kompilator, który rozumie dialekt GNU C C99 i wewnętrzne cechy Intela). Rozszerzenia wektorów GNU C są bardzo wygodne, aby kompilator generował magiczne liczby dla dzielenia / modulo przy użyciu modularnych odwrotności multiplikatywnych, a okazjonalne __attribute__s są przydatne.

Można to zapisać przenośnie, ale zajmie to więcej kodu.

Uwagi dotyczące wydajności:

Nakładający się sklep do wstawiania nowych linii ma znaczny narzut, aby zdecydować, gdzie go umieścić (nieprzewidywalne rozgałęzienia i wąskie gardła nakładki na Core2), ale sam sklep nie ma wpływu na wydajność. Komentowanie tylko tej instrukcji sklepu w asmie kompilatora (pozostawiając wszystkie rozgałęzienia bez zmian) pozostawiło wydajność Core2 całkowicie niezmienioną, a powtarzane przebiegi dały ten sam czas do +/- mniej niż 1%. Doszedłem więc do wniosku, że bufor / pamięć podręczna radzą sobie z tym dobrze.

Mimo to użycie pewnego rodzaju okna obrotowego ascii_digitspacez jednym elementem o nowej linii może być jeszcze szybsze, jeśli rozwiniemy się na tyle, że znikną jakiekolwiek liczniki / rozgałęzienia.

Zapisywanie do / dev / null jest w zasadzie brakiem operacji, więc bufor prawdopodobnie pozostaje gorący w pamięci podręcznej L2 (256 kB na rdzeń w Haswell). Oczekuje się idealnego przyspieszenia z wektorów 128b do wektorów 256b: nie ma dodatkowych instrukcji, a wszystko (łącznie ze sklepami) dzieje się z podwójną szerokością. Jednak gałąź wstawiania nowej linii jest pobierana dwa razy częściej. Niestety nie miałem czasu na konfigurację cygwina Haswella z tą częścią #ifdef.

2,5 GHz * 32B / 13,7 GB / s = 5,84 cykli na sklep AVX2 na Haswell. To całkiem nieźle, ale może być szybsze. Może w wywołaniach systemowych cygwin jest trochę narzutów, niż myślałem. Nie próbowałem komentować tych w danych wyjściowych asm kompilatora (co zapewni, że nic nie zostanie zoptymalizowane).

Pamięć podręczna L1 może obsługiwać jeden magazyn 32B na zegar, a L2 nie jest znacznie mniejszą przepustowością (chociaż większe opóźnienie).

Kiedy spojrzałem na IACA kilka wersji temu (bez rozgałęzienia dla nowych linii, ale otrzymując tylko jeden wektor ASCII na wektor RNG), przewidywałem coś w rodzaju jednego sklepu wektorowego 32B na 4 lub 5 zegarów.

Miałem nadzieję przyspieszyć wydobywanie większej ilości danych z każdego wyniku RNG, na podstawie samego spojrzenia na asm, biorąc pod uwagę przewodniki Agner Fog i inne zasoby optymalizacyjne, do których dodałem linki w wiki tagu SO x86 ).

Prawdopodobnie byłoby to znacznie szybsze na Skylake , gdzie mnożenie liczb całkowitych wektora i przesunięcie może działać na dwukrotnie większej liczbie portów (p0 / p1) w porównaniu do Haswella (tylko p0). Xorshift i ekstrakcja cyfr używają wielu przesunięć i mnożeń. ( Aktualizacja: Skylake działa na 3.02 IPC, co daje nam 3,77 cykli na 32-bajtowy sklep AVX2 , z czasem 0,030s na 1 GB iteracji, pisząc do /dev/nullLinux 4.15 na i7-6700k przy 3,9 GHz.

Do poprawnego działania nie wymaga trybu 64-bitowego . Wersja SSE2 jest równie szybka po kompilacji -m32, ponieważ nie potrzebuje bardzo wielu rejestrów wektorowych, a cała 64-bitowa matematyka jest wykonywana w wektorach, a nie w rejestrach ogólnego przeznaczenia.

W rzeczywistości jest nieco szybszy w trybie 32-bitowym na Core2, ponieważ makro-fuzja porównania / rozgałęzienia działa tylko w trybie 32-bitowym, więc jest mniej ulepszeń rdzenia poza kolejnością (18,3 s (1,85 instrukcji na zegar) vs 16,9 s (2,0 IPC)). Mniejszy rozmiar kodu, ponieważ nie ma przedrostków REX, pomaga również dekoderom Core2.

Ponadto niektóre ruchy wektorowe reg-reg są zastępowane obciążeniami, ponieważ nie wszystkie stałe są już ustalane w regach wektorowych. Ponieważ przepustowość ładowania z pamięci podręcznej L1 nie jest wąskim gardłem, to w rzeczywistości pomaga. (np. pomnożenie przez stały wektor set1(10): movdqa xmm0, xmm10/ pmullw xmm0, xmm1zamienia się w movdqa xmm0, [constant]/ pmullw xmm0, xmm1.) Ponieważ reg-reg MOVDQA wymaga portu ALU, konkuruje on z wykonaną pracą, ale obciążenie MOVDQA konkuruje tylko o szerokość pasma dekodowania interfejsu. (Posiadanie 4-bajtowego adresu w wielu instrukcjach anuluje wiele korzyści z zapisywania prefiksów REX.

Nie zdziwiłbym się, gdyby uratowanie ALU MOVDQA było źródłem prawdziwych korzyści, ponieważ frontend powinien nadążać za średnią 2.0 IPC.

Wszystkie te różnice znikają na Haswell, gdzie cała sprawa powinna przebiegać z odkodowanej pamięci podręcznej, jeśli nie z bufora sprzężenia zwrotnego. Makro-synteza gałęzi ALU + działa w obu trybach od Nehalem.

Oto rozwiązanie, które, mam nadzieję, jest łatwe do zrozumienia:

od -An -x /dev/urandom | tr -dc 0-9 | fold -w100 | awk NF=NF FS= | head -c1G

• odtworzy jednolity strumień cyfr szesnastkowych z /dev/random.
• trpozbywa się liter, zachowując tylko 0-9cyfry
• fold zapewnia, że ​​w wierszu jest 100 cyfr
• awk wstawia spacje do linii
• head obcina wejście do 1 gigabajta

Możesz użyć tego jotpolecenia:

jot -r 50000000 0 9 | fmt -w 200 > output.txt

Jest to podobne do metody Stéphane'a Chazelasa, jednak czytam 64 bity jednocześnie, aby poprawić wydajność. Dystrybucja jest nadal jednolita, ale teraz dostajesz 19 cyfr na każde 8 bajtów zamiast tylko 8 w najlepszym przypadku, jak wcześniej

perl -nle 'BEGIN{$/=\8; $,=" "}
           $n = unpack("Q");
           next if $n >= 10000000000000000000;
           $s = sprintf("%019u", $n);
           push @a, (split //, $s);
           if (@a >= 100) {print (splice @a, 0, 100);}' < /dev/urandom | head -c1G

Na platformie 32-bitowej za każdym razem będzie odczytywanych 9 cyfr zamiast 19.

W pewnym sensie zgadzam się z Nominal Animal na używanie skompilowanego języka programowania, jeśli potrzebujesz prędkości. Nie musisz jednak pisać własnego kodu RNG w C. C ++ 11 oferuje doskonałą Mersenne Twister jako część standardowej biblioteki.

#include <time.h>
#include <random>
#include <iostream>
using namespace std;

int main() {
    mt19937 gen(time(0)); 
    uniform_int_distribution<> dist(0,9);

    for(int j=0; j<5000000; j++){
        for (int i = 0; i < 99; i++) {  
            cout << dist(gen) << " ";
        }  
        cout << dist(gen) << endl;
    }
    return 0;
}

Powyższy kod jest dość prosty i zajmuje około minuty, gdy przesyłam dane wyjściowe do pliku. Możemy iść znacznie szybciej, tworząc ciąg wystarczająco duży na 100 cyfr i włamując do niego cyfry. To pozwala nam wywoływać cout na każdej linii, a nie na każdej cyfrze.

#include <time.h>
#include <random>
#include <iostream>
using namespace std;

int main() {
    mt19937 gen(time(0)); 
    uniform_int_distribution<> dist(0,9);

    char line[201];
    for(int i=1; i<199; i++)
        line[i] = ' ';
    line[199] = '\n';
    line[200] = 0;

    for(int j=0; j<5000000; j++){
        for (int i = 0; i < 199; i += 2) {  
            line[i] = dist(gen)+'0';
        }  
        cout << line;
    }
    return 0;
}

Ten kod zajmuje mojej maszynie około sześciu sekund. Pamiętaj, że to standardowe wyjście, więc potokuj go do pliku.

Mam kilka zastrzeżeń. Najpierw piszę to na komputerze z systemem Windows. Myślę, że wszystkie biblioteki są obecne w systemie Linux, ale jeśli się mylę, koniecznie zwróć na to uwagę.

Poza tym generuje dokładnie pół miliarda cyfr oddzielonych spacjami, co technicznie jest gigabajtem, ale może nie dokładnie tym, czego chciałeś. Wyprowadza 5 milionów linii, 100 cyfr na linię. Jeśli różnica jest ważna, możesz zwiększyć liczbę wierszy. W moim systemie Windows plik wydaje się być nieco większy niż 10 ^ 9 bajtów, co myślę, że ma to związek z dodatkowymi znakami nowej linii.

To zależy od twojej definicji „losowej”. Jeśli masz na myśli kryptograficznie losowe, musisz tylko zdobyć dobrą bibliotekę i ugryźć kulę, poczekać, aż się uruchomi.

Jeśli potrzebujesz czegoś, co wygląda dość losowo, oto prosty sposób:

1. Uzyskaj plik o długości kilku Gb. Twój ulubiony film będzie dobry.
2. Zgraj to, łatwy sposób na wyciśnięcie powtarzających się wzorów
3. Przejrzyj plik jednoznacznie (pół bajta) na raz. Każda wartość będzie wynosić od 0 do 15. Wyrzuć mniej niż 1 lub więcej niż 10. Odejmij 1 od każdego z pierwszych miliardów ocalałych i wypisz go jako cyfrę.

Uruchomienie na wolnej maszynie może zająć godzinę; wystarczająco szybki i losowy do większości celów.

#!/bin/bash
FILE_CREAT='/tmp/testfile'
MAX_SIZE=$(( 1 * 1024 * 1024 ))
rm -rf ${FILE_CREAT}
while true
do
    STRING=''
    for (( i = 0 ; i < 100 ; i++ ))
    do
        NUM_RAN=$(cat /dev/urandom | tr -dc 0-9 | head -c 1)
        if [ $i -eq 0 ]
        then
            STRING=${NUM_RAN}
        else
            STRING=${STRING}' '${NUM_RAN}
        fi
    done
    echo ${STRING} >> $FILE_CREAT
    FILE_SIZE=$(du -s ${FILE_CREAT} | awk '{print $1}')
    if [ ${FILE_SIZE} -ge ${MAX_SIZE} ]
    then
        break
    fi
done
exit $1