Подсмотрел простую задачку, на плюсы, но не суть. Примерно такая:

Пусть у нас на диске есть файл размером 4 гигабайта. Его можно представить, как 2^30 32-битных беззнаковых чисел. Нужно отсортировать этот файл. То есть программа должна сгенерировать еще один файл размером в 4 гигабайта, в котором содержатся те же числа, что и в исходном, но упорядочены по возрастанию. Стандартные алгоритмы сортировки (qsort, std::sort) напрямую применить невозможно, так как для их выполнения нужно как минимум 4 гигабайта оперативной памяти. Но отсортировать числа на диске возможно, если использовать дополнительное пространство на жестком диске. Нужно написать консольную программу, которая в argv[1] получает имя файла, который нужно отсортировать (размер файла до 16Gb, размер кратен четырем), в argv[2] — имя файла, в который нужно записать отсортированные данные.

Ограничения:

Программа не может рассчитывать, что возможно выделить более 256Mb памяти.
Программа должна эффективно использовать несколько ядер.


Работает эффективно. Эффективно значит

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

Т.е. классический external sort с bucket-ми на count sort:
шаг 1: из N сегментов входного файла, делаем N bucket-в, которые сортируем в памяти каждый за линейное время, выгружаем их в N временных файлов
шаг 2: используя priority queue (heap), затягиваем по 1 числу из каждого временного файла до размера N, выводим в выходной файл наименьшее (не помню точных деталей from top of my head)

Что меня тут смущает: задача полностью загрузить CPU. Интуиция мне подсказывает, что даже с nvme ssd, уже на одном ядре оно упрётся в скорость IO. Сделать число потоков для count sort по числу логических ядер и размер bucket как 256mb/ 32bit / число ядер? Но все эти 8/12/16/whatever потоки кинутся читать из одного и того же входного файла, это уйдёт в ядро и там упрётся в bottleneck единственного мьютекса. Опять не выйдёт получить 100% загрузки CPU по всем ядрам.

Или не упрётся?


Дискас.

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

$>Что меня тут смущает: задача полностью загрузить CPU. Интуиция мне подсказывает, что даже с nvme ssd, уже на одном ядре оно упрётся в скорость IO. Сделать число потоков для count sort по числу логических ядер и размер bucket как 256mb/ 32bit / число ядер? Но все эти 8/12/16/whatever потоки кинутся читать из одного и того же входного файла, это уйдёт в ядро и там упрётся в bottleneck единственного мьютекса. Опять не выйдёт получить 100% загрузки CPU по всем ядрам.

$>Или не упрётся?

Просто пример (восстановление базы SQL Server на 4xNVMe Simple Storage Spaces (по-факту RAID0)):

Сортируй чанки пузырьком

По-моему задача бессмысленная в отрыве от конкретных характеристик. И процессор и диск могут работать со скоростью, отличающейся в разы.

PS а как ты хочешь сортировать чанки за линейное время? Что за count sort? Он для 32-битных чисел сработает на 256 MB?

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

vsb>По-моему задача бессмысленная в отрыве от конкретных характеристик. И процессор и диск могут работать со скоростью, отличающейся в разы.
Там нужно написать програмку и прлгнать её. Очевидно, amd64 и ssd. Про hdd не сказано.

vsb>PS а как ты хочешь сортировать чанки за линейное время? Что за count sort? Он для 32-битных чисел сработает на 256 MB?
Да, этот вопрос я упустил. Count sort (сортировка подсчётом) потребует 16гб памяти.

Можно считать сегментами по 0-64mb, ... (64mb * 4байта = 256mb) и выгружать в файлы. Потом из этих файлов с счетчиками сгенерировать результирующий файл. Останется линейная сложность и упрется в IO.

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

$>

$>используя немного памяти, зато полностью загружая CPU.
$>нельзя придумать существенно более эффективное (на десятки процентов, или с принципиально лучшей временной сложностью) решение.
$>

Ну, на одном ядре сортируем, другие просто загружаем, чтобы согреть воздух в помещении.

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

$>Дискас.

У Кнута есть целая глава, посвященная сортировкам данных на ленте, которые не лезут в память. Лента — это такое устройство, которое со сносной скоростью умеет читать/писать последовательно, но очень медленно перематывается.

vsb>>По-моему задача бессмысленная в отрыве от конкретных характеристик. И процессор и диск могут работать со скоростью, отличающейся в разы.
$>Очевидно, amd64 и ssd.
неочевидно.

$>Про hdd не сказано.
про hdd не сказано также как не сказано про ssd, или как-то иначе? типа точно не hdd.

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

$>Что меня тут смущает: задача полностью загрузить CPU. Интуиция мне подсказывает, что даже с nvme ssd, уже на одном ядре оно упрётся в скорость IO. Сделать число потоков для count sort по числу логических ядер и размер bucket как 256mb/ 32bit / число ядер? Но все эти 8/12/16/whatever потоки кинутся читать из одного и того же входного файла, это уйдёт в ядро и там упрётся в bottleneck единственного мьютекса. Опять не выйдёт получить 100% загрузки CPU по всем ядрам.

Сделай спинлок на ожиданиии данных — получишь 100% утилизацию .

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

$>Дискас.
В задаче явно предполагается такой алгоритм действий:
1. Тянем блок данных (265 метров) в память. В это время CPU спит.
2. Сортируем блок в памяти
3. Пишем отсортированный блок на диск.
4. Повторяем 1-3 для каждого блока
5. Выполняем сортировку слиянием.
"Эффективность" здесь относится только к шагу 2. На самом деле понятно, что шаги 1/3 и 2 можно "вдвинуть" друг в друга, т.к. одни из них чисто IO, а другие — чисто CPU.
Если при какой-то степени параллелизма у нас время шага 2 становится меньше, чем 1+3, то смысла дальше пилить уже нету, и общее время работы не улучшится.
Однако, авторы всё равно хотят, чтобы шаг 2 выполнился максимально быстро.
Надо полагать, ожидают аналогичного подхода — пилим блок на подблоки, каждый сортируем в отдельном потоке, потом сливаем.

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

