Как я могу ускорить построчное чтение файла ASCII? (C++)
Вот немного кода, который является существенным узким местом после некоторого измерения:
//-----------------------------------------------------------------------------
// 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();
}
Я читаю ~200000 слов, и это занимает около 240 мс на моей машине. Является ли использование ifstream здесь эффективно? Могу ли я сделать лучше? Я читаю о mmap() реализации, но я не понимаю их на 100%. Входной файл - это просто текстовые строки с окончанием строки * nix.
РЕДАКТИРОВАТЬ: дополнительный вопрос для предлагаемых альтернатив: будет ли любая альтернатива (за исключением увеличения размера буфера потока) подразумевать, что я напишу парсер, который проверяет каждый символ на наличие новых строк? Мне нравится простой синтаксис потоков, но я могу переписать что-то более мелкое, если мне нужно для скорости. Чтение всего файла в память является жизнеспособным вариантом, это всего лишь около 2 МБ.
РЕДАКТИРОВАТЬ #2: Я обнаружил, что замедление для меня было связано с набором вставки, но для тех, кто все еще заинтересован в ускорении построчно файла ввода / вывода, пожалуйста, прочитайте ответы здесь И проверьте Матье М. продолжение по теме.
9 ответов
Быстрое профилирование в моей системе (linux-2.6.37, gcc-4.5.2, скомпилировано с -O3) показывает, что ввод-вывод не является узким местом. Используете ли fscanf в массив символов с последующим dict.insert () или operator>> как и в вашем точном коде, это занимает примерно столько же времени (155 - 160 мсек, чтобы прочитать файл из 240 тыс. слов).
Замена GCC std::unordered_set с std::vector<std::string> в вашем коде падает время выполнения до 45 мс (fscanf) - 55 мс (operator>>) для меня. Попробуйте профилировать IO и установить вставку отдельно.
Как правило, вы можете повысить производительность, увеличив размер буфера.
Сразу после строительства 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;
}
Библиотеки C++ и C одинаково быстро считывают данные с диска и уже буферизируются для компенсации задержки дискового ввода-вывода. Вы не собираетесь делать это быстрее, добавляя больше буферизации.
Самым большим отличием является то, что потоки C++ выполняют множество манипуляций в зависимости от локали. Преобразование символов / Пунктуальный и т. Д. / И т. Д.
В результате библиотеки C будут быстрее.
Замененная мертвая ссылка
По какой-то причине связанный вопрос был удален. Поэтому я перемещаю соответствующую информацию здесь. Связанный вопрос был о скрытых возможностях в C++.
Хотя не технически часть STL.
Библиотека потоков является частью стандартной библиотеки C++.
Для потоков:
Локализации.
Очень немногие люди действительно пытаются научиться правильно устанавливать и / или манипулировать языковым стандартом потока.
Вторая крутая вещь - шаблоны итераторов.
Наиболее конкретно для меня это потоковые итераторы, которые в основном превращают потоки в очень простые контейнеры, которые затем могут использоваться вместе со стандартными алгоритмами.
Примеры:
- Знаете ли вы, что локали изменят "." в десятичном числе на любой другой символ автоматически.
- Знаете ли вы, что локали будут добавлять ',' каждую третью цифру, чтобы ее было легче читать.
- Знаете ли вы, что локали могут быть использованы для манипулирования текстом на пути (например, преобразование из UTF-16 в UTF-8 (при записи в файл).
и т.п.
Примеры:
- Добавление запятой для каждых трех цифр
- Используя пространство в качестве разделителя
- Установите десятичный разделитель
- Простой выходной фильтр
- Установить текущую локаль
- Подсчитать количество символов, отправленных на вывод
- Сделать отступ для каждой строки
- UTF-16 (поток) -> UTF-16 (внутренний) преобразователь (не проверено)
Моя система (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])
Практические советы:
- У самой простой структуры данных меньше затрат времени. Простой массив быстрее, чем вектор. массив char быстрее строки В Интернете есть много информации об этом.
Мои измерения:
Обратите внимание: я не очищал кэш ОС и кеш жесткого диска. Последнее, что я не могу контролировать, но первым можно управлять с помощью:
sync; sudo sh -c 'echo 3 > /proc/sys/vm/drop_caches'
Также я не пропустил те измерения, которые включали много переключений контекста и так далее. Таким образом, есть место для более качественных измерений.
Мой код:
14–16 мс для чтения из файла и вставки данных в двумерный массив символов (чтение и вставка) 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 мс. Вы не указали ни один из них. Так что, я думаю, ты не использовал это. Как я пытаюсь ответить на ваш главный вопрос.
Что вы можете сделать проще всего, но лучше с вашим текущим кодом?
- [лучшее использование API высокого уровня] Используйте "getline(wordListFile, word)" вместо "wordListFile >> word". Также я думаю, что "getline" более читабелен, чем оператор ">>".
Составлено с -O2: 142-170 мс. Повышение скорости ~ 12-15 мс по сравнению с исходным кодом.
Скомпилировано с -O0 (если вы опустите флаг -O, уровень "-O" по умолчанию также равен 0): 213-235 мс. Повышение скорости ~ 10-13 мс по сравнению с исходным кодом.
- [лучшее использование API высокого уровня] Избегайте перефразирования с помощью "dict.reserve(XXXXXX);", @David Rodríguez - dribeas также упоминал об этом. Если ваш словарь статичен или вы можете угадать его размер словаря (например, по размеру файла, деленному на среднюю длину слова). Сначала запустите без "резерва" и выведите bucket_count (cout << "bucket_count = " << dict.bucket_count() << "\n";), в моем случае это 299951. Затем я добавил "dict.reserve(299951);".
Составлено с -O2: 99-121- [137] мс. ~ 33-43- [49] мс увеличение скорости по сравнению с исходным кодом.
Что вы можете сделать более продвинутым, чтобы ускорить его?
Реализуйте свою собственную хеш-функцию для вашего конкретного ввода данных. Используйте массив символов вместо строки STL. После того, как вы это сделали, только потом пишите код с прямым вводом-выводом ОС. Как вы заметили (из моих измерений также видно), что структура данных является узким местом. Если носитель очень медленный, но процессор очень быстрый, сожмите файл, распакуйте его в своей программе.
Мой код не идеален, но все же он лучше, чем все, что можно увидеть выше: http://pastebin.com/gQdkmqt8 (хеш-функция из Интернета, также может быть лучше)
Не могли бы вы предоставить более подробную информацию о том, какую систему (одну или диапазон) вы планируете оптимизировать?
Информация о сложности времени: Должны быть ссылки... Но у меня не так много репутации, как новичка в stackru.
Мой ответ по-прежнему имеет отношение к чему-либо? Пожалуйста, добавьте комментарий или проголосуйте, поскольку я не вижу PM, как я вижу.
Считывание всего файла за один раз в памяти и последующая работа с ним, вероятно, будут быстрее, так как это позволит избежать повторного обращения к диску для чтения другого фрагмента.
Является ли 0.25s на самом деле проблемой? Если вы не собираетесь загружать гораздо большие файлы, есть ли необходимость сделать это быстрее, если это сделает его менее читабельным?
Правильная реализация библиотеки ввода-вывода позволит вам кешировать данные, избегая чрезмерного доступа к диску и системных вызовов. Я рекомендую вам использовать инструмент уровня системных вызовов (например, strace, если вы работаете под Linux), чтобы проверить, что на самом деле происходит с вашим IO.
Очевидно, что dict.insert(xxx) также может быть неприятным, если он не допускает вставку O(1).
Если вы действительно хотите быстро, вычеркните istream и string и создайте тривиальный класс Read_Only_Text вокруг const char* & size, затем карту памяти файла и вставьте в unordered_set<Read_Only_Text> со ссылками на встроенные строки. Это будет означать, что вам не нужно хранить файл 2 Мб, даже если количество уникальных ключей может быть намного меньше, но заполнение будет очень и очень быстрым. Я знаю, что это боль, но я делал это несколько раз для различных задач, и результаты очень хорошие.
Верьте или нет, производительность потока stdlib при чтении данных намного ниже, чем в подпрограммах библиотеки C. Если вам нужна максимальная производительность чтения ввода-вывода, не используйте потоки C++. Я обнаружил, что это сложный путь на сайтах, где конкурируют алгоритмы - мой код будет превышать время ожидания теста, используя потоки C++ для чтения стандартного ввода, но завершится через много времени, используя простые операции 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, так и в потоках может быть таким разным. Перед тем как понизить голос: иди измерь это сам. Суть не в том, чтобы установить тонны состояния (которые обычно никто не устанавливает), а просто в коде, который люди чаще всего пишут. Мнение ничего не значит в производительности: мера, мера, мера это все, что имеет значение.
К сожалению, вы мало что можете сделать, чтобы повысить производительность при использовании fstream.
Вы можете получить очень небольшое улучшение скорости, читая большие куски файла, а затем анализируя отдельные слова, но это зависит от того, как ваша реализация fstream выполняет буферизацию.
Единственный способ добиться значительных улучшений - это использовать функции ввода / вывода вашей операционной системы. Например, в Windows открытие файла с флагом FILE_FLAG_SEQUENTIAL_SCAN может ускорить чтение, а также использовать асинхронное чтение для получения данных с диска и их параллельного анализа.