{"id":265316,"date":"2015-09-10T01:05:02","date_gmt":"2015-09-09T21:05:02","guid":{"rendered":"http:\/\/savepearlharbor.com\/?p=265316"},"modified":"-0001-11-30T00:00:00","modified_gmt":"-0001-11-29T21:00:00","slug":"","status":"publish","type":"post","link":"https:\/\/savepearlharbor.com\/?p=265316","title":{"rendered":"\u0421\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0430 \u0446\u0435\u043b\u044b\u0445 \u0447\u0438\u0441\u0435\u043b \u043f\u0440\u0438 \u043d\u0435\u0445\u0432\u0430\u0442\u043a\u0435 \u043f\u0430\u043c\u044f\u0442\u0438"},"content":{"rendered":"<p>       <i>\u0410\u0432\u0442\u043e\u0440 \u043e\u0440\u0438\u0433\u0438\u043d\u0430\u043b\u0430 \u043d\u0430 \u0430\u043d\u0433\u043b\u0438\u0439\u0441\u043a\u043e\u043c \u044f\u0437\u044b\u043a\u0435 \u2014 \u0445\u0430\u0431\u0440\u0430\u044e\u0437\u0435\u0440  <a href=\"http:\/\/habrahabr.ru\/users\/dzeban\/\" class=\"user_link\">dzeban<\/a> <\/i><\/p>\n<h4>\u0412\u0432\u0435\u0434\u0435\u043d\u0438\u0435<\/h4>\n<p>  <a href=\"http:\/\/habrahabr.ru\/post\/266083\/\">\u0412 \u043f\u0440\u043e\u0448\u043b\u044b\u0439 \u0440\u0430\u0437 \u043c\u044b \u043e\u0431\u0441\u0443\u0434\u0438\u043b\u0438<\/a>, \u043a\u0430\u043a \u043c\u043e\u0436\u043d\u043e \u0438\u0441\u043a\u0443\u0441\u0441\u0442\u0432\u0435\u043d\u043d\u043e \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0438\u0442\u044c \u0434\u043e\u0441\u0442\u0443\u043f\u043d\u0443\u044e \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0435 \u043f\u0430\u043c\u044f\u0442\u044c. \u0412 \u043a\u0430\u0447\u0435\u0441\u0442\u0432\u0435 \u0431\u043e\u043d\u0443\u0441\u0430 \u044f \u0437\u0430\u043f\u043e\u043b\u0443\u0447\u0438\u043b \u0441\u0435\u0431\u0435 <a href=\"https:\/\/github.com\/dzeban\/restrict-memory\/blob\/master\/memrestrict.c\">libmemrestrict <\/a>\u2013 \u0431\u0438\u0431\u043b\u0438\u043e\u0442\u0435\u043a\u0443 \u0441 \u043e\u0431\u0451\u0440\u0442\u043a\u0430\u043c\u0438 \u0444\u0443\u043d\u043a\u0446\u0438\u0439 \u0432\u0440\u043e\u0434\u0435 malloc \u0434\u043b\u044f \u043e\u0442\u0441\u043b\u0435\u0436\u0438\u0432\u0430\u043d\u0438\u044f \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u044f \u043f\u0430\u043c\u044f\u0442\u0438, \u0438 <a href=\"https:\/\/github.com\/dzeban\/restrict-memory\/blob\/master\/ptrace-restrict.c\">ptrace-restrict <\/a>\u2014 \u0438\u043d\u0441\u0442\u0440\u0443\u043c\u0435\u043d\u0442 \u043d\u0430 \u0431\u0430\u0437\u0435 ptrace, \u043f\u0435\u0440\u0435\u0445\u0432\u0430\u0442\u044b\u0432\u0430\u044e\u0449\u0438\u0439 \u0432\u044b\u0437\u043e\u0432\u044b brk, sbrk \u0438 mmap \u0441 \u0442\u043e\u0439 \u0436\u0435 \u0446\u0435\u043b\u044c\u044e.<\/p>\n<p>  \u0422\u0430\u043a \u0437\u0430\u0447\u0435\u043c \u043d\u0430\u043c \u043f\u044b\u0442\u0430\u0442\u044c\u0441\u044f \u043e\u0440\u0433\u0430\u043d\u0438\u0437\u043e\u0432\u044b\u0432\u0430\u0442\u044c \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u0435 \u043f\u0430\u043c\u044f\u0442\u0438 \u2013 \u0442\u0430\u043a \u043b\u0438 \u044d\u0442\u043e \u0447\u0430\u0441\u0442\u043e \u0432\u0441\u0442\u0440\u0435\u0447\u0430\u0435\u0442\u0441\u044f? \u041a\u043e\u0433\u0434\u0430 \u0432 \u043f\u043e\u0441\u043b\u0435\u0434\u043d\u0438\u0439 \u0440\u0430\u0437 \u041e\u041e\u041c \u043f\u0440\u0438\u0431\u0438\u043b \u0432\u0430\u0448\u0435 \u043f\u0440\u0438\u043b\u043e\u0436\u0435\u043d\u0438\u0435? \u0412\u044b \u0432\u0441\u0435\u0433\u0434\u0430 \u0434\u0443\u043c\u0430\u0435\u0442\u0435 \u043e \u043f\u043e\u0442\u0440\u0435\u0431\u043b\u0435\u043d\u0438\u0438 \u043f\u0430\u043c\u044f\u0442\u0438 \u0432\u043e \u0432\u0440\u0435\u043c\u044f \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f? \u041f\u0430\u043c\u044f\u0442\u044c \u2013 \u0448\u0442\u0443\u043a\u0430 \u0434\u0435\u0448\u0451\u0432\u0430\u044f, \u0438 \u0435\u0441\u043b\u0438 \u0432\u0430\u043c \u043d\u0435 \u0445\u0432\u0430\u0442\u0430\u0435\u0442 \u043f\u0430\u043c\u044f\u0442\u0438, \u0434\u043e\u0431\u0430\u0432\u044c\u0442\u0435 \u0435\u0449\u0451 \u043f\u0430\u0440\u0443 \u0433\u0438\u0433\u0430\u0431\u0430\u0439\u0442.<\/p>\n<p>  \u0418, \u0442\u0435\u043c \u043d\u0435 \u043c\u0435\u043d\u0435\u0435, \u043d\u0435\u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e \u0431\u0435\u0441\u043a\u043e\u043d\u0435\u0447\u043d\u043e \u0434\u043e\u0431\u0430\u0432\u043b\u044f\u0442\u044c \u043f\u0430\u043c\u044f\u0442\u044c \u2013 \u0438 \u043d\u0435 \u0438\u0437-\u0437\u0430 \u0442\u043e\u0433\u043e, \u0447\u0442\u043e \u0443 \u0432\u0430\u0441 \u043d\u0435\u0442 \u0431\u0435\u0441\u043a\u043e\u043d\u0435\u0447\u043d\u043e\u0433\u043e \u0435\u0451 \u0438\u0441\u0442\u043e\u0447\u043d\u0438\u043a\u0430. \u041f\u0440\u0438 \u043e\u0431\u0440\u0430\u0431\u043e\u0442\u043a\u0435 \u0411\u043e\u043b\u044c\u0448\u0438\u0445 \u0434\u0430\u043d\u043d\u044b\u0445 \u043f\u0440\u043e\u0441\u0442\u043e \u043d\u0435\u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e \u0432\u043c\u0435\u0441\u0442\u0438\u0442\u044c \u0432\u0435\u0441\u044c \u0432\u0432\u043e\u0434 \u0432 \u043c\u0430\u0441\u0441\u0438\u0432 \u2013 \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e \u0440\u0430\u0441\u043f\u0440\u0435\u0434\u0435\u043b\u044f\u0442\u044c \u0434\u0430\u043d\u043d\u044b\u0435 \u043c\u0435\u0436\u0434\u0443 \u043e\u043f\u0435\u0440\u0430\u0442\u0438\u0432\u043a\u043e\u0439, \u043d\u043e\u0441\u0438\u0442\u0435\u043b\u044f\u043c\u0438 \u0438 \u0441\u0435\u0442\u044c\u044e. \u041d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u044b \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u044b \u0438 \u0442\u0435\u0445\u043d\u0438\u043a\u0438 \u0434\u043b\u044f \u0442\u0430\u043a\u043e\u0439 \u043e\u0431\u0440\u0430\u0431\u043e\u0442\u043a\u0438 \u0434\u0430\u043d\u043d\u044b\u0445.<\/p>\n<p>  \u0418 \u0432\u043e\u0442 \u044f \u0437\u0430\u043d\u044f\u043b\u0441\u044f \u043f\u043e\u0434\u043e\u0431\u043d\u044b\u043c\u0438 \u0437\u0430\u0434\u0430\u0447\u0430\u043c\u0438, \u043d\u0430\u0447\u0430\u0432 \u0441 \u043f\u0440\u043e\u0441\u0442\u043e\u0439 \u2013 \u043a\u0430\u043a \u043e\u0442\u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u043c\u0438\u043b\u043b\u0438\u043e\u043d \u0446\u0435\u043b\u044b\u0445 \u0447\u0438\u0441\u0435\u043b (4 MiB \u0434\u0430\u043d\u043d\u044b\u0445) \u043f\u0440\u0438 \u043d\u0430\u043b\u0438\u0447\u0438\u0438 2 MiB \u043f\u0430\u043c\u044f\u0442\u0438? \u042d\u0442\u0443 \u0437\u0430\u0434\u0430\u0447\u0443 \u043c\u043e\u0436\u043d\u043e \u043e\u0431\u043e\u0431\u0449\u0438\u0442\u044c \u043d\u0430 \u0442\u043e\u0442 \u0441\u043b\u0443\u0447\u0430\u0439, \u043a\u043e\u0433\u0434\u0430 \u0443 \u0432\u0430\u0441 \u043d\u0435\u0434\u043e\u0441\u0442\u0430\u0442\u043e\u0447\u043d\u043e \u043f\u0430\u043c\u044f\u0442\u0438, \u0447\u0442\u043e\u0431\u044b \u0432\u043c\u0435\u0441\u0442\u0438\u0442\u044c \u0432\u0441\u0435 \u0434\u0430\u043d\u043d\u044b\u0435.<\/p>\n<h4>\u0414\u0430\u043d\u043e<\/h4>\n<p>  \u041d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e \u043d\u0430\u043f\u0438\u0441\u0430\u0442\u044c \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0443 \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0438 \u043d\u0430\u0431\u043e\u0440\u0430 \u0446\u0435\u043b\u044b\u0445 \u0447\u0438\u0441\u0435\u043b, \u0445\u0440\u0430\u043d\u044f\u0449\u0438\u0445\u0441\u044f \u0432 \u0444\u0430\u0439\u043b\u0435. \u0414\u043b\u044f \u0435\u0433\u043e \u0441\u043e\u0437\u0434\u0430\u043d\u0438\u044f \u044f \u043d\u0430\u043f\u0438\u0441\u0430\u043b \u043f\u0440\u043e\u0441\u0442\u0435\u0439\u0448\u0438\u0435 \u0443\u0442\u0438\u043b\u0438\u0442\u044b <a href=\"https:\/\/github.com\/dzeban\/cs\/blob\/master\/number\/randints.c\">randints <\/a>\u0438 <a href=\"https:\/\/github.com\/dzeban\/cs\/blob\/master\/number\/rangeints.c\">rangeints<\/a><\/p>\n<p>  \u041f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0430 \u0434\u043e\u043b\u0436\u043d\u0430 \u0432\u044b\u0434\u0430\u0432\u0430\u0442\u044c \u043e\u0442\u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u044b\u0439 \u043c\u0430\u0441\u0441\u0438\u0432 \u043d\u0430 stdout \u0432 \u0432\u0438\u0434\u0435 \u0442\u0435\u043a\u0441\u0442\u0430<\/p>\n<p>  \u041e\u043d\u0430 \u0434\u043e\u043b\u0436\u043d\u0430 \u0438\u0437\u043c\u0435\u0440\u0438\u0442\u044c \u0432\u0440\u0435\u043c\u044f \u0440\u0430\u0431\u043e\u0442\u044b \u0438 \u0432\u044b\u0432\u0435\u0441\u0442\u0438 \u0435\u0433\u043e \u043d\u0430 stderr. \u041d\u0435\u043b\u044c\u0437\u044f \u043f\u0440\u043e\u0441\u0442\u043e \u0437\u0430\u043f\u0443\u0441\u0442\u0438\u0442\u044c \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0443 \u0447\u0435\u0440\u0435\u0437 \u0443\u0442\u0438\u043b\u0438\u0442\u0443 time, \u043f\u043e\u0442\u043e\u043c\u0443 \u0447\u0442\u043e \u043e\u043d\u0430 \u043f\u043e\u0441\u0447\u0438\u0442\u0430\u0435\u0442 \u0432\u0440\u0435\u043c\u044f \u043d\u0430 \u0447\u0442\u0435\u043d\u0438\u0435 \u0444\u0430\u0439\u043b\u0430 \u0438 \u0432\u0440\u0435\u043c\u044f \u043d\u0430 \u0435\u0433\u043e \u0432\u044b\u0432\u043e\u0434.<\/p>\n<p>  \u041e\u043d\u0430 \u0434\u043e\u043b\u0436\u043d\u0430 \u0440\u0430\u0431\u043e\u0442\u0430\u0442\u044c, \u0438\u043c\u0435\u044f \u043f\u0430\u043c\u044f\u0442\u0438 \u043a\u0430\u043a \u043c\u0438\u043d\u0438\u043c\u0443\u043c \u0432 \u0434\u0432\u0430 \u0440\u0430\u0437\u0430 \u043c\u0435\u043d\u044c\u0448\u0435 \u043e\u0431\u044a\u0451\u043c\u0430 \u0444\u0430\u0439\u043b\u0430. \u0414\u043b\u044f \u044d\u0442\u043e\u0433\u043e \u043c\u044b \u043f\u0440\u0438\u043c\u0435\u043d\u0438\u043c libmemrestrict \u0438\u043b\u0438 ptrace-restrict.<\/p>\n<p>  \u0414\u043b\u044f \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u043c\u0435\u0442\u043e\u0434\u043e\u0432 \u044d\u0442\u0438 \u0443\u0442\u0438\u043b\u0438\u0442\u044b \u043d\u0435 \u043f\u0440\u0438\u0433\u043e\u0434\u044f\u0442\u0441\u044f. \u041d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u0434\u043b\u044f mmap \u043e\u043d\u0438 \u043d\u0435 \u0441\u0440\u0430\u0431\u043e\u0442\u0430\u044e\u0442 \u2013 \u043f\u0440\u0438\u0434\u0451\u0442\u0441\u044f \u0444\u0438\u0437\u0438\u0447\u0435\u0441\u043a\u0438 \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0438\u0442\u044c \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u0435 \u043f\u0430\u043c\u044f\u0442\u0438.<\/p>\n<p>  \u041e\u043d\u0438 \u0431\u0443\u0434\u0443\u0442 \u043f\u0440\u043e\u0432\u0435\u0440\u044f\u0442\u044c\u0441\u044f \u0434\u043b\u044f \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u043e\u0440\u0438\u0433\u0438\u043d\u0430\u043b\u044c\u043d\u043e\u0439 \u0437\u0430\u0434\u0430\u0447\u0438 (\u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0438 4 MiB \u0432 2 MiB). \u0422\u0430\u043a\u0436\u0435 \u044f \u0437\u0430\u043f\u0443\u0449\u0443 \u0438\u0445 \u043d\u0430 \u0432\u0438\u0440\u0442\u0443\u0430\u043b\u043a\u0435 \u0441\u043e 128 MiB \u043f\u0430\u043c\u044f\u0442\u0438 \u0434\u043b\u044f \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0438 500 Mb (125 \u043c\u0438\u043b\u043b\u0438\u043e\u043d\u043e\u0432 \u0447\u0435\u0442\u044b\u0440\u0451\u0445\u0431\u0430\u0439\u0442\u043d\u044b\u0445 \u0446\u0435\u043b\u044b\u0445).<br \/>  <a name=\"habracut\"><\/a>  <\/p>\n<h4>\u041d\u0430\u0438\u0432\u043d\u044b\u0439 \u043f\u043e\u0434\u0445\u043e\u0434<\/h4>\n<p>  \u041f\u043e\u043f\u0440\u043e\u0431\u0443\u0435\u043c \u043e\u0442\u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u0447\u0438\u0441\u043b\u0430 \u043d\u0430\u043f\u0440\u044f\u043c\u0443\u044e \u0438 \u043f\u043e\u0434\u0441\u0447\u0438\u0442\u0430\u0435\u043c \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u0435 \u043f\u0430\u043c\u044f\u0442\u0438 (\u0438 \u0432\u0440\u0435\u043c\u044f). <a href=\"https:\/\/github.com\/dzeban\/cs\/blob\/master\/sorting\/external\/naive.c\">\u041f\u0440\u043e\u0441\u0442\u043e \u0441\u0447\u0438\u0442\u0430\u0435\u043c \u0444\u0430\u0439\u043b <\/a>\u0432 \u043c\u0430\u0441\u0441\u0438\u0432 \u0446\u0435\u043b\u044b\u0445, \u0438 \u0432\u044b\u0437\u043e\u0432\u0435\u043c qsort.<\/p>\n<p>  \u041f\u043e\u043f\u0440\u043e\u0431\u0443\u0435\u043c \u0444\u0430\u0439\u043b \u0441 4 \u041c\u0431 \u0434\u0430\u043d\u043d\u044b\u0445. \u0411\u0435\u0437 \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u0439 \u0432\u0441\u0451 \u0440\u0430\u0431\u043e\u0442\u0430\u0435\u0442:<\/p>\n<pre><code class=\"bash\">$ .\/naive 4M.bin &gt; \/dev\/null 4000000 bytes sorted in 0.323146 seconds <\/code><\/pre>\n<p>  \u043d\u043e \u044d\u0442\u043e \u043d\u0435\u0438\u043d\u0442\u0435\u0440\u0435\u0441\u043d\u043e. \u041e\u0433\u0440\u0430\u043d\u0438\u0447\u0438\u043c \u043f\u0430\u043c\u044f\u0442\u044c 2 MiB:<\/p>\n<pre><code class=\"bash\">$ LD_PRELOAD=.\/libmemrestrict.so .\/naive ints &gt; ints.sorted  Segmentation fault <\/code><\/pre>\n<p>  \u041f\u043e\u0434\u043d\u0438\u043c\u0435\u043c \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u0435 \u0434\u043e 4 MiB \u2013 \u0438 \u0432\u043d\u043e\u0432\u044c \u043d\u0435\u0443\u0434\u0430\u0447\u0430. (libmemrestrict \u0447\u0438\u0442\u0430\u0435\u0442 \u043d\u0430\u0441\u0442\u0440\u043e\u0439\u043a\u0438 \u0438\u0437 \u043e\u043a\u0440\u0443\u0436\u0435\u043d\u0438\u044f). <\/p>\n<pre><code class=\"bash\">$ MR_THRESHOLD=5000000 LD_PRELOAD=.\/libmemrestrict.so .\/naive ints &gt; ints.sorted  Segmentation fault <\/code><\/pre>\n<p>  \u041e\u0447\u0435\u0432\u0438\u0434\u043d\u043e, \u0434\u043b\u044f qsort \u0442\u0440\u0435\u0431\u0443\u0435\u0442\u0441\u044f \u0431\u043e\u043b\u044c\u0448\u0435 \u043f\u0430\u043c\u044f\u0442\u0438. \u041f\u043e\u0441\u043c\u043e\u0442\u0440\u0438\u043c, \u0441\u043a\u043e\u043b\u044c\u043a\u043e \u043e\u043d \u0445\u043e\u0447\u0435\u0442, \u043f\u0440\u0438 \u043f\u043e\u043c\u043e\u0449\u0438 <a href=\"http:\/\/alex.dzyoba.com\/linux\/profiling-valgrind.html#massif\">massif \u043e\u0442 valgrind<\/a>:<\/p>\n<pre><code class=\"bash\">$ valgrind --tool=massif .\/naive ints  $ ms_print massif.out.10676 <\/code><\/pre>\n<p>  \u0412\u043e\u0442 \u0432\u0430\u043c \u043a\u0440\u0430\u0441\u0438\u0432\u044b\u0439 \u0433\u0440\u0430\u0444\u0438\u043a:<\/p>\n<pre><code class=\"bash\">    MB     8.819^               :::::::::::::::::::::::::::#                               |                   :                          #                               |                   :                          #                               |                   :                          #                               |                   :                          #                               |                   :                          #                               |                   :                          #                               |                   :                          #                               |                   :                          #                               |            :::::::@                          #::::::::::::::::::::::::       |            :      @                          #                               |            :      @                          #                               |            :      @                          #                               |            :      @                          #                               |            :      @                          #                               |      @@@@@@:      @                          #                               |      @     :      @                          #                               |      @     :      @                          #                               |   :::@     :      @                          #                               | :::  @     :      @                          #                                 0 +-----------------------------------------------------------------------&gt;Gi      0                                                                   1.721 <\/code><\/pre>\n<p>  \u0412\u0438\u0434\u043d\u043e \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u0440\u0430\u0437\u043c\u0435\u0449\u0435\u043d\u0438\u0439 \u0434\u0430\u043d\u043d\u044b\u0445, \u0443\u0434\u0432\u0430\u0438\u0432\u0430\u044e\u0449\u0438\u0445 \u0437\u0430\u043f\u0440\u043e\u0441\u044b \u0432 \u043f\u0430\u043c\u044f\u0442\u0438 \u0434\u043e 4 MiB \u2013 \u044d\u0442\u043e \u043c\u043e\u0439 \u043c\u0430\u0441\u0441\u0438\u0432, \u0438 \u0437\u0430\u0442\u0435\u043c \u0435\u0449\u0451 \u0447\u0435\u0442\u044b\u0440\u0435 MiB \u0434\u043b\u044f qsort. \u0421\u0442\u0430\u0442\u0438\u0441\u0442\u0438\u043a\u0430:<\/p>\n<pre><code class=\"bash\">--------------------------------------------------------------------------------   n        time(i)         total(B)   useful-heap(B) extra-heap(B)    stacks(B) --------------------------------------------------------------------------------  21    173,222,581        5,247,504        4,000,568     1,246,936            0  22    173,223,802        5,246,920        4,000,000     1,246,920            0  23    173,226,655        5,247,504        4,000,568     1,246,936            0  24    173,229,202        5,246,920        4,000,000     1,246,920            0  25    173,229,311        9,246,928        8,000,000     1,246,928            0  26    869,058,772        9,246,928        8,000,000     1,246,928            0 86.52% (8,000,000B) (heap allocation functions) malloc\/new\/new[], --alloc-fns, etc. -&gt;43.26% (4,000,000B) 0x400A26: readfile (in \/home\/avd\/dev\/cs\/sorting\/external\/naive) | -&gt;43.26% (4,000,000B) 0x400ACD: main (in \/home\/avd\/dev\/cs\/sorting\/external\/naive) |    -&gt;43.26% (4,000,000B) 0x35D40383F7: qsort_r (in \/usr\/lib64\/libc-2.18.so) | -&gt;43.26% (4,000,000B) 0x400B3D: main (in \/home\/avd\/dev\/cs\/sorting\/external\/naive) |    -&gt;00.00% (0B) in 1+ places, all below ms_print's threshold (01.00%) <\/code><\/pre>\n<p>  4 \u043c\u0438\u043b\u043b\u0438\u043e\u043d\u0430 \u0431\u0430\u0439\u0442 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u044e \u044f, \u0438 \u0435\u0449\u0451 4 \u043c\u0438\u043b\u043b\u0438\u043e\u043d\u0430 \u2014 qsort_r. \u0418 \u0435\u0449\u0451 1,2 MB \u0434\u043e\u043f\u043e\u043b\u043d\u0438\u0442\u0435\u043b\u044c\u043d\u043e \u0432 \u043a\u0443\u0447\u0435 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u0442 massif.<\/p>\n<p>  \u0421\u0443\u0434\u044f \u043f\u043e \u0432\u0441\u0435\u043c\u0443, \u0432 \u044d\u0442\u043e\u043c \u0441\u043b\u0443\u0447\u0430\u0435 qsort \u0432\u0435\u0434\u0451\u0442 \u0441\u0435\u0431\u044f \u043a\u0430\u043a O(n) \u043f\u043e \u043e\u0442\u043d\u043e\u0448\u0435\u043d\u0438\u044e \u043a \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u0438 \u043f\u043e \u043e\u0431\u044a\u0451\u043c\u0443. \u0427\u0442\u043e \u0441\u0442\u0440\u0430\u043d\u043d\u043e, \u043f\u043e\u0441\u043a\u043e\u043b\u044c\u043a\u0443 qsort \u0440\u0430\u0431\u043e\u0442\u0430\u0435\u0442 \u00ab\u043d\u0430 \u043c\u0435\u0441\u0442\u0435\u00bb \u0438 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u0442 \u0440\u0430\u0437\u043b\u0438\u0447\u043d\u044b\u0435 \u0442\u0435\u0445\u043d\u0438\u043a\u0438 \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u0438, \u0433\u0430\u0440\u0430\u043d\u0442\u0438\u0440\u0443\u044e\u0449\u0438\u0435 \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c \u043f\u043e \u043e\u0431\u044a\u0451\u043c\u0443 \u0432 O(log n). \u0414\u043e\u043f\u043e\u043b\u043d\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0435 \u0447\u0442\u0435\u043d\u0438\u0435 \u043f\u043e \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u0438 glibc qsort.<\/p>\n<p>  \u041b\u0430\u0434\u043d\u043e \u2013 \u0430 \u0441\u043c\u043e\u0436\u0435\u0442 \u043b\u0438 \u043e\u043d \u043e\u0442\u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u0430\u0442\u044c 500 MB \u0432 128 MiB RAM?<\/p>\n<pre><code class=\"bash\">$ .\/naive 500M.bin &gt; \/dev\/null Segmentation fault <\/code><\/pre>\n<p>  \u041a\u043e\u043d\u0435\u0447\u043d\u043e, \u043d\u0435\u0442. \u0411\u044b\u0441\u0442\u0440\u043e\u0434\u0435\u0439\u0441\u0442\u0432\u0438\u0435:<\/p>\n<pre><code class=\"bash\">$ .\/naive 4M.bin &gt; \/dev\/null 4000000 bytes sorted in 0.322712 seconds <\/code><\/pre>\n<p>  \u0417\u043d\u0430\u0447\u0438\u0442, \u043d\u0430\u0438\u0432\u043d\u0430\u044f \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0430 \u043d\u0435\u043f\u043b\u043e\u0445\u043e \u0440\u0430\u0431\u043e\u0442\u0430\u0435\u0442 \u0431\u0435\u0437 \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u0439, \u0432\u043e\u043e\u0431\u0449\u0435 \u043d\u0435 \u0440\u0430\u0431\u043e\u0442\u0430\u0435\u0442 \u0441 \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u044f\u043c\u0438, \u0430 qsort \u0442\u0440\u0435\u0431\u0443\u0435\u0442 \u0441\u0435\u0431\u0435 \u043f\u0430\u043c\u044f\u0442\u0438 O(n). \u042d\u0442\u043e \u0441\u0442\u0440\u0430\u043d\u043d\u043e. \u041a \u043f\u0440\u0438\u043c\u0435\u0440\u0443, \u0435\u0441\u043b\u0438 \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0438\u0442\u044c \u043f\u0430\u043c\u044f\u0442\u044c 5,3 \u041c\u0431, \u043e\u043d\u0430 \u0437\u0430\u0440\u0430\u0431\u043e\u0442\u0430\u0435\u0442 \u0438 \u043d\u0435 \u0437\u0430\u0442\u0440\u0435\u0431\u0443\u0435\u0442 \u043f\u0430\u043c\u044f\u0442\u0438 \u043e\u0431\u044a\u0451\u043c\u043e\u043c O(n). \u042f \u043f\u043e\u043a\u0430 \u0435\u0449\u0451 \u0440\u0430\u0437\u0431\u0438\u0440\u0430\u044e\u0441\u044c \u0441 \u044d\u0442\u0438\u043c.<\/p>\n<h4>\u0424\u0430\u0439\u043b \u0438 mmap <\/h4>\n<p>  mmap \u2013 \u0445\u0430\u043a\u0435\u0440\u0441\u043a\u0438\u0439 \u0441\u043f\u043e\u0441\u043e\u0431 \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0438 \u0431\u043e\u043b\u044c\u0448\u043e\u0433\u043e \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u0430 \u0434\u0430\u043d\u043d\u044b\u0445 \u0432 \u0443\u0441\u043b\u043e\u0432\u0438\u044f\u0445 \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u044f \u043f\u0430\u043c\u044f\u0442\u0438. \u041e\u043d \u043f\u0435\u0440\u0435\u043a\u043b\u0430\u0434\u044b\u0432\u0430\u0435\u0442 \u0433\u0440\u0443\u0437 \u0440\u0430\u0441\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u0438\u044f \u0434\u0430\u043d\u043d\u044b\u0445 \u043c\u0435\u0436\u0434\u0443 \u043f\u0430\u043c\u044f\u0442\u044c\u044e \u0438 \u0441\u0432\u043e\u043f\u043e\u043c \u043d\u0430 \u043f\u043b\u0435\u0447\u0438 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u043e\u043d\u043a\u0438.<\/p>\n<p>  \u0420\u0430\u0431\u043e\u0442\u0430\u0435\u0442 \u044d\u0442\u043e \u0442\u0430\u043a:  <\/p>\n<ul>\n<li>\u0427\u0435\u0440\u0435\u0437 mmap \u043c\u044b \u043e\u0442\u043f\u0440\u0430\u0432\u043b\u044f\u0435\u043c \u0432\u0435\u0441\u044c \u0444\u0430\u0439\u043b \u0432 \u043f\u0430\u043c\u044f\u0442\u044c<\/li>\n<li>\u041f\u043e\u043b\u0443\u0447\u0430\u0435\u043c \u043e\u0442 \u043d\u0435\u0433\u043e \u0443\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u044c \u043d\u0430 \u0434\u0430\u043d\u043d\u044b\u0435<\/li>\n<li>\u0412\u044b\u0437\u044b\u0432\u0430\u0435\u043c \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0438 \u0434\u0430\u043d\u043d\u044b\u0445 \u043f\u043e \u044d\u0442\u043e\u043c\u0443 \u0443\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u044e<\/li>\n<\/ul>\n<p>  \u0418 \u0432\u0441\u0451! \u0422\u0435\u043f\u0435\u0440\u044c \u0432\u044b \u043d\u0435 \u043f\u043e\u043b\u0443\u0447\u0438\u0442\u0435 \u043f\u0435\u0440\u0435\u043f\u043e\u043b\u043d\u0435\u043d\u0438\u0435 \u043f\u0430\u043c\u044f\u0442\u0438, \u0434\u0430\u0436\u0435 \u0441\u043e\u0440\u0442\u0438\u0440\u0443\u044f \u0444\u0430\u0439\u043b \u043f\u043e \u043e\u0431\u044a\u0451\u043c\u0443 \u0431\u043e\u043b\u044c\u0448\u0438\u0439, \u0447\u0435\u043c \u0434\u043e\u0441\u0442\u0443\u043f\u043d\u0430\u044f \u043f\u0430\u043c\u044f\u0442\u044c. \u0414\u043b\u044f \u043f\u043e\u043d\u0438\u043c\u0430\u043d\u0438\u044f \u0440\u0430\u0431\u043e\u0442\u044b \u043c\u0435\u0445\u0430\u043d\u0438\u0437\u043c\u0430 \u043d\u0443\u0436\u043d\u043e \u043d\u0435\u043c\u043d\u043e\u0433\u043e \u0440\u0430\u0437\u043e\u0431\u0440\u0430\u0442\u044c\u0441\u044f \u0441 \u0443\u043f\u0440\u0430\u0432\u043b\u0435\u043d\u0438\u0435\u043c \u043f\u0430\u043c\u044f\u0442\u044c\u044e \u0432 \u041e\u0421.<\/p>\n<p>  \u041a\u0430\u0436\u0434\u0430\u044f \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0430 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0430 \u043f\u0440\u043e\u0446\u0435\u0441\u0441\u043e\u043c, \u0443 \u043a\u043e\u0442\u043e\u0440\u043e\u0433\u043e \u0435\u0441\u0442\u044c \u0441\u0432\u043e\u0451 \u043b\u0438\u0447\u043d\u043e\u0435, \u0438\u0437\u043e\u043b\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u043e\u0435 \u043e\u0442 \u0434\u0440\u0443\u0433\u0438\u0445, \u0432\u0438\u0440\u0442\u0443\u0430\u043b\u044c\u043d\u043e\u0435 \u0430\u0434\u0440\u0435\u0441\u043d\u043e\u0435 \u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u0441\u0442\u0432\u043e. \u0414\u043b\u0438\u043d\u0430 \u0435\u0433\u043e \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0430 \u0448\u0438\u0440\u0438\u043d\u043e\u0439 \u0448\u0438\u043d\u044b CPU, \u0442\u043e \u0435\u0441\u0442\u044c \u0434\u043b\u044f 32-\u0431\u0438\u0442\u043d\u043e\u0433\u043e CPU \u043e\u043d\u0430 \u0440\u0430\u0432\u043d\u0430 2<sup>32<\/sup>, \u0442\u043e \u0435\u0441\u0442\u044c 4 GiB.<\/p>\n<p>  \u0412\u0441\u0451 \u0440\u0430\u0437\u043c\u0435\u0449\u0435\u043d\u0438\u0435 \u043f\u0430\u043c\u044f\u0442\u0438, \u043a\u043e\u0442\u043e\u0440\u044b\u043c \u0437\u0430\u043d\u0438\u043c\u0430\u0435\u0442\u0441\u044f \u043f\u0440\u043e\u0446\u0435\u0441\u0441, \u043f\u0440\u043e\u0438\u0441\u0445\u043e\u0434\u0438\u0442 \u0432 \u0432\u0438\u0440\u0442\u0443\u0430\u043b\u044c\u043d\u043e\u0439 \u043f\u0430\u043c\u044f\u0442\u0438. \u042d\u0442\u0430 \u0432\u0438\u0440\u0442\u0443\u0430\u043b\u044c\u043d\u0430\u044f \u043f\u0430\u043c\u044f\u0442\u044c \u043e\u0442\u043e\u0431\u0440\u0430\u0436\u0430\u0435\u0442\u0441\u044f \u043d\u0430 \u0444\u0438\u0437\u0438\u0447\u0435\u0441\u043a\u0443\u044e \u043f\u043e\u0434\u0441\u0438\u0441\u0442\u0435\u043c\u043e\u0439 \u044f\u0434\u0440\u0430 \u0434\u043b\u044f \u0440\u0430\u0431\u043e\u0442\u044b \u0441 \u043f\u0430\u043c\u044f\u0442\u044c\u044e \u2014 MMU. \u0418 \u043e\u0431\u044b\u0447\u043d\u043e \u043f\u0440\u043e\u0438\u0441\u0445\u043e\u0434\u0438\u0442 \u0432 \u00ab\u043b\u0435\u043d\u0438\u0432\u043e\u043c\u00bb \u0440\u0435\u0436\u0438\u043c\u0435 \u2013 \u0442\u043e \u0435\u0441\u0442\u044c, \u043a\u043e\u0433\u0434\u0430 \u043f\u0440\u043e\u0446\u0435\u0441\u0441 \u043f\u0440\u043e\u0441\u0438\u0442 \u043f\u0430\u043c\u044f\u0442\u0438, \u044f\u0434\u0440\u043e \u0435\u043c\u0443 \u0441\u0440\u0430\u0437\u0443 \u0435\u0451 \u0434\u0430\u0451\u0442, \u043d\u043e \u043f\u0440\u0438 \u044d\u0442\u043e\u043c \u0444\u0438\u0437\u0438\u0447\u0435\u0441\u043a\u0438 \u043d\u0435 \u0440\u0430\u0437\u043c\u0435\u0449\u0430\u0435\u0442 \u0435\u0451 \u043c\u0433\u043d\u043e\u0432\u0435\u043d\u043d\u043e \u2013 \u0442\u043e \u0435\u0441\u0442\u044c, \u0441\u0442\u0440\u0430\u043d\u0438\u0446\u0430 \u0432\u0438\u0440\u0442\u0443\u0430\u043b\u044c\u043d\u043e\u0439 \u043f\u0430\u043c\u044f\u0442\u0438 \u043d\u0435 \u043e\u0442\u043e\u0431\u0440\u0430\u0436\u0430\u0435\u0442\u0441\u044f \u0441\u0440\u0430\u0437\u0443 \u043d\u0430 \u0444\u0438\u0437\u0438\u0447\u0435\u0441\u043a\u0443\u044e. \u041a\u043e\u0433\u0434\u0430 \u043a \u0442\u0430\u043a\u043e\u0439 \u0441\u0442\u0440\u0430\u043d\u0438\u0446\u0435 \u043f\u0440\u043e\u0438\u0441\u0445\u043e\u0434\u0438\u0442 \u0434\u043e\u0441\u0442\u0443\u043f (\u043d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u043d\u0430 \u0437\u0430\u043f\u0438\u0441\u044c), MMU \u0441\u043e\u0437\u0434\u0430\u0435\u0442 \u0438\u0441\u043a\u043b\u044e\u0447\u0435\u043d\u0438\u0435 \u00abpage fault\u00bb, \u043a\u043e\u0442\u043e\u0440\u043e\u0435 \u044f\u0434\u0440\u043e \u043e\u0431\u0440\u0430\u0431\u0430\u0442\u044b\u0432\u0430\u0435\u0442, \u043e\u0442\u043e\u0431\u0440\u0430\u0436\u0430\u044f \u0432\u0438\u0440\u0442\u0443\u0430\u043b\u044c\u043d\u0443\u044e \u0441\u0442\u0440\u0430\u043d\u0438\u0446\u0443 \u043d\u0430 \u0444\u0438\u0437\u0438\u0447\u0435\u0441\u043a\u0443\u044e. \u0422\u0435\u043f\u0435\u0440\u044c \u043e\u043d\u0430 \u043e\u0442\u043e\u0431\u0440\u0430\u0436\u0435\u043d\u0430, \u0438 \u0437\u0430\u043f\u0438\u0441\u044c \u0432 \u044d\u0442\u0443 \u0441\u0442\u0440\u0430\u043d\u0438\u0446\u0443 <a href=\"http:\/\/en.wikipedia.org\/wiki\/Memory_management_unit\">\u0431\u0443\u0434\u0435\u0442 \u0442\u0440\u0430\u043d\u0441\u043b\u0438\u0440\u043e\u0432\u0430\u0442\u044c\u0441\u044f MMU <\/a>\u043a\u0430\u043a \u0437\u0430\u043f\u0438\u0441\u044c \u043f\u043e \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0451\u043d\u043d\u043e\u043c\u0443 \u0430\u0434\u0440\u0435\u0441\u0443 \u0432 \u0444\u0438\u0437\u0438\u0447\u0435\u0441\u043a\u043e\u0439 \u043f\u0430\u043c\u044f\u0442\u0438.<\/p>\n<p>  \u0421 \u0434\u0440\u0443\u0433\u043e\u0439 \u0441\u0442\u043e\u0440\u043e\u043d\u044b, \u0435\u0441\u043b\u0438 \u043f\u043e\u043c\u043d\u0438\u0442\u044c, \u0447\u0442\u043e \u0432\u0438\u0440\u0442\u0443\u0430\u043b\u044c\u043d\u043e\u0435 \u0430\u0434\u0440\u0435\u0441\u043d\u043e\u0435 \u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u0441\u0442\u0432\u043e \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u043e \u043b\u0438\u0448\u044c \u0440\u0430\u0437\u043c\u0435\u0440\u043e\u043c \u0448\u0438\u043d\u044b CPU, \u043c\u043e\u0436\u043d\u043e \u043f\u043e\u043f\u0430\u0441\u0442\u044c \u0432 \u0441\u0438\u0442\u0443\u0430\u0446\u0438\u044e, \u0432 \u043a\u043e\u0442\u043e\u0440\u043e\u0439 \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0430 \u0437\u0430\u0445\u043e\u0447\u0435\u0442 \u0437\u0430\u043d\u044f\u0442\u044c \u0431\u043e\u043b\u044c\u0448\u0435 \u043f\u0430\u043c\u044f\u0442\u0438, \u0447\u0435\u043c \u0435\u0441\u0442\u044c \u0432 \u043d\u0430\u043b\u0438\u0447\u0438\u0438. \u041a \u043f\u0440\u0438\u043c\u0435\u0440\u0443, \u0432 32-\u0431\u0438\u0442\u043d\u043e\u0439 \u0441\u0438\u0441\u0442\u0435\u043c\u0435, \u0438\u043c\u0435\u044e\u0449\u0435\u0439 256 MiB RAM, \u043f\u0440\u043e\u0446\u0435\u0441\u0441 \u043c\u043e\u0436\u0435\u0442 \u0440\u0430\u0437\u043c\u0435\u0441\u0442\u0438\u0442\u044c \u0438 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c 1 GiB \u043f\u0430\u043c\u044f\u0442\u0438. \u0412 \u0442\u0430\u043a\u043e\u043c \u0441\u043b\u0443\u0447\u0430\u0435 \u0441\u0442\u0440\u0430\u043d\u0438\u0446\u044b \u043f\u0430\u043c\u044f\u0442\u0438 \u043f\u043e\u043f\u0430\u0434\u0443\u0442 \u0432 \u0441\u0432\u043e\u043f \u2013 \u043e\u043d\u0438 \u0432\u043c\u0435\u0441\u0442\u043e RAM \u043f\u043e\u043f\u0430\u0434\u0443\u0442 \u043d\u0430 \u043d\u0430\u043a\u043e\u043f\u0438\u0442\u0435\u043b\u044c, \u0442\u0430\u043a\u043e\u0439, \u043a\u0430\u043a \u0436\u0451\u0441\u0442\u043a\u0438\u0439 \u0434\u0438\u0441\u043a. \u041f\u0440\u0438 \u0434\u043e\u0441\u0442\u0443\u043f\u0435 \u043a \u0442\u0430\u043a\u043e\u0439 \u0441\u0442\u0440\u0430\u043d\u0438\u0446\u0435 \u044f\u0434\u0440\u043e \u0441\u0447\u0438\u0442\u0430\u0435\u0442 \u0435\u0451 \u0441 \u043d\u0430\u043a\u043e\u043f\u0438\u0442\u0435\u043b\u044f \u0438 \u043e\u0442\u043f\u0440\u0430\u0432\u0438\u0442 \u0432 \u043f\u0430\u043c\u044f\u0442\u044c (\u0437\u0430\u043c\u0435\u043d\u044f\u044f \u0434\u0440\u0443\u0433\u0443\u044e \u0441\u0442\u0440\u0430\u043d\u0438\u0446\u0443 \u0432 \u043f\u0430\u043c\u044f\u0442\u0438).<\/p>\n<p>  \u042f\u0434\u0440\u043e \u043d\u0435\u043f\u043b\u043e\u0445\u043e \u0441\u043f\u0440\u0430\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u0441 \u0440\u0430\u0441\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u0438\u0435\u043c \u0434\u0430\u043d\u043d\u044b\u0445 \u043c\u0435\u0436\u0434\u0443 \u043f\u0430\u043c\u044f\u0442\u044c\u044e \u0438 \u043d\u0430\u043a\u043e\u043f\u0438\u0442\u0435\u043b\u0435\u043c, \u043f\u043e\u044d\u0442\u043e\u043c\u0443 \u0435\u0441\u0442\u0435\u0441\u0442\u0432\u0435\u043d\u043d\u043e \u043f\u043e\u043f\u044b\u0442\u0430\u0442\u044c\u0441\u044f \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c \u044d\u0442\u043e \u0435\u0433\u043e \u0441\u0432\u043e\u0439\u0441\u0442\u0432\u043e \u0432 \u043d\u0430\u0448\u0435\u0439 \u0437\u0430\u0434\u0430\u0447\u0435. \u041a\u043e\u0433\u0434\u0430 \u043c\u044b \u0432\u044b\u0437\u043e\u0432\u0435\u043c mmap \u0434\u043b\u044f \u043d\u0430\u0448\u0435\u0433\u043e \u0444\u0430\u0439\u043b\u0430, \u044f\u0434\u0440\u043e \u0437\u0430\u0440\u0435\u0437\u0435\u0440\u0432\u0438\u0440\u0443\u0435\u0442 \u0434\u0438\u0430\u043f\u0430\u0437\u043e\u043d \u0432\u0438\u0440\u0442\u0443\u0430\u043b\u044c\u043d\u044b\u0445 \u0430\u0434\u0440\u0435\u0441\u043e\u0432, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u043d\u0435 \u0431\u0443\u0434\u0435\u0442 \u0441\u0440\u0430\u0437\u0443 \u0440\u0430\u0437\u043c\u0435\u0449\u0451\u043d. \u041a\u043e\u0433\u0434\u0430 \u043c\u044b \u043f\u043e\u043f\u044b\u0442\u0430\u0435\u043c\u0441\u044f \u043f\u043e\u043b\u0443\u0447\u0438\u0442\u044c \u0434\u043e\u0441\u0442\u0443\u043f \u043a \u043d\u0438\u043c, \u044f\u0434\u0440\u043e \u043f\u043e\u0434\u0433\u0440\u0443\u0437\u0438\u0442 \u0435\u0433\u043e \u0438\u0437 \u0432\u0445\u043e\u0434\u043d\u043e\u0433\u043e \u0444\u0430\u0439\u043b\u0430 \u0432 \u043f\u0430\u043c\u044f\u0442\u044c. \u041a\u043e\u0433\u0434\u0430 \u0443 \u043d\u0430\u0441 \u0437\u0430\u043a\u043e\u043d\u0447\u0438\u0442\u0441\u044f \u0444\u0438\u0437\u0438\u0447\u0435\u0441\u043a\u0430\u044f \u043f\u0430\u043c\u044f\u0442\u044c, \u044f\u0434\u0440\u043e \u0443\u0431\u0435\u0440\u0451\u0442 \u0441\u0442\u0440\u0430\u043d\u0438\u0446\u044b \u0432 \u0441\u0432\u043e\u043f. \u0422\u0430\u043a\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c \u043c\u044b \u0431\u0443\u0434\u0435\u043c \u0431\u0430\u043b\u0430\u043d\u0441\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u0434\u0430\u043d\u043d\u044b\u043c\u0438 \u043c\u0435\u0436\u0434\u0443 \u0444\u0430\u0439\u043b\u043e\u043c \u043d\u0430 \u0434\u0438\u0441\u043a\u0435, \u043f\u0430\u043c\u044f\u0442\u044c\u044e \u0438 \u0441\u0432\u043e\u043f\u043e\u043c.<\/p>\n<p>  \u041e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u0435\u043c \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u0442\u043e\u043b\u044c\u043a\u043e \u0432\u0438\u0440\u0442\u0443\u0430\u043b\u044c\u043d\u043e\u0435 \u0430\u0434\u0440\u0435\u0441\u043d\u043e\u0435 \u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u0441\u0442\u0432\u043e (4 GiB \u0434\u043b\u044f 32bit \u0441\u0438\u0441\u0442\u0435\u043c\u044b \u0438 256 TiB \u0434\u043b\u044f 64bit), \u0438 \u0441\u0432\u043e\u043f \u2013 \u043d\u043e \u043d\u0430\u043a\u043e\u043f\u0438\u0442\u0435\u043b\u0438 \u0441\u0435\u0433\u043e\u0434\u043d\u044f \u0441\u0442\u043e\u044f\u0442 \u043d\u0435\u0434\u043e\u0440\u043e\u0433\u043e.<\/p>\n<p>  \u0412 \u0441\u0432\u044f\u0437\u0438 \u0441 \u0442\u0435\u043c, \u0447\u0442\u043e mmap \u0433\u0440\u0443\u0437\u0438\u0442 \u0432\u0435\u0441\u044c \u0444\u0430\u0439\u043b \u0432 \u0432\u0438\u0440\u0442\u0443\u0430\u043b\u044c\u043d\u0443\u044e \u043f\u0430\u043c\u044f\u0442\u044c, \u043c\u044b \u043d\u0435 \u0441\u043c\u043e\u0436\u0435\u043c \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c libmemrestrict \u0438\u043b\u0438 ptrace-restrict, \u043f\u043e\u0441\u043a\u043e\u043b\u044c\u043a\u0443 \u043e\u043d\u0438 \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0438\u0432\u0430\u044e\u0442 \u0441\u0430\u043c\u0443 \u0432\u0438\u0440\u0442\u0443\u0430\u043b\u044c\u043d\u0443\u044e \u043f\u0430\u043c\u044f\u0442\u044c. \u041f\u043e\u043f\u044b\u0442\u0430\u0432\u0448\u0438\u0441\u044c \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0438\u0442\u044c \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0443 \u0434\u0430\u043d\u043d\u044b\u0445 \u043e\u0431\u044a\u0451\u043c\u043e\u043c \u0432 100M \u0432 \u0432\u0438\u0440\u0442\u0443\u0430\u043b\u044c\u043d\u0443\u044e \u043f\u0430\u043c\u044f\u0442\u044c \u043e\u0431\u044a\u0451\u043c\u043e\u043c 10M, \u043c\u044b \u043f\u043e\u043b\u0443\u0447\u0438\u043c \u043e\u0448\u0438\u0431\u043a\u0443 \u043e\u0442 mmap:<\/p>\n<pre><code class=\"bash\">$ qemu-x86_64 -R 10M .\/mmaped 100M.bin  mmap stack: Cannot allocate memory <\/code><\/pre>\n<p>  \u041d\u0438\u0447\u0435\u0433\u043e \u0443\u0434\u0438\u0432\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0433\u043e \u2013 \u0444\u0430\u0439\u043b \u0433\u0440\u0443\u0437\u0438\u0442\u0441\u044f \u0432 \u0432\u0438\u0440\u0442\u0443\u0430\u043b\u044c\u043d\u0443\u044e \u043f\u0430\u043c\u044f\u0442\u044c, \u0438 \u044f\u0434\u0440\u043e \u0440\u0430\u0441\u043f\u0440\u0435\u0434\u0435\u043b\u044f\u0435\u0442 \u0435\u0451 \u043c\u0435\u0436\u0434\u0443 \u0444\u0438\u0437\u0438\u0447\u0435\u0441\u043a\u043e\u0439 \u043f\u0430\u043c\u044f\u0442\u044c\u044e \u0438 \u0441\u0432\u043e\u043f\u043e\u043c. \u0422\u0430\u043a \u0447\u0442\u043e \u043d\u0430\u043c \u043d\u0443\u0436\u043d\u043e \u043d\u0435 \u043c\u0435\u043d\u0435\u0435 100\u041c \u0432\u0438\u0440\u0442\u0443\u0430\u043b\u044c\u043d\u043e\u0439 \u043f\u0430\u043c\u044f\u0442\u0438, \u043f\u043b\u044e\u0441 \u0435\u0449\u0451 \u043d\u0435\u043c\u043d\u043e\u0433\u043e \u043c\u0435\u0441\u0442\u0430 \u0434\u043b\u044f qemu.<\/p>\n<p>  \u041f\u043e\u044d\u0442\u043e\u043c\u0443 \u0434\u043b\u044f \u0434\u0430\u043d\u043d\u043e\u0433\u043e \u043c\u0435\u0442\u043e\u0434\u0430 \u044f \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u044e \u0432\u0438\u0440\u0442\u0443\u0430\u043b\u044c\u043d\u0443\u044e \u043c\u0430\u0448\u0438\u043d\u0443 \u0441 128 MiB \u043f\u0430\u043c\u044f\u0442\u0438. <a href=\"https:\/\/github.com\/dzeban\/cs\/blob\/master\/sorting\/external\/mmaped.c\">\u0412\u043e\u0442 \u043c\u043e\u044f \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0430 \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0438<\/a>, \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u044e\u0449\u0430\u044f mmap. \u0418 \u0432\u0441\u0451 \u0440\u0430\u0431\u043e\u0442\u0430\u0435\u0442!<\/p>\n<pre><code class=\"bash\">$ free -m              total       used       free     shared    buffers     cached Mem:           119         42         76          0          4         16 -\/+ buffers\/cache:         21         97 Swap:          382          0        382  $ ll -h 500M.bin -rw-r--r-- 1 root root 477M Feb  3 05:39 500M.bin  $ .\/mmaped 500M.bin &gt; \/dev\/null 500000000 bytes sorted in 32.250000 seconds <\/code><\/pre>\n<p>  \u0418\u043d\u0444\u043e\u0440\u043c\u0430\u0446\u0438\u044f \u043e\u0442 top:<\/p>\n<pre><code class=\"bash\">PID  USER      PR  NI  VIRT  RES  SHR S  %CPU %MEM    TIME+  COMMAND 3167 root      20   0  480m  90m  90m R  84.6 76.4   1:18.65 mmaped  <\/code><\/pre>\n<p>  \u041c\u044b \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u043c 500 \u041c\u0431 \u0432\u0438\u0440\u0442\u0443\u0430\u043b\u044c\u043d\u043e\u0439 \u043f\u0430\u043c\u044f\u0442\u0438, \u0430 \u0440\u0435\u0430\u043b\u044c\u043d\u0430\u044f \u0434\u043e\u0441\u0442\u0443\u043f\u043d\u0430\u044f \u043f\u0430\u043c\u044f\u0442\u044c \u043f\u0440\u0438 \u044d\u0442\u043e\u043c \u0441\u043e\u0441\u0442\u0430\u0432\u043b\u044f\u0435\u0442 90 MiB. \u041e\u0442\u043c\u0435\u0442\u0438\u043c, \u0447\u0442\u043e MiB \u044d\u0442\u043e 2<sup>20<\/sup>, \u0430 MB \u044d\u0442\u043e 10<sup>6<\/sup> = 1 \u043c\u0438\u043b\u043b\u0438\u043e\u043d. \u0418 500 MB = 500 000 000 \u0431\u0430\u0439\u0442, \u0430 500 000 000 &gt;&gt; 20 = 476 MiB.<\/p>\n<p>  \u0413\u043b\u044f\u043d\u0443\u0432 \u043d\u0430 \u0434\u0435\u0442\u0430\u043b\u0438 \u043e\u0442 vmstat \u0432\u043e \u0432\u0440\u0435\u043c\u044f \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0438 500 MB, \u043c\u044b \u0443\u0432\u0438\u0434\u0438\u043c, \u043a\u0430\u043a \u044f\u0434\u0440\u043e \u0431\u0430\u043b\u0430\u043d\u0441\u0438\u0440\u0443\u0435\u0442 \u043c\u0435\u0436\u0434\u0443 \u0441\u0432\u043e\u043f\u043e\u043c, \u0434\u0438\u0441\u043a\u043e\u0432\u044b\u043c \u043a\u044d\u0448\u0435\u043c, \u0431\u0443\u0444\u0435\u0440\u0430\u043c\u0438 \u0438 \u0441\u0432\u043e\u0431\u043e\u0434\u043d\u043e\u0439 \u043f\u0430\u043c\u044f\u0442\u044c\u044e:<\/p>\n<pre><code class=\"bash\">procs -----------memory---------- ---swap-- -----io---- -system-- ----cpu----  r  b   swpd   free   buff  cache   si   so    bi    bo   in   cs us sy id wa  0  0      0  77776   2120  15104    1   27   710   971   24   34  3  1 95  1  1  1      0   2060    488  90068    1   27   785  1057   25   37  3  1 95  1  1  0    928   3400     60  89744    1   27   799  1092   25   38  3  1 94  1  0  2   1908   1928    212  92040    1   27   852  1174   26   40  4  1 94  1  0  2   3436   2360    280  93056    1   27   911  1282   28   42  4  1 94  2  0  0   5272   3688    196  94688    1   27  1066  1471   31   48  4  1 93  2  0  0   5272   3720    204  94700    1   27  1064  1469   31   48  4  1 93  2 <\/code><\/pre>\n<p>  \u0421\u043d\u0430\u0447\u0430\u043b\u0430 \u0443 \u043d\u0430\u0441 \u0431\u044b\u043b\u043e ~70 MiB \u0441\u0432\u043e\u0431\u043e\u0434\u043d\u043e\u0439 \u043f\u0430\u043c\u044f\u0442\u0438, \u043f\u0443\u0441\u0442\u043e\u0439 \u0441\u0432\u043e\u043f \u0438 \u043d\u0435\u043c\u043d\u043e\u0436\u043a\u043e \u043f\u0430\u043c\u044f\u0442\u0438 \u0431\u044b\u043b\u043e \u043e\u0442\u0434\u0430\u043d\u043e \u043f\u043e\u0434 \u0431\u0443\u0444\u0435\u0440\u044b I\/O \u0438 \u043a\u044d\u0448. \u0417\u0430\u0442\u0435\u043c \u043f\u043e\u0441\u043b\u0435 mmap \u0432\u0441\u044f \u044d\u0442\u0430 \u043f\u0430\u043c\u044f\u0442\u044c \u0443\u0448\u043b\u0430 \u043d\u0430 \u043a\u044d\u0448. \u041a\u043e\u0433\u0434\u0430 \u0441\u0432\u043e\u0431\u043e\u0434\u043d\u0430\u044f \u043f\u0430\u043c\u044f\u0442\u044c \u043a\u043e\u043d\u0447\u0438\u043b\u0430\u0441\u044c, \u044f\u0434\u0440\u043e \u0441\u0442\u0430\u043b\u043e \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c \u0441\u0432\u043e\u043f, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u0443\u0432\u0435\u043b\u0438\u0447\u0438\u0432\u0430\u0435\u0442\u0441\u044f \u0432\u043c\u0435\u0441\u0442\u0435 \u0441 \u0443\u0432\u0435\u043b\u0438\u0447\u0435\u043d\u0438\u0435\u043c \u0437\u0430\u0433\u0440\u0443\u0437\u043a\u0438 I\/O. \u0418 \u043c\u044b \u043f\u0440\u0438\u0445\u043e\u0434\u0438\u043c \u043a \u0442\u043e\u043c\u0443, \u0447\u0442\u043e \u043f\u043e\u0447\u0442\u0438 \u0432\u0441\u044f \u043f\u0430\u043c\u044f\u0442\u044c \u043e\u0442\u0434\u0430\u043d\u0430 \u043f\u043e\u0434 \u043a\u044d\u0448 \u0434\u0438\u0441\u043a\u0430 \u2013 \u0447\u0442\u043e \u043d\u043e\u0440\u043c\u0430\u043b\u044c\u043d\u043e, \u043f\u043e\u0441\u043a\u043e\u043b\u044c\u043a\u0443 \u0441\u0442\u0440\u0430\u043d\u0438\u0446\u044b \u0441 \u0434\u0438\u0441\u043a\u043e\u0432\u044b\u043c \u043a\u044d\u0448\u0435\u043c, \u0432 \u0441\u043b\u0443\u0447\u0430\u0435, \u043a\u043e\u0433\u0434\u0430 \u043d\u0430\u043c \u0442\u0440\u0435\u0431\u0443\u0435\u0442\u0441\u044f \u043f\u0430\u043c\u044f\u0442\u044c \u043f\u043e\u0434 \u043f\u0440\u0438\u043b\u043e\u0436\u0435\u043d\u0438\u0435, \u0443\u0445\u043e\u0434\u044f\u0442 \u043f\u0435\u0440\u0432\u044b\u043c\u0438.<\/p>\n<p>  \u0418\u0442\u0430\u043a, \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0430 \u0447\u0435\u0440\u0435\u0437 mmap \u2013 \u043f\u0440\u0438\u043a\u043e\u043b\u044c\u043d\u044b\u0439 \u0445\u0430\u043a, \u0442\u0440\u0435\u0431\u0443\u044e\u0449\u0438\u0439 \u0431\u0430\u0437\u043e\u0432\u044b\u0445 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u0439 \u043e \u0440\u0430\u0431\u043e\u0442\u0435 \u0441 \u043f\u0430\u043c\u044f\u0442\u044c\u044e, \u0438 \u0434\u0430\u044e\u0449\u0438\u0439 \u043f\u0440\u043e\u0441\u0442\u043e\u0435 \u0440\u0435\u0448\u0435\u043d\u0438\u0435 \u0434\u043b\u044f \u043e\u0431\u0440\u0430\u0431\u043e\u0442\u043a\u0438 \u0431\u043e\u043b\u044c\u0448\u043e\u0433\u043e \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u0430 \u0434\u0430\u043d\u043d\u044b\u0445 \u043f\u0440\u0438 \u043c\u0430\u043b\u0435\u043d\u044c\u043a\u043e\u043c \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u0435 \u043f\u0430\u043c\u044f\u0442\u0438.<\/p>\n<h4>\u0412\u043d\u0435\u0448\u043d\u044f\u044f \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0430 \u0441\u043e \u0441\u043b\u0438\u044f\u043d\u0438\u0435\u043c<\/h4>\n<p>  \u0414\u043e\u043f\u0443\u0441\u0442\u0438\u043c, mmap \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c \u043d\u0435\u043b\u044c\u0437\u044f \u2014 \u0432\u044b \u0445\u043e\u0442\u0438\u0442\u0435 \u043e\u0442\u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u0444\u0430\u0439\u043b \u0432 5 GiB \u043d\u0430 32-\u0431\u0438\u0442\u043d\u043e\u0439 \u0441\u0438\u0441\u0442\u0435\u043c\u0435.<\/p>\n<p>  \u0421\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u0435\u0442 \u0438\u0437\u0432\u0435\u0441\u0442\u043d\u044b\u0439 \u043f\u043e\u043f\u0443\u043b\u044f\u0440\u043d\u044b\u0439 \u0441\u043f\u043e\u0441\u043e\u0431 \u043f\u043e\u0434 \u043d\u0430\u0437\u0432\u0430\u043d\u0438\u0435\u043c \u00ab\u0432\u043d\u0435\u0448\u043d\u044f\u044f \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0430 \u0441\u043e \u0441\u043b\u0438\u044f\u043d\u0438\u0435\u043c\u00bb. \u0415\u0441\u043b\u0438 \u0443 \u0432\u0430\u0441 \u043d\u0435 \u0445\u0432\u0430\u0442\u0430\u0435\u0442 \u043f\u0430\u043c\u044f\u0442\u0438, \u043d\u0443\u0436\u043d\u043e \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c \u0432\u043d\u0435\u0448\u043d\u0438\u0439 \u043d\u0430\u043a\u043e\u043f\u0438\u0442\u0435\u043b\u044c \u2014 \u043d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u0436\u0451\u0441\u0442\u043a\u0438\u0439 \u0434\u0438\u0441\u043a. \u041f\u0440\u0438\u0434\u0451\u0442\u0441\u044f \u0442\u043e\u043b\u044c\u043a\u043e \u0440\u0430\u0431\u043e\u0442\u0430\u0442\u044c \u0441 \u0434\u0430\u043d\u043d\u044b\u043c\u0438 \u043f\u043e \u043a\u0443\u0441\u043e\u0447\u043a\u0443, \u043f\u043e\u0441\u043a\u043e\u043b\u044c\u043a\u0443 \u0432 \u043f\u0430\u043c\u044f\u0442\u044c \u043e\u043d\u0438 \u0432\u0441\u0435 \u043d\u0435 \u0432\u043b\u0435\u0437\u0443\u0442.<\/p>\n<p>  \u0412\u043d\u0435\u0448\u043d\u044f\u044f \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0430 \u0441\u043e \u0441\u043b\u0438\u044f\u043d\u0438\u0435\u043c \u0440\u0430\u0431\u043e\u0442\u0430\u0435\u0442 \u0442\u0430\u043a:  <\/p>\n<ul>\n<li>\u0440\u0430\u0437\u0431\u0438\u0432\u0430\u0435\u0442\u0435 \u0434\u0430\u043d\u043d\u044b\u0435 \u043d\u0430 \u043a\u0443\u0441\u043a\u0438 \u043f\u043e \u043e\u0431\u044a\u0451\u043c\u0443 \u0434\u043e\u0441\u0442\u0443\u043f\u043d\u043e\u0439 \u043f\u0430\u043c\u044f\u0442\u0438<\/li>\n<li>\u043a\u0430\u0436\u0434\u044b\u0439 \u043a\u0443\u0441\u043e\u043a \u0441\u043e\u0440\u0442\u0438\u0440\u0443\u0435\u0442\u0441\u044f \u0432 \u043f\u0430\u043c\u044f\u0442\u0438 \u0438 \u043f\u0438\u0448\u0435\u0442\u0441\u044f \u043d\u0430 \u0432\u043d\u0435\u0448\u043d\u0438\u0439 \u043d\u043e\u0441\u0438\u0442\u0435\u043b\u044c<\/li>\n<li>\u0442\u0435\u043f\u0435\u0440\u044c \u0443 \u0432\u0430\u0441 \u0435\u0441\u0442\u044c \u043a\u0443\u0441\u043a\u0438 \u0440\u0430\u0437\u043c\u0435\u0440\u043e\u043c filesize\/buffersize<\/li>\n<li>\u0447\u0438\u0442\u0430\u0435\u0442\u0435 \u0447\u0430\u0441\u0442\u0438 \u043a\u0443\u0441\u043a\u043e\u0432 \u0440\u0430\u0437\u043c\u0435\u0440\u043e\u043c buffersize\/#chunks, \u0447\u0442\u043e\u0431\u044b \u043e\u0431\u044a\u0435\u0434\u0438\u043d\u0438\u0442\u044c \u0438\u0445 \u0432 \u0431\u0443\u0444\u0435\u0440\u0435 \u0438 \u0432\u044b\u0432\u0435\u0441\u0442\u0438 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442 \u0432 \u0444\u0430\u0439\u043b<\/li>\n<\/ul>\n<p>  \u042f \u0441\u0434\u0435\u043b\u0430\u043b <a href=\"https:\/\/github.com\/dzeban\/cs\/blob\/master\/sorting\/external\/external-merge.c\">\u043f\u0440\u043e\u0441\u0442\u0443\u044e \u043d\u0435\u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u0443\u044e \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044e<\/a>:<\/p>\n<pre><code class=\"bash\">$ LD_PRELOAD=.\/libmemrestrict.so .\/external-merge 4M.bin 1048576 &gt; \/dev\/null 4194304 bytes sorted in 0.383171 seconds <\/code><\/pre>\n<p>  \u041e\u0442\u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u0430\u043b\u0438, \u0438\u043c\u0435\u044f 2 MiB \u043f\u0430\u043c\u044f\u0442\u0438 \u0438 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u044f \u0431\u0443\u0444\u0435\u0440 \u0432 1 MiB.<\/p>\n<p>  \u0422\u0435\u043f\u0435\u0440\u044c \u043e\u0442\u0441\u043e\u0440\u0442\u0438\u0440\u0443\u0435\u043c 500 \u041c\u0431. \u0421\u043d\u0430\u0447\u0430\u043b\u0430 \u043e\u0442\u043a\u043b\u044e\u0447\u0438\u043c \u0441\u0432\u043e\u043f, \u043f\u043e\u0441\u043a\u043e\u043b\u044c\u043a\u0443 \u043c\u044b \u0443\u043f\u0440\u0430\u0432\u043b\u044f\u0435\u043c \u043e\u0431\u043c\u0435\u043d\u043e\u043c \u043a\u0443\u0441\u043a\u043e\u0432 \u0434\u0430\u043d\u043d\u044b\u0445 \u0432\u0440\u0443\u0447\u043d\u0443\u044e.<\/p>\n<pre><code class=\"bash\">$ swapoff \/dev\/vda5 <\/code><\/pre>\n<p>  \u041e\u0431\u043d\u0443\u043b\u0438\u043c \u043a\u044d\u0448\u0438:<\/p>\n<pre><code class=\"bash\">$ echo 3 &gt; \/proc\/sys\/vm\/drop_caches <\/code><\/pre>\n<p>  \u041f\u0440\u043e\u0432\u0435\u0440\u0438\u043c \u0434\u043e\u0441\u0442\u0443\u043f\u043d\u0443\u044e \u043f\u0430\u043c\u044f\u0442\u044c:<\/p>\n<pre><code class=\"bash\">$ free -m              total       used       free     shared    buffers     cached Mem:           119         28         90          0          0          6 -\/+ buffers\/cache:         21         97 Swap:            0          0          0 <\/code><\/pre>\n<p>  \u0411\u0443\u0434\u0435\u043c \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c \u0431\u0443\u0444\u0435\u0440 \u0432 50 \u041c\u0431 \u2013 \u0432 10 \u0440\u0430\u0437 \u043c\u0435\u043d\u044c\u0448\u0435 \u0440\u0430\u0437\u043c\u0435\u0440\u0430 \u0444\u0430\u0439\u043b\u0430.<\/p>\n<pre><code class=\"bash\">$ .\/external-merge 500M.bin 50000000 &gt; \/dev\/null 500000000 bytes sorted in 120.115180 seconds <\/code><\/pre>\n<p>  \u041d\u0438\u0447\u043e\u0441\u0438\u0439, \u0434\u0432\u0435 \u043c\u0438\u043d\u0443\u0442\u044b! \u0421 \u0447\u0435\u0433\u043e \u0431\u044b \u044d\u0442\u043e? \u041a\u043e\u043d\u0435\u0447\u043d\u043e, \u0438\u0437-\u0437\u0430 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0439 I\/O. \u0422\u0440\u0438 \u0432\u0435\u0449\u0438 \u0442\u043e\u0440\u043c\u043e\u0437\u044f\u0442 \u043f\u0440\u043e\u0446\u0435\u0441\u0441. \u041d\u0430 \u0444\u0430\u0437\u0435 \u0440\u0430\u0437\u0434\u0435\u043b\u0435\u043d\u0438\u044f \u0434\u0430\u043d\u043d\u044b\u0445 \u043c\u044b \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e \u0447\u0438\u0442\u0430\u0435\u043c \u0444\u0430\u0439\u043b, \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u044f \u043c\u0430\u043b\u0435\u043d\u044c\u043a\u0438\u0439 \u0431\u0443\u0444\u0435\u0440. \u041d\u0430 \u0444\u0430\u0437\u0435 \u0441\u043b\u0438\u044f\u043d\u0438\u044f \u043c\u044b \u043e\u0442\u043a\u0440\u044b\u0432\u0430\u0435\u043c \u0438 \u0437\u0430\u043a\u0440\u044b\u0432\u0430\u0435\u043c \u0444\u0430\u0439\u043b\u044b \u0441 \u043a\u0443\u0441\u043a\u0430\u043c\u0438 \u0438\u043d\u0444\u043e\u0440\u043c\u0430\u0446\u0438\u0438. \u0410 \u0435\u0449\u0451 \u0435\u0441\u0442\u044c \u0438 \u0432\u044b\u0432\u043e\u0434 \u2013 \u043d\u0430 \u0444\u0430\u0437\u0435 \u0441\u043b\u0438\u044f\u043d\u0438\u044f \u043c\u044b \u0432\u044b\u0432\u043e\u0434\u0438\u043c 50 \u041c\u0431 \u0434\u0430\u043d\u043d\u044b\u0445 \u043d\u0430 stdout, \u0447\u0442\u043e, \u043d\u0435\u0441\u043c\u043e\u0442\u0440\u044f \u043d\u0430 \u043f\u0435\u0440\u0435\u043d\u0430\u043f\u0440\u0430\u0432\u043b\u0435\u043d\u0438\u0435 \u0432 \/dev\/null, \u0434\u0430\u0451\u0442 \u043d\u0430\u0433\u0440\u0443\u0437\u043e\u0447\u043a\u0443. \u0415\u0441\u043b\u0438 \u044d\u0442\u043e \u043e\u0442\u043a\u043b\u044e\u0447\u0438\u0442\u044c, \u043c\u044b \u043f\u043e\u043b\u0443\u0447\u0430\u0435\u043c \u043f\u0440\u0438\u0440\u043e\u0441\u0442 \u0431\u044b\u0441\u0442\u0440\u043e\u0434\u0435\u0439\u0441\u0442\u0432\u0438\u044f \u043d\u0430 25%.<\/p>\n<pre><code class=\"bash\">$ .\/external-merge-no-output 500M.bin 50000000 &gt; \/dev\/null 500000000 bytes sorted in 87.140000 seconds <\/code><\/pre>\n<p>  \u0418\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u0435 \u043f\u0430\u043c\u044f\u0442\u0438 \u043c\u0435\u043d\u044f \u0443\u0441\u0442\u0440\u0430\u0438\u0432\u0430\u0435\u0442. \u0415\u0441\u043b\u0438 \u0437\u0430\u043f\u0443\u0441\u0442\u0438\u0442\u044c \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0443 \u0447\u0435\u0440\u0435\u0437 massif, \u043c\u043e\u0436\u043d\u043e \u0443\u0432\u0438\u0434\u0435\u0442\u044c, \u0447\u0442\u043e \u043f\u0438\u043a \u043f\u043e\u0442\u0440\u0435\u0431\u043b\u0435\u043d\u0438\u044f \u2013 \u044d\u0442\u043e \u0440\u0430\u0437\u043c\u0435\u0440 \u0431\u0443\u0444\u0435\u0440\u0430 \u0438 \u043d\u0435\u0431\u043e\u043b\u044c\u0448\u0430\u044f \u043a\u0443\u0447\u0430.<\/p>\n<pre><code class=\"bash\">-------------------------------------------------------------------------------- Command:            .\/external-merge 500M.bin 50000000 Massif arguments:   (none) ms_print arguments: massif.out.17423 --------------------------------------------------------------------------------       MB 47.75^                                                                  :::::       |#::::::@:::::::::::@:::::::::@:::@::::@::::@::::::::@::::@::::@:::@           |# : :  @ :  : :  : @  : :    @   @    @    @   :    @    @    @   @           |# : :  @ :  : :  : @  : :    @   @    @    @   :    @    @    @   @           |# : :  @ :  : :  : @  : :    @   @    @    @   :    @    @    @   @           |# : :  @ :  : :  : @  : :    @   @    @    @   :    @    @    @   @           |# : :  @ :  : :  : @  : :    @   @    @    @   :    @    @    @   @           |# : :  @ :  : :  : @  : :    @   @    @    @   :    @    @    @   @           |# : :  @ :  : :  : @  : :    @   @    @    @   :    @    @    @   @           |# : :  @ :  : :  : @  : :    @   @    @    @   :    @    @    @   @           |# : :  @ :  : :  : @  : :    @   @    @    @   :    @    @    @   @           |# : :  @ :  : :  : @  : :    @   @    @    @   :    @    @    @   @           |# : :  @ :  : :  : @  : :    @   @    @    @   :    @    @    @   @           |# : :  @ :  : :  : @  : :    @   @    @    @   :    @    @    @   @           |# : :  @ :  : :  : @  : :    @   @    @    @   :    @    @    @   @           |# : :  @ :  : :  : @  : :    @   @    @    @   :    @    @    @   @           |# : :  @ :  : :  : @  : :    @   @    @    @   :    @    @    @   @           |# : :  @ :  : :  : @  : :    @   @    @    @   :    @    @    @   @           |# : :  @ :  : :  : @  : :    @   @    @    @   :    @    @    @   @           |# : :  @ :  : :  : @  : :    @   @    @    @   :    @    @    @   @         0 +-----------------------------------------------------------------------&gt;Gi      0                                                                   332.5  Number of snapshots: 98  Detailed snapshots: [4 (peak), 10, 20, 29, 32, 35, 38, 45, 48, 54, 64, 74, 84, 94]  --------------------------------------------------------------------------------   n        time(i)         total(B)   useful-heap(B) extra-heap(B)    stacks(B) --------------------------------------------------------------------------------   0              0                0                0             0            0   1        119,690              584              568            16            0   2        123,141       50,004,496       50,000,568         3,928            0   3      4,814,014       50,005,080       50,001,136         3,944            0   4      4,817,234       50,005,080       50,001,136         3,944            0 99.99% (50,001,136B) (heap allocation functions) malloc\/new\/new[], --alloc-fns, etc. -&gt;99.99% (50,000,000B) 0x400FA2: external_merge_sort (in \/root\/external-merge) | -&gt;99.99% (50,000,000B) 0x40128E: main (in \/root\/external-merge) |    -&gt;00.00% (1,136B) in 1+ places, all below ms_print's threshold (01.00%) <\/code><\/pre>\n<p>  \u041c\u043e\u0436\u043d\u043e \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0438\u0442\u044c \u043f\u0430\u043c\u044f\u0442\u044c \u0438 50 \u041c\u0431, \u043f\u043b\u044e\u0441 \u0435\u0449\u0451 500 KB \u043d\u0430 \u0432\u0440\u0435\u043c\u0435\u043d\u043d\u044b\u0435 \u0441\u0442\u0440\u043e\u043a\u0438, \u0441\u043e\u0434\u0435\u0440\u0436\u0430\u0449\u0438\u0435 \u043f\u0443\u0442\u0438 \u043a \u0444\u0430\u0439\u043b\u0430\u043c:<\/p>\n<pre><code class=\"bash\">$ LD_PRELOAD=.\/libmemrestrict.so MR_THRESHOLD=51000000 .\/external-merge 500M.bin 50000000 &gt; \/dev\/null 500000000 bytes sorted in 87.900000 seconds <\/code><\/pre>\n<p>  \u0412 \u043e\u0431\u0449\u0435\u043c, \u0441 \u043f\u0430\u043c\u044f\u0442\u044c\u044e \u2013 \u043e\u043a, \u0441 \u0431\u044b\u0441\u0442\u0440\u043e\u0434\u0435\u0439\u0441\u0442\u0432\u0438\u0435\u043c \u2013 \u043d\u0435 \u043e\u043a. mmap \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u043b\u0430 \u0441\u0434\u0435\u043b\u0430\u0442\u044c \u044d\u0442\u0443 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u044e \u0437\u0430 32 \u0441\u0435\u043a\u0443\u043d\u0434\u044b. \u0414\u0430\u0432\u0430\u0439\u0442\u0435 \u0443\u043b\u0443\u0447\u0448\u0430\u0442\u044c \u043d\u0430\u0448 \u0441\u043f\u043e\u0441\u043e\u0431.<\/p>\n<p>  \u041f\u0440\u043e\u0432\u0435\u0434\u0451\u043c \u043f\u0440\u043e\u0444\u0438\u043b\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u0435 \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u044b \u043f\u0440\u0438 \u043f\u043e\u043c\u043e\u0449\u0438 gprof. \u0421\u043e\u0437\u0434\u0430\u0434\u0438\u043c \u0431\u0438\u043d\u0430\u0440\u043d\u0438\u043a<\/p>\n<pre><code class=\"bash\">$ gcc -pg -g -Wall -Wextra external-merge.c -o external-merge-gprof <\/code><\/pre>\n<p>  \u0418 \u0432\u044b\u0437\u043e\u0432\u0435\u043c \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0443 \u043c\u043d\u043e\u0433\u043e\u043a\u0440\u0430\u0442\u043d\u043e \u0434\u043b\u044f \u043d\u0430\u043a\u043e\u043f\u043b\u0435\u043d\u0438\u044f \u0441\u0442\u0430\u0442\u0438\u0441\u0442\u0438\u043a\u0438 \u043f\u0440\u0438 \u043f\u043e\u043c\u043e\u0449\u0438 \u043c\u043e\u0435\u0433\u043e \u0443\u0434\u043e\u0431\u0441\u0442\u0432\u0435\u043d\u043d\u043e\u0433\u043e \u0441\u043a\u0440\u0438\u043f\u0442\u0430 \u0438\u0437 \u0441\u0442\u0430\u0442\u044c\u0438 \u043f\u043e gprof. \u0412\u043e\u0442 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442:<\/p>\n<pre><code class=\"bash\">%   cumulative   self              self     total            time   seconds   seconds    calls  Ts\/call  Ts\/call  name     81.98    432.87   432.87                             compar 18.17    528.82    95.95                             print_arr 0.00    528.82     0.00     1100     0.00     0.00  form_filename 0.00    528.82     0.00      100     0.00     0.00  merge 0.00    528.82     0.00      100     0.00     0.00  save_buf 0.00    528.82     0.00       10     0.00     0.00  external_merge_sort 0.00    528.82     0.00       10     0.00     0.00  split <\/code><\/pre>\n<p>  \u0411\u043e\u043b\u044c\u0448\u0430\u044f \u0447\u0430\u0441\u0442\u044c \u0432\u0440\u0435\u043c\u0435\u043d\u0438 \u0443\u0448\u043b\u0430 \u043d\u0430 \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0443 \u0438 \u0432\u044b\u0432\u043e\u0434. \u041d\u043e \u043d\u0435 \u0437\u0430\u0431\u0443\u0434\u044c\u0442\u0435, \u0447\u0442\u043e gprof \u043d\u0435 \u043f\u043e\u043a\u0430\u0437\u044b\u0432\u0430\u0435\u0442 \u0432\u0440\u0435\u043c\u044f, \u0443\u0448\u0435\u0434\u0448\u0435\u0435 \u043d\u0430 \u0441\u0438\u0441\u0442\u0435\u043c\u043d\u044b\u0435 \u0432\u044b\u0437\u043e\u0432\u044b \u0438 I\/O.<\/p>\n<p>  \u0427\u0442\u043e \u0442\u0443\u0442 \u043c\u043e\u0436\u043d\u043e \u0443\u043b\u0443\u0447\u0448\u0438\u0442\u044c?  <\/p>\n<ul>\n<li>\u0434\u043e\u0431\u0430\u0432\u0438\u0442\u044c \u0432\u043e \u0432\u043d\u0435\u0448\u043d\u044e\u044e \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0443 \u043c\u043d\u043e\u0433\u043e\u043f\u043e\u0442\u043e\u0447\u043d\u043e\u0441\u0442\u044c \u0438 \u0442\u0440\u044e\u043a\u0438 \u0441 I\/O<\/li>\n<li>\u0432\u0437\u044f\u0442\u044c \u0434\u0440\u0443\u0433\u043e\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0438<\/li>\n<\/ul>\n<p>  \u0423\u043d\u0438\u0432\u0435\u0440\u0441\u0430\u043b\u044c\u043d\u0430\u044f \u0432\u043d\u0435\u0448\u043d\u044f\u044f \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0430 \u0441\u043e \u0441\u043b\u0438\u044f\u043d\u0438\u0435\u043c \u2013 \u044d\u0442\u043e \u043f\u0440\u043e\u0441\u0442\u0430\u044f \u0438\u0434\u0435\u044f \u0434\u043b\u044f \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0438 \u0431\u043e\u043b\u044c\u0448\u0438\u0445 \u0434\u0430\u043d\u043d\u044b\u0445 \u043f\u0440\u0438 \u043c\u0430\u043b\u043e\u043c \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u0435 \u043f\u0430\u043c\u044f\u0442\u0438, \u043d\u043e \u0431\u0435\u0437 \u043a\u0430\u043a\u0438\u0445-\u043b\u0438\u0431\u043e \u0443\u043b\u0443\u0447\u0448\u0435\u043d\u0438\u0439 \u043e\u043d\u0430 \u0440\u0430\u0431\u043e\u0442\u0430\u0435\u0442 \u043c\u0435\u0434\u043b\u0435\u043d\u043d\u043e.<\/p>\n<h4>\u041d\u0430\u0441\u0442\u0440\u0430\u0438\u0432\u0430\u0435\u043c \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0443<\/h4>\n<p>  \u041c\u043e\u0436\u043d\u043e, \u043a\u043e\u043d\u0435\u0447\u043d\u043e, \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c \u043c\u043d\u043e\u0433\u043e\u043f\u043e\u0442\u043e\u0447\u043d\u043e\u0441\u0442\u044c \u0434\u043b\u044f \u0440\u0430\u0437\u0434\u0435\u043b\u0435\u043d\u0438\u044f \u0438 \u0441\u043b\u0438\u044f\u043d\u0438\u044f \u2013 \u043d\u043e \u044d\u0442\u043e \u043f\u043b\u043e\u0445\u0430\u044f \u0438\u0434\u0435\u044f. \u0418\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u0435 \u0435\u0433\u043e \u043d\u0430 \u0444\u0430\u0437\u0435 \u0440\u0430\u0437\u0434\u0435\u043b\u0435\u043d\u0438\u044f \u0441\u043c\u044b\u0441\u043b\u0430 \u043d\u0435 \u0438\u043c\u0435\u0435\u0442, \u043f\u043e\u0442\u043e\u043c\u0443 \u0447\u0442\u043e \u0434\u0430\u043d\u043d\u044b\u0435 \u0441\u043e\u0434\u0435\u0440\u0436\u0430\u0442\u0441\u044f \u0432 \u043e\u0434\u043d\u043e\u043c \u0431\u0443\u0444\u0435\u0440\u0435. \u041c\u043e\u0436\u043d\u043e \u043f\u043e\u043f\u044b\u0442\u0430\u0442\u044c\u0441\u044f \u043f\u043e\u0432\u043b\u0438\u044f\u0442\u044c \u043d\u0430 \u0442\u043e, \u043a\u0430\u043a \u044f\u0434\u0440\u043e \u0447\u0438\u0442\u0430\u0435\u0442 \u0434\u0430\u043d\u043d\u044b\u0435. \u0414\u043b\u044f \u044d\u0442\u043e\u0433\u043e \u0435\u0441\u0442\u044c \u0434\u0432\u0435 \u0444\u0443\u043d\u043a\u0446\u0438\u0438:  <\/p>\n<ul>\n<li> readahead (\u0442\u043e\u043b\u044c\u043a\u043e \u0432 Linux).<\/li>\n<li> posix_fadvise \u0441 POSIX_FADV_SEQUENTIAL.<\/li>\n<\/ul>\n<p>  \u041e\u043d\u0438 \u0441\u043e\u043e\u0431\u0449\u0430\u044e\u0442 \u043f\u043e\u0434\u0441\u0438\u0441\u0442\u0435\u043c\u0435 \u0443\u043f\u0440\u0430\u0432\u043b\u0435\u043d\u0438\u044f \u043f\u0430\u043c\u044f\u0442\u044c\u044e \u043e \u0442\u043e\u043c, \u043a\u0430\u043a \u043c\u044b \u0431\u0443\u0434\u0435\u043c \u0447\u0438\u0442\u0430\u0442\u044c \u0434\u0430\u043d\u043d\u044b\u0435. \u0412 \u043d\u0430\u0448\u0435\u043c \u0441\u043b\u0443\u0447\u0430\u0435 \u0447\u0442\u0435\u043d\u0438\u0435 \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e, \u043f\u043e\u044d\u0442\u043e\u043c\u0443 \u0431\u044b\u043b\u043e \u0431\u044b \u043d\u0435\u043f\u043b\u043e\u0445\u043e \u0443\u0432\u0438\u0434\u0435\u0442\u044c \u0441\u043e\u0434\u0435\u0440\u0436\u0438\u043c\u043e\u0435 \u0444\u0430\u0439\u043b\u0430 \u0432 \u043a\u044d\u0448\u0435 \u0441\u0442\u0440\u0430\u043d\u0438\u0446.<\/p>\n<p>  \u041d\u0430 \u0444\u0430\u0437\u0435 \u0441\u043b\u0438\u044f\u043d\u0438\u044f \u043c\u044b \u043c\u043e\u0436\u0435\u043c \u043d\u0435 \u0434\u0435\u043b\u0430\u0442\u044c \u043f\u043e\u0441\u0442\u043e\u044f\u043d\u043d\u044b\u0435 \u043e\u0442\u043a\u0440\u044b\u0442\u0438\u044f \u0438 \u0437\u0430\u043a\u0440\u044b\u0442\u0438\u044f \u0444\u0430\u0439\u043b\u043e\u0432, \u0430 \u0441\u043e\u0437\u0434\u0430\u0442\u044c \u0432\u044b\u0434\u0435\u043b\u0435\u043d\u043d\u044b\u0435 \u043f\u043e\u0442\u043e\u043a\u0438 \u0434\u043b\u044f \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u0438\u0437 \u0444\u0430\u0439\u043b\u043e\u0432. \u041a\u0430\u0436\u0434\u044b\u0439 \u043f\u043e\u0442\u043e\u043a \u0431\u0443\u0434\u0435\u0442 \u0434\u0435\u0440\u0436\u0430\u0442\u044c \u043e\u0442\u043a\u0440\u044b\u0442\u044b\u043c \u0441\u0432\u043e\u0439 \u0444\u0430\u0439\u043b\u0438\u043a, \u0430 \u043c\u044b \u0431\u0443\u0434\u0435\u043c \u0437\u0430\u043f\u043e\u043b\u043d\u044f\u0442\u044c \u0434\u043b\u044f \u043d\u0435\u0433\u043e \u0431\u0443\u0444\u0435\u0440. \u041a\u043e\u0433\u0434\u0430 \u043e\u043d \u0437\u0430\u043f\u043e\u043b\u043d\u044f\u0435\u0442\u0441\u044f, \u043e\u043d \u0441\u043e\u0440\u0442\u0438\u0440\u0443\u0435\u0442\u0441\u044f \u0438 \u0432\u044b\u0432\u043e\u0434\u0438\u0442\u0441\u044f. \u0418 \u0435\u0449\u0451 \u0434\u043b\u044f \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u043f\u043e\u0442\u043e\u043a\u0430 \u0431\u0443\u0434\u0435\u0442 \u0440\u0430\u0431\u043e\u0442\u0430\u0442\u044c readahead.<\/p>\n<p>  \u0412\u043e\u0442 \u0443\u0441\u043e\u0432\u0435\u0440\u0448\u0435\u043d\u0441\u0442\u0432\u043e\u0432\u0430\u043d\u043d\u0430\u044f \u043c\u043d\u043e\u0433\u043e\u043f\u043e\u0442\u043e\u0447\u043d\u0430\u044f \u0432\u0435\u0440\u0441\u0438\u044f \u0432\u043d\u0435\u0448\u043d\u0435\u0439 \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0438 \u0441\u043e \u0441\u043b\u0438\u044f\u043d\u0438\u0435\u043c. \u041d\u0443, \u043a\u0430\u043a \u044f \u0438 \u0441\u043a\u0430\u0437\u0430\u043b, \u043c\u043d\u043e\u0433\u043e\u043f\u043e\u0442\u043e\u0447\u043d\u043e\u0441\u0442\u044c \u2013 \u043d\u0435 \u043e\u0447\u0435\u043d\u044c \u0445\u043e\u0440\u043e\u0448\u0430\u044f \u0438\u0434\u0435\u044f. \u041d\u0430 \u043e\u0434\u043d\u043e\u044f\u0434\u0435\u0440\u043d\u043e\u043c \u043f\u0440\u043e\u0446\u0435 \u0440\u0430\u0437\u043d\u0438\u0446\u044b \u043d\u0438\u043a\u0430\u043a\u043e\u0439 \u043d\u0435\u0442.<\/p>\n<pre><code class=\"bash\">$ .\/mt-ext-merge 500M.bin 50000000 &gt; \/dev\/null 500000000 bytes sorted in 117.380000 seconds <\/code><\/pre>\n<p>  \u042d\u0442\u043e \u0441 \u0432\u044b\u0432\u043e\u0434\u043e\u043c \u0434\u0430\u043d\u043d\u044b\u0445. \u0410 \u0431\u0435\u0437 \u0432\u044b\u0432\u043e\u0434\u0430:<\/p>\n<pre><code class=\"bash\">$ .\/mt-ext-merge-no-output 500M.bin 50000000 &gt; \/dev\/null 500000000 bytes sorted in 91.040000 seconds <\/code><\/pre>\n<p>  \u041d\u0443 \u043b\u0430\u0434\u043d\u043e, \u0434\u0430\u0432\u0430\u0439\u0442\u0435 \u043f\u043e\u043f\u0440\u043e\u0431\u0443\u0435\u043c \u043d\u0430 \u0447\u0435\u0442\u044b\u0440\u0451\u0445\u044a\u044f\u0434\u0435\u0440\u043d\u043e\u0439 \u043c\u0430\u0448\u0438\u043d\u0435 (Intel Core i7-3612QM CPU @ 2.10GHz):<\/p>\n<pre><code class=\"bash\">$ .\/naive 500M.bin &gt; \/dev\/null  500000000 bytes sorted in 23.040499 seconds  $ .\/mmaped 500M.bin &gt; \/dev\/null 500000000 bytes sorted in 23.542076 seconds  $ .\/external-merge 500M.bin 50000000 &gt; \/dev\/null  500000000 bytes sorted in 39.228695 seconds  $ .\/mt-external-merge 500M.bin 50000000 &gt; \/dev\/null  500000000 bytes sorted in 41.062793 seconds  $ .\/external-merge-no-output 500M.bin 50000000 &gt; \/dev\/null 500000000 bytes sorted in 28.893745 seconds  $ .\/mt-external-merge-no-output 500M.bin 50000000 &gt; \/dev\/null 500000000 bytes sorted in 28.368976 seconds  \u0422\u0435\u043f\u0435\u0440\u044c \u0434\u043b\u044f \u0441\u0442\u0430 \u043a\u0443\u0441\u043e\u0447\u043a\u043e\u0432 \u0438 \u0441\u0442\u0430 \u043f\u043e\u0442\u043e\u043a\u043e\u0432:  $ .\/external-merge-no-output 500M.bin 5000000 &gt; \/dev\/null 500000000 bytes sorted in 27.107728 seconds  $ .\/mt-external-merge-no-output 500M.bin 5000000 &gt; \/dev\/null 500000000 bytes sorted in 28.558468 seconds <\/code><\/pre>\n<p>  \u0420\u0430\u0437\u043d\u0438\u0446\u044b \u043c\u0435\u0436\u0434\u0443 external-merge \u0438 mt-external-merge \u043d\u0435\u0442. \u0421 \u0447\u0435\u0433\u043e \u044d\u0442\u043e? \u0414\u0430 \u043f\u043e\u0442\u043e\u043c\u0443, \u0447\u0442\u043e \u043c\u043d\u043e\u0433\u043e\u043f\u043e\u0442\u043e\u0447\u043d\u043e\u0441\u0442\u044c \u043d\u0435 \u0440\u0435\u0448\u0430\u0435\u0442 \u043f\u0440\u043e\u0431\u043b\u0435\u043c\u044b \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u0439 \u0432\u0432\u043e\u0434\u0430 \u0438 \u0432\u044b\u0432\u043e\u0434\u0430. \u041e\u043d\u0430 \u0445\u043e\u0440\u043e\u0448\u043e \u043f\u043e\u0434\u043e\u0439\u0434\u0451\u0442 \u0434\u043b\u044f \u0442\u0435\u0445 \u0441\u043b\u0443\u0447\u0430\u0435\u0432, \u043a\u043e\u0433\u0434\u0430:  <\/p>\n<ul>\n<li>\u0438\u0441\u043f\u043e\u043b\u043d\u0435\u043d\u0438\u0435 \u043f\u043e\u0442\u043e\u043a\u043e\u0432 \u043d\u0435\u0437\u0430\u0432\u0438\u0441\u0438\u043c\u043e<\/li>\n<li>\u0440\u0435\u0441\u0443\u0440\u0441\u044b \u0432\u0432\u043e\u0434\u0430 \u0438 \u0432\u044b\u0432\u043e\u0434\u0430 \u043c\u043e\u0433\u0443\u0442 \u0440\u0430\u0431\u043e\u0442\u0430\u0442\u044c \u043f\u0430\u0440\u0430\u043b\u043b\u0435\u043b\u044c\u043d\u043e \u2013 \u043d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u043a\u0430\u043a RAID<\/li>\n<\/ul>\n<p>  \u0423 \u043d\u0430\u0441 \u043f\u043e\u0442\u043e\u043a\u0438 \u0432\u0437\u0430\u0438\u043c\u043e\u0437\u0430\u0432\u0438\u0441\u0438\u043c\u044b \u2013 \u0433\u043b\u0430\u0432\u043d\u043e\u043c\u0443 \u043f\u043e\u0442\u043e\u043a\u0443 \u043f\u0440\u0438\u0445\u043e\u0434\u0438\u0442\u0441\u044f \u0436\u0434\u0430\u0442\u044c \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0438 \u0431\u0443\u0444\u0435\u0440\u0430, \u0430 \u0443\u0436\u0435 \u043f\u043e\u0442\u043e\u043c \u043d\u0430\u0447\u0438\u043d\u0430\u0442\u044c \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0435\u0435 \u0447\u0442\u0435\u043d\u0438\u0435 \u0438\u0437 \u0444\u0430\u0439\u043b\u0430. \u0418 \u0447\u0442\u0435\u043d\u0438\u0435 \u0434\u043b\u044f \u0440\u0430\u0437\u0434\u0435\u043b\u0435\u043d\u0438\u044f \u0438\u0434\u0451\u0442 \u0431\u044b\u0441\u0442\u0440\u0435\u0435, \u0447\u0435\u043c \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0430 \u0431\u0443\u0444\u0435\u0440\u0430, \u043f\u043e\u044d\u0442\u043e\u043c\u0443 \u0431\u043e\u043b\u044c\u0448\u0443\u044e \u0447\u0430\u0441\u0442\u044c \u0432\u0440\u0435\u043c\u0435\u043d\u0438 \u043f\u043e\u0442\u043e\u043a\u0438 \u0436\u0434\u0443\u0442, \u043f\u043e\u043a\u0430 \u043e\u0441\u043d\u043e\u0432\u043d\u043e\u0439 \u043f\u043e\u0442\u043e\u043a \u0437\u0430\u043a\u043e\u043d\u0447\u0438\u0442 \u0440\u0430\u0431\u043e\u0442\u0443.<\/p>\n<p>  \u041d\u0443\u0436\u043d\u044b \u0434\u0440\u0443\u0433\u0438\u0435 \u0441\u043f\u043e\u0441\u043e\u0431\u044b \u0443\u043b\u0443\u0447\u0448\u0435\u043d\u0438\u044f \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430.<\/p>\n<h4>\u041e\u0441\u043e\u0431\u044b\u0435 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u044b \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0438<\/h4>\n<p>  \u041f\u043e\u043f\u0440\u043e\u0431\u0443\u0435\u043c \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c \u0447\u0442\u043e-\u0442\u043e \u043e\u0442\u043b\u0438\u0447\u043d\u043e\u0435 \u043e\u0442 QuickSort. \u0420\u0430\u0437 \u0443\u0436 \u043c\u044b \u0437\u043d\u0430\u0435\u043c, \u0447\u0442\u043e \u0441\u043e\u0440\u0442\u0438\u0440\u0443\u0435\u043c \u0446\u0435\u043b\u044b\u0435 \u0447\u0438\u0441\u043b\u0430, \u043d\u0430\u0434\u043e \u044d\u0442\u043e \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c. \u0415\u0441\u0442\u044c \u043e\u0441\u043e\u0431\u044b\u0435 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u044b, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u044e\u0442\u0441\u044f \u0434\u043b\u044f \u043a\u043e\u043d\u043a\u0440\u0435\u0442\u043d\u044b\u0445 \u0442\u0438\u043f\u043e\u0432 \u0434\u0430\u043d\u043d\u044b\u0445, \u0438 \u0438\u0445 \u043c\u043e\u0436\u043d\u043e \u0440\u0430\u0437\u0434\u0435\u043b\u0438\u0442\u044c \u043d\u0430 \u0434\u0432\u0435 \u0433\u0440\u0443\u043f\u043f\u044b:  <\/p>\n<ul>\n<li>\u043d\u0435 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u044e\u0442 \u0441\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u044f<\/li>\n<li>\u043d\u0435 \u0442\u0440\u0435\u0431\u0443\u044e\u0442 \u0437\u0430\u0433\u0440\u0443\u0437\u043a\u0438 \u0432\u0441\u0435\u0433\u043e \u043c\u0430\u0441\u0441\u0438\u0432\u0430 \u0432 \u043f\u0430\u043c\u044f\u0442\u044c<\/li>\n<\/ul>\n<p>  \u041e\u043d\u0438 \u0440\u0430\u0431\u043e\u0442\u0430\u044e\u0442 \u043b\u0443\u0447\u0448\u0435, \u0447\u0435\u043c O(n log(n)) \u2013 \u043d\u0438\u0436\u043d\u044f\u044f \u0433\u0440\u0430\u043d\u0438\u0446\u0430 \u0434\u043b\u044f \u0441\u0440\u0430\u0432\u043d\u0438\u0432\u0430\u044e\u0449\u0438\u0445 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u043e\u0432 \u0432\u0440\u043e\u0434\u0435 QuickSort. \u041d\u043e \u043d\u0435 \u0432\u0441\u0435 \u043e\u043d\u0438 \u043f\u043e\u0434\u043e\u0439\u0434\u0443\u0442 \u0432 \u0441\u043b\u0443\u0447\u0430\u0435 \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u044f \u043f\u0430\u043c\u044f\u0442\u0438. \u041f\u043e\u044d\u0442\u043e\u043c\u0443 \u044f \u043e\u0441\u0442\u0430\u043d\u043e\u0432\u0438\u043b\u0441\u044f \u043d\u0430 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u0438 \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0438 \u043f\u043e\u0434\u0441\u0447\u0451\u0442\u043e\u043c<\/p>\n<h4>\u0421\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0430 \u043f\u043e\u0434\u0441\u0447\u0451\u0442\u043e\u043c<\/h4>\n<p>  \u0415\u0441\u043b\u0438 \u0443 \u043d\u0430\u0441 \u043c\u043d\u043e\u0433\u043e \u0434\u0430\u043d\u043d\u044b\u0445 \u0441 \u043c\u0430\u043b\u044b\u043c \u0440\u0430\u0437\u0431\u0440\u043e\u0441\u043e\u043c, \u043c\u043e\u0436\u043d\u043e \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0443 \u043f\u043e\u0434\u0441\u0447\u0451\u0442\u043e\u043c. \u0418\u0434\u0435\u044f \u043f\u0440\u043e\u0441\u0442\u0430 \u2013 \u043c\u044b \u0431\u0443\u0434\u0435\u043c \u0445\u0440\u0430\u043d\u0438\u0442\u044c \u0432 \u043f\u0430\u043c\u044f\u0442\u0438 \u043d\u0435 \u0434\u0430\u043d\u043d\u044b\u0435, \u0430 \u043c\u0430\u0441\u0441\u0438\u0432 \u0441\u0447\u0451\u0442\u0447\u0438\u043a\u043e\u0432. \u041c\u044b \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e \u0447\u0438\u0442\u0430\u0435\u043c \u0434\u0430\u043d\u043d\u044b\u0435 \u0438 \u0443\u0432\u0435\u043b\u0438\u0447\u0438\u0432\u0430\u0435\u043c \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0443\u044e\u0449\u0438\u0435 \u0441\u0447\u0451\u0442\u0447\u0438\u043a\u0438. \u0421\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 \u043f\u043e \u0432\u0440\u0435\u043c\u0435\u043d\u0438 \u043b\u0438\u043d\u0435\u0439\u043d\u0430, \u0430 \u043f\u043e \u043e\u0431\u044a\u0451\u043c\u0443 \u2013 \u043f\u0440\u043e\u043f\u043e\u0440\u0446\u0438\u043e\u043d\u0430\u043b\u044c\u043d\u0430 \u0434\u0438\u0430\u043f\u0430\u0437\u043e\u043d\u0443 \u0434\u0430\u043d\u043d\u044b\u0445.<\/p>\n<p>  \u041f\u0440\u043e\u0441\u0442\u0430\u044f \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f \u0440\u0430\u0431\u043e\u0442\u0430\u0435\u0442 \u0441 \u043c\u0430\u0441\u0441\u0438\u0432\u043e\u043c \u043e\u0442 0 \u0434\u043e N. \u0426\u0435\u043b\u044b\u0435 \u0447\u0438\u0441\u043b\u0430 \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0443\u044e\u0442 \u0438\u043d\u0434\u0435\u043a\u0441\u0430\u043c \u043c\u0430\u0441\u0441\u0438\u0432\u0430. <a href=\"https:\/\/github.com\/dzeban\/cs\/blob\/master\/sorting\/counting-array.c\">\u0412\u043e\u0442 \u043c\u043e\u0439 \u0432\u0430\u0440\u0438\u0430\u043d\u0442<\/a>, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u043d\u0435\u043f\u043b\u043e\u0445\u043e \u0440\u0430\u0431\u043e\u0442\u0430\u0435\u0442 \u0438 \u0431\u0435\u0437 \u0432\u0441\u044f\u043a\u043e\u0433\u043e \u0442\u044e\u043d\u0438\u043d\u0433\u0430. \u0412\u0442\u043e\u0440\u043e\u0439 \u0430\u0440\u0433\u0443\u043c\u0435\u043d\u0442 \u2013 \u0440\u0430\u0437\u043c\u0435\u0440 \u0431\u0443\u0444\u0435\u0440\u0430 \u0432 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430\u0445. \u0411\u0443\u0444\u0435\u0440\u0438\u0437\u0430\u0446\u0438\u044f \u0441\u0438\u043b\u044c\u043d\u043e \u0443\u0441\u043a\u043e\u0440\u044f\u0435\u0442 \u0440\u0430\u0431\u043e\u0442\u0443, \u043f\u043e\u0441\u043a\u043e\u043b\u044c\u043a\u0443 \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0430 \u0447\u0438\u0442\u0430\u0435\u0442 \u0438\u0437 \u0444\u0430\u0439\u043b\u0430 \u043d\u0435 \u043f\u043e 4 \u0431\u0430\u0439\u0442\u0430.<\/p>\n<pre><code class=\"bash\">$ .\/counting-array 500M-range.bin 1000000 &gt; \/dev\/null Range is 1000000 500000000 bytes sorted in 3.240000 seconds <\/code><\/pre>\n<p>  \u0423\u0433\u0443\u043c\u0441. \u041f\u043e\u043b\u0433\u0438\u0433\u0430 \u0434\u0430\u043d\u043d\u044b\u0445 \u043e\u0442\u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u043e \u0437\u0430 3 \u0441 \u043f\u043e\u043b\u043e\u0432\u0438\u043d\u043e\u0439 \u0441\u0435\u043a\u0443\u043d\u0434\u044b \u043d\u0430 128 MiB \u043f\u0430\u043c\u044f\u0442\u0438 \u0438 \u043e\u0434\u043d\u043e\u043c CPU. \u0421\u0440\u0430\u0432\u043d\u0438\u043c \u0441 qsort \u0438\u043b\u0438 mmap:<\/p>\n<pre><code class=\"bash\">$ .\/mmaped 500M-range.bin &gt; \/dev\/null 500000000 bytes sorted in 76.150000 seconds <\/code><\/pre>\n<p>  \u0412 23 \u0440\u0430\u0437\u0430 \u0431\u044b\u0441\u0442\u0440\u0435\u0435!<\/p>\n<p>  \u041d\u043e \u043d\u0435 \u0437\u0430\u0431\u044b\u0432\u0430\u0439\u0442\u0435 \u043e\u0431 \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u044f\u0445 \u2013 \u0442\u043e\u043b\u044c\u043a\u043e \u0446\u0435\u043b\u044b\u0435 \u0447\u0438\u0441\u043b\u0430 (\u0438\u043b\u0438 \u0438\u0445 \u044d\u043a\u0432\u0438\u0432\u0430\u043b\u0435\u043d\u0442), \u0438 \u043d\u0435\u0431\u043e\u043b\u044c\u0448\u043e\u0439 \u0438\u0445 \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u044b\u0439 \u043f\u0440\u043e\u043c\u0435\u0436\u0443\u0442\u043e\u043a. \u042f \u043f\u044b\u0442\u0430\u043b\u0441\u044f \u0434\u0435\u043b\u0430\u0442\u044c <a href=\"https:\/\/github.com\/dzeban\/cs\/blob\/master\/sorting\/counting.c\">\u0432\u0430\u0440\u0438\u0430\u043d\u0442 \u0441 \u043d\u0435\u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u044b\u043c\u0438 \u043f\u0440\u043e\u043c\u0435\u0436\u0443\u0442\u043a\u0430\u043c\u0438 <\/a>\u0447\u0435\u0440\u0435\u0437 \u0445\u044d\u0448\u0438 \u0438 \u0431\u0438\u043d\u0430\u0440\u043d\u044b\u0439 \u043f\u043e\u0438\u0441\u043a \u2013 \u043d\u043e \u0431\u044b\u0441\u0442\u0440\u043e\u0434\u0435\u0439\u0441\u0442\u0432\u0438\u0435 \u0443 \u043d\u0435\u0433\u043e \u043e\u0447\u0435\u043d\u044c \u043f\u043b\u043e\u0445\u043e\u0435.<\/p>\n<p>  \u0410 \u0435\u0441\u043b\u0438 \u043c\u044b \u043f\u0440\u0435\u0434\u043f\u043e\u043b\u043e\u0436\u0438\u043c \u0443\u043d\u0438\u043a\u0430\u043b\u044c\u043d\u043e\u0441\u0442\u044c \u043d\u0430\u0448\u0438\u0445 \u0447\u0438\u0441\u0435\u043b, \u0442\u043e \u0441\u0447\u0451\u0442\u0447\u0438\u043a\u0438 \u043c\u043e\u0433\u0443\u0442 \u0431\u044b\u0442\u044c \u0442\u043e\u043b\u044c\u043a\u043e \u0432 \u0434\u0432\u0443\u0445 \u0441\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u044f\u0445 \u2013 \u0435\u0441\u0442\u044c \u0438\u043b\u0438 \u043d\u0435\u0442, \u043f\u043e\u044d\u0442\u043e\u043c\u0443 \u043e\u043d\u0438 \u043c\u043e\u0433\u0443\u0442 \u0431\u044b\u0442\u044c \u043e\u0434\u043d\u043e\u0431\u0438\u0442\u043d\u044b\u043c\u0438. \u0422\u043e\u0433\u0434\u0430 \u043d\u0430\u0448 \u043c\u0430\u0441\u0441\u0438\u0432 \u0443\u0436\u043c\u0451\u0442\u0441\u044f. \u0414\u0430 \u0438 \u043c\u0430\u0441\u0441\u0438\u0432 \u043d\u0430\u043c \u043d\u0435 \u043d\u0443\u0436\u0435\u043d \u2013 \u043c\u044b \u043c\u043e\u0436\u0435\u043c \u0445\u0440\u0430\u043d\u0438\u0442\u044c \u0447\u0438\u0441\u043b\u0430 \u0432 \u0432\u0438\u0434\u0435 \u0431\u0438\u0442\u043e\u0432, \u0442\u043e \u0435\u0441\u0442\u044c \u0432\u043c\u0435\u0441\u0442\u043e \u043c\u0430\u0441\u0441\u0438\u0432\u0430 \u0443 \u043d\u0430\u0441 \u0431\u0443\u0434\u0435\u0442 \u0432\u0435\u043a\u0442\u043e\u0440. \u0427\u0438\u0442\u0430\u0435\u043c \u0444\u0430\u0439\u043b \u0438 \u0443\u0441\u0442\u0430\u043d\u0430\u0432\u043b\u0438\u0432\u0430\u0435\u043c N-\u043d\u044b\u0439 \u0431\u0438\u0442, \u0435\u0441\u043b\u0438 \u0442\u0430\u043c \u0432\u0441\u0442\u0440\u0435\u0442\u0438\u043b\u043e\u0441\u044c \u0447\u0438\u0441\u043b\u043e N. \u041f\u043e\u0441\u043b\u0435 \u044d\u0442\u043e\u0433\u043e \u043f\u0440\u043e\u0441\u0442\u043e \u043f\u0440\u043e\u0445\u043e\u0434\u0438\u043c\u0441\u044f \u043f\u043e \u0432\u0435\u043a\u0442\u043e\u0440\u0443 \u0438 \u0432\u044b\u0432\u043e\u0434\u0438\u043c \u0432 \u0444\u0430\u0439\u043b \u0442\u0435 \u0447\u0438\u0441\u043b\u0430, \u0434\u043b\u044f \u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u0432\u0437\u0432\u0435\u0434\u0435\u043d\u044b \u0431\u0438\u0442\u044b.<\/p>\n<p>  \u0422\u0430\u043a\u0438\u0435 \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u0442\u0440\u0435\u0431\u0443\u044e\u0442 \u0432\u043d\u0438\u043c\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0433\u043e \u043f\u043e\u0434\u0445\u043e\u0434\u0430, \u043f\u043e\u0441\u043a\u043e\u043b\u044c\u043a\u0443 \u0432\u0441\u0451 \u0440\u0430\u0432\u043d\u043e \u043c\u043e\u0436\u043d\u043e \u0432\u044b\u0439\u0442\u0438 \u0437\u0430 \u043f\u0440\u0435\u0434\u0435\u043b\u044b \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u0439. \u041a \u043f\u0440\u0438\u043c\u0435\u0440\u0443, \u0434\u043b\u044f \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0438 \u0432\u0441\u0435\u0445 \u0447\u0438\u0441\u0435\u043b \u0438\u0437 \u043f\u0440\u043e\u043c\u0435\u0436\u0443\u0442\u043a\u0430 \u0446\u0435\u043b\u044b\u0445 (2<sup>32<\/sup>), \u0432\u0430\u043c \u043f\u043e\u043d\u0430\u0434\u043e\u0431\u0438\u0442\u0441\u044f 1 \u0431\u0438\u0442 \u043d\u0430 \u043a\u0430\u0436\u0434\u043e\u0435 \u0447\u0438\u0441\u043b\u043e, \u0430 \u044d\u0442\u043e 4294967296 \u0431\u0438\u0442 = 536870912 \u0431\u0430\u0439\u0442 = 512 MiB. \u0410 \u0443 \u043d\u0430\u0441 \u0435\u0441\u0442\u044c \u0442\u043e\u043b\u044c\u043a\u043e 128 MiB, \u0447\u0435\u0433\u043e \u0432\u0430\u043c \u043d\u0435 \u0445\u0432\u0430\u0442\u0438\u0442. \u041d\u043e \u0432 \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u0441\u043b\u0443\u0447\u0430\u044f\u0445 \u0432\u044b\u0438\u0433\u0440\u044b\u0448 \u0431\u0443\u0434\u0435\u0442 \u043a\u043e\u043b\u043e\u0441\u0441\u0430\u043b\u044c\u043d\u044b\u043c \u2013 \u0432\u043e\u0442 \u0438\u0441\u0442\u043e\u0440\u0438\u044f \u043d\u0430 \u044d\u0442\u0443 \u0442\u0435\u043c\u0443 \u0438\u0437 <a href=\"http:\/\/www.cs.bell-labs.com\/cm\/cs\/pearls\/cto.html\">\u00abProgramming Pearls\u00bb by Jon Bentley<\/a>.<\/p>\n<p>  \u0417\u043d\u0430\u043d\u0438\u0435 \u0432\u0430\u0448\u0438\u0445 \u0434\u0430\u043d\u043d\u044b\u0445 \u043e\u0447\u0435\u043d\u044c \u043f\u043e\u043b\u0435\u0437\u043d\u043e.<\/p>\n<h4>\u0418\u0442\u043e\u0433<\/h4>\n<p>  \u0417\u0430 5 \u043c\u0435\u0441\u044f\u0446\u0435\u0432, \u043f\u043e\u0442\u0440\u0430\u0447\u0435\u043d\u043d\u044b\u0445 \u043d\u0430 \u0441\u0442\u0430\u0442\u044c\u044e, \u044f \u0441\u0434\u0435\u043b\u0430\u043b \u043c\u043d\u043e\u0433\u043e \u0447\u0435\u0433\u043e \u2013 \u0434\u0435\u0441\u044f\u0442\u043e\u043a \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c, \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u0445\u043e\u0440\u043e\u0448\u0438\u0445 \u0438\u0434\u0435\u0439, \u043c\u043d\u043e\u0433\u043e \u043f\u043b\u043e\u0445\u0438\u0445. \u0418 \u043c\u043d\u043e\u0433\u043e \u0447\u0435\u0433\u043e \u0435\u0449\u0451 \u043c\u043e\u0436\u043d\u043e \u0441\u0434\u0435\u043b\u0430\u0442\u044c \u0438 \u043f\u043e\u043f\u0440\u0430\u0432\u0438\u0442\u044c.<\/p>\n<p>  \u041f\u0440\u043e\u0441\u0442\u0430\u044f \u043f\u0440\u043e\u0431\u043b\u0435\u043c\u0430 \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0438 \u0434\u0430\u043d\u043d\u044b\u0445 \u043f\u0440\u0438 \u043d\u0435\u0434\u043e\u0441\u0442\u0430\u0442\u043a\u0435 \u043f\u0430\u043c\u044f\u0442\u0438 \u0432\u044b\u044f\u0432\u0438\u043b\u0430 \u0446\u0435\u043b\u044b\u0439 \u043d\u0430\u0431\u043e\u0440 \u0441\u0442\u0440\u0430\u043d\u043d\u043e\u0441\u0442\u0435\u0439, \u043e \u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u043c\u044b \u043e\u0431\u044b\u0447\u043d\u043e \u043d\u0435 \u0434\u0443\u043c\u0430\u0435\u043c:  <\/p>\n<ul>\n<li>\u0440\u0430\u0441\u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u0451\u043d\u043d\u044b\u0435 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u044b \u043d\u0435 \u043f\u043e\u0434\u0445\u043e\u0434\u044f\u0442 \u0434\u043b\u044f \u0432\u0441\u0435\u0445 \u043f\u0440\u043e\u0431\u043b\u0435\u043c<\/li>\n<li>\u043e\u0442\u043b\u0430\u0434\u043a\u0430 \u0438 \u043f\u0440\u043e\u0444\u0438\u043b\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u0435 \u2013 \u043e\u0447\u0435\u043d\u044c \u043f\u043e\u043b\u0435\u0437\u043d\u044b\u0435 \u0438 \u043d\u0430\u0433\u043b\u044f\u0434\u043d\u044b\u0435 \u0432\u0435\u0449\u0438<\/li>\n<li>I\/O \u2013 \u043f\u0440\u043e\u0431\u043b\u0435\u043c\u043d\u0430\u044f \u043e\u0431\u043b\u0430\u0441\u0442\u044c, \u0435\u0441\u043b\u0438 \u043d\u0435 \u043f\u0435\u0440\u0435\u043a\u043b\u0430\u0434\u044b\u0432\u0430\u0442\u044c \u0432\u0441\u044e \u0440\u0430\u0431\u043e\u0442\u0443 \u043d\u0430 \u044f\u0434\u0440\u043e<\/li>\n<li>\u043c\u043d\u043e\u0433\u043e\u043f\u043e\u0442\u043e\u0447\u043d\u043e\u0441\u0442\u044c \u043d\u0435 \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043f\u0430\u043d\u0430\u0446\u0435\u0435\u0439 \u0434\u043b\u044f \u0434\u043e\u0441\u0442\u0438\u0436\u0435\u043d\u0438\u044f \u0441\u043a\u043e\u0440\u043e\u0441\u0442\u0438<\/li>\n<li>\u0437\u043d\u0430\u0439\u0442\u0435 \u0432\u0430\u0448\u0438 \u0434\u0430\u043d\u043d\u044b\u0435 \u0438 \u0432\u0430\u0448\u0435 \u043e\u043a\u0440\u0443\u0436\u0435\u043d\u0438\u0435<\/li>\n<\/ul>\n<p>  \u0422\u0430\u0431\u043b\u0438\u0447\u043a\u0430 \u0434\u043b\u044f \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0438:  <\/p>\n<table>\n<tr>\n<td>\u0422\u0435\u0441\u0442 <\/td>\n<td>\u041d\u0430\u0438\u0432\u043d\u044b\u0439 QuickSort <\/td>\n<td>mmap \u0438 QuickSort <\/td>\n<td>\u0412\u043d\u0435\u0448\u043d\u044f\u044f \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0430 \u0441\u043e \u0441\u043b\u0438\u044f\u043d\u0438\u0435\u043c <\/td>\n<td>\u041c\u043d\u043e\u0433\u043e\u043f\u043e\u0442\u043e\u0447\u043d\u0430\u044f \u0432\u043d\u0435\u0448\u043d\u044f\u044f \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0430 \u0441\u043e \u0441\u043b\u0438\u044f\u043d\u0438\u0435\u043c <\/td>\n<td>\u0421\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0430 \u043f\u043e\u0434\u0441\u0447\u0451\u0442\u043e\u043c<\/td>\n<\/tr>\n<tr>\n<td>4 MiB in 2 MiB <\/td>\n<td>Segfault <\/td>\n<td>N\/A <\/td>\n<td>0.38s <\/td>\n<td>0.41s <\/td>\n<td>0.01<\/td>\n<\/tr>\n<tr>\n<td>500 MB in 128 MiB <\/td>\n<td>Segfault <\/td>\n<td>32.25s <\/td>\n<td>87.14s <\/td>\n<td>91.04 <\/td>\n<td>3.24<\/td>\n<\/tr>\n<\/table>\n<p>  \u041f\u043e\u0437\u043d\u0430\u0439\u0442\u0435 \u0432\u0430\u0448\u0438 \u0434\u0430\u043d\u043d\u044b\u0435 \u0438 \u0440\u0430\u0437\u0440\u0430\u0431\u043e\u0442\u0430\u0439\u0442\u0435 \u043f\u0440\u043e\u0441\u0442\u043e\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0434\u043b\u044f \u0440\u0430\u0431\u043e\u0442\u044b \u0441 \u043d\u0438\u043c\u0438!<\/p>\n<h4>\u0421\u0441\u044b\u043b\u043a\u0438<\/h4>\n<p>  <\/p>\n<ul>\n<li><a href=\"http:\/\/neopythonic.blogspot.ru\/2008\/10\/sorting-million-32-bit-integers-in-2mb.html\">\u0421\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0430 \u043c\u0438\u043b\u043b\u0438\u043e\u043d\u0430 32-\u0431\u0438\u0442\u043d\u044b\u0445 \u0447\u0438\u0441\u0435\u043b \u0432 2 \u041c\u0431 \u043f\u0430\u043c\u044f\u0442\u0438 \u043d\u0430 Python<\/a><\/li>\n<li><a href=\"http:\/\/www.umbrant.com\/blog\/2011\/external_sorting.html\">\u0412\u043d\u0435\u0448\u043d\u044f\u044f \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0430 \u0431\u043e\u043b\u044c\u0448\u0438\u0445 \u043d\u0430\u0431\u043e\u0440\u043e\u0432 \u0434\u0430\u043d\u043d\u044b\u0445<\/a><\/li>\n<li><a href=\"http:\/\/www.reddit.com\/r\/programming\/comments\/grrrr\/efficiently_sorting_datasets_bigger_than_memory_c\/\">\u042d\u0444\u0444\u0435\u043a\u0442\u0438\u0432\u043d\u0430\u044f \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0430 \u0434\u0430\u043d\u043d\u044b\u0445, \u043f\u043e \u043e\u0431\u044a\u0451\u043c\u0443 \u043f\u0440\u0435\u0432\u044b\u0448\u0430\u044e\u0449\u0438\u0445 \u043e\u0431\u044a\u0451\u043c \u043f\u0430\u043c\u044f\u0442\u0438<\/a><\/li>\n<li><a href=\"http:\/\/www.cs.bell-labs.com\/cm\/cs\/pearls\/cto.html\">\u0420\u0430\u0441\u043a\u0440\u044b\u0432\u0430\u0435\u043c \u0443\u0441\u0442\u0440\u0438\u0446\u0443 (1-\u044f \u0441\u0442\u0430\u0442\u044c\u0438 \u0438\u0437 \u00ab\u0416\u0435\u043c\u0447\u0443\u0436\u0438\u043d \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f\u00bb)<\/a><\/li>\n<li><a href=\"http:\/\/www.drdobbs.com\/parallel\/multithreaded-file-io\/220300055\">\u041c\u043d\u043e\u0433\u043e\u043f\u043e\u0442\u043e\u0447\u043d\u044b\u0439 \u0432\u0432\u043e\u0434 \u0438 \u0432\u044b\u0432\u043e\u0434 \u0444\u0430\u0439\u043b\u043e\u0432<\/a><\/li>\n<li><a href=\"http:\/\/www.drdobbs.com\/architecture-and-design\/algorithm-improvement-through-performanc\/220300654\">\u0423\u043b\u0443\u0447\u0448\u0435\u043d\u0438\u0435 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u043e\u0432 \u043f\u0440\u0438 \u043f\u043e\u043c\u043e\u0449\u0438 \u0438\u0437\u043c\u0435\u0440\u0435\u043d\u0438\u044f \u0431\u044b\u0441\u0442\u0440\u043e\u0434\u0435\u0439\u0441\u0442\u0432\u0438\u044f, \u0447\u0430\u0441\u0442\u044c 2<\/a><\/li>\n<li><a href=\"http:\/\/stackoverflow.com\/questions\/3969813\/which-parallel-sorting-algorithm-has-the-best-average-case-performance\">\u0410\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u044b \u043f\u0430\u0440\u0430\u043b\u043b\u0435\u043b\u044c\u043d\u043e\u0439 \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0438<\/a><\/li>\n<\/ul>\n<div class=\"clear\"><\/div>\n<p> \u0441\u0441\u044b\u043b\u043a\u0430 \u043d\u0430 \u043e\u0440\u0438\u0433\u0438\u043d\u0430\u043b \u0441\u0442\u0430\u0442\u044c\u0438 <a href=\"http:\/\/habrahabr.ru\/post\/266557\/\"> http:\/\/habrahabr.ru\/post\/266557\/<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<p>       <i>\u0410\u0432\u0442\u043e\u0440 \u043e\u0440\u0438\u0433\u0438\u043d\u0430\u043b\u0430 \u043d\u0430 \u0430\u043d\u0433\u043b\u0438\u0439\u0441\u043a\u043e\u043c \u044f\u0437\u044b\u043a\u0435 \u2014 \u0445\u0430\u0431\u0440\u0430\u044e\u0437\u0435\u0440  <a href=\"http:\/\/habrahabr.ru\/users\/dzeban\/\" class=\"user_link\">dzeban<\/a> <\/i><\/p>\n<h4>\u0412\u0432\u0435\u0434\u0435\u043d\u0438\u0435<\/h4>\n<p>  <a href=\"http:\/\/habrahabr.ru\/post\/266083\/\">\u0412 \u043f\u0440\u043e\u0448\u043b\u044b\u0439 \u0440\u0430\u0437 \u043c\u044b \u043e\u0431\u0441\u0443\u0434\u0438\u043b\u0438<\/a>, \u043a\u0430\u043a \u043c\u043e\u0436\u043d\u043e \u0438\u0441\u043a\u0443\u0441\u0441\u0442\u0432\u0435\u043d\u043d\u043e \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0438\u0442\u044c \u0434\u043e\u0441\u0442\u0443\u043f\u043d\u0443\u044e \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0435 \u043f\u0430\u043c\u044f\u0442\u044c. \u0412 \u043a\u0430\u0447\u0435\u0441\u0442\u0432\u0435 \u0431\u043e\u043d\u0443\u0441\u0430 \u044f \u0437\u0430\u043f\u043e\u043b\u0443\u0447\u0438\u043b \u0441\u0435\u0431\u0435 <a href=\"https:\/\/github.com\/dzeban\/restrict-memory\/blob\/master\/memrestrict.c\">libmemrestrict <\/a>\u2013 \u0431\u0438\u0431\u043b\u0438\u043e\u0442\u0435\u043a\u0443 \u0441 \u043e\u0431\u0451\u0440\u0442\u043a\u0430\u043c\u0438 \u0444\u0443\u043d\u043a\u0446\u0438\u0439 \u0432\u0440\u043e\u0434\u0435 malloc \u0434\u043b\u044f \u043e\u0442\u0441\u043b\u0435\u0436\u0438\u0432\u0430\u043d\u0438\u044f \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u044f \u043f\u0430\u043c\u044f\u0442\u0438, \u0438 <a href=\"https:\/\/github.com\/dzeban\/restrict-memory\/blob\/master\/ptrace-restrict.c\">ptrace-restrict <\/a>\u2014 \u0438\u043d\u0441\u0442\u0440\u0443\u043c\u0435\u043d\u0442 \u043d\u0430 \u0431\u0430\u0437\u0435 ptrace, \u043f\u0435\u0440\u0435\u0445\u0432\u0430\u0442\u044b\u0432\u0430\u044e\u0449\u0438\u0439 \u0432\u044b\u0437\u043e\u0432\u044b brk, sbrk \u0438 mmap \u0441 \u0442\u043e\u0439 \u0436\u0435 \u0446\u0435\u043b\u044c\u044e.<\/p>\n<p>  \u0422\u0430\u043a \u0437\u0430\u0447\u0435\u043c \u043d\u0430\u043c \u043f\u044b\u0442\u0430\u0442\u044c\u0441\u044f \u043e\u0440\u0433\u0430\u043d\u0438\u0437\u043e\u0432\u044b\u0432\u0430\u0442\u044c \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u0435 \u043f\u0430\u043c\u044f\u0442\u0438 \u2013 \u0442\u0430\u043a \u043b\u0438 \u044d\u0442\u043e \u0447\u0430\u0441\u0442\u043e \u0432\u0441\u0442\u0440\u0435\u0447\u0430\u0435\u0442\u0441\u044f? \u041a\u043e\u0433\u0434\u0430 \u0432 \u043f\u043e\u0441\u043b\u0435\u0434\u043d\u0438\u0439 \u0440\u0430\u0437 \u041e\u041e\u041c \u043f\u0440\u0438\u0431\u0438\u043b \u0432\u0430\u0448\u0435 \u043f\u0440\u0438\u043b\u043e\u0436\u0435\u043d\u0438\u0435? \u0412\u044b \u0432\u0441\u0435\u0433\u0434\u0430 \u0434\u0443\u043c\u0430\u0435\u0442\u0435 \u043e \u043f\u043e\u0442\u0440\u0435\u0431\u043b\u0435\u043d\u0438\u0438 \u043f\u0430\u043c\u044f\u0442\u0438 \u0432\u043e \u0432\u0440\u0435\u043c\u044f \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f? \u041f\u0430\u043c\u044f\u0442\u044c \u2013 \u0448\u0442\u0443\u043a\u0430 \u0434\u0435\u0448\u0451\u0432\u0430\u044f, \u0438 \u0435\u0441\u043b\u0438 \u0432\u0430\u043c \u043d\u0435 \u0445\u0432\u0430\u0442\u0430\u0435\u0442 \u043f\u0430\u043c\u044f\u0442\u0438, \u0434\u043e\u0431\u0430\u0432\u044c\u0442\u0435 \u0435\u0449\u0451 \u043f\u0430\u0440\u0443 \u0433\u0438\u0433\u0430\u0431\u0430\u0439\u0442.<\/p>\n<p>  \u0418, \u0442\u0435\u043c \u043d\u0435 \u043c\u0435\u043d\u0435\u0435, \u043d\u0435\u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e \u0431\u0435\u0441\u043a\u043e\u043d\u0435\u0447\u043d\u043e \u0434\u043e\u0431\u0430\u0432\u043b\u044f\u0442\u044c \u043f\u0430\u043c\u044f\u0442\u044c \u2013 \u0438 \u043d\u0435 \u0438\u0437-\u0437\u0430 \u0442\u043e\u0433\u043e, \u0447\u0442\u043e \u0443 \u0432\u0430\u0441 \u043d\u0435\u0442 \u0431\u0435\u0441\u043a\u043e\u043d\u0435\u0447\u043d\u043e\u0433\u043e \u0435\u0451 \u0438\u0441\u0442\u043e\u0447\u043d\u0438\u043a\u0430. \u041f\u0440\u0438 \u043e\u0431\u0440\u0430\u0431\u043e\u0442\u043a\u0435 \u0411\u043e\u043b\u044c\u0448\u0438\u0445 \u0434\u0430\u043d\u043d\u044b\u0445 \u043f\u0440\u043e\u0441\u0442\u043e \u043d\u0435\u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e \u0432\u043c\u0435\u0441\u0442\u0438\u0442\u044c \u0432\u0435\u0441\u044c \u0432\u0432\u043e\u0434 \u0432 \u043c\u0430\u0441\u0441\u0438\u0432 \u2013 \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e \u0440\u0430\u0441\u043f\u0440\u0435\u0434\u0435\u043b\u044f\u0442\u044c \u0434\u0430\u043d\u043d\u044b\u0435 \u043c\u0435\u0436\u0434\u0443 \u043e\u043f\u0435\u0440\u0430\u0442\u0438\u0432\u043a\u043e\u0439, \u043d\u043e\u0441\u0438\u0442\u0435\u043b\u044f\u043c\u0438 \u0438 \u0441\u0435\u0442\u044c\u044e. \u041d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u044b \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u044b \u0438 \u0442\u0435\u0445\u043d\u0438\u043a\u0438 \u0434\u043b\u044f \u0442\u0430\u043a\u043e\u0439 \u043e\u0431\u0440\u0430\u0431\u043e\u0442\u043a\u0438 \u0434\u0430\u043d\u043d\u044b\u0445.<\/p>\n<p>  \u0418 \u0432\u043e\u0442 \u044f \u0437\u0430\u043d\u044f\u043b\u0441\u044f \u043f\u043e\u0434\u043e\u0431\u043d\u044b\u043c\u0438 \u0437\u0430\u0434\u0430\u0447\u0430\u043c\u0438, \u043d\u0430\u0447\u0430\u0432 \u0441 \u043f\u0440\u043e\u0441\u0442\u043e\u0439 \u2013 \u043a\u0430\u043a \u043e\u0442\u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u043c\u0438\u043b\u043b\u0438\u043e\u043d \u0446\u0435\u043b\u044b\u0445 \u0447\u0438\u0441\u0435\u043b (4 MiB \u0434\u0430\u043d\u043d\u044b\u0445) \u043f\u0440\u0438 \u043d\u0430\u043b\u0438\u0447\u0438\u0438 2 MiB \u043f\u0430\u043c\u044f\u0442\u0438? \u042d\u0442\u0443 \u0437\u0430\u0434\u0430\u0447\u0443 \u043c\u043e\u0436\u043d\u043e \u043e\u0431\u043e\u0431\u0449\u0438\u0442\u044c \u043d\u0430 \u0442\u043e\u0442 \u0441\u043b\u0443\u0447\u0430\u0439, \u043a\u043e\u0433\u0434\u0430 \u0443 \u0432\u0430\u0441 \u043d\u0435\u0434\u043e\u0441\u0442\u0430\u0442\u043e\u0447\u043d\u043e \u043f\u0430\u043c\u044f\u0442\u0438, \u0447\u0442\u043e\u0431\u044b \u0432\u043c\u0435\u0441\u0442\u0438\u0442\u044c \u0432\u0441\u0435 \u0434\u0430\u043d\u043d\u044b\u0435.<\/p>\n<h4>\u0414\u0430\u043d\u043e<\/h4>\n<p>  \u041d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e \u043d\u0430\u043f\u0438\u0441\u0430\u0442\u044c \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0443 \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0438 \u043d\u0430\u0431\u043e\u0440\u0430 \u0446\u0435\u043b\u044b\u0445 \u0447\u0438\u0441\u0435\u043b, \u0445\u0440\u0430\u043d\u044f\u0449\u0438\u0445\u0441\u044f \u0432 \u0444\u0430\u0439\u043b\u0435. \u0414\u043b\u044f \u0435\u0433\u043e \u0441\u043e\u0437\u0434\u0430\u043d\u0438\u044f \u044f \u043d\u0430\u043f\u0438\u0441\u0430\u043b \u043f\u0440\u043e\u0441\u0442\u0435\u0439\u0448\u0438\u0435 \u0443\u0442\u0438\u043b\u0438\u0442\u044b <a href=\"https:\/\/github.com\/dzeban\/cs\/blob\/master\/number\/randints.c\">randints <\/a>\u0438 <a href=\"https:\/\/github.com\/dzeban\/cs\/blob\/master\/number\/rangeints.c\">rangeints<\/a><\/p>\n<p>  \u041f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0430 \u0434\u043e\u043b\u0436\u043d\u0430 \u0432\u044b\u0434\u0430\u0432\u0430\u0442\u044c \u043e\u0442\u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u044b\u0439 \u043c\u0430\u0441\u0441\u0438\u0432 \u043d\u0430 stdout \u0432 \u0432\u0438\u0434\u0435 \u0442\u0435\u043a\u0441\u0442\u0430<\/p>\n<p>  \u041e\u043d\u0430 \u0434\u043e\u043b\u0436\u043d\u0430 \u0438\u0437\u043c\u0435\u0440\u0438\u0442\u044c \u0432\u0440\u0435\u043c\u044f \u0440\u0430\u0431\u043e\u0442\u044b \u0438 \u0432\u044b\u0432\u0435\u0441\u0442\u0438 \u0435\u0433\u043e \u043d\u0430 stderr. \u041d\u0435\u043b\u044c\u0437\u044f \u043f\u0440\u043e\u0441\u0442\u043e \u0437\u0430\u043f\u0443\u0441\u0442\u0438\u0442\u044c \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0443 \u0447\u0435\u0440\u0435\u0437 \u0443\u0442\u0438\u043b\u0438\u0442\u0443 time, \u043f\u043e\u0442\u043e\u043c\u0443 \u0447\u0442\u043e \u043e\u043d\u0430 \u043f\u043e\u0441\u0447\u0438\u0442\u0430\u0435\u0442 \u0432\u0440\u0435\u043c\u044f \u043d\u0430 \u0447\u0442\u0435\u043d\u0438\u0435 \u0444\u0430\u0439\u043b\u0430 \u0438 \u0432\u0440\u0435\u043c\u044f \u043d\u0430 \u0435\u0433\u043e \u0432\u044b\u0432\u043e\u0434.<\/p>\n<p>  \u041e\u043d\u0430 \u0434\u043e\u043b\u0436\u043d\u0430 \u0440\u0430\u0431\u043e\u0442\u0430\u0442\u044c, \u0438\u043c\u0435\u044f \u043f\u0430\u043c\u044f\u0442\u0438 \u043a\u0430\u043a \u043c\u0438\u043d\u0438\u043c\u0443\u043c \u0432 \u0434\u0432\u0430 \u0440\u0430\u0437\u0430 \u043c\u0435\u043d\u044c\u0448\u0435 \u043e\u0431\u044a\u0451\u043c\u0430 \u0444\u0430\u0439\u043b\u0430. \u0414\u043b\u044f \u044d\u0442\u043e\u0433\u043e \u043c\u044b \u043f\u0440\u0438\u043c\u0435\u043d\u0438\u043c libmemrestrict \u0438\u043b\u0438 ptrace-restrict.<\/p>\n<p>  \u0414\u043b\u044f \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u043c\u0435\u0442\u043e\u0434\u043e\u0432 \u044d\u0442\u0438 \u0443\u0442\u0438\u043b\u0438\u0442\u044b \u043d\u0435 \u043f\u0440\u0438\u0433\u043e\u0434\u044f\u0442\u0441\u044f. \u041d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u0434\u043b\u044f mmap \u043e\u043d\u0438 \u043d\u0435 \u0441\u0440\u0430\u0431\u043e\u0442\u0430\u044e\u0442 \u2013 \u043f\u0440\u0438\u0434\u0451\u0442\u0441\u044f \u0444\u0438\u0437\u0438\u0447\u0435\u0441\u043a\u0438 \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0438\u0442\u044c \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u0435 \u043f\u0430\u043c\u044f\u0442\u0438.<\/p>\n<p>  \u041e\u043d\u0438 \u0431\u0443\u0434\u0443\u0442 \u043f\u0440\u043e\u0432\u0435\u0440\u044f\u0442\u044c\u0441\u044f \u0434\u043b\u044f \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u043e\u0440\u0438\u0433\u0438\u043d\u0430\u043b\u044c\u043d\u043e\u0439 \u0437\u0430\u0434\u0430\u0447\u0438 (\u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0438 4 MiB \u0432 2 MiB). \u0422\u0430\u043a\u0436\u0435 \u044f \u0437\u0430\u043f\u0443\u0449\u0443 \u0438\u0445 \u043d\u0430 \u0432\u0438\u0440\u0442\u0443\u0430\u043b\u043a\u0435 \u0441\u043e 128 MiB \u043f\u0430\u043c\u044f\u0442\u0438 \u0434\u043b\u044f \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0438 500 Mb (125 \u043c\u0438\u043b\u043b\u0438\u043e\u043d\u043e\u0432 \u0447\u0435\u0442\u044b\u0440\u0451\u0445\u0431\u0430\u0439\u0442\u043d\u044b\u0445 \u0446\u0435\u043b\u044b\u0445).  <\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[],"tags":[],"class_list":["post-265316","post","type-post","status-publish","format-standard","hentry"],"_links":{"self":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/265316","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=265316"}],"version-history":[{"count":0,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/265316\/revisions"}],"wp:attachment":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=265316"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=265316"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=265316"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}