Замер скорости: во что обходятся компиляция и работа

Работа: быстрее Python в 1,28 раза, медленнее Node в 1,81, медленнее написанного руками C в 4,52 — геометрическое среднее по пяти задачам. Компиляция окупается против Python на трёх задачах из пяти (за 6, 13 и 20 прогонов), против Node — ни на одной. Цена доказуемости: на 97,5 % функций корпуса она неотличима от нуля, на оставшихся 2,5 % сторож объявленной меры утраивает время функции.

Что мерили

Три вопроса: во сколько раз мы медленнее Python и Node, какая часть отставания — цена доказуемости, а какая — недоделанность, и что даёт наибольший выигрыш за наименьшую работу.

Пять задач, каждая записана на flang, Python и JavaScript, плюс эталон на C, написанный руками. Без эталона отставание flang не разложить на «своё» и «общее для всех компилируемых языков».

Правило, по которому написаны все три текста: алгоритм один, а записан он так, как эту вещь пишут на данном языке. Никаких библиотечных сокращений ни у кого: ни sorted(), ни Array.prototype.sort, ни регулярных выражений, ни срезов вида lst[0::2]. Разрешены ровно те встроенные формы, которые есть у всех троих: разделение строки и перевод строки в число. Где flang печатается в цикл (хвостовой самовызов), у Python и JS стоит цикл; где flang рекурсирует по-настоящему, рекурсируют и они.

Вход не передаётся снаружи: каждая задача сама строит свои данные одним и тем же линейным конгруэнтным генератором. Иначе замер мерил бы разбор JSON на входе. Выход — одно число, контрольная сумма, чувствительная к порядку: печать стотысячного списка съела бы больше, чем сама сортировка.

Две задачи записаны на flang ДВАЖДЫ — и это главный приём всего замера. Сортировка: обычной функцией и тотальной с топливом. НОД: обычной функцией и тотальной с объявленной мерой (убывает б), то есть со сторожем в рантайме. Одно и то же вычисление, одна и та же контрольная сумма, разница только в том, доказано ли завершение. Цена доказуемости тут не рассуждается — она вычитается.

Восемь сборок одной и той же программы. Разница между соседними и есть цена очередной вещи:

Вычёркивание сделано макросами в файле МОДУЛЯ, а не в рантайме: сам рантайм обязан собираться обычным, иначе в нём нечего было бы звать. Все восемь сборок обязаны дать одно и то же число на каждой задаче; харнесс это сверяет и объявляет замер недействительным при расхождении. Расхождений нет ни одного.

Тексты на Python (218 строк) и JavaScript (181) приложены целиком в конце страницы; текст на flang — 432 строки, эталон на C — 242.

Как мерили

Машина. AMD EPYC 7742, два сокета, 64 ядра на сокет, 256 логических процессоров, 499 ГиБ памяти, Linux 7.0.0-29-generic.

Версии.

Сколько кругов и что берётся. Время работы — медиана из 11 прогонов, полное время процесса. Время компиляции процессами — медиана из 5, слагаемые внутри процесса — из 7. Сборки и языки чередуются внутри каждого круга, а не меряются блоками: иначе всплеск нагрузки достался бы целиком одному участнику. Приводится медиана, а рядом минимум и максимум, а не среднее: одно попадание в чужой всплеск сдвигает среднее и не сдвигает медиану.

Два стенда. Машина общая. Под нагрузкой (средняя загрузка 100–190, чужие счётные задачи по 100–260 % ЦП каждая) размах между минимумом и максимумом доходит до 30 %, и разницу меньше 10 % такой замер различать не умеет. Замер работы, изъятия и арены снят на тихой машине: разброс 1–3 %. Приборы цены доказуемости читаются вычитанием соседних сборок, и абсолютные миллисекунды в их таблицах — с шумного стенда; вывод там опирается на разы, а не на проценты.

Полное время процесса, а не «чистый счёт». Разделять «запуск» и «счёт» здесь нечестно: у собранного бинарника запуск почти бесплатен, а у Python и Node он стоит заметных миллисекунд, и это их настоящее свойство. Пустая задача (запуститься и ничего не сделать) стоит: flang 5,4, эталон на C 4,1, Python 18,7, Node 40,5 мс.

Все числа — прогоны. В отчёте нет ни одной оценки. Там, где инструмента не оказалось, стоит «нет в системе», а не приблизительное значение.

Числа

Работа: где мы против Python, Node и C

