Quel est le moyen le plus rapide de générer un fichier texte de 1 Go contenant des chiffres aléatoires?

52

J'ai essayé un script bash, mais la création d'un fichier simple de 1 Mo a pris trop de temps. Je pense que la réponse réside dans l’utilisation de /dev/randomou /dev/urandom, mais d’autres publications n’expliquent que l’ajout de toutes sortes de données à un fichier à l’aide de ces éléments, mais j’aimerais n’ajouter que des chiffres.

Alors, y a-t-il une commande que je peux utiliser pour créer un fichier aléatoire de taille 1 Go contenant uniquement des nombres compris entre 0 et 9?

Edit: je veux que la sortie soit quelque chose comme ça

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

La plage est comprise entre 0 et 9, ce qui signifie uniquement les chiffres 0, 1, 2, 3, 4, 5, 6, 7, 8 et 9. Ils doivent également être séparés par un espace et être égaux à 100 par ligne, jusqu'au nnombre de lignes. C’est quelque chose qui m’importe peu, je veux que ma taille finale soit de 1 Go.

Edit: J'utilise Ubuntu 16.04 LTS

posixKing
la source
21
Vous devriez probablement dire ce que vous entendez par "aléatoire" - force cryptographique aléatoire, ou une séquence pseudo-aléatoire est-elle adéquate?
Toby Speight
4
@posixKing: Notez que bien que ma réponse soit parfaitement ironique, je ne suggère pas réellement d'écrire un programme C pour une telle tâche! - Si vous générez régulièrement de tels ensembles de données volumineux, ou si vous les générez souvent, cette approche peut vous faire gagner du temps. (Sur mon ordinateur portable, il génère 1 Go de chiffres séparés par des espaces en une dizaine de secondes.) Toutefois, s’il s’agit d’un événement ponctuel, n’envisagez même pas d’écrire un programme C pour cela (à moins que vous n'aimiez la programmation, tenez compte de cette pratique ou telle); les commandes de shell et les utilitaires réalisent la tâche en moins de temps et d’efforts consacrés.
Nominal Animal
7
C'est assez rapide et conforme à la norme RFC 1149.5:yes 4 | tr '\n' ' ' | fold -w 200 | head -c1G
Matthew Crumley

Réponses:

38

C'est en partie une réponse ironique, à cause du titre de la question.

Lorsque vous recherchez "le moyen le plus rapide de ..." , la réponse est presque toujours un outil spécialisé. Cela "réponses" montre un tel outil, juste pour que vous puissiez expérimenter.

Ce n'est pas une réponse sérieuse, car vous ne devriez pas rechercher d'outils spécialisés pour des tâches que vous ne faites qu'une fois ou très rarement. Vous verrez que vous finirez par passer plus de temps à chercher des outils et à en apprendre davantage sur eux que de faire des choses réellement. Les coquilles et les utilitaires n’apprécient pas bashet awkne sont pas les plus rapides, mais vous pouvez généralement écrire une seule ligne pour accomplir le travail, en ne dépensant que quelques secondes. On perlpeut également utiliser de meilleurs langages de script , bien que la courbe d'apprentissage perlsoit raide, et j'hésite à le recommander, car j'ai été traumatisée par de terribles projets Perl. pythonpar contre est légèrement handicapé par ses entrées / sorties plutôt lentes; ce n'est toutefois un problème que lorsque vous filtrez ou générez des giga-octets de données.

Dans tous les cas, l’exemple de programme C89 suivant (qui utilise POSIX.1 pour une horloge de précision supérieure uniquement si disponible) devrait atteindre un taux de génération d’environ 100 Mo / s (testé sous Linux sur un ordinateur portable doté d’un processeur Intel i5-4200U, en transférant la à /dev/null), en utilisant un assez bon générateur de nombres pseudo-aléatoires. (La sortie doit réussir tous les tests BigCrunch, à l'exception du test MatrixRank, car le code utilise xorshift64 * et la méthode d'exclusion pour éviter de biaiser les chiffres.)

chiffres décimaux.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;
}

Nous pouvons faire beaucoup plus rapidement si nous passons à une mémoire tampon de ligne, et fwrite()cela une fois au lieu de produire chaque chiffre à la fois. Notez que nous continuons de garder le flux entièrement mis en mémoire tampon pour éviter les écritures partielles (sans alimentation sur deux) si la sortie est un périphérique en mode bloc.

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

Remarque: les deux exemples ont été édités le 18/11/2016 pour assurer une distribution uniforme des chiffres (zéro est exclu; voir par exemple ici pour une comparaison et des détails sur divers générateurs de nombres pseudo-aléatoires).

Compiler en utilisant par exemple

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

et éventuellement installer à l'échelle du système à l' /usr/binaide

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

Il faut le nombre de chiffres par ligne et le nombre de lignes. Parce que 1000000000 / 100 / 2 = 5000000(cinq millions; total d'octets divisé par colonnes divisé par 2), vous pouvez utiliser

./decimal-digits 100 5000000 > digits.txt

générer le gigaoctet digits.txtsouhaité par l’opérateur.

Notez que le programme lui-même est écrit avec plus de lisibilité que d’efficacité. Mon intention ici n'est pas de montrer l'efficacité du code - j'utiliserais de toute façon POSIX.1 et les E / S de bas niveau, plutôt que les interfaces C génériques - mais de vous permettre de voir facilement quel type d'équilibre existe avec les efforts déployés en développant des outils dédiés par rapport à leurs performances, par rapport à des monolithes, des scripts courts shell ou awk

En utilisant la bibliothèque GNU C, l'appel de la fputc()fonction pour chaque sortie de caractère entraîne une très petite surcharge (d'un appel de fonction indirect ou conditionnel - l' FILEinterface est en fait assez complexe et polyvalente, vous voyez). Sur cet ordinateur portable Intel Core i5-4200U /dev/null, la première version (fputc) prend environ 11 secondes pour être redirigée vers la sortie , tandis que la version ligne à la fois ne prend que 1,3 seconde.

J'écris souvent de tels programmes et générateurs uniquement parce que j'aime jouer avec d'énormes jeux de données. Je suis bizarre comme ça. Par exemple, j’ai un jour écrit un programme pour imprimer toutes les valeurs à virgule flottante IEEE-754 positives finies dans un fichier texte, avec une précision suffisante pour obtenir la même valeur lors de l’analyse. La taille du fichier était de quelques gigaoctets (peut-être 4G environ); il n'y a pas autant de floats positifs finis qu'on pourrait le penser. Je l'ai utilisé pour comparer les implémentations qui lisent et analysent ces données.

Pour les cas d'utilisation normale, comme dans le cas du PO, les scripts shell, les scriptlets et les one-liners constituent la meilleure approche. Moins de temps passé pour accomplir la tâche globale. (Sauf s'ils ont besoin d'un fichier différent chaque jour ou à peu près, ou s'il y a beaucoup de personnes qui ont besoin d'un fichier différent, dans lequel - rarement - un outil dédié comme ci-dessus pourrait justifier l'effort consenti.)

