Apa cara tercepat untuk menghasilkan file teks 1 GB yang berisi angka acak?

Saya mencoba skrip bash, tetapi butuh waktu terlalu lama untuk membuat file 1 MB sederhana. Saya pikir jawabannya terletak pada menggunakan /dev/randomatau /dev/urandom, tetapi posting lain di sini hanya menunjukkan bagaimana cara menambahkan semua jenis data ke file menggunakan hal-hal ini, tetapi saya ingin menambahkan hanya angka.

Jadi, adakah perintah yang bisa saya gunakan untuk membuat file acak berukuran 1 GB yang hanya berisi angka antara 0 dan 9?

Sunting: Saya ingin hasilnya seperti ini

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

Kisarannya adalah 0 - 9 yang berarti hanya angka 0, 1, 2, 3, 4, 5, 6, 7, 8 dan 9. Juga saya membutuhkannya untuk dipisahkan dengan ruang dan 100 per baris, hingga njumlah baris. Ini adalah sesuatu yang saya tidak peduli, saya ingin ukuran akhir saya menjadi 1 GB.

Sunting: Saya menggunakan Ubuntu 16.04 LTS

Ini sebagian merupakan jawaban yang tidak jelas, karena judul pertanyaannya.

Ketika Anda mencari "cara tercepat untuk ..." , jawabannya hampir selalu merupakan alat khusus. "Jawaban" ini menunjukkan satu alat seperti itu, supaya Anda bisa bereksperimen.

Ini bukan jawaban yang serius, karena Anda tidak harus melihat ke dalam alat khusus untuk pekerjaan yang hanya Anda lakukan sekali, atau sangat jarang. Anda lihat, Anda akan menghabiskan lebih banyak waktu mencari alat dan belajar tentang itu, daripada benar-benar melakukan hal-hal. Kerang dan utilitas menyukai bashdan awkbukan yang tercepat, tetapi Anda biasanya dapat menulis satu baris untuk mencapai pekerjaan itu, menghabiskan hanya beberapa detik. Bahasa scripting yang lebih baik seperti perljuga dapat digunakan, meskipun kurva belajar untuk perlcuram, dan saya ragu untuk merekomendasikannya untuk tujuan seperti itu, karena saya telah trauma dengan proyek perl yang mengerikan. pythondi sisi lain sedikit cacat oleh I / O yang agak lambat; namun ini hanya masalah saat Anda memfilter atau menghasilkan gigabytes data.

Bagaimanapun, program contoh C89 berikut (yang menggunakan POSIX.1 hanya untuk jam akurasi yang lebih tinggi jika tersedia) harus mencapai sekitar 100 MB / s tingkat generasi (diuji di Linux pada laptop dengan prosesor Intel i5-4200U, menyalurkan output to /dev/null), menggunakan generator nomor pseudo-acak yang cukup bagus. (Keluaran harus lulus semua tes BigCrunch, kecuali tes MatrixRank, karena kode menggunakan xorshift64 * dan metode pengecualian untuk menghindari bias angka.)

desimal-digit.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;
}

Kita dapat membuatnya jauh lebih cepat, jika kita beralih ke buffer garis, dan fwrite()itu sekaligus bukannya menghasilkan setiap digit sekaligus. Perhatikan bahwa kami tetap menjaga aliran buffer sepenuhnya, untuk menghindari penulisan sebagian (non-power-of-two) jika output adalah perangkat blok.

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

Catatan: kedua contoh diedit pada 2016-11-18 untuk memastikan distribusi angka yang seragam (nol dikecualikan; lihat misalnya di sini untuk perbandingan dan detail tentang berbagai generator angka pseudo-acak).

Kompilasi menggunakan misalnya

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

dan secara opsional menginstal seluruh sistem untuk /usr/binmenggunakan

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

Dibutuhkan jumlah digit per baris, dan jumlah baris. Karena 1000000000 / 100 / 2 = 5000000(lima juta; total byte dibagi dengan kolom dibagi 2), Anda dapat menggunakan

./decimal-digits 100 5000000 > digits.txt

untuk menghasilkan ukuran gigabyte digits.txtseperti yang diinginkan oleh OP.

Perhatikan bahwa program itu sendiri ditulis lebih dengan keterbacaan daripada efisiensi dalam pikiran. Maksud saya di sini adalah bukan untuk menunjukkan efisiensi kode - saya akan menggunakan POSIX.1 dan I / O tingkat rendah, daripada antarmuka C generik - tetapi agar Anda dengan mudah melihat keseimbangan seperti apa yang ada dengan upaya yang dihabiskan dalam mengembangkan alat khusus dibandingkan kinerjanya, dibandingkan dengan skrip satu shell atau pendek atau awk.

