Qual é a maneira mais rápida de gerar um arquivo de texto de 1 GB contendo dígitos aleatórios?

52

Tentei um script bash, mas demorou muito para criar um arquivo simples de 1 MB. Acho que a resposta está em usar /dev/randomor /dev/urandom, mas outras postagens aqui mostram apenas como adicionar todos os tipos de dados a um arquivo usando essas coisas, mas quero adicionar apenas números.

Então, existe um comando que eu possa usar para criar um arquivo aleatório de tamanho 1 GB contendo apenas números entre 0 e 9?

Edit: Eu quero que a saída seja algo como isto

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

O intervalo é de 0 a 9, significando apenas os números 0, 1, 2, 3, 4, 5, 6, 7, 8 e 9. Também preciso que eles sejam separados por espaço e 100 por linha, até o nnúmero de linhas. Isso é algo que eu não ligo, quero que meu tamanho final seja de 1 GB.

Edit: Estou usando o Ubuntu 16.04 LTS

posixKing
fonte
21
Você provavelmente deveria dizer o que quer dizer com "aleatório" - força criptográfica aleatória ou uma sequência pseudo-aleatória é adequada?
perfil completo de Toby Speight
4
@posixKing: Note que, embora minha resposta seja definitivamente explícita - na verdade não estou sugerindo escrever um programa C para essa tarefa! -, se você gera rotineiramente conjuntos de dados tão grandes ou com frequência, a abordagem pode economizar seu tempo. (No meu laptop, ele gera 1 GB de dígitos separados por espaço em cerca de dez segundos.) No entanto, se for um caso único, nem pense em escrever um programa C para isso (a menos que você goste de programar e considere isso prática ou tal); os comandos e utilitários do shell realizam a tarefa com menos tempo e esforço total gastos.
Animal Nominal
7
Isso é muito rápido e compatível com RFC 1149.5:yes 4 | tr '\n' ' ' | fold -w 200 | head -c1G
Matthew Crumley

Respostas:

38

Esta é parcialmente uma resposta explícita, por causa do título da pergunta.

Quando você procura "o caminho mais rápido para ..." , a resposta é quase sempre uma ferramenta especializada. Essas "respostas" mostram uma dessas ferramentas, apenas para que você possa experimentar.

Esta não é uma resposta séria, porque você não deve procurar ferramentas especializadas para trabalhos que realiza apenas uma vez ou muito raramente. Veja bem, você passará mais tempo procurando ferramentas e aprendendo sobre elas do que realmente fazendo coisas. Os reservatórios e utilitários gostam bashe awknão são os mais rápidos, mas geralmente você pode escrever uma linha para realizar o trabalho, gastando apenas alguns segundos. Linguagens de script melhores como perltambém podem ser usadas, embora a curva de aprendizado perlseja grande, e hesito em recomendá-la para tais propósitos, porque fiquei traumatizada por projetos perl terríveis. pythonpor outro lado, é um pouco prejudicado por sua E / S bastante lenta; é apenas um problema quando você filtra ou gera gigabytes de dados.

De qualquer forma, o exemplo de programa C89 a seguir (que usa o POSIX.1 para um relógio de maior precisão somente se disponível) deve atingir uma taxa de geração de cerca de 100 MB / s (testada no Linux em um laptop com um processador Intel i5-4200U, canalizando a saída para /dev/null), usando um bom gerador de números pseudo-aleatórios. (A saída deve passar em todos os testes do BigCrunch, exceto no teste MatrixRank, pois o código usa xorshift64 * e o método de exclusão para evitar distorções nos dígitos.)

dígitos decimais.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;
}

Podemos torná-lo muito mais rápido, se mudarmos para um buffer de linha, e fwrite()uma vez, em vez de emitir cada dígito por vez. Observe que ainda mantemos o fluxo totalmente em buffer, para evitar gravações parciais (sem potência de dois) se a saída for um dispositivo de bloco.

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

Nota: ambos os exemplos editados em 18/11/2016 para garantir a distribuição uniforme de dígitos (zero é excluído; veja, por exemplo, aqui para comparação e detalhes sobre vários geradores de números pseudo-aleatórios).

Compilar usando, por exemplo

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

e, opcionalmente, instalar todo o sistema para /usr/binusar

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

Leva o número de dígitos por linha e o número de linhas. Porque 1000000000 / 100 / 2 = 5000000(cinco milhões; bytes totais divididos por colunas divididas por 2), você pode usar

./decimal-digits 100 5000000 > digits.txt

para gerar o tamanho de gigabyte digits.txtconforme desejado pelo OP.

Observe que o próprio programa é escrito mais com legibilidade do que eficiência em mente. Minha intenção aqui não é mostrar a eficiência do código - eu usaria POSIX.1 e E / S de baixo nível de qualquer maneira, em vez de interfaces C genéricas - mas permitir que você veja facilmente que tipo de equilíbrio existe com o esforço despendido no desenvolvimento de ferramentas dedicadas versus seu desempenho, em comparação com one-liners ou shell curto ou scriptlets awk.

Usando a biblioteca GNU C, chamar a fputc()função para cada saída de caracteres gera uma sobrecarga muito pequena (de uma chamada de função indireta ou condicionais - a FILEinterface é realmente bastante complexa e versátil, você vê). Neste laptop Intel Core i5-4200U em particular, o redirecionamento da saída para /dev/nulla primeira versão (fputc) leva cerca de 11 segundos, enquanto a versão linha por vez leva apenas 1,3 segundos.

Por vezes, escrevo esses programas e geradores apenas porque gosto de brincar com grandes conjuntos de dados. Eu sou estranho assim. Por exemplo, uma vez eu escrevi um programa para imprimir todos os valores positivos de ponto flutuante IEEE-754 finitos em um arquivo de texto, com precisão suficiente para gerar exatamente o mesmo valor quando analisado. O arquivo tinha alguns gigabytes de tamanho (talvez 4G ou mais); não existem tantos floats positivos finitos como se poderia pensar. Eu usei isso para comparar implementações que lêem e analisam esses dados.

