Вопросы Теги

Какой самый быстрый способ сгенерировать текстовый файл размером 1 ГБ, содержащий случайные цифры?

Проблема возникла из-за того, что расширения netfilter не были включены в мою пропатченную версию ядра Linux.

Поэтому мне пришлось перекомпилировать ядро и активировать различные опции конфигурации, такие как: 

# Xtables targets
#
CONFIG_NETFILTER_XT_TARGET_AUDIT=y
CONFIG_NETFILTER_XT_TARGET_CHECKSUM=y
CONFIG_NETFILTER_XT_TARGET_CLASSIFY=y
CONFIG_NETFILTER_XT_TARGET_CONNMARK=y
CONFIG_NETFILTER_XT_TARGET_CONNSECMARK=y
CONFIG_NETFILTER_XT_TARGET_DSCP=y

# This one provides the TTL target
CONFIG_NETFILTER_XT_TARGET_HL=y 
CONFIG_NETFILTER_XT_TARGET_HMARK=y
...

и теперь все работает!

52
21.11.2016, 22:14
10 ответов

Это частично насмешливый ответ из-за названия вопроса.

Когда вы ищете «самый быстрый способ ...» , почти всегда ответом является какой-то специализированный инструмент. Эти «ответы» показывают один из таких инструментов, чтобы вы могли поэкспериментировать.

Это несерьезный ответ, потому что вам не следует искать специализированные инструменты для работы, которую вы выполняете только один раз или очень редко. Видите ли, вы в конечном итоге потратите больше времени на поиск инструментов и изучение их, чем на самом деле. Оболочки и утилиты, такие как bash и awk , не самые быстрые, но обычно вы можете написать однострочник для выполнения работы, потратив всего несколько секунд. Можно также использовать более совершенные языки сценариев, такие как perl , хотя кривая изучения perl очень крутая, и я не решаюсь рекомендовать его для таких целей, потому что я был травмирован ужасным Perl проекты. python , с другой стороны, немного затруднен из-за довольно медленного ввода-вывода; однако это проблема только при фильтрации или генерации гигабайт данных.

В любом случае следующая программа-пример C89 (которая использует POSIX.1 для повышения точности тактовой частоты, только если она доступна) должна достичь скорости генерации около 100 МБ / с (проверено в Linux на ноутбуке с процессором Intel i5-4200U, направляя вывод в / dev / null ), используя довольно хороший генератор псевдослучайных чисел. (Выходные данные должны пройти все тесты BigCrunch, кроме теста MatrixRank, поскольку в коде используется xorshift64 * и метод исключения, чтобы избежать смещения цифр.)

decimal-digits.c: 

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

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

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

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

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

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

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

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

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

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

    return result - UINT64_C(1);
}

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

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

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

    return retval;
}

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

    if (!src)
        return errno = EINVAL;

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

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

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

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

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

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

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

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

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

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

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

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

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

    return EXIT_SUCCESS;
}

Мы можем сделать это намного быстрее, если переключимся на строковый буфер, и fwrite () он будет работать один раз вместо того, чтобы выводить каждую цифру за раз. Обратите внимание, что мы по-прежнему сохраняем полную буферизацию потока, чтобы избежать частичной (не степени двойки) записи, если выход является блочным устройством. 

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

Примечание: оба примера, отредактированные 18.11.2016 до , обеспечивают равномерное распределение цифр (ноль исключен; см., Например, здесь для сравнения и подробностей о различных псевдослучайных числах. генераторы).

Скомпилируйте с использованием, например, 

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

и, возможно, установите для всей системы в / usr / bin с помощью 

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

. Требуется количество цифр в строке и количество строк. Поскольку 1000000000/100/2 = 5000000 (пять миллионов; общее количество байтов, разделенных на столбцы, разделенные на 2), вы можете использовать 

./decimal-digits 100 5000000 > digits.txt

для создания digits.txt размером гигабайт как желаемый OP.

Обратите внимание, что сама программа написана больше для удобочитаемости, чем для эффективности. Мое намерение здесь не в том, чтобы продемонстрировать эффективность кода - я бы все равно использовал POSIX.1 и низкоуровневый ввод-вывод, а не общие интерфейсы C, - а чтобы вы могли легко увидеть, какой баланс между затраченными усилиями в разработке специализированных инструментов по сравнению с их производительностью, по сравнению с однострочными, короткими оболочками или сценариями awk.

