Was ist der schnellste Weg, um eine 1 GB große Textdatei mit zufälligen Ziffern zu generieren?

52

Ich habe ein Bash-Skript ausprobiert, aber es hat zu lange gedauert, eine einfache 1-MB-Datei zu erstellen. Ich denke, die Antwort liegt in der Verwendung von /dev/randomoder /dev/urandom, aber in anderen Beiträgen wird nur gezeigt, wie man mit diesen Dingen alle Arten von Daten zu einer Datei hinzufügt, aber ich möchte nur Zahlen hinzufügen.

Gibt es einen Befehl, mit dem ich eine zufällige Datei mit einer Größe von 1 GB erstellen kann, die nur Zahlen zwischen 0 und 9 enthält?

Edit: Ich möchte, dass die Ausgabe so ähnlich ist

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

Der Bereich ist 0 - 9, was bedeutet, dass nur die Zahlen 0, 1, 2, 3, 4, 5, 6, 7, 8 und 9 verwendet werden. Außerdem müssen sie durch Leerzeichen getrennt sein und 100 pro Zeile, bis zur nAnzahl der Zeilen. Dies ist mir egal, ich möchte, dass meine endgültige Größe 1 GB beträgt.

Edit: Ich benutze Ubuntu 16.04 LTS

posixKing
quelle
21
Sie sollten wahrscheinlich sagen, was Sie mit "zufällig" meinen - kryptografische Stärke zufällig, oder ist eine pseudozufällige Sequenz ausreichend?
Toby Speight
4
@posixKing: Beachten Sie, dass ich, obwohl meine Antwort definitiv ironisch ist, nicht wirklich vorschlage, ein C-Programm für eine solche Aufgabe zu schreiben! - Wenn Sie routinemäßig so große Datenmengen generieren oder diese häufig generieren, können Sie durch diesen Ansatz Zeit sparen. (Auf meinem Laptop werden 1 GB durch Leerzeichen getrennte Ziffern in ungefähr zehn Sekunden generiert.) Wenn dies jedoch ein einmaliges Ereignis ist, sollten Sie nicht einmal daran denken, ein C-Programm dafür zu schreiben (es sei denn, Sie möchten programmieren, und berücksichtigen Sie dies Praxis oder so); Die Shell-Befehle und -Dienstprogramme erledigen die Aufgabe in kürzerer Zeit und mit geringerem Aufwand.
Nominal Animal
7
Dies ist ziemlich schnell und RFC 1149.5-konform:yes 4 | tr '\n' ' ' | fold -w 200 | head -c1G
Matthew Crumley

Antworten:

38

Dies ist aufgrund des Titels der Frage teilweise eine humoristische Antwort.

Wenn Sie nach "dem schnellsten Weg zu ..." suchen , ist die Antwort fast immer ein spezielles Werkzeug. Diese "Antworten" zeigen ein solches Tool, nur damit Sie experimentieren können.

Dies ist keine ernsthafte Antwort, da Sie sich nicht mit speziellen Tools für Aufgaben befassen sollten, die Sie nur einmal oder sehr selten ausführen. Sie werden am Ende mehr Zeit damit verbringen, nach Werkzeugen zu suchen und mehr darüber zu lernen, als Dinge zu tun. Muscheln und Hilfsprogramme mögen bashund awksind nicht die schnellsten, aber Sie können in der Regel einen Einzeiler schreiben , um den Auftrag zu erledigen, und dabei nur Sekunden verwenden. Bessere Skriptsprachen wie perlkönnen ebenfalls verwendet werden, obwohl die Lernkurve für perlsteil ist, und ich zögere, sie für solche Zwecke zu empfehlen, da ich von schrecklichen Perl-Projekten traumatisiert bin. pythonauf der anderen Seite ist es leicht behindert durch sein eher langsames I / O; Dies ist jedoch nur dann ein Problem, wenn Sie Gigabyte an Daten filtern oder generieren.

In jedem Fall sollte das folgende C89-Beispielprogramm (das POSIX.1 nur für eine höhere Taktgenauigkeit verwendet, falls verfügbar) eine Generierungsrate von etwa 100 MB / s erreichen (getestet unter Linux auf einem Laptop mit einem Intel i5-4200U-Prozessor, der die Ausgabe weiterleitet) zu /dev/null), mit einem ziemlich guten Pseudozufallszahlengenerator. (Die Ausgabe sollte alle BigCrunch-Tests mit Ausnahme des MatrixRank-Tests bestehen, da der Code xorshift64 * und die Ausschlussmethode verwendet, um ein Verzerren der Ziffern zu vermeiden.)

Dezimalstellen.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;
}

Wir können es viel schneller machen, wenn wir zu einem Zeilenpuffer wechseln, und zwar fwrite()einmal, anstatt jede Ziffer einzeln auszugeben. Beachten Sie, dass der Stream weiterhin vollständig gepuffert bleibt, um partielle Schreibvorgänge (ohne Zweierpotenz) zu vermeiden, wenn es sich bei der Ausgabe um ein Blockgerät handelt.

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

Hinweis: Beide Beispiele wurden am 18.11.2016 bearbeitet, um eine gleichmäßige Verteilung der Ziffern zu gewährleisten (Null ist ausgeschlossen; siehe z. B. hier für Vergleiche und Details zu verschiedenen Pseudozufallszahlengeneratoren).

Kompilieren Sie zum Beispiel mit

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

und optional installieren systemweit /usr/binmit

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

Es werden die Anzahl der Stellen pro Zeile und die Anzahl der Zeilen verwendet. Weil 1000000000 / 100 / 2 = 5000000(fünf Millionen; Gesamtbytes geteilt durch Spalten geteilt durch 2), können Sie verwenden

./decimal-digits 100 5000000 > digits.txt

um die digits.txtvom OP gewünschte Gigabyte-Größe zu erzeugen .

Beachten Sie, dass das Programm selbst mehr auf Lesbarkeit als auf Effizienz ausgelegt ist. Ich möchte hier nicht die Effizienz des Codes demonstrieren - ich würde sowieso POSIX.1 und Low-Level-I / O anstelle von generischen C-Schnittstellen verwenden -, sondern Ihnen zeigen, welche Art von Balance es mit Aufwand gibt bei der Entwicklung dedizierter Tools im Vergleich zu ihrer Leistung im Vergleich zu Einzeiler- oder Short-Shell- oder awk-Scriptlets.

Bei Verwendung der GNU C-Bibliothek verursacht der Aufruf der fputc()Funktion für jede Zeichenausgabe einen sehr geringen Overhead (durch einen indirekten Funktionsaufruf oder durch Bedingungen - die FILESchnittstelle ist tatsächlich ziemlich komplex und vielseitig, wie Sie sehen). Auf diesem bestimmten Intel Core i5-4200U-Laptop /dev/nulldauert die Umleitung der Ausgabe auf die erste (fputc) Version ungefähr 11 Sekunden, während die Version für eine einzelne Zeile nur 1,3 Sekunden dauert.

Ich schreibe solche Programme und Generatoren oft nur, weil ich gerne mit riesigen Datensätzen spiele. Ich bin so komisch. Zum Beispiel habe ich einmal ein Programm geschrieben, um alle endlichen positiven IEEE-754-Gleitkommawerte in eine Textdatei zu drucken, mit ausreichender Genauigkeit, um genau den gleichen Wert zu erhalten, wenn sie analysiert werden. Die Datei hatte eine Größe von einigen Gigabyte (vielleicht 4 GB oder so); es gibt nicht so viele endliche positive floats, wie man meinen könnte. Ich habe dies verwendet, um Implementierungen zu vergleichen, die solche Daten lesen und analysieren.

