Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / C++ Новый топик    Ответить
Топик располагается на нескольких страницах: 1 2 3 4 5      [все]
 как быстрее всего прочесть большой файл с числами, каждое с новой строки?  [new]
log_here
Member [заблокирован]

Откуда:
Сообщений: 331
Допустим, есть файл, состоящий из 100 000 000 000 чисел int, каждое число записано с новой строчки.
Надо последовательно его прочесть. Мне кажется, будет намного быстрее, если читать не число за числом, а сразу много чисел читать и загружать в локальный массив (вектор), проводя загрузку несколько раз.

Как можно это сделать?
Если есть ещё более быстрый способ -- ещё лучше.

я знаю, что можно использовать [code cpp] std::fstream[code],
но есть ли более быстрый способ?
28 ноя 15, 22:35    [18486457]     Ответить | Цитировать Сообщить модератору
 Re: как быстрее всего прочесть большой файл с числами, каждое с новой строки?  [new]
log_here
Member [заблокирован]

Откуда:
Сообщений: 331
И ещё вопрос: почему файл с
1024 * 1024 / sizeof(int)
числами занимает ощутимо больше, чем 1 МБ, даже если числа внутри файла ничем не разделены?
28 ноя 15, 22:39    [18486472]     Ответить | Цитировать Сообщить модератору
 Re: как быстрее всего прочесть большой файл с числами, каждое с новой строки?  [new]
White Owl
Member

Откуда:
Сообщений: 12362
log_here
Допустим, есть файл, состоящий из 100 000 000 000 чисел int, каждое число записано с новой строчки.
Надо последовательно его прочесть. Мне кажется, будет намного быстрее, если читать не число за числом, а сразу много чисел читать и загружать в локальный массив (вектор), проводя загрузку несколько раз.
Правильно, читаешь блок байтиков и расшифровываешь их из буфера в массив.

log_here
я знаю, что можно использовать [code cpp] std::fstream[code],
но есть ли более быстрый способ?
Самостоятельно написать аналог, но убрать из него все проверки на ошибки чтения и расшифровки, а потом молиться что ошибки не случаться.
29 ноя 15, 01:57    [18487101]     Ответить | Цитировать Сообщить модератору
 Re: как быстрее всего прочесть большой файл с числами, каждое с новой строки?  [new]
kolobok0
Member

Откуда:
Сообщений: 1937
log_here
...Как можно это сделать?...есть ли более быстрый способ?


тут очень важно знать - что хотите получить на выходе? Если например Вам нужно отсортировать их - то всё гораздо проще :)

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

удачи вам
(круглый)

ЗЫ
А что значит запись
1024 * 1024 / sizeof(int)
????

это типа
1 048 576 интов
или
1 048 576 разделить на размерность инта

????
29 ноя 15, 01:57    [18487103]     Ответить | Цитировать Сообщить модератору
 Re: как быстрее всего прочесть большой файл с числами, каждое с новой строки?  [new]
log_here
Member [заблокирован]

Откуда:
Сообщений: 331
kolobok0
тут очень важно знать - что хотите получить на выходе? Если например Вам нужно отсортировать их - то всё гораздо проще :)

Например, хочу прочесть и пересчитать какие-то особенные элементы (скажем, бОльшие, чем 100).

kolobok0
ЗЫ
А что значит запись
1024 * 1024 / sizeof(int)
????

1 048 576 разделить на размерность инта

????
вторая версия -- правильная.

Правильно, читаешь блок байтиков и расшифровываешь их из буфера в массив.

Ну так я и прошу простейший способ (код) того, как это сделать.
29 ноя 15, 02:40    [18487199]     Ответить | Цитировать Сообщить модератору
 Re: как быстрее всего прочесть большой файл с числами, каждое с новой строки?  [new]
kolobok0
Member

Откуда:
Сообщений: 1937
log_here
...прочесть и пересчитать какие-то особенные элементы (скажем, бОльшие, чем 100).

1 048 576 разделить на размерность инта

...как это сделать.


1) эту задачу необходимо сразу делать по ходу чтения(на это как бы намекает большие величины для хранения всего)..
2) а теперь переведите свой вопрос на русский:
...почему файл с (1 048 576 разделить на размерность инта) числами занимает ощутимо больше, чем 1 МБ, даже если числа внутри файла ничем не разделены?
в переводе вопроса, необходимо указать а) размерность инта б) тип числа в который пишется (1 048 576 разделить на размерность инта)
3) как это сделать =
цикл. в цикле чтение фрагмента файла, вычисление того чего нужно.
написать код, запостить сюда, Вам укажут на недочёты и в какую сторону двигаться дальше...
ну либо в раздел работа и нанимаете того, кто это сделает за бабки. но лучше самому...

удачи вам
(круглый)
29 ноя 15, 02:58    [18487222]     Ответить | Цитировать Сообщить модератору
 Re: как быстрее всего прочесть большой файл с числами, каждое с новой строки?  [new]
Dima T
Member

Откуда:
Сообщений: 13622
log_here
Если есть ещё более быстрый способ -- ещё лучше.

Есть: один поток читает блоками, второй обрабатывает. Т.к. самое узкое место тут чтение с диска, то оно должно быть непрерывным.
29 ноя 15, 14:04    [18487608]     Ответить | Цитировать Сообщить модератору
 Re: как быстрее всего прочесть большой файл с числами, каждое с новой строки?  [new]
Dimitry Sibiryakov
Member

Откуда:
Сообщений: 47373

Dima T
один поток читает блоками, второй обрабатывает.

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

Posted via ActualForum NNTP Server 1.5

29 ноя 15, 14:06    [18487615]     Ответить | Цитировать Сообщить модератору
 Re: как быстрее всего прочесть большой файл с числами, каждое с новой строки?  [new]
mayton
Member

Откуда: loopback
Сообщений: 40400
log_here, лучшее - враг хорошего.

Напиши макет который хоть как-то работает и опубликуй его в форуме. Далее
по обстановке неравнодушные энтузиасты предложат тебе решение по оптимизации.
29 ноя 15, 14:39    [18487687]     Ответить | Цитировать Сообщить модератору
 Re: как быстрее всего прочесть большой файл с числами, каждое с новой строки?  [new]
log_here
Member [заблокирован]

Откуда:
Сообщений: 331
mayton,

     void f(const std::string& file_name)
     {
	std::ifstream stream(file_name, std::ios::in);
           std::list<int> list;

	int x;
	while(stream >> x)
	{
                 list.push_back(x);
                 if (list.size() == 1000 * 1000 * 1000)
                 {
                        // что-то сделать с list
                        list.resize(0);
                 }
	}
            
            // и здесь обработать оставшийся list
 
	
	stream.close();
      }


Но, как я указывал, здесь элементы заходят по одному, а не пачкой, что гораздо медленнее.
29 ноя 15, 16:15    [18487887]     Ответить | Цитировать Сообщить модератору
 Re: как быстрее всего прочесть большой файл с числами, каждое с новой строки?  [new]
Dimitry Sibiryakov
Member

Откуда:
Сообщений: 47373

log_here
здесь элементы заходят по одному, а не пачкой, что гораздо медленнее.

Во-первых, увеличь ему буфер до 32-64к, как показано здесь:
http://en.cppreference.com/w/cpp/io/basic_streambuf/pubsetbuf
Во-вторых, избавься от набивания чисел в список, это медленная операция.

Posted via ActualForum NNTP Server 1.5

29 ноя 15, 16:26    [18487910]     Ответить | Цитировать Сообщить модератору
 Re: как быстрее всего прочесть большой файл с числами, каждое с новой строки?  [new]
log_here
Member [заблокирован]

Откуда:
Сообщений: 331
Dimitry Sibiryakov,

buf1 работает быстрее buf2 всего лишь в 2 раза, а не в 10, как я ожидал.

#include <fstream>
#include <iterator>
#include <string>
#include <vector>
#include <sstream>
#include <time.h>

void buf1()
{
	const clock_t begin_time = clock();
	
	std::vector<int> v(1000000);
	
	int cnt = -1;
	std::ifstream file;
	char buf[1024 * 64];
	
	file.rdbuf()->pubsetbuf(buf, sizeof buf);
	file.open("./input.txt");
	
	for (std::string line; getline(file, line);) {
		v[++cnt] = std::stoi(line);
	}
	
	std::cout << float( 1000 * (clock () - begin_time )) /  CLOCKS_PER_SEC << std::endl;
}

void buf2()
{
	const clock_t begin_time = clock();
	
	std::string file_name("./input.txt");
	
	std::ifstream stream(file_name, std::ios::in);
	std::list<int> list;

	
	std::vector<int> v(10000000);
	int idx = -1;

	int x;
	while(stream >> x)
	{
		v[++idx] =  x;
	}
	
	stream.close();
	
	std::cout << float( 1000 * (clock () - begin_time )) /  CLOCKS_PER_SEC << std::endl;
}

int main(int argc, _TCHAR* argv[])
{
	buf1();
	buf2();
	while (1);
	return 0;
}
29 ноя 15, 16:54    [18487977]     Ответить | Цитировать Сообщить модератору
 Re: как быстрее всего прочесть большой файл с числами, каждое с новой строки?  [new]
Dimitry Sibiryakov
Member

Откуда:
Сообщений: 47373

Избавься от getline.

Каков результат в мегабайтах в секунду?

Posted via ActualForum NNTP Server 1.5

29 ноя 15, 17:08    [18488009]     Ответить | Цитировать Сообщить модератору
 Re: как быстрее всего прочесть большой файл с числами, каждое с новой строки?  [new]
log_here
Member [заблокирован]

Откуда:
Сообщений: 331
Dimitry Sibiryakov,

как избавляться от getline?
   // вместо
   //for (std::string line; getline(file, line);) {
   //	v[++cnt] = std::stoi(line);
   //}

   // записал
   int x;
   while(file >> x)
   {
      v[++cnt] =  x;
   }


время только увеличилось.

про время: в файле input.txt 1 000 000 элементов, читается за 1.3 с и 2.6 с соответствунно.
29 ноя 15, 17:25    [18488072]     Ответить | Цитировать Сообщить модератору
 Re: как быстрее всего прочесть большой файл с числами, каждое с новой строки?  [new]
Dimitry Sibiryakov
Member

Откуда:
Сообщений: 47373

log_here
как избавляться от getline?

Используй массив char вместо string и file.getline.

Какую букву из "мегабайты в секунду" ты не понял?..

Posted via ActualForum NNTP Server 1.5

29 ноя 15, 17:30    [18488114]     Ответить | Цитировать Сообщить модератору
 Re: как быстрее всего прочесть большой файл с числами, каждое с новой строки?  [new]
log_here
Member [заблокирован]

Откуда:
Сообщений: 331
7.8 МБ / 1.3 c = 6 МБ/c и
7.8 МБ / 2.6 c = 3 МБ/c

сообветственно.

Dimitry Sibiryakov
Используй массив char вместо string и file.getline.

Не мог бы расписать?
29 ноя 15, 17:43    [18488191]     Ответить | Цитировать Сообщить модератору
 Re: как быстрее всего прочесть большой файл с числами, каждое с новой строки?  [new]
Dima T
Member

Откуда:
Сообщений: 13622
log_here
Не мог бы расписать?

Читаешь блок X байт (символов). Дальше разбираешь посимвольно. Примерно так:
Н = 0
цикл: прочитать блок символов
  цикл: прочитать очередной символ блока в С
    если С = 0-9
        Н = Н*10 + С
    иначе  // С = перевод строки
       если Н != 0 записать Н в массив результатов
       Н = 0
   конец цикла
конец цикла

0 замени на недопустимое значение, если невозможно - добавь флаг.
29 ноя 15, 18:45    [18488372]     Ответить | Цитировать Сообщить модератору
 Re: как быстрее всего прочесть большой файл с числами, каждое с новой строки?  [new]
Зимаргл
Guest
Тесты, что я видел, показывают что потоки (iostreams) С++ работают довольно медленно.

Соответственно, хотите скорость - читайте и парсите напрямую.
Хотя почему так - хз, они не для скорости предназначены изначально.

Кому надо, пусть ковыряет подробности.
Я как-то смотрел генерированный ассемблер, он был ужасен =)
29 ноя 15, 23:38    [18489327]     Ответить | Цитировать Сообщить модератору
 Re: как быстрее всего прочесть большой файл с числами, каждое с новой строки?  [new]
log_here
Member [заблокирован]

Откуда:
Сообщений: 331
Написал так, работает быстрее.
Только как понять, что достигнут конец файла, ведь так можно до бесконечности цикл с "i" проходить?
void buf3()
{
	const clock_t begin_time = clock();
	
	std::ifstream ifs("./input_file.txt", std::ios::binary);
	char buff[32 * 512];

	for (int i = 0; ; ++i){
		ifs.read(buf, sizeof(buff) / sizeof(*buff));
		for (int j = 0; j < 32 * 512; ++j){
			if (buff[j] == '-'){
			} else if(buff[j] == '\n') {
			} else {
				// Обрабатываем '0' - '9'
			}
		}
		//std::cout << std::endl;
	}
	
	std::cout << float( 1000 * (clock () - begin_time )) /  CLOCKS_PER_SEC << std::endl;
}
29 ноя 15, 23:55    [18489381]     Ответить | Цитировать Сообщить модератору
 Re: как быстрее всего прочесть большой файл с числами, каждое с новой строки?  [new]
mayton
Member

Откуда: loopback
Сообщений: 40400
Посмотри как тут пишут.

http://www.cplusplus.com/reference/istream/istream/read/

Вообще по настоящему перформить с файлами надо без std. IMHO.
30 ноя 15, 00:11    [18489413]     Ответить | Цитировать Сообщить модератору
 Re: как быстрее всего прочесть большой файл с числами, каждое с новой строки?  [new]
MasterZiv
Member

Откуда: Питер
Сообщений: 34437
log_here
Допустим, есть файл, состоящий из 100 000 000 000 чисел int, каждое число записано с новой строчки.
Надо последовательно его прочесть. Мне кажется, будет намного быстрее, если читать не число за числом, а сразу много чисел читать и загружать в локальный массив (вектор), проводя загрузку несколько раз.

Как можно это сделать?
Если есть ещё более быстрый способ -- ещё лучше.

я знаю, что можно использовать [code cpp] std::fstream[code],
но есть ли более быстрый способ?



на самом деле все равно, как читать.
лишь бы не посимвольно.
если читать строку gets() или аналогом, то будет вполне хорошо.
30 ноя 15, 01:24    [18489621]     Ответить | Цитировать Сообщить модератору
 Re: как быстрее всего прочесть большой файл с числами, каждое с новой строки?  [new]
MasterZiv
Member

Откуда: Питер
Сообщений: 34437
log_here
И ещё вопрос: почему файл с
1024 * 1024 / sizeof(int)
числами занимает ощутимо больше, чем 1 МБ, даже если числа внутри файла ничем не разделены?


во первых, они таки разделены, переводами строк (1 или2символов)
во вторых, числа наверняка записаны как строки, поэтому надо считать не как size of int , а порядок числа, умножить на size of char.
30 ноя 15, 01:28    [18489623]     Ответить | Цитировать Сообщить модератору
 Re: как быстрее всего прочесть большой файл с числами, каждое с новой строки?  [new]
log_here
Member [заблокирован]

Откуда:
Сообщений: 331
MasterZiv
на самом деле все равно, как читать.
лишь бы не посимвольно.
если читать строку gets() или аналогом, то будет вполне хорошо.

лишь бы не посимвольно -- это лишь бы не как в buf3()?
30 ноя 15, 01:34    [18489632]     Ответить | Цитировать Сообщить модератору
 Re: как быстрее всего прочесть большой файл с числами, каждое с новой строки?  [new]
Dima T
Member

Откуда:
Сообщений: 13622
log_here
Написал так, работает быстрее.
Только как понять, что достигнут конец файла, ведь так можно до бесконечности цикл с "i" проходить?

Читай хэлп на std::istream::read()

И проверка у тебя не очень корректная. Что будет если встретятся последовательности "12-345", "12x345" ?
30 ноя 15, 07:04    [18489772]     Ответить | Цитировать Сообщить модератору
 Re: как быстрее всего прочесть большой файл с числами, каждое с новой строки?  [new]
MasterZiv
Member

Откуда: Питер
Сообщений: 34437
log_here
лишь бы не посимвольно -- это лишь бы не как в buf3()?


Я не знаю, что такое buf3().
30 ноя 15, 15:18    [18492642]     Ответить | Цитировать Сообщить модератору
 Re: как быстрее всего прочесть большой файл с числами, каждое с новой строки?  [new]
Изопропил
Member

Откуда:
Сообщений: 31078
простейший конечный автомат - никак не изобразить?
30 ноя 15, 15:50    [18492878]     Ответить | Цитировать Сообщить модератору
 Re: как быстрее всего прочесть большой файл с числами, каждое с новой строки?  [new]
PPA
Member

Откуда: Караганда -> Липецк
Сообщений: 805
log_here,

А покажи сырой формат файла input_file.txt что в нем лежит - первые n-строк.
и какие правила его формирования?
если длина записей "плавает" у тебя buf3 не будет работать корректно.
рекомендую кроме скорости чтения считать контрольную сумму данных из фала - чтобы заранее словить и логические ошибки алгоритма.

также попробуй сделать buf4() с использованием boost::iostreams::mapped_file_source
у тебя файл 90 гиг - усложнит чуток и придется прыгать по сегментам,
но зато исключишь лишнюю копию данных в памяти - все упрется в диск и cpu.
1 дек 15, 12:23    [18496606]     Ответить | Цитировать Сообщить модератору
 Re: как быстрее всего прочесть большой файл с числами, каждое с новой строки?  [new]
mayton
Member

Откуда: loopback
Сообщений: 40400
У меня какое-то адское déjà vu.

Почему мы всё время рекомендуем новичкам использовать Memory Mapped Files даже
там где задача - ярко выраженно требует поточной обработки.

Коллеги. Поясните. Что за тренд такой?
1 дек 15, 12:29    [18496658]     Ответить | Цитировать Сообщить модератору
 Re: как быстрее всего прочесть большой файл с числами, каждое с новой строки?  [new]
PPA
Member

Откуда: Караганда -> Липецк
Сообщений: 805
mayton,

Тут нет тренда.
если автор ищет способ ускорить чтение файла - почему-бы не попробовать все способы?

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

ну и если не сложно приведите свой пример поточной обработки.
рассмотрим его плюсы и минусы.
1 дек 15, 14:51    [18497664]     Ответить | Цитировать Сообщить модератору
 Re: как быстрее всего прочесть большой файл с числами, каждое с новой строки?  [new]
Изопропил
Member

Откуда:
Сообщений: 31078
PPA
может для оптимального решения достаточно поправить несколько
строк в том софте, который сохраняет пары int-значений в виде текста в 100 гиговый файл
а потом заставляет другой процесс героически парсить это гавно.

memory mapped file на 100 гигов - здесь явно не при делах
1 дек 15, 15:17    [18497854]     Ответить | Цитировать Сообщить модератору
 Re: как быстрее всего прочесть большой файл с числами, каждое с новой строки?  [new]
Dima T
Member

Откуда:
Сообщений: 13622
PPA
если автор ищет способ ускорить чтение файла - почему-бы не попробовать все способы?

Судя по замерам не ту проблему он решает
log_here
7.8 МБ / 1.3 c = 6 МБ/c и
7.8 МБ / 2.6 c = 3 МБ/c

это медленно даже если файл тянуть по 100 Мбитной сетке.
Как-то тестил: чтение блоками по 64Кб оптимально, дальнейшее увеличение блока ускорения не дает. Мап тоже тестил, получилось одинаково по скорости.

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

Допустим скорость чтения 50 Мб/с (неоптимальное чтение среднего HDD), тогда получается что 10% времени чтение - 90% обработка. Ускорим мы чтение до 500 Мб/с: 1% чтение - 90% обработка. И толку от этих 9% ускорения?
1 дек 15, 15:31    [18497959]     Ответить | Цитировать Сообщить модератору
 Re: как быстрее всего прочесть большой файл с числами, каждое с новой строки?  [new]
mayton
Member

Откуда: loopback
Сообщений: 40400
PPA
Также вы ведь не знаете все условия задачи.
может для оптимального решения достаточно поправить несколько
строк в том софте, который сохраняет пары int-значений в виде текста в 100 гиговый файл
а потом заставляет другой процесс героически парсить это гавно.

Я согласен. Давайте заслушаем ВСЕ условия задачи. Кстати я-бы не начал
перформить до тех пор пока не узнал бы целевую ОС. Судя по путям
у афтора Linux - но хотелось-бы услышать подтверждение.
1 дек 15, 15:35    [18497999]     Ответить | Цитировать Сообщить модератору
 Re: как быстрее всего прочесть большой файл с числами, каждое с новой строки?  [new]
MasterZiv
Member

Откуда: Питер
Сообщений: 34437
mayton
У меня какое-то адское déjà vu.

Почему мы всё время рекомендуем новичкам использовать Memory Mapped Files даже
там где задача - ярко выраженно требует поточной обработки.

Коллеги. Поясните. Что за тренд такой?


Да вот я тоже не знаю, тем более что Memory Mapped Files ничего не ускоряют...
1 дек 15, 17:06    [18498539]     Ответить | Цитировать Сообщить модератору
 Re: как быстрее всего прочесть большой файл с числами, каждое с новой строки?  [new]
Изопропил
Member

Откуда:
Сообщений: 31078
MasterZiv
Да вот я тоже не знаю, тем более что Memory Mapped Files ничего не ускоряют...

они ж для разделения данных между процессами, а не для ускорения.
1 дек 15, 17:48    [18498811]     Ответить | Цитировать Сообщить модератору
 Re: как быстрее всего прочесть большой файл с числами, каждое с новой строки?  [new]
mayton
Member

Откуда: loopback
Сообщений: 40400
Изопропил
MasterZiv
Да вот я тоже не знаю, тем более что Memory Mapped Files ничего не ускоряют...

они ж для разделения данных между процессами, а не для ускорения.

Коллеги! Ну блин куда мы заехали? При чём тут разделение? Сабж не о том.
1 дек 15, 18:09    [18498920]     Ответить | Цитировать Сообщить модератору
 Re: как быстрее всего прочесть большой файл с числами, каждое с новой строки?  [new]
Изопропил
Member

Откуда:
Сообщений: 31078
mayton,

сколько мегабайт в секунду является нормальным на твой взгляд?
1 дек 15, 18:14    [18498932]     Ответить | Цитировать Сообщить модератору
 Re: как быстрее всего прочесть большой файл с числами, каждое с новой строки?  [new]
Basil A. Sidorov
Member

Откуда:
Сообщений: 9127
Скорость линейного чтения с диска.
1 дек 15, 18:15    [18498939]     Ответить | Цитировать Сообщить модератору
 Re: как быстрее всего прочесть большой файл с числами, каждое с новой строки?  [new]
mayton
Member

Откуда: loopback
Сообщений: 40400
Опять двадцать пять. Вы о чём? Хотите что-бы я назвал скорость
современного дискового интерфейса типа Sata-3 ? Я ее не помню
дословно.

Что такое нормально? Чтоб юзер был доволен текущим приложением.
Вот это и есть критерий нормально.
1 дек 15, 18:18    [18498954]     Ответить | Цитировать Сообщить модератору
 Re: как быстрее всего прочесть большой файл с числами, каждое с новой строки?  [new]
Basil A. Sidorov
Member

Откуда:
Сообщений: 9127
Пользователь никогда (или почти никогда) не бывает доволен быстродействием программы.
А "скорость линейного чтения с диска" - нормальный и объективный критерий.
1 дек 15, 18:21    [18498968]     Ответить | Цитировать Сообщить модератору
 Re: как быстрее всего прочесть большой файл с числами, каждое с новой строки?  [new]
Dimitry Sibiryakov
Member

Откуда:
Сообщений: 47373

Basil A. Sidorov
А "скорость линейного чтения с диска" - нормальный и объективный
критерий.

Лучше всё же не полагаться на линейность, а в качестве критерия использовать скорость
копирования этого же файла в /dev/nul.

Posted via ActualForum NNTP Server 1.5

1 дек 15, 18:29    [18498993]     Ответить | Цитировать Сообщить модератору
 Re: как быстрее всего прочесть большой файл с числами, каждое с новой строки?  [new]
Dima T
Member

Откуда:
Сообщений: 13622
Изопропил
mayton,

сколько мегабайт в секунду является нормальным на твой взгляд?

~100 мб/с в среднем нормально. Замерить точнее просто: в фаре запускаешь копирование, в качестве места назначения пишешь nul. Будет показывать скорость чтения конкретного файла.
1 дек 15, 18:31    [18499003]     Ответить | Цитировать Сообщить модератору
 Re: как быстрее всего прочесть большой файл с числами, каждое с новой строки?  [new]
Изопропил
Member

Откуда:
Сообщений: 31078
Dima T
Будет показывать скорость чтения конкретного файла.

из кэша.....
1 дек 15, 18:48    [18499118]     Ответить | Цитировать Сообщить модератору
 Re: как быстрее всего прочесть большой файл с числами, каждое с новой строки?  [new]
mayton
Member

Откуда: loopback
Сообщений: 40400
Давайте вернёмся к нашей задаче. У нас 100 млрд целых чисел в текстовом файле
и автору нужно это всё загрузить в коллекцию STD.

Вот как-то в таком вот аспекте.
1 дек 15, 19:29    [18499320]     Ответить | Цитировать Сообщить модератору
 Re: как быстрее всего прочесть большой файл с числами, каждое с новой строки?  [new]
Изопропил
Member

Откуда:
Сообщений: 31078
mayton
Вот как-то в таком вот аспекте.

память прикупил топикстартер?
1 дек 15, 19:38    [18499345]     Ответить | Цитировать Сообщить модератору
 Re: как быстрее всего прочесть большой файл с числами, каждое с новой строки?  [new]
Dima T
Member

Откуда:
Сообщений: 13622
Изопропил
Dima T
Будет показывать скорость чтения конкретного файла.

из кэша.....

Это со второго раза и то в случае если кэш больше файла. Если не путаю речь о 90 Гб, тут рядовой комп точно не закэширует.
1 дек 15, 19:54    [18499384]     Ответить | Цитировать Сообщить модератору
 Re: как быстрее всего прочесть большой файл с числами, каждое с новой строки?  [new]
mayton
Member

Откуда: loopback
Сообщений: 40400
На самом деле - афтор чёртов партизан и не говорит что он дальше будет делать с числами
а это мега важно для оптимизации. Далее. Линух или Виндовс. Хер ево знает но пускай
будет линух.

Вот шаблон который я скачал в стековервлоу http://stackoverflow.com/questions/28197649/reading-binary-file-in-c-in-chunks

size_t bytesRead = 0;
file = fopen(myfile, "rb");   

if (file != NULL)    
{
  // read up to sizeof(buffer) bytes
  while ((bytesRead = fread(buffer, 1, sizeof(buffer), file)) > 0)
  {
    // process bytesRead worth of data in buffer
  }
}


Его можно взять за основу. Есть блочное чтение и достаточно низкий уровень API.
Можно еще поискать open/read/close.

Далее. Работаем с байтами. Если автору нужны символы - то конвертит.

Синхронная работа.
// process bytesRead worth of data in buffer

buffer....


Собственно здесь должен быть некий finite-state-machine который
разбирает поток символов на целые числа.

while(...){
   // process byte (char)
   // convert into integer
   // process integer stream
}


Поскольку работаем синхронно - то чуть блокируем I/O.

Для асинхронной работы нужно увеличить буфер и работать
с двумя буферами или с кольцом и в 2 процесса.

Вот вобщем-то такое моё предложение.

Буду рад улучшениям и пожеланиям.

Не возражаю против магии Хогвартса mmaped-files но прошу аргументации.

Если лучше - то почему. Что достигаем? Что теряем? Напомню что в смежном
топике мы при тестинге на запись не учитывали отложенный flush и получали
неверную картину фиксации записи.

Напомню также что афтор упорно пытается прогрузить 100 млрд в коллекцию.
Возможно мы отговорим его от такого странного хода но в любом случае
memory надо использовать по хозяйски и не вносить в уравнение "свободная
память" нечто что не укладывается в прогноз по minimal requrements.

Напомню также что решение любой задачи не должно быть краш-тестом
для других приложений которые тихо зависнут или умрут по I/O timeout.
Нужно помнить о кооперативном разделении всех ресурсов.
1 дек 15, 20:49    [18499569]     Ответить | Цитировать Сообщить модератору
 Re: как быстрее всего прочесть большой файл с числами, каждое с новой строки?  [new]
Изопропил
Member

Откуда:
Сообщений: 31078
mayton
Напомню также что афтор упорно пытается прогрузить 100 млрд в коллекцию.

с этого начинать нужно
1 дек 15, 22:33    [18500014]     Ответить | Цитировать Сообщить модератору
 Re: как быстрее всего прочесть большой файл с числами, каждое с новой строки?  [new]
log_here
Member [заблокирован]

Откуда:
Сообщений: 331
mayton,

ОС - Linux.
Предположим для простоты, что собираюсь сортировать (внешняя сотрировка).
2 дек 15, 01:52    [18500524]     Ответить | Цитировать Сообщить модератору
 Re: как быстрее всего прочесть большой файл с числами, каждое с новой строки?  [new]
Изопропил
Member

Откуда:
Сообщений: 31078
log_here
Предположим для простоты
давай реальную задачу,
алгоритмы внешней сортировки в любом учебнике описаны
2 дек 15, 06:51    [18500639]     Ответить | Цитировать Сообщить модератору
 Re: как быстрее всего прочесть большой файл с числами, каждое с новой строки?  [new]
Dima T
Member

