Почему нет принудительного TCO?
От: cppguard  
Дата: 11.02.22 00:28
Оценка:
Off-top mode on. Начиная с С++17 добавляют всякую ненужную дичь. Давече прочитал про грядущие нововведения С++23 — прям "ооочень нужные штуки", как мы жили без них? Складывается ощущение, что в коммитете просто каждый пытается оптимизировать свои алгоритмы: Гугл — свой Хром, Яндекс — свои микросервисы, ну и остальные до кучи. Потому как мне непонятно, зачем вводить коды возврата, а пару стандартов позже ещё что-то выдумывать (речь про std::expected)?

Но это всё брюзжание. Интересно следующие — почему не вводят конструкцию, которая бы позволила гарантировать tail call optimization? То есть пишешь, что-то вроде
unsigned factorial(unsigned n) {
  if (n)
    [[force-tco]] return n * factorial(n - 1);
  else
    return 1;
}

и если TCO не удаётся по каким-то причинам, то это становится ошибкой компиляции. Ведь тогда бы можно было писать на С++ как на Лиспе! Код бы стал лаконичнее и безопаснее. А что вы думаете?
Re: Почему нет принудительного TCO?
От: reversecode google
Дата: 11.02.22 00:38
Оценка: +1
компилятор и так его делает везде где может сделать
Re: Почему нет принудительного TCO?
От: LaptevVV Россия  
Дата: 11.02.22 01:11
Оценка:
C>Off-top mode on. Начиная с С++17 добавляют всякую ненужную дичь. Давече прочитал про грядущие нововведения С++23 — прям "ооочень нужные штуки", как мы жили без них? Складывается ощущение, что в коммитете просто каждый пытается оптимизировать свои алгоритмы: Гугл — свой Хром, Яндекс — свои микросервисы, ну и остальные до кучи. Потому как мне непонятно, зачем вводить коды возврата, а пару стандартов позже ещё что-то выдумывать (речь про std::expected)?
Столяров комитет обозвал так: банда международных террористов, по недоразумению называющаяся комитетом по стандартизации...

C>Но это всё брюзжание. Интересно следующие — почему не вводят конструкцию, которая бы позволила гарантировать tail call optimization?

C>и если TCO не удаётся по каким-то причинам, то это становится ошибкой компиляции. Ведь тогда бы можно было писать на С++ как на Лиспе! Код бы стал лаконичнее и безопаснее. А что вы думаете?
да оно и так делается по умолчанию
Хочешь писать как на Лиспе — почитай книгу Ивана Чукича Функциональное программирование на С++
Хочешь быть счастливым — будь им!
Без булдырабыз!!!
Re[2]: Почему нет принудительного TCO?
От: cppguard  
Дата: 11.02.22 02:24
Оценка:
Здравствуйте, reversecode, Вы писали:

R>компилятор и так его делает везде где может сделать


Но ведь вопрос не в этом! А в том, чтобы гарантировать такую оптимизацию и гарантироваано не взрывать стек.
Re: Почему нет принудительного TCO?
От: netch80 Украина http://netch80.dreamwidth.org/
Дата: 11.02.22 07:49
Оценка: 7 (1)
Здравствуйте, cppguard, Вы писали:

C>Но это всё брюзжание. Интересно следующие — почему не вводят конструкцию, которая бы позволила гарантировать tail call optimization?


Основной вопрос — в каких пределах в C++ и в каких случаях это полезно.
IMO, поскольку язык процедурный, все существенные случаи могут быть свёрнуты в цикл.
Это, наверно, не так, если TCO делается не из одной функции (ваш пример с факториалом в этом смысле ужасен), а хотя бы в двух (f вызывает g, g — f), а ещё лучше в большем количестве.

Из моего опыта с Erlang (где tail call единственный способ организовать цикл) — наоборот, рекурсия с хвостовыми вызовами имеет проблемы. У меня был случай, когда надо было отрабатывать с полсотни параметров, устанавливаемых через дерево конфигурации (потомок может переопределять параметры из предка), вычисление становилось чем-то вроде:

for (i = 1; i <= currdepth; ++i) {
  foo = params[i].foo ?? foo
  bar = params[i].bar ?? bar
  ...
}


В цикле это всё в одном фрейме, а в рекурсии придётся как минимум передавать структуру по указателю, а как максимум мапу или пучок отдельных переменных... громоздкое (tm).