Für normale Anwendungsfälle wie das OP sind Shell-Skripte und Scriptlets und Einzeiler der bessere Ansatz. Weniger Zeitaufwand für die Ausführung der Gesamtaufgabe. (Außer, wenn sie jeden Tag eine andere Datei benötigen oder wenn es viele Menschen gibt, die eine andere Datei benötigen. In seltenen Fällen kann ein spezielles Tool wie oben den Aufwand rechtfertigen.)

Nominelles Tier
quelle
Ja, wahrscheinlich mmap()ist dies der einfachste Weg, um die beste E / A-Geschwindigkeit zu erreichen - aber vergleichen Sie dies, bevor Sie Ansprüche geltend machen!
Toby Speight
@TobySpeight: Unter Linux ist Low-Level-E / A, dh die Verwendung write(), in der Regel schneller als mmap(). fwrite()ist nicht viel langsamer. Ja, das habe ich gemessen (nur nicht für dieses Beispiel); write()Bei großen Datenblöcken (262144, 524288 oder 1048576 Byte) ist die Leistung tendenziell höher als bei den anderen Methoden. Die Version der fputc()in GNU C implementierten Bibliothek (die ich auch ausgiebig getestet habe) ist aus mehreren Gründen langsam. Insbesondere muss die Implementierung für jedes hinzugefügte Zeichen entweder bedingte Sprünge oder indirekte Aufrufe ausführen. Dieser geringfügige Mehraufwand summiert sich so oft.
Nominal Animal
Nur aus Interesse - haben Sie einen Leistungsvergleich mit den anderen Antworten durchgeführt?
Digitales Trauma
2
@DigitalTrauma: Ich habe sie nur für Sie ausgeführt und die Ausgabe an umgeleitet /dev/null. Das Scriptlet von Stéphane Chazelas dauert ungefähr 52 Sekunden. Perl-Snippet (einschließlich der headFilterung) ca. 58 Sekunden; Ihr shufSnippet (mit dem richtigen Timing; Sie messen nur die Shuf-Zeit, vorausgesetzt, die Paste dauert nicht länger) dauert ungefähr 69 Sekunden. Das C ++ 11-Programm von James Hollis dauert jeweils 14 Sekunden. Das obige Programm dauert 10 Sekunden.
Nominal Animal
3
(Verlor meinen Gedankengang oben, sorry.) Punkt ist, die Auswahl des richtigen Algorithmus - der ausreichend zufälligen, aber sehr schnellen PRNG hier - ergab eine Geschwindigkeitssteigerung von fast einer Größenordnung (10 ×). (Die letztere Version meiner Programme ist ungefähr 40-mal schneller als die Shell- oder Perl-Snippets.) Dies ist typisch. Vielleicht hätte ich mehr Wert darauf legen sollen, den richtigen Algorithmus zu wählen, wenn ich ein Programm geschrieben habe. (Auf der anderen Seite handelt es sich nicht um eine Programmierfrage, sondern um eine Unix / Linux-Frage zur Generierung vieler Ziffern.)
Nominal Animal
81

Diese:

 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

(unter der Annahme einer headunterstützten Implementierung -c) scheint auf meinem System relativ schnell zu sein.

trÜbersetzt den gesamten Byte-Bereich (0 bis 255, 0 bis 0377 in Oktal): Die 25 ersten Bytes als 0, die 25 nächsten als 1 ... 25 9 die restlichen (250 bis 255) zu "x", die wir dann Verwerfen Sie (mit tr -d x), da wir eine gleichmäßige Verteilung wünschen (vorausgesetzt, Sie /dev/urandomhaben selbst eine gleichmäßige Verteilung), und geben Sie daher einigen Ziffern keinen Bias.

Das ergibt eine Ziffer für 97% der Bytes von /dev/urandom. fold -w 1macht es eine Ziffer pro Zeile. paste -swird mit einer Liste von Trennzeichen aufgerufen, die aus 99 Leerzeichen und einem Zeilenumbruchzeichen besteht, sodass in jeder Zeile 100 durch Leerzeichen getrennte Ziffern stehen.

head -c1Gerhält den ersten GiB (2 30 ) davon. Beachten Sie, dass die letzte Zeile abgeschnitten und nicht begrenzt wird. Sie können auf 2 30 -1 kürzen und die fehlende Zeile manuell hinzufügen oder auf 10 9 Bytes kürzen, was 50 Millionen dieser 200-Byte-Zeilen entspricht (dies head -n 50000000würde es auch zu einem Standard- / portablen Befehl machen).

Diese Timings (erhalten von zsheinem Quad-Core-System) geben einen Hinweis darauf, wo die CPU-Zeit verbracht wird:

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

Der erste trist der Flaschenhals, der die meiste Zeit im Kernel verbracht hat (ich nehme an, für die Zufallszahlengenerierung). Das Timing entspricht in etwa der Rate, mit der ich Bytes /dev/uramdomabrufen kann (ca. 19MiB / s, und hier produzieren wir 2 Bytes für jeweils 0,97 Bytes von / dev / urandom mit einer Rate von 32MiB / s). foldscheint eine unangemessene Menge an CPU-Zeit (15s) aufzuwenden, nur um nach jedem Byte ein Zeilenumbruchzeichen einzufügen, aber das wirkt sich nicht auf die Gesamtzeit aus, da es in meinem Fall auf einer anderen CPU funktioniert (durch Hinzufügen der -bOption wird es geringfügig länger effizient, dd cbs=1 conv=unblockscheint eine bessere Alternative zu sein).

Sie können das head -c1Gund das Rasieren für einige Sekunden aufheben, indem Sie die Dateigröße ( limit filesize 1024mmit zshoder ulimit -f "$((1024*1024))"mit den meisten anderen Shells (einschließlich zsh)) in einer Subshell begrenzen.

Das könnte verbessert werden, wenn wir 2 Ziffern für jedes Byte extrahieren würden, aber wir würden dafür einen anderen Ansatz benötigen. Das Obige ist sehr effizient, da trnur jedes Byte in einem 256-Byte-Array nachgeschlagen wird. Dies kann nicht für 2 Bytes gleichzeitig durchgeführt werden, und hexdump -e '1/1 "%02u"'die Berechnung der Textdarstellung eines Bytes mithilfe komplexerer Algorithmen wäre teurer als die Zufallszahlengenerierung. Wenn Sie jedoch wie in meinem Fall über CPU-Kerne verfügen, deren Zeit noch übrig ist, gelingt es möglicherweise noch, einige Sekunden zu sparen:

Mit:

< /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

Ich bekomme (beachte jedoch, dass es hier 1.000.000.000 Bytes im Gegensatz zu 1.073.741.824 sind):

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

Insgesamt mehr CPU-Zeit, aber besser verteilt auf meine 4 CPU-Kerne, sodass weniger Zeit für die Wanduhr benötigt wird. Der Engpass ist jetzt hexdump.

Wenn wir ddanstelle von zeilenbasiert arbeiten fold, können wir den Arbeitsaufwand reduzieren hexdumpund die Arbeitsverteilung zwischen den CPUs verbessern:

< /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')" -

(hier unter der Annahme von GNU ddfür sein iflag=fullblockund status=none), was ergibt:

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