Откуда:
Сообщений: 13622
+ Создание тестового файла
void create_file(const char* filename) {
	FILE* file = fopen(filename, "wb");   
	if (file != NULL) { 
		for(int i = 0; i < 1000000000; i++) {
			fprintf(file, "%d\n", rand());
		}
		fclose(file);
	}
}

у меня получилось 5398 Мб.
Меряем фаром скорость чтения (копирование в nul) - 620 Мб/с
Время 8,7 сек. это минимально возможное время.
+ Цикл только чтение
void read_speed(const char* filename) {
	int count = 0;
	clock_t start = clock();
	FILE* file = fopen(filename, "rb");   
	if (file != NULL) { 
		int n = 0;
		bool store = false;
		char buffer[1024 * 64];
		size_t bytesRead = 0;
		while ((bytesRead = fread(buffer, 1, sizeof(buffer), file)) > 0) {
			count++;
		}
		fclose(file);
	}
	printf("Count %d blocks Time %f sec.\n", count, (double)(clock() - start) / CLOCKS_PER_SEC);
}

Время 9,1 сек. т.е. всего на 5% больше минимума.

+ Замер на С++ (std::ifstream)
void ifstream_speed(const char* filename)
{
	clock_t start = clock();
	std::ifstream ifs(filename, std::ios::binary);
	char buff[1024 * 64];
	int count = 0;

	while(ifs){
		ifs.read(buff, sizeof(buff));
		count++;
	}
	ifs.close();
	printf("Count %d blocks Time %f sec.\n", count, (double)(clock() - start) / CLOCKS_PER_SEC);
}

Время 9,5 сек. Чуть хуже, но не критично. 9% больше минимума.

+ Добавляем примитивный парсер: все что не числа - то разделители
void read_ints(const char* filename) {
	int count = 0;
	clock_t start = clock();
	FILE* file = fopen(filename, "rb");   
	if (file != NULL) { 
		int n = 0;
		bool store = false;
		char buffer[1024 * 64];
		size_t bytesRead = 0;
		while ((bytesRead = fread(buffer, 1, sizeof(buffer), file)) > 0) {
			for(size_t i = 0; i < bytesRead; i++) {
				// считаем что все числа целые и разделены любыми разделителями
				if(buffer[i] >= '0' && buffer[i] <= '9') {
					n = n * 10 + buffer[i] - '0';
					store = true;
				} else if(store) {
					// тут сохраняем результат
					//printf("%d\n", n);
					count++;
					store = false;
					n = 0;
				}
			}
		}
		fclose(file);
	}
	printf("Read %d numbers Time %f sec.\n", count, (double)(clock() - start) / CLOCKS_PER_SEC);
}

Время 16,7 сек. т.е. уже почти половина времени пошла на разбор. А тут еще никакого сохранения нет.

Как уже написал 18497959 - парсер надо оптимизировать, а не чтение ускорять
2 дек 15, 07:46    [18500686]     Ответить | Цитировать Сообщить модератору
 Re: как быстрее всего прочесть большой файл с числами, каждое с новой строки?  [new]
Изопропил
Member

Откуда:
Сообщений: 31078
Dima T,

отрицательные числа - не обрабатываешь, за переполнением - не следишь
2 дек 15, 08:10    [18500720]     Ответить | Цитировать Сообщить модератору
 Re: как быстрее всего прочесть большой файл с числами, каждое с новой строки?  [new]
Dima T
Member

Откуда:
Сообщений: 13622
+ С указателями чуть быстрее
void read_ints(const char* filename) {
	int count = 0;
	clock_t start = clock();
	FILE* file = fopen(filename, "rb");   
	if (file != NULL) { 
		int n = 0;
		bool store = false;
		char buffer[1024 * 8];
		size_t bytesRead = 0;
		while ((bytesRead = fread(buffer, 1, sizeof(buffer), file)) > 0) {
			char* end = buffer + bytesRead;
			for(char* cur = buffer; cur < end; cur++) {
				// считаем что все числа целые и разделены любыми разделителями
				if(*cur >= '0' && *cur <= '9') {
					n = n * 10 + *cur - '0';
					store = true;
				} else if(store) {
					// тут сохраняем результат
					//printf("%d\n", n);
					count++;
					store = false;
					n = 0;
				}
			}
		}
		fclose(file);
	}
	printf("Read %d numbers Time %f sec.\n", count, (double)(clock() - start) / CLOCKS_PER_SEC);
}

Померил еще зависимость времени от размера буфера
РазмерВремя
4 Кб 15.1
8 Кб 14.8
16 Кб 14.9
32 Кб 14.8
64 Кб 15.5
128 Кб 15.6
256 Кб 15.8
512 Кб 16.0

ХЗ почему так. Может из-за кэша проца.
2 дек 15, 08:14    [18500726]     Ответить | Цитировать Сообщить модератору
 Re: как быстрее всего прочесть большой файл с числами, каждое с новой строки?  [new]
Dima T
Member

Откуда:
Сообщений: 13622
Изопропил
Dima T,

отрицательные числа - не обрабатываешь, за переполнением - не следишь

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

Я к тому что чтение ускорять бесполезно - надо разбор ускорять.
2 дек 15, 08:19    [18500735]     Ответить | Цитировать Сообщить модератору
 Re: как быстрее всего прочесть большой файл с числами, каждое с новой строки?  [new]
Изопропил
Member

Откуда:
Сообщений: 31078
Dima T
Я же написал что парсер минимальный. Просто для демонстрации его влияния на общее время работы.

усложнение серьёзно повлияет на время работы - демонстрация ни о чём
2 дек 15, 08:21    [18500741]     Ответить | Цитировать Сообщить модератору
 Re: как быстрее всего прочесть большой файл с числами, каждое с новой строки?  [new]
Dima T
Member

Откуда:
Сообщений: 13622
Изопропил
усложнение серьёзно повлияет на время работы

Я разве обратное утверждаю? Мой примитивнейший парсер уже почти вдвое замедлил работу. Это несерьезное влияние?
Изопропил
демонстрация ни о чём

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

Я о том что ТСу надо парсер свой писать и затачивать его под свою задачу.
2 дек 15, 09:06    [18500892]     Ответить | Цитировать Сообщить модератору
 Re: как быстрее всего прочесть большой файл с числами, каждое с новой строки?  [new]
Dima T
Member

Откуда:
Сообщений: 13622
+ Добавил отрицательные и контроль переполнения
void read_ints2(const char* filename) {
	int count = 0;
	clock_t start = clock();
	FILE* file = fopen(filename, "rb");   
	if (file != NULL) { 
		int n = 0;
		bool minus = false;
		bool store = false;
		bool overflow = false;
		char buffer[1024 * 8];
		size_t bytesRead = 0;
		while ((bytesRead = fread(buffer, 1, sizeof(buffer), file)) > 0) {
			char* end = buffer + bytesRead;
			for(char* cur = buffer; cur < end; cur++) {
				// считаем что все числа целые и разделены любыми разделителями
				if(*cur >= '0' && *cur <= '9') {
					int k = n * 10 + *cur - '0';
					if(!overflow) overflow = k < n;
					n = k;
					store = true;
				} else {
					if(store) {
						// тут сохраняем результат
						if(overflow) {
							printf("overflow\n");// переполнение
							overflow = false;
						} else {
							if(minus) {
								n = -n;
								minus = false;
							}
							//printf("%d\n", n);
							count++;
						}
						store = false;
						n = 0;
					}
					minus = (*cur == '-');
				}
			}
		}
		fclose(file);
	}
	printf("Read %d numbers Time %f sec.\n", count, (double)(clock() - start) / CLOCKS_PER_SEC);
}

Время 18.7 сек
Не особо замедлилось. Всего на 25%
2 дек 15, 09:33    [18501044]     Ответить | Цитировать Сообщить модератору
 Re: как быстрее всего прочесть большой файл с числами, каждое с новой строки?  [new]
Pallaris
Member

Откуда: Украина, Донецк
Сообщений: 1600
Задачка с собеседования?
2 дек 15, 09:35    [18501057]     Ответить | Цитировать Сообщить модератору
 Re: как быстрее всего прочесть большой файл с числами, каждое с новой строки?  [new]
Изопропил
Member

Откуда:
Сообщений: 31078
Dima T,

грязненько парсер выглядит
2 дек 15, 10:00    [18501149]     Ответить | Цитировать Сообщить модератору
 Re: как быстрее всего прочесть большой файл с числами, каждое с новой строки?  [new]
Dima T
Member

Откуда:
Сообщений: 13622
Изопропил
Dima T,

грязненько парсер выглядит

Напиши чистенько если время есть. Накидал по-быстрому первое что в голову пришло. Работает вроде правильно, но особо не тестил.
Что именно не понравилось?
2 дек 15, 10:23    [18501244]     Ответить | Цитировать Сообщить модератору
 Re: как быстрее всего прочесть большой файл с числами, каждое с новой строки?  [new]
mayton
Member

Откуда: loopback
Сообщений: 40400
Dima T
Изопропил
Dima T,

грязненько парсер выглядит

Напиши чистенько если время есть. Накидал по-быстрому первое что в голову пришло. Работает вроде правильно, но особо не тестил.
Что именно не понравилось?

Дима!

9 секунд чистого чтения против 15 секунд чтения + парсера?

Верно я понял твои цифры?
2 дек 15, 11:27    [18501750]     Ответить | Цитировать Сообщить модератору
 Re: как быстрее всего прочесть большой файл с числами, каждое с новой строки?  [new]
Dima T
Member

Откуда:
Сообщений: 13622
mayton, ты все правильно понял.
2 дек 15, 11:30    [18501774]     Ответить | Цитировать Сообщить модератору
 Re: как быстрее всего прочесть большой файл с числами, каждое с новой строки?  [new]
mayton
Member

Откуда: loopback
Сообщений: 40400
Тогда курим двух-процессный режим. Возможно там будут нюансы.
Но неплохо было-бы сделать 1 процесс-поставщик который поставляет готовые
chunks (чётный - нечётный), а второй за ним подбирает и парсит. Это для модели
когда скорость чтения с диска достаточно равномерна.