Para casos de uso normais, como o OP está tendo, scripts de shell, scriptlets e one-liners são a melhor abordagem. Menos tempo gasto para realizar a tarefa geral. (Exceto se eles precisarem de um arquivo diferente a cada dia ou mais, ou se houver muitas pessoas que precisem de um arquivo diferente, no qual, raro, uma ferramenta dedicada como a acima, justifique o esforço despendido.)

Animal Nominal
fonte
Sim, provavelmente mmap()é o caminho mais fácil para a melhor velocidade de E / S - mas faça uma referência antes de fazer qualquer reclamação!
perfil completo de Toby Speight
@TobySpeight: No Linux, a E / S de baixo nível, ou seja write(), o uso , normalmente é mais rápida que mmap(). fwrite()não é muito mais lento. Sim, comparei isso (mas não neste exemplo em particular); write()em pedaços grandes (262144, 524288 ou 1048576 bytes) tende a superar os outros métodos. A versão fputc()implementada na biblioteca GNU C (que eu também fiz extensivamente comparada) é lenta por vários motivos; em particular, a implementação precisa fazer saltos condicionais ou chamadas indiretas para cada caractere adicionado; que a pequena sobrecarga incorrida muitas vezes aumenta.
Animal Nominal
Apenas por interesse - você fez uma comparação de desempenho com as outras respostas?
Digital Trauma
2
@ DigitalTrauma: Acabei de executá-los para você, redirecionando a saída para /dev/null. O scriptlet de Stéphane Chazelas leva cerca de 52 segundos; snippet perl (incluindo a headfiltragem) cerca de 58 segundos; seu shufsnippet (com o tempo correto; você só mede o tempo shuf, supondo que a pasta não demore mais) leva cerca de 69 segundos. O C ++ 11 de James Hollis, um programa de linha por vez, leva 14 segundos. O programa acima leva 10 segundos.
Animal Nominal
3
(Perdi minha linha de raciocínio acima, desculpe.) A questão é que, ao escolher o algoritmo certo - o PRNG suficientemente aleatório, mas muito rápido aqui -, rendeu quase um aumento de velocidade na ordem de magnitude (10 ×). (A última versão dos meus programas é cerca de 40 vezes mais rápida que os snippets shell ou perl.) Isso é típico. Talvez eu devesse ter enfatizado a escolha do algoritmo certo ao escrever um programa mais na minha resposta acima? (Por outro lado, esta não é uma questão de programação, mas uma questão em Unix / Linux, sobre a forma de gerar lotes de dígitos.)
Nominal animal
81

Este:

 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

(assumindo uma headimplementação compatível -c) parece ser razoavelmente rápido no meu sistema.

trconverte todo o intervalo de bytes (0 a 255, 0 a 0377 em octal): os 25 primeiros bytes como 0, os 25 seguintes como 1 ... depois 259 o restante (250 a 255) para "x", que então descarte (com tr -d x) como queremos uma distribuição uniforme (supondo que ela /dev/urandomtenha uma distribuição uniforme) e, portanto, não forneça um viés para alguns dígitos.

Isso produz um dígito para 97% dos bytes de /dev/urandom. fold -w 1torna um dígito por linha. paste -sé chamado com uma lista de separadores que consiste em 99 caracteres de espaço e um caractere de nova linha, para ter 100 dígitos separados por espaço em cada linha.

head -c1Greceberá o primeiro GiB (2 30 ) disso. Observe que a última linha será truncada e não limitada. Você pode truncar para 2 30 -1 e adicionar a nova linha ausente manualmente, ou truncar para 10 9 bytes em vez disso, que são 50 milhões dessas linhas de 200 bytes ( head -n 50000000também o tornariam um comando padrão / portátil).

Esses tempos (obtidos zshem um sistema quad-core) fornecem uma indicação de onde o tempo da CPU é gasto:

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

O primeiro tré o gargalo da garrafa, na maioria das vezes gasto no kernel (suponho que seja para a geração de números aleatórios). O tempo está aproximadamente alinhado com a taxa pela qual posso obter bytes /dev/uramdom(cerca de 19MiB / se aqui produzimos 2 bytes para cada 0,97 byte de / dev / urandom a uma taxa de 32MiB / s). foldparece estar gastando uma quantidade razoável de tempo de CPU (15s) apenas para inserir um caractere de nova linha após cada byte, mas isso não afeta o tempo geral, pois funciona em uma CPU diferente no meu caso (adicionar a -bopção torna muito mais eficiente, dd cbs=1 conv=unblockparece ser uma alternativa melhor).

Você pode acabar com o head -c1Gcorte de alguns segundos e definir um limite no tamanho do arquivo ( limit filesize 1024mcom zshou ulimit -f "$((1024*1024))"com a maioria dos outros shells (inclusive zsh)) em vez de um subshell.

Isso poderia ser melhorado se extraíssemos 2 dígitos para cada byte, mas precisaríamos de uma abordagem diferente para isso. O acima é muito eficiente, porque trapenas procura cada byte em uma matriz de 256 bytes. Ele não pode fazer isso por 2 bytes de cada vez, e usar coisas como hexdump -e '1/1 "%02u"'essa que calcula a representação de texto de um byte usando algoritmos mais complexos seria mais caro que a própria geração de números aleatórios. Ainda assim, se, como no meu caso, você tiver núcleos de CPU cujo tempo de sobra, ele ainda poderá raspar alguns segundos:

Com:

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