Zurück zur Zufallsgenerierung als Engpass.

Wie von @OleTange bereits erwähnt, können Sie mit diesem opensslDienstprogramm einen schnelleren (insbesondere bei Prozessoren mit AES-Befehlen) Pseudozufallsgenerator für Bytes erstellen.

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

auf meinem System spuckt 15 mal so viele Bytes pro Sekunde als /dev/urandom. (Ich kann nicht kommentieren, wie es in Bezug auf kryptografisch sichere Zufallsquellen verglichen wird, wenn dies auf Ihren Anwendungsfall zutrifft.)

</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')" -

Jetzt gibt es:

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

zurück zum hexdumpFlaschenhals.

Da ich noch CPUs übrig habe, kann ich drei davon hexdumpparallel betreiben .

</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')" -

(das <&3wird für andere Shells als zshdas close-Kommando stdin on / dev / null benötigt, wenn es im Hintergrund ausgeführt wird).

Jetzt bis zu 6,2 Sekunden und meine CPUs fast voll ausgelastet.

Stéphane Chazelas
quelle
3
Ich habe gerade meine vorherige Antwort gelöscht und für diese gestimmt. Ich habe einige der Anforderungen nicht erhalten. Schöne Antwort übrigens.
Marcelo
3
Warum generierst du nicht mehrere Ziffern bei jedem Durchgang? Auch wenn Sie Byte für Byte lesen, können Sie jedes Mal 2 Ziffern erzeugen
phuclv
@LưuVĩnhPhúc, ich habe die perlVariante entfernt, die sowieso deutlich langsamer war. Ich kann mit diesem tr | fold | paste-Ansatz keine 2 Stellen pro Byte erhalten.
Stéphane Chazelas
Ich bin afk oder ich würde es selbst versuchen, aber Sie könnten versuchen, 42 Bytes gleichzeitig in 100-102 Ziffern umzuwandeln, indem Sie bcdie 0, 1 oder 2 höchstwertigen Ziffern verwenden.
Eric Towers
gitlab.com/ole.tange/tangetools/tree/master/rand generiert 1-4 GB Pseudozufall pro Sekunde (AES-Qualität).
Ole Tange
23

Wenn Sie shufverfügbar sind (aktuelle GNU-Coreutils), können Sie dies tun:

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

Auf meiner VM ist dies jetzt etwas langsamer als die Antwort von Stéphane, und zwar um einen Faktor von 3: 4.

Digitales Trauma
quelle
shufauf meinem Firmen-PC hat nicht -r, fmthat nicht -gzu
phuclv
2
@ LưuVĩnhPhúc Yep - YMMV. Ich habe festgestellt, dass Core-Utils Version 8.25 diese hat, aber 8.4 nicht. Welche Version benutzt du?
Digitales Trauma
1
Ich benutze Coreutils
8.13
@ StéphaneChazelas clever paste/ printftrick - danke. Ihre Antwort ist jetzt anscheinend schneller.
Digitales Trauma
17

Wenn Sie keine Zufälligkeit mit sehr hoher Qualität benötigen und eine nahezu gleichmäßige Verteilung ausreichend ist, können Sie sehr schnell vorgehen, insbesondere auf einer modernen CPU mit effizienten SIMD-Ganzzahlvektoren wie x86 mit SSE2 oder AVX2.

Dies ist wie die Antwort von @ NominalAnimal, da wir beide die gleiche Idee hatten, aber manuell für x86 vektorisiert haben. (Und mit Zufallszahlen von schlechterer Qualität, aber wahrscheinlich immer noch gut genug für viele Anwendungsfälle.) Dies ist ungefähr 15- bis 30-mal schneller als der Code von @ Nominal, bei einer ASCII-Ausgabe von ~ 13 GB / s auf einem 2,5-GHz-Intel-Haswell CPU mit AVX2. Das ist immer noch weniger als die theoretische maximale Hauptspeicherbandbreite (Dual-Channel-DDR3-1600 ist ungefähr 25,6 GB / s), aber ich habe das Schreiben in / dev / null geplant, so dass nur ein Puffer neu geschrieben wird, der im Cache heiß bleibt. Skylake sollte denselben Code deutlich schneller ausführen als Haswell (siehe unten in dieser Antwort).

Vorausgesetzt, Sie haben tatsächlich irgendwo einen E / A-Engpass auf der Festplatte oder leiten diesen weiter, bedeutet eine schnelle Implementierung, dass Ihre CPU nicht einmal höher takten muss als im Leerlauf. Es verbraucht viel weniger Gesamtenergie, um das Ergebnis zu erzielen. (Batterielebensdauer / Hitze / globale Erwärmung.)