Медиана из 11 прогонов, миллисекунды, полное время процесса. Столбец «сегодня» — дерево как есть; два левых показывают, что дали две правки, ставшие умолчанием.

Разброс «сегодня»: коллатц [131,4 … 145,6], нод [76,5 … 79,5], сортировка [174,6 … 183,1], строки [318,7 … 344,7], дерево [539,7 … 594,6].

По задачам против Python: коллатц 0,41, нод 0,63, сортировка 0,71, строки 0,77 — быстрее на четырёх из пяти. Дерево 2,02 остаётся медленнее вдвое, и причина не в проверках, а в ширине значения: узел варианта — это fl_variant (24 байта) плюс три fl_field по 40 байт = 144 байта на узел против 24 у структуры на C. Снимается это третьей правкой, которая не сделана.

Что дал каждый из двух вкладов

Флаг на двух задачах из пяти не дал ничего: НОД 0,98 и дерево 1,00 — обе цифры внутри разброса. Всё, что он дал, он дал на коллатце (1,51), сортировке (1,19) и строках (1,11).

Вторая правка — не «убрать проверку тега», а перестать звать ради неё функцию из другой единицы трансляции. Такой вызов берёт два значения по 32 байта, проверяет у обоих тег, делит два double, кладёт результат по указателю и возвращает статус; теперь тайпчекер кладёт выведенный тип отметкой на узел, а генератор печатает fl_number(a.as.number + b.as.number) прямо в выражении. На коллатце это 3,26 раза сверх -flto.

Изъятие: снять правку — замер обязан вернуться

Правило репозитория: правка, от снятия которой ничего не меняется, ничего и не держит. Проверено тремя сборками ОДНОЙ программы, чередующимися внутри круга, 9 кругов:

Снятие отметки возвращает коллатц ровно на уровень «только -flto» (411 против 396 в отдельном замере — разница внутри разброса). Ответы у всех трёх сборок на всех задачах одинаковы: по одному различному значению на задачу.

Компиляция: путь от исходника до работающей программы

Медиана из 5 прогонов, миллисекунды, полное время процесса.

Точки сравнения на той же машине, в том же чередовании:

Пустой запуск полезен как мера того, сколько стоит просто добраться до кода: наш flang check на самом маленьком файле — 123 мс, из них 40–50 мс — старт Node, на котором написан компилятор, и ещё около 50 мс — чтение 1,6 МиБ его собственных модулей (замерено пятью прогонами: 42, 54, 52, 59, 40 мс). То есть до первой полезной работы уходит около 100 мс, и от размера программы это не зависит вовсе.

Платим мы не за проверки, а за cc. На самом большом файле репозитория весь наш передний край — 1 197 мс, а сборка порождённого C — 16 996 мс. Мы — 7 % пути, компилятор C — 93 %. Почему так: 4 548 строк flang превращаются в 29 719 строк C (6,5 раза), и это не считая рантайма, который печатается к каждой программе целиком; у self/parser.flang — 4 336 строк flang → 31 486 строк C, 7,3 раза.

Из чего складываются эти 17 секунд — поштучным замером объектов:

Сумма — 12,7 с, а make -j4 в таблице выше дал медиану 17,0 с при разбросе [10,4 … 26,1]: поштучный замер сделан отдельно и лёг к нижнему краю разброса.

Наш C при этом дешевле обычного в пересчёте на строку: порождённый модуль — 0,39 мс/строку, рантайм — 0,38, а написанный руками reference.c — 1,32 (компиляция без линковки; сам запуск cc стоит 0,03 с). Порождённый код многословный, но простой: оптимизировать в нём почти нечего. Семнадцать секунд берутся из объёма, а не из сложности.

Из чего складывается передний край

Внутри одного процесса, медиана из 7 прогонов, миллисекунды. Первый прогон в процессе («холодный») стоит в 1,5–4 раза дороже — движок ещё не видел этого кода; для пользователя, который зовёт flang один раз, настоящее время именно холодное, и оно приведено отдельной строкой.

Доказательства не стоят почти ничего. На самом большом файле анализ тотальности, обязательства, ядро доказательств и законы вместе — 15,8 мс из 520 мс переднего края, то есть 3 %. А от полного пути до работающей программы (18 193 мс) это 0,09 %. Проверка предъявленных доказательств — 0,10 мс.

Дорого — разбор. Лексер плюс разбор плюс связывание (а связывание это тот же разбор, только импортированных файлов) — 286 мс из 520, 55 %. Дальше генератор кода — 115 мс, 22 %.

Постоянная часть генератора — 4 мс на любую программу. Это чтение рантайма (9 628 строк C) с диска и проверка его на сырые двунаправленные управляющие символы при каждом вызове. От размера программы не зависит.

Рост нелинейный, но умеренный: от 43 строк до 4 548 (в 106 раз) передний край вырос с 12 до 520 мс, то есть в 43 раза. По функциям — с 2 до 545 (272 раза) при том же росте времени в 43 раза.

Чем правки заплатили на сборке

На большом файле сборка стала вдвое быстрее, а не вдвое медленнее: с -flto шаг cc -c перестаёт оптимизировать и дешевеет, а оптимизация уезжает на компоновку, где gcc режет программу на разделы и обрабатывает их параллельно. На маленькой программе разделов один, и плата за компоновку видна. Поэтому флаг включён умолчанием; кому нужна быстрая сборка — make CFLAGS='-std=c99 -O2', и это написано в самом Makefile.

Вторая правка платит вторым проходом проверки типов на переднем крае: отметка кладётся по её выводу, а без неё этот проход почти всегда пропускается (арифметика есть почти в каждой программе, а частичные формы — редко). Замерено чередованием двух деревьев, 7 кругов, медиана полного времени процесса flang emit c:

Семнадцать миллисекунд на самом большом файле — против семнадцати секунд, которые на нём же тратит cc.

За сколько прогонов окупается компиляция

Сравнивать нашу компиляцию с запуском Python и Node в разах бессмысленно: у них её нет вовсе. Осмысленное сравнение — сколько прогонов нужно, чтобы разовая плата за компиляцию вернулась выигрышем в работе. Программа замера (432 строки) компилируется за 1 297 мс (emit 223 + make 1 074).

Против Node не окупается ни одна задача: на всех пяти Node остаётся быстрее — от −19 мс на НОД до −328 мс на дереве.

Пиковая память пяти задач

/usr/bin/time, максимальный резидентный размер, МиБ:

Где данных нет (коллатц, НОД), мы ровно на уровне C. Где данные есть — мы в 12 раз тяжелее Python на сортировке и в 16 раз на дереве. Это ширина значения: sizeof(fl_value) — 32 байта против 8 у double, узел варианта — 144 байта против 24. Ни одна из двух правок ширины не трогает, поэтому память ими и не менялась.

Арена: пик «Сортировки вставками» перестал расти

Взята «Сортировка вставками» из examples/rosetta/quicksort.flang — тотальная, доказанная структурно, написанная прямо, без единой хитрости, то есть не надуманный случай, а обычная программа на этом языке. Она же была самым тяжёлым числом этого замера: на 4 000 элементах она набирала 178 ГиБ и не досчитывала — процесс приходилось снимать, чтобы не уронить машину.

Область памяти на вызов сняла кубический рост, область на каждую свёртку — квадратичный. Обе печатает компилятор, то есть их получает любая программа, а не одна выбранная функция. Одиночные прогоны на тихой машине:

Ответы сверены md5sum и совпадают побайтово на обеих задачах. Пик перестаёт расти вовсе: на 4 000 он такой же, как на 250. Против того состояния, с которого начинался замер, — 178 ГиБ и снятый процесс — сегодня 8 МиБ и досчитанный ответ: в 22 785 раз меньше памяти там, где программа вообще не работала.

Откуда рост брался. «Сортировка вставками» — это свёртка ... как акк и эл → «Вставить по порядку» от эл и акк, и в напечатанном C она разворачивается в обычный цикл со строкой akk = fl_t13;. Область получала рекурсивная «Вставить по порядку» и не получала сама свёртка, поэтому каждый из n промежуточных накопителей длины 1…n перекладывался вниз, в арену свёртки, и лежал там до конца сортировки: живых значений n, мёртвых n²/2 − n. На 4 000 элементах это 4 тысячи живых и почти 8 миллионов мёртвых — 99,95 % пика. Теперь отметка снимается ОДИН раз перед циклом, и каждый виток закрывает область этой же отметкой, отдав вниз новый накопитель:

  fl_value akk = fl_list(NULL, 0);
  const fl_mark fl_svertka = fl_region_open(ctx);
  for (...) {
    FL_TRY(bystraya_sortirovka_vstavit_po_poryadku(ctx, el, akk, &fl_t13, error));
    akk = fl_t13;
    FL_TRY(fl_region_close(ctx, fl_svertka, FL_OK, &akk, error));  /* и заново взять границу */
  }

Законность: после akk = fl_t13 прежний накопитель не читает никто, а входной список и его элементы построены вызывающим и лежат НИЖЕ отметки. Ни чистота, ни тотальность при этом не трогаются: правило «переиспользовать только там, где доказано, что старое значение больше не читается» выполнено не догадкой, а видом цикла.

Время названо честно: по нему правка дороже, и вот чем. Откат витка копирует накопитель, а «Приписать в начало» теряет при этом хвостовой запас массива, и следующее «добавить» идёт на копию вместо записи на месте. Отсюда порог FL_REGION_LOOP_GAIN = 16 против FL_REGION_GAIN = 4 у области на вызов: накопление (добавить в накопитель, наросшее лишь вдвое больше живого) отказывается от отката по построению, а перестройка (новый накопитель на каждом витке, наросшее ≈ k²/2 при живых k) проходит с k ≈ 32. С равными бюджетами та же правка стоила 262 с на 4 000 — 1,74 раза вместо 1,37; порог вернул 55 секунд из 111, и остаток — цена самих копий. Если однажды окажется, что полтора раза по времени того не стоят, порог — одна строка: на 64 или 256 область на свёртке гаснет почти везде.

Сколько байт прибавила область к печати

Из +6 785 в рантайме кодом являются около 900 байт; остальное — объяснение довода законности над fl_region_recycle.

Цена доказуемости 1: счётчик шагов, счётчик глубины, сторож стека

Это то, без чего объявленные пределы (FLANG_RECURSION_LIMIT) перестали бы быть пределами. Вычеркнуто тремя способами — от «не считать» до «убрать вызовы целиком»:

Разница между первым и последним столбцом — 0,9 … 8,9 %, и она целиком внутри разброса. Что это именно шум, видно по двум местам, где вычёркивание работы сделало программу МЕДЛЕННЕЕ: на коллатце сборка с выключенным счётом дала 652 мс против 641 у базовой, на сортировке сборка с вычеркнутым fl_tick — 348 против

1. Физически такого быть не может; значит и разницы в другую сторону этот прибор

на таких величинах не различает.

Доля в превышении над написанным руками C:

Счётчики стоят неотличимо от нуля. Убирать их не надо: выигрыш был бы нулевой, а держат они объявленный предел, без которого напечатанная программа падала бы по SIGSEGV вместо FLANG_RECURSION_LIMIT.

Отдельная заметка. Счётчик шагов нужен обычным функциям: они вправе не завершаться, и без него напечатанная программа крутилась бы вечно. У тотальной функции завершение доказано, и счётчик там логически избыточен — но fl_tick печатается ей ровно так же (в программе замера его несут и «Через один», и «Слить с топливом», обе доказанные). Это несогласованность, а не расход: убрать её значит выиграть ноль. «Доказано, а всё равно проверяем» — единственное такое место, найденное замером, и оно ничего не стоит.

Цена доказуемости 2: сторож объявленной меры

Единственное место, где доказательство оставляет настоящий след внутри работающей программы. Автор пишет убывает б, и компилятор ставит на каждый рекурсивный вызов проверку: мера строго убыла, не ушла ниже нуля, осталась целой. Один и тот же Евклид, записанный дважды: доказанный НОД — 238,2 мс против 78,6 у обычного, то есть в 3,03 раза дороже. До двух правок было 448,2 против 149,6 — 3,00 раза: обе записи ускорились одинаково, доля сторожа не изменилась.

Это честная цена, а не изъян: без сторожа тотальная на IEEE-754 была бы ложным обещанием (остатки пары (φ, 1) не кончаются никогда), и сторож переводит ложь в отказ FLANG_MEASURE. Но цена именно такая, и её надо знать.

Цена доказуемости 3: приём «топливо»

Сортировка слиянием, записанная обычной функцией и тотальной с топливом. Тот же алгоритм, тот же ответ:

Топливо здесь — не украшение подписи: доказанная запись на каждом уровне склеивает две половины в список-топливо для слияния, и это лишний проход по всем данным.

Насколько доказуемость распространена в корпусе

Свод по корпусу: 162 файла, 2 799 функций.

Параметр-топливо встречается в корпусе у 5 функций (fibonacci, 704-binary-search, primes-by-trial-division и две в merge-sort).

Итого 71 функция из 2 799 — 2,5 % платит за доказуемость что-то измеримое. Остальные 97,5 % платят счётчиками, а те неотличимы от нуля. По компиляции доказательства стоят 3 % переднего края и 0,09 % полного пути. Всё прочее отставание — недоделанность, а не цена гарантий: ни одно обещание языка от ширины fl_value не зависит.

Чем это ограничено

• tsc не измерен и не оценён. В системе его нет. Ставить TypeScript ради замера значило бы мерить не ту машину, на которой всё остальное; сказать «примерно столько же, сколько…» значило бы выдать догадку за прогон.
• Разницу меньше 10 % шумный стенд не различает. Размах между минимумом и максимумом доходит там до 30 % — например, у «дерева» flang дал [643 … 963]. Поэтому выводы говорят о разах, а не о процентах.
• Окупаемость посчитана в невыгодную для нас сторону. 1 297 мс — это компиляция всего файла с пятью задачами сразу, а не одной из них. Отдельная задача компилировалась бы дешевле.
• Таблица слагаемых переднего края завышена, и обе оговорки в нашу невыгоду. Харнесс разбирает исходник дважды: один раз чтобы показать цену разбора, второй — чтобы собрать программу для остальных шагов; на self/types.flang это лишние 48 мс из 520. И строка «всего» — время внутри уже запущенного процесса: процесс целиком (flang emit c = 1 197 мс) добавляет к нему старт, чтение модулей компилятора и запись 2 МиБ файлов на диск.
• Проверку тега снять совсем нельзя, и это выяснилось прогоном корпуса. Граница входа сверяет не всё — вид неизвестно (параметр полиморфизма и значение-функция) она пропускает, потому что сверять его не с чем. Через эту дверь чужое значение доезжает до доказанного места: «Отобразить» от Удвоить и [1, "два"] со снятой проверкой отвечало 1.32e-309 вместо отказа FLANG_TYPE — то есть отказ менялся на неверный ответ. Поэтому снят не тег, а межмодульный вызов: сверка печатается одним if в теле вызывающего. Цена честности измерена: коллатц 132,5 мс вместо 121,6 без сверки — 9 %, и 2 % по геометрическому среднему.
• Ширина значения не сделана. sizeof(fl_value) = 32 байта при 8 у double; узел варианта с тремя полями — 144 байта при 24 у структуры C. Отсюда дерево вдвое медленнее Python и 12–16-кратная память. Это перестройка представления, а не правка, и оценивать её числом строк было бы враньём.
• Область памяти дана не всем, кому нужна. отобразить и отфильтровать печатаются рядом со свёрткой, но накопителя у них нет, и выигрыш там не измерен. Признак, по которому область даётся, — «функция рекурсивна», а нужен «тело выделяет»: обычная функция, склеивающая большие списки в цикле, области не получает. Замена признака — анализ на 150–250 строк плюс замер, что область не начала стоить дороже, чем экономит, на корпусе из 234 программ.

Как повторить

Раздел для тех, кто развивает язык. Команды ниже — команды репозитория, а не языка: они зовут харнессы замера прямо из дерева исходников. Тому, кто языком пользуется, ничего из этого не нужно.

Все скрипты лежат в benchmarks/speed/. Ни один не трогает репозиторий: всё собирается в указанный каталог.

# 1. Собрать восемь вариантов одной программы плюс эталон на C
benchmarks/speed/assemble.sh /tmp/zamer

# 2. Время работы: пять задач, восемь сборок, чередование, 11 кругов
node benchmarks/speed/work.mjs /tmp/zamer --кругов 11

# 3. Пиковая память тех же задач.
#    Замер написан планом на flang, и каталог сборки назван в нём числом —
#    «.sborka» рядом с планом, — потому что доводов у плана нет. Готовится он
#    тем же assemble.sh, запущенным без довода.
benchmarks/speed/assemble.sh
bootstrap/flang io benchmarks/speed/memory.flang

# 4. Рост арены на «Сортировке вставками» (с пределом адресного пространства)
mkdir -p /tmp/zamer/qs
bootstrap/flang emit examples/rosetta/quicksort.flang \
  --target c --out /tmp/zamer/qs --max-steps 2000000000
make -C /tmp/zamer/qs -j4
benchmarks/speed/arena.sh /tmp/zamer/qs

# 5. Время компиляции: итоги процессами, вместе с точками сравнения
node benchmarks/speed/kompilyaciya.mjs --кругов 5

# 6. Время компиляции: слагаемые внутри одного процесса
node benchmarks/speed/faz.mjs flang/self/types.flang --повторов 7

# 7. Свод по корпусу: чем несётся обещание «тотальная» и где сторожа
./ярлык доказательства:ведомость

Разовая проба одной задачи на трёх языках, с временем и памятью:

benchmarks/speed/probe.sh /tmp/zamer/base/flang_cli "Обход дерева" дерево 100000

Перед node в ручных прогонах ставьте LC_ALL=C.UTF-8 — имена задач записаны кириллицей, и без этого аргументы приезжают побитыми. Харнессы ставят её сами.

Приложение: тексты на Python и JavaScript

Приложены целиком, чтобы сравнение можно было проверить, а не принять на веру. Текст на flang — benchmarks/speed/programs/tasks.flang (432 строки), эталон на C — benchmarks/speed/programs/reference.c (242 строки).

tasks.py

# SPDX-FileCopyrightText: 2026 Digitable (Marat Zimnurov)
# SPDX-License-Identifier: BSD-2-Clause
"""Те же четыре задачи, что в tasks.flang, на Python 3.

Правило перевода — шаг в шаг:
  • где flang печатается в цикл (хвостовой самовызов) — здесь цикл;
  • где flang рекурсирует по-настоящему — здесь рекурсия;
  • никаких библиотечных сокращений: ни sorted(), ни срезов вида lst[0::2].
    Разрешены ровно те встроенные формы, которые есть и у flang: разделение
    строки (str.split ↔ «разделить … по …») и перевод строки в число
    (int ↔ «к числу»).

Запуск:  python3 tasks.py ЗАДАЧА РАЗМЕР
         python3 tasks.py коллатц 20000
Печатает одно число — ту же контрольную сумму, что и остальные два языка.
"""
import sys

A = 25173
C = 13849
M = 65536


def chisla(skolko, zerno):
    """«Числа»: хвостовой самовызов — значит цикл."""
    out = []
    x = zerno
    for _ in range(skolko):
        x = (A * x + C) % M
        out.append(x)
    return out


def otpechatok(elementy):
    """«Отпечаток»: свёртка."""
    acc = 0
    for e in elementy:
        acc = (acc * 31 + e) % 1000003
    return acc


# ── задача 1: счёт на числах ────────────────────────────────────────────────


def shagov_kollatca(n):
    """«Шагов Коллатца»: хвостовой самовызов — цикл."""
    nabrano = 0
    while n > 1:
        n = n // 2 if n % 2 == 0 else 3 * n + 1
        nabrano += 1
    return nabrano


def kollatc(predel):
    """«Сумма Коллатца»: тоже хвостовой, но вызов внутрь — настоящий."""
    summa = 0
    tekushchee = 1
    while tekushchee <= predel:
        summa += shagov_kollatca(tekushchee)
        tekushchee += 1
    return summa


# ── задача 1-бис: НОД ───────────────────────────────────────────────────────
# У flang эта задача записана дважды — с объявленной мерой (и сторожем в
# рантайме) и без неё. Здесь запись одна: понятия «доказано» у Python нет, и
# изображать его было бы подлогом. Ответ у всех записей один.


def nod(a, b):
    while b != 0:
        a, b = b, a % b
    return a


def nod_zadacha(predel):
    summa = 0
    tekushchee = 1
    while tekushchee <= predel:
        summa += nod(tekushchee, 40902)
        tekushchee += 1
    return summa


# ── задача 2: сортировка слиянием ───────────────────────────────────────────


def cherez_odin(elementy, s):
    """«Через один»: каждый второй, начиная с позиции s."""
    out = []
    i = s
    n = len(elementy)
    while i < n:
        out.append(elementy[i])
        i += 2
    return out


def sliyanie(pervyy, vtoroy):
    """«Слияние»: хвостовой самовызов — цикл с двумя указателями."""
    out = []
    i = 0
    j = 0
    n = len(pervyy)
    m = len(vtoroy)
    while i < n and j < m:
        if pervyy[i] <= vtoroy[j]:
            out.append(pervyy[i])
            i += 1
        else:
            out.append(vtoroy[j])
            j += 1
    while i < n:
        out.append(pervyy[i])
        i += 1
    while j < m:
        out.append(vtoroy[j])
        j += 1
    return out


def sortirovka(elementy):
    """«Сортировка»: рекурсия настоящая — значит и здесь рекурсия."""
    if len(elementy) <= 1:
        return elementy
    levaya = cherez_odin(elementy, 0)
    pravaya = cherez_odin(elementy, 1)
    return sliyanie(sortirovka(levaya), sortirovka(pravaya))


# ── задача 3: обход дерева ──────────────────────────────────────────────────
# Лист — None, узел — кортеж (ключ, слева, справа). Значения неизменяемы, как
# у flang: вставка переписывает путь и возвращает новое дерево.


def vstavit(derevo, novyy):
    if derevo is None:
        return (novyy, None, None)
    kl, l, p = derevo
    if novyy < kl:
        return (kl, vstavit(l, novyy), p)
    return (kl, l, vstavit(p, novyy))


def sobrat_derevo(skolko, zerno):
    derevo = None
    x = zerno
    for _ in range(skolko):
        x = (A * x + C) % M
        derevo = vstavit(derevo, x)
    return derevo


def summa_dereva(derevo):
    if derevo is None:
        return 0
    kl, l, p = derevo
    return (kl + summa_dereva(l)) + summa_dereva(p)


def glubina_dereva(derevo):
    if derevo is None:
        return 0
    _, l, p = derevo
    gl = glubina_dereva(l)
    gp = glubina_dereva(p)
    return (gl if gl > gp else gp) + 1


def obhod_dereva(skolko):
    derevo = sobrat_derevo(skolko, 12345)
    return summa_dereva(derevo) + 1000000 * glubina_dereva(derevo)


# ── задача 4: разбор строк ──────────────────────────────────────────────────


def udvoit_tekst(tekst, raz):
    for _ in range(raz):
        tekst = tekst + "," + tekst
    return tekst


def razbor_strok(raz):
    tekst = udvoit_tekst("17,42,8,99,3,71,25,60,14,88", raz)
    acc = 0
    for kusok in tekst.split(","):
        acc = (acc * 31 + int(kusok)) % 1000003
    return acc


# ── точки входа ─────────────────────────────────────────────────────────────


def sortirovka_zadacha(skolko):
    return otpechatok(sortirovka(chisla(skolko, 12345)))


ZADACHI = {
    "коллатц": kollatc,
    "нод": nod_zadacha,
    "сортировка": sortirovka_zadacha,
    "дерево": obhod_dereva,
    "строки": razbor_strok,
}


def main(argv):
    if len(argv) != 3 or argv[1] not in ZADACHI:
        sys.stderr.write("использование: tasks.py {%s} РАЗМЕР\n" % "|".join(ZADACHI))
        return 2
    sys.setrecursionlimit(200000)
    sys.stdout.write("%d\n" % ZADACHI[argv[1]](int(argv[2])))
    return 0


if __name__ == "__main__":
    sys.exit(main(sys.argv))

tasks.mjs

/* SPDX-FileCopyrightText: 2026 Digitable (Marat Zimnurov) */
/* SPDX-License-Identifier: BSD-2-Clause */
/**
 * Те же четыре задачи, что в tasks.flang, на JavaScript (Node.js).
 *
 * Правило перевода — шаг в шаг, как и у tasks.py:
 *   • где flang печатается в цикл (хвостовой самовызов) — здесь цикл;
 *   • где flang рекурсирует по-настоящему — здесь рекурсия;
 *   • никаких библиотечных сокращений: ни Array.prototype.sort, ни filter по
 *     индексу. Разрешены ровно те встроенные формы, которые есть и у flang:
 *     String.prototype.split (↔ «разделить … по …») и Number (↔ «к числу»).
 *
 * Запуск:  LC_ALL=C.UTF-8 node tasks.mjs ЗАДАЧА РАЗМЕР
 * Печатает одно число — ту же контрольную сумму, что и остальные два языка.
 */
const A = 25173
const C = 13849
const M = 65536

function chisla(skolko, zerno) {
  const out = []
  let x = zerno
  for (let i = 0; i < skolko; i += 1) {
    x = (A * x + C) % M
    out.push(x)
  }
  return out
}

function otpechatok(elementy) {
  let acc = 0
  for (const e of elementy) acc = (acc * 31 + e) % 1000003
  return acc
}

/* ── задача 1: счёт на числах ─────────────────────────────────────────────── */

function shagovKollatca(n) {
  let nabrano = 0
  while (n > 1) {
    n = n % 2 === 0 ? n / 2 : 3 * n + 1
    nabrano += 1
  }
  return nabrano
}

function kollatc(predel) {
  let summa = 0
  for (let tekushchee = 1; tekushchee <= predel; tekushchee += 1) {
    summa += shagovKollatca(tekushchee)
  }
  return summa
}

/* ── задача 1-бис: НОД ────────────────────────────────────────────────────── */
/* У flang эта задача записана дважды — с объявленной мерой (и сторожем в
   рантайме) и без неё. Здесь запись одна: понятия «доказано» у JavaScript нет,
   и изображать его было бы подлогом. Ответ у всех записей один. */

function nod(a, b) {
  while (b !== 0) {
    const ost = a % b
    a = b
    b = ost
  }
  return a
}

function nodZadacha(predel) {
  let summa = 0
  for (let tekushchee = 1; tekushchee <= predel; tekushchee += 1) summa += nod(tekushchee, 40902)
  return summa
}

/* ── задача 2: сортировка слиянием ────────────────────────────────────────── */

function cherezOdin(elementy, s) {
  const out = []
  for (let i = s; i < elementy.length; i += 2) out.push(elementy[i])
  return out
}

function sliyanie(pervyy, vtoroy) {
  const out = []
  let i = 0
  let j = 0
  while (i < pervyy.length && j < vtoroy.length) {
    if (pervyy[i] <= vtoroy[j]) {
      out.push(pervyy[i])
      i += 1
    } else {
      out.push(vtoroy[j])
      j += 1
    }
  }
  while (i < pervyy.length) {
    out.push(pervyy[i])
    i += 1
  }
  while (j < vtoroy.length) {
    out.push(vtoroy[j])
    j += 1
  }
  return out
}

function sortirovka(elementy) {
  if (elementy.length <= 1) return elementy
  const levaya = cherezOdin(elementy, 0)
  const pravaya = cherezOdin(elementy, 1)
  return sliyanie(sortirovka(levaya), sortirovka(pravaya))
}

/* ── задача 3: обход дерева ───────────────────────────────────────────────── */
/* Лист — null, узел — массив [ключ, слева, справа]. Значения не правятся:
   вставка переписывает путь и возвращает новое дерево, как у flang. */

function vstavit(derevo, novyy) {
  if (derevo === null) return [novyy, null, null]
  const [kl, l, p] = derevo
  if (novyy < kl) return [kl, vstavit(l, novyy), p]
  return [kl, l, vstavit(p, novyy)]
}

function sobratDerevo(skolko, zerno) {
  let derevo = null
  let x = zerno
  for (let i = 0; i < skolko; i += 1) {
    x = (A * x + C) % M
    derevo = vstavit(derevo, x)
  }
  return derevo
}

function summaDereva(derevo) {
  if (derevo === null) return 0
  return derevo[0] + summaDereva(derevo[1]) + summaDereva(derevo[2])
}

function glubinaDereva(derevo) {
  if (derevo === null) return 0
  const gl = glubinaDereva(derevo[1])
  const gp = glubinaDereva(derevo[2])
  return (gl > gp ? gl : gp) + 1
}

function obhodDereva(skolko) {
  const derevo = sobratDerevo(skolko, 12345)
  return summaDereva(derevo) + 1000000 * glubinaDereva(derevo)
}

/* ── задача 4: разбор строк ───────────────────────────────────────────────── */

function udvoitTekst(tekst, raz) {
  for (let i = 0; i < raz; i += 1) tekst = tekst + "," + tekst
  return tekst
}

function razborStrok(raz) {
  const tekst = udvoitTekst("17,42,8,99,3,71,25,60,14,88", raz)
  let acc = 0
  for (const kusok of tekst.split(",")) acc = (acc * 31 + Number(kusok)) % 1000003
  return acc
}

/* ── точки входа ──────────────────────────────────────────────────────────── */

const ZADACHI = {
  "коллатц": kollatc,
  "нод": nodZadacha,
  "сортировка": (skolko) => otpechatok(sortirovka(chisla(skolko, 12345))),
  "дерево": obhodDereva,
  "строки": razborStrok,
}

const [, , zadacha, razmer] = process.argv
if (zadacha === undefined || ZADACHI[zadacha] === undefined) {
  process.stderr.write(`использование: node tasks.mjs {${Object.keys(ZADACHI).join("|")}} РАЗМЕР\n`)
  process.exit(2)
}
process.stdout.write(`${ZADACHI[zadacha](Number(razmer))}\n`)