Как читать и анализировать текстовый файл с числами, быстро (в C)?

Ответ 1

Некоторые предложения:

a) Рассмотрим преобразование (или предварительную обработку) файла в двоичный формат; с тем чтобы свести к минимуму размер файла, а также резко снизить стоимость разбора. Я не знаю диапазоны для ваших значений, но различные методы (например, используя один бит, чтобы определить, является ли число маленьким или большим, и сохранение числа в виде либо 7-битного целого числа, либо 31-битного целого) может уменьшить вдвое файл IO (и удваивает скорость чтения файла с диска) и сокращает затраты на разборку до почти ничего. Примечание. Для максимального эффекта вы должны изменить любое программное обеспечение, созданное в первую очередь.

b) Чтение всего файла в памяти перед его анализом является ошибкой. Он удваивает объем требуемой ОЗУ (и затраты на выделение/освобождение) и имеет недостатки для кэшей CPU. Вместо этого прочитайте небольшую часть файла (например, 16 KiB) и обработайте его, затем прочитайте следующий фрагмент и обработайте его и так далее; так что вы постоянно используете одну и ту же небольшую буферную память.

c) Используйте parallelism для файла IO. Нетрудно прочитать следующий фрагмент файла, когда вы обрабатываете предыдущий фрагмент файла (либо с помощью двух потоков, либо с помощью асинхронного ввода-вывода).

d) Предварительно выделите память для "соседних" структур и удалите вызовы из всех/всех malloc() из вашего цикла. Наилучшим случаем является использование статически выделенного массива в качестве пула - например, Neighbor myPool[MAX_NEIGHBORS];, где malloc() можно заменить на &myPool[nextEntry++];. Это уменьшает/устраняет накладные расходы malloc(), а также улучшает локальность кэша для самих данных.

e) Используйте parallelism для сохранения значений. Например, у вас может быть несколько потоков, в которых первый поток обрабатывает все случаи, когда root_level % NUM_THREADS == 0, второй поток обрабатывает все случаи, когда root_level % NUM_THREADS == 1 и т.д.

Со всем вышесказанным (предполагая современный 4-ядерный процессор), я думаю, вы можете получить общее время (для чтения и хранения) до менее 15 секунд.

Ответ 2

Мое предложение состояло в том, чтобы сформировать конвейер обработки и потопить его. Чтение файла - это связанная с вводом-выводом задача, и синтаксический анализ связан с ЦП. Они могут выполняться одновременно параллельно.

Ответ 3

Существует несколько возможностей. Вам придется экспериментировать.

• Используйте то, что дает вам ОС. Если Windows, проверьте overlapped io. Это позволяет проводить вычисления при анализе одного буфера, заполненного данными, в то время как ядро ​​Windows заполняет другое. Затем переключите буферы и продолжайте. Это связано с тем, что предложил @Neal, но имеет меньше накладных расходов для буферизации. Windows вводит данные непосредственно в буфер через канал DMA. Нет копирования. Если Linux, проверьте файлы с отображением памяти. Здесь ОС использует аппаратное обеспечение виртуальной памяти, чтобы делать больше или меньше того, что делает Windows с перекрытием.

• Введите собственное целочисленное преобразование. Вероятно, это будет немного быстрее, чем создание клинового вызова на целое число.

Вот пример кода. Вы хотите полностью ограничить количество сравнений.

// Process one input buffer.
*end_buf = ' '; // add a sentinel at the end of the buffer
for (char *p = buf; p < end_buf; p++) {
  // somewhat unsafe (but fast) reliance on unsigned wrapping
  unsigned val = *p - '0';
  if (val <= 9) {
    // Found start of integer.
    for (;;) {
      unsigned digit_val = *p - '0';
      if (digit_val > 9) break;
      val = 10 * val + digit_val;
      p++;
    }
    ... do something with val
  }
}

• Не называть malloc один раз за запись. Вы должны выделять блоки из нескольких структур за раз.

• Экспериментируйте с размерами буфера.

• Оптимизация компилятора. Это тот код, который сильно выигрывает от превосходного генерации кода.

Ответ 4

Да, стандартные функции преобразования библиотеки удивительно медленны.

Если переносимость не является проблемой, я бы сохранил карту памяти. Затем для анализа всей карты памяти можно использовать код C99 (непроверенный):

#include <stdlib.h>
#include <errno.h>

struct pair {
    unsigned long  key;
    unsigned long  value;
};

typedef struct {
    size_t       size; /* Maximum number of items */
    size_t       used; /* Number of items used */
    struct pair  item[];
} items;

/* Initial number of items to allocate for */
#ifndef ITEM_ALLOC_SIZE
#define ITEM_ALLOC_SIZE 8388608
#endif

/* Adjustment to new size (parameter is old number of items) */
#ifndef ITEM_REALLOC_SIZE
#define ITEM_REALLOC_SIZE(from) (((from) | 1048575) + 1048577)
#endif 

items *parse_items(const void *const data, const size_t length)
{
    const unsigned char       *ptr = (const unsigned char *)data;
    const unsigned char *const end = (const unsigned char *)data + length;
    items                  *result;
    size_t                  size = ITEMS_ALLOC_SIZE;
    size_t                  used = 0;
    unsigned long           val1, val2;

    result = malloc(sizeof (items) + size * sizeof (struct pair));
    if (!result) {
        errno = ENOMEM;
        return NULL;
    }

    while (ptr < end) {

        /* Skip newlines and whitespace. */
        while (ptr < end && (*ptr == '\0' || *ptr == '\t' ||
                             *ptr == '\n' || *ptr == '\v' ||
                             *ptr == '\f' || *ptr == '\r' ||
                             *ptr == ' '))
            ptr++;

        /* End of data? */
        if (ptr >= end)
            break;

        /* Parse first number. */
        if (*ptr >= '0' && *ptr <= '9')
            val1 = *(ptr++) - '0';
        else {
            free(result);
            errno = ECOMM; /* Bad data! */
            return NULL;
        }
        while (ptr < end && *ptr >= '0' && *ptr <= '9') {
            const unsigned long old = val1;
            val1 = 10UL * val1 + (*(ptr++) - '0');
            if (val1 < old) {
                free(result);
                errno = EDOM; /* Overflow! */
                return NULL;
            }
        }

        /* Skip whitespace. */
        while (ptr < end && (*ptr == '\t' || *ptr == '\v'
                             *ptr == '\f' || *ptr == ' '))
            ptr++;
        if (ptr >= end) {
            free(result);
            errno = ECOMM; /* Bad data! */
            return NULL;
        }

        /* Parse second number. */
        if (*ptr >= '0' && *ptr <= '9')
            val2 = *(ptr++) - '0';
        else {
            free(result);
            errno = ECOMM; /* Bad data! */
            return NULL;
        }
        while (ptr < end && *ptr >= '0' && *ptr <= '9') {
            const unsigned long old = val2;
            val1 = 10UL * val2 + (*(ptr++) - '0');
            if (val2 < old) {
                free(result);
                errno = EDOM; /* Overflow! */
                return NULL;
            }
        }
        if (ptr < end) {
            /* Error unless whitespace or newline. */
            if (*ptr != '\0' && *ptr != '\t' && *ptr != '\n' &&
                *ptr != '\v' && *ptr != '\f' && *ptr != '\r' &&
                *ptr != ' ') {
                free(result);
                errno = ECOMM; /* Bad data! */
                return NULL;
            }

            /* Skip the rest of this line. */
            while (ptr < end && *ptr != '\n' && *ptr != '\r')
                ptr++;
        }

        /* Need to grow result? */
        if (used >= size) {
            items *const old = result;

            size = ITEMS_REALLOC_SIZE(used);
            result = realloc(result, sizeof (items) + size * sizeof (struct pair));
            if (!result) {
                free(old);
                errno = ENOMEM;
                return NULL;
            }
        }

        result->items[used].key = val1;
        result->items[used].value = val2;
        used++;
    }

    /* Note: we could reallocate result here,
     *       if memory use is an issue.
    */

    result->size = size;
    result->used = used;

    errno = 0;
    return result;
}

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

По крайней мере, ядро ​​Linux хорошо разбирается в шаблонах доступа к памяти/файлу; использование madvise() также помогает.

Если вы не можете использовать карту памяти, то функция разбора будет немного другой: она добавит к существующему результату, и если конечная строка в буфере будет частичной, это будет указывать так (и количество символов не анализируется), так что вызывающий может memmove() буфера, читать больше данных и продолжать синтаксический анализ. (Используйте 16-байтовые выровненные адреса для чтения новых данных, чтобы увеличить скорость копирования. Вам необязательно перемещать непрочитанные данные в точное начало буфера, как видите, просто сохраняйте текущую позицию в буферизованных данных.)

Вопросы?

Ответ 5

Во-первых, что ваше дисковое оборудование? Один диск SATA, вероятно, будет превышен со скоростью 100 МБ/с. И, вероятно, больше 50-70 МБ/с. Если вы уже перемещаете данные с диска (ов) так быстро, как можете, вся настройка программного обеспечения, которую вы делаете, будет потрачена впустую.

Если ваше аппаратное обеспечение CAN поддерживает чтение быстрее? Во-первых, ваш шаблон чтения - один раз прочитайте весь файл в памяти - это идеальный вариант использования для прямого ввода-вывода. Откройте файл open( "/file/name", O_RDONLY | O_DIRECT );. Прочитайте буферы с выравниванием по страницам (см. Справочную страницу для valloc()) в блоках размера страницы. Использование прямого ввода-вывода приведет к тому, что ваши данные обходят двойную буферизацию в кеше страницы ядра, что бесполезно, когда вы читаете много данных, которые быстро и не перечитывают одни и те же страницы данных снова и снова.

Если вы используете настоящую высокопроизводительную файловую систему, вы можете читать асинхронно и, скорее всего, быстрее с помощью lio_listio() или aio_read(). Или вы можете просто использовать несколько потоков для чтения и использовать pread(), чтобы у вас не было времени на поиск времени, а потому, что, когда вы читаете несколько потоков, поиск в открытом файле влияет на все потоки, пытающиеся прочитать из файла.

И сделайте не попытку быстрого чтения в новом блоке памяти malloc'd - memset(). Поскольку действительно быстрые дисковые системы могут накачивать данные в ЦП быстрее, чем менеджер виртуальной памяти может создавать виртуальные страницы для процесса.