Каким должен быть язык программирования? Анализ и критика Описание языка Компилятор
Отечественные разработки Cтатьи на компьютерные темы Компьютерный юмор Новости и прочее

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

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

            Дело осложнялось тем, что компилятор, который я использую [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*229=4294967296 байт. И это только для хранения адресов возврата! Но возникшую сложность работы со стеком я решил обратить себе на пользу и специально в разных других тестах, там, где таких больших значений не требовалось, начал устанавливать значение указателя стека больше 232. Этот прием позволил быстро выявить все свои ошибки перевода с 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

Автор: Д.Ю.Караваев. 09.08.2015

Опубликовано: 2018.08.26, последняя правка: 2022.02.17    16:40

ОценитеОценки посетителей
   █████████ 3 (21.4%)
   ████████████ 4 (28.5%)
   ████████████ 4 (28.5%)
   █████████ 3 (21.4%)

Отзывы

✅  2022/02/20 20:54, Автор сайта          #0 

Я тоже загляделся на воздушный шарик, как цирковой стрелок :) Но в этой статье нет описания теста Кнута. Главный герой отсутствует на сцене. А без него, как кажется, разговор ведётся если не впустую, то как-то отвлечённо. Посмотрел Википедии исходник на Алгол-60:
begin real procedure A(k, x1, x2, x3, x4, x5);
value k; integer k;
real x1, x2, x3, x4, x5;
begin real procedure B;
begin k := k - 1;
B := A := A(k, B, x1, x2, x3, x4)
end;
if k ≤ 0 then A := x4 + x5 else B
end;
outreal(A(10, 1, -1, -1, 1, 0))
end;
Вроде коротко, но мало что понятно. Алгол-60 — не торт. Кстати, исходник на PL/1 в статье Дмитрия Юрьевича тоже отсутствует :) Разбираемся с объяснениями.

1. Определения вложенных функций: поскольку B определяется в локальном контексте A, тело B имеет доступ к объектам, которые являются локальными для A. Это в первую очередь k, который изменяем, а также x1, x2, x3, x4 и x5. Для Pascal, потомка Algol это просто, но для C, другого потомка Algol, это невозможно без ручного моделирования механизма адресации C для передачи указатели на локальные переменные функций.

2. Ссылки на функции : в рекурсивном вызове A (k, B, x1, x2, x3, x4) B является не вызовом, а указателем на B. В будет вызвана через указатель только тогда, когда k больше нуля.

3. Дуализм констант / функций: параметры от x1 до x5 в вызове A могут быть числовыми константами или указателем на функцию B, выражение x4 + x5 должно быть подготовлено для обработки обоих случаев, как если бы формальные параметры x4 и x5 были заменены соответствующими фактическими параметр (вызов по имени). Это, вероятно, больше проблема для языков со статической типизацией, чем для языков с динамической типизацией.

И всё равно не всё ясно.

Отдельно хочется отметить впечатления от прочтения исходника на Алголе-60. По «технике безопасности» Алгол ушёл не далеко от ассемблера. Одна процедура запросто модифицирует значения в другой процедуре. В параметрах процедуры адрес процедуры запросто перемешивается с числовыми константами. Внутри определения процедуры вызывается сама процедура с константными параметрами. По современным меркам — это говнокод. При разглядывании «древнее» программирование видится ездой по дороге в любую сторону в любом месте проезжей части. Дорожной разметки нет, дорожных знаков нет, и какое — лево- или правостороннее движение — не понятно.

✅  2022/02/20 21:35, kt          #1 

Вот ссылка на исходную статью с текстом.
https://rsdn.org/article/pl1/PL1ex7/pl1ex7.xml

✅  2022/02/20 22:00, Автор сайта          #2 

Да, прошу извинить, на RSDN Ваша статья подробнее. И там исходник на PL/1 есть. А на rosettacode.org есть исходники на других языках.

✅  2022/02/21 13:16, Gudleifr          #3 

В параметрах процедуры адрес процедуры запросто перемешивается с числовыми константами

В Algol 60 не было передачи "по адресу", было "по наименованию", т.е. текстографически.

По «технике безопасности» Алгол ушёл не далеко от ассемблера

Это, как ругать компьютер за подключение блока питания к сети 220v. Опасно, же!

Добавить свой отзыв

Написать автору можно на электронную почту
mail(аt)compiler.su

Авторизация

Регистрация

Выслать пароль

Карта сайта


Содержание

Каким должен быть язык программирования?

Анализ и критика

Описание языка

Компилятор

Отечественные разработки

Cтатьи на компьютерные темы

●  О превращении кибернетики в шаманство

●  Про лебедей, раков и щук

●  О замысле и воплощении

●  О русском ассемблере

●  Арифметика синтаксиса-3

●  Концепция владения в Rust на примерах

●●  Концепция владения в Rust на примерах, часть 2

●●  Концепция владения в Rust на примерах, часть 3

●  Суть побочных эффектов в чисто функциональных языках

●  О неулучшаемой архитектуре процессоров

●  Двадцать тысяч строк кода, которые потрясут мир?

●  Почему владение/заимствование в Rust такое сложное?

●  Масштабируемые архитектуры программ

●  О создании языков

●●  Джоэл Спольски о функциональном программировании

●  Почему Хаскелл так мало используется в отрасли?

●  Программирование исчезнет. Будет дрессировка нейронных сетей

●  О глупости «программирования на естественном языке»

●  Десятка худших фич C#

●  Бесплатный софт в мышеловке

●  Исповедь правового нигилиста

●  ЕС ЭВМ — это измена, трусость и обман?

●  Русской операционной системой должна стать ReactOS

●  Почему обречён язык Форт

●  Программирование без программистов — это медицина без врачей

●  Электроника без электронщиков

●  Программисты-профессионалы и программирующие инженеры

●  Статьи Дмитрия Караваева

●●  Идеальный транслятор

●●  В защиту PL/1

●●  К вопросу о совершенствовании языка программирования

●●  Опыт самостоятельного развития средства программирования в РКК «Энергия»

●●  О реализации метода оптимизации при компиляции

●●  О реализации метода распределения регистров при компиляции

●●  О распределении памяти при выполнении теста Кнута

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

●●  О размещении переменных в стеке

●●  Сколько проходов должно быть у транслятора?

●●  Чтение лексем

●●  Экстракоды при синтезе программ

●●  Об исключенных командах или за что «списали» инструкцию INTO?

●●  Типы в инженерных задачах

●●  Непрерывное компилирование

●●  Об одной реализации специализированных операторов ввода-вывода

●●  Особенности реализации структурной обработки исключений в Win64

●●  О русском языке в программировании

●●  Формула расчета точности для умножения

●●  Права доступа к переменным

●●  Заметки о выходе из функции без значения и зеркальности get и put

●●  Модификация исполняемого кода как способ реализации массивов с изменяемыми границами

●●  Ошибка при отсутствии выполняемых действий

●●  О PL/1 и почему в нём не зарезервированы ключевые слова

●●  Не поминайте всуе PL/1

●●  Скорость в попугаях

●●  Крах операции «Инкогнито»

●●  Предопределённый результат

●●  Поддержка профилирования кода программы на низком уровне

●●  К вопросу о парадигмах

●  Следующие 7000 языков программирования

●●  Что нового с 1966 года?

●●  Наблюдаемая эволюция языка программирования

●●  Ряд важных языков в 2017 году

●●  Слоны в комнате

●●  Следующие 7000 языков программирования: заключение

Компьютерный юмор

Новости и прочее




Последние отзывы

2024/12/07 20:54 ••• Клихальт
Переключатель

2024/12/06 18:44 ••• Анкнав
Русский язык и программирование

2024/12/01 00:00 ••• alextretyak
Продолжение цикла и выход из него

2024/11/29 23:08 ••• Вежливый Лис
О русском ассемблере

2024/11/26 23:53 ••• Бурановский дедушка
ЕС ЭВМ — это измена, трусость и обман?

2024/11/25 18:31 ••• Деньги на WWWетер
Ресурсы, посвящённые созданию языков программирования и компиляторов

2024/11/12 20:24 ••• Вежливый Лис
Правила языка: строки, комментарии

2024/11/12 13:10 ••• Вежливый Лис
Новости и прочее

2024/11/12 00:32 ••• Автор сайта
Оценка надёжности функции с несколькими реализациями

2024/11/06 02:50 ••• Иван
Энтузиасты-разработчики компиляторов и их проекты

2024/11/05 23:51 ••• Борис К.
Изменение приоритетов операций

2024/11/05 23:38 ••• Борис К.
Шестнадцатиричные и двоичные константы

2024/11/01 12:11 ••• ИванАс
Русской операционной системой должна стать ReactOS