Как я могу ускорить построчное чтение файла ASCII?(C ++) - PullRequest
Новая
       49

Как я могу ускорить построчное чтение файла ASCII?(C ++)

11 голосов
/ 02 марта 2011

Вот фрагмент кода, который является существенным узким местом после выполнения некоторых измерений: 

//-----------------------------------------------------------------------------
//  Construct dictionary hash set from dictionary file
//-----------------------------------------------------------------------------
void constructDictionary(unordered_set<string> &dict)
{
    ifstream wordListFile;
    wordListFile.open("dictionary.txt");

    std::string word;
    while( wordListFile >> word )
    {
        if( !word.empty() )
        {
            dict.insert(word);
        }
    }

    wordListFile.close();
}

Я читаю ~ 200 000 слов, и на моем компьютере это занимает около 240 мс.Эффективно ли использование ifstream здесь?Могу ли я сделать лучше?Я читаю о mmap() реализациях, но я не понимаю их на 100%.Входной файл представляет собой просто текстовые строки с * nix окончаниями строки.

РЕДАКТИРОВАТЬ: дополнительный вопрос для предлагаемых альтернатив: любая альтернатива (минус увеличениеРазмеры буфера потока) подразумевают, что я пишу парсер, который проверяет каждый символ на наличие новых строк?Мне нравится простой синтаксис потоков, но я могу переписать что-то более мелкое, если мне нужно для скорости.Чтение всего файла в память является жизнеспособным вариантом, это всего лишь около 2 МБ.

РЕДАКТИРОВАНИЕ № 2: Я обнаружил, что замедление для меня было связано с установленной вставкой,но для тех, кто все еще заинтересован в ускорении построчного ввода-вывода файла, прочитайте ответы здесь И ознакомьтесь с продолжением Матье М. по теме.

Ответы [ 9 ]

8 голосов
/ 02 марта 2011

Быстрое профилирование в моей системе (linux-2.6.37, gcc-4.5.2, скомпилировано с -O3) показывает, что ввод-вывод не является узким местом.Используете ли вы fscanf в массиве символов, а затем dict.insert () или operator>>, как в вашем точном коде, это занимает примерно одно и то же время (155 - 160 мсек, чтобы прочитать файл из 240 тыс. Слов).

Замена std::unordered_set gcc на std::vector<std::string> в вашем коде сокращает время выполнения до 45 мс (fscanf) - 55 мс (operator>>) для меня.Попробуйте профилировать IO и установить вставку отдельно.

4 голосов
/ 02 марта 2011

Как правило, можно повысить производительность, увеличив размер буфера.

Сразу после построения ifstream вы можете установить его внутренний буфер, используя: 

char LocalBuffer[4096]; // buffer

std::ifstream wordListFile("dictionary.txt");

wordListFile.rdbuf()->pubsetbuf(LocalBuffer, 4096);

Примечание: результат rdbuf гарантированно не будет нулевым, если построение ifstream завершилось успешно

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

Я выполнил несколько простых измерений, используя небольшой собственный тест, вы можете найти код ниже (и меня интересуют критики):

gcc 3.4.2 на SLES 10 (sp 3)
C : 9.52725e + 06
C ++ : 1.11238e + 07
Разница: 1,59655e + 06

Что дает замедление крика 17% .

Это учитывает:

  • автоматическое управление памятью (без переполнения буфера)
  • автоматическое управление ресурсами (без риска длязакрыть файл)
  • обработка locale

Итак, мы можем утверждать, что потоки медленные ... но, пожалуйста, не бросайте свой случайный кусок кодаи жалуется, что это медленно, оптимизация - тяжелая работа.

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

#include <fstream>
#include <iostream>
#include <iomanip>

#include <cmath>
#include <cstdio>

#include "benchmark.h"

struct CRead
{
  CRead(char const* filename): _filename(filename) {}

  void operator()()
  {
    FILE* file = fopen(_filename, "r");

    int count = 0;
    while ( fscanf(file,"%s", _buffer) == 1 ) { ++count; }

    fclose(file);
  }

  char const* _filename;
  char _buffer[1024];
};

struct CppRead
{
  CppRead(char const* filename): _filename(filename), _buffer() {}

  enum { BufferSize = 16184 };

  void operator()()
  {
    std::ifstream file(_filename);
    file.rdbuf()->pubsetbuf(_buffer, BufferSize);

    int count = 0;
    std::string s;
    while ( file >> s ) { ++count; }
  }

  char const* _filename;
  char _buffer[BufferSize];
};