Eu recebo (observe, porém, que aqui há 1.000.000.000 de bytes em oposição a 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

Mais tempo de CPU em geral, mas melhor distribuído entre meus 4 núcleos de CPU, por isso acaba levando menos tempo para o relógio de parede. O gargalo é agora hexdump.

Se usarmos em ddvez da linha fold, poderemos realmente reduzir a quantidade de trabalho hexdumpnecessária e melhorar o equilíbrio do trabalho entre as CPUs:

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

(assumindo aqui o GNU ddpor seu iflag=fullblocke status=none) que fornece:

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

De volta à geração de números aleatórios, sendo o gargalo.

Agora, como apontado por @OleTange, se você tiver o opensslutilitário, poderá usá-lo para obter um gerador de bytes pseudo-aleatórios mais rápido (especialmente em processadores que possuem instruções AES).

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

no meu sistema vomita 15 vezes mais bytes por segundo que /dev/urandom. (Não posso comentar como ele se compara em termos de fonte de aleatoriedade criptograficamente segura, se isso se aplica ao seu caso de uso).

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

Agora dá:

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

de volta a hexdumpser o gargalo.

Como ainda tenho CPUs de sobra, posso executar 3 hexdumpem paralelo.

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

( <&3é necessário para shells que não sejam os zshcomandos stdin de fechamento em / dev / null quando executados em segundo plano).

Agora com 6.2 segundos e minhas CPUs quase totalmente utilizadas.

Stéphane Chazelas
fonte
3
Acabei de excluir minha resposta anterior e votei nessa. Não recebi alguns dos requisitos. Boa resposta btw.
Marcelo
3
por que você não gera vários dígitos a cada passagem? Mesmo se você ler byte a byte, ainda poderá produzir 2 dígitos por vez
phuclv
@ LưuVĩnhPhúc, removi a perlvariante que era significativamente mais lenta de qualquer maneira. Não consigo obter 2 dígitos por byte com essa abordagem de colar | dobra |.
Stéphane Chazelas
Estou afk ou tentaria fazer isso sozinho, mas você poderia tentar converter 42 bytes de cada vez para 100 a 102 dígitos usando bc(depois solte os 0, 1 ou 2 dígitos mais significativos).
Eric Towers
gitlab.com/ole.tange/tangetools/tree/master/rand gera 1 a 4 GB de pseudoaleatório por segundo (qualidade AES).
precisa
23

Se você tem shufdisponível (o recente GNU coreutils possui), você pode fazer o seguinte:

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

Na minha VM, isso agora é um pouco mais lento que a resposta de Stéphane em um fator de 3: 4.

Trauma Digital
fonte
shufno meu PC empresa não tem -r, fmtnão tem -gmuito
phuclv
2
@ LưuVĩnhPhúc Sim - YMMV. Descobri que a versão 8.25 do core-utils possui esses, mas o 8.4 não. Qual versão você está usando?
Digital Trauma
11
Estou usando o coreutils 8.13 #
phuclv
@ StéphaneChazelas inteligente paste/ printftruque - obrigado. Sua resposta agora é aparentemente mais rápida.
Digital Trauma
17

Se você não precisa de aleatoriedade de qualidade muito alta e a distribuição quase uniforme é boa o suficiente, você pode ir muito rápido, especialmente em uma CPU moderna com vetores inteiros SIMD eficientes como x86 com SSE2 ou AVX2.

É a resposta do @ NominalAnimal, já que ambos tínhamos a mesma idéia, mas vetorizamos manualmente o x86. (E com números aleatórios de pior qualidade, mas provavelmente bons o suficiente para muitos casos de uso.) Isso é executado 15 ou 30 vezes mais rápido que o código do @ Nominal, a ~ 13 GB / s de saída ASCII em um Intel Haswell de 2,5 GHz CPU com AVX2. Isso ainda é menos do que a largura de banda máxima teórica da memória principal (o DDR3-1600 de canal duplo é de cerca de 25,6 GB / s), mas eu estava escrevendo no / dev / null, então na verdade é apenas reescrevendo um buffer que permanece quente no cache. O Skylake deve executar esse mesmo código significativamente mais rápido que o Haswell (veja o final desta resposta).

Supondo que você realmente gargalo na E / S para o disco ou canalizando isso em algum lugar, uma implementação rápida significa que sua CPU nem precisa ter um clock mais alto do que ocioso. Ele usa muito menos energia total para produzir o resultado. (Vida útil da bateria / aquecimento / aquecimento global.)

Isso é tão rápido que você provavelmente não deseja gravá-lo em disco. Apenas gere novamente conforme necessário (da mesma semente, se desejar os mesmos dados novamente). Mesmo se você quiser alimentá-lo com um processo multiencadeado que possa usar todas as CPUs, executar isso para canalizar os dados para ele deixará quente no cache L3 (e cache L2 no núcleo que o escreveu) e use muito pouco tempo de CPU. (Porém, observe que o encanamento acrescenta muita sobrecarga em relação à gravação /dev/null. Em um Skylake i7-6700k, o encanamento para wc -cou outro programa que apenas lê + descarta sua entrada, é cerca de 8x mais lento do que gravar/dev/null e usa apenas 70% de um CPU, mas ainda são 4,0 GB / s em uma CPU de 3,9 GHz.

Gerá-lo é mais rápido do que relê-lo, mesmo a partir de um SSD rápido conectado ao PCIe, mas o IDK é mais eficiente em termos de energia (o multiplicador de vetores inteiros fica muito ocupado e provavelmente consome muita energia, juntamente com outros AVX2 ALUs vetoriais 256b). OTOH, não sei quanto tempo de CPU lendo no disco levaria para algo que estava maximizando todos os núcleos que processavam essa entrada. Eu acho que uma alternância de contexto para gerar novamente em blocos de 128k pode ser competitiva com a execução de código do sistema de arquivos / pagecache e a alocação de páginas para ler dados do disco. Claro, se já está quente no pagecache, é basicamente um erro. OTOH, já escrevemos sobre o mais rápido que o memcpy! (que precisa dividir a largura de banda da memória principal entre leitura e gravação). Observe também que escrever na memória que 'rep movsb(memcpy e memset otimizados em microcódigo, que evitam a RFO, desde a implementação de Andy Glew no P6 (Pentium Pro )).


Até agora, isso é apenas uma prova de conceito, e o tratamento da nova linha está apenas aproximadamente correto. Está errado nas extremidades de um buffer de potência de 2. Com mais tempo de desenvolvimento. Estou confiante de que poderia encontrar uma maneira mais eficiente de inserir novas linhas também exatamente corretas, com sobrecarga pelo menos tão baixa quanto essa (em comparação com a saída de apenas espaços). Eu acho que isso é algo como 10 a 20%. Estou interessado apenas em saber o quão rápido poderíamos fazer essa execução, não em ter uma versão aprimorada, então deixarei essa parte como um exercício para o leitor, com comentários descrevendo algumas idéias.


Em um Haswell i5 em seu turbo máximo de 2,5 GHz, com RAM DDR3-1600MHz, o tempo produziu 100 GiB, mas diminuiu. (Cronometrado no cygwin64 no Win10 com o gcc5.4 -O3 -march=native, omitido -funroll-loopsporque eu estava tendo bastante dificuldade em obter execuções decentes neste laptop emprestado. Deveria ter inicializado o Linux em um USB).

escrevendo para / dev / null, a menos que seja especificado de outra forma.

  • James Hollis: (não testado)
  • Versão fwrite do nominal: ~ 2.21s
  • this (SSE2): ~ 0.142s (tempos não escalados = real = 14.232s, usuário = 13.999s, sys = 0.187s).
  • this (AVX-128): ~ 0.140s
  • this (AVX2): ~ 0.073s (sem escala: real = 0m7.291s, usuário = 0m7.125s, sys = 0m0.155s).
  • essa tubulação cygwin (AVX2) para wc -c, com tamanho de buffer de 128 kB: 0,32s com CPU a 2,38 GHz (máximo de turbo de núcleo duplo). (tempos não dimensionados: real = 32.466s usuário = 11.468s sys = 41.092s, incluindo isso e wc). Porém, apenas metade dos dados foi realmente copiada, porque meu programa bobo pressupõe que a gravação faça o buffer completo, mesmo que esse não seja o caso, e o cygwin write () faça apenas 64k por chamada em um canal.

Portanto, com o SSE2, isso é cerca de 15 vezes mais rápido que o código escalar do @Nominal Animal. Com o AVX2, é cerca de 30 vezes mais rápido. Eu não tentei uma versão do código do Nominal que apenas usa em write()vez de fwrite(), mas presumivelmente para buffers grandes, o stdio geralmente fica fora do caminho. Se estiver copiando os dados, isso representaria muita desaceleração.


Tempos para produzir 1 GB de dados em um Core2Duo E6600 (caches L2 compartilhados de 2,4 GHz, L1 privado 32kiB, L4 compartilhados com 4MiB), DDR2-533MHz no Linux 4.2 de 64 bits (Ubuntu 15.10). Ainda usando um tamanho de buffer de 128 kB para write (), ainda não exploramos essa dimensão.

escrevendo para / dev / null, a menos que seja especificado de outra forma.

  • (SSE2) isso com manipulação de nova linha e 4 vetores de dígitos de cada vetor de bytes aleatórios: 0,183s (tempo de execução de 100GiB em 18,3s, mas resultados semelhantes para execuções de 1GiB). 1,85 instruções por ciclo.
  • (SSE2), canalizando para wc -c: 0.593s (sem escala: real = 59.266s usuário = 20.148s sys = 1m6.548s, incluindo o tempo de CPU do wc). O mesmo número de chamadas do sistema write () que o cygwin, mas na verdade canaliza todos os dados porque o Linux lida com todos os 128k de write () em um pipe.
  • A fwrite()versão do NominalAnimal (gcc5.2 -O3 -march=native) é executada com ./decdig 100 $((1024*1024*1024/200)) > /dev/null: 3.19s +/- 0.1%, com 1,40 instrução por ciclo. -funroll-loops fez talvez uma pequena diferença. clang-3.8 -O3 -march=native: 3,42s +/- 0,1%
  • Canal nominal fwritepara wc -c: real = 3.980s usuário = 3.176s sys = 2.080s
  • A versão linha de cada vez de James Hollis ( clang++-3.8 -O3 -march=native): 22.885s +/- 0,07%, com 0,84 instruções por ciclo. (g ++ 5.2 foi um pouco mais lento: 22,98s). Escrever apenas uma linha de cada vez provavelmente doeu significativamente.
  • Stéphane Chazelas tr < /dev/urandom | ...: real = 41.430s usuário = 26.832s sys = 40.120s. trestava obtendo todo o núcleo da CPU para si próprio na maioria das vezes, gastando quase todo o tempo no driver do kernel, gerando bytes aleatórios e copiando-os para um pipe. O outro núcleo nessa máquina de núcleo duplo estava executando o restante do pipeline.
  • time LC_ALL=C head -c512M </dev/urandom >/dev/null: ou seja, apenas lendo tanta aleatoriedade sem tubulação: real = 35.018s usuário = 0.036s sys = 34.940s.
  • O programa perl do Phúc de Phúc (perl v5.20.2 do Ubuntu15.10)
    LANG=en_CA.UTF-8:: real = 4m32.634s usuário = 4m3.288s sys = 0m29.364.
    LC_ALL=C LANG=C: real = 4m18.637s usuário = 3m50.324s sys = 0m29.356s. Ainda muito lento.

  • (SSE2) isso sem manipulação de nova linha e 3 ou 4 vetores de dígitos de cada vetor de bytes aleatórios (quase exatamente a mesma velocidade: o dig3 = v%10passo é o ponto de equilíbrio neste HW): 0,166s (instruções de 1,82 por ciclo) . Esse é basicamente o limite mais baixo para o que podemos chegar perto com o manuseio de nova linha perfeitamente eficiente.

  • (SSE2) Versão antiga sem manipulação de nova linha, mas obtendo apenas um dígito por elemento uint16_t usando v%10, 0.222 segundos +/- 0.4%, 2.12 instruções por ciclo. (Compilado com gcc5.2 -march=native -O3 -funroll-loops,. Desenrola os loops para ajudar nesse código neste hardware. Não o use cegamente, especialmente para programas grandes).
  • (SSE2) Versão antiga disso, gravando em um arquivo (em um RAID10f2 de 3 discos rígidos magnéticos rápidos, pouco otimizados para gravações): ~ 4 segundos. Poderia ir mais rápido, ajustando as configurações do buffer de E / S do kernel para permitir muito mais dados sujos antes dos blocos write (). O tempo do "Sistema" ainda é ~ 1,0 segundos, muito maior que o tempo do "usuário". Nesse sistema antigo, com RAM DDR2-533 lenta, leva cerca de 4x mais tempo para o kernel memorizar os dados no pagecache e executar as funções XFS do que para o meu loop reescrevê-lo no local em um buffer que permanece quente em cache.

Como isso é feito

Um PRNG rápido é obviamente essencial. O xorshift128 + pode ser vetorizado, para que você tenha dois ou quatro geradores de 64 bits em paralelo, em elementos de um vetor SIMD. Cada etapa produz um vetor completo de bytes aleatórios. ( Implementação de 256b AVX2 aqui com intrínsecas da Intel ). Optei pela escolha nominal de xorshift * da Nominal, porque a multiplicação de inteiros vetoriais de 64 bits é possível no SSE2 / AVX2 com técnicas de precisão estendida .


Dado um vetor de bytes aleatórios, podemos dividir cada elemento de 16 bits em vários dígitos decimais. Produzimos vários vetores de elementos de 16 bits, cada um com um dígito ASCII + espaço ASCII . Armazenamos isso diretamente em nosso buffer de saída.

Minha versão original costumava x / 6554obter um dígito aleatório de cada elemento uint16_t de um vetor. É sempre entre 0 e 9, inclusive. É tendencioso 9, porque (2^16 -1 ) / 6554é apenas 9.99923. (6554 = ceil ((2 ^ 16-1) / 10), que garante que o quociente seja sempre <10.)

x/6554pode ser calculado com uma multiplicação por uma constante "mágica" ( o ponto fixo recíproco ) e um deslocamento à direita do resultado da metade alta. Este é o melhor caso de divisão por uma constante; alguns divisores realizam mais operações e a divisão assinada exige trabalho extra. x % 10tem um viés semelhante e não é tão barato de calcular. (a saída asm do gcc é equivalente a x - 10*(x/10), ou seja, uma multiplicação e subtração extras no topo da divisão usando um inverso multiplicativo modular.) Além disso, o bit mais baixo do xorshift128 + não é de alta qualidade , portanto é melhor dividir para obter entropia de bits altos ( qualidade e velocidade) do que o módulo para obter entropia de bits baixos.

No entanto, podemos usar mais da entropia em cada uint16_t observando os dígitos decimais baixos, como a digit()função @ Nominal . Para obter o desempenho máximo, decidi x/6554usar os 3 dígitos decimais baixos e , para salvar um PMULLW e PSUBW (e provavelmente algum MOVDQA) versus a opção de qualidade mais alta, usar os 4 dígitos decimais baixos. x / 6554 é levemente afetado pelos três dígitos decimais baixos, portanto, existe alguma correlação entre os dígitos do mesmo elemento (separação de 8 ou 16 dígitos na saída ASCII, dependendo da largura do vetor).

Eu acho que o gcc está dividindo por 100 e 1000, em vez de uma cadeia mais longa que sucessivamente se divide por 10, portanto, provavelmente não está diminuindo significativamente o comprimento da cadeia de dependência não transportada por loop que produz 4 resultados de cada saída PRNG. port0 (multiplicação e deslocamento de vetores) é o gargalo por causa dos inversos multiplicativos modulares e as mudanças no xorshift +, portanto é definitivamente útil salvar uma multiplicação de vetores.

O xorshift + é tão rápido que mesmo usando apenas ~ 3,3 bits de aleatoriedade a cada 16 (ou seja, 20% de eficiência) não é muito mais lento do que dividi-lo em vários dígitos decimais. Apenas aproximamos a distribuição uniforme, porque essa resposta é focada na velocidade, desde que a qualidade não seja muito ruim.

Qualquer tipo de comportamento condicional que mantenha um número variável de elementos exigiria muito mais trabalho. (Mas talvez ainda possa ser feito de maneira eficiente usando as técnicas de empacotamento à esquerda do SIMD . No entanto, isso fica menos eficiente para tamanhos de elementos pequenos; as tabelas de pesquisa de máscara aleatória gigantes não são viáveis ​​e não há embaralhamento de faixa de AVX2 com menos de 32 Uma versão PSHUFB de 128b ainda pode gerar uma máscara em tempo real com o BMI2 PEXT / PDEP, como você pode no AVX2 com elementos maiores , mas é complicado porque um número inteiro de 64 bits contém apenas 8 bytes. nessa resposta tem algum código que pode funcionar para contagens mais altas de elementos.)


Se a latência do RNG for um gargalo, poderíamos ir ainda mais rápido executando dois vetores de geradores em paralelo, alternando qual deles usamos. O compilador ainda pode facilmente manter tudo em registros em um loop desenrolado, e isso permite que as duas cadeias de dependência sejam executadas em paralelo.

Na versão atual, detalhando a saída do PRNG, na verdade, gargalos na taxa de transferência da porta 0, não na latência do PRNG, portanto, não há necessidade disso.


O código: versão AVX2

Versão completa com mais comentários sobre o Godbolt compiler explorer .

Não é muito arrumado, desculpe, eu tenho que dormir e quero postar isso.

Para obter a versão SSE2, s/_mm256/_mm, s/256/128/, s/v16u/v8u/, e mudança vector_size(32)para 16. Também alterar o incremento de nova linha de 4 * 16-4 * 8. (Como eu disse, o código é confuso e não está bem configurado para compilar duas versões. Não planejava originalmente fazer uma versão AVX2, mas eu realmente queria testar em uma CPU Haswell a que tinha acesso.)

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

}

Compile com gcc, clang ou ICC (ou, esperançosamente, qualquer outro compilador que entenda o dialeto GNU C de C99 e as intrínsecas da Intel). As extensões vetoriais GNU C são altamente convenientes para que o compilador gere os números mágicos para divisão / módulo usando inversos multiplicativos modulares, e __attribute__s ocasionais são úteis.

Isso pode ser escrito de forma portável, mas seria necessário mais código.


Notas de desempenho:

A loja sobreposta para inserir novas linhas possui uma sobrecarga significativa para decidir onde colocá-la (previsões incorretas de ramificação e gargalos de front-end no Core2), mas a própria loja não tem impacto no desempenho. Comentar apenas as instruções de armazenamento no asm do compilador (deixando todas as ramificações iguais) deixou o desempenho no Core2 completamente inalterado, com execuções repetidas dando o mesmo tempo a +/- menos de 1%. Portanto, concluo que o buffer / cache da loja lida com isso muito bem.

Ainda assim, usar algum tipo de janela rotativa ascii_digitspacecom um elemento com uma nova linha pode ser ainda mais rápido, se desenrolarmos o suficiente para que qualquer contador / ramificação desapareça.


Gravar em / dev / null é basicamente não operacional, portanto o buffer provavelmente permanece quente no cache L2 (256 kB por núcleo em Haswell). A aceleração perfeita de vetores 128b para 256b é esperada: não há instruções extras e tudo (incluindo as lojas) acontece com o dobro da largura. Porém, a ramificação de inserção de nova linha é obtida duas vezes mais. Infelizmente, não tive tempo na minha configuração de cywell do Haswell com essa parte #ifdefeditada.

2.5GHz * 32B / 13.7GB / s = 5.84 ciclos por loja AVX2 em Haswell. Isso é muito bom, mas poderia ser mais rápido. Talvez haja alguma sobrecarga nas chamadas do sistema cygwin do que eu pensava. Não tentei comentar isso na saída asm do compilador (o que garantiria que nada fosse otimizado).

O cache L1 pode sustentar um armazenamento de 32B por relógio, e o L2 não possui uma largura de banda muito menor (latência mais alta).

Quando examinei a IACA algumas versões atrás (sem a ramificação de novas linhas, mas apenas obtendo um vetor ASCII por vetor RNG), estava prevendo algo como um armazenamento de vetor 32B por 4 ou 5 relógios.

Eu esperava obter mais agilidade ao extrair mais dados de cada resultado RNG, com base em olhar para mim, considerando os guias de Agner Fog e outros recursos de otimização aos quais adicionei links no wiki de tags do SO x86 .)

