1. это не merge sort, там есть вставка в середину.

2. а это вообще работает на объеме файла, который не влазит в память? Т.е. у тестеров оно могло просто свалиться в использование файла подкачки.

3. asynс здесь могут сослужить очень плохую службу, вместо этого руками запускать потоков (тасков) ровно столько, сколько есть ядер (для серверного кода это неприемлемо, но тут у нас выдуманное окружение).

В соревнованиях по сортировке (есть и такие, да) при merge sort вроде бы используют heap.
Типа, делать "heapify" оказывается быcтрее, чем из раза в раз пробегать по списку указателей на сегмент и выбирать сегмент с наименьшей головой.

Здравствуйте, AtCrossroads, Вы писали:

Вы же это мне отвечали, на стартовое сообщение, верно?

AC>1. это не merge sort, там есть вставка в середину.

Где?

AC>2. а это вообще работает на объеме файла, который не влазит в память? Т.е. у тестеров оно могло просто свалиться в использование файла подкачки.

А почему не должно? в какой момент времени в памяти может оказаться количество данных, пропорциональное размеру входного файла?

AC>3. asynс здесь могут сослужить очень плохую службу, вместо этого руками запускать потоков (тасков) ровно столько, сколько есть ядер (для серверного кода это неприемлемо, но тут у нас выдуманное окружение).

_FR>Вы же это мне отвечали, на стартовое сообщение, верно?
На стоартовое.

_FR>Где?
_FR>А почему не должно? в какой момент времени в памяти может оказаться количество данных, пропорциональное размеру входного файла?

Тогда я фигово понял ваше решение.

"Правильное" решение, думаю, такое:

1. Читаем файл по секциям, каждую секцию параллельно сортируем обычным List.Sort, сохраняем в новые файлы
1.1. Читаем и пишем в одином потоке;
1.2. Сортируем в потоках, равных количеству ядер (скорее всего с учетом гипер-трединга);

2. Делаем merge sort, т.е. пока все секции не кончатся, выбираем наилучшую.

2.1 Как хорошо организовать буферизацию тут я не знаю, но, вероятно, поможет mmf, особенно если они "совместимы" с Memory и Span. Типа, может можно легко избежать аллоцирования managed-памяти для каждой строки.

2.2. Если секций много, вероятно, вместо того, чтобы каждый раз из списка выбирать лучшую секцию, можно использовать heap. Heap, естественно, делать каннонично, на массиве, а не дереве с указетелями

Здравствуйте, AtCrossroads, Вы писали:

AC>"Правильное" решение, думаю, такое:
AC>1. Читаем файл по секциям, …

А как это? Что в вашем понимании секция и как их найти в файле?

AC>>"Правильное" решение, думаю, такое:
AC>>1. Читаем файл по секциям, …

_FR>А как это? Что в вашем понимании секция и как их найти в файле?

Завести очередь несортированных списков List<List<string>>. Запустить поток, который этот список пополняет, посто последовательно читая из stream.
Запустить поток, который смотрит на этот списко и запускает потоки сортировки (не больше, чем ядер). Отсортированные списки строк складываются в новую очередь.
Первый поток поток (который читает), пишет отсортированные списки во временные файлы (вероятно, совмещать чтение и запись именно в одном потоке не обязательно; цель, не перемежать обращения к диску).

Может быть можно сделать код проще: запускать одновременно тасков по числу ядрер.
В каждом таске "захватываем чтение-запись" (просто lock на любом объекте), читаем кусок из stream.
Сортируем.
"Захватываем чтение-запись", пишем во временный файл.

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

Наверное, так.

Здравствуйте, _FRED_, Вы писали:

_FR>Решение моё интервьюеров не удовлетворило, говорят, что очень медленно работает: как обычно, у меня на лаптопе как раз всё летает, файл в 1Г сортируется за 13 с небольшим секунд, а у ревьюеров получилось 130c на файл 1 гиг Так мне написали.
Диски могут быть разные (особенно весело, если тестируется в docker/kubernetes с настройками по-умолчанию, там все оооочень медленно). И локальная память. Сколько у вас на машине памяти? Вдруг окажется, что все записанные файлы потом читаются не с диска, а из дискового кэша? Хорошо бы было писать на диск. За неимением диска попробуйте хотя бы флешку (внешний жесткий диск будет идеальным решением). Там случайный доступ не так плох, как в блинных конструкциях, но скорость — низкая. Если промахнулись с буферами, может быть заметно. И если на машине много памяти — перезагружайтесь между этапами (генерация->разбиение->слияние), чтобы данные из кэша удалялись. Или отмонтируйте/примонтируйте ее, только сравните скорость с перезагрузкой.

