Сортировку файлов называют внешней сортировкой потому что сортируются последовательности элементов
Прочитав эту статью, я вспомнил, как писал внешнюю сортировку, которая использовала O(1) внешней памяти. Функция получала бинарый файл и максимальный размер памяти, которую она могла выделить под массив:
- Разделим файл на блоки, которые помещаются в доступную память. Обозначим эти блоки Block_1, Block_2, …, Block_(S-1), Block_S. Установим P = 1.
- Читаем Block_P в память.
- Отсортируем данные в памяти и запишем назад в Block_P. Установим P = P + 1, и если P ≤ S, то читаем Block_P в память и повторяем этот шаг. Другими словами, отсортируем каждый блок файла.
- Разделим каждый блок на меньшие блоки B_1 и B_2. Каждый из таких блоков занимает половину доступной памяти.
- Читаем блок B_1 блока Block_1 в первую половину доступной памяти. Установим Q = 2.
- Читаем блок B_1 блока Block_Q во вторую половину доступной памяти.
- Объеденим массивы в памяти с помощью in-place слияния, запишем вторую половину памяти в блок B_1 блока Block_Q и установим Q = Q + 1, если Q ≤ S, читаем блок B_1 блока Block_Q во вторую половину доступной памяти и повторяем этот шаг.
- Записываем первую половину доступной памяти в блок B_1 блока Block_1. Так как мы всегда оставляли в памяти меньшую половину элементов и провели слияние со всеми блоками, то в этой части памяти хранятся M минимальных элементы всего файла.
- Читаем блок B_2 блока Block_S во вторую половину доступной памяти. Установим Q = S −1.
- Читаем блок B_2 блока Block_Q в первую половину доступной памяти.
- Объеденим массивы в памяти с помощью in-place слияния, запишем первую половину доступной памяти в блок B_2 блока Block_Q и установим Q = Q −1. Если Q ≥ 1 читаем блок B_2 блока Block_Q в первую половину доступной памяти и повторяем этот шаг.
- Записываем вторую половину доступной памяти в блок B_2 блока Block_S. Аналогично шагу 8, тут хранятся максимальные элементы всего файла.
- Начиная от блока B_2 блока Block_1 и до блока B_1 блока Block_S, определим новые блоки в файле и снова пронумеруем их Block_1 to Block_S. Разделим каждый блок на блоки B_1 и B_2. Установим P = 1.
- Читаем B_1 и B_2 блока Block_P в память. Объеденим массивы в памяти. запишем отсортированный массив назад в Block_P и установим P = P +1. Если P ≤ S, повторяем этот шаг.
- Если S > 1, возвращаемся к шагу 5. Каждый раз мы выделяем M минимальных и максимальных элементов, записываем их в начало и конец файла соответственно, а потом делаем то же самое с оставшимися элементами, пока не дойдем до середины файла.
Реализуем алгоритм на C++.
Для начала определим количество блоков и размер блока в байтах и в элементах и выделим память:
Теперь пункты 2-3 — сортируем каждый блок:
Саму сортировку мы напишем чуть позднее.
Приступим к слияниям. Нижняя половина:
И аналогично верхняя:
Перераспределяем блоки, завершаем цикл и не забываем освободить память:
Осталось реализовать функции flat_quick_sort и in_place_merge. Идею (и большую часть реализации) flat quick sort я взял в статье хабраюзера ripatti. Я только заменил median of medians (посчитал это оверкиллом в среднем случае) на median-of-nine и добавил сортировку вставками для маленьких частей массива.
Со слиянием было сложнее. Сначала я использовал заглушку, использующую O(n) памяти:
Когда я захотел заменить заглушку in-place версией, оказалось, что быстрые алгоритмы in-place слияния в большинстве своем достаточно запутанные (посмотрите, например, On optimal and efficient in place merging). Мне надо было что-то попроще, и я выбрал алгоритм из статьи A simple algorithm for in-place merging:
Аннотация: В лекции рассматриваются определение и классификация алгоритмов внешних сортировок, понятия фаз и путей в алгоритмах внешних сортировок, приводятся описания и реализации алгоритмов внешней сортировки слиянием и естественной сортировки.
Цель лекции: изучить основные алгоритмы внешних сортировок, научиться решать задачи сортировок массивов различными методами и выполнять оценку эффективности алгоритмов внешней сортировки .
Внешние сортировки применяются к данным, которые хранятся во внешней памяти. При выполнении таких сортировок требуется работать с данными, расположенными на внешних устройствах последовательного доступа . Для файлов, расположенных на таких устройствах в каждый момент времени доступен только один компонент последовательности данных, что является существенным ограничением по сравнению с сортировкой массивов , где всегда доступен каждый элемент.
Внешняя сортировка – это сортировка данных, которые расположены на внешних устройствах и не вмещающихся в оперативную память .
Данные, хранящиеся на внешних устройствах , имеют большой объем, что не позволяет их целиком переместить в оперативную память , отсортировать с использованием одного из алгоритмов внутренней сортировки, а затем вернуть их на внешнее устройство . В этом случае осуществлялось бы минимальное количество проходов через файл , то есть было бы однократное чтение и однократная запись данных. Однако на практике приходится осуществлять чтение, обработку и запись данных в файл по блокам, размер которых зависит от операционной системы и имеющегося объема оперативной памяти, что приводит к увеличению числа проходов через файл и заметному снижению скорости сортировки.
К наиболее известным алгоритмам внешних сортировок относятся:
- сортировки слиянием (простое слияние и естественное слияние);
- улучшенные сортировки (многофазная сортировка и каскадная сортировка).
Из представленных внешних сортировок наиболее важным является метод сортировки с помощью слияния. Прежде чем описывать алгоритм сортировки слиянием введем несколько определений.
Основным понятием при использовании внешней сортировки является понятие серии. Серия (упорядоченный отрезок) – это последовательность элементов, которая упорядочена по ключу.
Количество элементов в серии называется длиной серии. Серия, состоящая из одного элемента, упорядочена всегда. Последняя серия может иметь длину меньшую, чем остальные серии файлов. Максимальное количество серий в файле N (все элементы не упорядочены). Минимальное количество серий одна (все элементы упорядочены).
В основе большинства методов внешних сортировок лежит процедура слияния и процедура распределения. Слияние – это процесс объединения двух (или более) упорядоченных серий в одну упорядоченную последовательность при помощи циклического выбора элементов, доступных в данный момент. Распределение – это процесс разделения упорядоченных серий на два и несколько вспомогательных файла.
Фаза – это действия по однократной обработке всей последовательности элементов. Двухфазная сортировка – это сортировка , в которой отдельно реализуется две фазы: распределение и слияние. Однофазная сортировка – это сортировка , в которой объединены фазы распределения и слияния в одну.
Двухпутевым слиянием называется сортировка , в которой данные распределяются на два вспомогательных файла. Многопутевым слиянием называется сортировка , в которой данные распределяются на N (N > 2) вспомогательных файлов.
Общий алгоритм сортировки слиянием
Сначала серии распределяются на два или более вспомогательных файлов. Данное распределение идет поочередно: первая серия записывается в первый вспомогательный файл , вторая – во второй и так далее до последнего вспомогательного файла. Затем опять запись серии начинается в первый вспомогательный файл . После распределения всех серий, они объединяются в более длинные упорядоченные отрезки, то есть из каждого вспомогательного файла берется по одной серии, которые сливаются. Если в каком-то файле серия заканчивается, то переход к следующей серии не осуществляется. В зависимости от вида сортировки сформированная более длинная упорядоченная серия записывается либо в исходный файл , либо в один из вспомогательных файлов. После того как все серии из всех вспомогательных файлов объединены в новые серии, потом опять начинается их распределение. И так до тех пор, пока все данные не будут отсортированы.
Выделим основные характеристики сортировки слиянием:
- количество фаз в реализации сортировки;
- количество вспомогательных файлов, на которые распределяются серии.
Рассмотрим основные и наиболее важные алгоритмы внешних сортировок более подробно.
Сортировка простым слиянием
Одна из сортировок на основе слияния называется простым слиянием.
Алгоритм сортировки простым слияния является простейшим алгоритмом внешней сортировки , основанный на процедуре слияния серией.
В данном алгоритме длина серий фиксируется на каждом шаге. В исходном файле все серии имеют длину 1, после первого шага она равна 2, после второго – 4, после третьего – 8, после k -го шага – 2 k .
Алгоритм сортировки простым слиянием
Шаг 1. Исходный файл f разбивается на два вспомогательных файла f1 и f2 .
Шаг 2. Вспомогательные файлы f1 и f2 сливаются в файл f , при этом одиночные элементы образуют упорядоченные пары.
Шаг 3. Полученный файл f вновь обрабатывается, как указано в шагах 1 и 2. При этом упорядоченные пары переходят в упорядоченные четверки.
Шаг 4. Повторяя шаги, сливаем четверки в восьмерки и т.д., каждый раз удваивая длину слитых последовательностей до тех пор, пока не будет упорядочен целиком весь файл ( рис. 43.1).
После выполнения i проходов получаем два файла, состоящих из серий длины 2 i . Окончание процесса происходит при выполнении условия 2 i >=n . Следовательно, процесс сортировки простым слиянием требует порядка O(log n) проходов по данным.
Признаками конца сортировки простым слиянием являются следующие условия:
- длина серии не меньше количества элементов в файле (определяется после фазы слияния);
- количество серий равно 1 (определяется на фазе слияния).
- при однофазной сортировке второй по счету вспомогательный файл после распределения серий остался пустым.
Заметим, что для выполнения внешней сортировки методом простого слияния в оперативной памяти требуется расположить всего лишь две переменные – для размещения очередных элементов (записей) из вспомогательных файлов. Исходный и вспомогательные файлы будут O(log n) раз прочитаны и столько же раз записаны.
Аннотация: В лекции рассматриваются определение и классификация алгоритмов внешних сортировок, понятия фаз и путей в алгоритмах внешних сортировок, приводятся описания и реализации алгоритмов внешней сортировки слиянием и естественной сортировки.
Цель лекции: изучить основные алгоритмы внешних сортировок, научиться решать задачи сортировок массивов различными методами и выполнять оценку эффективности алгоритмов внешней сортировки .
Внешние сортировки применяются к данным, которые хранятся во внешней памяти. При выполнении таких сортировок требуется работать с данными, расположенными на внешних устройствах последовательного доступа . Для файлов, расположенных на таких устройствах в каждый момент времени доступен только один компонент последовательности данных, что является существенным ограничением по сравнению с сортировкой массивов , где всегда доступен каждый элемент.
Внешняя сортировка – это сортировка данных, которые расположены на внешних устройствах и не вмещающихся в оперативную память .
Данные, хранящиеся на внешних устройствах , имеют большой объем, что не позволяет их целиком переместить в оперативную память , отсортировать с использованием одного из алгоритмов внутренней сортировки, а затем вернуть их на внешнее устройство . В этом случае осуществлялось бы минимальное количество проходов через файл , то есть было бы однократное чтение и однократная запись данных. Однако на практике приходится осуществлять чтение, обработку и запись данных в файл по блокам, размер которых зависит от операционной системы и имеющегося объема оперативной памяти, что приводит к увеличению числа проходов через файл и заметному снижению скорости сортировки.
К наиболее известным алгоритмам внешних сортировок относятся:
- сортировки слиянием (простое слияние и естественное слияние);
- улучшенные сортировки (многофазная сортировка и каскадная сортировка).
Из представленных внешних сортировок наиболее важным является метод сортировки с помощью слияния. Прежде чем описывать алгоритм сортировки слиянием введем несколько определений.
Основным понятием при использовании внешней сортировки является понятие серии. Серия (упорядоченный отрезок) – это последовательность элементов, которая упорядочена по ключу.
Количество элементов в серии называется длиной серии. Серия, состоящая из одного элемента, упорядочена всегда. Последняя серия может иметь длину меньшую, чем остальные серии файлов. Максимальное количество серий в файле N (все элементы не упорядочены). Минимальное количество серий одна (все элементы упорядочены).
В основе большинства методов внешних сортировок лежит процедура слияния и процедура распределения. Слияние – это процесс объединения двух (или более) упорядоченных серий в одну упорядоченную последовательность при помощи циклического выбора элементов, доступных в данный момент. Распределение – это процесс разделения упорядоченных серий на два и несколько вспомогательных файла.
Фаза – это действия по однократной обработке всей последовательности элементов. Двухфазная сортировка – это сортировка , в которой отдельно реализуется две фазы: распределение и слияние. Однофазная сортировка – это сортировка , в которой объединены фазы распределения и слияния в одну.
Двухпутевым слиянием называется сортировка , в которой данные распределяются на два вспомогательных файла. Многопутевым слиянием называется сортировка , в которой данные распределяются на N (N > 2) вспомогательных файлов.
Общий алгоритм сортировки слиянием
Сначала серии распределяются на два или более вспомогательных файлов. Данное распределение идет поочередно: первая серия записывается в первый вспомогательный файл , вторая – во второй и так далее до последнего вспомогательного файла. Затем опять запись серии начинается в первый вспомогательный файл . После распределения всех серий, они объединяются в более длинные упорядоченные отрезки, то есть из каждого вспомогательного файла берется по одной серии, которые сливаются. Если в каком-то файле серия заканчивается, то переход к следующей серии не осуществляется. В зависимости от вида сортировки сформированная более длинная упорядоченная серия записывается либо в исходный файл , либо в один из вспомогательных файлов. После того как все серии из всех вспомогательных файлов объединены в новые серии, потом опять начинается их распределение. И так до тех пор, пока все данные не будут отсортированы.
Выделим основные характеристики сортировки слиянием:
- количество фаз в реализации сортировки;
- количество вспомогательных файлов, на которые распределяются серии.
Рассмотрим основные и наиболее важные алгоритмы внешних сортировок более подробно.
Сортировка простым слиянием
Одна из сортировок на основе слияния называется простым слиянием.
Алгоритм сортировки простым слияния является простейшим алгоритмом внешней сортировки , основанный на процедуре слияния серией.
В данном алгоритме длина серий фиксируется на каждом шаге. В исходном файле все серии имеют длину 1, после первого шага она равна 2, после второго – 4, после третьего – 8, после k -го шага – 2 k .
Алгоритм сортировки простым слиянием
Шаг 1. Исходный файл f разбивается на два вспомогательных файла f1 и f2 .
Шаг 2. Вспомогательные файлы f1 и f2 сливаются в файл f , при этом одиночные элементы образуют упорядоченные пары.
Шаг 3. Полученный файл f вновь обрабатывается, как указано в шагах 1 и 2. При этом упорядоченные пары переходят в упорядоченные четверки.
Шаг 4. Повторяя шаги, сливаем четверки в восьмерки и т.д., каждый раз удваивая длину слитых последовательностей до тех пор, пока не будет упорядочен целиком весь файл ( рис. 43.1).
После выполнения i проходов получаем два файла, состоящих из серий длины 2 i . Окончание процесса происходит при выполнении условия 2 i >=n . Следовательно, процесс сортировки простым слиянием требует порядка O(log n) проходов по данным.
Признаками конца сортировки простым слиянием являются следующие условия:
- длина серии не меньше количества элементов в файле (определяется после фазы слияния);
- количество серий равно 1 (определяется на фазе слияния).
- при однофазной сортировке второй по счету вспомогательный файл после распределения серий остался пустым.
Заметим, что для выполнения внешней сортировки методом простого слияния в оперативной памяти требуется расположить всего лишь две переменные – для размещения очередных элементов (записей) из вспомогательных файлов. Исходный и вспомогательные файлы будут O(log n) раз прочитаны и столько же раз записаны.
Аннотация: В лекции рассматриваются определение и классификация алгоритмов внешних сортировок, понятия фаз и путей в алгоритмах внешних сортировок, приводятся описания и реализации алгоритмов внешней сортировки слиянием и естественной сортировки.
Цель лекции: изучить основные алгоритмы внешних сортировок, научиться решать задачи сортировок массивов различными методами и выполнять оценку эффективности алгоритмов внешней сортировки .
Внешние сортировки применяются к данным, которые хранятся во внешней памяти. При выполнении таких сортировок требуется работать с данными, расположенными на внешних устройствах последовательного доступа . Для файлов, расположенных на таких устройствах в каждый момент времени доступен только один компонент последовательности данных, что является существенным ограничением по сравнению с сортировкой массивов , где всегда доступен каждый элемент.
Внешняя сортировка – это сортировка данных, которые расположены на внешних устройствах и не вмещающихся в оперативную память .
Данные, хранящиеся на внешних устройствах , имеют большой объем, что не позволяет их целиком переместить в оперативную память , отсортировать с использованием одного из алгоритмов внутренней сортировки, а затем вернуть их на внешнее устройство . В этом случае осуществлялось бы минимальное количество проходов через файл , то есть было бы однократное чтение и однократная запись данных. Однако на практике приходится осуществлять чтение, обработку и запись данных в файл по блокам, размер которых зависит от операционной системы и имеющегося объема оперативной памяти, что приводит к увеличению числа проходов через файл и заметному снижению скорости сортировки.
К наиболее известным алгоритмам внешних сортировок относятся:
- сортировки слиянием (простое слияние и естественное слияние);
- улучшенные сортировки (многофазная сортировка и каскадная сортировка).
Из представленных внешних сортировок наиболее важным является метод сортировки с помощью слияния. Прежде чем описывать алгоритм сортировки слиянием введем несколько определений.
Основным понятием при использовании внешней сортировки является понятие серии. Серия (упорядоченный отрезок) – это последовательность элементов, которая упорядочена по ключу.
Количество элементов в серии называется длиной серии. Серия, состоящая из одного элемента, упорядочена всегда. Последняя серия может иметь длину меньшую, чем остальные серии файлов. Максимальное количество серий в файле N (все элементы не упорядочены). Минимальное количество серий одна (все элементы упорядочены).
В основе большинства методов внешних сортировок лежит процедура слияния и процедура распределения. Слияние – это процесс объединения двух (или более) упорядоченных серий в одну упорядоченную последовательность при помощи циклического выбора элементов, доступных в данный момент. Распределение – это процесс разделения упорядоченных серий на два и несколько вспомогательных файла.
Фаза – это действия по однократной обработке всей последовательности элементов. Двухфазная сортировка – это сортировка , в которой отдельно реализуется две фазы: распределение и слияние. Однофазная сортировка – это сортировка , в которой объединены фазы распределения и слияния в одну.
Двухпутевым слиянием называется сортировка , в которой данные распределяются на два вспомогательных файла. Многопутевым слиянием называется сортировка , в которой данные распределяются на N (N > 2) вспомогательных файлов.
Общий алгоритм сортировки слиянием
Сначала серии распределяются на два или более вспомогательных файлов. Данное распределение идет поочередно: первая серия записывается в первый вспомогательный файл , вторая – во второй и так далее до последнего вспомогательного файла. Затем опять запись серии начинается в первый вспомогательный файл . После распределения всех серий, они объединяются в более длинные упорядоченные отрезки, то есть из каждого вспомогательного файла берется по одной серии, которые сливаются. Если в каком-то файле серия заканчивается, то переход к следующей серии не осуществляется. В зависимости от вида сортировки сформированная более длинная упорядоченная серия записывается либо в исходный файл , либо в один из вспомогательных файлов. После того как все серии из всех вспомогательных файлов объединены в новые серии, потом опять начинается их распределение. И так до тех пор, пока все данные не будут отсортированы.
Выделим основные характеристики сортировки слиянием:
- количество фаз в реализации сортировки;
- количество вспомогательных файлов, на которые распределяются серии.
Рассмотрим основные и наиболее важные алгоритмы внешних сортировок более подробно.
Сортировка простым слиянием
Одна из сортировок на основе слияния называется простым слиянием.
Алгоритм сортировки простым слияния является простейшим алгоритмом внешней сортировки , основанный на процедуре слияния серией.
В данном алгоритме длина серий фиксируется на каждом шаге. В исходном файле все серии имеют длину 1, после первого шага она равна 2, после второго – 4, после третьего – 8, после k -го шага – 2 k .
Алгоритм сортировки простым слиянием
Шаг 1. Исходный файл f разбивается на два вспомогательных файла f1 и f2 .
Шаг 2. Вспомогательные файлы f1 и f2 сливаются в файл f , при этом одиночные элементы образуют упорядоченные пары.
Шаг 3. Полученный файл f вновь обрабатывается, как указано в шагах 1 и 2. При этом упорядоченные пары переходят в упорядоченные четверки.
Шаг 4. Повторяя шаги, сливаем четверки в восьмерки и т.д., каждый раз удваивая длину слитых последовательностей до тех пор, пока не будет упорядочен целиком весь файл ( рис. 43.1).
После выполнения i проходов получаем два файла, состоящих из серий длины 2 i . Окончание процесса происходит при выполнении условия 2 i >=n . Следовательно, процесс сортировки простым слиянием требует порядка O(log n) проходов по данным.
Признаками конца сортировки простым слиянием являются следующие условия:
- длина серии не меньше количества элементов в файле (определяется после фазы слияния);
- количество серий равно 1 (определяется на фазе слияния).
- при однофазной сортировке второй по счету вспомогательный файл после распределения серий остался пустым.
Заметим, что для выполнения внешней сортировки методом простого слияния в оперативной памяти требуется расположить всего лишь две переменные – для размещения очередных элементов (записей) из вспомогательных файлов. Исходный и вспомогательные файлы будут O(log n) раз прочитаны и столько же раз записаны.
В прошлый раз мы обсудили, как можно искусственно ограничить доступную программе память. В качестве бонуса я заполучил себе libmemrestrict – библиотеку с обёртками функций вроде malloc для отслеживания использования памяти, и ptrace-restrict — инструмент на базе ptrace, перехватывающий вызовы brk, sbrk и mmap с той же целью.
Так зачем нам пытаться организовывать ограничение памяти – так ли это часто встречается? Когда в последний раз ООМ прибил ваше приложение? Вы всегда думаете о потреблении памяти во время программирования? Память – штука дешёвая, и если вам не хватает памяти, добавьте ещё пару гигабайт.
И, тем не менее, невозможно бесконечно добавлять память – и не из-за того, что у вас нет бесконечного её источника. При обработке Больших данных просто невозможно вместить весь ввод в массив – необходимо распределять данные между оперативкой, носителями и сетью. Необходимы алгоритмы и техники для такой обработки данных.
И вот я занялся подобными задачами, начав с простой – как отсортировать миллион целых чисел (4 MiB данных) при наличии 2 MiB памяти? Эту задачу можно обобщить на тот случай, когда у вас недостаточно памяти, чтобы вместить все данные.
Необходимо написать программу сортировки набора целых чисел, хранящихся в файле. Для его создания я написал простейшие утилиты randints и rangeints
Программа должна выдавать отсортированный массив на stdout в виде текста
Она должна измерить время работы и вывести его на stderr. Нельзя просто запустить программу через утилиту time, потому что она посчитает время на чтение файла и время на его вывод.
Она должна работать, имея памяти как минимум в два раза меньше объёма файла. Для этого мы применим libmemrestrict или ptrace-restrict.
Для некоторых методов эти утилиты не пригодятся. Например, для mmap они не сработают – придётся физически ограничить использование памяти.
Они будут проверяться для решения оригинальной задачи (сортировки 4 MiB в 2 MiB). Также я запущу их на виртуалке со 128 MiB памяти для сортировки 500 Mb (125 миллионов четырёхбайтных целых).
Наивный подход
Попробуем отсортировать числа напрямую и подсчитаем использование памяти (и время). Просто считаем файл в массив целых, и вызовем qsort.
Попробуем файл с 4 Мб данных. Без ограничений всё работает:
но это неинтересно. Ограничим память 2 MiB:
Поднимем ограничение до 4 MiB – и вновь неудача. (libmemrestrict читает настройки из окружения).
Очевидно, для qsort требуется больше памяти. Посмотрим, сколько он хочет, при помощи massif от valgrind:
Вот вам красивый график:
Видно несколько размещений данных, удваивающих запросы в памяти до 4 MiB – это мой массив, и затем ещё четыре MiB для qsort. Статистика:
4 миллиона байт использую я, и ещё 4 миллиона — qsort_r. И ещё 1,2 MB дополнительно в куче использует massif.
Судя по всему, в этом случае qsort ведёт себя как O(n) по отношению к сложности по объёму. Что странно, поскольку qsort работает «на месте» и использует различные техники оптимизации, гарантирующие сложность по объёму в O(log n). Дополнительное чтение по реализации glibc qsort.
Ладно – а сможет ли он отсортировать 500 MB в 128 MiB RAM?
Конечно, нет. Быстродействие:
Значит, наивная сортировка неплохо работает без ограничений, вообще не работает с ограничениями, а qsort требует себе памяти O(n). Это странно. К примеру, если ограничить память 5,3 Мб, она заработает и не затребует памяти объёмом O(n). Я пока ещё разбираюсь с этим.
Файл и mmap
mmap – хакерский способ сортировки большого количества данных в условиях ограничения памяти. Он перекладывает груз распределения данных между памятью и свопом на плечи операционки.
- Через mmap мы отправляем весь файл в память
- Получаем от него указатель на данные
- Вызываем алгоритм сортировки данных по этому указателю
И всё! Теперь вы не получите переполнение памяти, даже сортируя файл по объёму больший, чем доступная память. Для понимания работы механизма нужно немного разобраться с управлением памятью в ОС.
Каждая программа представлена процессом, у которого есть своё личное, изолированное от других, виртуальное адресное пространство. Длина его ограничена шириной шины CPU, то есть для 32-битного CPU она равна 2 32 , то есть 4 GiB.
Всё размещение памяти, которым занимается процесс, происходит в виртуальной памяти. Эта виртуальная память отображается на физическую подсистемой ядра для работы с памятью — MMU. И обычно происходит в «ленивом» режиме – то есть, когда процесс просит памяти, ядро ему сразу её даёт, но при этом физически не размещает её мгновенно – то есть, страница виртуальной памяти не отображается сразу на физическую. Когда к такой странице происходит доступ (например, на запись), MMU создает исключение «page fault», которое ядро обрабатывает, отображая виртуальную страницу на физическую. Теперь она отображена, и запись в эту страницу будет транслироваться MMU как запись по определённому адресу в физической памяти.
С другой стороны, если помнить, что виртуальное адресное пространство ограничено лишь размером шины CPU, можно попасть в ситуацию, в которой программа захочет занять больше памяти, чем есть в наличии. К примеру, в 32-битной системе, имеющей 256 MiB RAM, процесс может разместить и использовать 1 GiB памяти. В таком случае страницы памяти попадут в своп – они вместо RAM попадут на накопитель, такой, как жёсткий диск. При доступе к такой странице ядро считает её с накопителя и отправит в память (заменяя другую страницу в памяти).
Ядро неплохо справляется с распределением данных между памятью и накопителем, поэтому естественно попытаться использовать это его свойство в нашей задаче. Когда мы вызовем mmap для нашего файла, ядро зарезервирует диапазон виртуальных адресов, который не будет сразу размещён. Когда мы попытаемся получить доступ к ним, ядро подгрузит его из входного файла в память. Когда у нас закончится физическая память, ядро уберёт страницы в своп. Таким образом мы будем балансировать данными между файлом на диске, памятью и свопом.
Ограничением является только виртуальное адресное пространство (4 GiB для 32bit системы и 256 TiB для 64bit), и своп – но накопители сегодня стоят недорого.
В связи с тем, что mmap грузит весь файл в виртуальную память, мы не сможем использовать libmemrestrict или ptrace-restrict, поскольку они ограничивают саму виртуальную память. Попытавшись ограничить сортировку данных объёмом в 100M в виртуальную память объёмом 10M, мы получим ошибку от mmap:
Ничего удивительного – файл грузится в виртуальную память, и ядро распределяет её между физической памятью и свопом. Так что нам нужно не менее 100М виртуальной памяти, плюс ещё немного места для qemu.
Поэтому для данного метода я использую виртуальную машину с 128 MiB памяти. Вот моя программа сортировки, использующая mmap. И всё работает!
Информация от top:
Мы используем 500 Мб виртуальной памяти, а реальная доступная память при этом составляет 90 MiB. Отметим, что MiB это 2 20 , а MB это 10 6 = 1 миллион. И 500 MB = 500 000 000 байт, а 500 000 000 >> 20 = 476 MiB.
Глянув на детали от vmstat во время сортировки 500 MB, мы увидим, как ядро балансирует между свопом, дисковым кэшем, буферами и свободной памятью:
Сначала у нас было ~70 MiB свободной памяти, пустой своп и немножко памяти было отдано под буферы I/O и кэш. Затем после mmap вся эта память ушла на кэш. Когда свободная память кончилась, ядро стало использовать своп, который увеличивается вместе с увеличением загрузки I/O. И мы приходим к тому, что почти вся память отдана под кэш диска – что нормально, поскольку страницы с дисковым кэшем, в случае, когда нам требуется память под приложение, уходят первыми.
Итак, сортировка через mmap – прикольный хак, требующий базовых представлений о работе с памятью, и дающий простое решение для обработки большого количества данных при маленьком количестве памяти.
Внешняя сортировка со слиянием
Допустим, mmap использовать нельзя — вы хотите отсортировать файл в 5 GiB на 32-битной системе.
Существует известный популярный способ под названием «внешняя сортировка со слиянием». Если у вас не хватает памяти, нужно использовать внешний накопитель — например, жёсткий диск. Придётся только работать с данными по кусочку, поскольку в память они все не влезут.
Отсортировали, имея 2 MiB памяти и используя буфер в 1 MiB.
Теперь отсортируем 500 Мб. Сначала отключим своп, поскольку мы управляем обменом кусков данных вручную.
Проверим доступную память:
Будем использовать буфер в 50 Мб – в 10 раз меньше размера файла.
Ничосий, две минуты! С чего бы это? Конечно, из-за операций I/O. Три вещи тормозят процесс. На фазе разделения данных мы последовательно читаем файл, используя маленький буфер. На фазе слияния мы открываем и закрываем файлы с кусками информации. А ещё есть и вывод – на фазе слияния мы выводим 50 Мб данных на stdout, что, несмотря на перенаправление в /dev/null, даёт нагрузочку. Если это отключить, мы получаем прирост быстродействия на 25%.
Использование памяти меня устраивает. Если запустить программу через massif, можно увидеть, что пик потребления – это размер буфера и небольшая куча.
Можно ограничить память и 50 Мб, плюс ещё 500 KB на временные строки, содержащие пути к файлам:
В общем, с памятью – ок, с быстродействием – не ок. mmap позволяла сделать эту операцию за 32 секунды. Давайте улучшать наш способ.
Проведём профилирование программы при помощи gprof. Создадим бинарник
И вызовем программу многократно для накопления статистики при помощи моего удобственного скрипта из статьи по gprof. Вот результат:
Большая часть времени ушла на сортировку и вывод. Но не забудьте, что gprof не показывает время, ушедшее на системные вызовы и I/O.
- добавить во внешнюю сортировку многопоточность и трюки с I/O
- взять другой алгоритм сортировки
Универсальная внешняя сортировка со слиянием – это простая идея для сортировки больших данных при малом количестве памяти, но без каких-либо улучшений она работает медленно.
Настраиваем сортировку
- readahead (только в Linux).
- posix_fadvise с POSIX_FADV_SEQUENTIAL.
Они сообщают подсистеме управления памятью о том, как мы будем читать данные. В нашем случае чтение последовательно, поэтому было бы неплохо увидеть содержимое файла в кэше страниц.
На фазе слияния мы можем не делать постоянные открытия и закрытия файлов, а создать выделенные потоки для каждого из файлов. Каждый поток будет держать открытым свой файлик, а мы будем заполнять для него буфер. Когда он заполняется, он сортируется и выводится. И ещё для каждого потока будет работать readahead.
Вот усовершенствованная многопоточная версия внешней сортировки со слиянием. Ну, как я и сказал, многопоточность – не очень хорошая идея. На одноядерном проце разницы никакой нет.
Это с выводом данных. А без вывода:
Ну ладно, давайте попробуем на четырёхъядерной машине (Intel Core i7-3612QM CPU @ 2.10GHz):
- исполнение потоков независимо
- ресурсы ввода и вывода могут работать параллельно – например, как RAID
У нас потоки взаимозависимы – главному потоку приходится ждать сортировки буфера, а уже потом начинать следующее чтение из файла. И чтение для разделения идёт быстрее, чем сортировка буфера, поэтому большую часть времени потоки ждут, пока основной поток закончит работу.
Нужны другие способы улучшения алгоритма.
Особые алгоритмы сортировки
- не используют сравнения
- не требуют загрузки всего массива в память
Они работают лучше, чем O(n log(n)) – нижняя граница для сравнивающих алгоритмов вроде QuickSort. Но не все они подойдут в случае ограничения памяти. Поэтому я остановился на использовании сортировки подсчётом
Сортировка подсчётом
Если у нас много данных с малым разбросом, можно использовать сортировку подсчётом. Идея проста – мы будем хранить в памяти не данные, а массив счётчиков. Мы последовательно читаем данные и увеличиваем соответствующие счётчики. Сложность алгоритма по времени линейна, а по объёму – пропорциональна диапазону данных.
Простая реализация работает с массивом от 0 до N. Целые числа соответствуют индексам массива. Вот мой вариант, который неплохо работает и без всякого тюнинга. Второй аргумент – размер буфера в элементах. Буферизация сильно ускоряет работу, поскольку программа читает из файла не по 4 байта.
Угумс. Полгига данных отсортировано за 3 с половиной секунды на 128 MiB памяти и одном CPU. Сравним с qsort или mmap:
В 23 раза быстрее!
Но не забывайте об ограничениях – только целые числа (или их эквивалент), и небольшой их последовательный промежуток. Я пытался делать вариант с непоследовательными промежутками через хэши и бинарный поиск – но быстродействие у него очень плохое.
А если мы предположим уникальность наших чисел, то счётчики могут быть только в двух состояниях – есть или нет, поэтому они могут быть однобитными. Тогда наш массив ужмётся. Да и массив нам не нужен – мы можем хранить числа в виде битов, то есть вместо массива у нас будет вектор. Читаем файл и устанавливаем N-ный бит, если там встретилось число N. После этого просто проходимся по вектору и выводим в файл те числа, для которых взведены биты.
Такие решения требуют внимательного подхода, поскольку всё равно можно выйти за пределы ограничений. К примеру, для сортировки всех чисел из промежутка целых (2 32 ), вам понадобится 1 бит на каждое число, а это 4294967296 бит = 536870912 байт = 512 MiB. А у нас есть только 128 MiB, чего вам не хватит. Но в некоторых случаях выигрыш будет колоссальным – вот история на эту тему из «Programming Pearls» by Jon Bentley.
Знание ваших данных очень полезно.
Читайте также: