_Автор оригинала на английском языке — хабраюзер [dzeban][1] _

#### Введение

[В прошлый раз мы обсудили][2], как можно искусственно ограничить доступную программе память. В качестве бонуса я заполучил себе [libmemrestrict ][3]– библиотеку с обёртками функций вроде malloc для отслеживания использования памяти, и [ptrace-restrict ][4]— инструмент на базе ptrace, перехватывающий вызовы brk, sbrk и mmap с той же целью. Так зачем нам пытаться организовывать ограничение памяти – так ли это часто встречается? Когда в последний раз ООМ прибил ваше приложение? Вы всегда думаете о потреблении памяти во время программирования? Память – штука дешёвая, и если вам не хватает памяти, добавьте ещё пару гигабайт. И, тем не менее, невозможно бесконечно добавлять память – и не из-за того, что у вас нет бесконечного её источника. При обработке Больших данных просто невозможно вместить весь ввод в массив – необходимо распределять данные между оперативкой, носителями и сетью. Необходимы алгоритмы и техники для такой обработки данных. И вот я занялся подобными задачами, начав с простой – как отсортировать миллион целых чисел (4 MiB данных) при наличии 2 MiB памяти? Эту задачу можно обобщить на тот случай, когда у вас недостаточно памяти, чтобы вместить все данные.

#### Дано

Необходимо написать программу сортировки набора целых чисел, хранящихся в файле. Для его создания я написал простейшие утилиты [randints ][5]и [rangeints][6] Программа должна выдавать отсортированный массив на stdout в виде текста Она должна измерить время работы и вывести его на stderr. Нельзя просто запустить программу через утилиту time, потому что она посчитает время на чтение файла и время на его вывод. Она должна работать, имея памяти как минимум в два раза меньше объёма файла. Для этого мы применим libmemrestrict или ptrace-restrict. Для некоторых методов эти утилиты не пригодятся. Например, для mmap они не сработают – придётся физически ограничить использование памяти. Они будут проверяться для решения оригинальной задачи (сортировки 4 MiB в 2 MiB). Также я запущу их на виртуалке со 128 MiB памяти для сортировки 500 Mb (125 миллионов четырёхбайтных целых). [Читать дальше →][7]

[1]: http://habrahabr.ru/users/dzeban/
[2]: http://habrahabr.ru/post/266083/
[3]: https://github.com/dzeban/restrict-memory/blob/master/memrestrict.c
[4]: https://github.com/dzeban/restrict-memory/blob/master/ptrace-restrict.c
[5]: https://github.com/dzeban/cs/blob/master/number/randints.c
[6]: https://github.com/dzeban/cs/blob/master/number/rangeints.c
[7]: http://habrahabr.ru/post/266557/#habracut