_FR>В целом как сделано: на вход программе сортировки подаётся путь к файлу и количество строк, на которые можно перед сортировкой разбить входной файл.
Разбивать было бы правильно динамически, исходя из доступной/выделенной памяти. Т.е. быть более агрессивным в ее использовании.

_FR>Схематично, алгоритм такой: входной файл вычитывается PipeReader-ом: столько строк, сколько задано... Пока эти строки сохраняются в файл, начимаем вычитывать следующий буфер, дабы избежать простоя.
Вот здесь на дисковой подсистеме у вас начинаются сложности. Писать и читать одновременно — это лишние позиционирования головок диска. Очень хорошо было бы их разделять. Т.е. сначала читаем порцию данных (это рабочая порция). (*) Начинаем читать следующую порцию данных. Пока данные читаются, сортируем рабочую порцию. Дожидаемся завершения чтения "следующей порции". Записываем рабочую порцию. Устанавливаем "текущую порцию" в "следующую порцию". Повторяем начиная с (*). В этом случае чтение может быть вообще линейным. Запись линейной не будет никогда (пишутся данные, потом метадата). Буферизация вроде бы нормально настроена. Можно еще сказать CanSeek: false.

_FR>Буду брагодарем за объяснения, как это должно быть сделано правильно.
Для начала — выкинуть всю асинхронность. У вас все равно весь код работает последовательно. Если все сделано правильно, то он утыкается в производительность ввода/вывода. Этим вводом управляете вы, так что загрузить дисковую систему можете. Все эти async/await усложняют код и добавляют накладные расходы на управление асинхронностью. А тольку — только немного от выделения сортировки. Далее — стоит все читать StreamReader'ом (и буфер ему можно дать). Вот какой смысл заморачиваться с PipeReader, Encoder и всем остальным? Я даже посмотрел его исходники и соответствующие ему исходники StreamPipeReader. Так вот, я не вижу, чтобы ReadAsync запускал упреждающую операцию чтения следующего буфера пока мы разбираем текущие данные. Т.е. вы ничего по сравнению с StreamReader.nextLine() не выигрываете.

Далее. Строки стоит разобрать в объекты/записи со строкой и числом. Иначе вы на каждое сравнение сканируете префикс. Какая там длина среднего случайно распределенного числа? 7-8 символов? При этом сравнение строк имеет хорошие шансы закончиться на первом/втором символе. Ну и не нужно будет parseInt делать для сравнения. Ну и тут же еще одно замечание. Вы уверены, что list.clear() хоть в чем-то лучше создания нового списка?

После разбора/чтения/записи можно делать слияние. У вас там тоже все очень последовательно (и можно сделать синхронно). Кстати, как раз там у вас используется StreamReader, зачем в других местах нужно было все усложнять? В слиянии стоит использовать правильную структуру. Ну хотя бы начать с PriorityQueue. Потом можно вручную сделать heap. На ручном heap можно уменьшить количество балансировок (вместо двух — на извлечение и на добавление можно делать одну — после извлечения и добавления нового состояния). Решающим для скорости это быть не должно, но все же.

Вот уже после этого можно оптимизировать. Например, вынести сортировку в отдельный поток. Отдельный поток — это Thread.Start(), Thread.Join(), никаких тасков и асинхронности. Замерить увеличение скорости (при работе с флешкой, ага ). Потом сделать параллельно чтение с записью, оценить прибавку скорости. На данном этапе оно может дать небольшую прибавку, так как у вас все же есть небольшие промежутки, когда производятся вычисление. А может вызвать замедление (на жестком диске). Но даже если и есть, прибавка в теории должна быть небольшая (единицы процентов).

Здравствуйте, AtCrossroads, Вы писали:

AC>>>"Правильное" решение, думаю, такое:
AC>>>1. Читаем файл по секциям, …
_FR>>А как это? Что в вашем понимании секция и как их найти в файле?

AC>Завести очередь несортированных списков List<List<string>>. Запустить поток, который этот список пополняет, посто последовательно читая из stream.
AC>Запустить поток, который смотрит на этот списко и запускает потоки сортировки (не больше, чем ядер). Отсортированные списки строк складываются в новую очередь.
AC>Первый поток поток (который читает), пишет отсортированные списки во временные файлы (вероятно, совмещать чтение и запись именно в одном потоке не обязательно; цель, не перемежать обращения к диску).

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

AC>Может быть можно сделать код проще: запускать одновременно тасков по числу ядрер.
AC>В каждом таске "захватываем чтение-запись" (просто lock на любом объекте), читаем кусок из stream.

А как это вяжется с необходимостью находить начала-конца строк в файле? Как нам гарантировать, что "кусок из stream" начнётся с начала строки?

Здравствуйте, _FRED_, Вы писали:

_FR>Вот с тех пор мне интересно, где я мог пойти не тем путём: разница достаточно большаая, скорее всего на более медленном железе так плохо вышло не из-за каких-то микрооптимизаций, которые я не смог сделать, а в чём-то принципиальном. Но где

Попробовал запустить на линукс. Программа ест 2-3 Гб оперативки (назависимо от размера файла).
Конечно, может это особенность .NET на линукс. Но если также работает и на windows, то программа может банально уходить в своп.

Здравствуйте, maxkar, Вы писали:

_FR>>Решение моё интервьюеров не удовлетворило, говорят, что очень медленно работает: как обычно, у меня на лаптопе как раз всё летает, файл в 1Г сортируется за 13 с небольшим секунд, а у ревьюеров получилось 130c на файл 1 гиг Так мне написали.
M>Диски могут быть разные (особенно весело, если тестируется в docker/kubernetes с настройками по-умолчанию, там все оооочень медленно). И локальная память. Сколько у вас на машине памяти? Вдруг окажется, что все записанные файлы потом читаются не с диска, а из дискового кэша? Хорошо бы было писать на диск. За неимением диска попробуйте хотя бы флешку (внешний жесткий диск будет идеальным решением). Там случайный доступ не так плох, как в блинных конструкциях, но скорость — низкая. Если промахнулись с буферами, может быть заметно. И если на машине много памяти — перезагружайтесь между этапами (генерация->разбиение->слияние), чтобы данные из кэша удалялись. Или отмонтируйте/примонтируйте ее, только сравните скорость с перезагрузкой.

Спасибо, это я учту, поэксперементировать со флешкой не догадался.

_FR>>В целом как сделано: на вход программе сортировки подаётся путь к файлу и количество строк, на которые можно перед сортировкой разбить входной файл.
M>Разбивать было бы правильно динамически, исходя из доступной/выделенной памяти. Т.е. быть более агрессивным в ее использовании.

Это мне показалость излишним для тестового задания, ибо 1) тут можно долго подбирать хорошую эвристику и 2) если вдруг код будут запускать на машинке в большим объёмом памяти, то показать, как она умеет работать с малым будет сложно.

_FR>>Схематично, алгоритм такой: входной файл вычитывается PipeReader-ом: столько строк, сколько задано... Пока эти строки сохраняются в файл, начимаем вычитывать следующий буфер, дабы избежать простоя.
M>Вот здесь на дисковой подсистеме у вас начинаются сложности. Писать и читать одновременно — это лишние позиционирования головок диска.

Наверное да, показалось странным работать с большими файлами в шаше время на ХДД (но тогда и на памяти экономить, наверное, было бы и не нужно).

M>Очень хорошо было бы их разделять. Т.е. сначала читаем порцию данных (это рабочая порция). (*) Начинаем читать следующую порцию данных. Пока данные читаются, сортируем рабочую порцию. Дожидаемся завершения чтения "следующей порции". Записываем рабочую порцию. Устанавливаем "текущую порцию" в "следующую порцию". Повторяем начиная с (*). В этом случае чтение может быть вообще линейным. Запись линейной не будет никогда (пишутся данные, потом метадата). Буферизация вроде бы нормально настроена.

Спасибо, интересная идея, это попробую.