Dies ist so schnell, dass Sie es wahrscheinlich nicht auf die Festplatte schreiben möchten. Generieren Sie sie einfach nach Bedarf neu (aus demselben Startwert, wenn Sie dieselben Daten erneut benötigen ). Selbst wenn Sie es einem Multithread-Prozess zuführen möchten, der alle CPUs verwenden kann, wird es beim Ausführen dieses Befehls zum Weiterleiten der Daten im L3-Cache (und im L2-Cache auf dem Kern, der es geschrieben hat) heiß belassen und daher sehr häufig verwendet wenig CPU-Zeit. (Beachten Sie jedoch, dass das Piping im /dev/nullVergleich zum Schreiben viel Aufwand verursacht . Bei einem Skylake i7-6700k, das an ein wc -canderes Programm weitergeleitet wird, das nur seine Eingabe liest und verwirft, ist es ungefähr 8x langsamer als das Schreiben an/dev/null und verbraucht nur 70% von a CPU: Aber das sind immer noch 4,0 GB / s bei einer 3,9-GHz-CPU.

Das erneute Generieren ist schneller als das erneute Lesen selbst von einer schnellen, mit PCIe verbundenen SSD, aber IDK, wenn es energieeffizienter ist (der Vektor-Integer-Multiplikator ist ziemlich beschäftigt und wahrscheinlich, zusammen mit anderen AVX2-Geräten, ziemlich leistungshungrig) 256b Vektor-ALUs). OTOH, ich weiß nicht, wie viel CPU-Zeit das Lesen von der Festplatte für etwas kostet, bei dem alle Kerne, die diese Eingabe verarbeiten, maximal waren. Ich würde vermuten, dass ein Kontextwechsel, der in 128k-Blöcken neu generiert wird, mit dem Ausführen von Dateisystem- / Pagecache-Code und dem Zuweisen von Seiten zum Lesen von Daten von der Festplatte konkurrieren kann. Wenn es im Pagecache bereits heiß ist, ist es natürlich nur im Grunde genommen memcpy. OTOH, wir schreiben schon so schnell wie memcpy! (was die Hauptspeicherbandbreite zwischen Lesen und Schreiben aufteilen muss). (Beachten Sie auch, dass das Schreiben in den Speicher, dass 'rep movsb(optimiertes memcpy und memset im Mikrocode, das RFO vermeidet, seit Andy Glew es in P6 (Pentium Pro) implementiert hat ).


Bisher ist dies nur ein Proof of Concept und das Newline-Handling ist nur annähernd korrekt. Es ist falsch um die Enden eines Potenz-2-Puffers. Mit mehr Entwicklungszeit. Ich bin zuversichtlich, dass ich einen effizienteren Weg finden könnte, um Zeilenumbrüche einzufügen, der auch genau richtig ist, mit mindestens so geringem Overhead (verglichen mit der Ausgabe nur von Leerzeichen). Ich denke, das sind ungefähr 10 bis 20%. Ich bin nur daran interessiert zu wissen, wie schnell wir diesen Lauf machen können, und nicht daran, eine polierte Version davon zu haben. Deshalb werde ich diesen Teil als Übung für den Leser mit Kommentaren belassen, in denen einige Ideen beschrieben werden.


Auf einem Haswell i5 mit 2,5 GHz maximalem Turbo und DDR3-1600 MHz RAM wurde die Erzeugung von 100 GiB zwar zeitlich festgelegt, aber verkleinert. (Zeitlich festgelegt auf cygwin64 unter Win10 mit gcc5.4 -O3 -march=native, weggelassen, -funroll-loopsda es mir schon schwer genug fiel, auf diesem geliehenen Laptop anständige zeitliche Abläufe zu erzielen . Hätte nur Linux über USB booten sollen).

Schreiben nach / dev / null, sofern nicht anders angegeben.

  • James Hollis: (nicht getestet)
  • Nominals fwrite Version: ~ 2.21s
  • dies (SSE2): ~ 0,142 s (nicht skalierte Zeiten = real = 14,232 s, Benutzer = 13,999 s, sys = 0,187 s).
  • dies (AVX-128): ~ 0,140s
  • this (AVX2): ~ 0,073 s (nicht skaliert: real = 0 m7,291 s, user = 0 m7,125 s, sys = 0 m0,155 s).
  • Diese (AVX2-) Cygwin-Piping-Funktion wc -cmit 128 KB Puffergröße: 0,32 s bei einer CPU mit 2,38 GHz (maximaler Dual-Core-Turbo). (unskalierte Zeiten: real = 32.466s user = 11.468s sys = 41.092s, einschließlich dieser und wc). Allerdings wurde nur die Hälfte der Daten tatsächlich kopiert, da mein albernes Programm davon ausgeht, dass write den vollen Puffer ausführt, obwohl dies nicht der Fall ist und cygwin write () nur 64k pro Aufruf in eine Pipe ausführt.

Mit SSE2 ist dies ungefähr 15-mal schneller als der skalare Code von @Nominal Animal. Mit AVX2 ist es ungefähr 30-mal schneller. Ich habe nicht versucht , eine Version von Code der Nominal , die gerade verwendet write()statt fwrite(), sondern vermutlich für große Puffer stdio meist aus dem Weg bleibt. Wenn die Daten kopiert werden, führt dies zu einer starken Verlangsamung.


1 GB Daten auf einem Core2Duo E6600 (Merom 2,4 GHz, 32 KB privater L1, 4 MB gemeinsam genutzter L2-Caches), DDR2-533 MHz in 64-Bit-Linux 4.2 (Ubuntu 15.10). Diese Dimension wurde noch nicht untersucht, obwohl für write () eine Puffergröße von 128 KB verwendet wurde.

Schreiben nach / dev / null, sofern nicht anders angegeben.

  • (SSE2) dies mit Zeilenumbruchbehandlung und 4 Vektoren von Ziffern aus jedem Vektor von Zufallsbytes: 0,183 s (zeitgesteuert mit 100 GiB in 18,3 s, aber ähnlichen Ergebnissen für 1 GiB-Läufe). 1,85 Anweisungen pro Zyklus.
  • (SSE2) Dies, Weiterleiten an wc -c: 0,593 s (nicht skaliert: real = 59,266 s Benutzer = 20,148 s sys = 1 m 6,548 s, einschließlich der CPU-Zeit von wc). Die gleiche Anzahl von write () - Systemaufrufen wie bei cygwin, jedoch werden alle Daten per Piping übertragen, da Linux alle 128.000 write () -Aufrufe an eine Pipe verarbeitet.
  • NominalAnimals fwrite()Version (gcc5.2 -O3 -march=native), ausgeführt mit ./decdig 100 $((1024*1024*1024/200)) > /dev/null: 3,19s +/- 0,1%, mit 1,40 Anweisungen pro Zyklus. -Funroll-Loops machten vielleicht einen winzigen Unterschied. clang-3.8 -O3 -march=native: 3,42 s +/- 0,1%
  • Nominale Weiterleitung fwritean wc -c: real = 3.980s user = 3.176s sys = 2.080s
  • James Hollis 'Line-at-Time-Version ( clang++-3.8 -O3 -march=native): 22.885s +/- 0.07%, mit 0.84 Anweisungen pro Zyklus. (g ++ 5.2 war etwas langsamer: 22,98s). Das Schreiben von jeweils nur einer Zeile hat wahrscheinlich erheblich geschadet.
  • Stéphane Chazelas tr < /dev/urandom | ...: real = 41.430s user = 26.832s sys = 40.120s. trIch habe die meiste Zeit den gesamten CPU-Kern auf sich gestellt und fast die gesamte Zeit im Kernel-Treiber verbracht, um zufällige Bytes zu generieren und sie in eine Pipe zu kopieren. Der andere Kern dieser Dual-Core-Maschine war der Rest der Pipeline.
  • time LC_ALL=C head -c512M </dev/urandom >/dev/null: dh nur so viel Zufall ohne Pipe lesen: real = 35.018s user = 0.036s sys = 34.940s.
  • Lưu Vĩnh Phúcs Perl-Programm (Perl v5.20.2 von Ubuntu15.10)::
    LANG=en_CA.UTF-8real = 4m32.634s user = 4m3.288s sys = 0m29.364.
    LC_ALL=C LANG=C: real = 4m18.637s user = 3m50.324s sys = 0m29.356s. Immer noch sehr langsam.

  • (SSE2) dies ohne Zeilenumbruchbehandlung und entweder 3 oder 4 Vektoren von Ziffern aus jedem Vektor von zufälligen Bytes (fast genau die gleiche Geschwindigkeit: der dig3 = v%10Schritt ist auf dieser HW ungefähr ausgeglichen): 0,166 s (1,82 Anweisungen pro Zyklus) . Dies ist im Grunde die Untergrenze für das, was wir mit einem perfekt effizienten Newline-Handling erreichen können.

  • (SSE2) Alte Version ohne Zeilenumbruch, sondern nur mit einer Ziffer pro uint16_t-Element v%10, 0,222 Sekunden +/- 0,4%, 2,12 Anweisungen pro Zyklus. (Kompiliert mit gcc5.2 -march=native -O3 -funroll-loops. Unroll-Schleifen helfen bei diesem Code auf dieser Hardware. Verwenden Sie ihn nicht blind, besonders bei großen Programmen.)
  • (SSE2) Alte Version davon, Schreiben in eine Datei (auf einem RAID10f2 von 3 schnellen Magnetfestplatten, nicht sehr für Schreibvorgänge optimiert): ~ 4 Sekunden. Könnte schneller gehen, indem die Einstellungen des Kernel-E / A-Puffers angepasst werden, um viel mehr schmutzige Daten vor write () -Blöcken zuzulassen. "System" -Zeit ist immer noch ~ 1,0 Sekunden, viel höher als "Benutzer" -Zeit. Auf diesem alten System mit langsamem DDR2-533-RAM dauert es ca. 4x länger, bis der Kernel die Daten in den Pagecache kopiert und die XFS-Funktionen ausführt, als auf meinem Loop, um sie in einem Puffer neu zu schreiben, der heiß bleibt Zwischenspeicher.

Wie es gemacht wird

Ein schnelles PRNG ist offensichtlich unerlässlich. xorshift128 + kann vektorisiert werden, sodass Sie zwei oder vier 64-Bit-Generatoren parallel in Elementen eines SIMD-Vektors haben. Jeder Schritt erzeugt einen vollständigen Vektor von Zufallsbytes. ( 256b AVX2 Implementierung hier mit Intel Intrinsics ). Ich habe es wegen Nominals Wahl von xorshift * ausgewählt, da die 64-Bit-Vektor-Ganzzahl-Multiplikation nur in SSE2 / AVX2 mit Techniken mit erweiterter Genauigkeit möglich ist .


Bei einem Vektor aus zufälligen Bytes können wir jedes 16-Bit-Element in mehrere Dezimalstellen aufteilen. Wir erzeugen mehrere Vektoren von 16-Bit-Elementen, bei denen es sich jeweils um eine ASCII-Ziffer + einen ASCII-Raum handelt . Wir speichern das direkt in unserem Ausgabepuffer.

Meine ursprüngliche Version hat nur verwendet x / 6554, um eine zufällige Ziffer von jedem uint16_t-Element eines Vektors zu erhalten. Es ist immer zwischen 0 und 9, einschließlich. Es ist voreingenommen von 9, weil (2^16 -1 ) / 6554es nur 9.99923 ist. (6554 = ceil ((2 ^ 16-1) / 10), wodurch sichergestellt wird, dass der Quotient immer <10 ist.)

x/6554kann mit einer Multiplikation mit einer "magischen" Konstante ( dem Festkomma-Kehrwert ) und einer Rechtsverschiebung des Ergebnisses der hohen Hälfte berechnet werden . Dies ist der beste Fall für die Division durch eine Konstante; Einige Divisoren nehmen mehr Operationen vor, und signierte Divisionen erfordern zusätzliche Arbeit. x % 10hat eine ähnliche Tendenz und ist nicht so billig zu berechnen. (gcc ASM Ausgang entspricht x - 10*(x/10), also eine zusätzliche Multiplikation und Subtraktion auf der Oberseite der Teilung eine modulare multiplikative Inverse verwendet.) Auch das niedrigste Bit der xorshift128 + ist nicht so hohe Qualität , so Dividieren Entropie aus High - Bits nehmen besser ( für Qualität sowie Geschwindigkeit) als Modulo, um Entropie von niedrigen Bits zu nehmen.

Wir können jedoch mehr von der Entropie in jedem uint16_t verwenden, indem wir uns die niedrigen Dezimalstellen ansehen, wie z. B. die digit()Funktion von @ Nominal . Um die maximale Leistung zu erzielen, habe ich mich entschieden, die niedrigen 3 Dezimalstellen zu verwenden und x/6554eine PMULLW und PSUBW (und wahrscheinlich einige MOVDQA) zu speichern, im Vergleich zu der Option mit der höheren Qualität, bei der die 4 niedrigen Dezimalstellen verwendet werden. x / 6554 wird geringfügig von den niedrigen 3 Dezimalstellen beeinflusst, sodass eine gewisse Korrelation zwischen den Stellen desselben Elements besteht (8- oder 16-stelliger Abstand in der ASCII-Ausgabe, abhängig von der Vektorbreite).

Ich denke, dass gcc durch 100 und durch 1000 dividiert und nicht durch eine längere Kette, die nacheinander durch 10 dividiert wird, sodass die Länge der nicht durch Schleifen übertragenen Abhängigkeitskette, die 4 Ergebnisse aus jeder PRNG-Ausgabe erzeugt, wahrscheinlich nicht wesentlich verkürzt wird. port0 (Vektormultiplikation und -verschiebung) ist der Engpass aufgrund der modularen multiplikativen Inversen und der Verschiebungen in xorshift +, daher ist es definitiv nützlich, eine Vektormultiplikation zu speichern.

xorshift + ist so schnell, dass selbst die Verwendung von nur ~ 3,3 Bit Zufälligkeit von 16 (dh 20% Wirkungsgrad) nicht viel langsamer ist als das Zerlegen in mehrere Dezimalstellen. Wir nähern uns nur der gleichmäßigen Verteilung, da diese Antwort auf Geschwindigkeit ausgerichtet ist, solange die Qualität nicht zu schlecht ist.

Jede Art von bedingtem Verhalten, das eine variable Anzahl von Elementen beibehält, würde viel mehr Arbeit erfordern. (Könnte aber mit SIMD-Links-Packing-Techniken möglicherweise noch effizienter durchgeführt werden . Dies wird jedoch bei kleinen Elementgrößen weniger effizient. Riesen-Shuffle-Mask-Lookup-Tabellen sind nicht realisierbar und es gibt keine AVX2-Lane-Crossing-Shuffle mit weniger als 32-Bit.) Bit-Elemente: Eine 128-Bit-PSHUFB-Version kann mit BMI2 PEXT / PDEP zwar wie bei AVX2 mit größeren Elementen im laufenden Betrieb eine Maske generieren , dies ist jedoch schwierig, da eine 64-Bit-Ganzzahl nur 8 Byte enthält Zu dieser Antwort gibt es einen Code, der möglicherweise für höhere Elementzahlen geeignet ist.)


Wenn die Latenz des RNG ein Engpass ist, können wir noch schneller vorgehen, indem wir zwei Vektoren von Generatoren parallel schalten und abwechselnd den von uns verwendeten verwenden. Der Compiler kann immer noch problemlos alles in Registern in einer entrollten Schleife halten, wodurch die beiden Abhängigkeitsketten parallel ausgeführt werden können.

In der aktuellen Version, in der die PRNG-Ausgabe reduziert wird, besteht tatsächlich ein Engpass beim Durchsatz von Port 0, nicht bei der PRNG-Latenz, sodass dies nicht erforderlich ist.


Der Code: AVX2-Version

Vollversion mit weiteren Kommentaren zum Godbolt-Compiler-Explorer .

Nicht sehr aufgeräumt, sorry ich muss einschlafen und will das hier posten.

Um die SSE2 Version zu erhalten, s/_mm256/_mm, s/256/128/, s/v16u/v8u/, und ändern vector_size(32)bis 16. Auch den Newline Schritt ändern von 4 * 16-4 * 8. (Wie gesagt, Code ist chaotisch und nicht für das Kompilieren von zwei Versionen geeignet. Eigentlich wollte ich keine AVX2-Version erstellen, aber dann wollte ich unbedingt eine Haswell-CPU testen, auf die ich Zugriff hatte.)

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

}

Kompilieren Sie mit gcc, clang oder ICC (oder hoffentlich mit jedem anderen Compiler, der den GNU C-Dialekt von C99 und die Intelsics von Intel versteht). GNU C-Vektorerweiterungen sind äußerst praktisch, damit der Compiler die magischen Zahlen für Division / Modulo mit modularen multiplikativen Inversen generiert, und gelegentliche __attribute__s sind nützlich.

Dies könnte portabel geschrieben werden, aber es würde mehr Code erfordern.


Leistungsmerkmale:

Der überlappende Speicher zum Einfügen von Zeilenumbrüchen ist mit erheblichem Aufwand verbunden, um zu entscheiden, wo er platziert werden soll (Verzweigungsfehler und Frontend-Engpässe bei Core2). Der Speicher selbst hat jedoch keine Auswirkungen auf die Leistung. Wenn Sie nur diese Speicheranweisung im Compiler asm auskommentieren (wobei alle Verzweigungen gleich bleiben), blieb die Leistung auf Core2 vollständig unverändert, und wiederholte Durchläufe gaben +/- weniger als 1% dieselbe Zeit. Daraus schließe ich, dass der Speicherpuffer / Cache das in Ordnung bringt.