Provavelmente seria significativamente mais rápido no Skylake , onde o número inteiro de vetores se multiplica e o deslocamento pode ser executado em duas vezes mais portas (p0 / p1) em comparação com Haswell (apenas p0). O xorshift e a extração de dígitos usam muitos turnos e multiplicam. ( Atualização: o Skylake o executa em 3,02 IPC, fornecendo-nos 3,77 ciclos por loja AVX2 de 32 bytes , com tempo de 0,030s por iteração de 1 GB, gravando /dev/nullno Linux 4.15 no i7-6700k a 3.9GHz.


Não requer o modo de 64 bits para funcionar bem . A versão SSE2 é tão rápida quando compilada -m32, porque não precisa de muitos registros vetoriais, e toda a matemática de 64 bits é feita em vetores, não em registros de uso geral.

Na verdade, é um pouco mais rápido no modo de 32 bits no Core2, porque a macro-fusão de comparação / ramificação só funciona no modo de 32 bits, portanto há menos uops para o núcleo fora de ordem (18,3s (1,85 instruções por relógio) vs 16,9 s (2,0 IPC)). O tamanho do código menor, por não ter prefixos REX, também ajuda os decodificadores do Core2.

Além disso, alguns movimentos do vetor reg-reg são substituídos por cargas, já que nem todas as constantes se fixam mais no vetor regs. Como a taxa de transferência de carga do cache L1 não é um gargalo, isso realmente ajuda. (por exemplo, multiplicando por um vetor constante de set1(10): movdqa xmm0, xmm10/ pmullw xmm0, xmm1transforma-se em movdqa xmm0, [constant]/ pmullw xmm0, xmm1.) Como o MOVDQA reg-reg requer uma porta ALU, ele compete com o trabalho real que está sendo feito, mas uma carga MOVDQA compete apenas pela largura de banda da decodificação do front-end. (Ter um endereço de 4 bytes em muitas instruções cancela muito do ganho ao salvar os prefixos REX.

Eu não ficaria surpreso se salvar ALU MOVDQA for de onde vêm os ganhos reais, já que o front-end deve acompanhar muito bem a média de 2,0 IPC.

Todas essas diferenças desaparecem em Haswell, onde tudo deve ser executado a partir do cache decodificado, se não o buffer de loopback. A macro fusão de ramo ALU + funciona nos dois modos desde Nehalem.

Peter Cordes
fonte
6
Eu simplesmente amo como você entrou no "modo animal" no assunto! :) Mais importante, é um excelente exemplo de que tipo de ganho está disponível, se você realmente precisa ou deseja obter o máximo desempenho, utilizando um conhecimento de nível muito baixo do hardware disponível. Além disso, estamos usando apenas um thread aqui; Os processadores Intel / AMD para desktop e servidor mais atuais (e até os ARM em tablets e SBCs leves) têm vários núcleos; portanto, ainda existem mais acelerações disponíveis no mundo real. E, finalmente, quão impraticável é a "maneira mais rápida de" fazer perguntas, devido ao grande esforço envolvido.
Animal Nominal
11
@NominalAnimal: Sim, até mesmo um lento quad ARM ou octo core poderia saturar facilmente a largura de banda da memória principal fazendo o mesmo com o NEON (mesmo se eles estivessem conectados ao DDR3 de canal duplo rápido), se tiver 64 bits de adição e troca SIMD inteiros . Suponho que o NEON tenha multiplicações de tamanho de elemento de 16 bits para o trabalho de áudio. O agendamento de instruções seria muito mais trabalhoso para um ARM em ordem, porque cada iteração da cadeia de dependência transportada por loop (o xorshift128 +) alimenta algumas cadeias de dependência independentes de cortar isso e armazená-lo na memória ...
Peter Cordes
... A execução fora de ordem consome isso no café da manhã, porque a coisa toda é curta o suficiente para que várias iterações se encaixem no ROB (192 uops no HSW IIRC). (ou seja, a "janela" de instruções que a execução fora de ordem vê inclui várias iterações). Portanto, a CPU pode concluir o armazenamento final por 2 ou 3 iterações atrás, enquanto também inicia o início da iteração atual. Isso oculta a latência das cadeias independentes, portanto, apenas a taxa de transferência é importante. Em um núcleo em ordem, isso exigiria pipelining software ...
Peter Cordes
... Um bom compilador ARM deve fazer isso por você se você o escrever com intrínsecas (ou sintaxe do vetor nativo GNU C para a coisa toda, como eu deveria ter feito em primeiro lugar). Eu não tenho nenhuma experiência em fazer isso de verdade, então você pode precisar massagear seu loop e talvez fazer um desenrolamento manual / pipelining de software na fonte para obter um bom desempenho. (Existem alguns núcleos ARM fora de ordem, encontrados em telefones de última geração, mas eles não têm uma janela fora de ordem tão grande quanto a Haswell. OTOH, eles também têm uma taxa de transferência de pico menor, portanto ganhar com a descoberta de mais ILP).
Peter Cordes
11
@NominalAnimal: também concordou com a bobagem da pergunta. "O mais rápido", sem restrições à qualidade da aleatoriedade, é bobo ... Com o BTRFS, os mesmos dados no disco podem fazer parte de um arquivo várias vezes (consulte EXTENT_SAME na 4.2 ). Assim, você pode gerar um 4kiB ou 1 MB aleatório e repeti-lo. É aleatoriedade com um curto período, mas ainda é aleatória e custa apenas E / S de metadados. (Na verdade, você precisa do bloco para acabar com uma nova linha lcm (4096, 4096 * 200) = 4096 * 200 = 819200 = 800kiB, para que o seu bloco de repetição é qualquer múltiplo de que..)
Peter Cordes
14

Aqui está uma solução que espero que seja simples de entender:

od -An -x /dev/urandom | tr -dc 0-9 | fold -w100 | awk NF=NF FS= | head -c1G
  • odcria um fluxo uniforme de dígitos hexadecimais de /dev/random.
  • trse livrar das letras, mantendo apenas 0-9dígitos
  • fold garante que haja 100 dígitos por linha
  • awk insere espaços dentro de linhas
  • head trunca a entrada para 1 gigabyte
sam hocevar
fonte
2
Essa é uma boa maneira alternativa de produzir mais de um dígito por byte de / dev / random enquanto ainda possui uma distribuição uniforme, que produz 320 dígitos para cada 256 bytes de / dev / urandom em média (menos do que quando você converte bytes <200 módulo 100 ao decimal, que fornece 400 dígitos para cada 256 bytes).
Stéphane Chazelas
6

Você pode usar o jotcomando para isso:

jot -r 50000000 0 9 | fmt -w 200 > output.txt
Gardenhead
fonte
11
@DigitalTrauma Minha versão do fmtnão tem uma opção de largura da meta. De qualquer forma, será exato porque todos os dígitos ocupam exatamente uma coluna!
gardenhead
Para o registro, minha fmtversão é fmt (GNU coreutils) 8.25(Ubuntu 16.04)
Digital Trauma
2
o número certo para meio gb é: 1024 * 1024 * 1024/2 =536870912
Olivier Dulac
11
@OlivierDulac Depende de qual "gigabyte" você está falando. Algumas pessoas usam 1 Gb para significar 10 ^ 9 em vez de 2 ^ 30, mesmo que seja tecnicamente incorreto. Além disso, eu como números redondos agradáveis :)
gardenhead
6
@ Gardard, cada vez mais pessoas tendem a migrar para Gigabyte == 1e9 e Gibibyte == 2 ^ 30, pois essa é a definição padrão da IEC. Veja Wikipedia . Observe que o próprio Gb preferiria ser Giga- bit .
Stéphane Chazelas
6