M>Можно еще сказать CanSeek: false.

Где это можно сказать?

_FR>>Буду брагодарем за объяснения, как это должно быть сделано правильно.
M>Для начала — выкинуть всю асинхронность. У вас все равно весь код работает последовательно. Если все сделано правильно, то он утыкается в производительность ввода/вывода. Этим вводом управляете вы, так что загрузить дисковую систему можете. Все эти async/await усложняют код и добавляют накладные расходы на управление асинхронностью.

Неужели накладные расходы на асинхронность будут сравнимы в вашем понимании с накладными расходами на ввод-вывод или на вручную щзапущенные потоки?

M>А тольку — только немного от выделения сортировки.

Нет: async вызван использованием PipeReader-а, а он выбран как средство, позволяющее минимизировать объём используемой памяти (по сравнению, например, со StreamReader::ReadLine()).

M>Далее — стоит все читать StreamReader'ом (и буфер ему можно дать). Вот какой смысл заморачиваться с PipeReader, Encoder и всем остальным?

Я сделал реализацию на StreamReader::ReadLine(), чтобы увидеть, что смысл есть и разница в скорости (на выделении памяти под строки) и в самой используемой памяти мне понравилась.

M>Я даже посмотрел его исходники и соответствующие ему исходники StreamPipeReader. Так вот, я не вижу, чтобы ReadAsync запускал упреждающую операцию чтения следующего буфера пока мы разбираем текущие данные. Т.е. вы ничего по сравнению с StreamReader.nextLine() не выигрываете.

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

M>Далее. Строки стоит разобрать в объекты/записи со строкой и числом. Иначе вы на каждое сравнение сканируете префикс. Какая там длина среднего случайно распределенного числа? 7-8 символов? При этом сравнение строк имеет хорошие шансы закончиться на первом/втором символе. Ну и не нужно будет parseInt делать для сравнения.

Хм, спасибо, подумаю. Тут идея та же: не тратить память повторно. Строковая часть может быть достаточно большой и дублировать её совсем не хотелось.

M>Ну и тут же еще одно замечание. Вы уверены, что list.clear() хоть в чем-то лучше создания нового списка?

Конечно. Списки-то большие, а вся идея была в том, что бы потратить как можно меньше памяти.

M>После разбора/чтения/записи можно делать слияние. У вас там тоже все очень последовательно (и можно сделать синхронно). Кстати, как раз там у вас используется StreamReader, зачем в других местах нужно было все усложнять? В слиянии стоит использовать правильную структуру. Ну хотя бы начать с PriorityQueue. Потом можно вручную сделать heap. На ручном heap можно уменьшить количество балансировок (вместо двух — на извлечение и на добавление можно делать одну — после извлечения и добавления нового состояния). Решающим для скорости это быть не должно, но все же.

Да, сортировка на время операций влияния почти не оказывает. Вам кажется, что она будет выглядеть легче/понятнее, чем BinarySerach/Insert в список? Зачем тогда менять?

M>Вот уже после этого можно оптимизировать. Например, вынести сортировку в отдельный поток. Отдельный поток — это Thread.Start(), Thread.Join(), никаких тасков и асинхронности. Замерить увеличение скорости (при работе с флешкой, ага ). Потом сделать параллельно чтение с записью, оценить прибавку скорости. На данном этапе оно может дать небольшую прибавку, так как у вас все же есть небольшие промежутки, когда производятся вычисление. А может вызвать замедление (на жестком диске). Но даже если и есть, прибавка в теории должна быть небольшая (единицы процентов).

Это всё не так прозаично интересно. Мне интересно, как должен выглядеть алгоритм, который работает быстрее на порядок.

Здравствуйте, Буравчик, Вы писали:

_FR>>Вот с тех пор мне интересно, где я мог пойти не тем путём: разница достаточно большаая, скорее всего на более медленном железе так плохо вышло не из-за каких-то микрооптимизаций, которые я не смог сделать, а в чём-то принципиальном. Но где

Б>Попробовал запустить на линукс. Программа ест 2-3 Гб оперативки (назависимо от размера файла).
Б>Конечно, может это особенность .NET на линукс. Но если также работает и на windows, то программа может банально уходить в своп.