Использование библиотеки GNU C, вызов функции fputc () для каждого вывода символа влечет за собой очень небольшие накладные расходы (косвенный вызов функции или условные выражения - интерфейс FILE на самом деле довольно сложный и универсальный, понимаете).На этом конкретном ноутбуке Intel Core i5-4200U с перенаправлением вывода на / dev / null первая (fputc) версия занимает около 11 секунд, тогда как построчная версия занимает всего 1,3 секунды. .

Я часто пишу такие программы и генераторы только потому, что мне нравится играть с огромными наборами данных. Я такой странный. Например, однажды я написал программу для вывода всех конечных положительных значений с плавающей запятой IEEE-754 в текстовый файл с достаточной точностью, чтобы получить точно такое же значение при синтаксическом анализе. Размер файла составлял несколько гигабайт (возможно, 4G или около того); конечных положительных чисел с плавающей запятой не так много, как можно было бы подумать. Я использовал это для сравнения реализаций, которые читают и анализируют такие данные.

Для обычных случаев использования, таких как OP, сценарии оболочки, скриптлеты и однострочники являются лучшим подходом. Меньше времени тратится на выполнение общей задачи. (За исключением случаев, когда им нужен новый файл каждый день или около того, или есть много людей, которым нужен другой файл, и в этом случае - в редких случаях - специальный инструмент, как указано выше, может оправдать затраченные усилия.)

{{1 }}
40
27.01.2020, 19:33

Это: 

 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

(при условии, что реализация head , которая поддерживает -c ), кажется достаточно быстрой в моей системе.

tr переводит весь диапазон байтов (от 0 до 255, от 0 до 0377 в восьмеричной системе): 25 первых байтов как 0, следующие 25 байтов как 1 ... затем 25 9 остальные (от 250 до 255) к "x", который мы затем отбрасываем (с помощью tr -dx ), поскольку мы хотим равномерного распределения (предполагая, что / dev / urandom сам имеет равномерное распределение) и поэтому не даем смещения до нескольких цифр.

Это дает одну цифру для 97% байтов / dev / urandom . fold -w 1 делает одну цифру в строке. paste -s вызывается со списком разделителей, который состоит из 99 пробелов и одного символа новой строки, чтобы в каждой строке было 100 цифр, разделенных пробелами.

head -c1G получит первый ГиБ (2 30 ) этого. Обратите внимание, что последняя строка будет усечена и не ограничена. Вы можете усечь до 2 30 -1 и вручную добавить недостающую новую строку или вместо этого усечь до 10 9 байтов, что составляет 50 миллионов из этих 200-байтовых строк ( head - n 50000000 также сделает его стандартной / переносимой командой).

Эти тайминги (полученные с помощью zsh в четырехъядерной системе) показывают, на что тратится время ЦП: 

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

Первое tr - это горлышко бутылки. , большую часть времени, проведенного в ядре (я полагаю, для генерации случайных чисел). Время примерно соответствует скорости, с которой я могу получать байты из / dev / uramdom (около 19 МБ / с, и здесь мы производим 2 байта на каждые 0,97 байта / dev / urandom со скоростью 32 МБ / с. с). fold , похоже, тратит неоправданное количество процессорного времени (15 секунд) только на вставку символа новой строки после каждого байта, но это не влияет на общее время, поскольку в моем случае это работает на другом процессоре (добавление параметр -b делает его немного более эффективным, dd cbs = 1 conv = unblock кажется лучшей альтернативой).