C>и если TCO не удаётся по каким-то причинам, то это становится ошибкой компиляции. Ведь тогда бы можно было писать на С++ как на Лиспе! Код бы стал лаконичнее и безопаснее. А что вы думаете?


Не вижу причин однозначно утверждать ни про лаконичность, ни про безопасность. Зато есть причины думать наоборот.
The God is real, unless declared integer.
Re: Почему нет принудительного TCO?
От: Alexander G Украина  
Дата: 11.02.22 08:15
Оценка:
Здравствуйте, cppguard, Вы писали:

C>Off-top mode on. Начиная с С++17 добавляют всякую ненужную дичь. Давече прочитал про грядущие нововведения С++23 — прям "ооочень нужные штуки", как мы жили без них? Складывается ощущение, что в коммитете просто каждый пытается оптимизировать свои алгоритмы: Гугл — свой Хром, Яндекс — свои микросервисы, ну и остальные до кучи. Потому как мне непонятно, зачем вводить коды возврата, а пару стандартов позже ещё что-то выдумывать (речь про std::expected)?


Ровно по той же логике, что и tail call optimization. Сделать можно, кому-то нужно, где-то не в С++ уже есть — значит имеет смысл.
Лично мне std::expected и некоторые другие добавления в С++23 полезнее обязательного tail call optimization.

C>и если TCO не удаётся по каким-то причинам, то это становится ошибкой компиляции. Ведь тогда бы можно было писать на С++ как на Лиспе! Код бы стал лаконичнее и безопаснее. А что вы думаете?


Можно писать пропозл, чо.

Легальность и в некоторых случая обязательность return value optimization и не-привествование std::move на return value уже даёт некоторую почву -- много где оно уже работает, пусть и без требования.

Есть некоторая сложность с тем, что стандарт не говорит про то, что вообще обязательно есть stack, даже несмотря на stack unwinding при исключениях и std::stacktrace из C++23, но дело поправимое.

Есть проблема с тем, что если аттрибуты не поддерживаются вообще, они должны игнорироваться реализацией. Ну тут спасает feature test macro.

Ещё сейчас компиляторы не всегда могут сгенерировть настолько оптимальный код для оптимизированных хвостовых вызовов, как для изначально циклов. Ну то QoI во-первых, во-вторых тоже дело поправимое.


Видимо на самом деле не так уж оно и нужно, если такого пропозла не было.
Русский военный корабль идёт ко дну!
Re[2]: Почему нет принудительного TCO?
От: sergii.p  
Дата: 11.02.22 08:32
Оценка: +1
Здравствуйте, LaptevVV, Вы писали:

LVV>Хочешь писать как на Лиспе — почитай книгу Ивана Чукича Функциональное программирование на С++


тот же Чукич пишет, что TCO никем и ничем не гарантируется. То есть вообще-то так писать нельзя. Я сам недавно столкнулся с тем, что рванул стек. В релизе нормально, в дебаге падает. Когда у вас дебаг-версия не работает это как бы не очень хорошо.
Re[2]: Почему нет принудительного TCO?
От: cppguard  
Дата: 11.02.22 08:51
Оценка:
Здравствуйте, Alexander G, Вы писали:

AG>Легальность и в некоторых случая обязательность return value optimization и не-привествование std::move на return value уже даёт некоторую почву -- много где оно уже работает, пусть и без требования.


Я говорю про то, что можно гарантировать, типа copy-ellision (хотя, не совсем верный пример). То,что разные оптимизации существуют, это хорошо. Но рекурсивные алгоритмы без гарантии TCO гарантированно взорвут стек.

AG>Есть некоторая сложность с тем, что стандарт не говорит про то, что вообще обязательно есть stack, даже несмотря на stack unwinding при исключениях и std::stacktrace из C++23, но дело поправимое.


Вот за это люблю С++: на одном ресурсе обсуждаешь что-то из стандарта, и тебе говорят про необязательное существование стека (я бы очень хотел взглянуть на эти платформы), обсуждаешь на другом, и там тебе говорят, что proposal оптимизирован для x86-64, чтобы всё весело влезало в свободные регистры. Истина, как всегда, is out there.

AG>Видимо на самом деле не так уж оно и нужно, если такого пропозла не было.