Animal nominal
la source
Ouais, c’est probablement mmap()le moyen le plus simple d’atteindre la meilleure vitesse d’E / S - mais une référence avant de faire des déclarations!
Toby Speight
@TobySpeight: Sous Linux, les E / S de bas niveau, c'est-à-dire l'utilisation write(), sont généralement plus rapides que mmap(). fwrite()n'est pas beaucoup plus lent. Oui, j'ai comparé cela (mais pas pour cet exemple particulier); write()en gros morceaux (262144, 524288 ou 1048576 octets) a tendance à surperformer les autres méthodes. La version de fputc()mise en œuvre dans la bibliothèque GNU C (que j'ai également analysée de manière approfondie) est lente pour un certain nombre de raisons; en particulier, l'implémentation doit faire des sauts conditionnels ou des appels indirects pour chaque caractère ajouté; cette légère surcharge générée si souvent s'additionne.
Nominal Animal
Juste par intérêt - avez-vous fait une comparaison de performance avec les autres réponses?
Digital Trauma
2
@ DigitalTrauma: Je viens de les exécuter pour vous, redirigeant la sortie vers /dev/null. Le scriptlet de Stéphane Chazelas prend environ 52 secondes; perl snippet (y compris le headfiltrage) environ 58 secondes; votre shufextrait (avec le bon timing; vous ne mesurez que le temps shuf, en supposant que la pâte ne prendra pas plus longtemps) prend environ 69 secondes. Le programme C ++ 11 de James Hollis, une ligne à la fois, prend 14 secondes. Le programme ci-dessus prend 10 secondes.
Nominal Animal
3
(Désolée, j'ai perdu le fil de mes pensées ci-dessus.) Point, choisir le bon algorithme - le PRNG suffisamment aléatoire mais très rapide ici - a donné une augmentation de vitesse presque d'un ordre de grandeur (10 ×). (La dernière version de mes programmes est environ 40 fois plus rapide que les extraits de shell ou de Perl.) C'est typique. J'aurais peut-être dû insister sur le choix du bon algorithme lors de l'écriture d'un programme plus détaillé dans ma réponse ci-dessus? (D'un autre côté, ce n'est pas une question de programmation, mais une question Unix / Linux sur la façon de générer beaucoup de chiffres.)
Nominal Animal
81

Cette:

 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

(en supposant une headmise en œuvre qui prend en charge -c) semble être assez rapide sur mon système.

trtraduit la plage d'octets entière (0 à 255, 0 à 0377 en octal): les 25 premiers octets sont 0, les 25 suivants en tant que 1 ... puis 25 9 le reste (250 à 255) en "x", puis éliminez (avec tr -d x) car nous voulons une distribution uniforme (en supposant qu’elle /dev/urandomait une distribution uniforme elle-même) et ne donnons donc pas un biais à certains chiffres.

Cela produit un chiffre pour 97% des octets de /dev/urandom. fold -w 1en fait un chiffre par ligne. paste -sest appelé avec une liste de séparateurs qui se compose de 99 caractères d'espacement et d'un caractère de nouvelle ligne, afin d'avoir 100 chiffres séparés par des espaces sur chaque ligne.

head -c1Gobtiendra le premier GiB (2 30 ) de cela. Notez que la dernière ligne sera tronquée et non délimitée. Vous pouvez tronquer à 2 30 -1 et ajouter manuellement la nouvelle ligne manquante, ou tronquer à 10 9 octets, ce qui représente 50 millions de ces lignes de 200 octets (en head -n 50000000ferait également une commande standard / portable).

Ces temporisations (obtenues par zshun système à quatre coeurs) donnent une indication de l'endroit où le temps CPU est utilisé:

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

Le premier trest le goulot d'étranglement, la plupart du temps passé dans le noyau (je suppose pour la génération de nombres aléatoires). Le timing correspond approximativement au débit auquel je peux obtenir des octets /dev/uramdom(environ 19 Mo / s et nous produisons ici 2 octets pour chaque 0,97 octet de / dev / urandom à un débit de 32 Mo / s). foldsemble dépenser une quantité déraisonnable de temps processeur (15s) juste pour insérer un caractère de nouvelle ligne après chaque octet, mais cela n’affecte pas le temps total car il fonctionne sur un processeur différent dans mon cas (ajouter l’ -boption le rend très légèrement plus efficace, dd cbs=1 conv=unblocksemble être une meilleure alternative).

Vous pouvez vous en passer head -c1Get gagner quelques secondes en définissant une limite de taille de fichier ( limit filesize 1024mavec zshou ulimit -f "$((1024*1024))"avec la plupart des autres shells (y compris zsh)) à la place dans un sous-shell.

Cela pourrait être amélioré si nous extrayions 2 chiffres pour chaque octet, mais nous aurions besoin d'une approche différente pour cela. Ce qui précède est très efficace car il trsuffit de rechercher chaque octet dans un tableau de 256 octets. Cela ne peut pas être fait pendant 2 octets à la fois, et utiliser de telles choses hexdump -e '1/1 "%02u"'pour calculer la représentation textuelle d'un octet en utilisant des algorithmes plus complexes serait plus coûteux que la génération de nombres aléatoires elle-même. Néanmoins, si, comme dans mon cas, vous avez des cœurs de processeur dont le temps est compté, il peut encore arriver à gagner quelques secondes:

Avec:

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

Je reçois (notez cependant qu'il s'agit ici de 1 000 000 000 d'octets, par opposition à 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

Globalement, plus de temps processeur, mais mieux réparti entre mes 4 cœurs de processeurs, le temps de travail est donc réduit. Le goulot d'étranglement est maintenant hexdump.

Si nous utilisons ddau lieu de la ligne fold, nous pouvons réellement réduire la quantité de travail hexdumpà faire et améliorer l'équilibre du travail entre les processeurs:

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

(en supposant ici que GNU est ddson iflag=fullblocket status=none) ce qui donne:

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

Retour à la génération de nombres aléatoires étant le goulot d'étranglement.

Maintenant, comme l'a souligné @OleTange, si vous avez l' opensslutilitaire, vous pouvez l'utiliser pour obtenir un générateur d'octets pseudo-aléatoire plus rapide (en particulier sur les processeurs dotés d'instructions AES).

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

sur mon système génère 15 fois plus d'octets par seconde que /dev/urandom. (Je ne peux pas dire comment cela se compare en termes de source aléatoire d'aléas sécurisée par cryptographie si cela s'applique à votre cas d'utilisation).

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

Donne maintenant:

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

Retour à hexdumpêtre le goulot d'étranglement.

Comme il me reste encore des processeurs, je peux en exécuter 3 hexdumpen parallèle.

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

(le <&3est nécessaire pour les shells autres que les zshcommandes stdin sur / dev / null des commandes de fermeture lorsqu'il est exécuté en arrière-plan).

Maintenant, à 6,2 secondes et mes processeurs presque pleinement utilisés.

Stéphane Chazelas
la source
3
Je viens de supprimer ma réponse précédente et de voter pour celle-ci. Je n'ai pas eu certaines des exigences. Belle réponse d'ailleurs.
Marcelo
3
pourquoi ne générez-vous pas plusieurs chiffres à chaque passage? Même si vous lisez octet par octet, vous pouvez toujours produire 2 chiffres à chaque fois
phuclv
@ LưuVĩnhPhúc, j'ai supprimé la perlvariante qui était nettement plus lente de toute façon. Je ne peux pas obtenir 2 chiffres par octet avec cette approche tr | fold | paste.
Stéphane Chazelas
Je suis afk ou j'essayais cela moi-même, mais vous pourriez essayer de convertir 42 octets à la fois en 100-102 chiffres en utilisant bc(laissez tomber les 0, 1 ou les 2 chiffres les plus significatifs).
Eric Towers
gitlab.com/ole.tange/tangetools/tree/master/rand génère 1-4 Go de pseudo-aléatoires par seconde (qualité AES).
Ole Tange
23

Si vous avez à shufdisposition (récemment, GNU coreutils en a), vous pouvez le faire:

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

Sur ma machine virtuelle, cela est maintenant un peu plus lent que la réponse de Stéphane d'environ 3: 4.

Trauma numérique
la source
shufsur mon entreprise PC n'a pas -r, fmtn'a pas -gtrop
phuclv
2
@ LưuVĩnhPhúc Yep - YMMV. J'ai trouvé la version 8.25 de core-utils en possède, mais pas la version 8.4. Quelle version utilisez-vous?
Trauma numérique
1
J'utilise coreutils 8.13
phuclv
@ StéphaneChazelas intelligent paste/ printfastuce - merci. Votre réponse est maintenant apparemment plus rapide.
Digital Trauma
17

Si vous n'avez pas besoin d'aléatoire de très haute qualité et que la distribution presque uniforme convient, vous pouvez aller très vite, en particulier sur un processeur moderne doté de vecteurs entiers SIMD efficaces tels que x86 avec SSE2 ou AVX2.

Cela ressemble à la réponse de @ NominalAnimal puisque nous avions tous deux la même idée, mais vectorisés manuellement pour x86. (Et avec des nombres aléatoires de qualité médiocre, mais toujours suffisants pour de nombreux cas d'utilisation.) Cela s'exécute environ 15 ou 30 fois plus rapidement que le code de @ Nominal, à environ 13 Go / s de sortie ASCII sur un Intel Haswell cadencé à 2,5 GHz. CPU avec AVX2. C’est toujours moins que la bande passante maximale théorique de la mémoire principale (la DDR3-1600 à double canal est d’environ 25,6 Go / s), mais j’étais en train d’écrire sur / dev / null; Skylake devrait exécuter ce même code considérablement plus rapidement que Haswell (voir le bas de cette réponse).

En supposant que vous ayez un goulot d’étranglement sur les entrées / sorties sur le disque ou sur une tuyauterie quelque part, une implémentation rapide signifie que votre processeur n’a même pas besoin d’être plus rapide qu’au ralenti. Il utilise beaucoup moins d'énergie totale pour produire le résultat. (Vie de la batterie / chaleur / réchauffement climatique.)

C'est tellement rapide que vous ne voulez probablement pas l'écrire sur le disque. Il suffit de générer de nouveau au besoin (à partir de la même graine si vous voulez à nouveau les mêmes données). Même si vous souhaitez le transmettre à un processus multithread pouvant utiliser tous les processeurs, son exécution pour y diriger les données le laissera chaud dans le cache L3 (et le cache L2 du noyau qui l'a écrit), et peu de temps processeur. (Mais notez que la tuyauterie ajoute beaucoup de frais généraux par rapport à l’écriture /dev/null. Sur un Skylake i7-6700k, la tuyauterie vers wc -cou un autre programme qui lit juste + supprime son entrée, c’est environ 8 fois plus lent que l’écriture/dev/null , et n’utilise que 70% CPU, mais cela reste 4,0 Go / s sur un processeur 3.9GHz.

La régénérer est plus rapide que de le relire même à partir d'un SSD rapide connecté par PCIe, mais un IDK s'il est plus économe en énergie (le multiplicateur de vecteur entier est assez occupé et il est probablement très gourmand en énergie, avec d'autres AVX2 256b ALU vectorielles). OTOH, je ne sais pas combien de temps CPU lire sur un disque enlèverait quelque chose qui dépassait tous les cœurs traitant cette entrée. J'imagine qu'un changement de contexte pour générer de nouveau des morceaux de 128 Ko pourrait être concurrentiel avec le code de système de fichiers / pagecache en cours d'exécution et l'allocation de pages pour la lecture de données à partir du disque. Bien sûr, si il fait déjà chaud dans la pagecache, c’est tout simplement mémorable. OTOH, nous écrivons déjà à peu près aussi vite que memcpy! (qui doit partager la bande passante de la mémoire principale entre la lecture et l’écriture). (Notez également que l'écriture en mémoire que 'rep movsb(optimisé memcpy et memset dans le microcode, ce qui évite les RFO, puisque Andy Glew l’a implémenté dans P6 (Pentium Pro )).


Jusqu'à présent, il ne s'agit que d'une preuve de concept et la gestion de la nouvelle ligne n'est qu'approximativement correcte. C'est faux autour des extrémités d'un tampon de puissance de 2. Avec plus de temps de développement. Je suis convaincu que je pourrais trouver un moyen plus efficace d'insérer des nouvelles lignes tout à fait corrects, avec des frais généraux au moins aussi faibles que cela (par rapport à la sortie d'espaces uniquement). Je pense que c'est quelque chose comme 10 à 20%. Je voudrais seulement savoir à quelle vitesse nous pourrions faire cela, et non pas en avoir une version perfectionnée. Je laisserai donc cette partie comme un exercice pour le lecteur, avec des commentaires décrivant certaines idées.


Sur un Haswell i5 à son turbo maxi de 2,5 GHz, avec une RAM DDR3-1600 MHz , chronométré à 100 GiB mais réduit. (Chronométré sur cygwin64 sur Win10 avec gcc5.4 -O3 -march=native, omis -funroll-loopscar j'avais assez de mal à obtenir un timing correct sur cet ordinateur portable emprunté. Il aurait fallu démarrer Linux sur une clé USB).

écrire dans / dev / null sauf indication contraire.

  • James Hollis's: (non testé)
  • La version fwrite de Nominal: ~ 2.21s
  • this (SSE2): ~ 0,142 (temps non mis à l'échelle = réel = 14,232s, utilisateur = 13,999s, sys = 0,187s).
  • ceci (AVX-128): ~ 0.140s
  • this (AVX2): ~ 0,073 s (non mis à l'échelle: réel = 0m7,291s, utilisateur = 0m7,125s, sys = 0m0,155s).
  • cette tuyauterie cygwin (AVX2) vers wc -c, avec une taille de mémoire tampon de 128 Ko: 0,32 seconde avec un processeur à 2,38 GHz (turbo dual-core max). (Temps non mis à l'échelle: réel = 32.466s utilisateur = 11.468s sys = 41.092s, y compris ceci et wc). Cependant, seulement la moitié des données ont été copiées, car mon programme idiot suppose que l’écriture remplit la totalité du tampon, même si ce n’est pas le cas et que cygwin write () ne produit que 64k par appel dans un tube.

Donc, avec SSE2, il est environ 15 fois plus rapide que le code scalaire de @Nominal Animal. Avec AVX2, c'est environ 30 fois plus rapide. Je n'ai pas essayé une version du code de Nominal qui utilise simplement write()au lieu de fwrite(), mais vraisemblablement pour les grands tampons, stdio reste généralement à l'écart. S'il s'agit de copier les données, cela entraînerait beaucoup de ralentissement.


Il est temps de produire 1 Go de données sur un Core2Duo E6600 (caches Merom 2,4 GHz, L1 privé 32 koB, caches L2 partagés 4 Mo), DDR2-533 MHz sous Linux 4.2 64 bits (Ubuntu 15.10). Toujours en utilisant une taille de tampon de 128kiB pour write (), je n’ai pas exploré cette dimension.

écrire dans / dev / null sauf indication contraire.

  • (SSE2) cela avec une manipulation de nouvelle ligne et 4 vecteurs de chiffres de chaque vecteur d'octets aléatoires: 0,183s (chronométré en faisant 100GiB en 18.3s, mais des résultats similaires pour les exécutions 1GiB). 1,85 instructions par cycle.
  • (SSE2) cela, la tuyauterie à wc -c: 0.593s (non mis à l'échelle: real = 59.266s utilisateur = 20.148s sys = 1m6.548s, temps de calcul de wc compris). Même nombre d'appels système write () que pour cygwin, mais en réalité, canalisation de toutes les données, car Linux gère tous les 128k d'un write () vers un canal.
  • La fwrite()version de NominalAnimal (gcc5.2 -O3 -march=native), fonctionnant avec ./decdig 100 $((1024*1024*1024/200)) > /dev/null: 3.19s +/- 0.1%, avec 1,40 instruction par cycle. Les boucles de compression ont peut-être fait une petite différence. clang-3.8 -O3 -march=native: 3.42s ± 0.1%
  • Piping nominal fwriteà wc -c: real = utilisateur 3.980 = 3.176s sys = 2.080s
  • Version par ligne de James Hollis ( clang++-3.8 -O3 -march=native): 22.885s +/- 0.07%, avec 0.84 instructions par cycle. (g ++ 5,2 était légèrement plus lent: 22,98s). Écrire une ligne à la fois a probablement fait très mal.
  • Stéphane Chazelas's tr < /dev/urandom | ...: real = 41.430s user = 26.832s sys = 40.120s. trLa plupart du temps, la totalité du cœur de la CPU était occupée par lui-même, passant presque tout son temps dans le pilote du noyau à générer des octets aléatoires et à les copier dans un canal. L'autre cœur de cette machine double cœur exécutait le reste du pipeline.
  • time LC_ALL=C head -c512M </dev/urandom >/dev/null: c'est- à- dire en train de lire autant d'aléas sans tuyauterie: real = 35.018s user = 0.036s sys = 34.940s.
  • Programme perl de Lưu Vĩnh Phúc (perl v5.20.2 d'Ubuntu15.10)
    LANG=en_CA.UTF-8:: real = 4m32.634s user = 4m3.288s sys = 0m29.364.
    LC_ALL=C LANG=C: real = 4m18.637s user = 3m50.324s sys = 0m29.356s. Toujours très lent.

  • (SSE2) ceci sans traitement de saut de ligne , ni avec 3 ou 4 vecteurs de chiffres de chaque vecteur d'octets aléatoires (presque exactement la même vitesse: l' dig3 = v%10étape concerne le seuil de rentabilité sur ce matériel): 0,166 (1,82 instructions par cycle) . C’est fondamentalement la limite inférieure de ce que nous pouvons approcher avec une manipulation de nouvelle ligne parfaitement efficace.

  • (SSE2) Ancienne version de cette manipulation sans saut de ligne, mais seulement obtenir un chiffre par élément uint16_t à l' aide v%10, 0.222 secondes +/- 0,4%, 2.12 instructions par cycle. (Compilé avec gcc5.2, les -march=native -O3 -funroll-loopsboucles de déroulage peuvent aider pour ce code sur ce matériel. Ne l'utilisez pas aveuglément, en particulier pour les gros programmes).
  • (SSE2) Ancienne version de cette opération, écriture dans un fichier (sur un disque RAID10f2 de 3 disques durs magnétiques rapides, pas très optimisé pour les écritures): ~ 4 secondes. Pourrait aller plus vite en modifiant les paramètres de la mémoire tampon d'E / S du noyau afin de permettre beaucoup plus de données altérées avant les blocs write (). Le temps "système" est toujours ~ 1,0 seconde, beaucoup plus élevé que le temps "utilisateur". Sur cet ancien système avec une mémoire vive DDR2-533 lente, il faut environ 4x plus de temps au noyau pour mémoriser les données dans la page de cache et exécuter les fonctions XFS plutôt que pour ma boucle afin de continuer à les réécrire sur place dans une mémoire tampon qui reste chaude. cache.

Comment c'est fait

Un PRNG rapide est évidemment essentiel. xorshift128 + peut être vectorisé, vous avez donc deux ou quatre générateurs 64 bits en parallèle, dans des éléments d’un vecteur SIMD. Chaque étape produit un vecteur complet d'octets aléatoires. ( Implémentation AVX2 256b ici avec les composants intrinsèques Intel ). Je l'ai choisi par rapport au choix de xorshift * de Nominal, car la multiplication vectorielle entière sur 64 bits n'est possible que dans SSE2 / AVX2 avec des techniques de précision étendue .


Avec un vecteur d'octets aléatoires, nous pouvons découper chaque élément de 16 bits en plusieurs chiffres décimaux. Nous produisons plusieurs vecteurs d'éléments 16 bits qui sont chacun un chiffre ASCII + un espace ASCII . Nous stockons cela directement dans notre tampon de sortie.

Ma version originale x / 6554consistait simplement à obtenir un chiffre aléatoire de chaque élément uint16_t d'un vecteur. C'est toujours entre 0 et 9 inclus. C'est biaisé 9, car ce (2^16 -1 ) / 6554n'est que 9.99923. (6554 = ceil ((2 ^ 16-1) / 10), ce qui garantit que le quotient est toujours <10.)

x/6554peut être calculé en multipliant par une constante "magique" ( la réciproque en virgule fixe ) et un décalage à droite du résultat supérieur. C'est le meilleur cas pour la division par une constante; certains diviseurs prennent plus d'opérations, et la division signée prend un travail supplémentaire. x % 10a un biais similaire et n'est pas aussi bon marché pour calculer. (la sortie asm de gcc est équivalent à x - 10*(x/10), soit une multiplication et de soustraction supplémentaire sur le dessus de la division en utilisant un inverse multiplicatif modulaire.) En outre, le bit le plus bas de xorshift128 + ne sont pas aussi haute qualité , de sorte que la division de prendre l' entropie de bits de poids fort est meilleur ( pour la qualité ainsi que la vitesse) que modulo pour prendre l’entropie des bits bas.

Cependant, nous pouvons utiliser plus d'entropie dans chaque uint16_t en regardant les chiffres décimaux bas, comme la digit()fonction de @ Nominal . Pour des performances maximales, j'ai décidé de prendre les 3 chiffres décimaux les plus bas et x/6554, pour enregistrer un PMULLW et un PSUBW (et probablement du MOVDQA) par rapport à l'option de qualité supérieure consistant à prendre les 4 chiffres décimaux les plus bas. x / 6554 est légèrement affecté par les 3 chiffres décimaux, il existe donc une corrélation entre les chiffres du même élément (séparation de 8 ou 16 chiffres dans la sortie ASCII, en fonction de la largeur du vecteur).

Je pense que gcc divise par 100 et par 1000, plutôt que par une chaîne plus longue qui se divise successivement par 10, de sorte que cela ne raccourcit probablement pas de manière significative la longueur de la chaîne de dépendance non acheminée par boucle qui produit 4 résultats pour chaque sortie de PRNG. port0 (vecteur multiplier et déplacer) est le goulot d'étranglement en raison des inverses multiplicatifs modulaires et des changements dans xorshift +, il est donc certainement utile de sauvegarder un vecteur multiplier.

xorshift + est si rapide que même utiliser seulement ~ 3,3 bits d’aléatoire sur 16 (soit une efficacité de 20%) n’est pas beaucoup plus lent que de le découper en plusieurs chiffres décimaux. Nous ne faisons qu’approximer la distribution uniforme, car cette réponse est axée sur la rapidité tant que la qualité n’est pas mauvaise.

Tout type de comportement conditionnel qui conserve un nombre variable d'éléments nécessiterait beaucoup plus de travail. (Mais pourrait peut-être encore être fait assez efficacement en utilisant les techniques de gauchissement SIMD . Cependant, cela devient moins efficace pour les éléments de petite taille; les tables de recherche de masques de masques géants ne sont pas viables, et il n'y a pas de mélange de passages de voies AVX2 inférieur à 32 - Une version PSHUFB de 128b pourrait toujours générer un masque à la volée avec BMI2 PEXT / PDEP, comme vous pouvez le faire pour AVX2 avec des éléments plus volumineux , mais cela pose problème, car un entier de 64 bits ne contient que 8 octets. sur cette réponse a un code qui pourrait fonctionner pour un nombre plus élevé d'éléments.)


Si la latence du générateur de ressources aléatoires est un goulot d'étranglement, nous pourrions aller encore plus vite en exécutant deux vecteurs de générateurs en parallèle, en alternant celui que nous utilisons. Le compilateur peut toujours conserver facilement tous les registres dans une boucle déroulée, ce qui permet aux deux chaînes de dépendance de s'exécuter en parallèle.

Dans la version actuelle, en découpant la sortie du PRNG, nous avons en fait un goulot d'étranglement sur le débit du port 0, et non du temps de latence du PRNG. Ce n'est donc pas nécessaire.


Le code: version AVX2

Version complète avec plus de commentaires sur l'explorateur du compilateur Godbolt .

Pas très bien rangé, désolé je dois me coucher et je veux que ça soit posté.

Pour obtenir la version SSE2, s/_mm256/_mm, s/256/128/, s/v16u/v8u/et le changement vector_size(32)à 16 changer également l'incrément de 4 * retour à la ligne 16-4 * 8. (Comme je l'ai dit, le code est complexe et mal configuré pour la compilation de deux versions. Je n'avais pas prévu au départ de créer une version AVX2, mais je voulais vraiment tester sur un processeur Haswell auquel j'avais accès.)

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

}

Compilez avec gcc, clang ou ICC (ou, espérons-le, avec tout autre compilateur comprenant le dialecte GNU C de C99 et les éléments intrinsèques d’Intel). Les extensions de vecteur GNU C sont très pratiques pour permettre au compilateur de générer les nombres magiques pour division / modulo à l’aide d’inverses multiplicatifs modulaires, et les __attribute__s occasionnels sont utiles.

Cela pourrait être écrit de manière portable, mais cela prendrait plus de code.


Notes de performance:

Le magasin qui se chevauche pour insérer des nouvelles lignes a un temps système important pour décider où le placer (erreurs de prédiction de succursale et goulots d'étranglement frontaux sur Core2), mais le magasin lui-même n'a aucun impact sur les performances. En commentant uniquement cette instruction de stockage dans l'asm du compilateur (en laissant toutes les branches identiques), les performances sur Core2 sont restées inchangées, les exécutions répétées donnant le même temps à +/- moins de 1%. Je conclus donc que le tampon de mémoire tampon / cache s’en occupe parfaitement.

Néanmoins, utiliser une sorte de fenêtre tournante ascii_digitspaceavec un élément ayant une nouvelle ligne pourrait être encore plus rapide, si nous déroulons suffisamment pour que les compteurs / ramifications disparaissent.


L'écriture dans / dev / null est fondamentalement une opération non-opérée, donc le tampon reste probablement chaud dans le cache L2 (256 ko par cœur sur Haswell). On attend une accélération parfaite des vecteurs 128b à 256b: il n’ya pas d’instructions supplémentaires et tout (y compris les magasins) se passe avec une largeur deux fois plus grande. La branche d'insertion de nouvelle ligne est prise deux fois plus souvent, cependant. Malheureusement, je n'ai pas eu le temps de ma configuration Haswell cygwin avec cette partie #ifdef.

2,5 GHz * 32B / 13,7 Go / s = 5,84 cycles par magasin AVX2 sur Haswell. C'est très bien, mais pourrait être plus rapide. Peut-être qu'il y a des frais généraux dans les appels système cygwin que je ne le pensais. Je n'ai pas essayé de commenter ceux-ci dans la sortie asm du compilateur (ce qui ferait en sorte que rien ne soit optimisé.)

La mémoire cache N1 peut gérer une mémoire de 32B par horloge et L2 n’est pas beaucoup de bande passante inférieure (latence plus élevée, cependant).

Lorsque j'ai consulté IACA il y a quelques versions (sans ramification pour les nouvelles lignes, mais en obtenant seulement un vecteur ASCII par vecteur RNG), il prédit quelque chose comme un magasin de vecteurs 32B par 4 ou 5 horloges.

J'espérais obtenir plus de rapidité en extrayant plus de données de chaque résultat RNG, en regardant moi-même l'asm, en considérant les guides d'Agner Fog et d'autres ressources d'optimisation pour lesquelles j'ai ajouté des liens dans le wiki du tag SO x86 .)

Il est probable que ce serait beaucoup plus rapide sur Skylake , où le vecteur entier se multiplie et que shift peut s'exécuter sur deux fois plus de ports (p0 / p1) que Haswell (p0 uniquement). xorshift et l'extraction des chiffres utilisent beaucoup de décalages et de multiplications. ( Mise à jour: Skylake l’utilise à 3,02 IPC, nous donnant 3,77 cycles par magasin AVX2 sur 32 octets , chronométrés à 0,030 s par itération de 1 Go, en écrivant /dev/nullsur Linux 4.15 sur i7-6700k à 3,9 GHz.


Il ne nécessite pas le mode 64 bits pour bien fonctionner . La version SSE2 est aussi rapide quand elle est compilée -m32, car elle n’a pas besoin de beaucoup de registres de vecteurs, et tous les calculs 64 bits sont effectués en vecteurs, et non en registres à usage général.

En réalité, il est légèrement plus rapide en mode 32 bits sur Core2, car la macro-fusion de comparaison / branche ne fonctionne qu'en mode 32 bits, de sorte qu'il y a moins d'ops pour le noyau en panne (18.3s (1.85 Instructions Per Clock) vs 16,9 s (2,0 IPC)). La taille de code plus petite de l'absence de préfixe REX aide également les décodeurs de Core2.

De plus, certains déplacements vectoriels reg-reg sont remplacés par des charges, car toutes les constantes ne sont plus corrigées dans les registres vectoriels. Étant donné que le débit de charge du cache N1 n'est pas un goulot d'étranglement, cela aide en réalité. (par exemple, la multiplication par un vecteur constant de set1(10): movdqa xmm0, xmm10/ pmullw xmm0, xmm1se transforme en movdqa xmm0, [constant]/ pmullw xmm0, xmm1.) Comme le MOVDQA régulier nécessite un port ALU, il rivalise avec le travail réel en cours, mais une charge MOVDQA ne concourt que pour la bande passante de décodage frontale. (Le fait d'avoir une adresse de 4 octets dans de nombreuses instructions annule en grande partie l'avantage de la sauvegarde des préfixes REX.

Je ne serais pas surpris si ce sont les gains réels qui proviennent de l’ajout de ALU MOVDQA uops, car l’interface devrait plutôt bien suivre la moyenne de 2,0 IPC.

Toutes ces différences disparaissent sur Haswell, où tout devrait fonctionner à partir du cache décodé-uop, sinon du tampon de bouclage. La macro-fusion de branche ALU + fonctionne dans les deux modes depuis Nehalem.

Peter Cordes
la source
6
J'adore comment tu es passé en "mode bête" dans le sujet! :) Plus important encore, il s'agit d'un excellent exemple du type de gains disponibles, si vous avez réellement besoin ou souhaitez optimiser les performances, en utilisant une connaissance de très bas niveau du matériel dont vous disposez. De plus, nous n'utilisons qu'un fil ici; La plupart des processeurs Intel / AMD pour ordinateurs de bureau et serveurs actuels (et même des processeurs ARM dans les tablettes légères et les SBC) ont plusieurs cœurs, de sorte qu'il existe encore des accélérations disponibles dans le monde réel. Enfin, à quel point "le moyen le plus rapide" est-il peu pratique , en raison des efforts déployés.
Nominal Animal
1
@NominalAnimal: Ouais, même un noyau ARM lent ou un noyau octo pourrait facilement saturer la bande passante de la mémoire principale en faisant la même chose avec NEON (même s’ils étaient raccordés à la DDR3 rapide à double canal), s’il intègre un décalage de 64 bits SIMD . Je suppose que NEON a des multiplications d’éléments 16 bits pour le travail audio. La planification des instructions nécessiterait beaucoup plus de travail pour un ARM en ordre, car chaque itération de la chaîne de dépendances véhiculées par la boucle (xorshift128 +) alimente quelques chaînes de dépendances indépendantes consistant à la couper et à la stocker dans la mémoire ...
Peter Cordes
... Une exécution hors service consomme cela au petit-déjeuner, car le tout est suffisamment court pour que plusieurs itérations tiennent dans la ROB (192 oups sur le HSW IIRC). (c’est-à-dire que la "fenêtre" d’instructions que l’exécution non conforme voit comprend plusieurs itérations). Ainsi, le processeur peut terminer le dernier magasin pendant 2 ou 3 itérations tout en commençant au début de l'itération en cours. Cela cache la latence des chaînes indépendantes, seul le débit compte. Sur un cœur en ordre, cela nécessiterait un traitement logiciel en pipeline ...
Peter Cordes
... Un bon compilateur ARM devrait en faire une partie pour vous si vous l'écrivez avec des éléments intrinsèques (ou la syntaxe de vecteur natif GNU C pour l'ensemble, comme j'aurais dû le faire auparavant). Je n'ai aucune expérience de ce type en réalité, vous devrez peut-être vous concentrer sur votre boucle et peut-être faire du déroulage manuel / du traitement en pipeline dans la source pour obtenir le bon résultat. (Certains noyaux ARM hors service se trouvent dans les téléphones haut de gamme, mais ils n’ont pas une fenêtre hors service aussi large que Haswell. OTOH, leur débit de pointe est également inférieur; gagner à trouver plus d’ILP).
Peter Cordes
1
@NominalAnimal: aussi, d'accord sur la bêtise de la question. "Le plus rapide" sans restrictions sur la qualité aléatoire est ridicule ... Avec BTRFS, les mêmes données sur disque peuvent faire partie d'un fichier à plusieurs reprises (voir EXTENT_SAME en 4.2 ). Ainsi, vous pouvez générer un 4kiB ou 1 Mo aléatoire et le répéter. C'est aléatoire avec une courte période, mais c'est quand même aléatoire et ça ne coûte que des métadonnées I / O. (En fait, vous avez besoin que le bloc se termine par une nouvelle ligne. Lcm (4096, 4096 * 200) = 4096 * 200 = 819200 = 800kiB, votre bloc de répétition est donc un multiple de celui-ci.)
Peter Cordes
14

Voici une solution que j'espère simple à comprendre:

od -An -x /dev/urandom | tr -dc 0-9 | fold -w100 | awk NF=NF FS= | head -c1G
  • odcrée un flux uniforme de chiffres hexadécimaux à partir de /dev/random.
  • trse débarrasse des lettres, ne garde que les 0-9chiffres
  • fold assure qu'il y a 100 chiffres par ligne
  • awk insère des espaces à l'intérieur des lignes
  • head tronque l'entrée à 1 gigaoctet
sam hocevar
la source
2
C'est une bonne alternative pour produire plus d'un chiffre par octet de / dev / random tout en conservant une distribution uniforme, ce qui produit 320 chiffres pour chaque 256 octets de / dev / urandom en moyenne (moins que lorsque vous convertissez des octets <200 modulo 100 à la décimale, ce qui vous donne cependant 400 chiffres pour 256 octets).
Stéphane Chazelas
6

Vous pouvez utiliser la jotcommande pour cela:

jot -r 50000000 0 9 | fmt -w 200 > output.txt
tête de jardin
la source
1
@DigitalTrauma Ma version de fmtn'a pas d'option de largeur de but. Quoi qu'il en soit, ce sera exact car tous les chiffres occupent exactement une colonne!
Gardenhead
Pour mémoire, ma fmtversion est fmt (GNU coreutils) 8.25(Ubuntu 16.04)
Digital Trauma
2
le bon numéro pour un demi-Go est: 1024 * 1024 * 1024/2 =536870912
Olivier Dulac
1
@OlivierDulac Cela dépend du "gigaoctet" dont vous parlez. Certaines personnes utilisent 1 Go pour signifier 10 ^ 9 au lieu de 2 ^ 30, même si c'est techniquement incorrect. De plus, j'aime bien les chiffres ronds :)
gardenhead
6
@gardenhead, de plus en plus de gens ont maintenant tendance à migrer vers Gigabyte == 1e9 et Gibibyte == 2 ^ 30, ce qui correspond à la définition standard de la CEI. Voir Wikipedia . Notez que Gb lui - même serait plutôt giga- peu .
Stéphane Chazelas
6

Cette méthode est similaire à celle de Stéphane Chazelas, mais je lis simultanément 64 bits pour améliorer les performances. La distribution est toujours uniforme mais vous obtenez maintenant 19 chiffres pour chaque 8 octets au lieu de 8 dans le meilleur des cas comme avant

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

Sur la plate-forme 32 bits, 9 chiffres seront lus à chaque fois au lieu de 19.

phuclv
la source
Cela peut générer une exception si votre système ne prend pas en charge l'entier 64 bits ou perln'est pas compilé avec une prise en charge quadruple.
jeudi
@ cuonglm oui comme je l'ai dit si perl n'a pas 64 bits sur ce système, il faut changer le programme next if $n >= 1000000000; $s = sprintf("%09u", $n);pour obtenir seulement 9 chiffres
phuclv
Vous ne pouvez pas, le programme tombera en panne $n = unpack("Q")si quad n'est pas supporté.
jeudi
1
@cuonglm change BEGIN{$/=\4; $,=" "} $n = unpack("L");aussi
phuclv
1
Désolé, mais cela donne 19 chiffres à partir d'une entrée de 8 octets. environ 54,2% du temps, mais pas le reste, avec une moyenne de 1,29 digits par octet en entrée. Si vous utilisez plus comme Stéphane et que vous le <16e18divisez par 16, vous obtenez 18 chiffres 86,7% pour 1,95 dpB. Avec 32 bits, <4e9 /4obtient 9 chiffres 93,1% pour 2,10 dpB. Mais 5 octets (sous forme hexadécimale (H10)) <1e12donnent 12 chiffres à 90,9% pour 2,18 dpB, ou diviser l’hexagone en deux et <1e6 donner chaque moitié à 6 chiffres à 95,4% pour 2,29 dpB; cela approche la limite de log_10 (256) = 2,41.
dave_thompson_085
3

Je suis plutôt d'accord avec Nominal Animal pour utiliser un langage de programmation compilé si vous avez besoin de rapidité. Cependant, vous n'avez pas besoin d'écrire votre propre code RNG en C. C ++ 11 offre l'excellent Mersenne Twister dans le cadre de sa bibliothèque standard.

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

Le code ci-dessus est relativement simple et prend environ une minute lorsque je dirige la sortie vers un fichier. Nous pouvons aller beaucoup plus vite en créant une chaîne pouvant contenir 100 chiffres et en la piratant. Cela nous permet d'appeler chaque ligne plutôt que chaque chiffre.

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

Ce code prend ma machine environ six secondes. Rappelez-vous qu'il s'agit d'une sortie standard, transmettez-la dans un fichier.

J'ai quelques dénis de responsabilité. Tout d'abord, j'écris ceci sur un PC Windows. Je pense que les bibliothèques sont toutes présentes sous Linux, mais si je me trompe, assurez-vous de le préciser.

En outre, il génère exactement un demi-milliard de chiffres séparés par des espaces, ce qui est techniquement un gigaoctet mais peut-être pas exactement ce que vous vouliez. Il génère 5 millions de lignes, 100 chiffres par ligne. Si la différence est importante, vous pouvez augmenter le nombre de lignes. Sur ma machine Windows, le fichier semble légèrement plus grand que 10 ^ 9 octets, ce qui, je pense, a quelque chose à voir avec des caractères de nouvelle ligne supplémentaires.

James Hollis
la source
2
Hé, la critique n'est pas vraiment juste! :) La majeure partie de mon programme est l'analyse de paramètres en ligne de commande. Si j'omets également les commentaires, les vérifications d'erreur et le code du nombre de colonnes et de lignes générées, je peux le rendre moins de deux fois la taille de votre code - à peine monstrueux . :) Blague à part: Oui, les bibliothèques sont disponibles dans la plupart des distributions Linux. Sur mon ordinateur portable, votre ligne à la fois prend environ 14 secondes, alors que ma version à la fois ne prend que 1,3 seconde. La différence est uniquement due au PRNG: Mersenne Twister est beaucoup plus lent que Xorshift64 *.
Animal nominal
1
J'aimerais souligner une chose pratique que vous avez manquée, mais j'espère que vous ne la prenez pas pour de la négativité, mais plutôt pour réfléchir: comme je l'ai mentionné dans ma réponse, les programmes ponctuels en valent rarement la peine. le temps qu'ils ont pris pour écrire. C'est pourquoi l'ajout d'une analyse de ligne de commande et du texte d'utilisation de l'aide en vaut presque toujours la peine. J'ai un grand nombre de programmes utilitaires de ce type et, plutôt que de rechercher leurs sources pour découvrir ce que fait chacun d'entre eux, je les exécute simplement pour qu'ils me le disent; et je peux modifier leur comportement assez pour répondre à plus d'un besoin. Amortissement des coûts de développement.
Nominal Animal
@NominalAnimal Une autre chose importante est que vous avez canalisé la sortie vers /dev/nulllaquelle serait beaucoup plus rapide que l'écriture dans un fichier réel
phuclv
@ LưuVĩnhPhúc: Eh bien, pas vraiment. Cet ordinateur dispose d’un SSD de 128 Go Samsung, avec des lectures et écritures séquentielles d’environ 500 Mo / s. Si vous mettez quatre dans une configuration logicielle RAID0 sous Linux, vous obtiendrez plus de 1 Go de lecture et d'écriture lors de la génération de jeux de données aussi volumineux (j'estime environ 1,75 To / s). 1 Go / s a ​​été atteint il y a des années avec 12 disques SATA (plateaux tournants, pas même SSD) avec Linux sw-RAID0. (Remarque: octets / s, pas bits / s.) Bien sûr, cela semble idiot pour une machine "normale", mais ceux qui jouent avec de grands ensembles de données trouvent cela intéressant - vous gagnez du temps ( tout avec de grands ensembles de données) de cette façon.
Nominal Animal
1
@NominalAnimal et Lu'u: Plus important encore, si vous avez assez de RAM, le programme peut se terminer bien avant que toutes les données ne soient sur disque. La plupart du travail dans un write()appel système volumineux est une mémoire dans la pagecache, qui ne se bloque que si le noyau décide de le faire au lieu d’allouer plus d’espace tampon. Ce programme ne doit être goulot d’étranglement sur les E / S de disque que lorsque la mémoire est saturée ou si vous avez utilisé O_DIRECT pour contourner le pagecache. Si vous write()utilisez des morceaux de taille inférieure à la taille du cache, il est à espérer que vos données ne seront stockées qu'une seule fois dans la mémoire principale et que le tampon réécrit sur place reste actif dans le cache L2 ou L3.
Peter Cordes
1

Cela dépend de votre définition de "aléatoire". Si vous voulez dire par cryptographie aléatoire, il vous suffit d’avoir une bonne bibliothèque et de mordre la balle, attendez qu’elle s’exécute.

Si vous avez juste besoin de quelque chose d'assez aléatoire, voici un moyen simple:

  1. Obtenez un fichier de plusieurs Go de long. Votre film préféré sera bon.
  2. Gzip it, un moyen facile de faire sortir les motifs répétés
  3. Parcourez le fichier nybble (un demi-octet) à la fois. Chaque valeur sera comprise entre 0 et 15. Jetez toute valeur inférieure à 1 ou supérieure à 10. Soustrayez 1 de chacun des premiers milliards de survivants et écrivez-le sous forme de chiffre.

Cela peut prendre une heure pour fonctionner sur une machine lente; assez rapide et assez aléatoire pour la plupart des buts.

Malvolio
la source
9
/dev/urandomest susceptible d'être meilleur que gzip, à la fois en vitesse et en caractère aléatoire.
Stig Hemmer
Get a file that is several Gb longvous aurez besoin d’un fichier ** d’au moins 8 Go pour obtenir un fichier de 1 Go
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
la source
1
Bienvenue sur le site! Voir les liens sur ma page de profil. Il y a beaucoup de problèmes ici que je vois presque universellement dans les scripts shell, mais cela ne les corrige pas.
Wildcard
2
@Wildcard: jamais cat file | trquand vous pouvez simplement tr <file. IIRC, vous pouvez même <file tr. Je pensais que vous parliez simplement de la lenteur de ce script shell, comme du | awkaprès chaque ligne pour vérifier la taille, et en rouvrant le fichier pour ajouter chaque ligne au lieu de rediriger en dehors de la boucle.
Peter Cordes
2
@PeterCordes, oui. Pourquoi utiliser une boucle shell pour traiter du texte est-il considéré comme une mauvaise pratique? est particulièrement pertinent - ce script est basé sur l'idée que Bash est un langage de programmation tel que C, ce qui n'est pas le cas. Mais, \ @NamNT, j'espère que vous restez sur ce site car il est clair que vous avez un esprit très logique. :)
Wildcard
4
@PeterCordes cat /dev/urandom | busy-cmdest l'un de ces rares cas où cela peut avoir un sens, car il peut diviser la génération aléatoire et la commande occupée entre les processeurs. Pas tellement pour tr mais fait une différence pour Sam, odpar exemple.
Stéphane Chazelas
1
@ StéphaneChazelas: ah oui !! Oui, l'appel système read () est l'endroit où le temps processeur RNG est utilisé.
Peter Cordes