Вы можете избавиться от head -c1G и сократить время на несколько секунд, установив ограничение на размер файла ( limit размер файла 1024m с помощью zsh или ulimit -f "$ ((1024 * 1024))" с большинством других оболочек (включая zsh ) вместо подоболочки.

Это можно было бы улучшить, если бы мы извлекли по 2 цифры для каждого байта, но для этого нам понадобится другой подход. Вышеупомянутое очень эффективно, потому что tr просто просматривает каждый байт в 256-байтовом массиве. Он не может делать это для 2 байтов за раз, и использование таких вещей, как hexdump -e '1/1 "% 02u"' , которое вычисляет текстовое представление байта с использованием более сложных алгоритмов, было бы более сложным. дороже, чем сама генерация случайных чисел. Тем не менее, если, как в моем случае, у вас есть ядра ЦП, время которых можно сэкономить, ему все равно удастся сэкономить несколько секунд:

С: 

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

Я получаю (обратите внимание, что здесь 1 000 000 000 байт вместо 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

В целом больше процессорного времени, но лучше распределяется между моими четырьмя ядрами процессора, так что в итоге оно занимает меньше времени на настенных часах. Теперь узким местом является шестнадцатеричный дамп .

Если мы используем dd вместо строчного свертки , мы можем фактически уменьшить объем работы, которую необходимо выполнить hexdump , и улучшить баланс работа между процессорами: 

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

(здесь предполагается, что GNU dd для его iflag = fullblock и status = none ), что дает: 

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

Возврат к генерации случайных чисел, являющейся узким местом.

Теперь, как указывает @OleTange, если у вас есть утилита openssl , вы можете использовать ее для получения более быстрого (особенно на процессорах с инструкциями AES) псевдослучайного генератора байтов. 

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

в моей системе выделяет в 15 раз больше байтов в секунду, чем / dev / urandom . (Я не могу прокомментировать его сравнение с криптографически безопасным источником случайности , если это применимо к вашему варианту использования). 

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

Теперь возвращает: 

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

обратно к hexdump , являющемуся узким местом.

Поскольку у меня еще есть свободные процессоры, я могу запустить 3 из этих шестнадцатеричных дампа параллельно. 

</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 требуется для оболочек, отличных от zsh , которые закрывают стандартный ввод команд на / dev / null при запуске в фоновом режиме).

Теперь время сократилось до 6,2 секунды, и мои процессоры почти полностью загружены.

81
27.01.2020, 19:33

Для этого можно использовать команду jot:

jot -r 50000000 0 9 | fmt -w 200 > output.txt
6
27.01.2020, 19:33

Это похоже на метод Стефана Шазеласа, однако я считываю сразу 64 бита, чтобы повысить производительность. Распределение по-прежнему равномерное, но теперь вы получаете 19 цифр на каждые 8 ​​байтов вместо 8 в лучшем случае, как раньше 

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

На 32-битной платформе каждый раз будет считываться 9 цифр вместо 19.

{{1 }}
6
27.01.2020, 19:33

Вот решение, которое, я надеюсь, простое для понимания: 

od -An -x /dev/urandom | tr -dc 0-9 | fold -w100 | awk NF=NF FS= | head -c1G
  • od создает однородный поток шестнадцатеричных цифр из / dev / random .
  • tr избавляется от букв, только сохранение 0-9 цифр
  • свертка гарантирует, что в каждой строке будет 100 цифр
  • awk вставляет пробелы внутри строк
  • head усекает ввод до 1 гигабайта
14
27.01.2020, 19:33

Я вроде как согласен с Nominal Animal в использовании скомпилированного языка программирования, если вам нужна скорость. Однако вам не нужно писать собственный код ГСЧ на C. C ++ 11 предлагает отличный Mersenne Twister как часть своей стандартной библиотеки.

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

Приведенный выше код достаточно прост и занимает около минуты, когда я передаю вывод в файл. Мы можем пойти намного быстрее, создав строку, достаточно большую для 100 цифр, и вставив в нее цифры. Это позволяет нам вызывать cout каждую строку, а не каждую цифру. 

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

Этот код занимает у моей машины около шести секунд. Помните, что это стандартный вывод, поэтому перенаправьте его в файл.

У меня есть несколько заявлений об отказе от ответственности. Сначала я пишу это на ПК с Windows. Я думаю, что все библиотеки присутствуют в Linux, но если я ошибаюсь, обязательно укажите на это.

Кроме того, он фактически выводит ровно полмиллиарда цифр, разделенных пробелами, что технически составляет гигабайт, но, возможно, не совсем то, что вам нужно. Он выводит 5 миллионов строк, по 100 цифр в строке. Если разница важна, можно увеличить количество строк. В моем окне Windows файл кажется немного больше, чем 10 ^ 9 байт, что, как мне кажется, связано с дополнительными символами новой строки.

3
27.01.2020, 19:33

Если вам не нужна случайность очень высокого качества и достаточно хорошее распределение, близкое к однородному, вы можете пойти действительно быстро, особенно на современных процессорах с эффективными целочисленными векторами SIMD, такими как x86 с SSE2 или AVX2.

Это похоже на ответ @ NominalAnimal , поскольку у нас обоих была одна и та же идея, но вручную векторизовали для x86. (И со случайными числами худшего качества, но все же, вероятно, достаточно хороши для многих случаев использования.) Это работает примерно в 15 или 30 раз быстрее, чем код @ Nominal, при ~ 13 ГБ / с вывода ASCII на Intel Haswell 2,5 ГГц CPU с AVX2. Это все еще меньше теоретической максимальной пропускной способности основной памяти (двухканальная DDR3-1600 составляет около 25,6 ГБ / с), но я рассчитывал время записи в / dev / null, поэтому на самом деле он просто перезаписывает буфер, который остается горячим в кеше. Skylake должен запускать этот же код значительно быстрее, чем Haswell (см. Нижнюю часть этого ответа).

Предполагая, что у вас действительно есть узкое место при вводе-выводе на диск или где-то в конвейере, быстрая реализация означает, что вашему ЦП даже не нужно работать выше, чем в режиме ожидания.Для получения результата он потребляет гораздо меньше энергии. (Срок службы батареи / нагревание / глобальное потепление.)

Это настолько быстро, что вы, вероятно, не захотите записывать его на диск. Просто при необходимости повторно сгенерируйте (из того же начального числа, если вам снова нужны те же данные). Даже если вы хотите передать его многопоточному процессу, который может использовать все процессоры, запуск этого для передачи данных ему оставит его горячим в кэше L3 (и кешем L2 на ядре, которое его записало), и использовать очень мало процессорного времени. (Но обратите внимание, что конвейер добавляет много накладных расходов по сравнению с записью в / dev / null . На Skylake i7-6700k, конвейерный канал к wc -c или другой программе, которая просто читает + отбрасывает свой ввод, это примерно в 8 раз медленнее, чем запись в / dev / null , и использует только 70% ЦП. Но это все еще 4,0 ГБ / с для ЦП с тактовой частотой 3,9 ГГц.

Повторное создание происходит быстрее, чем повторное считывание даже с быстрого твердотельного накопителя, подключенного к PCIe, но IDK, если он более энергоэффективен (векторно-целочисленный множитель довольно загружен, и он, вероятно, довольно энергоемкий, наряду с другими AVX2. 256b векторных ALU). OTOH, я не знаю, сколько процессорного времени, считывающего с диска, отнимет у чего-то, что загружало все ядра, обрабатывающие этот ввод. может конкурировать с запуском кода файловой системы / кэша страниц и выделением страниц для чтения данных с диска. Конечно, если в кэше страниц уже горячо, это просто memcpy. OTOH, мы уже я пишу так же быстро, как memcpy! (который должен разделить полосу пропускания основной памяти между чтением и записью).(Также обратите внимание, что запись в память, которая еще не горячая в кеше, обычно запускает чтение для владения для поддержания когерентности кеша, чего можно избежать с помощью невременных хранилищ или с помощью x86 rep movsb (оптимизированный memcpy и memset в микрокоде, который избегает RFO, с тех пор, как Энди Глю реализовал его в P6 (Pentium Pro) )).

Пока это только доказательство концепции, и обработка новой строки верна только приблизительно. Это неправильно на концах буфера со степенью двойки. С большим временем разработки. Я уверен, что смогу найти более эффективный способ вставки новой строки, который также является совершенно правильным, с такими же низкими накладными расходами (по сравнению с выводом только пробелов). Я думаю, что это примерно от 10 до 20%. Меня интересует только то, насколько быстро мы можем выполнить этот запуск, а не то, чтобы на самом деле иметь его доработанную версию, поэтому я оставлю эту часть в качестве упражнения для читателя с комментариями, описывающими некоторые идеи.

На Haswell i5 с максимальной частотой 2,5 ГГц в режиме турбо, с оперативной памятью DDR3-1600 МГц , с синхронизированным производством 100 ГБ, но с уменьшенным масштабом. (Приурочено к cygwin64 на Win10 с gcc5.4 -O3 -march = native , опущено -funroll-loops , так как мне было трудно добиться приличного времени на этом заимствованном ноутбуке . Должен был только что загрузился Linux через USB).

запись в / dev / null, если не указано иное.

  • Джеймс Холлис: (не тестировался)
  • Версия записи номинала: ~ 2,21 с
  • это (SSE2): ~ 0,142 с (немасштабированное время = реальное = 14,232 с, пользователь = 13,999 с, sys = 0,187 с).
  • this (AVX-128): ~ 0,140 сек.
  • this (AVX2): ~ 0.073 с (немасштабированное: вещественное = 0 мин. 7,291 с, пользовательское = 0 мин. 7,125 с, sys = 0 мин. 0,155 с).
  • this (AVX2) cygwin соединяется с wc -c с размером буфера 128 КБ: 0,32 с при частоте процессора 2,38 ГГц (макс. Двухъядерный турбо). (Немасштабированное время: реальное = 32,466 с, пользователь = 11,468 с, системное = 41,092 с, включая это и wc ). На самом деле была скопирована только половина данных, потому что моя глупая программа предполагает, что запись выполняет полный буфер, хотя это не так, и cygwin write () выполняет только 64 КБ на вызов в канал.

Таким образом, с SSE2 это примерно в 15 раз быстрее, чем скалярный код @Nominal Animal. С AVX2 это примерно в 30 раз быстрее. Я не пробовал версию кода Nominal, которая просто использует write () вместо fwrite () , но, по-видимому, для больших буферов stdio в основном не используется. Если он копирует данные, это приведет к значительному замедлению работы.

Время создания 1 ГБ данных на Core2Duo E6600 (Merom 2,4 ГГц, частный L1 32 КБ, общий кэш L2 4 МБ), DDR2-533 МГц в 64-разрядной версии Linux 4.2 (Ubuntu 15.10). Все еще используя размер буфера 128 КБ для write (), не исследовали это измерение.

запись в / dev / null, если не указано иное.

  • (SSE2) это с обработкой новой строки и 4 векторами цифр из каждого вектора случайных байтов: 0,183 с (рассчитано по времени при выполнении 100 ГБ за 18,3 с, но аналогичные результаты для прогонов 1 ГБ). 1,85 инструкций за цикл.
  • (SSE2) это, соединяется с wc -c : 0,593 с (немасштабировано: реальный = 59,266 с пользователь = 20,148 с sys = 1 м6,548 с, включая процессорное время wc). Такое же количество системных вызовов write (), как и в cygwin, но на самом деле все данные передаются по конвейеру, потому что Linux обрабатывает все 128 Кбайт write () в конвейер.
  • Версия NominalAnimal fwrite () (gcc5.2 -O3 -march = native ), запустить с ./ decdig 100 $ ((1024 * 1024 * 1024/200))> / dev / null : 3,19 с +/- 0,1%, с 1,40 инструкциями за цикл. -funroll-loops, может быть, немного изменили ситуацию. clang-3.8 -O3 -march = native : 3.42s +/- 0.1%
  • Nominal- fwrite piping to wc -c : real = 3.980 s user = 3.176s sys = 2.080s
  • Построчная версия Джеймса Холлиса ( clang ++ - 3.8 -O3 -march = native ): 22,885s +/- 0,07%, с 0,84 инструкций за цикл. (g ++ 5.2 был немного медленнее: 22,98 с). Написание только одной строки за раз, вероятно, значительно повредит.
  • tr Стефана Шазела : real = 41,430 сек. Пользователь = 26,832 сек. sys = 40,120 сек. tr большую часть времени передавал себе все ядро ​​процессора, проводя почти все свое время в драйвере ядра, генерируя случайные байты и копируя их в конвейер. Другое ядро ​​этой двухъядерной машины выполняло оставшуюся часть конвейера.
  • время LC_ALL = C head -c512M / dev / null : т.е. просто чтение такой большой случайности без конвейера: real = 35.018s user = 0.036s sys = 34.940с.
  • Perl-программа Лу Винь Фука (perl v5.20.2 из Ubuntu15.10):
    LANG = en_CA.UTF-8 : real = 4m32.634s user = 4m3.288s sys = 0m29.364.
    LC_ALL = C LANG = C : real = 4m18,637s user = 3m50,324s sys = 0m29,356s. Все еще очень медленно.
  • (SSE2) это без обработки новой строки и с 3 или 4 векторами цифр из каждого вектора случайных байтов (почти такая же скорость: dig3 = v% 10 шаг о безубыточности на этом HW): 0,166 с (1,82 инструкции за цикл). По сути, это нижний предел того, к чему мы можем приблизиться с идеально эффективной обработкой новой строки.
  • (SSE2) Старая версия без обработки новой строки, но получение только одной цифры на элемент uint16_t с использованием v% 10 , 0,222 секунды +/- 0,4%, 2,12 инструкций за цикл. (Скомпилировано с помощью gcc5.2, -march = native -O3 -funroll-loops . Циклы развертывания действительно помогают для этого кода на этом оборудовании. Не используйте его вслепую, особенно для больших программ).
  • (SSE2) Старая версия этого, запись в файл (на RAID10f2 из 3 быстрых магнитных жестких дисков, не очень оптимизированных для записи): ~ 4 секунды. Можно было бы работать быстрее, настроив параметры буфера ввода-вывода ядра, чтобы разрешить гораздо больше грязных данных перед блоками write (). «Системное» время по-прежнему составляет ~ 1.0 секунды, что намного больше, чем «пользовательское» время. В этой старой системе с медленной оперативной памятью DDR2-533 ядру требуется примерно в 4 раза больше времени для сохранения данных в кэше страниц и выполнения функций XFS, чем для моего цикла, чтобы продолжать переписывать их на месте в буфере, который остается горячим в кеш.

Как это делается

Очевидно, что быстрый ГПСЧ необходим. xorshift128 + может быть векторизован, поэтому у вас есть два или четыре 64-битных генератора параллельно в элементах вектора SIMD. Каждый шаг создает полный вектор случайных байтов.( Реализация 256b AVX2 здесь со встроенными функциями Intel ). Я выбрал его вместо xorshift *, который выбрал Номинал, потому что 64-битное векторное целочисленное умножение возможно только в SSE2 / AVX2 с методами повышенной точности .

Учитывая вектор случайных байтов, мы можем разбить каждый 16-битный элемент на несколько десятичных цифр. Мы производим несколько векторов 16-битовые элементы, каждый из которых представляет собой одну цифру ASCII + пробел ASCII . Мы сохраняем это прямо в нашем выходном буфере.

Моя первоначальная версия просто использовала x / 6554 для получения одной случайной цифры из каждого элемента uint16_t вектора. Всегда от 0 до 9 включительно. Он отклоняется от 9 , потому что (2 ^ 16 -1) / 6554 составляет всего 9,99923. (6554 = ceil ((2 ^ 16-1) / 10), что гарантирует, что частное всегда <10.)

x / 6554 можно вычислить, умножив на единицу "магическую" константу (, обратная величина с фиксированной точкой ) и сдвиг вправо результата с высокой половиной. Это лучший случай деления на константу; некоторые делители требуют больше операций, а деление со знаком требует дополнительной работы. x% 10 имеет аналогичное смещение и не так дешево в вычислении. (Вывод asm gcc эквивалентен x - 10 * (x / 10) , то есть дополнительному умножению и вычитанию поверх деления с использованием модульного обратного умножения.) Кроме того, младший бит xorshift128 + не так высокого качества , поэтому деление для получения энтропии из старших битов лучше (как по качеству, так и по скорости), чем по модулю для извлечения энтропии из младших битов.

Однако мы можем использовать больше энтропии в каждом uint16_t, глядя на младшие десятичные цифры, как функция @ Nominal digit () . Для максимальной производительности я решил взять 3 младшие десятичные цифры и x / 6554 , чтобы сэкономить один PMULLW и PSUBW (и, возможно, некоторый MOVDQA), вместо более качественного варианта использования 4 младших десятичных цифр.x / 6554 слегка зависит от трех младших десятичных цифр, поэтому существует некоторая корреляция между цифрами из одного и того же элемента (разделение 8 или 16 цифр в выводе ASCII, в зависимости от ширины вектора).

Я думаю, что gcc делит на 100 и на 1000, а не на более длинную цепочку, которая последовательно делится на 10, поэтому это, вероятно, не значительно сокращает длину цепочки зависимостей без циклического переноса, которая дает 4 результата на каждом выходе PRNG. . port0 (векторное умножение и сдвиг) является узким местом из-за модульных мультипликативных инверсий и сдвигов в xorshift +, поэтому определенно полезно сохранить векторное умножение.

xorshift + настолько быстр, что даже использование только ~ 3,3 бита случайности из каждых 16 (т.е. 20% эффективности) не намного медленнее, чем разбиение его на несколько десятичных цифр. Мы только приближаемся к равномерному распределению, потому что этот ответ ориентирован на скорость, если качество не так уж и плохо.

Любой вид условного поведения, поддерживающий переменное количество элементов, потребует гораздо больше работы. (Но, возможно, все еще можно было бы сделать несколько эффективно с использованием методов левой упаковки SIMD . Однако это становится менее эффективным для небольших размеров элементов; гигантские таблицы поиска по маске тасования нежизнеспособны, и нет пересечения полос AVX2 перемешайте элементы размером менее 32 бит. Версия 128b PSHUFB может по-прежнему иметь возможность генерировать маску на лету с BMI2 PEXT / PDEP, как вы можете для AVX2 с более крупными элементами , но это сложно, потому что 64-битное целое число содержит только 8 байтов.Ссылка Godbolt в этом ответе содержит некоторый код, который может работать для большего количества элементов.)

Если задержка ГСЧ является узким местом, мы могли бы пойти еще быстрее, запустив два вектора генераторов параллельно, чередуя тот, который мы используем. Компилятор по-прежнему может легко хранить все в регистрах в развернутом цикле, и это позволяет двум цепочкам зависимостей работать параллельно.

В текущей версии, разделив вывод PRNG, мы фактически ограничиваем пропускную способность порта 0, а не задержку PRNG, поэтому в этом нет необходимости.

Код: версия AVX2

Полная версия с дополнительными комментариями в проводнике компилятора Godbolt .

Не очень аккуратно, извините, мне нужно спать, и я хочу опубликовать это.

Чтобы получить версию SSE2, s / _mm256 / _mm , s / 256/128 / , s / v16u / v8u / и измените vector_size (32) на 16. Также измените приращение новой строки с 4 * 16 на 4 * 8. (Как я уже сказал, код запутан и плохо настроен для компиляции двух версий. Изначально не планировал делать версию AVX2, но потом я действительно хотел протестировать процессор Haswell, к которому у меня был доступ.) 

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

}

Компилируйте с помощью gcc, clang или ICC (или, надеюсь, любого другого компилятора, который понимает диалект GNU C для C99 и встроенные функции Intel). Векторные расширения GNU C очень удобны, чтобы заставить компилятор генерировать магические числа для деления / по модулю с использованием модульных мультипликативных инверсий, и иногда полезны __ attribute __ s.

Это можно было бы написать переносимо, но для этого потребовалось бы больше кода.

Примечания по производительности:

Перекрывающееся хранилище для вставки новых строк имеет значительные накладные расходы, чтобы решить, где его разместить (неверные предсказания ветвлений и узкие места внешнего интерфейса в Core2), но само хранилище не влияет на производительность.Комментируя только эту инструкцию сохранения в asm компилятора (оставляя все ветвления одинаковыми), производительность Core2 полностью не изменилась, а повторные запуски дали одинаковое время +/- менее 1%. Итак, я прихожу к выводу, что буфер / кеш хранилища справляются с этим нормально.

Тем не менее, использование некоторого вращающегося окна ascii_digitspace с одним элементом, имеющим новую строку, может быть даже быстрее, если мы развернем достаточно, чтобы исчезли все счетчики / ветвления.

Запись в / dev / null в основном не выполняется, поэтому буфер, вероятно, остается горячим в кэше L2 (256 КБ на ядро ​​на Haswell). Ожидается идеальное ускорение с векторов 128b до векторов 256b: нет дополнительных инструкций, и все (включая хранилища) происходит с вдвое большей шириной. Однако ветвь вставки новой строки используется в два раза чаще. К сожалению, у меня не было времени на моей настройке Haswell cygwin с удаленной частью #ifdef .

2,5 ГГц * 32 Б / 13,7 ГБ / с = 5,84 цикла на одно хранилище AVX2 на Haswell. Это неплохо, но могло бы быть быстрее. Может быть, в системных вызовах cygwin есть некоторые накладные расходы, чем я думал. Я не пробовал комментировать их в выводе asm компилятора (что гарантирует, что ничего не будет оптимизировано).

Кэш L1 может поддерживать одно хранилище 32 байт за такт, а L2 не намного снижает пропускную способность (хотя и более высокая задержка).

Когда я смотрел на IACA несколько версий назад (без перехода для новой строки, но получал только один вектор ASCII на вектор RNG), он предсказывал что-то вроде одного хранилища векторов 32B на 4 или 5 тактов.

Я надеялся получить больше ускорения за счет извлечения большего количества данных из каждого результата ГСЧ, основываясь на собственном просмотре asm, учитывая руководства Агнера Фога и другие ресурсы по оптимизации, на которые я добавил ссылки для в вики по тегам SO x86 .)

