Одновременная работа с большим числом файлов. , ...которые не умещаются в памяти.

Всем привет, поделитесь опытом

Есть 1000 сортированных массивов в 1000 файлов по 10 Mb каждый.
Надо объединить их сортировкой слиянием.

Открываю все файлы на чтение (CreateFileA) и построчно читаю их - очень долго.
Загрузить в память сразу 1000 * 10Mb не получается, ограничение windows 2Gb на процесс.

Стоит ли грузить в память по несколько штук, объединять, а затем объединять объединённые?
...или кеширование файлов windows и так подгружает файлы в память достаточно большими кусками?

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

Сообщение отредактировано: Akina - 24.09.19, 08:16

FateFlex
Грузите в память по 500 мБ. Соответственно по 50 файлов.
1000/50=20
И далее останется 20 файлов. И их сливаете их читая построчно.

Цитата FateFlex @ 24.09.19, 07:53

...или кеширование файлов windows и так подгружает файлы в память достаточно большими кусками?

Он подгружает столько сколько вы укажите. Обычно это 4 или 8 кб, реже 64 кб.

Но суть не в этом, а в том что 1000 файлов.


Akina

Цитата Akina @ 24.09.19, 08:15

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

Так вы ОС говорите перемести головку 1000 раз и каждый раз в разное место и так по кругу. ОС не знает когда какие запросы поступят от приложений и планировать не может поэтому обслуживает в порядке живой очереди.

Начнём с того что постановку на чтение вы делаете последовательно. Новую порцию запрашиваете после чтения предыдущий. Если бы вы параллельно ставили запросы тогда бы ОС могла планировать. Путём перестановки запросов и группировки близко расположенных.
Если запросы последовательные, то ОС не может предсказать ничего. Просто не существует такого алгоритма. Можно использовать марковские цепи но для них нужна статистика десятки, а то и тысячи запросов. К тому времени пока вы соберёте такую статистику все файлы будут прочитаны.

Допустим у вас асинхронное чтение. Но проблема в том, что вы читаете 1000 файлов из середины. Значит запрашиваемые кластеры будут находится на расстояние в 10 мб всё время. Поэтому не будет никаких соседних кластеров.

Жёсткий диск мог бы спланировать своё чтение если бы файлы лежали на одной радиане(или цилиндре). Но насколько мне известно это либо вовсе не реализовано либо реализовано только в серверных дисках с интерфейсом SCSI.

Цитата Pavia @ 24.09.19, 17:14

Так вы ОС говорите перемести головку 1000 раз и каждый раз в разное место и так по кругу. ОС не знает когда какие запросы поступят от приложений и планировать не может поэтому обслуживает в порядке живой очереди.

Насколько я знаю, уже практически во всех ОС реализован лифт чтения-записи, а не тупая FIFO-очередь. Я уж не говорю о том, что гарантии, что все файлы нефрагментированы и лежат последовательно, отсутствует как класс. Так что рандом обеспечен практически гарантированно, причём с самого начала. Но зато чтение сразу всех избавляет от буферизации промежуточных результатов на диск и многопроходности сортировки. Для 1000 файлов можно сразу зачитать по мегабайту с каждого, и подчитывать по полмегабайта, когда необработанный остаток станет меньше полумегабайта. К тому же вряд ли данные расположены в файлах очень равномерно - так что почти сразу подчитывание превратится в рандом. И, кстати, уже к моменту первого подчитывания на диск будет сброшено порядка 250 мегабайт отсортированных данных.

Нет, если сразу ориентроваться на двухпроходную сортировку - то да, можно работать с порциями по 32, скажем, файла, и тогда на первом проходе их можно считывать все целиком, и лишь на втором проходе буферизовать. Но это удваивает объём как чтения, так и записи...

M

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

FateFlex, и я пожалуй вставлю своих пять копеек ... Задача поставлена нечетко!!!
Что значит "массивов"??? Если файлы текстовые - это один колинкор, если файлы имеют записи равной длины - это второй. В первом случае я бы порекомендовал провести предварительную индексацию (смещение+длина), в втором случае я бы порекомендовл прислушаться к советам Анины... С маленькими дополнениями. А именно:

1) Не забирать у ОС более 85% оперативы - она это не любит, и начинает в панике сбрасывать страницы на диск (различные), типа на упреждение. А мой выбор вааще 50% и не выше. Да и смысл????!!! Дисковая подсистема работает значительно тормознее вычислений. Вывод - читаем по необходимости.
2) Читаем не по Мегобайтам а N-записям - чтобы потом не дочитывать

Далее вариативно. Я бы создал 10 потоков, которые обслуживают по 100 фалов. "Обслуживают" - это значит подгружают по необходимости пулы записей в своих 100 стеках. M-потокв занимается выборкой "вершин" стеков и их упорядочиванием.

Ну и самый важный вопрос!!! Если задача не периодическая - нафик оптимизацию. Главное контроль памяти. Если разовая - запускай, ложись спать, сходи в бассейн, покушай суши ... и получи результат

Все ИМХО.

Цитата Pavia @ 24.09.19, 17:14

Он подгружает столько сколько вы укажите.

Попробую увеличить до мегабайта.

Цитата Pavia @ 24.09.19, 17:14

Так вы ОС говорите перемести головку 1000 раз и каждый раз в разное место и так по кругу.

С точки зрения железа не подумал у меня 8 процессов каждый свои условные 1000 файлов объединяют для винта это ад похоже. Буду последовательно файлы читать.

Цитата Akina @ 24.09.19, 20:37

Я уж не говорю о том, что гарантии, что все файлы нефрагментированы и лежат последовательно, отсутствует как класс.

По счастливому совпадению, как раз так, все лежат друг за другом и не фрагментированы.

Цитата JoeUser @ 24.09.19, 20:53

Что значит "массивов"?

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

Цитата JoeUser @ 24.09.19, 20:53

Если задача не периодическая - нафик оптимизацию.

Почти не периодическая, но в реальности это около 10.000 файлов от 1 Mb до 100 Gb, поэтому придётся съесть очень много суши, запить бассейном и завалиться как спящая красавица.

Значит выбор между числом проходов сортировки и числом циклов чтения.

Цитата JoeUser @ 24.09.19, 20:53

Я бы создал 10 потоков, которые обслуживают по 100 фалов. "Обслуживают" - это значит подгружают по необходимости пулы записей в своих 100 стеках. M-потокв занимается выборкой "вершин" стеков и их упорядочиванием.

Может получиться "вечный кайф".
Даже если предположить, что все файлы не фрагментированы,
всё равно, при одновременном чтении больших файлов из разных
потоков будут активно использоваться движения блока головок диска.
Т.е. возможна ситуация, когда некий файл начали читать, система
прервала поток, передала время другому. Его файлы "далеко", потащили
туда блок головок электро-механической операцией. Начали читать, и опять.
Поток прерван, другой поток хочет почитать файлы, которые "далеко".
---
При такой реализации будет истрачено много времени из-за медленных операций
электро-механики.
я бы постарался обойтись одним рабочим потоком.

А если попробовать не изобретать велосипед, а взять напрокат?
Читаем полностью файл, парсим и пишем в таблицу базы данных с “правильными» индексами. Повторяем чтение остальных файлов.
В таблице данные расположены упорядоченно.

Цитата Pavia @ 24.09.19, 19:27

Он подгружает столько сколько вы укажите. Обычно это 4 или 8 кб, реже 64 кб.

А как это задать? Поверхностный гуглинг ничего не дал, ключевые слова подскажите хотя бы

Цитата MIF @ 26.09.19, 13:37

Читаем полностью файл, парсим и пишем в таблицу базы данных с “правильными» индексами.

А как рассчитать эти "правильные" индексы ?
Алгоритмы сортировки этого не делают.
Они сравнивают два объекта в соответствии
с критерием и меняют местами в массиве.
Индексы массива выбираются в соответствии с алгоритмом
сортировки.
---
Можно попытаться изобрести число, соответствующее значимости объекта.
Тогда "да". Можно будет в индексном массиве указать файл, строку, число.
Сразу просится простой вариант - рассматриваем код символа как
коэф. числа в системе счисления. Если код символа выбираем в пределах
0-255, тогда это система счисления по основанию 256.
Ещё надо знать максимальный размер строки и быть уверенным, что разрядной
сетки целого числа хватит для вычисления максимального значения.
Тогда может получится - для каждой строки можно точно вычислить её "вес".
Поскольку текстовые строки содержат не весь набор кодов, то возможна экономия.
Основание системы счисления - это размер алфавита.

