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

Пусть у нас на диске есть файл размером 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 по всем ядрам.

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


Дискас.