Эффективное чтение очень большого текстового файла в переполнении стека
У меня очень большой текстовый файл (45 ГБ). Каждая строка текстового файла содержит два 64-разрядных целых числа без знака, разделенных пробелами, как показано ниже.
4624996948753406865 10214715013130414417
4305027007407867230 4569406367070518418
10817905656952544704 3697712211731468838
…
…
Я хочу прочитать файл и выполнить некоторые операции с числами.
Мой код на C ++:
void process_data(string str)
{
vector<string> arr;
boost::split(arr, str, boost::is_any_of(" \n"));
do_some_operation(arr);
}
int main()
{
unsigned long long int read_bytes = 45 * 1024 *1024;
const char* fname = "input.txt";
ifstream fin(fname, ios::in);
char* memblock;
while(!fin.eof())
{
memblock = new char[read_bytes];
fin.read(memblock, read_bytes);
string str(memblock);
process_data(str);
delete [] memblock;
}
return 0;
}
Я относительно новичок в C ++. Когда я запускаю этот код, я сталкиваюсь с этими проблемами.
-
Из-за чтения файла в байтах иногда последняя строка блока соответствует незаконченной строке в исходном файле («4624996948753406865 10214» вместо фактической строки «4624996948753406865 10214715013130414417» основного файла).
-
Этот код работает очень, очень медленно. Требуется около 6 сек для выполнения одного блока операций в 64-битной системе Intel Core i7 920 с 6 ГБ оперативной памяти. Существуют ли методы оптимизации, которые я могу использовать для улучшения времени выполнения?
-
Нужно ли включать «\ n» вместе с пустым символом в функцию повышения разбиения?
Я читал о файлах mmap в C ++, но я не уверен, что это правильный способ сделать это. Если да, пожалуйста, приложите несколько ссылок.
Решение
Я бы перепроектировал это, чтобы действовать в потоковом режиме, а не на блоке.
Более простой подход был бы:
std::ifstream ifs("input.txt");
std::vector<uint64_t> parsed(std::istream_iterator<uint64_t>(ifs), {});
Если вы знаете примерно, сколько значений ожидается, используя std::vector::reserve впереди может ускорить его дальше.
В качестве альтернативы вы можете использовать отображенный в памяти файл и перебирать последовательность символов.
- Как быстро проанализировать разделенные пробелами числа в C ++? показывает эти подходы с ориентирами для поплавков.
Обновить Я изменил вышеупомянутую программу для разбора uint32_tс в вектор.
При использовании образца входного файла 4,5 ГБ[1] программа запускается за 9 секунд[2]:
sehe@desktop:/tmp$ make -B && sudo chrt -f 99 /usr/bin/time -f "%E elapsed, %c context switches" ./test smaller.txt
g++ -std=c++0x -Wall -pedantic -g -O2 -march=native test.cpp -o test -lboost_system -lboost_iostreams -ltcmalloc
parse success
trailing unparsed: '
'
data.size(): 402653184
0:08.96 elapsed, 6 context switches
Конечно, он выделяет как минимум 402653184 * 4 * байт = 1,5 гибибайта. Так когда
Вы читаете файл размером 45 ГБ, вам понадобится около 15 ГБ ОЗУ, чтобы просто сохранить
вектор (при условии отсутствия фрагментации при перераспределении): 45GiB разбор
завершается за 10 минут 45 секунд:
make && sudo chrt -f 99 /usr/bin/time -f "%E elapsed, %c context switches" ./test 45gib_uint32s.txt
make: Nothing to be done for `all'.
tcmalloc: large alloc 17570324480 bytes == 0x2cb6000 @ 0x7ffe6b81dd9c 0x7ffe6b83dae9 0x401320 0x7ffe6af4cec5 0x40176f (nil)
Parse success
Trailing unparsed: 1 characters
Data.size(): 4026531840
Time taken by parsing: 644.64s
10:45.96 elapsed, 42 context switches
Для сравнения просто работает wc -l 45gib_uint32s.txt заняло ~ 12 минут (без планирования приоритетов в реальном времени, хотя). wc является невероятно быстро
Полный код, используемый для теста
#include <boost/spirit/include/qi.hpp>
#include <boost/iostreams/device/mapped_file.hpp>
#include <chrono>
namespace qi = boost::spirit::qi;
typedef std::vector<uint32_t> data_t;
using hrclock = std::chrono::high_resolution_clock;
int main(int argc, char** argv) {
if (argc<2) return 255;
data_t data;
data.reserve(4392580288); // for the 45 GiB file benchmark
// data.reserve(402653284); // for the 4.5 GiB file benchmark
boost::iostreams::mapped_file mmap(argv[1], boost::iostreams::mapped_file::readonly);
auto f = mmap.const_data();
auto l = f + mmap.size();
using namespace qi;
auto start_parse = hrclock::now();
bool ok = phrase_parse(f,l,int_parser<uint32_t, 10>() % eol, blank, data);
auto stop_time = hrclock::now();
if (ok)
std::cout << "Parse success\n";
else
std::cerr << "Parse failed at #" << std::distance(mmap.const_data(), f) << " around '" << std::string(f,f+50) << "'\n";
if (f!=l)
std::cerr << "Trailing unparsed: " << std::distance(f,l) << " characters\n";
std::cout << "Data.size(): " << data.size() << "\n";
std::cout << "Time taken by parsing: " << std::chrono::duration_cast<std::chrono::milliseconds>(stop_time-start_parse).count() / 1000.0 << "s\n";
}
[1] генерируется с od -t u4 /dev/urandom -A none -v -w4 | pv | dd bs=1M count=$((9*1024/2)) iflag=fullblock > smaller.txt
[2] очевидно, это было с файлом, кэшированным в буферном кеше на Linux — большой файл не имеет этого преимущества
Другие решения
Я могу только догадываться, что узкое место находится в:
string str(memblock);
-Потому что вы выделяете 45MB длинный сегмент в памяти.
Вы должны читать файл построчно, как описано здесь:
Чтобы профилировать вашу программу, вы можете напечатать clock () между каждой строкой, как описано в:
Вы можете отобразить файл в память, но это будет зависеть от платформы (для unix, который будет mmap в окнах CreateFileMapping / MapViewIntoFile); Тем не менее, если в 32-битной системе у вас могут возникнуть проблемы, если не осталось достаточно большого блока виртуальной памяти (в 64-битных системах такой проблемы не будет).
Предполагается, что отображение памяти выполняется быстрее, чем чтение блока данных с блока на диск.
В Linux, используя C <stdio.h> вместо потоков C ++ может помочь производительность (потому что потоки C ++ построены выше FILE-s). Вы могли бы использовать Readline (3) или же fgets (3) или же fscanf (3). Вы можете установить больший буфер (например, 64 КБ или 256 КБ), используя SetBuffer (3) и т.д … Но я думаю, что ваша (улучшенная) программа будет связана с вводом / выводом, а не с процессором.
Тогда вы могли бы поиграть с posix_fadvise (2)
Вы могли бы рассмотреть возможность использования отображения памяти ММАП (2) & madvise (2) (смотрите также m режим для Еореп (3)). Смотрите также Readahead (2)
Наконец, если ваш алгоритм это позволяет, вы можете csplit файлы разбиты на части и обрабатывают каждый из них в параллельных процессах.