А джаваскриптопитонячий std::any прям вот всем позарез нужен? Или это для тех, кто написал первую версию на питоне и потом такой: "сейчас перепишем на С++, всё летать будет!". Я, кстати, прямо сейчас работаю над проектом, который с Java на С++ именно с такой мотивацией переписали Или другой пример: в Java есть Map::computeIfAbsent, который очень удобен для написания branch-less кода, а в С++ можно соснуть петушок на палочке, но зато есть emplace, insert, try_insert, try_emplace — на любой вкус и лад =) Как я уже написал, я считаю, что большинство членов коммитета тащат в стандарт то, что нужно их компаниям, а не то, что нужно среднему программисту по палате.
Re[2]: Почему нет принудительного TCO?
От: cppguard  
Дата: 11.02.22 08:58
Оценка:
Здравствуйте, netch80, Вы писали:

N>Основной вопрос — в каких пределах в C++ и в каких случаях это полезно.

N>IMO, поскольку язык процедурный, все существенные случаи могут быть свёрнуты в цикл.
N>Это, наверно, не так, если TCO делается не из одной функции (ваш пример с факториалом в этом смысле ужасен), а хотя бы в двух (f вызывает g, g — f), а ещё лучше в большем количестве.

N>Из моего опыта с Erlang (где tail call единственный способ организовать цикл) — наоборот, рекурсия с хвостовыми вызовами имеет проблемы. У меня был случай, когда надо было отрабатывать с полсотни параметров, устанавливаемых через дерево конфигурации (потомок может переопределять параметры из предка), вычисление становилось чем-то вроде:


N>
N>for (i = 1; i <= currdepth; ++i) {
N>  foo = params[i].foo ?? foo
N>  bar = params[i].bar ?? bar
N>  ...
N>}
N>


N>В цикле это всё в одном фрейме, а в рекурсии придётся как минимум передавать структуру по указателю, а как максимум мапу или пучок отдельных переменных... громоздкое (tm).


В данном конкретном случае вы просто бы не пользовались этой возможностью

N>Не вижу причин однозначно утверждать ни про лаконичность, ни про безопасность. Зато есть причины думать наоборот.


Лишние переменные для обновления состояния. В рекурсивном коде их нет. А вообще пример навеян размышлениями над этим постом https://rsdn.org/forum/cpp.applied/8185323.1
Автор: cppguard
Дата: 01.02.22
. Если написать поиск по дереву рекурсивно, то проблема с удалённым конструктором копирования unique_ptr исчезает. Да и даже если убрать unique_ptr вообще, то мы не можем изменять переменную ссылочного типа, поэтому придётся заворачивать её в новый класс или что-то выдумывать.
Re[3]: Почему нет принудительного TCO?
От: Alexander G Украина  
Дата: 11.02.22 09:06
Оценка:
Здравствуйте, cppguard, Вы писали:

C>Вот за это люблю С++: на одном ресурсе обсуждаешь что-то из стандарта, и тебе говорят про необязательное существование стека (я бы очень хотел взглянуть на эти платформы), обсуждаешь на другом, и там тебе говорят, что proposal оптимизирован для x86-64, чтобы всё весело влезало в свободные регистры.


Одно другому не противоречит. В основном C++ нацелен на перформанс реальных платформах (откуда взялся тот же std::hardware_constructive_interference_size), но нереальные тоже как бы поддерживаются (emscripten как пример)

И да, я не говорю что "отсуствие" стека — блокер, можно определить, если надо. Обязали же в C++20 two's complement, ну и тут можно тоже стать ближе к железу.

C>А джаваскриптопитонячий std::any прям вот всем позарез нужен? Или это для тех, кто написал первую версию на питоне и потом такой: "сейчас перепишем на С++, всё летать будет!". Я, кстати, прямо сейчас работаю над проектом, который с Java на С++ именно с такой мотивацией переписали Или другой пример: в Java есть Map::computeIfAbsent, который очень удобен для написания branch-less кода, а в С++ можно соснуть петушок на палочке, но зато есть emplace, insert, try_insert, try_emplace — на любой вкус и лад =) Как я уже написал, я считаю, что большинство членов коммитета тащат в стандарт то, что нужно их компаниям, а не то, что нужно среднему программисту по палате.


"Большинство С++ программистов не знает, чем занимается большинство С++ программистов"

Я думаю, что нет никаких "средних программистов по палате".
Мне any не очень нужен, но computeIfAbsent тоже не нужен
(в моём мире branch-less код — это без машинных инструкций перехода, соотвественно, computeIfAbsent к нему отношения не имеет)
Русский военный корабль идёт ко дну!
Re[3]: Почему нет принудительного TCO?
От: saf_e  
Дата: 11.02.22 09:12
Оценка:
Здравствуйте, cppguard, Вы писали:

C>в Java есть Map::computeIfAbsent


Я правильно понимаю что смысл этой ф-ции (условно)?:
V computeIfAbsent(K, func<V (F)>)
{
  auto it = find(F);
  if(it == end())
      it = insert(K, func(K));
  
 return it->V;
}
Re[3]: Почему нет принудительного TCO?
От: netch80 Украина http://netch80.dreamwidth.org/
Дата: 11.02.22 09:54
Оценка: 7 (1)
Здравствуйте, cppguard, Вы писали:

C>Вот за это люблю С++: на одном ресурсе обсуждаешь что-то из стандарта, и тебе говорят про необязательное существование стека (я бы очень хотел взглянуть на эти платформы),


Тут может быть два разных случая:

1. Стека формально нет в архитектуре, но нет проблем его сэмулировать для языка типа C/C++.
Это, например, обыкновеннейшая System/Z, потомок IBM 360. Стек для C и других подобных эмулируется через регистр 15.
Это новомодный RISC-V. Тоже, стек существует только в рамках соглашения (x2 — указатель стека, x1 — регистр адреса возврата), ну и сжатые инструкции и хинты реализации заточены под это (хотите другие — не пользуйтесь сжатыми и будете иметь проблемы секьюрити, где они есть).

2. Стека нет в архитектуре и ресурсы не позволяют сэмулировать его. Это вообще исключает рекурсию.

Из опыта — такое было в той же IBM 360 на ранних этапах. Области сохранения данных, если нужно, размещались рядом с функциями (подпрограммами). Сейчас это возможно на супермелких платформах (уровня AVR или ниже).

-----

Живой пример на первое. Берём код (что-то такое чтобы не влезало в регистры):

#include <stdio.h>
struct result { int x, y, z; };
struct result moo(int a, int b, int c, int d, int e, int f, int g, int h) {
  struct result r;
  r.x = a*b + c*d + e*f + g*h; r.y = a*c + b*d + e*g + f*h;
  r.z = a*e + b*f + c*g + d*h;
  printf("x=%d y=%d z=%d\n", r.x, r.y, r.z); return r;
}


Просим ассемблер (запускается на убунте на стандартном десктопе): /usr/bin/s390x-linux-gnu-gcc-9 -S -O t01.c

Смотрим выхлоп (урезаю кучу вычислений и комментирую)

moo:
        ; сохранили callee-saved регистры (включая адрес возврата) скопом в стеке
        stmg    %r6,%r15,48(%r15)
        lay     %r15,-160(%r15) ; зарезервировали 160 байт в стеке
        lgr     %r8,%r2 ; адрес структуры возврата - первый скрытый аргумент
        lr      %r9,%r3 ; a
        msr     %r9,%r4 ; b
        lr      %r1,%r5 ; c
        msr     %r1,%r6 ; d
        ar      %r9,%r1
        l       %r1,324(%r15) ; e (уже не влез в первые 6 регистров, лежит в стеке)
        ms      %r1,332(%r15) ; f (аналогично)
...
        ; вызвали printf(), адрес возврата помещён в r14 (не на стек, это вам не x86)
        brasl   %r14,__printf_chk@PLT
...
        lmg     %r6,%r15,208(%r15) ; восстановили регистры скопом
        br      %r14 ; BR 14 - древний мем, все давно забыли


Но это всё ещё позволяет рекурсию, конечно. Просто для иллюстрации, что стека тут в явном виде нет
(ничто не мешало r15 применить под что угодно другое).

Как это влияет на системное программирование — отдельный разговор — могу описать, если интересно.
The God is real, unless declared integer.
Отредактировано 11.02.2022 11:36 netch80 . Предыдущая версия .
Re[4]: Почему нет принудительного TCO?
От: cppguard  
Дата: 11.02.22 10:01
Оценка:
Здравствуйте, saf_e, Вы писали:

_>Здравствуйте, cppguard, Вы писали:


C>>в Java есть Map::computeIfAbsent


_>Я правильно понимаю что смысл этой ф-ции (условно)?:

_>
_>V computeIfAbsent(K, func<V (F)>)
_>{
_>  auto it = find(F);
_>  if(it == end())
_>      it = insert(K, func(K));
  
_> return it->V;
_>}
_>


Абсолютно верно. Тривиальность реализации не означает ненужность, иначе весь <algorithm> можно было бы выкинуть.
Re: Нашёл упоминание в пропозле
От: Alexander G Украина  
Дата: 11.02.22 11:04
Оценка: 12 (1)
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2019/p1063r2.pdf

искать по "tail return"
Русский военный корабль идёт ко дну!
Re: Почему нет принудительного TCO?
От: watchmaker  
Дата: 11.02.22 12:23
Оценка: 22 (2)
Здравствуйте, cppguard, Вы писали:

C> То есть пишешь, что-то вроде

C>    [[force-tco]] return n * factorial(n - 1);


Ты же в курсе про [clang::musttail]]?
Пример использования как раз в гугловых библиотеках: https://blog.reverberate.org/2021/04/21/musttail-efficient-interpreters.html
Примерно через такие контибы к нам тоже код с обязательным tail-call-elimination уже приезжает

И это пример хорошего, хоть и медленного, способа развития языка: не просто писать в стандарте "давайте делать tail-call-elimination", а сначала сделать реализацию хотя бы в одном компиляторе, собрать проблемы, и на основе их уже решать в каком виде тащить это в стандарт.

C> и если TCO не удаётся по каким-то причинам, то это становится ошибкой компиляции


Вот засада описать какие причины должны приводить к ошибке, а какие — нет. Это ведь не должно зависеть от версии компилятора или настроек его оптимизатора (пример, как clang корректно делает tailcall даже при -O0, хотя при -O2 уже сам может заменить рекурсивный алгоритм на итеративный).
И вторая, связанная с ней проблема, что в C++ множество существующих паттернов (вроде использование классов с RAII) завязаны на то, что return не является последним действием в функции.
То есть повсеместно использовать будет сложно, пока только в отдельных загончиках и библиотеках, как в том же protobuf, где код специально переписывали, чтобы удалить действия после return.
Re: Почему нет принудительного TCO?
От: SkyDance Земля  
Дата: 11.02.22 13:25
Оценка:
C>Off-top mode on. Начиная с С++17 добавляют всякую ненужную дичь.

По мне так начиная с С99...

Но в целом да, именно так оно и работает, большие компании пропихивают то, что им удобно. Это, в общем-то, правильный подход. Куда хуже если компания начинает делать свой Лас-Вегас, форк языка, скажем, приделывать типизацию к PHP... oh wait.
Отредактировано 11.02.2022 13:27 SkyDance . Предыдущая версия .
Re[5]: Почему нет принудительного TCO?
От: saf_e  
Дата: 15.02.22 09:33
Оценка:
Здравствуйте, cppguard, Вы писали:

C>Абсолютно верно. Тривиальность реализации не означает ненужность, иначе весь <algorithm> можно было бы выкинуть.


И тут встает второй вопрос: на сколько часто это нужно?
Вот мне такая ф-ция не особо нужна, а тем же empty пользуюсь регулярно.
В джаве, скорее всего, из-за отсутствия итераторов она актуальна, в плюсах — не особо.
Я понимаю что именно сейчас она вам актуальна, но врятли стоит добавлять каждую ф-цию которая кому-то пригодилась )
Re[6]: Почему нет принудительного TCO?
От: cppguard  
Дата: 15.02.22 18:57
Оценка:
Здравствуйте, saf_e, Вы писали:

_>В джаве, скорее всего, из-за отсутствия итераторов она актуальна, в плюсах — не особо.


Дело не в итераторах, а в том, что можно иметь ленивые вычисления. Это ведь любимая проповедь церкви С++ — you don't pay for what you don't use.
Re[5]: Почему нет принудительного TCO?
От: Alexander G Украина  
Дата: 16.02.22 07:48
Оценка:
Здравствуйте, cppguard, Вы писали:


C>Абсолютно верно. Тривиальность реализации не означает ненужность, иначе весь <algorithm> можно было бы выкинуть.


В optional похожее добавили (называется or_else, см. также transform, and_then и value_or). Есть шанс, что и это кто-то добавит.
Русский военный корабль идёт ко дну!
Re[6]: Почему нет принудительного TCO?
От: cppguard  
Дата: 16.02.22 10:18
Оценка:
Здравствуйте, Alexander G, Вы писали:

AG>В optional похожее добавили (называется or_else, см. также transform, and_then и value_or). Есть шанс, что и это кто-то добавит.


С++23
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.