На сколько строк разбивали файл (второй параметр командной строки)? Размер потребляемой памяти должен записеть не от размера входного файла, а от этого параметра.

Здравствуйте, Буравчик, Вы писали:

_FR>>Вот с тех пор мне интересно, где я мог пойти не тем путём: разница достаточно большаая, скорее всего на более медленном железе так плохо вышло не из-за каких-то микрооптимизаций, которые я не смог сделать, а в чём-то принципиальном. Но где

Б>Попробовал запустить на линукс. Программа ест 2-3 Гб оперативки (назависимо от размера файла).
Б>Конечно, может это особенность .NET на линукс. Но если также работает и на windows, то программа может банально уходить в своп.

Поправил ошибку в конфигурации
Можно обновиться, поправить локально или указать дополнительный параметр "--File:MergeFileWriteBufferSizeMiB 1"

Здравствуйте, _FRED_, Вы писали:

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

Интересно, они сравнивают со своим велосипедом или с UNIX-утилитой sort? Эта утилита портирована под Windows.

Здравствуйте, _FRED_, Вы писали:

_FR>Здравствуйте, Буравчик, Вы писали:

_FR>>>Вот с тех пор мне интересно, где я мог пойти не тем путём: разница достаточно большаая, скорее всего на более медленном железе так плохо вышло не из-за каких-то микрооптимизаций, которые я не смог сделать, а в чём-то принципиальном. Но где

Б>>Попробовал запустить на линукс. Программа ест 2-3 Гб оперативки (назависимо от размера файла).
Б>>Конечно, может это особенность .NET на линукс. Но если также работает и на windows, то программа может банально уходить в своп.

_FR>Поправил ошибку в конфигурации
_FR>Можно обновиться, поправить локально или указать дополнительный параметр "--File:MergeFileWriteBufferSizeMiB 1"

Запустил с новой конфигурацией

Чанки по 10_000 строк

File "DataSort-10G.txt" sorted as "DataSort-10G-1981.txt" in 00:02:35.0843764.
Command being timed: "nocache ./SortFile --FilePath /home/USER/DataSort-10G.txt --MaxReadLines 10000"
User time (seconds): 139.03
System time (seconds): 23.07
Percent of CPU this job got: 104%
Elapsed (wall clock) time (h:mm:ss or m:ss): 2:35.59
Average shared text size (kbytes): 0
Average unshared data size (kbytes): 0
Average stack size (kbytes): 0
Average total size (kbytes): 0
Maximum resident set size (kbytes): 2186664
Average resident set size (kbytes): 0
Major (requiring I/O) page faults: 102
Minor (reclaiming a frame) page faults: 1934872
Voluntary context switches: 350870
Involuntary context switches: 2089
Swaps: 0
File system inputs: 41969328
File system outputs: 41950936
Socket messages sent: 0
Socket messages received: 0
Signals delivered: 0
Page size (bytes): 4096
Exit status: 0

Чанки по 100_000 строк. Да, потребление уменьшилось

Command being timed: "nocache ./SortFile --FilePath /home/USER/DataSort-10G.txt --MaxReadLines 100000"
User time (seconds): 115.12
System time (seconds): 22.52
Percent of CPU this job got: 106%
Elapsed (wall clock) time (h:mm:ss or m:ss): 2:09.62
Average shared text size (kbytes): 0
Average unshared data size (kbytes): 0
Average stack size (kbytes): 0
Average total size (kbytes): 0
Maximum resident set size (kbytes): 675316
Average resident set size (kbytes): 0
Major (requiring I/O) page faults: 106
Minor (reclaiming a frame) page faults: 2260903
Voluntary context switches: 329002
Involuntary context switches: 1429
Swaps: 0
File system inputs: 41963448
File system outputs: 41943816
Socket messages sent: 0
Socket messages received: 0
Signals delivered: 0
Page size (bytes): 4096
Exit status: 0

Но все равно потребление памяти большое.

Для сравнения — вывод сортировки на питоне для чанков 10_000 строк.
Работает чуть быстрее, потребляет меньше памяти. Это в один поток, без асинков