int main(int argc, char* argv[])
{
  size_t iterations = 1;
  if (argc > 1) { iterations = atoi(argv[1]); }

  char const* filename = "largefile.txt";

  CRead cread(filename);
  CppRead cppread(filename);

  double ctime = benchmark(cread, iterations);
  double cpptime = benchmark(cppread, iterations);

  std::cout << "C  : " << ctime << "\n"
               "C++: " << cpptime << "\n";

  return 0;
}
2 голосов
/ 10 октября 2013

Моя система (3.2.0-52-generic, g ++ - 4.7 (Ubuntu / Linaro 4.7.3-2ubuntu1 ~ 12.04) 4.7.3, скомпилировано с -O2 , если не указано, CPU: i3 -2125)

В моих тестовых случаях я использовал словарь 295068 слов (так что слов на 100 000 больше, чем в вашем): http://dl.dropboxusercontent.com/u/4076606/words.txt

С точки зрения сложности времени:

  • В худшем случае сложность вашей программы: O (n * n) = O (n [читать данные] * n [вставить в unordered_set])
  • Среднее значение сложности вашей программы: O (n) = O (n [читать данные] * 1 [вставить в unordered_set])

Практические советы:

  • В большинстве простых структур данных меньше затрат времени. Простой массив быстрее, чем вектор. массив символов быстрее строки. В Интернете много информации об этом.

Мои измерения:

Примечание: я не очищал кэш ОС и кеш жесткого диска. Последнее, что я не могу контролировать, но первым можно управлять с помощью: 

sync; sudo sh -c 'echo 3 > /proc/sys/vm/drop_caches'

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

Мой код:

14–16 мс для чтения из файла и вставки данных в массив символов 2D (чтение и вставка) n раз

65-75 мс для поиска с помощью двоичный поиск все слова ( поиск n раз ):

Всего = 79-91 мс

61-78 мс для чтения из файла и вставки данных в массив символов unordered_set (чтение и вставка) n раз

7-9 мс до поиск по хэшу n раз

Всего = 68-87 мс

Если вы выполняете поиск больше раз, чем вставляете, выберите хэш-таблицу (unordered_set), в противном случае бинарный поиск (с простым массивом).

Ваш оригинальный код (поиск и вставка):

Скомпилировано с -O2: 157-182 мс

Скомпилировано с -O0 (если вы опустите флаг -O, уровень "-O" по умолчанию также равен 0): 223-248 мс

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

Что вы можете сделать проще всего, но лучше с вашим текущим кодом?

  1. [лучшее использование API высокого уровня] Используйте «getline (wordListFile, word)» вместо «wordListFile >> word». Также я думаю, что "getline" более читабелен, чем оператор ">>".

Скомпилировано с -O2: 142-170 мс. Увеличение скорости ~ 12-15 мс по сравнению с исходным кодом.

Скомпилировано с -O0 (если вы опустите флаг -O, уровень "-O" по умолчанию также равен 0): 213-235 мс. ~ 10-13 мс ускорения по сравнению с исходным кодом.

  1. [лучшее использование API высокого уровня] Избегайте перефразирования с помощью «dict.reserve (XXXXXX);», @David Rodríguez - dribeas также упоминал об этом. Если ваш словарь статический или вы можете угадать его размер словаря (например, по размеру файла, деленному на среднюю длину слова) Сначала запустите без «резерва» и выведите bucket_count (cout << «bucket_count =» << dict.bucket_count () << «\ n»;), в моем случае это 299951. Затем я добавил «dict.reserve (299951) ;.»</li>

Скомпилировано с -O2: 99-121- [137] мс. ~ 33-43- [49] мс ускорение скорости по сравнению с исходным кодом.

Что вы можете сделать более продвинутым, чтобы ускорить его?

Реализуйте свою собственную хеш-функцию для вашего конкретного ввода данных. Используйте массив символов вместо строки STL. После того, как вы это сделали, только потом пишите код с прямым вводом-выводом ОС. Как вы заметили (из моих измерений также видно), что структура данных является узким местом. Если носитель очень медленный, но процессор очень быстрый, сожмите файл, распакуйте его в вашей программе.

Мой код не идеален, но все же он лучше, чем что-либо, что можно увидеть выше: http://pastebin.com/gQdkmqt8 (хеш-функция из Интернета, также может быть лучше)

Не могли бы вы предоставить более подробную информацию о том, какую систему (одну или диапазон) вы планируете оптимизировать?

Информация о сложности времени: Должны быть ссылки ... Но у меня не так много репутации, как у меняЯ новичок в stackoverflow.

Мой ответ по-прежнему имеет отношение к чему-либо?Пожалуйста, добавьте комментарий или голосуйте, поскольку я не вижу PM, как я вижу.

2 голосов
/ 02 марта 2011

Библиотеки C ++ и C одинаково быстро считывают данные с диска и уже буферизируются для компенсации задержки дискового ввода-вывода. Вы не собираетесь делать это быстрее, добавляя больше буферизации.

Самым большим отличием является то, что потоки C ++ выполняют множество манипуляций в зависимости от локали. Преобразования символов / Знаки препинания и т. Д. / И т. Д.

В результате библиотеки C будут работать быстрее.

Заменена мертвая ссылка

По какой-то причине связанный вопрос был удален. Поэтому я перемещаю соответствующую информацию здесь. Связанный вопрос был о скрытых возможностях в C ++.

Хотя технически не является частью STL.
Библиотека потоков является частью стандартной библиотеки C ++.

Для потоков:

Локализация.

Очень немногие люди действительно пытаются узнать, как правильно устанавливать и / или манипулировать языковым стандартом потока.

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

Примеры:

  • Знаете ли вы, что локали изменят '.' в десятичном числе на любой другой символ автоматически.
  • Знаете ли вы, что локали будут добавлять ',' каждую третью цифру, чтобы ее было легче читать.
  • Знаете ли вы, что локали можно использовать для манипулирования текстом на пути (например, преобразование из UTF-16 в UTF-8 (при записи в файл).

и т.д.

Примеры:

2 голосов
/ 02 марта 2011

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

Действительно ли проблема в 0,25 с?Если вы не собираетесь загружать гораздо большие файлы, есть ли необходимость сделать это быстрее, если это сделает его менее читабельным?

1 голос
/ 02 марта 2011

Правильная реализация библиотеки IO позволит вам кэшировать данные, избегая чрезмерного доступа к диску и системных вызовов.Я рекомендую вам использовать инструмент уровня системных вызовов (например, strace, если вы работаете под Linux), чтобы проверить, что на самом деле происходит с вашим IO.

Очевидно, что dict.insert(xxx) также может быть неудобством, если оно не 't разрешить вставку O (1).

0 голосов
/ 02 марта 2011

Если вы действительно хотите быстро, вычеркните istream и string и создайте тривиальный класс Read_Only_Text вокруг const char* & size, затем сопоставьте файл памяти и вставьте его в unordered_set<Read_Only_Text> со ссылками на встроенные строки. Это будет означать, что вам не нужно хранить файл 2 Мб, даже если количество уникальных ключей может быть намного меньше, но заполнение будет очень и очень быстрым. Я знаю, что это боль, но я делал это несколько раз для различных задач, и результаты очень хорошие.

0 голосов
/ 02 марта 2011

К сожалению, вы мало что можете сделать, чтобы повысить производительность при использовании fstream.

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

Единственный способ добиться значительных улучшений - это использовать функции ввода-вывода вашей ОС.Например, в Windows открытие файла с флагом FILE_FLAG_SEQUENTIAL_SCAN может ускорить чтение, а также использовать асинхронное чтение для получения данных с диска и их параллельного анализа.

0 голосов
/ 02 марта 2011

Верьте или нет, производительность потока stdlib при чтении данных намного ниже, чем в подпрограммах библиотеки C. Если вам нужна максимальная производительность чтения ввода-вывода, не используйте потоки c ++. Я обнаружил, что это сложный путь на сайтах, где конкурируют алгоритмы - мой код будет превышать время ожидания теста, используя потоки c ++ для чтения stdin, но завершится через много времени, используя простые операции C FILE.

Редактировать: просто попробуйте эти две программы на некоторых данных образца. Я запустил их на Mac OS X 10.6.6, используя g ++ i686-apple-darwin10-g ++ - 4.2.1 (GCC) 4.2.1 (сборка Apple Inc., сборка 5664) для файла с 1 миллионом строк «howdythere», и Версия scanf работает в 5 раз быстрее, чем версия cin: 

#include <stdio.h>

int main()
{
    int count = 0;
    char buf[1024];
    while ( scanf("%s", buf) == 1 )
        ++ count;

    printf( "%d lines\n", count );
}

и 

#include <iostream>

int main()
{
    char buf[1024];
    int count = 0;

    while ( ! std::cin.eof() )
    {
        std::cin.getline( buf, 1023 );
        if ( ! std::cin.eof() )
            ++count;
    }
   std::cout << count << " lines" << std::endl;
}

Редактировать: изменил файл данных на «как», чтобы устранить разницу между двумя случаями. Сроки результатов не изменились.

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

...