Какова подходящая настройка madvise для чтения файла в обратном направлении?

Я использую gcc 4.7.2 на 64-битной Linux-системе.

У меня есть 20 больших отсортированных бинарных файлов POD, которые мне нужно прочитать как часть окончательного слияния во внешней сортировке слиянием.

Обычно я бы mmap все файлы для чтения и использования multiset<T,LessThan> управлять сортировкой слияния от малого к большому, прежде чем делать mmap записать на диск.

Тем не менее, я понял, что если я буду держать std::mutex на каждом из этих файлов я могу создать второй поток, который читает файл в обратном порядке и одновременно сортирует его по большому и малому размеру. Если я заранее решу, что первый поток будет принимать ровно n / 2 элемента, а второй поток возьмет на себя все остальное, мне не понадобится мьютекс на выходе.

Ожидается, что в этом конкретном случае могут возникнуть споры о блокировке чтения, в среднем, 1 к 20, так что это приемлемо.

Теперь вот мой вопрос. В первом случае очевидно, что мне следует позвонить madvise с MADV_SEQUENTIAL, но я понятия не имею, что мне делать во втором случае, когда я читаю файл в обратном направлении.

Не вижу MADV_REVERSE в справочных страницах. Должен ли я использовать MADV_NORMAL или, может быть, не звоните madvise совсем?

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

Мои шаги для внешней сортировки слиянием

1. Возьмите n = 1 миллиард случайных чисел и разбейте их на 20 осколков одинакового размера.
2. Сортируйте каждый осколок по отдельности от маленького к большому и запишите каждый в отдельный файл.
3. Откройте 40 mmap, по 2 для каждого файла, один для продвижения вперед, один для перехода назад, свяжите мьютекс с каждым файлом.
4. Создать std::multiset<T,LessThan> buff_fwd; для передней нити и std::multiset<T,GreaterThan> buff_rev для обратной нити. Некоторые люди предпочитают использовать очереди с приоритетами здесь, но, по сути, здесь будет работать контейнер sort-on-insert.
5. Мне нравится называть два буфера поверхностными и каменными, представляющими наименьшее и наибольшее числа, еще не добавленные в окончательную сортировку.
6. Добавляйте элементы из сегментов до тех пор, пока n / 2 не будет израсходовано, и сбросьте фрагменты в один выходной файл, используя mmap от начала к середине и от конца к середине в другом потоке. Вы можете в основном очищать данные по своему усмотрению, но по крайней мере это следует сделать до того, как один из буферов использует слишком много памяти.