Если будут сильные рывки - тогда имеет смысл сделать буферы побольше двух.
И завернуть их в бублик.
2 дек 15, 11:36    [18501814]     Ответить | Цитировать Сообщить модератору
 Re: как быстрее всего прочесть большой файл с числами, каждое с новой строки?  [new]
Изопропил
Member

Откуда:
Сообщений: 31078
mayton
Но неплохо было-бы сделать 1 процесс-поставщик который поставляет готовые
chunks (чётный - нечётный), а второй за ним подбирает и парсит

так следует действовать и с единственным процессом - получили буфер(синхронно/асинхронно, прочитали из хэндла/получили из фильтра и т д) - передали буфер парсеру.
2 дек 15, 12:05    [18502019]     Ответить | Цитировать Сообщить модератору
 Re: как быстрее всего прочесть большой файл с числами, каждое с новой строки?  [new]
mayton
Member

Откуда: loopback
Сообщений: 40400
Изопропил, согласен.
2 дек 15, 12:10    [18502048]     Ответить | Цитировать Сообщить модератору
 Re: как быстрее всего прочесть большой файл с числами, каждое с новой строки?  [new]
mayton
Member

Откуда: loopback
Сообщений: 40400
Асинхронное всё API здесь? Или еще где-то?
#include <aio.h>
2 дек 15, 13:33    [18502624]     Ответить | Цитировать Сообщить модератору
 Re: как быстрее всего прочесть большой файл с числами, каждое с новой строки?  [new]
YesSql
Guest
mayton
Асинхронное всё API здесь? Или еще где-то?
#include <aio.h>

Если мы говорим о линуксе то это user-space эмуляция POSIX AIO

linux aio сдесь
#include <linux/aio_abi.h>
2 дек 15, 17:44    [18504375]     Ответить | Цитировать Сообщить модератору
 Re: как быстрее всего прочесть большой файл с числами, каждое с новой строки?  [new]
mayton
Member

Откуда: loopback
Сообщений: 40400
Ну тогда всё чики-пики. Только я щас метаюсь между форумом и багофиксом поставки.

Может кто-то "запилит" AIO-реализацию?
2 дек 15, 17:47    [18504385]     Ответить | Цитировать Сообщить модератору
 Re: как быстрее всего прочесть большой файл с числами, каждое с новой строки?  [new]
YesSql
Guest
mayton
Ну тогда всё чики-пики. Только я щас метаюсь между форумом и багофиксом поставки.

Может кто-то "запилит" AIO-реализацию?

Нет никакого смысла использовать POSIX AIO эмуляцию. Делайте "true unix way" один процесс читает и выдает в stdout а другой берет из stdin и парсирует. Просто в реализации и оптимально. Можно и еще упростить - вместо первого процесса и bash сойдет. ;)
2 дек 15, 18:03    [18504465]     Ответить | Цитировать Сообщить модератору
 Re: как быстрее всего прочесть большой файл с числами, каждое с новой строки?  [new]
mayton
Member

Откуда: loopback
Сообщений: 40400
YesSql, некислую часть задач новичков в С++ можно свести к bash, grep, awk ...
2 дек 15, 18:12    [18504505]     Ответить | Цитировать Сообщить модератору
 Re: как быстрее всего прочесть большой файл с числами, каждое с новой строки?  [new]
Dima T
Member

Откуда:
Сообщений: 13622
mayton
Может кто-то "запилит" AIO-реализацию?

про AIO не в курсе. Хотел по-быстрому переделать под два потока на WinAPI: один читает, второй парсит. Переписал, но криво работает, 3 часа уже ошибку ищу. Вроде элементарная задача. Подозревать WinAPI в кривости последнее дело, явно сам где-то накосячил, не найду - выложу на общее обсуждение.
2 дек 15, 18:13    [18504514]     Ответить | Цитировать Сообщить модератору
 Re: как быстрее всего прочесть большой файл с числами, каждое с новой строки?  [new]
mayton
Member

Откуда: loopback
Сообщений: 40400
Dima T
mayton
Может кто-то "запилит" AIO-реализацию?

про AIO не в курсе. Хотел по-быстрому переделать под два потока на WinAPI: один читает, второй парсит. Переписал, но криво работает, 3 часа уже ошибку ищу. Вроде элементарная задача. Подозревать WinAPI в кривости последнее дело, явно сам где-то накосячил, не найду - выложу на общее обсуждение.

Давай в sourceforge. Я тоже покурю. Только вечером.

Заодно сравним мультипоточность Win и мультипроцессность в Пингвине.
2 дек 15, 18:19    [18504536]     Ответить | Цитировать Сообщить модератору
 Re: как быстрее всего прочесть большой файл с числами, каждое с новой строки?  [new]
Изопропил
Member

Откуда:
Сообщений: 31078
Dima T
Хотел по-быстрому переделать под два потока на WinAPI

на WinAPI лучше будет completion port и один поток
2 дек 15, 18:42    [18504618]     Ответить | Цитировать Сообщить модератору
 Re: как быстрее всего прочесть большой файл с числами, каждое с новой строки?  [new]
Dima T
Member

Откуда:
Сообщений: 13622
Начитался про lock-free алгоритмы, хотел на практике затестить, задача подходящая, но похоже что-то я недопонял. Подождем до завтра. Утром обычно все понятнее становится. Не взлетит - выложу на общее о(б)суждение :) Взлетит - тоже выложу.
2 дек 15, 18:42    [18504620]     Ответить | Цитировать Сообщить модератору
 Re: как быстрее всего прочесть большой файл с числами, каждое с новой строки?  [new]
Dima T
Member

Откуда:
Сообщений: 13622
Изопропил
на WinAPI лучше будет completion port и один поток

Нет цели сделать на/под WinAPI, т.е. только под Win. Есть обратная цель - сделать универсально. Но де-факто есть VC2008 на XP. Там нет С++11 с трэдами и <atomic>. От XP отказаться пока не готов: VC2012 где есть С++11 - не ставится. Надо наверно уже переехать на W7, но жаба давит: там где живет 5 виртуалок на XP - еле влазит одна W7. SSD не резиновые.
2 дек 15, 18:57    [18504678]     Ответить | Цитировать Сообщить модератору
 Re: как быстрее всего прочесть большой файл с числами, каждое с новой строки?  [new]
mayton
Member

Откуда: loopback
Сообщений: 40400
А мне вот это интересно попробовать

https://www.freebsd.org/ru/features.html
Многопоточая модель M:N через pthreads делает возможным масштабируемое исполнение потоков на множестве CPU, ставя множество пользовательских потоков в соответствие малому количеству Kernel Schedulable Entities. С принятием модели Scheduler Activation такой подход к многопоточности может быть адаптирован к специфическим требованиям широкого набора приложений.
2 дек 15, 19:24    [18504781]     Ответить | Цитировать Сообщить модератору
 Re: как быстрее всего прочесть большой файл с числами, каждое с новой строки?  [new]
Dima T
Member

Откуда:
Сообщений: 13622
mayton,

ИМХУ это следствие. Закон Амдала никто не отменил. Все остальное - это следствие. Надо причину обходить.

lock-free алгоритмы зацепили тем что без явной потребности синхронизации потоков они не потребляют (точнее минимально потребляют) лишние ресурсы. Взять тут же задачу топика: если не требуется одновременно писать и читать с одного буфера, то зачем тратить ресурсы на синхронизацию? Синхронизация она же не бесплатная. Как-то я тут проводил тесты разных мутексов и т.п.
2 дек 15, 20:14    [18504932]     Ответить | Цитировать Сообщить модератору
 Re: как быстрее всего прочесть большой файл с числами, каждое с новой строки?  [new]
mayton
Member

Откуда: loopback
Сообщений: 40400
В нашем случае Амдал сдулся до 9 секунд.

Будем штурмовать рубеж?
2 дек 15, 20:27    [18504983]     Ответить | Цитировать Сообщить модератору
 Re: как быстрее всего прочесть большой файл с числами, каждое с новой строки?  [new]
Dima T
Member

Откуда:
Сообщений: 13622
mayton
В нашем случае Амдал сдулся до 9 секунд.

Будем штурмовать рубеж?

К 9 бы надо прийти для начала. Потом уже с Амдалом спорить.
2 дек 15, 20:36    [18505012]     Ответить | Цитировать Сообщить модератору
 Re: как быстрее всего прочесть большой файл с числами, каждое с новой строки?  [new]
Изопропил
Member

Откуда:
Сообщений: 31078
Dima T
Там нет С++11

C без плюсов достаточно
2 дек 15, 21:50    [18505242]     Ответить | Цитировать Сообщить модератору
 Re: как быстрее всего прочесть большой файл с числами, каждое с новой строки?  [new]
alexy_black
Member

Откуда: Санкт-Петербург
Сообщений: 664
парни, не бейти сильно, не читал обсуждение до конца, но делаю вброс :)
наверное корутины самое то :) когда выполняется какое-либо условие, можно файл дальше не читать. если например, это произошло в начале файла, то сразу и готово! экономия почти 100%

boost.org/libs/coroutine2
3 дек 15, 11:54    [18507205]     Ответить | Цитировать Сообщить модератору
 Re: как быстрее всего прочесть большой файл с числами, каждое с новой строки?  [new]
mayton
Member

Откуда: loopback
Сообщений: 40400
Какое еще условие бро? У нас нет ничего подобного. Надо прочитать 100 млрд текстовых строк.
3 дек 15, 12:39    [18507570]     Ответить | Цитировать Сообщить модератору
 Re: как быстрее всего прочесть большой файл с числами, каждое с новой строки?  [new]
alexy_black
Member

Откуда: Санкт-Петербург
Сообщений: 664
mayton
Какое еще условие бро? У нас нет ничего подобного. Надо прочитать 100 млрд текстовых строк.

а потом что с ними делать? должно же быть хоть что-то нужное :)
хотя если просто прочитать, то корутины только затормозят процесс - придется прыгать на контекст... но если строк 100 млрд, а прочитав 99 млрд можно остановиться, то корутины сильно укорят, наверное :)
3 дек 15, 13:01    [18507754]     Ответить | Цитировать Сообщить модератору
 Re: как быстрее всего прочесть большой файл с числами, каждое с новой строки?  [new]