Menggunakan perpustakaan C GNU, memanggil fputc()fungsi untuk setiap output karakter menimbulkan overhead yang sangat kecil (dari panggilan fungsi tidak langsung, atau kondisional - FILEantarmuka sebenarnya cukup kompleks dan fleksibel, Anda lihat). Pada laptop Intel Core i5-4200U khusus ini, mengalihkan output ke /dev/null, versi (fputc) pertama membutuhkan waktu sekitar 11 detik, sedangkan versi line-at-a-time hanya membutuhkan waktu 1,3 detik.

Kebetulan saya sering menulis program dan generator seperti itu hanya karena saya suka bermain dengan dataset besar. Aku aneh seperti itu. Sebagai contoh, saya pernah menulis sebuah program untuk mencetak semua nilai floating-point IEEE-754 positif yang terbatas ke dalam file teks, dengan presisi yang cukup untuk menghasilkan nilai yang sama persis ketika diuraikan. File tersebut berukuran beberapa gigabytes (mungkin 4G atau lebih); tidak ada banyak positif positif yang terbatas floatseperti yang diperkirakan orang. Saya menggunakan ini untuk membandingkan implementasi yang membaca dan mengurai data tersebut.

Untuk kasus penggunaan normal, seperti yang dimiliki OP, skrip shell dan skrip dan satu-garis adalah pendekatan yang lebih baik. Lebih sedikit waktu yang dihabiskan untuk menyelesaikan tugas keseluruhan. (Kecuali jika mereka memerlukan file yang berbeda setiap hari atau lebih, atau ada banyak orang yang membutuhkan file yang berbeda, di mana - kasus yang jarang terjadi, alat khusus seperti di atas, dapat menjamin upaya yang dihabiskan.)

Ini:

 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

(dengan asumsi headimplementasi yang mendukung -c) tampaknya cukup cepat di sistem saya.

trmenerjemahkan seluruh rentang byte (0 hingga 255, 0 hingga 0377 dalam oktal): 25 byte pertama sebagai 0, 25 byte berikutnya sebagai 1 ... kemudian 25 9 sisanya (250 hingga 255) menjadi "x" yang kemudian buang (dengan tr -d x) seperti yang kita inginkan distribusi seragam (dengan asumsi /dev/urandommemiliki distribusi seragam itu sendiri) dan jadi tidak memberikan bias pada beberapa digit.

Itu menghasilkan satu digit untuk 97% dari byte /dev/urandom. fold -w 1menjadikannya satu digit per baris. paste -sdisebut dengan daftar pemisah yang terdiri dari 99 karakter spasi dan satu karakter baris baru, sehingga memiliki 100 digit spasi yang terpisah pada setiap baris.

head -c1Gakan mendapatkan GiB pertama (2 ³⁰ ) dari itu. Perhatikan bahwa baris terakhir akan terpotong dan tidak direvisi. Anda dapat memotong ke 2 ³⁰ -1 dan menambahkan baris baru yang hilang dengan tangan, atau memotong ke 10 ⁹ byte sebagai gantinya yang merupakan 50 juta dari 200 byte baris ( head -n 50000000juga akan membuatnya menjadi perintah standar / portable).

Pengaturan waktu ini (diperoleh zshpada sistem quad-core), memberikan indikasi di mana waktu CPU dihabiskan:

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

Yang pertama tradalah leher botol, sebagian besar waktu dihabiskan di kernel (saya kira untuk generasi nomor acak). Waktunya kira-kira sejalan dengan tingkat saya bisa mendapatkan byte dari /dev/uramdom(sekitar 19MiB / s dan di sini kami menghasilkan 2 byte untuk setiap 0,97 byte / dev / urandom pada tingkat 32MiB / s). foldtampaknya menghabiskan jumlah waktu CPU (15-an) yang tidak masuk akal hanya untuk memasukkan karakter baris baru setelah setiap byte tetapi itu tidak mempengaruhi waktu keseluruhan karena bekerja pada CPU yang berbeda dalam kasus saya (menambahkan -bopsi membuatnya sangat sedikit lebih banyak efisien, dd cbs=1 conv=unblocksepertinya alternatif yang lebih baik).

Anda dapat menghapus head -c1Gdan mencukur beberapa detik dengan menetapkan batas ukuran file ( limit filesize 1024mdengan zshatau ulimit -f "$((1024*1024))"dengan sebagian besar shell lainnya (termasuk zsh)) sebagai gantinya dalam subkulit.