Die Verwendung eines rotierenden Fensters ascii_digitspacemit einem Element, das einen Zeilenvorschub enthält, ist möglicherweise sogar noch schneller, wenn Sie das Fenster so weit ausrollen, dass alle Zähler / Verzweigungen verschwinden.


Das Schreiben in / dev / null ist im Grunde genommen ein No-Op, daher bleibt der Puffer im L2-Cache wahrscheinlich heiß (256 KB pro Kern bei Haswell). Die perfekte Beschleunigung von 128b-Vektoren auf 256b-Vektoren wird erwartet: Es gibt keine zusätzlichen Anweisungen, und alles (einschließlich der Speicher) geschieht mit der doppelten Breite. Der Zweig zum Einfügen von Zeilenumbrüchen wird jedoch doppelt so häufig verwendet. Leider habe ich bei meinem Haswell Cygwin-Setup keine Zeit dafür gehabt, dass dieser Teil ausgefallen ist #ifdef.

2,5 GHz * 32 B / 13,7 GB / s = 5,84 Zyklen pro AVX2-Speicher auf Haswell. Das ist ziemlich gut, könnte aber schneller sein. Vielleicht gibt es in den Cygwin-Systemaufrufen etwas Overhead, als ich dachte. Ich habe nicht versucht, diese in der asm-Ausgabe des Compilers zu kommentieren (was sicherstellen würde, dass nichts wegoptimiert wird.)

Der L1-Cache kann einen 32B-Speicher pro Takt unterstützen, und L2 weist keine wesentlich geringere Bandbreite auf (jedoch eine höhere Latenz).

Als ich mir IACA vor einigen Versionen ansah (ohne Verzweigung nach Zeilenumbrüchen, aber nur einen ASCII-Vektor pro RNG-Vektor), sagte es so etwas wie einen 32B-Vektorspeicher pro 4 oder 5 Takte voraus.

Ich hatte gehofft, durch das Extrahieren von mehr Daten aus jedem RNG-Ergebnis eine Beschleunigung zu erzielen, indem ich mir den Asm selbst ansah und die Anleitungen von Agner Fog und andere Optimierungsressourcen berücksichtigte, für die ich Links im SO x86-Tag-Wiki hinzugefügt habe .)

Auf Skylake wäre dies wahrscheinlich bedeutend schneller , da die Multiplikation und Verschiebung von Vektor-Ganzzahlen auf doppelt so vielen Ports (p0 / p1) ausgeführt werden kann wie bei Haswell (nur p0). Sowohl die Xorshift- als auch die Ziffernextraktion verwenden viele Verschiebungen und Multiplikationen. ( Update: Skylake führt es mit 3.02 IPC aus, was 3,77 Zyklen pro 32-Byte-AVX2-Speicher ergibt, zeitgesteuert mit 0.030s pro 1-GB-Iteration, und schreibt /dev/nullauf Linux 4.15 auf i7-6700k mit 3.9GHz.


Es ist kein 64-Bit-Modus erforderlich, um einwandfrei zu funktionieren . Die SSE2-Version ist beim Kompilieren genauso schnell -m32, da sie nicht sehr viele Vektorregister benötigt und die gesamte 64-Bit-Mathematik in Vektoren und nicht in Allzweckregistern ausgeführt wird.

Im 32-Bit-Modus ist es auf Core2 sogar etwas schneller, da die Makrofusion von Compare / Branch nur im 32-Bit-Modus funktioniert. Daher gibt es weniger Uops für den nicht ordnungsgemäßen Core (18.3s (1.85 Instructions Per Clock) vs 16,9 s (2,0 IPC)). Die kleinere Codegröße ohne REX-Präfix hilft auch den Core2-Decodern.

Außerdem werden einige Reg-Reg-Vektorbewegungen durch Ladevorgänge ersetzt, da nicht mehr alle Konstanten in Vektorregs festgelegt sind. Da der Ladedurchsatz aus dem L1-Cache kein Engpass ist, hilft dies tatsächlich. (z. B. Multiplikation mit einem konstanten Vektor von set1(10): movdqa xmm0, xmm10/ pmullw xmm0, xmm1wird zu movdqa xmm0, [constant]/ pmullw xmm0, xmm1.) Da für reg-reg MOVDQA ein ALU-Port erforderlich ist, konkurriert es mit der tatsächlich ausgeführten Arbeit, aber ein MOVDQA-Ladevorgang konkurriert nur um die Front-End-Dekodierungsbandbreite. (Wenn eine 4-Byte-Adresse in vielen Befehlen enthalten ist, wird ein Großteil des Gewinns durch das Speichern von REX-Präfixen aufgehoben.

Es würde mich nicht wundern, wenn beim Speichern von ALU MOVDQA-Ups die eigentlichen Gewinne erzielt werden, da das Frontend mit dem Durchschnitt von 2,0 IPC ziemlich gut mithalten sollte.

Alle diese Unterschiede verschwinden in Haswell, wo das Ganze vom decodierten UOP-Cache ausgeführt werden sollte, wenn nicht vom Loopback-Puffer. ALU + Branch Macro-Fusion funktioniert seit Nehalem in beiden Modi.

Peter Cordes
quelle
6
Ich finde es einfach toll, wie du dich mit dem Thema "Biest-Modus" beschäftigt hast ! :) Was noch wichtiger ist, es ist ein hervorragendes Beispiel dafür, welche Art von Gewinnen verfügbar sind, wenn Sie wirklich die maximale Leistung benötigen oder herausholen möchten, und dabei nur sehr geringe Kenntnisse über die vorhandene Hardware nutzen. Außerdem verwenden wir hier nur einen Thread. Die meisten aktuellen Intel / AMD-Desktop- und Server-Prozessoren (und sogar ARM-Prozessoren in leichten Tablets und SBCs) verfügen über mehrere Kerne, sodass noch mehr Echtzeit-Beschleunigungen verfügbar sind. Und schließlich, wie unpraktisch "der schnellste Weg zu" Fragen sind, aufgrund des bloßen Aufwandes.
Nominal Animal
1
@NominalAnimal: Ja, selbst ein langsamer ARM-Quad- oder Octo-Core könnte die Hauptspeicherbandbreite mit NEON problemlos auslasten (selbst wenn sie an schnelles Zweikanal-DDR3 angeschlossen wären), wenn es 64-Bit-Ganzzahl-SIMD-Adds und -Shifts enthält . Ich gehe davon aus, dass NEON 16-Bit-Multiplikatoren für die Audio-Arbeit hat. Instruction-Scheduling wäre für einen in-order-ARM viel aufwändiger, da jede Iteration der schleifengetragenen Abhängigkeitskette (das xorshift128 +) ein paar unabhängige Abhängigkeitsketten speist, die diese zerhacken und im Speicher ablegen ...
Peter Cordes
... Die Ausführung außerhalb der Reihenfolge isst das zum Frühstück, weil das Ganze so kurz ist, dass mehrere Iterationen in den ROB passen (192 Uops auf HSW IIRC). (dh das "Fenster" von Befehlen, das bei der Ausführung außerhalb der Reihenfolge angezeigt wird, enthält mehrere Iterationen). So kann die CPU den letzten Speicher vor zwei oder drei Iterationen beenden und gleichzeitig zu Beginn der aktuellen Iteration beginnen. Dadurch wird die Latenz der unabhängigen Ketten ausgeblendet, sodass nur der Durchsatz von Bedeutung ist. Auf einem in-order-Kern würde dies Software-Pipelining erfordern ...
Peter Cordes,
... Ein guter ARM-Compiler sollte einiges davon für Sie tun, wenn Sie es mit Intrinsics schreiben (oder GNU C native Vektorsyntax für das Ganze, wie ich es eigentlich hätte tun sollen). Ich habe keine Erfahrung damit, also müssen Sie möglicherweise Ihre Schleife massieren und möglicherweise manuelles Abrollen / Software-Pipelining in der Quelle durchführen, um ein gutes Ergebnis zu erzielen. (Es gibt einige außer Betrieb befindliche ARM-Kerne, die in High-End-Telefonen zu finden sind, aber kein so großes Fenster wie Haswell haben. OTOH, sie haben auch einen geringeren Spitzendurchsatz, daher gibt es weniger mehr ILP zu finden).
Peter Cordes
1
@ NominalAnimal: auch über die Albernheit der Frage einig. "Schnellste" ohne Einschränkung der Qualität der Zufälligkeit ist albern ... Mit BTRFS können dieselben Daten auf der Festplatte mehrmals Teil einer Datei sein (siehe EXTENT_SAME in 4.2 ). Sie können also zufällige 4kB oder 1MB erzeugen und wiederholen. Es ist Zufall mit einer kurzen Periode, aber es ist immer noch zufällig und kostet nur Metadaten-E / A. (Eigentlich muss der Block mit einem Zeilenumbruch enden. Lcm (4096, 4096 * 200) = 4096 * 200 = 819200 = 800kB, also ist Ihr Wiederholungsblock ein Vielfaches davon.)
Peter Cordes
14

Hier ist eine Lösung, von der ich hoffe, dass sie einfach zu verstehen ist:

od -An -x /dev/urandom | tr -dc 0-9 | fold -w100 | awk NF=NF FS= | head -c1G
  • odErstellt einen einheitlichen Stream von hexadezimalen Ziffern aus /dev/random.
  • trBefreit sich von Buchstaben und behält nur 0-9Ziffern
  • fold Stellt sicher, dass 100 Stellen pro Zeile vorhanden sind
  • awk fügt Leerzeichen in Zeilen ein
  • head verkürzt die Eingabe auf 1 Gigabyte
sam hocevar
quelle
2
Dies ist eine gute Alternative, um mehr als eine Stelle pro Byte von / dev / random zu erzeugen, während die Verteilung immer noch einheitlich ist. Pro 256 Bytes von / dev / urandom werden durchschnittlich 320 Stellen erzeugt (weniger, als wenn Sie Bytes <200 modulo konvertieren 100 bis dezimal, was Ihnen jedoch 400 Stellen für jeweils 256 Bytes gibt).
Stéphane Chazelas
6

Sie können den jotBefehl dazu verwenden:

jot -r 50000000 0 9 | fmt -w 200 > output.txt
Gartenkopf
quelle
1
@DigitalTrauma Meine Version von fmthat keine Zielbreitenoption . Wie auch immer, es wird genau sein, da alle Ziffern genau eine Spalte einnehmen!
Gardenhead
Für die Aufzeichnung ist meine fmtVersion fmt (GNU coreutils) 8.25(Ubuntu 16.04)
Digitales Trauma
2
Die richtige Zahl für ein halbes GB ist: 1024 * 1024 * 1024/2 =536870912
Olivier Dulac
1
@OlivierDulac Hängt davon ab, von welchem ​​"Gigabyte" Sie sprechen. Einige Leute verwenden 1 GB, um 10 ^ 9 statt 2 ^ 30 zu bedeuten, obwohl es technisch inkorrekt ist. Außerdem mag ich schöne runde Zahlen :)
gardenhead
6
@gardenhead, immer mehr Leute tendieren dazu, zu Gigabyte == 1e9 und Gibibyte == 2 ^ 30 zu wechseln, da dies die IEC-Standarddefinition ist. Siehe Wikipedia . Beachten Sie, dass Gb selbst eher Giga- wäre Bit .
Stéphane Chazelas
6