mayton
Member

Откуда: loopback
Сообщений: 40400
Да не ко мне это вопрос. Но в общем случае, если афтор хочет гнать по ним аналитику
то я в принципе не понимаю мотивации останавливаться.

Или ты что-то другое хотел предложить?
3 дек 15, 13:33    [18508052]     Ответить | Цитировать Сообщить модератору
 Re: как быстрее всего прочесть большой файл с числами, каждое с новой строки?  [new]
Dima T
Member

Откуда:
Сообщений: 13622
Доделал, вроде работает но не быстро :(

Тестовый файл был 1 млрд. чисел. Файл 6 Гб.
На i7 (4 ядра) RAM 32 Гб
ТестВремя сек.
Только чтение2.7
Однопоточный разбор14.6
Многопоточный12.9

На i5 (2 ядра + HT) RAM 4 Гб
ТестВремя сек.
Только чтение34.3
Однопоточный разбор55.6
Многопоточный69.8

+ Исходник (все три теста и генератор файла)
#include <windows.h>
#include <time.h>
#include <process.h>
#include <stdio.h>

#define BUF_COUNT 128
#define BUF_SIZE 1024 * 8

// Создание файла
void create_file(const char* filename, int size) {
	FILE* file = fopen(filename, "rb");   
	if (file != NULL) { 
		// Файл уже есть
		printf("Use file %s\n", filename);
		fclose(file);
		return;
	}
	printf("Create file %s size %d ...", filename, size);
	file = fopen(filename, "wb");   
	if (file != NULL) { 
		for(int i = 0; i < size; i++) {
			fprintf(file, "%d\n", rand());
		}
		fclose(file);
	}
}

// Замер скорости чтения
void read_speed(const char* filename) {
	int count = 0;
	clock_t start = clock();
	FILE* file = fopen(filename, "rb");   
	if (file != NULL) { 
		int n = 0;
		bool store = false;
		char buffer[BUF_SIZE];
		size_t bytesRead = 0;
		while ((bytesRead = fread(buffer, 1, sizeof(buffer), file)) > 0) {
			count++;
		}
		fclose(file);
	}
	printf("ONLY READ: Count %d blocks Time %f sec.\n", count, (double)(clock() - start) / CLOCKS_PER_SEC);
}

// Однопоточный вариант
void read_ints(const char* filename) {
	clock_t start = clock();
	int count = 0;
	int check = 0;
	FILE* file = fopen(filename, "rb");   
	if (file != NULL) { 
		int n = 0;
		bool minus = false;
		bool store = false;
		bool overflow = false;
		char buffer[1024 * 8];
		size_t bytesRead = 0;
		while ((bytesRead = fread(buffer, 1, sizeof(buffer), file)) > 0) {
			char* end = buffer + bytesRead;
			for(char* cur = buffer; cur < end; cur++) {
				// считаем что все числа целые и разделены любыми разделителями
				if(*cur >= '0' && *cur <= '9') {
					int k = n * 10 + *cur - '0';
					if(!overflow) overflow = k < n;
					n = k;
					store = true;
				} else {
					if(store) {
						// тут сохраняем результат
						if(overflow) {
							printf("overflow\n");// переполнение
							overflow = false;
						} else {
							if(minus) {
								n = -n;
								minus = false;
							}
							check ^= n;
							//printf("%d\n", n);
							count++;
						}
						store = false;
						n = 0;
					}
					minus = (*cur == '-');
				}
			}
		}
		fclose(file);
	}
	printf("Read %d numbers CheckSum %X Time %f sec.\n", count, check, (double)(clock() - start) / CLOCKS_PER_SEC);
}

//Синхронный printf() из разных потоков
void mt_printf(const char* text, int value = -1) {
	static CRITICAL_SECTION cs;
	volatile static bool init = false;
	if(!init) {
		init = true;
		InitializeCriticalSectionAndSpinCount(&cs, 4000);
	}
	EnterCriticalSection(&cs);
	if(value == -1) {
		printf("%05d: %s\n", clock(), text);
	} else {
		printf("%05d: %s %d\n", clock(), text, value);
	}
	LeaveCriticalSection(&cs);
}

// Буфер
typedef struct {
	volatile long size;
	char data[BUF_SIZE];
} buf_t;

// Параметры потока чтения
typedef struct {
	const char* filename;
	HANDLE wait; // Event для ожидания
	volatile long wait_count; // Количество ожидающих
	CRITICAL_SECTION cs;
	buf_t buf[BUF_COUNT];
	volatile long buf_count; // Количество заполненных буферов
} param_t;


// Ожидание в пробуждением другого потока
void wait_one(param_t* param, HANDLE thread = NULL) {
	// Возобновление другого потока
	EnterCriticalSection(&param->cs);
	if(param->wait_count != 0) {
		SetEvent(param->wait); 
		Sleep(0);
		while(param->wait_count != 0) {
			//mt_printf("Warning: Sleep(1)");
			Sleep(1);
		}
	}
	// Ожидание
	ResetEvent(param->wait); 
	if(param->wait_count != 0) {
		mt_printf("Error: wake up");
		LeaveCriticalSection(&param->cs);
	} else {
		InterlockedExchangeAdd(&param->wait_count, 1);
		LeaveCriticalSection(&param->cs);
		if(thread) { // Дополнительно ожидать завершение потока
			HANDLE wait[2];
			wait[0] = param->wait;
			wait[1] = thread;
			if(WaitForMultipleObjects(2, wait, FALSE, 1000) == WAIT_TIMEOUT) {
				mt_printf("Error: wait timeout");
			}
		} else if(WaitForSingleObject(param->wait, 1000) == WAIT_TIMEOUT) {
			mt_printf("Error: wait timeout");
		}
		InterlockedExchangeAdd(&param->wait_count, -1);
	}
}

// Пробуждение спящих
void wake_up(param_t* param) {
	if(param->wait_count != 0 && param->buf_count > BUF_COUNT / 2) {
		EnterCriticalSection(&param->cs);
		if(param->wait_count != 0) {
			SetEvent(param->wait); 
			Sleep(0);
			while(param->wait_count != 0) {
				//mt_printf("Warning: Sleep(1)");
				Sleep(1);
			}
		}
		LeaveCriticalSection(&param->cs);
	}
}
// Поток чтения
unsigned __stdcall read_thread(void* par) {
	int count = 0; // счетчик запусков ожидания разбора
	param_t* param = (param_t*) par;
	FILE* file = fopen(param->filename, "rb");   
	if (file != NULL) { 
		long cur_buf = 0;
		size_t read = 0;
		// Чтение в buf[cur_buf]
		while ((read = fread(param->buf[cur_buf].data, 1, BUF_SIZE, file)) > 0) {
			// Установка размера прочитанного
			if(InterlockedExchange(&param->buf[cur_buf].size, read) != 0) {
				mt_printf("Error: Bufer not empty (1)");
				break;
			}
			#ifdef _DEBUG
			mt_printf("read end", cur_buf);
			#endif
			InterlockedExchangeAdd(&param->buf_count, 1);
			wake_up(param); // пробуждение разбора
			// следующий буфер
			cur_buf++;
			if(cur_buf == BUF_COUNT) cur_buf = 0;

			// Проверка что буфер пустой
			if(param->buf[cur_buf].size != 0) {
				// Ожидание пустого буфера
				#ifdef _DEBUG
				mt_printf("read wait", cur_buf);
				#endif
				wait_one(param);
				count++;
			}
			#ifdef _DEBUG
			mt_printf("read start", cur_buf);
			#endif
		}
		if(count > 0) mt_printf("read wait times", count);
	}
	//if(param->wait_count != 0) SetEvent(param->wait);
	_endthreadex(0);
	return 0;
}

void read_ints_mt(const char* filename) {
	clock_t start = clock();
	// Подготовка и запуск потока чтения
	param_t* param = (param_t*) calloc(1, sizeof(param_t));
	if(!param) {
		mt_printf("Error: no memory");
		return;
	}
	param->filename = filename;
	param->wait = CreateEvent(NULL, FALSE, FALSE, NULL);
	InitializeCriticalSection(&param->cs);
    unsigned th_id;
    HANDLE th = (HANDLE)_beginthreadex(NULL, 0, &read_thread, param, 0, &th_id );
	int wait_count = 0;
	// Разбор
	int n = 0;
	bool minus = false;
	bool store = false;
	bool overflow = false;
	int check = 0;
	int numbers_count = 0;
	size_t cur_buf = 0;
	buf_t* buf = NULL;
	while(1) {
		if(param->buf[cur_buf].size == 0) { // Нечего разбирать
			if(WaitForSingleObject(th, 0) != WAIT_TIMEOUT) break; // Поток приема завершен
			// Ожидание чтения
			#ifdef _DEBUG
			mt_printf("parse wait", cur_buf);
			#endif
			wait_count++;
			wait_one(param, th);
		}
		#ifdef _DEBUG
		mt_printf("parse start", cur_buf);
		#endif
		// Разбор буфера
		char* end = param->buf[cur_buf].data + param->buf[cur_buf].size;
		for(char* cur = param->buf[cur_buf].data; cur < end; cur++) {
			// считаем что все числа целые и разделены любыми разделителями
			if(*cur >= '0' && *cur <= '9') {
				int k = n * 10 + *cur - '0';
				if(!overflow) overflow = k < n;
				n = k;
				store = true;
			} else {
				if(store) {
					// тут сохраняем результат
					if(overflow) {
						mt_printf("overflow");// переполнение
						overflow = false;
					} else {
						if(minus) {
							n = -n;
							minus = false;
						}
						check ^= n;
						//printf("%d\n", n);
						numbers_count++;
					}
					store = false;
					n = 0;
				}
				minus = (*cur == '-');
			}
		}
		// Пометка буфера разобранным
		if(InterlockedExchange(&(param->buf[cur_buf].size), 0) == 0) {
			if(WaitForSingleObject(th, 0) != WAIT_TIMEOUT) break; // Поток приема завершен
			mt_printf("Error: size == 0 (2)");
			break;
		}
		InterlockedExchangeAdd(&param->buf_count, -1);
		#ifdef _DEBUG
		mt_printf("parse end", cur_buf);
		#endif
		// Переход на следующий буфер
		cur_buf++;
		if(cur_buf == BUF_COUNT) cur_buf = 0;
	}
	WaitForSingleObject(th, INFINITE);
	printf("MT Read %d numbers CheckSum %X Wait %d times Time %f sec.\n", numbers_count, check, wait_count, (double)(clock() - start) / CLOCKS_PER_SEC);
	CloseHandle(th);
	CloseHandle(param->wait);
	DeleteCriticalSection(&param->cs);
	free(param);

}


int main(int argc, char* argv[])
{
	char file[] = "big.txt";
	create_file(file, 1000000000);
	//char file[] = "mini.txt";
	//create_file(file, 100000000);
	read_speed(file);
	read_ints(file);
	read_ints_mt(file);

	return 0;
}

С синхронизацией устал разбираться. Потоки догоняют друг-друга, один еще не успел в ожидание встать, второй уже все закончил и будит первого.
Вчера был вариант с двумя эвентами. По одному на каждый поток. Так он и не заработал. В итоге сделал один эвент на двоих и пробуждение второго если он спит во время усыпления первого. Но и то какой-то изврат получился. Даже Sleep(1) пришлось воткнуть. Функции wait_one() и wake_up()

Может кто идею подкинет как синхронизацию организовать?
3 дек 15, 17:51    [18509999]     Ответить | Цитировать Сообщить модератору
 Re: как быстрее всего прочесть большой файл с числами, каждое с новой строки?  [new]
mayton
Member

Откуда: loopback
Сообщений: 40400
Dima T, большое спасибо за бенчмарки. Сходу могу предположить что синхронизация происходит
слишком часто. Возможно имеет смысл увеличить размер чанка (блока) ?
3 дек 15, 17:58    [18510047]     Ответить | Цитировать Сообщить модератору
 Re: как быстрее всего прочесть большой файл с числами, каждое с новой строки?  [new]
Dima T
Member

Откуда:
Сообщений: 13622
Размеры тут
#define BUF_COUNT 128
#define BUF_SIZE 1024 * 8

BUF_COUNT кол-во буферов, BUF_SIZE размер одного
Работает по кольцу: чтение заполняет по кругу пока на заполненный не наткнется, разбор - разбирает пока на пустой не наткнется.

Забыл кол-во остановок (усыплений) добавить. Перетестил на i7 - оба потока по 4650 раз засыпали. Второй комп недоступен. Завтра только перемерю.

ИМХУ надо эту корявость в синхронизации менять. Вопрос на что? С виду простая задачка, но весь мозг об нее сломал.
3 дек 15, 18:54    [18510336]     Ответить | Цитировать Сообщить модератору
 Re: как быстрее всего прочесть большой файл с числами, каждое с новой строки?  [new]
kolobok0
Member

Откуда:
Сообщений: 1937
mayton,

оптимальный размер блока будет когда
время чтения блока = времени обработки этого блока


(круглый)
ЗЫ
И это апсолютно не максимальный буффер!!!
3 дек 15, 23:40    [18511386]     Ответить | Цитировать Сообщить модератору
 Re: как быстрее всего прочесть большой файл с числами, каждое с новой строки?  [new]
Dima T
Member

Откуда:
Сообщений: 13622
Перемерил на i5:
со 128 буферами по 8 Кб чтение засыпало 313 раз разбор 6286
+ сделал 128 по 64 Кб Вот лог трех запусков

Use file big.txt
ONLY READ: Count 86380 blocks Time 57.236000 sec.
Read 1000000000 numbers CheckSum 4231 Time 57.205000 sec.
MT Read 1000000000 numbers CheckSum 4231 Wait 680 times Time 57.034000 sec.

Use file big.txt
ONLY READ: Count 86380 blocks Time 58.854000 sec.
Read 1000000000 numbers CheckSum 4231 Time 57.595000 sec.
MT Read 1000000000 numbers CheckSum 4231 Wait 701 times Time 58.828000 sec.

Use file big.txt
ONLY READ: Count 86380 blocks Time 64.600000 sec.
Read 1000000000 numbers CheckSum 4231 Time 60.949000 sec.
MT Read 1000000000 numbers CheckSum 4231 Wait 736 times Time 54.694000 sec.

Все три варианта сравнялись ))
Если в кэш не влазит и читается с HDD - время чтения величина переменная. Замерять тут что-то бесполезно.