Isso é semelhante ao método de Stéphane Chazelas, no entanto, li 64 bits de uma só vez para melhorar o desempenho. A distribuição ainda é uniforme, mas agora você recebe 19 dígitos para cada 8 bytes, em vez de apenas 8 no melhor dos casos, como antes

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

Na plataforma de 32 bits, 9 dígitos serão lidos a cada vez, em vez de 19.

phuclv
fonte
Isso pode gerar uma exceção se o seu sistema não suportar números inteiros de 64 bits ou perlnão for compilado com suporte para quad.
amigos estão dizendo sobre cuonglm
@cuonglm sim como eu disse, se perl não é 64 bits em que o sistema, em seguida, o programa deve ser alterado para next if $n >= 1000000000; $s = sprintf("%09u", $n);obter apenas 9 dígitos
phuclv
Você não pode, o programa falhará $n = unpack("Q")se o quad não for suportado.
amigos estão dizendo sobre cuonglm
11
@cuonglm mudar para BEGIN{$/=\4; $,=" "} $n = unpack("L");também #
phuclv
11
Desculpe, mas isso recebe 19 dígitos da entrada de 8 bytes apenas em 54,2% do tempo e nenhum o restante, com média de 1,29 dígitos por byte de entrada. Se mais do que Stephane você usa <16e18e divide por 16, obtém 18 dígitos 86,7% para 1,95 dpB. Com 32 bits, <4e9 /4obtém 9 dígitos 93,1% para 2,10 dpB. Mas 5 bytes (como hexadecimal (H10)) <1e12fornecem 12 dígitos 90,9% para 2,18 dpB, ou dividem o hexadecimal ao meio e, a cada metade, <1e6 fornecem 6 dígitos 95,4% para 2,29 dpB; isso se aproxima do limite de log_10 (256) = 2,41.
David_thompson_085
3