Dies ähnelt der Methode von Stéphane Chazelas, allerdings lese ich 64 Bit auf einmal, um die Leistung zu verbessern. Die Verteilung ist immer noch einheitlich, aber jetzt erhalten Sie 19 Ziffern für jeweils 8 Bytes anstelle von nur 8 im besten Fall wie zuvor

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

Auf 32-Bit-Plattformen werden statt 19 jedes Mal 9 Ziffern gelesen.

phuclv
quelle
Dies kann eine Ausnahme auslösen, wenn Ihr System keine 64-Bit-Ganzzahlen unterstützt oder perlnicht mit Quad-Unterstützung kompiliert ist.
17.
@ Cuonglm Ja, wie gesagt, wenn Perl nicht 64 Bit auf diesem System ist, muss das Programm geändert werden next if $n >= 1000000000; $s = sprintf("%09u", $n);, um nur 9 Ziffern zu erhalten
phuclv
Sie können nicht, das Programm stürzt ab, $n = unpack("Q")wenn Quad nicht unterstützt wird.
17.
1
@ Cuonglm ändern, um BEGIN{$/=\4; $,=" "} $n = unpack("L");auch
Phuclv
1
Es tut uns leid, aber es werden nur in etwa 54,2% der Fälle 19 Stellen aus 8 Byte eingegeben, während die restlichen Stellen durchschnittlich 1,29 Stellen pro Eingabebyte enthalten. Wenn Sie Stephane ähnlicher verwenden <16e18und durch 16 teilen, erhalten Sie 18 Stellen mit 86,7% für 1,95 dpB. Mit 32bit <4e9 /4erhält man 9 Stellen 93,1% für 2,10 dpB. Aber 5 Bytes (als Hex (H10)) <1e12ergeben 12 Ziffern 90,9% für 2,18 dpB, oder das Hex in zwei Hälften teilen und jede Hälfte <1e6 ergibt 6 Ziffern 95,4% für 2,29 dpB; Dies nähert sich der Grenze von log_10 (256) = 2,41.
Dave_thompson_085
3

Ich bin mit Nominal Animal einverstanden, eine kompilierte Programmiersprache zu verwenden, wenn Sie Geschwindigkeit benötigen. Sie müssen jedoch keinen eigenen RNG-Code in C schreiben. C ++ 11 bietet den exzellenten Mersenne Twister als Teil seiner Standardbibliothek.

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

Der obige Code ist einigermaßen einfach und dauert ungefähr eine Minute, wenn ich die Ausgabe in eine Datei leite. Wir können viel schneller vorgehen, indem wir einen String erstellen, der groß genug für 100 Ziffern ist, und die Ziffern hineinhacken. Auf diese Weise können wir jede Zeile und nicht jede Ziffer aufrufen.

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

Dieser Code benötigt meine Maschine ungefähr sechs Sekunden. Denken Sie daran, dass es sich um eine Standardausgabe handelt, und leiten Sie sie an eine Datei weiter.

Ich habe ein paar Haftungsausschlüsse. Zunächst schreibe ich dies auf einem Windows-PC. Ich denke, dass die Bibliotheken unter Linux alle vorhanden sind, aber wenn ich mich irre, sei darauf hingewiesen.