PS Синхронизация один раз сглючила. Остались там какие-то косяки.
4 дек 15, 07:34    [18511803]     Ответить | Цитировать Сообщить модератору
 Re: как быстрее всего прочесть большой файл с числами, каждое с новой строки?  [new]
Dima T
Member

Откуда:
Сообщений: 13622
Понял в чем у меня проблема с синхронизацией. Думал что раз разбудили поток - значит ему есть что делать, а случаи если нечего - считал ошибкой.
В общем самый первый вариант был правильный. Просто не хватало проверки после пробуждения.

Результаты теста с буфером 64 Кб для МТ 128 буферов
На i7 (4 ядра) RAM 32 Гб
ТестВремя сек.
Только чтение1.24
Однопоточный разбор14.7
Многопоточный13.6

Уходов в спячку: чтение - 1150, разбор - 5
На i5 (2 ядра + HT) RAM 4 Гб
ТестВремя сек.
Только чтение55
Однопоточный разбор55
Многопоточный55

Уходов в спячку: чтение - 0, разбор - 650

+ Исходник
#include <windows.h>
#include <time.h>
#include <process.h>
#include <stdio.h>

#define BUF_COUNT 128
#define BUF_SIZE 1024 * 64

// Создание файла
void create_file(const char* filename, int size) {
	FILE* file = fopen(filename, "rb");   
	if (file != NULL) { 
		// Файл уже есть
		printf("Use file %s\n", filename);
		fclose(file);
		return;
	}
	printf("Create file %s size %d ...\n", filename, size);
	file = fopen(filename, "wb");   
	if (file != NULL) { 
		for(int i = 0; i < size; i++) {
			fprintf(file, "%d\n", rand());
		}
		fclose(file);
	}
}

// Замер скорости чтения
void read_speed(const char* filename) {
	int count = 0;
	clock_t start = clock();
	FILE* file = fopen(filename, "rb");   
	if (file != NULL) { 
		int n = 0;
		bool store = false;
		char buffer[BUF_SIZE];
		size_t bytesRead = 0;
		while ((bytesRead = fread(buffer, 1, sizeof(buffer), file)) > 0) {
			count++;
		}
		fclose(file);
	}
	printf("ONLY READ: Count %d blocks Time %f sec.\n", count, (double)(clock() - start) / CLOCKS_PER_SEC);
}

// Блочный парсер
class parser {
	int n;
	bool minus;
	bool store;
	bool overflow;
public:
	int count;
	int check;

	parser() {
		n = 0;
		count = 0;
		check = 0;
		minus = false;
		store = false;
		overflow = false;
	}

	void parse_block(const char* data, int size) {
		const char* end = data + size;
		for(const char* cur = data; cur < end; cur++) {
			// считаем что все числа целые и разделены любыми разделителями
			if(*cur >= '0' && *cur <= '9') {
				int k = n * 10 + *cur - '0';
				if(!overflow) overflow = k < n;
				n = k;
				store = true;
			} else {
				if(store) {
					// тут сохраняем результат
					if(overflow) {
						printf("overflow\n");// переполнение
						overflow = false;
					} else {
						if(minus) {
							n = -n;
							minus = false;
						}
						check ^= n;
						//printf("%d\n", n);
						count++;
					}
					store = false;
					n = 0;
				}
				minus = (*cur == '-');
			}
		}
	}
};

// Однопоточный вариант
void read_ints(const char* filename) {
	clock_t start = clock();
	FILE* file = fopen(filename, "rb");   
	parser p;
	if (file != NULL) { 
		char buffer[BUF_SIZE];
		size_t bytesRead = 0;
		while ((bytesRead = fread(buffer, 1, sizeof(buffer), file)) > 0) p.parse_block(buffer, bytesRead);
		fclose(file);
	}
	printf("Read %d numbers CheckSum %X Time %f sec.\n", p.count, p.check, (double)(clock() - start) / CLOCKS_PER_SEC);
}

// printf()
void mt_printf(const char* text, int value = -1) {
	if(value == -1) {
		printf("%05d: %s\n", clock(), text);
	} else {
		printf("%05d: %s %d\n", clock(), text, value);
	}
}

// Буфер
typedef struct {
	volatile long size;
	char data[BUF_SIZE];
} buf_t;

// Параметры потока чтения
typedef struct {
	const char* filename;
	HANDLE read_wait; // Event для ожидания чтения
	HANDLE parse_wait; // Event для ожидания разбора
	buf_t buf[BUF_COUNT];
	volatile long buf_count; // Количество заполненных буферов
	volatile long read_wait_count; // Счетчик засыпаний чтения
	volatile long read_result; // Результат завершения чтения
} param_t;

// Поток чтения
unsigned __stdcall read_thread(void* par) {
	param_t* param = (param_t*) par;
	FILE* file = fopen(param->filename, "rb");   
	if (file != NULL) { 
		long cur_buf = 0;
		size_t read = 0;
		while (1) {
			// Проверка что буфер пустой
			if(param->buf[cur_buf].size != 0) {
				// Ожидание пустого буфера
				if(WaitForSingleObject(param->read_wait, 1000) == WAIT_TIMEOUT) {
					mt_printf("Error: read wait timeout");
					break;
				}
				if(param->buf[cur_buf].size != 0) continue;
				param->read_wait_count++;
			}
			// Чтение в buf[cur_buf]
			size_t read = fread(param->buf[cur_buf].data, 1, BUF_SIZE, file);
			if(read == 0) { // Файл прочитан
				param->read_result = 1;
				break;
			}
			// Установка размера прочитанного
			if(InterlockedExchange(&param->buf[cur_buf].size, read) != 0) {
				mt_printf("Error: Bufer not empty (1)");
				break;
			}
			// пробуждение разбора если занято более половины буферов
			if(InterlockedExchangeAdd(&param->buf_count, 1) >= BUF_COUNT/2) {
				SetEvent(param->parse_wait);
			}
			// следующий буфер
			cur_buf++;
			if(cur_buf == BUF_COUNT) cur_buf = 0;
		}
	}
	_endthreadex(0);
	return 0;
}