$>Подсмотрел простую задачку, на плюсы, но не суть. Примерно такая:
$>

$>Пусть у нас на диске есть файл размером 4 гигабайта. Его можно представить, как 2^30 32-битных беззнаковых чисел. Нужно отсортировать этот файл. То есть программа должна сгенерировать еще один файл размером в 4 гигабайта, в котором содержатся те же числа, что и в исходном, но упорядочены по возрастанию.
$>

Если числа не повторяются, то всё просто.

$>нельзя придумать существенно более эффективное (на десятки процентов, или с принципиально лучшей временной сложностью) решение.


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

тут имеется ввиду, видимо, что традиционный k-way merge не катит, т.к.
а)последним этапом в нем будет слияние k-отстортированных кусков, оно однопоточное и это довольно сложная и тяжелая операция
б)1е число ты сможешь вернуть очень-очень поздно, как минимум после того как всё прочитаешь,всё отсортируешь и всё запишешь

видимо хотят модфикацию quick sort with sampling, где на 1м этапе идет сэмплирование исходных данных (скажем читаем 1%), но определяется не середина, а (k-1) — границ для раскидывания по "корзинам"
если данные неравномерно распределены или какую-то корзинку перекосило, то либо запускают рекурсию, либо переключаются на какой-то другой алгоритм
а) у него очень простой и дешевый split streams
б) 1е число возвращается быстрее, после сортировки только 1й корзинки

На практике, твою "классику" списали лет 30 назад. Оно по описанию-то просто выглядит, но в реализации оказывается сложнее и работает хуже
надеюсь что рассказал что-то новое

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

$>Но отсортировать числа на диске возможно, если использовать дополнительное пространство на жестком диске.

Histogram sort с некоторыми модификациями. На самом деле, даже место на диске не нужно — можно уложиться в оперативку.

$>Работает эффективно. Эффективно значит используя немного памяти, зато полностью загружая CPU.

Я не понял. Задача — максимально загрузить CPU? Или максимально быстро выполнить сортировку?

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

Т.к. в файле 2^30 32-битных числа, то каждое из возможных чисел будет находиться в файле с мат.ожиданием 0,25. Есть подозрение, что (при высокой пропускной способности шины) перебор всех чисел от 0 до 2^32-1 и подсчёт количества этих чисел в файле окажется быстрее сортировки файла "по частям".

Ещё можно сделать адаптивный алгоритм. Взять небольшую часть файла и замерять: с какой скоростью данные читаются с диска и с какой скоростью данные сортируются процессором. Потом, в зависимости от результатов, высчитать оптимальный для данной машины способ сортировки. И отсортировать весь файл этим способом.

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

$>Дискас.

Merge sort отлично параллелится. Нужно подобрать оптимальный размер порции и количество рабочих потоков. Часть потоков выделить для ввода-вывода. Для промежуточных результатов можно использовать два файла такого же размера, что и входной, один из них в конце станет выходным. На каждой итерации из одного читаем, в другой пишем, на следующей они меняются ролями. Первый раз читаем из входного. Ввод-вывод при этом будет в основном последовательным, и возможно не станет узким местом. А если и станет, то все равно CPU должен неплохо загрузиться. Минимальную порцию разумется сортировать чем-то более эффективным в памяти.

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

W>Merge sort отлично параллелится. Нужно подобрать оптимальный размер порции и количество рабочих потоков. Часть потоков выделить для ввода-вывода. Для промежуточных результатов можно использовать два файла такого же размера, что и входной, один из них в конце станет выходным. На каждой итерации из одного читаем, в другой пишем, на следующей они меняются ролями. Первый раз читаем из входного. Ввод-вывод при этом будет в основном последовательным, и возможно не станет узким местом. А если и станет, то все равно CPU должен неплохо загрузиться. Минимальную порцию разумется сортировать чем-то более эффективным в памяти.

Чтобы загрузить CPU, не должно упираться в IO. Но чтение из одного и запись в другой- это 2 потока. Потоки сортировки заткнутся в ожидании. Более того, одновременное чтение и запись на одно и то же физическое устройство hdd убьёт его производительность на порядки.

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

$>Чтобы загрузить CPU, не должно упираться в IO. Но чтение из одного и запись в другой- это 2 потока. Потоки сортировки заткнутся в ожидании.

Внешняя сортировка, необходимая по условиям задачи, на каком-то этапе неизбежно упрется в I/O. Смысл задачи, как я понимаю, в том, чтобы загрузить CPU чем то полезным в моменты ожидания этого самого I/O. То есть многое будет зависеть от алгоритма координации рабочих потоков, при любом общем алгоритме сортировки. Тут есть над чем подумать, но мне кажется, с merge sort это вполне возможно. Поскольку количество потоков << количества частей, запускаться они будут с разницей во времени, что и позволит загрузить CPU. Нужно только обеспечить запуск следующей итерации для каждой части, как только все будет готово для этого. Это самая сложная часть.

$>Более того, одновременное чтение и запись на одно и то же физическое устройство hdd убьёт его производительность на порядки.

Это смотря какой hdd и контроллер. Современные не убъет, особено если читать/писать достаточно большими кусками. Но можно поэкспериментировать и с разнесением чтения и записи по времени.