Außerdem werden genau eine halbe Milliarde durch Leerzeichen getrennte Ziffern ausgegeben, was technisch gesehen ein Gigabyte ist, aber vielleicht nicht genau das, was Sie wollten. Es gibt 5 Millionen Zeilen mit 100 Stellen pro Zeile aus. Wenn der Unterschied wichtig ist, können Sie die Anzahl der Zeilen erhöhen. Auf meiner Windows-Box scheint die Datei etwas größer als 10 ^ 9 Bytes zu sein, was meiner Meinung nach mit zusätzlichen Zeilenumbrüchen zu tun hat.

James Hollis
quelle
2
Hey, die Kritik ist nicht wirklich fair! :) Der größte Teil meines Programms ist das Parsen von Befehlszeilenparametern. Wenn ich auch Kommentare, Fehlerprüfungen und die Anzahl der ausgegebenen Spalten und Zeilen weglasse, kann ich Ihren Code weniger als doppelt so groß machen - kaum monstruös . :) Scherz beiseite: Ja, die Bibliotheken sind in den meisten Linux-Distributionen verfügbar. Auf meinem Laptop dauert der Verbindungsaufbau etwa 14 Sekunden, während meine Version für den Verbindungsaufbau nur 1,3 Sekunden dauert. Der Unterschied liegt nur am PRNG: Mersenne Twister ist so viel langsamer als Xorshift64 *.
Nominal Animal
1
Es gibt eine praktische Sache, auf die ich hinweisen möchte, dass Sie etwas verpasst haben, aber ich hoffe, Sie sehen es nicht als Negativ, sondern als Denkanstoß: Wie ich in meiner Antwort erwähnt habe, lohnen sich One-Shot-Programme selten Zeit, die sie zum Schreiben brauchten. Aus diesem Grund lohnt es sich fast immer, die Befehlszeilenanalyse und den Hilfetext hinzuzufügen. Ich habe eine große Anzahl solcher Hilfsprogramme, und anstatt ihre Quellen zu durchsuchen, um herauszufinden, was jeder von ihnen tut, führe ich sie einfach aus, damit sie mir Bescheid geben. und ich kann ihr Verhalten genug ändern, um mehr als einer Notwendigkeit zu entsprechen. Amortisierung der Entwicklungskosten.
Nominal Animal
@NominalAnimal Eine weitere wichtige Sache ist, dass Sie die Ausgabe weitergeleitet haben, /dev/nulldie weitaus schneller als das Schreiben in eine echte Datei wäre
phuclv
@ LưuVĩnhPhúc: Na ja, nicht wirklich. Dieser Laptop hat eine Samsung 128 GB SSD mit ~ 500 MB / s sequenziellem Lesen und Schreiben. Fügen Sie vier in eine Linux-Software-RAID0-Konfiguration ein, und Sie erhalten deutlich mehr als ein Gigabyte pro Sekunde Lese- und Schreibzugriff, wenn Sie so große Datensätze generieren (ich schätze ~ 1,75 TB / s). 1 GB / s wurde vor Jahren mit 12 SATA-Laufwerken (rotierende Platten, nicht einmal SSDs) mit Linux sw-RAID0 erreicht. (Hinweis: Bytes / s, nicht Bits / s.) Sicher, es klingt albern für eine "normale" Maschine, aber diejenigen, die mit großen Datenmengen spielen, finden das lohnenswert - Sie sparen Zeit bei allem , was Sie tun (mit großen Datenmengen). dieser Weg.
Nominal Animal
1
@NominalAnimal und Lu'u: Noch wichtiger ist, dass das Programm beendet werden kann, wenn Sie über genügend RAM verfügen, bevor alle Daten auf der Festplatte gespeichert sind. Der größte Teil der Arbeit in einem großen write()Systemaufruf ist ein Memcpy in den Pagecache, der nur blockiert, wenn der Kernel dies beschließt, anstatt mehr Pufferplatz zuzuweisen. Dieses Programm sollte nur dann einen Engpass bei Festplatten-E / A verursachen, wenn der Speicher knapp ist oder wenn Sie O_DIRECT zum Umgehen des Pagecaches verwendet haben. Wenn Sie write()Teile haben, die kleiner als der Cache sind, werden Ihre Daten hoffentlich nur einmal im Hauptspeicher abgelegt, und der neu geschriebene Puffer bleibt im L2- oder L3-Cache aktiv.
Peter Cordes
1

Dies hängt von Ihrer Definition von "zufällig" ab. Wenn Sie kryptografisch zufällig meinen, müssen Sie nur eine gute Bibliothek besorgen und die Kugel beißen, und warten, bis sie ausgeführt wird.

Wenn Sie nur etwas benötigen, das ziemlich zufällig aussieht, haben Sie hier eine einfache Möglichkeit:

  1. Holen Sie sich eine Datei, die mehrere GB lang ist. Dein Lieblingsfilm wird gut.
  2. Gzip it, eine einfache Möglichkeit, wiederholte Muster auszudrücken
  3. Durchsuchen Sie die Datei jeweils um ein Nybble (ein halbes Byte). Jeder Wert liegt zwischen 0 und 15. Werfen Sie weniger als 1 oder mehr als 10 weg. Subtrahieren Sie 1 von jeder der ersten Milliarden Überlebenden und schreiben Sie es als Ziffer aus.

Die Ausführung auf einem langsamen Computer kann eine Stunde dauern. schnell genug und zufällig genug für die meisten Zwecke.

Malvolio
quelle
9
/dev/urandomist wahrscheinlich besser als gzip, sowohl in der Geschwindigkeit als auch in der Zufälligkeit.
Stig Hemmer
Get a file that is several Gb longSie benötigen eine Datei ** mit mindestens 8 GB, um eine 1-GB-Datei zu erhalten
phuclv
1
#!/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
NamNT
quelle
1
Willkommen auf der Seite! Siehe Links auf meiner Profilseite. Es gibt hier sehr viele Probleme, die ich fast überall in Shell-Skripten sehe, aber das macht sie nicht richtig.
Wildcard
2
@Wildcard: Niemals cat file | trwenn du nur kannst tr <file. IIRC können Sie sogar <file tr. Ich dachte, Sie sprechen nur über dieses Shell-Skript, das klobig und langsam aussieht, wie du | awknach jeder Zeile, um die Größe zu überprüfen, und öffnen die Datei erneut, um jede Zeile anzuhängen, anstatt sie außerhalb der Schleife umzuleiten.
Peter Cordes
2
@ PeterCordes, ja. Warum wird die Verwendung einer Shell-Schleife zum Verarbeiten von Text als schlechte Praxis angesehen? ist besonders relevant - dieses Skript basiert auf der Idee, dass Bash eine Programmiersprache wie C ist, was nicht der Fall ist. Aber, \ @NamNT, ich hoffe du bleibst auf dieser Seite, denn es ist klar, dass du einen sehr logischen Verstand hast. :)
Wildcard
4
@PeterCordes cat /dev/urandom | busy-cmdist einer der seltenen Fälle, in denen es sinnvoll sein kann, die zufällige Generierung und den ausgelasteten Cmd zwischen Prozessoren aufzuteilen. Nicht so sehr für tr, aber es macht zum Beispiel einen Unterschied für Sam's od.
Stéphane Chazelas
1
@ StéphaneChazelas: oh richtig !! Ja, beim Systemaufruf read () wird die RNG-CPU-Zeit ausgegeben.
Peter Cordes