void read_ints_mt(const char* filename) {
	clock_t start = clock();
	parser p;
	// Подготовка и запуск потока чтения
	param_t* param = (param_t*) calloc(1, sizeof(param_t));
	if(!param) {
		mt_printf("Error: no memory");
		return;
	}
	param->filename = filename;
	param->read_wait = CreateEvent(NULL, FALSE, FALSE, NULL);
	param->parse_wait = CreateEvent(NULL, FALSE, FALSE, NULL);
    unsigned th_id;
	HANDLE waits[2];
	waits[0] = param->parse_wait;
    waits[1] = (HANDLE)_beginthreadex(NULL, 0, &read_thread, param, 0, &th_id );
	int wait_count = 0;
	// Разбор
	size_t cur_buf = 0;
	buf_t* buf = NULL;
	while(1) {
		if(param->buf[cur_buf].size == 0) { 
			// Нечего разбирать
			if(WaitForSingleObject(waits[1], 0) != WAIT_TIMEOUT) break; // Поток приема завершен
			// Ожидание чтения
			if(WaitForMultipleObjects(2, waits, FALSE, 1000) == WAIT_TIMEOUT) {
				mt_printf("Error: parse wait timeout");
				break;
			}
			if(param->buf[cur_buf].size == 0) continue;
			wait_count++;
		}
		// Разбор буфера
		p.parse_block(param->buf[cur_buf].data, param->buf[cur_buf].size);
		// Пометка буфера разобранным
		if(InterlockedExchange(&(param->buf[cur_buf].size), 0) == 0) {
			mt_printf("Error: size == 0 (2)");
			break;
		}
		// пробуждение чтения если занято менее половины буферов
		if(InterlockedExchangeAdd(&param->buf_count, -1) <= BUF_COUNT/2) {
			SetEvent(param->read_wait);
		}
		// Переход на следующий буфер
		cur_buf++;
		if(cur_buf == BUF_COUNT) cur_buf = 0;
	}
	WaitForSingleObject(waits[1], INFINITE); // Ожидание завершения потока чтения
	if(param->read_result != 1) {
		mt_printf("Error: read not all");
	} else if(param->buf_count != 0) {
		mt_printf("Error: parse not all");
	}
	printf("MT Read %d numbers CheckSum %X Wait (R/P) %d/%d Time %f sec.\n", p.count, p.check, param->read_wait_count, wait_count, (double)(clock() - start) / CLOCKS_PER_SEC);
	CloseHandle(waits[1]);
	CloseHandle(param->parse_wait);
	CloseHandle(param->read_wait);
	free(param);
}


int main(int argc, char* argv[])
{
	printf("\nTest: size %d Kb count %d  Compile %s %s\n", BUF_SIZE / 1024, BUF_COUNT, __DATE__, __TIME__);
	char file[] = "big.txt";
	create_file(file, 1000000000);
	read_speed(file);
	read_ints(file);
	read_ints_mt(file);

	return 0;
}


PS ИМХУ бесполезно последовательное чтение параллелить: если данные в кэше - быстро прочитается, если с диска - ОС сама фоном упреждающее чтение делает.
4 дек 15, 11:56    [18512905]     Ответить | Цитировать Сообщить модератору
 Re: как быстрее всего прочесть большой файл с числами, каждое с новой строки?  [new]
mayton
Member

Откуда: loopback
Сообщений: 40400
Dima T
PS ИМХУ бесполезно последовательное чтение параллелить: если данные в кэше - быстро прочитается, если с диска - ОС сама фоном упреждающее чтение делает.

Есть мысли (только касамемо Windows)
1) Втопку упреждающее.
2) Покурить Джефри Рихтера. На тему Windows I/O
3) Отказаться от FILE*,fopen,fread и перейти к Windows-specific функциям которые описаны в MSDN.
4) Перетестировать заново.
4 дек 15, 12:21    [18513139]     Ответить | Цитировать Сообщить модератору
 Re: как быстрее всего прочесть большой файл с числами, каждое с новой строки?  [new]
mayton
Member

Откуда: loopback
Сообщений: 40400
Дима sorry я по прежнему озабочен чортовой пендосской медициной. Горят сроки.
И не успеваю даже модерировать плюсы. Так что читать твои сорцы
буду только в СБ-ВС. I think...
4 дек 15, 12:28    [18513197]     Ответить | Цитировать Сообщить модератору
 Re: как быстрее всего прочесть большой файл с числами, каждое с новой строки?  [new]
Dima T
Member

Откуда:
Сообщений: 13622
ИМХУ быстрее не станет. Нечего тут больше оптимизировать. Забыл померить для второго случая (файл в кэш не влазит): Фар копирует в nul за 54 сек, тесты работают 55. Т.е. с учетом погрешностей примерно одинаково.
4 дек 15, 12:52    [18513392]     Ответить | Цитировать Сообщить модератору
 Re: как быстрее всего прочесть большой файл с числами, каждое с новой строки?  [new]
Зимаргл
Guest
mayton
Dima T
PS ИМХУ бесполезно последовательное чтение параллелить: если данные в кэше - быстро прочитается, если с диска - ОС сама фоном упреждающее чтение делает.

Есть мысли (только касамемо Windows)
1) Втопку упреждающее.
2) Покурить Джефри Рихтера. На тему Windows I/O
3) Отказаться от FILE*,fopen,fread и перейти к Windows-specific функциям которые описаны в MSDN.
4) Перетестировать заново.

Там флажки есть на опережающее чтение итп
4 дек 15, 13:10    [18513525]     Ответить | Цитировать Сообщить модератору
 Re: как быстрее всего прочесть большой файл с числами, каждое с новой строки?  [new]
mayton
Member

Откуда: loopback
Сообщений: 40400
Фух... заскочил на минутку.

Челы качните http://www.hdtune.com/ и посмотрите sequential read/write speed

Убежал...
4 дек 15, 14:37    [18514245]     Ответить | Цитировать Сообщить модератору
 Re: как быстрее всего прочесть большой файл с числами, каждое с новой строки?  [new]
m_Sla
Member

Откуда:
Сообщений: 2702
идеи по парсеру
+
int table[16][16][16];

table[0][0][0] = 0;
...
table[1][2][3] = 123;
...
table[9][9][9] = 999;

int char_to_int_table(char str[])
{
    int  result=0;

    int a = str[0] - '0';
    int b = str[1] - '0';
    int c = str[2] - '0';

    result = table[ a ][ b ][ c ];

    return result;
}
уменьшаем кол-во умножений в 3 раза, но усложняется сам парсер
9 дек 15, 08:36    [18533226]     Ответить | Цитировать Сообщить модератору
 Re: как быстрее всего прочесть большой файл с числами, каждое с новой строки?  [new]
Dima T
Member

Откуда:
Сообщений: 13622
m_Sla
уменьшаем кол-во умножений в 3 раза, но усложняется сам парсер

ИМХУ не взлетит. Умножение целых не такая уж и тяжелая операция.
Можно просто убрать умножение. Заменил n*10 на n<<3 + n<<1.
Затестил. Вообще ничего не изменилось. Время было 13.51 сек, стало 13.49. Это погрешности измерения. Возможно оптимизатор сам заменил и умножения изначально не было.
9 дек 15, 09:01    [18533318]     Ответить | Цитировать Сообщить модератору
 Re: как быстрее всего прочесть большой файл с числами, каждое с новой строки?  [new]
Изопропил
Member

Откуда:
Сообщений: 31078
m_Sla
уменьшаем кол-во умножений в 3 раза,

ага, индексация многомерного массива без умножений обходится

PS на интел архитектуре умножение на 10 обычно без команды умножения делается
9 дек 15, 09:04    [18533328]     Ответить | Цитировать Сообщить модератору
 Re: как быстрее всего прочесть большой файл с числами, каждое с новой строки?  [new]
Dima T
Member

Откуда:
Сообщений: 13622
Изопропил
ага, индексация многомерного массива без умножений обходится

В данном случае обойдется: *4 легко заменяется на <<2
9 дек 15, 09:12    [18533369]     Ответить | Цитировать Сообщить модератору
 Re: как быстрее всего прочесть большой файл с числами, каждое с новой строки?  [new]
m_Sla
Member

Откуда:
Сообщений: 2702
Изопропил
m_Sla
уменьшаем кол-во умножений в 3 раза,

ага, индексация многомерного массива без умножений обходится

PS на интел архитектуре умножение на 10 обычно без команды умножения делается
там два умножения на 16, делается сдвигами

а на 10 как умножается, на lea ?
9 дек 15, 09:14    [18533373]     Ответить | Цитировать Сообщить модератору
 Re: как быстрее всего прочесть большой файл с числами, каждое с новой строки?  [new]
m_Sla
Member

Откуда:
Сообщений: 2702
затестил, аппаратное умножение быстро работает
Intel Pentium CPU G2020
2,559 попугая
           asm{
           mov eax,k
           add eax,eax
           lea eax,[4*eax+eax]
           mov k, eax
           }
           

2,762 попугая           
           asm{
           mov eax,k
           imul eax,eax,10
           mov k, eax
           }
           

2,62 попугая
           asm{
           mov eax,k
           mov edx,k
           shl eax,3
           add edx,edx
           add eax,edx
           mov k, eax
           }
9 дек 15, 10:01    [18533556]     Ответить | Цитировать Сообщить модератору
 Re: как быстрее всего прочесть большой файл с числами, каждое с новой строки?  [new]
Изопропил
Member

Откуда:
Сообщений: 31078
m_Sla
а на 10 как умножается, на lea ?

оно самое
9 дек 15, 14:27    [18535440]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: 1 2 3 4 5      [все]
Все форумы / C++ Ответить