Вероятно, это будет значительно быстрее на Skylake , где векторное целочисленное умножение и сдвиг может выполняться на вдвое большем количестве портов (p0 / p1) по сравнению с Haswell (только p0). xorshift и извлечение цифр используют много сдвигов и умножений. ( Обновление: Skylake запускает его со скоростью 3.02 IPC, что дает нам 3,77 цикла на 32-байтовое хранилище AVX2 , рассчитанное на 0,030 секунды на итерацию 1 ГБ, запись в / dev / null в Linux 4.15 на i7-6700k на частоте 3,9 ГГц.

Для нормальной работы не требуется 64-разрядный режим . Версия SSE2 работает так же быстро при компиляции с помощью -m32 , потому что это не так. Требуется очень много векторных регистров, и вся 64-битная математика выполняется в векторах, а не в регистрах общего назначения.

На самом деле это немного быстрее в 32-битном режиме на Core2, потому что макро-слияние сравнения / ветвления работает только в 32-битный режим, поэтому для ядра, вышедшего из строя, сокращается число операций (18,3 с (1,85 инструкций на такт) по сравнению с 16,9 с (2,0 IPC)). Меньший размер кода из-за отсутствия префиксов REX также помогает Core2 декодеры.

Кроме того, некоторые перемещения вектора reg-reg заменены загрузками, поскольку не все константы больше фиксируются в векторных регистрах. Поскольку пропускная способность загрузки из кеша L1 не является узким местом, это действительно помогает (например,умножение на постоянный вектор set1 (10) : movdqa xmm0, xmm10 / pmullw xmm0, xmm1 превращается в movdqa xmm0, [constant] / pmullw xmm0, xmm1 .) Поскольку reg-reg MOVDQA требует порта ALU, он конкурирует с реальной выполняемой работой, но загрузка MOVDQA конкурирует только за пропускную способность внешнего декодирования. (Наличие 4-байтового адреса внутри многих инструкций сводит на нет большую часть выгоды от сохранения префиксов REX.

Я не удивлюсь, если сохранение мопов ALU MOVDQA - это то, откуда исходит реальная выгода, поскольку интерфейс должен быть достаточно хорошо справляется со средним показателем IPC 2.0.

Все эти различия исчезают в Haswell, где все это должно запускаться из кэша декодированного uop, если не из буфера обратной связи. ALU + branch macro-fusion работает в обоих режимах начиная с Нехалема.

21
27.01.2020, 19:33

Если у вас есть shuf (в последних версиях GNU coreutils), вы можете сделать следующее:

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

На моей VM это немного медленнее, чем ответ Стефана, примерно в соотношении 3:4.

23
27.01.2020, 19:33 
#!/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
1
27.01.2020, 19:33

Это зависит от вашего определения слова «случайный». Если вы имеете в виду криптографически случайный, вам просто нужно получить хорошую библиотеку и укусить пулю, подождать, пока она запустится.

Если вам просто нужно что-то, что выглядит довольно случайным, вот простой способ:

  1. Получите файл размером в несколько гигабайт. Ваш любимый фильм будет хорош.
  2. Gzip it, простой способ выжать повторяющиеся шаблоны
  3. Просматривать файл по полубайту (полбайта) за раз. Каждое значение будет от 0 до 15. Выбросьте все, что меньше 1 или больше 10. Вычтите 1 из каждого первого миллиарда выживших и запишите его цифрой.

Запуск на медленной машине может занять час; достаточно быстро и случайным образом для большинства целей.

1
27.01.2020, 19:33

Теги

Похожие вопросы