Опыты со стеком или «чемпионат по выполнению теста Кнута»

Первая публикация 09.08.2015

Stack experiments or «Knut test competition»

Описание теста Д. Кнута «Man or boy?» на сайте [1] мне попалось на глаза случайно, но очень увлекло. Помнится, в прекрасном произведении «Три толстяка» был один персонаж – (цирковой) стрелок. Он во время погони увидел пролетающий воздушный шарик и сразу обо всем забыл, в том числе о погоне. Главное для него стало – попасть в шар. Я стал в чем-то похож на этого стрелка (который, кстати, в шар так и не попал). В ущерб работе и другим занятиям, главным для меня стало – выполнить тест Кнута с хорошим результатом, т.е. максимально эффективно использовать доступные стек и память так, чтобы добиться правильного завершения теста с наибольшим базовым значением. Базовое значение теста по существу является показателем степени числа рекурсивно вложенных вызовов, если такое число представить в виде 2ⁿ.

Дело осложнялось тем, что компилятор, который я использую [2], не запоминает контекст вызова рекурсивных процедур и, по сути, вообще не может выполнить этот тест. Эти трудности были обойдены моделированием запоминания контекстов через обращение к массиву, а собственно аппаратный стек стал использоваться только для запоминания адресов возврата из рекурсивных процедур. Кроме этого, возникли сложности с фрагментацией памяти из-за фиксированного размещения системных библиотек Windows-XP, что не позволяло использовать все доступные 3 Гбайт памяти как одну непрерывную область. Но и эти сложности были преодолены. Результаты я представил в статье [3] и был очень горд тем, что смог выполнить на обычном ноутбуке тест с базовым значением 27, что на тот момент являлось «мировым рекордом» среди всех результатов, перечисленных на сайте [1].

Поскольку этот сайт постоянно обновляется и дополняется, я года полтора продолжал считать себя действующим чемпионом по выполнению теста Кнута, хотя и отдавал себе отчет в том, что, например, массовый переход на Win64 изменит эту ситуацию. И вот на сайте появилось сообщение, что тест, написанный на Haskell, выполнен для базового значения 30. Таким образом, по использованным ресурсам мой рекорд был превзойден сразу в восемь раз, а я превратился в «экс-чемпиона». Разумеется, новый рекорд был установлен не на маленьком домашнем ноутбуке c 32-разрядной Windows, а на солидном AMD Opteron 6282SE c 384 Гбайт доступной памяти в «куче».

Но и я к тому времени приобрел для дома ноутбук c Intel Core i5-3210M, c 4 Гбайт памяти и домашней Windows 7 и занялся переводом своих средств разработки на Win64. Естественно, что первым тестом, который проверялся для доработанного компилятора, стал все тот же тест Кнута. С точки зрения языка PL/1, на котором я пишу, все получилось изящно – в доработанном для Win64 компиляторе появилась возможность определять переменные как целые со знаком размером в 8 байт, т.е. с атрибутами BINARY FIXED(63), которыми и были заменены в исходном тексте теста (текст на PL/1 я приводил в [3]) все переменные, ранее имевшие тип BINARY FIXED(31).

В целом, сложности, которые пришлось преодолевать в Win32, остались и в Win64. Например, некоторые системные библиотеки вроде NTDLL.DLL или KERNEL32.DLL и в Windows 7 упорно не хотят загружаться в «верхние» адреса памяти, разбивая свободное адресное пространство на несколько несмежных фрагментов, хотя теперь «потери» при этом не превышают 1 Гбайт.

Однако самым сложным для меня оказалась работа с «большим» стеком. Даже психологически трудно после стольких лет работы с Win32 привыкнуть к тому, что для хранения указателя вершины стека реально нужно 8 байт. Помните старое заявление Билла Гейтса, что «640 Кбайт хватит для всех задач»? Так вот, для выполнения теста Кнута с базовым значением 30 даже при моем построении алгоритма (напомню, в стеке хранится только дерево из адресов возврата двух рекурсивных процедур) для стека уже требуется 16*2²⁹=4294967296 байт. И это только для хранения адресов возврата! Но возникшую сложность работы со стеком я решил обратить себе на пользу и специально в разных других тестах, там, где таких больших значений не требовалось, начал устанавливать значение указателя стека больше 2³². Этот прием позволил быстро выявить все свои ошибки перевода с Win32 на Win64, связанные со стеком. И речь идет не просто о пропущенных в ассемблерных текстах системных подпрограмм ESP вместо требуемых теперь RSP, но и о более сложных связях. Тест Кнута неожиданно оказался прекрасной проверкой правильности средств разработки в среде Win64.

В результате мои программы стали более «ошибкоустойчивы» и как приятный бонус я вернул себе звание «чемпиона мира», выполнив в Windows 7 тест с базовым значением 31.

Как следует из этого «скриншота», через полтора часа после запуска теста глубина вложенных вызовов превысила миллиард. Т.е. при переходе на Win64 по сравнению с предыдущим лучшим своим результатом в Win32 удалось увеличить задействованные в программе ресурсы (память и стек) в 16 раз! Поскольку сами объекты теста (контексты вызовов, адреса возврата и возвращаемое значение) тоже увеличились с 4 до 8 байт, абсолютно использованные ресурсы увеличились по сравнению с Win32 даже в 32 раза. Конечно, при этом тест считается не быстро из-за недостаточного размера физической памяти. Кстати, на этом же ноутбуке можно было бы в принципе выполнить и тест с базовым значением 32, но для этого пришлось бы освободить весь 250 Гбайтный диск для файла подкачки страниц (нужно более 200 Гбайт). Очевидно, что следующие рекорды нужно ставить не на домашних компьютерах. Ну, или подождать, пока ресурсы домашних компьютеров не достигнут соответствующих величин.

Наверняка у читателя назрел вопрос: зачем было нужно это соревнование автора с неведомыми ему соперниками? И не напоминает ли оно соревнование «людоедки» Эллочки с дочерью миллионера Вандербильда? Нет, не напоминает. Потому, что решение сложной задачи использования всех возможных ресурсов компьютера (пусть даже эти ресурсы и довольно скромны по современным понятиям), позволяет использовать затем эти же приемы в реальных задачах, о чем я уже и писал в предыдущей статье [3]. В моем случае, приемы работы с «большими» массивами, размещенными к тому же в нескольких областях памяти, пригодились впоследствии при обработке больших объемов картографических данных. С помощью теста Кнута я научился реально использовать в программе всю доступную память.

И при достижении наилучших результатов элемент состязательности весьма важен. Поэтому призываю всех принять участие в «чемпионате по выполнению теста Кнута». Как показывает мой опыт, время, потраченное на разработку новых приемов использования доступной памяти и стека, не пропадает даром.

Литература

1. rosettacode.org/wiki/Man_or_boy_test
2. Д.Ю.Караваев «К вопросу о совершенствовании языка программирования» RSDN Magazine #4 2011
3. Д.Ю.Караваев «О распределении памяти при выполнении теста Кнута» RSDN Magazine #2 2012