User time (seconds): 89.14
System time (seconds): 36.63
Percent of CPU this job got: 87%
Elapsed (wall clock) time (h:mm:ss or m:ss): 2:23.48
Average shared text size (kbytes): 0
Average unshared data size (kbytes): 0
Average stack size (kbytes): 0
Average total size (kbytes): 0
Maximum resident set size (kbytes): 111604
Average resident set size (kbytes): 0
Major (requiring I/O) page faults: 7
Minor (reclaiming a frame) page faults: 27239
Voluntary context switches: 240699
Involuntary context switches: 1086
Swaps: 0
File system inputs: 41961088
File system outputs: 41950944
Socket messages sent: 0
Socket messages received: 0
Signals delivered: 0
Page size (bytes): 4096
Exit status: 0

Здравствуйте, _FRED_, Вы писали:

_FR>Спасибо, это я учту, поэксперементировать со флешкой не догадался.

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

M>>Очень хорошо было бы их разделять. Т.е. сначала читаем порцию данных (это рабочая порция). (*) Начинаем читать следующую порцию данных. Пока данные читаются, сортируем рабочую порцию. Дожидаемся завершения чтения "следующей порции". Записываем рабочую порцию. Устанавливаем "текущую порцию" в "следующую порцию". Повторяем начиная с (*). В этом случае чтение может быть вообще линейным. Запись линейной не будет никогда (пишутся данные, потом метадата). Буферизация вроде бы нормально настроена.

_FR>Спасибо, интересная идея, это попробую.

Это достигается с помощью асинков. Нужно только уменьшить их количество.
Асинхронными должны быть задачи, работающие с целыми чанками, а не строками.

Другой вариант — очереди.
При разбиении — один поток пишет в очередь, другой (или несколько) сортирует и записывает чанки.
При мерже — один поток читает и сортирует, второй пишет результирующий файл

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

Имхо системных буферов достаточно, зачем это все настраивать?

M>>Ну и тут же еще одно замечание. Вы уверены, что list.clear() хоть в чем-то лучше создания нового списка?
_FR>Конечно. Списки-то большие, а вся идея была в том, что бы потратить как можно меньше памяти.

Согласен, это может быть лучше для GC

M>>После разбора/чтения/записи можно делать слияние. У вас там тоже все очень последовательно (и можно сделать синхронно). Кстати, как раз там у вас используется StreamReader, зачем в других местах нужно было все усложнять? В слиянии стоит использовать правильную структуру. Ну хотя бы начать с PriorityQueue. Потом можно вручную сделать heap. На ручном heap можно уменьшить количество балансировок (вместо двух — на извлечение и на добавление можно делать одну — после извлечения и добавления нового состояния). Решающим для скорости это быть не должно, но все же.

_FR>Да, сортировка на время операций влияния почти не оказывает. Вам кажется, что она будет выглядеть легче/понятнее, чем BinarySerach/Insert в список? Зачем тогда менять?

Это спорное утверждение.

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

M>>Вот уже после этого можно оптимизировать. Например, вынести сортировку в отдельный поток. Отдельный поток — это Thread.Start(), Thread.Join(), никаких тасков и асинхронности. Замерить увеличение скорости (при работе с флешкой, ага ). Потом сделать параллельно чтение с записью, оценить прибавку скорости. На данном этапе оно может дать небольшую прибавку, так как у вас все же есть небольшие промежутки, когда производятся вычисление. А может вызвать замедление (на жестком диске). Но даже если и есть, прибавка в теории должна быть небольшая (единицы процентов).

_FR>Это всё не так прозаично интересно. Мне интересно, как должен выглядеть алгоритм, который работает быстрее на порядок.

Лучший алгоритм Вы реализовали — external merge sort.
Это IO-bound задача. Нужно просто загрузить диск на 100% последовательным доступом.
На порядок улучшить нельзя имхо.

Ваша реализация работает достаточно быстро (хотя написана сложно, на мой взгляд). И почему-то жрет память.
У проверяющих что-то пошло не так. Возможно из-за этого жора.

AC>>Может быть можно сделать код проще: запускать одновременно тасков по числу ядрер.
AC>>В каждом таске "захватываем чтение-запись" (просто lock на любом объекте), читаем кусок из stream.

_FR>А как это вяжется с необходимостью находить начала-конца строк в файле? Как нам гарантировать, что "кусок из stream" начнётся с начала строки?

хм.. ну просто StreamReader.ReadLine
К чтению в момент времени имеет доступ только один таск.

Выяснить, есть ли какой-нибудь способ не аллоцировать строки, а держать их в одной области памяти и иметь на них ссылку в виде, например Memory<>.
Если есть, это может дать очень существенный выигрыш при сортировке. Не из-за аллокакий, а из-за уменьшения кэшмиссов.

Здравствуйте, _FRED_, Вы писали:

_FR>Наверное да, показалось странным работать с большими файлами в шаше время на ХДД (но тогда и на памяти экономить, наверное, было бы и не нужно).
В наше время можно было бы загрузить этот "большой файл" в Azure и отсортировать его в памяти. Микрософт достаточно широкую линейку предлагает, есть машины с большим количеством памяти и достаточно средним процессором.

M>>Можно еще сказать CanSeek: false.
_FR>Где это можно сказать?
Я исходники не дочитал, его нельзя установить . Он где-то внутри FileStream инициализируется. Может быть, установить SequentialScan на запись? Хотя не знаю, можно ли так и поможет ли оно.

_FR>Неужели накладные расходы на асинхронность будут сравнимы в вашем понимании с накладными расходами на ввод-вывод или на вручную щзапущенные потоки?
Сравнимы быть не должны. Хотя зависит от диска. Потому что асинхронность требует какой-то реализации. В лучшем случае это инструкции чтения напрямую из памяти. В худшем — системные вызовы вроде мьютексов. При этом у вас асинхронности очень много. Грубо говоря, каждая строка разбирается асинхронно. Это создает лишние синхронизации/барьеры и все остальное. В предлагаемом мной решении (сортировка в отдельном потоке) у нас имеется один системный вызов на запуск потока, один — на остановку (Join в конце). Все остальное работает независимо и параллельно. Как Буравчик ниже предлагает, нужно работать с более крупными блоками без лишних расходов.

M>>А тольку — только немного от выделения сортировки.
_FR>Нет: async вызван использованием PipeReader-а, а он выбран как средство, позволяющее минимизировать объём используемой памяти (по сравнению, например, со StreamReader::ReadLine()).
Это не совсем та память, которую нужно оптимизировать. Ваш reader и прочие буфера имеют размер порядка мегабайтов. Причем это именно рабочие буфера. Когда вы делаете Encoder.ToString(), данные из буфера все равно копируются. Рабочий набор для сортировки должен быть порядка сотен мегабайт. Т.е. вы оптимизируете по памяти часть, занимающую проценты от общего потребления.

_FR>Хм, спасибо, подумаю. Тут идея та же: не тратить память повторно. Строковая часть может быть достаточно большой и дублировать её совсем не хотелось.
Там очень временное дублирование получается. В .NET сборщик мусора с поколениями. Наличие поколений говорит о том, что в целом платформа хорошо справляется с небольшими короткоживущими объектами. У вас "следующая строка" — короткоживущий объект. Из нее парсится число и делается substring. Всё. Из дополнительных расходов — struct для хранения числа и строки и дополнительное копирование строковых данных в Substring. Временно (на время работы Substring) — да, память в двойном размере строки.

M>>Ну и тут же еще одно замечание. Вы уверены, что list.clear() хоть в чем-то лучше создания нового списка?
_FR>Конечно. Списки-то большие, а вся идея была в том, что бы потратить как можно меньше памяти.
Вроде бы задача отсортировать быстро а не потратить меньше памяти? Про список вопросы про GC в первую очередь. Но да, наверное, clear лучше. Список в итоге все равно окажется где-то в старших поколениях, там переиспользование оправдано.

_FR>Да, сортировка на время операций влияния почти не оказывает. Вам кажется, что она будет выглядеть легче/понятнее, чем BinarySerach/Insert в список? Зачем тогда менять?
Да, лучше. Хотя-бы читабельнее. Например, в текущем коде мне очень не хватает комментария о том, почему мы экономим количество сравнений но не экономим количество копирований. Допустим, у нас массив короткий (5-10 элементов). Зачем нам вообще нужен двоичный поиск? Можно просто последовательно сравнивать элементы и копировать, пока не найдем позицию (типичный insertion sort). Больше сравнений, меньше ветвлений. Нет, я понимаю, что у вас сравнение тяжелое. Но сочетание двоичного поиска и линейной вставки выглядит странно.