Itu dapat ditingkatkan jika kita mengekstrak 2 digit untuk setiap byte, tetapi kita akan membutuhkan pendekatan yang berbeda untuk itu. Di atas sangat efisien karena trhanya mencari setiap byte dalam array 256 byte. Itu tidak dapat melakukan itu untuk 2 byte pada satu waktu, dan menggunakan hal-hal seperti hexdump -e '1/1 "%02u"'itu menghitung representasi teks dari byte menggunakan algoritma yang lebih kompleks akan lebih mahal daripada generasi nomor acak itu sendiri. Namun, jika seperti dalam kasus saya, Anda memiliki inti CPU yang memiliki waktu luang, mungkin masih dapat dimatikan beberapa detik:

Dengan:

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

Saya mendapatkan (perhatikan bahwa di sini 1.000.000.000 byte dibandingkan dengan 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

Lebih banyak waktu CPU secara keseluruhan, tetapi lebih baik didistribusikan di antara 4 core CPU saya, sehingga akhirnya memakan waktu lebih sedikit di dinding. Hambatannya sekarang hexdump.

Jika kita menggunakan ddalih-alih berbasis garis fold, kita sebenarnya dapat mengurangi jumlah pekerjaan yang hexdumpperlu dilakukan dan meningkatkan keseimbangan kerja antara CPU:

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

(di sini mengasumsikan GNU dduntuk iflag=fullblockdan status=none) yang memberi:

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

Kembali ke generasi nomor acak menjadi hambatan.

Sekarang, seperti yang ditunjukkan oleh @OleTange, jika Anda memiliki opensslutilitas, Anda bisa menggunakannya untuk mendapatkan yang lebih cepat (terutama pada prosesor yang memiliki instruksi AES) generator byte acak-acak.

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

pada sistem saya menghabiskan 15 kali lebih banyak byte per detik daripada /dev/urandom. (Saya tidak bisa mengomentari bagaimana perbandingannya dalam hal sumber acak yang aman secara kriptografis jika itu berlaku untuk use case Anda).

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

Sekarang berikan:

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

kembali hexdumpmenjadi hambatan.

Karena saya masih memiliki CPU yang tersisa, saya dapat menjalankan 3 dari mereka hexdumpsecara paralel.

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

( <&3diperlukan untuk shell selain dari zshitu perintah dekat 'stdin on / dev / null saat dijalankan di latar belakang).

Sekarang turun menjadi 6,2 detik dan CPU saya hampir sepenuhnya digunakan.

Jika Anda memiliki shuf(coreutils GNU terbaru tidak) Anda dapat melakukan ini:

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

Pada VM saya, ini sekarang sedikit lebih lambat daripada jawaban Stéphane sekitar 3: 4 faktor.

Jika Anda tidak memerlukan keacakan kualitas sangat tinggi, dan distribusi hampir seragam cukup baik, Anda dapat berjalan sangat cepat, terutama pada CPU modern dengan vektor integer SIMD efisien seperti x86 dengan SSE2 atau AVX2.

Ini seperti jawaban @ NominalAnimal karena kami berdua memiliki ide yang sama, tetapi secara manual di-vektor-kan untuk x86. (Dan dengan angka acak kualitas yang lebih buruk, tetapi mungkin masih cukup baik untuk banyak kasus penggunaan). Ini berjalan sekitar 15 atau 30 kali lebih cepat dari kode @ Nominal, pada ~ 13GB / s output ASCII pada 2.5GHz Intel Haswell CPU dengan AVX2. Itu masih kurang dari bandwidth maksimum memori teoretis max (dual channel DDR3-1600 adalah sekitar 25.6GB / s), tapi saya sedang menulis waktu untuk / dev / null jadi itu sebenarnya hanya menulis ulang buffer yang tetap panas di cache. Skylake harus menjalankan kode yang sama ini secara signifikan lebih cepat daripada Haswell (lihat bagian bawah jawaban ini).

Dengan asumsi Anda benar-benar bottleneck pada I / O ke disk atau pipa ini di suatu tempat, implementasi yang cepat berarti CPU Anda bahkan tidak perlu clock lebih tinggi daripada idle. Ia menggunakan energi total yang jauh lebih sedikit untuk menghasilkan hasilnya. (Usia baterai / panas / pemanasan global.)

Ini sangat cepat sehingga Anda mungkin tidak ingin menulisnya ke disk. Cukup hasilkan kembali sesuai kebutuhan (dari seed yang sama jika Anda menginginkan data yang sama lagi). Bahkan jika Anda ingin memasukkannya ke proses multi-utas yang dapat menggunakan semua CPU, menjalankan ini untuk menyalurkan data ke sana akan membuatnya panas di L3 cache (dan L2 cache pada inti yang menulisnya), dan gunakan sangat waktu CPU sedikit. (Tetapi perhatikan bahwa perpipaan menambahkan banyak overhead vs tulisan /dev/null. Pada Skylake i7-6700k, perpipaan ke wc -catau program lain yang hanya membaca + membuang inputnya, ini sekitar 8x lebih lambat daripada menulis/dev/null , dan hanya menggunakan 70% dari CPU, tetapi itu masih 4,0GB / s pada CPU 3,9GHz.

Menghasilkannya kembali lebih cepat daripada membacanya kembali bahkan dari SSD yang terhubung PCIe cepat, tetapi IDK jika lebih hemat daya (pengganda integer vektor tetap sangat sibuk, dan mungkin sangat haus daya, bersama dengan AVX2 lainnya 256b vektor ALU). OTOH, saya tidak tahu berapa banyak waktu CPU membaca dari disk akan mengambil dari sesuatu yang memaksimalkan semua core yang memproses input ini. Saya kira bahwa konteks-switch untuk menghasilkan kembali dalam potongan 128k mungkin kompetitif dengan menjalankan filesystem / kode pagecache dan mengalokasikan halaman untuk membaca data dari disk. Tentu saja, jika sudah panas di pagecache, itu pada dasarnya memcpy. OTOH, kami sudah menulis secepat memcpy! (yang harus membagi bandwidth memori utama antara membaca dan menulis). (Juga perhatikan bahwa menulis ke memori bahwa 'rep movsb(dioptimalkan memcpy dan memset dalam mikrokode, yang menghindari RFO, sejak implementasi Andy Glew di P6 (Pentium Pro) )).

Sejauh ini ini hanya bukti konsep, dan penanganan baris baru hanya kira-kira benar. Ada yang salah di sekitar ujung buffer power-of-2. Dengan lebih banyak waktu pengembangan. Saya yakin saya bisa menemukan cara yang lebih efisien untuk memasukkan baris baru yang juga tepat benar, dengan overhead setidaknya serendah ini (dibandingkan dengan hanya menghasilkan spasi). Saya pikir ini sekitar 10 hingga 20%. Saya hanya tertarik mengetahui seberapa cepat kami dapat menjalankan ini, tidak benar-benar memiliki versi yang dipoles, jadi saya akan meninggalkan bagian itu sebagai latihan untuk pembaca, dengan komentar yang menggambarkan beberapa ide.

Pada Haswell i5 pada 2.5GHz max turbo, dengan DDR3-1600MHz RAM , waktunya menghasilkan 100GiB tetapi diperkecil. (Waktunya pada cygwin64 pada Win10 dengan gcc5.4 -O3 -march=native, dihilangkan -funroll-loopskarena saya memiliki waktu yang cukup sulit untuk menjalankan pengaturan waktu yang layak pada laptop yang dipinjam ini. Seharusnya baru saja mem-boot Linux pada USB).

menulis ke / dev / null kecuali ditentukan lain.

• James Hollis's: (tidak diuji)
• Versi fwrite Nominal: ~ 2.21s
• this (SSE2): ~ 0.142s (waktu yang tidak dihitung = real = 14.232s, pengguna = 13.999s, sys = 0.187s).
• ini (AVX-128): ~ 0,140s
• ini (AVX2): ~ 0,073s (unscaled: real = 0m7.291s, pengguna = 0m7.125s, sys = 0m0.155s).
• ini (AVX2) cygwin piping ke wc -c, dengan 128kiB ukuran buffer: 0,32s dengan CPU pada 2,38GHz (max turbo dual-core). (waktu tidak dihitung: nyata = 32,466 pengguna = 11,468 detik sys = 41,092 detik, termasuk keduanya dan ini wc). Namun, hanya setengah data yang benar-benar disalin, karena program konyol saya menganggap bahwa tulis melakukan buffer penuh, meskipun itu tidak terjadi dan cygwin menulis () hanya melakukan 64k per panggilan ke pipa.

Jadi dengan SSE2 ini sekitar 15 kali lebih cepat dari kode skalar @Nominal Animal. Dengan AVX2, sekitar 30 kali lebih cepat. Saya tidak mencoba versi kode Nominal yang hanya menggunakan write()bukan fwrite(), tetapi mungkin untuk buffer besar stdio sebagian besar tetap menyingkir. Jika menyalin data, itu akan menyebabkan banyak pelambatan.

Kali untuk menghasilkan 1GB data pada Core2Duo E6600 (Merom 2.4GHz, 32kiB private L1, 4MiB berbagi cache L2), DDR2-533MHz di 64-bit Linux 4.2 (Ubuntu 15.10). Masih menggunakan ukuran buffer 128kiB untuk write (), belum menjelajahi dimensi itu.

menulis ke / dev / null kecuali ditentukan lain.

• (SSE2) ini dengan penanganan baris baru dan 4 vektor digit dari masing-masing vektor byte acak: 0,183s (waktunya melakukan 100GiB dalam 18,3s, tetapi hasil serupa untuk 1GiB berjalan). 1,85 instruksi per siklus.
• (SSE2) ini, menyalurkan ke wc -c: 0,593s (unscaled: real = 59.266s pengguna = 20.148s sys = 1m6.548s, termasuk waktu CPU wc). Jumlah yang sama dari sistem write () memanggil seperti dengan cygwin, tetapi sebenarnya mem-pip semua data karena Linux menangani semua 128k dari write () ke sebuah pipa.
• NominalAnimal ini fwrite()versi (gcc5.2 -O3 -march=native), dijalankan dengan ./decdig 100 $((1024*1024*1024/200)) > /dev/null: 3.19s +/- 0,1%, dengan 1,40 instruksi per siklus. -funroll-loop mungkin membuat perbedaan kecil. clang-3.8 -O3 -march=native: 3.42s +/- 0,1%
• Nominal fwritepiping ke wc -c: real = 3.980s pengguna = 3.176s sys = 2.080s
• Versi baris-at-a-waktu James Hollis ( clang++-3.8 -O3 -march=native): 22,855 +/- 0,07%, dengan 0,84 instruksi per siklus. (g ++ 5.2 sedikit lebih lambat: 22.98s). Menulis hanya satu baris pada satu waktu mungkin sangat menyakitkan.
• Stéphane Chazelas's tr < /dev/urandom | ...: real = 41,430s pengguna = 26,832s sys = 40,120s. trmendapatkan semua inti CPU untuk dirinya sendiri sebagian besar waktu, menghabiskan hampir seluruh waktunya di driver kernel menghasilkan byte acak dan menyalinnya ke sebuah pipa. Core lain pada mesin dual core ini menjalankan sisa pipa.
• time LC_ALL=C head -c512M </dev/urandom >/dev/null: yaitu hanya membaca bahwa banyak keacakan tanpa piping: real = 35.018s pengguna = 0,036s sys = 34.940s.
• Program perl Lưu Vĩnh Phúc (perl v5.20.2 dari Ubuntu15.10)
  LANG=en_CA.UTF-8:: real = 4m32.634s pengguna = 4m3.288s sys = 0m29.364.
  LC_ALL=C LANG=C: real = 4m18.637s pengguna = 3m50.324s sys = 0m29.356s. Masih sangat lambat.

• (SSE2) ini tanpa penanganan baris baru , dan 3 atau 4 vektor digit dari masing-masing vektor byte acak (kecepatan hampir persis sama: dig3 = v%10langkahnya adalah tentang impas pada HW ini): 0,166s (1,82 instruksi per siklus) . Ini pada dasarnya adalah batas bawah untuk apa yang bisa kita lakukan dengan penanganan baris baru yang sangat efisien.

• (SSE2) Versi lama ini tanpa penanganan baris baru, tetapi hanya mendapatkan satu digit per elemen uint16_t menggunakan v%10, 0,222 detik +/- 0,4%, 2,12 instruksi per siklus. (Dikompilasi dengan gcc5.2 -march=native -O3 -funroll-loops,. Buka gulungan tidak terjadi untuk membantu kode ini pada perangkat keras ini. Jangan menggunakannya secara membabi buta, terutama untuk program besar).
• (SSE2) Versi lama ini, menulis ke file (pada RAID10f2 dari 3 hard drive magnetik cepat, tidak terlalu dioptimalkan untuk menulis): ~ 4 detik. Bisa lebih cepat dengan mengubah pengaturan buffer I / O kernel untuk memungkinkan lebih banyak data kotor sebelum blok tulis (). Waktu "Sistem" masih ~ 1,0 detik, jauh lebih tinggi dari waktu "pengguna". Pada sistem lama ini dengan RAM DDR2-533 yang lambat, dibutuhkan ~ 4x lebih lama untuk memcpy data ke dalam pagecache dan menjalankan fungsi-fungsi XFS dibandingkan dengan loop saya untuk terus menulis ulang di tempat dalam buffer yang tetap panas di cache.

Bagaimana itu dilakukan

PRNG yang cepat jelas penting. xorshift128 + dapat di-vektor-kan, sehingga Anda memiliki dua atau empat generator 64-bit secara paralel, dalam elemen-elemen vektor SIMD. Setiap langkah menghasilkan vektor penuh byte acak. ( Implementasi 256b AVX2 di sini dengan Intel intrinsik ). Saya mengambilnya dari Nominal's pilihan xorshift *, karena multiplikasi vektor integer 64-bit hanya mungkin di SSE2 / AVX2 dengan teknik presisi yang diperluas .

Diberikan vektor byte acak, kita dapat memotong setiap elemen 16-bit menjadi beberapa angka desimal. Kami menghasilkan beberapa vektor elemen 16-bit yang masing-masing satu digit ASCII + ruang ASCII . Kami menyimpannya langsung ke buffer output kami.

Versi asli saya hanya digunakan x / 6554untuk mendapatkan satu digit acak dari setiap elemen uint16_t dari suatu vektor. Itu selalu antara 0 dan 9, inklusif. Itu bias jauh dari 9, karena (2^16 -1 ) / 6554hanya 9,99923. (6554 = ceil ((2 ^ 16-1) / 10), yang memastikan bahwa hasil bagi selalu <10.)

x/6554dapat dihitung dengan satu kalikan dengan konstanta "ajaib" ( titik tetap timbal balik ) dan pergeseran kanan dari hasil setengah tinggi. Ini adalah kasus terbaik untuk pembagian oleh konstanta; beberapa pembagi mengambil lebih banyak operasi, dan divisi yang ditandatangani membutuhkan kerja ekstra. x % 10memiliki bias yang sama dan tidak semurah untuk menghitung. (Keluaran asm gcc setara dengan x - 10*(x/10), yaitu penggandaan ekstra dan kurangi di atas divisi menggunakan invers multiplikatif modular.) Juga, bit xorshift128 + terendah tidak berkualitas tinggi , jadi membagi untuk mengambil entropi dari bit tinggi lebih baik ( untuk kualitas dan kecepatan) daripada modulo untuk mengambil entropi dari bit rendah.

Namun, kita dapat menggunakan lebih banyak entropi di setiap uint16_t dengan melihat angka desimal rendah, seperti digit()fungsi @ Nominal . Untuk kinerja maksimum, saya memutuskan untuk mengambil 3 angka desimal rendah dan x/6554, untuk menghemat satu PMULLW dan PSUBW (dan mungkin beberapa MOVDQA) vs. pilihan kualitas yang lebih tinggi dengan mengambil 4 angka desimal rendah. x / 6554 sedikit dipengaruhi oleh rendahnya 3 digit desimal, sehingga ada beberapa korelasi antara digit dari elemen yang sama (8 atau 16 digit pemisahan dalam output ASCII, tergantung pada lebar vektor).

Saya pikir gcc membaginya dengan 100 dan 1000, daripada rantai yang lebih panjang yang secara berturut-turut membaginya dengan 10, jadi mungkin tidak secara signifikan memperpendek panjang rantai ketergantungan yang tidak digerakkan-loop yang menghasilkan 4 hasil dari setiap output PRNG. port0 (vektor multiply dan shift) adalah hambatan karena inversi modular multiplikatif, dan pergeseran dalam xorshift +, jadi pasti berguna untuk menyimpan vektor-multiply.

xorshift + sangat cepat sehingga bahkan hanya menggunakan ~ 3,3 bit keacakan dari setiap 16 (yaitu efisiensi 20%) tidak jauh lebih lambat daripada memotongnya menjadi beberapa angka desimal. Kami hanya memperkirakan distribusi seragam, karena jawaban ini difokuskan pada kecepatan selama kualitasnya tidak terlalu buruk.

Setiap jenis perilaku kondisional yang membuat sejumlah variabel elemen akan membutuhkan lebih banyak pekerjaan. (Tapi mungkin masih bisa dilakukan agak efisien menggunakan teknik pengemasan kiri SIMD . Namun, yang menjadi kurang efisien untuk ukuran elemen kecil; tabel pencarian topeng-acak tidak memungkinkan, dan tidak ada AVX2 lane-crossing shuffle dengan yang lebih kecil dari 32- elemen bit. Sebuah versi 128H PSHUFB mungkin masih dapat menghasilkan topeng dengan cepat dengan BMI2 PEXT / PDEP, seperti yang Anda bisa untuk AVX2 dengan elemen yang lebih besar , tetapi rumit karena bilangan bulat 64-bit hanya menampung 8 byte. Link godbolt pada jawaban itu ada beberapa kode yang mungkin berfungsi untuk jumlah elemen yang lebih tinggi.)

Jika latensi RNG adalah hambatan, kita bisa lebih cepat lagi dengan menjalankan dua vektor generator secara paralel, bergantian mana yang kita gunakan. Compiler masih dapat dengan mudah menyimpan semuanya dalam register dalam satu loop yang tidak terbuka, dan itu memungkinkan dua rantai dependensi berjalan secara paralel.

Dalam versi saat ini, memotong output dari PRNG, kita sebenarnya bottleneck pada throughput port 0, bukan latensi PRNG, jadi tidak perlu untuk itu.

Kode: versi AVX2

Versi lengkap dengan lebih banyak komentar di explorer compiler Godbolt .

Tidak terlalu rapi, maaf saya harus tidur dan ingin memposting ini.

Untuk mendapatkan versi SSE2, s/_mm256/_mm, s/256/128/, s/v16u/v8u/, dan perubahan vector_size(32)ke 16. Juga mengubah selisih baris dari 4 * 16-4 * 8. (Seperti yang saya katakan, kode berantakan, dan tidak diatur dengan baik untuk mengkompilasi dua versi. Awalnya tidak berencana membuat versi AVX2, tapi kemudian saya benar-benar ingin menguji pada Haswell CPU yang saya punya akses.)

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

}

Kompilasi dengan gcc, dentang, atau ICC (atau mudah-mudahan kompiler lain yang memahami dialek GNU C C99, dan intrinsik Intel). Ekstensi vektor GNU C sangat mudah untuk mendapatkan kompiler untuk menghasilkan angka ajaib untuk divisi / modulo menggunakan inversi multiplikatif modular, dan sesekali __attribute__berguna.

Ini bisa ditulis dengan mudah, tetapi akan membutuhkan lebih banyak kode.

Catatan kinerja:

Toko tumpang tindih untuk menyisipkan baris baru memiliki overhead yang signifikan untuk memutuskan di mana menempatkannya (salah duga cabang, dan kemacetan frontend pada Core2), tetapi toko itu sendiri tidak memiliki dampak pada kinerja. Mengomentari hanya itu instruksi toko di asm kompiler (meninggalkan semua percabangan yang sama) meninggalkan kinerja pada Core2 sama sekali tidak berubah, dengan berjalan berulang memberikan waktu yang sama untuk +/- kurang dari 1%. Jadi saya menyimpulkan bahwa buffer toko / cache menanganinya dengan baik.

Namun, menggunakan beberapa jenis jendela putar ascii_digitspacedengan satu elemen yang memiliki baris baru mungkin lebih cepat, jika kita cukup membuka gulungan sehingga penghitung / percabangan hilang.

Menulis ke / dev / null pada dasarnya adalah no-op, jadi buffer mungkin tetap panas di L2 cache (256kiB per core pada Haswell). Diharapkan speedup sempurna dari 128b vektor ke 256b vektor: tidak ada instruksi tambahan, dan semuanya (termasuk toko) terjadi dengan lebar dua kali lipat. Cabang penyisipan baris baru diambil dua kali lebih sering. Sayangnya saya tidak sempat mengatur Haswell cygwin dengan bagian itu #ifdefdiedit.

2.5GHz * 32B / 13.7GB / s = 5.84 siklus per AVX2-store di Haswell. Itu cukup bagus, tetapi bisa lebih cepat. Mungkin ada beberapa overhead dalam panggilan sistem cygwin daripada yang saya kira. Saya tidak mencoba mengomentari mereka dalam output asm kompiler (yang akan memastikan bahwa tidak ada yang dioptimalkan.)

Cache L1 dapat mempertahankan satu toko 32B per jam, dan L2 tidak bandwidth yang jauh lebih rendah (latensi lebih tinggi, meskipun).

Ketika saya melihat IACA beberapa versi yang lalu (tanpa bercabang untuk baris baru, tetapi hanya mendapatkan satu vektor ASCII per vektor RNG), itu memprediksi sesuatu seperti satu toko vektor 32B per 4 atau 5 jam.

Saya berharap untuk mendapatkan lebih banyak percepatan dari mengekstraksi lebih banyak data dari setiap hasil RNG, berdasarkan pada melihat asm sendiri, mempertimbangkan panduan Agner Fog dan sumber daya pengoptimalan lainnya yang telah saya tambahkan tautan untuk dalam wiki tag SO x86 .)

Kemungkinan akan lebih cepat secara signifikan pada Skylake , di mana vektor integer dan pergeseran dapat berjalan pada port dua kali lebih banyak (p0 / p1) dibandingkan dengan Haswell (hanya p0). xorshift dan ekstraksi digit keduanya menggunakan banyak pergeseran dan penggandaan. ( Pembaruan: Skylake menjalankannya pada IPC 3.02, memberi kami 3,77 siklus per toko AVX2 32-byte , dihitung pada 0,030 detik per iterasi 1GB, menulis /dev/nulldi Linux 4,15 pada i7-6700k pada 3,9GHz.

Tidak memerlukan mode 64-bit untuk bekerja dengan baik . Versi SSE2 sama cepatnya ketika dikompilasi -m32, karena ia tidak membutuhkan register vektor yang sangat banyak, dan semua matematika 64-bit dilakukan dalam vektor, bukan register untuk keperluan umum.

Ini sebenarnya sedikit lebih cepat dalam mode 32-bit pada Core2, karena membandingkan / cabang makro-fusi hanya bekerja dalam mode 32-bit, jadi ada lebih sedikit uops untuk core out-of-order (18,3s (1,85 Instructions Per Clock) vs .16.9s (2.0 IPC)). Ukuran kode yang lebih kecil karena tidak memiliki awalan REX juga membantu decoder Core2.

Juga, beberapa gerakan vektor reg-reg diganti dengan beban, karena tidak semua konstanta memperbaiki dalam vektor regs lagi. Karena memuat throughput dari cache L1 bukan hambatan, ini sebenarnya membantu. (mis. mengalikan dengan vektor konstan set1(10): movdqa xmm0, xmm10/ pmullw xmm0, xmm1berubah menjadi movdqa xmm0, [constant]/ pmullw xmm0, xmm1.) Karena reg-reg MOVDQA membutuhkan port ALU, itu bersaing dengan pekerjaan nyata yang sedang dilakukan, tetapi beban MOVDQA hanya bersaing untuk bandwidth decode front-end. (Memiliki alamat 4-byte di dalam banyak instruksi membatalkan banyak keuntungan dari menyimpan awalan REX.

Saya tidak akan terkejut jika menyimpan ALU MOVDQA uops adalah tempat keuntungan sebenarnya berasal, karena frontend harus mengikuti rata-rata 2,0 IPC dengan cukup baik.

Semua perbedaan ini menghilang di Haswell, di mana semuanya harus dijalankan dari cache yang di-decode, jika bukan buffer loopback. Fusi makro cabang ALU + bekerja di kedua mode sejak Nehalem.

Inilah solusi yang saya harap mudah dimengerti:

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

• odmenciptakan aliran seragam dari angka heksadesimal /dev/random.
• trmenghilangkan huruf, hanya menyimpan 0-9digit
• fold memastikan ada 100 digit per baris
• awk menyisipkan spasi di dalam garis
• head memotong input ke 1 gigabyte

Anda dapat menggunakan jotperintah untuk ini:

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

Ini mirip dengan metode Stéphane Chazelas, namun saya membaca 64 bit sekaligus untuk meningkatkan kinerja. Distribusi masih seragam tetapi sekarang Anda mendapatkan 19 digit untuk setiap 8 byte, bukan hanya 8 dalam kasus terbaik seperti sebelumnya

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

Pada platform 32-bit, 9 digit akan dibaca setiap kali alih-alih 19.

Saya agak setuju dengan Nominal Animal dalam menggunakan bahasa pemrograman yang dikompilasi jika Anda membutuhkan kecepatan. Namun, Anda tidak perlu menulis kode RNG Anda sendiri dalam C. C ++ 11 menawarkan Mersenne Twister yang sangat baik sebagai bagian dari perpustakaan standarnya.

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

Kode di atas cukup sederhana dan memakan waktu sekitar satu menit ketika saya mengirim output ke file. Kita bisa bergerak jauh lebih cepat dengan membuat string yang cukup besar untuk 100 digit dan meretasnya. Ini memungkinkan kita untuk memanggil semua saluran daripada setiap digit.

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

Kode ini membutuhkan mesin saya sekitar enam detik. Ingat itu adalah output standar, jadi pipa itu ke file.

Saya punya beberapa penafian. Pertama, saya menulis ini di PC Windows. Saya pikir semua perpustakaan ada di Linux, tetapi jika saya salah, pastikan untuk menunjukkannya.

Juga, ini sebenarnya menghasilkan setengah miliar digit ruang yang terpisah, yang secara teknis satu gigabyte tetapi mungkin tidak persis seperti yang Anda inginkan. Ini menghasilkan 5 juta baris, 100 digit per baris. Jika perbedaannya penting, Anda dapat menambah jumlah garis. Pada kotak Windows saya, file tersebut tampaknya sedikit lebih besar dari 10 ^ 9 byte, yang saya pikir ada hubungannya dengan karakter baris baru tambahan.

Itu tergantung pada definisi Anda tentang "acak". Jika maksud Anda adalah cryptographically random, Anda hanya perlu mendapatkan perpustakaan yang bagus dan menggigit peluru, tunggu sampai berjalan.

Jika Anda hanya perlu sesuatu yang terlihat cukup acak, berikut ini adalah cara mudah:

1. Dapatkan file yang panjangnya beberapa Gb. Film favorit Anda akan bagus.
2. Gzip itu, cara mudah untuk memeras pola berulang
3. Pergi melalui file nybble (setengah byte) sekaligus. Setiap nilai akan berada di antara 0 dan 15. Buang kurang dari 1 atau lebih besar dari 10. Kurangi 1 dari masing-masing miliar pertama yang selamat dan catat sebagai digit.

Mungkin butuh satu jam untuk berjalan di mesin yang lambat; cukup cepat dan cukup acak untuk sebagian besar keperluan.

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