Добавлено 27.09.19, 22:41

Цитата FateFlex @ 26.09.19, 13:39

Цитата Pavia @ 24.09.19, 19:27

Он подгружает столько сколько вы укажите. Обычно это 4 или 8 кб, реже 64 кб.

А как это задать?

Можно так:
1. Для чтения файла делаем специальный объект - нам понадобяться
не только методы, но и свойства.
2. Будем использовать - "число байт в буфере", "индекс-указатель на актуальный байт".
3. При создании объекта будем указывать размер буфера чтения.
Для удобства предусмотрим установку параметра по умолчанию.
3. Открываем фал на чтение - объём считанного в буфере - 0, индекс 0.
4. Имеется метод типа "GetByte".
5. Просто вызываем его. Он работает так:
Проверим наличие данных в буфере - если данные есть, читаем 1 байт из буфера, уменьшаем
значение "число байт в буфере", увеличиваем "индекс-указатель на актуальный байт".
Если данных нет, читаем из файла порцию, равную размеру буфера, для его
полного заполнения. По результатам устанавливаем переменные
"число байт в буфере"=(действительно считанное),
"индекс-указатель на актуальный байт"=0
6. Так читаем и обрабатываем весь файл.
7. Если надо читать строки или другие "порции", используем методы на основе "GetByte".
---
С таким объектом удобно проводить опыты по определению максимальной скорости работы
от величины буфера.
---
Для записи в файл делаем аналогичный алгоритм.
Т.е. пишем не в файл и не в буфер. Пишем в "объект".
Который сам решает, когда весь имеющийся буфер с данными сбрасывать на диск.
---
Оба варианта я реализовал, постоянно пользуюсь, работает отлично.
Плюс особенно хорошо заметен на "слабых" системах.

Сообщение отредактировано: ЫукпШ - 28.09.19, 12:34

Цитата ЫукпШ @ 26.09.19, 11:54

Может получиться "вечный кайф".

Это справедливо для единственного HDD.
Для RAID-массива и SSD картина будет другая.

Цитата JoeUser @ 28.09.19, 11:32

Цитата ЫукпШ @ 26.09.19, 11:54

Может получиться "вечный кайф".

Это справедливо для единственного HDD.
Для RAID-массива и SSD картина будет другая.

Да. Но как сложаться обстоятельства в конкретной системе
в конкретное время не известно заранее.
---
Один раз я подобное видел и хотел посмотреть, чем закончится.
После около 4-5 часов "наблюдений" просто надоело.

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

Цитата JoeUser @ 28.09.19, 11:51

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

Например, так:
1. Одному Читателю дали буфер 128К, другому - 192К
2. Писателю дали 288К
Хотя я подозреваю, что это не обязательно, но не трудно и можно попробовать.

3. Нам известно, что данные файлов уже отсортированы. Допустим, сначала - "минимум".
4. читаем строку читателя 1 и строку читателя 2.
5. Сравниваем.
6. Писатель пишет минимум в результат.
7. Из читателя, данные которого пошли в результат, добываем ещё строку.
8. К пункту 5.
---
Приблизительно так, можно слить 2 файла в один.
Вот и всё.
Делаем так, пока не останется один файл.

Сообщение отредактировано: ЫукпШ - 28.09.19, 12:43

ЫукпШ, стоп-стоп-стоп. Не забываем что у современных HDD есть аппаратный буфер порядка 32Mb и технологии упреждающего чтения и отложенной записи. Так что чтение-запись уже явно не килобайтами.

Цитата JoeUser @ 28.09.19, 13:25

ЫукпШ, стоп-стоп-стоп. Не забываем что у современных HDD есть аппаратный буфер порядка 32Mb и технологии упреждающего чтения и отложенной записи.

По моему, это "ни о чём".
Эти средствами пользуется сам HDD.
Далее идёт система, в которой много процессов и потоков.
Наш номер тут 48, и рассчитывать на это нечего.