Здравствуйте, Буравчик, Вы писали:

Б>И почему-то жрет память.
А это просто. Там на каждый входной файл выделяется буфер в как минимум 1Мб. Это внутренний буфер FileStream, используется для того, чтобы уменьшить количество вызовов в ядро. Т.е. пользователь FileStream может читать единицы/десятки байт, а переключения контекстов будут выполняться редко. Но при большом количестве файлов таких буферов становится много. Это же показывают и ваши эксперименты — чем больше файлов, тем выше потребление. По умолчанию (без настройки) в FileStream вообще 4Кб буфер. Мегабайт там, наверное, много. Я не уверен, что даже самый агрессивный prefetch будет столько вычитывать. Что-то порядка 16-32Кб может быть идеальным вариантом.

Здравствуйте, maxkar, Вы писали:

_FR>>Да, сортировка на время операций влияния почти не оказывает. Вам кажется, что она будет выглядеть легче/понятнее, чем BinarySerach/Insert в список? Зачем тогда менять?
M>Да, лучше. Хотя-бы читабельнее. Например, в текущем коде мне очень не хватает комментария о том, почему мы экономим количество сравнений но не экономим количество копирований. Допустим, у нас массив короткий (5-10 элементов). Зачем нам вообще нужен двоичный поиск? Можно просто последовательно сравнивать элементы и копировать, пока не найдем позицию (типичный insertion sort). Больше сравнений, меньше ветвлений.

Мне это показалось логичным: если у нас разбивка происходин на небольшое число файлов, то и такая программа скорее всего не нужна, памяти у нас относительно много и операцию мы так и этак относительно быстро можем завершить.
Такие программы, для сортировки больших файлов с использованием ограниченной памяти, имеет смысл запускать на действительно больших файлах, которые во много раз больше имеющейся оперативки. Соответственно файлов будет много… я рассчитываю на тысячи.

M>Нет, я понимаю, что у вас сравнение тяжелое. Но сочетание двоичного поиска и линейной вставки выглядит странно.

Мне казалось, что это весьма распространённая практика — когда имеется сортированный список и нужно добавить в него элемент так, что бы список остался бы отсортированным

Здравствуйте, maxkar, Вы писали:

Б>>И почему-то жрет память.
M>А это просто. Там на каждый входной файл выделяется буфер в как минимум 1Мб. Это внутренний буфер FileStream, используется для того, чтобы уменьшить количество вызовов в ядро. Т.е. пользователь FileStream может читать единицы/десятки байт, а переключения контекстов будут выполняться редко. Но при большом количестве файлов таких буферов становится много. Это же показывают и ваши эксперименты — чем больше файлов, тем выше потребление. По умолчанию (без настройки) в FileStream вообще 4Кб буфер. Мегабайт там, наверное, много. Я не уверен, что даже самый агрессивный prefetch будет столько вычитывать. Что-то порядка 16-32Кб может быть идеальным вариантом.

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

Здравствуйте, _FRED_, Вы писали:

_FR>Привет,

_FR>Ещё в прошлом году дали в одной компании тестовое задание, которое мне показалось интересным сделать — во-первых, я на программиста не учился и сортировку файлов слиянием делать мне никогда не приходилось, только читал. Во-вторых, показалось, что в такой задаче можно как раз удачно поиграть с последними нововведениями в C# и dotnet и покапаться в спанах (может, в этом и была моя ошибка, подскажите).

Очень интересная задачка. Помимо упомянутого:
— HDD или SSD? HDD не умеет параллелить чтения и записи, дорогой seek.
— Насколько рандомные строки? Возможно, имеет смысл при записи чанков на диск сжимать данные
— формат строк и условие сортировки прямо подталкивает к другому формату данных для сортировки. zero-terminated string и число dword-ом. Помимо скорости сравнения, это еще и экономия памяти.
— хранить сортируемые данные непрерывными областями в памяти и сортировать смещения, аллокация каждой строчки в хипе — неэффективно.
— сделать эффективный мердж сотен чанков не так-то просто и может быть неэффективно на HDD, нужно поиграться с кол-вом мерджей