Eu meio que concordo com o Nominal Animal no uso de uma linguagem de programação compilada, se você precisar de velocidade. No entanto, você não precisa escrever seu próprio código RNG em C. O C ++ 11 oferece o excelente Mersenne Twister como parte de sua biblioteca padrão.

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

O código acima é razoavelmente simples e leva cerca de um minuto quando canalizo a saída para um arquivo. Podemos ir muito mais rápido criando uma string grande o suficiente para 100 dígitos e invadindo-a. Isso nos permite chamar cout todas as linhas e não todos os dígitos.

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

Esse código leva minha máquina por cerca de seis segundos. Lembre-se de que é uma saída padrão, então coloque-a em um arquivo.

Eu tenho algumas isenções de responsabilidade. Primeiro, estou escrevendo isso em um PC com Windows. Eu acho que as bibliotecas estão todas presentes no Linux, mas se eu estiver errado, não deixe de apontar.

Além disso, ele realmente gera exatamente meio bilhão de dígitos separados por espaço, o que é tecnicamente um gigabyte, mas talvez não seja exatamente o que você queria. Ele produz 5 milhões de linhas, 100 dígitos por linha. Se a diferença for importante, você pode aumentar o número de linhas. Na minha caixa do Windows, o arquivo parece ser um pouco maior que 10 ^ 9 bytes, o que eu acho que tem algo a ver com caracteres extras de nova linha.

James Hollis
fonte
2
Ei, as críticas não são realmente justas! :) A maior parte do meu programa é análise de parâmetros de linha de comando. Se eu também omitir comentários, verificações de erro e codificar o número de colunas e linhas de saída, posso torná-lo menos que o dobro do tamanho do seu código - dificilmente monstruoso . :) Brincadeiras à parte: Sim, as bibliotecas estão disponíveis na maioria das distribuições Linux. No meu laptop, sua linha por vez leva cerca de 14 segundos, enquanto minha versão por linha leva apenas 1,3 segundos. A diferença é apenas devido ao PRNG: Mersenne Twister é muito mais lento que o Xorshift64 *.
Animal Nominal
11
Há uma coisa prática que eu gostaria de salientar que você perdeu, mas espero que você não tome isso como negatividade, apenas algo para pensar: Como mencionei na minha resposta, os programas únicos raramente valem a pena. tempo que eles levaram para escrever. É por isso que a adição da análise de linha de comando e o texto de uso da ajuda quase sempre valem a pena. Eu tenho um grande conjunto desses programas utilitários e, em vez de procurar suas fontes para descobrir o que cada um deles faz, eu apenas os executo, para que eles me digam; e posso modificar o comportamento deles o suficiente para atender a mais de uma necessidade. Amortizando o custo de desenvolvimento.
Animal Nominal
@NominalAnimal outra coisa importante é que você canalizada a saída para /dev/nullo que seria muito mais rápido do que escrever para um arquivo real
phuclv
@ LưuVĩnhPhúc: Bem, na verdade não. Esta lappy possui um SSD Samsung de 128 GB, com ~ 500 MB / s de leituras e gravações seqüenciais. Coloque quatro em uma configuração de software RAID0 do Linux, e você terá mais de um gigabyte por segundo de leitura e gravação ao gerar conjuntos de dados tão grandes (estimamos ~ 1,75 TB / s). 1 GB / s foi alcançado anos atrás com 12 unidades SATA (discos giratórios, nem mesmo SSDs) com Linux sw-RAID0. (Nota: bytes / s, não bits / s.) Certamente, parece bobagem para uma máquina "normal", mas aqueles que brincam com grandes conjuntos de dados acham que vale a pena - você economiza tempo em tudo o que faz (com grandes conjuntos de dados) dessa maneira.
Animal Nominal
11
@NominalAnimal e Lu'u: Mais importante, se você tiver RAM suficiente, o programa poderá sair bem antes que todos os dados estejam no disco. A maior parte do trabalho em uma write()chamada de sistema grande é um memcpy no pagecache, que bloqueia apenas se o kernel decidir fazer isso em vez de alocar mais espaço no buffer. Este programa deve afunilar apenas a E / S do disco quando a memória estiver fraca ou se você tiver usado o O_DIRECT para ignorar o pagecache. Se você estiver write()em pedaços menores que o tamanho do cache, esperamos que seus dados entrem na memória principal apenas uma vez e o buffer reescrito no local permaneça quente no cache L2 ou L3.
22416 Peter Cordes
1

Depende da sua definição de "aleatório". Se você quer dizer criptograficamente aleatório, basta obter uma boa biblioteca e morder a bala, aguarde a execução.

Se você só precisa de algo que pareça aleatório, eis uma maneira fácil:

  1. Obtenha um arquivo com vários GB de comprimento. Seu filme favorito será bom.
  2. Gzip, uma maneira fácil de extrair padrões repetidos
  3. Percorra o arquivo um nybble (meio byte) de cada vez. Cada valor estará entre 0 e 15. Jogue fora menos que 1 ou maior que 10. Subtraia 1 de cada um dos primeiros bilhões de sobreviventes e escreva-o como um dígito.

Pode levar uma hora para rodar em uma máquina lenta; rápido o suficiente e aleatório o suficiente para a maioria dos propósitos.

Malvolio
fonte
9
/dev/urandomprovavelmente será melhor do que gzip, tanto em velocidade quanto em aleatoriedade.
amigos estão dizendo sobre
Get a file that is several Gb longvocê precisará de um arquivo ** de pelo menos 8 GB "para obter um arquivo de 1 GB
phuclv 14/04
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
fonte
11
Bem vindo ao site! Veja os links na minha página de perfil. Há muitos problemas aqui que vejo quase universalmente em scripts de shell, mas isso não os torna corretos.
Curinga
2
@Wildcard: nunca cat file | trquando você pode apenas tr <file. IIRC, você pode até <file tr. Eu pensei que você estava falando sobre esse script shell parecendo desajeitado e lento, como du | awkdepois de cada linha para verificar o tamanho e reabrindo o arquivo para acrescentar todas as linhas em vez de redirecionar para fora do loop.
Peter Cordes
2
@PeterCordes, sim. Por que o uso de um loop de shell para processar o texto é considerado uma má prática? é particularmente relevante - esse script é baseado na ideia de que o Bash é uma linguagem de programação como C, o que não é. Mas, \ @NamNT, espero que você permaneça neste site porque é claro que você tem uma mente muito lógica. :)
Caractere curinga
4
O @PeterCordes cat /dev/urandom | busy-cmdé um daqueles casos raros em que pode fazer sentido, pois pode dividir a geração aleatória e o cmd ocupado entre os processadores. Não é muito para tr, mas faz a diferença para o Sam, odpor exemplo.
Stéphane Chazelas
11
@ StéphaneChazelas: oh certo !! Sim, a chamada do sistema read () é onde o tempo da CPU RNG é gasto.
Peter Cordes