Указатели C как лингвистический парадокс

    Недавно один знакомый, которого я знаю через совсем не программистские круги, попросил помочь ему с лабораторной по C++. В коде было примерно следующее:

    void do_something(MyObj *input[], int count)
    {
        MyObj **copy = new MyObj*[count];
        for (int i = 0; i < count; ++i)
            *copy[i] = *input[i];
        ...
    }

    Этот случай напомнил о том, что тема указателей является едва ли не основным источником ошибок у изучающих язык студентов, а заодно — своеобразным перевалом, преодоление которого сопряжено с «щелчком» в голове, вызывать который, увы, умеют не все преподаватели. Надеюсь, предложенная ниже лингвистическая аналогия поможет нынешним студентам постигнуть эту концепцию, а их преподавателям или друзьям — донести до них это знание.

    Лет десять назад на одном форуме была загадана детская, вроде, загадка:
    Для чего еду обеда
    Людоедоедоеда
    Пригласила на обед
    Людоедоедовед?
    Я хочу показать, что эта загадка имеет самое прямое отношение к C/C++, поскольку тема указателей легко может быть разобрана по аналогии.

    Смотрите. Чтобы понять, что такое «еда обеда людоедоедоеда», нам нужно произвести лингвистический анализ последнего слова. Проще всего это сделать, читая корни справа налево:

    • Людоед = тот, кто ест людей.
    • Людоедоед = тот, кто ест людоедов = тот, кто ест тех, кто ест людей.
    • Людоедоедоед = тот, кто ест людоедоедов = тот, кто ест тех, кто ест людоедов = тот, кто ест тех, кто ест тех, кто ест людей.

    По удачному стечению обстоятельств, тот же порядок чтения — справа налево — применяется в C/C++ для ссылочных типов данных:

    • MyClass* = указатель на MyClass.
    • MyClass** = указатель на MyClass* = указатель на указатель на MyClass.
    • MyClass*** = указатель на MyClass** = указатель на указатель на MyClass* = указатель на указатель на указатель на MyClass.

    С правой частью разобрались, теперь принимаемся за левую.

    • Обед людоедоедоеда = обед того, кто ест людоедоедов = людоедоед.
    • Еда обеда людоедоедоеда = еда людоедоеда = еда того, кто ест людоедов = людоед.

    Стало быть, людоедоедовед (= тот, кто ведает теми, кто ест людоедов) пригласила на обед людоеда. Очевидно, цель такого приглашения — покормить своих подведомственных людоедоедов.

    То есть, лингвистическое правило оказывается таковым: поставив слово «еда» или «обед» слева от слова, оканчивающегося корнем «ед», мы скидываем этот последний корень, оставляя только словарную основу до него.

    Но аналогично же ведут себя и указатели в C/C++: если слева от сущности, имеющий тип «указатель на T», или «T*», мы поставим символ указателя (ту самую звёздочку), то в результате мы скинем один лишний указатель из типа, получив, собственно, T (или, если быть совсем точным, T&, но темы ссылок и прочих lvalue я сейчас намеренно не хочу касаться). Совсем грубо (игнорируя некоторые правила синтаксиса) можно записать, что

    • *(T*) === T,
    • *(T**) === T*,
    • **(T**) === T,
    • *(T***) === T**,
    • и так далее.

    Что в итоге? Я не сформулировал никакого чёткого правила и не сказал про указатели ничего нового. Я лишь надеюсь, что эта лингвистическая аналогия поможет кому-либо из изучающих C/C++ быстрее понять эту тему. Если принять звёздочку за еду, а Люду — за базовый тип… Вы поняли.
    Поделиться публикацией
    Комментарии 244
      +10
      А ведь есть языки, лишённые радости указателей!
        +2

        А может это и не плохо?
        Java хороший пример. (Да, знаю что можно использовать ссылки)

          0
          Какие такие ссылки?
            +3
            Всякие хаскели еще лучше. Ни указателей, ни ссылок.
              +24
              ни софта на них…
                –5
                Софта на хаскеле на моей машине поболе, чем на джаве.

                Да и вам как программисту самому писать или радоваться наличию софта?
                  +1
                  честно говоря не осилил я функциональщину. То ли статей толковых мало, то ли мозгов. Не понял фишки
                    –2
                    Смотря что вы изучали. Менять цикл на map просто так действительно смысла не так уж много.
                      +2
                      Ммм… какой map? std::map пользую, а Хаскель причем тут?
                        0
                        Ну такой вот map. Хотя лучше более общая штука, конечно.
                          0
                          Видимо, кому-то очень не нравится функциональщина. Ну ладно.
                            +1
                            Я думаю дело в другом.
                            Представьте, что вы веган, что бы вы говорили людям?
                              0
                              В треде об особенностях еды можно было бы и обсудить причины, побудившие бы меня быть веганом. Самое оно, как по мне.

                              И посмотрите на самый первый комментарий этой ветки.
                                +1
                                Я просто пошутил.
                                  0
                                  У меня всё очень плохо с восприятием шуток, прошу простить.
                                    +2
                                    Ну на самом деле Вы двигаете функциональные языки, словно это какая-то панацея. Все мои потуги что-то написать напоминают мне попытки забить шуруп молотком. У моих объектов в программах есть состояния, которые надо хранить — и то, что я прочел о ф-ных языках напоминает мне костыли. Мои проги пишутся для реального мира — embedded. И куда там это воткнуть — совершенно не понимаю (даже если были бы компиляторы соответсвующие). Простейшая задачка становится математическим ребусом. Вероятно есть, и может даже много, задач, где ф-ное программирование в тему. Я пока что не вижу таких, и судя по минусам Вам — не я один.
                                      0
                                      Все мои потуги что-то написать напоминают мне попытки забить шуруп молотком. У моих объектов в программах есть состояния, которые надо хранить — и то, что я прочел о ф-ных языках напоминает мне костыли.

                                      Ну так естественно в этом случае у вас будет ощущение забивания шурупом молотка. Функциональщина нужна не за тем, чтоб описывать состояние, а за тем, чтобы состояния не было.


                                      Мои проги пишутся для реального мира — embedded.

                                      Тогда вам точно функциональщина не нужна. Ее смысл в итоге сводится к декларативности (вместо того, чтобы описывать процесс получения результата, описываем сам результат, а уже компуктер догадается, как его получить). В embedded вам нужно описывать процесс by design.

                                        0
                                        Функциональщина нужна не за тем, чтоб описывать состояние, а за тем, чтобы состояния не было.

                                        Неа. Если достаточно упороться монадками, то наступает просветление и понимание, что чистоты нет, стейта нет, эффектов нет, потому что это сами по себе не дискриминирующие термины.

                                        State — это просто удобная абстракция некоего паттерна композиции функций, чтобы создать видимость объективно существующего стейта. Но мы ведь понимаем, что это ерунда.

                                        Программа, производящая IO-экшн, вполне себе чистая. Ну, просто как набор правил, как этот экшн произвести. Точно так же, как, на самом деле, и программа на С. Просто в программе на С у вас весь код — одно большое IO.

                                        Поэтому что важно — возможность себя ограничить. Если вы видите функцию, которая живёт не в IO, то вы точно1 знаете, что файлы она читать-писать не будет и на сервер не постучится. Если вы видите функцию, которая живёт в State s, то вы точно знаете, чем ограничено её «состояние».

                                        Ну я тут, короче, в очередной раз за систему типов и всё такое топлю.

                                        1
                                        Если погрепаете на тему unsafePerformIO или всякие там SafeHaskell включите, но это несущественно в рамках дискуссии.


                                        Тогда вам точно функциональщина не нужна. Ее смысл в итоге сводится к декларативности (вместо того, чтобы описывать процесс получения результата, описываем сам результат, а уже компуктер догадается, как его получить). В embedded вам нужно описывать процесс by design.

                                        Не вижу препятствий в eDSL для этого эмбеддеда (см. вышеупомянутый Ivory), статически тайпчекаемого и верифицируемого, описывающего при этом вполне императивный процесс.

                                        Я как раз сейчас играюсь с выражением и околоверификацией всякой локфри-ерунды на манер deja fu, но пока без того, о чём стоило бы говорить.
                                          0
                                          Неа. Если достаточно упороться монадками, то наступает просветление и понимание, что чистоты нет, стейта нет, эффектов нет, потому что это сами по себе не дискриминирующие термины.

                                          Ну так стейта нет — это то, о чем я и говорю. Если же у вас стейт есть, и вы пытаетесь его делать на ФП — то что-то не так. В смысле самого мышления.


                                          Не вижу препятствий в eDSL для этого эмбеддеда (см. вышеупомянутый Ivory), статически тайпчекаемого и верифицируемого, описывающего при этом вполне императивный процесс.

                                          Только DSL и верификация ортогональны функциональному программированию. Вообще, конечно, термин сейчас сильно размыт и следует по-хорошему уточнять, что под фп подразумевается. Я подразумеваю в базе чистую лямбда с надстройками. То есть какой-нибудь Scheme без макросов — сферическое ФП в вакууме.

                                            0
                                            Ну так стейта нет — это то, о чем я и говорю. Если же у вас стейт есть, и вы пытаетесь его делать на ФП — то что-то не так. В смысле самого мышления.

                                            Я про то, что его вообще нет в том смысле, что это бессмысленный термин сам по себе.

                                            Вот вы fold или unfoldr делаете, аккумулятор — это стейт?

                                            Я вот на Charts с их монадическим Easy API графички построил, у меня есть стейт?

                                            Или вот я вообще взял произвольную монаду и сижу в do-нотации, выковырял там из неё какой-то x и какой-то y типа
                                            foo :: Monad m => m Int
                                            foo = do
                                                x <- f1
                                                y <- f2
                                                pure $ x + y
                                            

                                            У меня здесь есть стейт, если m ~ Maybe и f1 и f2 соответствующие? А если теперь m ~ State s, и f1 = gets foo, f2 = gets bar?

                                            Только DSL и верификация ортогональны функциональному программированию. Вообще, конечно, термин сейчас сильно размыт и следует по-хорошему уточнять, что под фп подразумевается. Я подразумеваю в базе чистую лямбда с надстройками. То есть какой-нибудь Scheme без макросов — сферическое ФП в вакууме.

                                            Ну, я имею в виду написание eDSL и использование имеющейся в языке системы типов (да, я помню нашу дискуссию на эту тему) для предоставления некоторых гарантий. Хотя какой-нибудь идрис для этих целей подойдёт ещё лучше, потому что гарантий там можно выразить ещё больше, и do-нотация не только для Monad и Applicative.

                                            ФП такого толку — это про типы, ИМХО. Лямбда-исчисление я вам и на плюсах замутить могу. Туплы на них прикольно делаются, кстати, но то такое.
                                              0
                                              Вот вы fold или unfoldr делаете, аккумулятор — это стейт?

                                              Стейт — это не то, что в коде написано, а то, как код воспринимается (от кода при этом может зависит насколько сложно описываемые им вещи рассматривать в рамках той или иной парадигмы). Если вы рассуждаете об аккумуляторе фолда как о стейте — это стейт. Если нет — то нет. Аналогично с монадами. Если вы монадический код в IO воспринимаете как просто императивный код — ну, у вас тут стейт.


                                              ФП такого толку — это про типы, ИМХО. Лямбда-исчисление я вам и на плюсах замутить могу.

                                              А можно типы в императивщину добавить. И верифицировать. Или верифицировать без типов. Все-таки тут речь надо вести не просто о типах, а об определенном способе мышления и использования этих типов. В этом контексте правильно говорить не "фп — это когда есть А и Б", а, скорее, "фп — это когда нету А и Б" (и аналогично для любой другой парадигмы). Потому что именно отсутствие альтернатив вынуждает строить программу и рассуждать о ней определенным способом. Наличие же фич — лишь дает возможность.

                                                0
                                                Если вы рассуждаете об аккумуляторе фолда как о стейте — это стейт. Если нет — то нет.

                                                Хм, это интересный взгляд, надо подумать. Правда, мне не очень нравится некоторая его субъективность или зависимость от наблюдателя. Но, может, это и неплохо.

                                                Потому что именно отсутствие альтернатив вынуждает строить программу и рассуждать о ней определенным способом.

                                                Ну вы и на хаскеле можете всё писать в IO с IORef'ами, никто не запретит.

                                                А если вы как-то так внезапно добавите в C++ такую систему типов, что можно будет гарантировать чистоту, иммутабельность и прочие дорогие сердцу вещи, то да, у вас будет функциональное подмножество.
                                          0
                                          Функциональщина нужна не за тем, чтоб описывать состояние, а за тем, чтобы состояния не было

                                          Функция — это объект внутри которого выполняется некоторый код и куда опционально передаются параметры или возвращается результат. В этом смысле ФП это по прежнему ООП.

                                            0

                                            Одно и то же можно сказать разными способами. То, что можно сказать в ФП, можно сказать и в ООП. И наоборот.

                                              0

                                              Есть ЯП в которых нет объектов. Так что ваш тезис и тут некорректен.

                                                0
                                                Есть ЯП в которых нет объектов.

                                                Но это не мешает в них объекты использовать, моделируя на имеющихся примитивах. Точно так же как в ООП нет функций, но вы можете их использовать, моделируя при помощи объектов.

                                                  0

                                                  Программирование на JSONNET это ООП?

                                                    0

                                                    Нет, если по парадигмам, то это ближе всего к ФП, наверное. От ООП там вроде и вовсе ничего нету.

                                                      0

                                                      Верно, но тем не менее там сполошь и рядом объекты. В их построении не хватает сингулярности. Но это уже другая важная тема. Которую все старательно обходят стороной.

                                                        0
                                                        Это вы к чему, с-но?
                                                          0

                                                          К тому что массивы еще как то в объекты собрать можно, а вот функции нет. На уровне компилятора. И классы кстати тоже:) Lisp в этом ряду стоит обособоленно.

                                                            0
                                                            К тому что массивы еще как то в объекты собрать можно, а вот функции нет. На уровне компилятора. И классы кстати тоже

                                                            Можно, т.к. язык тьюринг-полный. Только, думаю, кодировка вам откровенно не понравится :)

                                                              0

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

                                                                0
                                                                > Нет нельзя.

                                                                Можно.
                                                                  0

                                                                  "fun":[1,2] — плс! хочу функцию:)

                                                                    0
                                                                    А что она должна делать?
                                                                      0
                                                                      function fun (a,b){
                                                                          var arg=arguments;
                                                                          console.log(arg);
                                                                          console.log(arg[0][0]+arg[0][1]);
                                                                      
                                                                      }
                                                                      var obj={
                                                                          ctx:fun,
                                                                          pars:[1,2]
                                                                      }
                                                                      
                                                                      fun([1,2]);
                                                                      obj.ctx(obj.pars);
                                                                        0
                                                                        Если я правильно угадал язык, то я его знаю очень плохо, и я не очень понимаю, что оно должно делать.
                                                                          0

                                                                          JS. Я привел пример вызова фунции двумя способами.
                                                                          Чего не хватает в языках. Собственно отдельного контекстного объекта с кодом которому можно передавать разные параметры по определенным правилам. Хочется чтобы параметры и код лежали где-то как отдельные компоненты и собирались на лету по запросам в целевой объект-контейнер. Контейнер содержал бы композицию из разных функций. А так мы не можем отдельно хранить тушку функции и результат.

                                                                            0
                                                                            Вполне можно хоть на хаскеле, хоть на плюсах, если я вас правильно понял.
                                                                              0

                                                                              Если можно пожалуйста проиллюстрируйте такую возможность примером.

                                                                                0
                                                                                Взять, например, std::apply, и лямбды с функциями хранить в одном месте, а туплы с их аргументами — в другом.
                                                                                  0

                                                                                  Спасибо. В JS apply тоже есть и анонимные функции. Нет не то. Хочется чтобы сами операторы в функции были бы элементами массива. Чтобы к ним можно было бы адресоваться.

                                                                      0

                                                                      Чего, не понял?

                                                                0
                                                                Я вот вообще не понял, что означает собирание массивов в объекты, и чем функции хуже массивов.
                                                                  0

                                                                  Самый простой вариант.


                                                                  [["key1","value1"],["key2","value2"]] последовательный поиск по ключу
                                                                  {"key1":"value1","key2":"value2"} - прямой доступ.

                                                                  Функция это уже объект.

                                              +1
                                              Неа, это не панацея. Есть области, в которых функциональные языки на текущем уровне развития — исключительно хреновый выбор. Какие-нибудь числодробилки, скажем, или задачи, где нужно просто очень много памяти. Под такие задачи я тоже беру C++ и счастливо пишу на нём.

                                              Но в остальных задачах, от, не знаю, какой-нибудь банальной обработки логов до написания компиляторов и всяких сервисов-микросервисов — да, функциональщина — очень хороший выбор. И с написанием стейтфул-программ там тоже всё вполне хорошо (не знаю, чем вам тот же State — костыль). А с многопоточностью ещё лучше, начиная от принципиального отсутствия класса проблем, связанных с разделяемыми данными, и заканчивая такими примитивами, как STM, например.

                                              Иными словами, мне проще перечислить задачи, где чистое ФП будет плохим выбором, чем где оно будет хорошим. Короче список получится.

                                              С эмбеддедом у меня мало опыта, правда, не знаю про актуальное состояние дел, но слышал про истории успеха с этим, например.
                                                0
                                                там похоже совсем не то. Под эмбеддед я понимаю микроконтроллеры. Вот пишут «описываем сам результат, а уже компуктер догадается, как его получить).» Совершенно не понимаю. Вот сидит себе микроконтроллер. Ждет пакет инфы с радиоэфира. По получении должен сделать то, потом то, все со строгой времянкой и в зависимости от состоянии кучи датчиков. Как тут описать результат — непонятно. Более менее все ясно с числами Фиббоначи только мне. Да и то, там рекурсия (?) за которую в embedded руки отрывают — мало ресурсов. Даже за динамическое выделение памяти не всегда по голове гладят. По-моему язык пригоден для математиков, задачи реального мира если и можно решить, то выглядит это как несчастная сова на глобусе. Но я не сильно вникал в ФП
                                                  0
                                                  там похоже совсем не то.

                                                  Вы про тот же Ivory? Я его не тыкал совсем, так, вместе с вами сейчас документацию читаю.

                                                  Вот пишут «описываем сам результат, а уже компуктер догадается, как его получить).»

                                                  Это уже пролог какой-то. Я бы сказал, что в функциональщине предполагаемая догадливость компуктера сильно меньше.

                                                  Более менее все ясно с числами Фиббоначи только мне. Да и то, там рекурсия (?) за которую в embedded руки отрывают — мало ресурсов.

                                                  Не, почему? Ivory вполне может компилировать это вот n `times` f во вполне себе императивный цикл. Собственно, подробное описание этого примера ровно об этом и говорит: «Here’s an Ivory procedure which computes Fibonacci numbers by mutating values on the stack in a loop.» На стеке. В цикле.

                                                  Даже за динамическое выделение памяти не всегда по голове гладят.

                                                  «Systems Programming: Ivory is well suited for writing programs which interact directly with hardware and do not require dynamic memory allocation.»

                                                  По-моему язык пригоден для математиков, задачи реального мира если и можно решить, то выглядит это как несчастная сова на глобусе.

                                                  Для математиков пригодны более другие языки, кстати, в хаскеле есть кое-какие криво сделанные вещи, из-за которых в некоторых областях конкретно он будет тоже очень плохим выбором (ну там, формальное доказательство теорем всякое, всё такое). А про реальные задачи, ну, я уже писал.
                                                    0
                                                    OK, спасибо за пояснения, думаю мне дергаться на этот счет рано. Вот что реально заставляет нервничать — это С++ со всеми его нововведениями, по-моему они задались целью сделать самый сложный язык на свете. Глядя на некоторые новые исходники на С++ хочется спросить «на каком это языке.» Впрочем отвлекся.
                                                      0
                                                      Ну, у меня есть знакомые товарищи, которые сидят на C++03 и в ус не дуют, им норм, так что это зависит.

                                                      Я, впрочем, и плюсы люблю нежной любовью, люблю обмазаться свежими темплейтами и компилировать. Из всех нововведений меня только std::launder раздражает. Но это дело такое, да.
                                                    0
                                                    Ждет пакет инфы с радиоэфира. По получении должен сделать то, потом то, все со строгой времянкой и в зависимости от состоянии кучи датчиков. Как тут описать результат — непонятно.

                                                    Ну видите, "должен сделать" — это уже не ФП. С точки зрения ФП — будет понятие некоего абстрактного действия. Вы можете создать действие, скомбинировать это действие вместе с какими-то другими действиями каким-то способом и получить новое действие. Пакет инфы и показания датчиков — это данные. Вы описываете, действие какого вида должно получится из каких данных, то есть описываете ф-ю (в математическом смысле) perform: Data -> Action, при этом не специфицируете, как эту ф-ю требуется вычислять. Далее вы можете ввести какие-то проверки на тот факт, что построенный на указанных данных Action удовлетворяет определенным условиям, например, у вас есть ф-я time Action -> int и вам надо убедиться, что time(perform(data)) < n. При этом если вы свой Action составляли из других экшонов при помощи некоторых комбинаторов, то у вас могут быть разные утверждения вроде (time(action1) = a, time(action2) = b => time(sequence(action1, action2)) = a + b); Вот если вы так все будете воспринимать — вы пишете на фп, при этом в качестве языка можете хоть сишку использовать.

                                                      0
                                                      боюсь что просмотр итогового кода (в дизасме) может привести к инфаркту, не?
                                                        0
                                                        боюсь что просмотр итогового кода (в дизасме) может привести к инфаркту, не?

                                                        Ну почему? Вы же можете выбрать комбинаторы близкие по смыслу к композиции существующих блоков кода на асме. В пределе — вообще совпадающими, тогда рассматриваемая штука будет просто средой метапрограммирования над асмом.

                                                          0
                                                          Кстати, нет, компиляторы-то уже вполне умные.

                                                          Парсеры на хаскелевском attoparsec приближаются по скорости к boost.spirit, который вообще один из быстрейших вариантов. Забавные бенчмарки бинарных парсеров я тоже видел, где cereal, что ли, уделывает аналогичный высокопроизводительный сишный парсер. Увы, сейчас не нагуглю.

                                                          А когда вчера мне компилятор функцию вида
                                                          fraction p list = length' (filter p xs) / length' xs
                                                              where length' = fromIntegral . length
                                                          

                                                          скомпилировал в однопроходный цикл по списку, я совсем не удивился.
                                                        0
                                                        Функциональное Программирование (ФП) можно представить себе как такое написание программы, когда ее выполнение представляет собой как бы вложенные друг за другом «математические функции»: fun1(fun2(fun3(x))) У каждой функции есть совершенно чёткий «вход» и совершенно чёткий «выход», также как у математических (вычислительных) функций: Выход = function(Вход). При этом ни одна функция внутри не обращается к каким-либо переменным/памяти/портам/итд, короче ко всему тому, что представляет собой состояние/память. Подобное состояние, если оно есть (к примеру порт), подается только как «вход». И вдобавок к этому функция должна быть детерминирована (делать одно и то же).
                                                        Что это даёт? Подобные функции не зависят ни от чего, кроме как своих входных параметров. И поэтому, если каждый раз перезапускать их с одними и теми же аргументами, мы будем получать на выходе один и тот же результат.
                                                        Эмбедщику можно это понять так, что данные словно бы передаются в регистрах, и в регистрах же возвращаются назад, ничего более не меняя.
                                                        Это очень удобно и для отладки и для написания стабильных программ — проблемы отладки чаще всего заключаются в том что при работе программы меняется какое-то внутреннее состояние (память, переменные, стек итд) и нет возможности сделать «шаг назад». А при ФП парадигме — достаточно подать на «вход» программы одни и те же предварительно записанные данные, и она выдаст один и тот же результат, пока мы не поправим саму программу.
                                                        Парадигма такова, что программа как бы «воздействует» на проходящие через нее данные или их потоки, сама же являя собой «чистый закон».
                                                        Что интересно, правильная и рекомендуемая методология *NIX программирования это, в некотором смысле, ФП: мелкие отдельные утилиты, каждая выполняющая свою функцию, принимающие данные на вход, и выдающие детерминированно одно и то же, при том что их можно объединять друг за другом, т.е. выход одной утилиты/команды по-цепочке передавать на вход другой.
                                                        Пиксельные шейдеры тоже при определенном приближении являют собой ФП-стиль, вместе с реактивным.
                                                        Часть существующих программ и так уже написана приближаясь к функциональному стилю.
                                                        Реальное ФП, конечно, подразумевает собой гораздо большее, но кое-какие полезные элементы почерпнуть из ФП, как видим, можно.
                                                          0
                                                          Спасибо, достаточно понятно объяснили, хотя реальная применимость мне пока туманна. Вот допустим хотим мы смоделировать покупателя. Чтобы он что-то купил ненужное, он должен продать что то ненужное (например свой труд). Продав, он получит деньги (состояние объекта). Причем поставить покупателя в функцию покупки просто так не очень просто (эти деньги могут лежать в банке, на них идет процент итп). То есть я могу примерно это представить, но совершенно не понимаю, как в ФП реализуется что-то асинхронное, завязанное на время, возникающее от случая к случаю… А еще такой вопрос, глядя на машинный код ФП программы, вы сможете отличить его от кода, полученного компиляцией с императивного языка?
                                                            0
                                                            То есть я могу примерно это представить, но совершенно не понимаю, как в ФП реализуется что-то асинхронное, завязанное на время, возникающее от случая к случаю…

                                                            В ФП функции — это тоже данные. С-но, действия, процессы, которые при помощи каких-то примитивов комбинируются в их наборы, ивент лупы с хендлерами и любые подобные вещи — это все данные.

                                                              0
                                                              Спасибо, достаточно понятно объяснили, хотя реальная применимость мне пока туманна.
                                                              Важным преимуществом ФП является параллелизм. Поскольку все функции для вычислений используют только свои параметры, можно организовать вычисление независимых функций в произвольном порядке или параллельно, на результат вычислений это не повлияет. Следование элементам ФП-парадигмы упрощает построение многозадачности (в т.ч. для hardware см. read-only, оно же immutability).
                                                              Вот допустим хотим мы смоделировать покупателя.

                                                              Это уже дальнейший вопрос, как моделируется предметная область.
                                                              1. Функции в ФП устанавливают отношение (relationship). Эмфазис ФП — трансформация значений/данных.
                                                              2. Функциональные языки часто гибридные (Object-Functional) — например OCaml, Scala.
                                                              совершенно не понимаю, как в ФП реализуется что-то асинхронное, завязанное на время, возникающее от случая к случаю…

                                                              «асинхронное, завязанное на время, возникающее от случая к случаю» — назовем это Discrete Event Processsing / Discrete Event Model.
                                                              Обработка событий — это область все же ортогональная к парадигме программирования. Это можно понять задавшись вопросом — как это представимо для других парадигм: ООП, процедурной на ЯВУ или таблицы прерываний с обработчиками на ассемблере. Тем не менее, смысл в этом замечании есть, поскольку классически под моделирование систем с дискретными событиями был создан именно ООП (Simula), а вот характерные для ФП relationship,transformation служат для решения задач в другом пространстве. Но так дело выглядит при первом взгляде. Когда же речь заходит о потоках событий, сигналах, и потоковой асинхронной обработке вообще — на сцене быстро появляется ФП. Сугубо практическое применение этому — Matlab и его Simulink.
                                                              А еще такой вопрос, глядя на машинный код ФП программы, вы сможете отличить его от кода, полученного компиляцией с императивного языка?
                                                              Я это понял как вопрос о парадигме, а не о языках, компиляторах и какие они порождают финальные исполняемые файлы. Императивное и функциональное представление эквивалентны (доказано теоретически). ФП лишь парадигма, также как ООП может быть заменено программированием в процедурном стиле (C++ программа в некоторых компиляторах претерпевает фазу превращения в C. На последнем можно вручную симулировать наследование и виртуальные методы). С другой стороны, при применении почерпнутых техник ФП к обычным программам можно увидеть некоторые архитектурные отличия. К примеру, посреди тела функции не будет обращения или модификации каких-либо переменных. Передача аргументов, возврат значений будет преимущественно by value, при этом можно будет заметить что переданные аргументы (втч данные по указателям/ссылкам) не модифицируются. Будет заметна однократная инициализация без пере-присваивания. Повторюсь, это в самом общем, генеральном смысле, не погружаясь в явные отличия которые порождают компиляторы и их оптимизации.
                                +1

                                Как это, а Ptr/ForeignPtr/StablePtr? ;)

                                  –1
                                  Это скорее хендлы.
                                    +1
                                    Надо, наверное, сразу было пояснить. Хендлы в том смысле, что для нормального программирования на хаскеле они не нужны совсем, эти Ptr'ы вылезают только при работе с FFI, посему относиться к ним лучше не как к указателям, а как к хендлам, описывающим некоторые внешние относительно языка ресурсы.
                                +4
                                В Java то, что мы используем для работы с объектами, вполне себе указатели. Просто мы лишены радости изменять эти указатели или создавать новые на их основе, используя простую арифметику (к примеру, получить таким образом указатель на массив, аналогичный данному, но начинающийся с третьего элемента). Например, если в метод передали (указатель на) объект, то можно спокойно манипулировать содержимым объекта, но вот взять и назначить указателю новый адрес (объекта) так, чтобы это было видно за пределами метода, нельзя. То есть при передаче объекта в метод создаётся копия указателя, с которой метод и работает. Всё это здорово упрощает жизнь, не давая выстрелить себе в ногу на ровном месте. Примитивы при передаче в метод всегда копируются. Если очень хочется менять сам примитив из метода, то его можно обернуть в объект и уже этот объект передать в метод.
                                0
                                Как такие языки решают проблему модификации «тяжёлых» объектов?
                                Вот надо в картинке изменить пару пикселей — не создавать же полную её копию?
                                  0
                                  Если вам нужно только изменить пару пикселей и всё, то в любом случае придётся создавать полную копию. Иначе можно удобным полудекларативным, полуимперативным API описать все необходимые изменения и потом один раз их выполнить.

                                  Примерно так работает, например, Repa, и как-то похоже работает Accelerate.
                                    +4
                                    Если вам нужно только изменить пару пикселей и всё, то в любом случае придётся создавать полную копию.

                                    Создание которой можно соптимизировать в мутацию, если доказать, что на объект существует лишь одна ссылка.

                                      +1
                                      Что тем проще сделать, чем более строг ваш язык. Особенно если там есть аффинные типы, например.
                                        0

                                        Ну да, я, с-но, и намекал на Clean.

                                    +2
                                    В таких языках любой «объект» на самом деле является указателем на соответсвующий объект. Копию нужно всегда делать явно.
                                      0
                                      Вот иллююстрация на Java:

                                      int i = 1;
                                      int j = 1;
                                      System.out.println(i == j); // true
                                      


                                      String i = "1";
                                      String j = "1";
                                      System.out.println(i == j); // false
                                      System.out.println(i.equals(j)); // true
                                      
                                        +2
                                        И ни фига подобного.
                                        В зависимости от того, как сложатся звезды у вас первое сравнение в примере со String может выдать true.
                                        А может и false.
                                        ideone.com/BkxRUq
                                          +1
                                          В данном конкретном примере звезды должны бы всегда складываться в true, если пользоваться стандартным javac, а не компилить в байткод самому.
                                        +1

                                        Дело в том, что компилятор одинаковые строковые константы в пределах класса может записывать в class-файл как одну константу (и делает это в данном частном случае). По ссылке из комментария выше это и происходит.

                                          0
                                          И вам спасибо :)
                                    0
                                    В Java нет указателей, но при работи с большими массивами int и индексами по ним, задача вполне логически тожественная указателям первого уровня.
                                      +2

                                      Не так страшны указатели, как их арифметика.

                                        +2
                                        До тех пор, пока у процессора есть инструкция «прочитать в регистр по ссылке», любой язык программирования, игнорирующий этот факт, будет просасывать Си по производительности.

                                        Правильный подход: богатая система типов, запрещающая творить фигню (Rust!), но сохраняющая указатели в полном объёме.
                                          +2
                                          Вообще говоря — не факт.
                                          Теоретически, языки более высокого уровня могут позволить применить гораздо более эффективные оптимизации, вроде многопоточности или вообще — менять применяемый алгоритм по мере накопления данных прямо во время выполнения.
                                            0
                                            менять применяемый алгоритм по мере накопления данных прямо во время выполнения

                                            Чем JVM уже некоторое время успешно занимается.
                                              0
                                              Одно другому не мешает. Однако, значения на стеке всё равно будут быстрее значений на хипе, а каким бы оптимизирующим не был компилятор, его GC всё равно сосёт, потому что есть.
                                                0
                                                Если объект не вылезает из nursing area, то его создать или удалить — это точно так же подвигать указатель, только не на стек, а внутри nursing area. От стека не особо отличается по производительности аллокаций и деаллокаций (если вы это под скоростью значений имели в виду, конечно).
                                                  0
                                                  При работе с переменными на стеке нет аллокации и деаллокации. И даже указатель на стеке двигать не надо — lifetimes определяют размер области на стеке на этапе компиляции (я про Rust).

                                                  Основная же проблема в том, что GC всё равно должен «узнать» о том, что объект больше не нужен. Если это решение принимается в runtime, да ещё и асинхронно с приложением, то это плохо.
                                                    +1
                                                    При работе с переменными на стеке нет аллокации и деаллокации.

                                                    В GC тоже ее нет. Один раз выделяется nursery (цельный кусок памяти), сохраняется указатель на его начало. Когда рантайму нужна память, то возвращается текущее значение указателя и сам указатель смещается на величину, которая, с-но, требуется для выделения. После исчерпывания nursery указатель просто сбрасывается на начало и процесс повторяется.


                                                    И даже указатель на стеке двигать не надо — lifetimes определяют размер области на стеке на этапе компиляции (я про Rust).

                                                    Вам надо двигать указатель на сам стек, что эквивалентно движению указателя в nursery. При этом сброс nursery происходит быстрее, чем сброс стека. Именно по-этому без кастомных аллокаторов с той же логикой вы никогда не достигнете в расте той же скорости работы с памятью, что и в, например, хаскеле.


                                                    Основная же проблема в том, что GC всё равно должен «узнать» о том, что объект больше не нужен.

                                                    В определенных предположениях можно гарантировать что объекты в nursery недостижимы, с-но ничего узнавать не надо, просто сбрасываем указатель на начало и все (при этом все объекты так и остаются в nursery но они потом перезапишутся). Это не очень хорошо работает в случае, например, ООП, но в случае ФП, когда вам надо выделять огромное количество короткоживущих, "одноразовых" объектов (гигабайты в секунду), эта техника незаменима. Если бы в том же хаскеле было не так а выделялись бы куски по стандартному new то оно бы по сути было неюзабельно.

                                                      0
                                                      А каким образом GC знает, где один кусок начинается, а где заканчивается? Где-то же нужно будет записать объект в список, либо использовать какие-то дополнительные пометки, иначе каким образом GC может перенести выживший объект дальше? Когда у вас происходит аллокация на стеке, то смещения на стеке (относительно SP) уже захардкожены компилятором в программу. Нет никакого «списка объектов», каждая переменная — всего лишь разное смещение в памяти (например, SP-0x20). В контексте nursery — это всё равно heap, а heap означает, что программа работает с динамическим указателем.

                                                        +1
                                                        А каким образом GC знает, где один кусок начинается, а где заканчивается? Где-то же нужно будет записать объект в список, либо использовать какие-то дополнительные пометки, иначе каким образом GC может перенести выживший объект дальше?

                                                        Смысл в том, что поскольку у вас практически никогда нет выживших объектов, то и переносить ничего не приходится. При этом определить, что выживших объектов нет, очень просто — поскольку данные иммутабельны, то более молодые данные могут ссылаться на более старые, но более старые не могут ссылаться на более новые. Если в текущем контексте нет ссылок на другие объекты в nurcery, значит, все, что левее — недоступные данные.
                                                        В том случае, когда ссылки есть — конечно, приходится проводить скан дальше и перемещать данные в основную память. Но это, еще раз, происходит очень редко.


                                                        Когда у вас происходит аллокация на стеке, то смещения на стеке (относительно SP) уже захардкожены компилятором в программу.

                                                        В функциональном рантайме все точно так же, у вас в хипе хранятся стекфреймы, относительно начала которых указываются смещение. И вам никто даже не мешает использовать SP в качестве регистра для хранения указателя.


                                                        В контексте nursery — это всё равно heap, а heap означает, что программа работает с динамическим указателем.

                                                        А чем по-вашему стек отличается от выделенного в хипе куска памяти, указатель на который лежит в SP?

                                                          0
                                                          «Почти ничего» не считается. GC должен знать где какой объект хранится. Это означает, что где-то должен быть записан указатель на него.

                                                          Любые операции с heap'ом требуют использовать адрес heap'а. Его можно хранить либо в регистре общего назначения (программисты любят раскидываться регистрами общего назначения), либо в переменной — т.е. в памяти.

                                                          Хранить указатель на heap в SP — это восхитительно. call и ret как делать тогда?

                                                          Стек от выделенного куска в heap'е отличается тем, что положение ячейки памяти в heap'е не определено в compile time, а в хороших языках программирования, вроде Rust, смещение относительно SP точно известно. Сам же стек обслуживается процессором, быстрее, чем обычные операции с памятью (аппаратная поддержка).
                                                            0
                                                            «Почти ничего» не считается. GC должен знать где какой объект хранится. Это означает, что где-то должен быть записан указатель на него.

                                                            А указатели и так есть, в других объектах.

                                                            Хранить указатель на heap в SP — это восхитительно. call и ret как делать тогда?

                                                            А нету никаких call и ret, одни джампы.

                                                            Да, и коллстека тоже нет.
                                                              0
                                                              Угу, нету call'ов в хаскеле. Смешно. Я вбил туда main = putStrLn «Hello, world!» и увидел call'ы. ЧЯДНТ?

                                                              Когда указатели в других объектах, их надо писать и читать (указатели) — это обращения к памяти. Чтение по фиксированному смещению от SP всегда быстрее, чем heap->data, потому что само значение heap тоже надо прочитать.
                                                                0
                                                                Угу, нету call'ов в хаскеле. Смешно. Я вбил туда main = putStrLn «Hello, world!» и увидел call'ы. ЧЯДНТ?

                                                                В IO своя атмосфера. Я с любопытством посмотрю, как вы получите call вне IO или ST.

                                                                Чтение по фиксированному смещению от SP всегда быстрее, чем heap->data, потому что само значение heap тоже надо прочитать.

                                                                Если heap у вас меняется нечасто, то амортизированно это не проблема.
                                                                  0
                                                                  В IO своя атмосфера.

                                                                  С-но, работы программы на хаскеле заканчивается тогда, когда вернули IO. Что там это IO потом делает — уже не барское дело :)

                                                                  0
                                                                  Чтение по фиксированному смещению от SP всегда быстрее, чем heap->data

                                                                  А зачем читать heap->data, если можно читать register->data?

                                                                    0
                                                                    Т.е. вы предлагаете для heap'а зарезервировать один регистр общего назначения? На arm вам такое простят, на x86_64 с трудом, на i386 на вас конкретно обидятся.
                                                                      +1
                                                                      на i386 на вас конкретно обидятся.

                                                                      Почему i386, а не БЭСМ-1? Ну и на самом деле всегда можно использовать сам SP.

                                                                        0
                                                                        dpkg-architecture -L|grep -v — -
                                                                        armhf
                                                                        armel
                                                                        mipsn32
                                                                        mipsn32el
                                                                        mipsn32r6
                                                                        mipsn32r6el
                                                                        mips64
                                                                        mips64el
                                                                        mips64r6
                                                                        mips64r6el
                                                                        powerpcspe
                                                                        x32
                                                                        arm64ilp32
                                                                        i386
                                                                        ia64
                                                                        alpha
                                                                        amd64
                                                                        armeb
                                                                        arm
                                                                        arm64
                                                                        avr32
                                                                        hppa
                                                                        m32r
                                                                        m68k
                                                                        mips
                                                                        mipsel
                                                                        mipsr6
                                                                        mipsr6el
                                                                        nios2
                                                                        or1k
                                                                        powerpc
                                                                        powerpcel
                                                                        ppc64
                                                                        ppc64el
                                                                        riscv64
                                                                        s390
                                                                        s390x
                                                                        sh3
                                                                        sh3eb
                                                                        sh4
                                                                        sh4eb
                                                                        sparc
                                                                        sparc64
                                                                        tilegx

                                                                        полный список тут:

                                                                        gist.github.com/amarao/9856494f69cc28e6280351e3a5fac5ec

                                                                        БЭСМ-1 не вижу.
                                                                          0

                                                                          А какое отношение данный список имеет к предмету разговора? Вдруг у меня вот свой личный список без i386-х смердящих и с БЭСМами бодрящими!
                                                                          Он же ничем не хуже вашего списка из ряда архитектур, выбранных случайным образом.

                                                                            0
                                                                            Я привёл список живых архитектур. Список не случайный, а исчерпывающий.
                                                                              0
                                                                              > Я привёл список живых архитектур.

                                                                              А зачем вы его привели? Вы поясните как-то свой аргумент. Типа: «вот список, по-этому...».
                                                                                0
                                                                                Я его привёл как доказательство, что БЭСМ — мёртвая архитектура. А i386 — живая.
                                                                                  +1
                                                                                  I386, строго говоря, уже мёртвая. Как и AArch32. Хотя AArch32 чуток поживее будет: процессоры без AArch64 ещё выпускаются, а без x86-64 — уже нет.

                                                                                  А так-то компиляторы и для 6502 есть, речь же не о них.
                                                                0
                                                                Стек от выделенного куска в heap'е отличается тем, что положение ячейки памяти в heap'е не определено в compile time, а в хороших языках программирования, вроде Rust, смещение относительно SP точно известно.

                                                                Положение аргументов относительно стекфрейма тоже известно в компайлтайме.


                                                                Сам же стек обслуживается процессором, быстрее, чем обычные операции с памятью (аппаратная поддержка).

                                                                Какая аппаратная поддержка? Стек — это обычная область памяти, которую ОС выделяет процессу. Неизвестно положение стекфрейма. Но оно и в расте неизвестно.

                                                                  0
                                                                  Аппаратная поддержка — это SP, call, ret, popa, pusha, pop и push инструкции.
                                                                    0
                                                                    Аппаратная поддержка — это SP, call, ret, popa, pusha, pop и push инструкции.

                                                                    С-но, если вы не используете call, ret, push, pop, то вам и не нужна эта аппаратная поддержка.

                                                                      0
                                                                      Но без стека вы всё равно не переживёте, потому что первое же прерывание потребует куда-то «всё это» сохранить.
                                                                        0
                                                                        Но без стека вы всё равно не переживёте, потому что первое же прерывание потребует куда-то «всё это» сохранить.

                                                                        Сохраняйте. В чем проблема? Вам же никто не запрещает стек использовать.

                                                                          0
                                                                          Если вы к тому, что «стек не нужен», можно без него, но в этой ситуации вы не можете использовать SP для другого (прерывания), а его аналог потребует пожертвовать одним из регистров. Можно, но хуже.
                                                                            0
                                                                            а его аналог потребует пожертвовать одним из регистров.

                                                                            Что, вообще говоря, не проблема.


                                                                            в этой ситуации вы не можете использовать SP для другого (прерывания), а его аналог потребует пожертвовать одним из регистров.

                                                                            Почему не могу? ОС же как-то использует и регистрами не жертвует.

                                                                              0
                                                                              К вопросу о необходимости регистров: www.youtube.com/watch?v=lXJ-tYqPARg
                                                                              и
                                                                              www.youtube.com/watch?v=nc2q4OOK6K8

                                                                              Ос не использует никакие регистры общего назначения когда исполняется userspace. Для этого стек (в частности) и нужен — сохранить регистры.
                                                                                0
                                                                                Ос не использует никакие регистры общего назначения когда исполняется userspace. Для этого стек (в частности) и нужен — сохранить регистры.

                                                                                И какой вывод вы из этого делаете?

                                                                                  0
                                                                                  Что жертвовать регистром общего назначения ради отказа от использования памяти на стеке — ошибка.
                                                                                    0
                                                                                    Я не знаю, что и где вы там обнаружили, но тот стек, на который указывает SP в userspace и тот стек, на который указывает SP в ядре — это разные стеки. Да, представьте себе — у процессора много регистров SP. И много стеков. Один регистр SP и один стек — это реальный режим, его перестали использовать до того, как большинство посетителей Хабре родились…
                                                                                      0
                                                                                      Да, представьте себе — у процессора много регистров SP. И много стеков. Один регистр SP и один стек — это реальный режим, его перестали использовать до того, как большинство посетителей Хабре родились…

                                                                                      Правильно ли я вас понимаю, что вы говорите не о переключаемых контекстах, а прямиком о нескольких hardware регистрах E®SP в x86/64?
                                                                                      Можно ссылку на эту информацию?
                                                                                        0
                                                                                        Несколько «настоящих» регистров существуют в ARM. В x86 регистр, строго говоря, один (на самом деле нет), но так как при возникновении прерывания он автоматически перезагружается из TSS, то говорить о том, что если мы его задействуем под «кучу», то он станет недоступен для прерываний — несколько глупо.
                                                                                          0
                                                                                          В x86 регистр, строго говоря, один (на самом деле нет)

                                                                                          Речь шла про x86/64.
                                                                                          Так один регистр стека хардварно, или нет?
                                                                                          Можно ссылку, откуда вы взяли информацию про несколько?
                                                                                            0
                                                                                            Так один регистр стека хардварно, или нет?
                                                                                            Архитектурно в x86 — он один. На уровне железа — их много. Но это совсем другая история.
                                                                                              +1
                                                                                              Архитектурно в x86 — он один. На уровне железа — их много. Но это совсем другая история.

                                                                                              Как многое можно еще придумать. Вспомнить m68K, CPU SMT/HT, многоядерность, виртуализацию… Смысл вопроса был, конечно, иной. Про количество регистров стека x86/64 с программной точки зрения (для одного, конечно же, ядра):
                                                                                              Да, представьте себе — у процессора много регистров SP. И много стеков. Один регистр SP и один стек — это реальный режим, его перестали использовать до того, как большинство посетителей Хабре родились…

                                                                                              С программной (втч системной) точки зрения, ядро x86/64 имеет единственный регистр стека, перезагружаемый в зависимости от уровня привилегий, событий, и выполнения задач. О случаях © «много регистров SP» всё же не известно…
                                                                                                –1
                                                                                                О случаях © всё же не известно…
                                                                                                Серьёзно?

                                                                                                Смысл вопроса был, конечно, иной. Про количество регистров стека x86/64 с программной точки зрения (для одного, конечно же, ядра):
                                                                                                Да, представьте себе — у процессора много регистров SP. И много стеков. Один регистр SP и один стек — это реальный режим, его перестали использовать до того, как большинство посетителей Хабре родились…
                                                                                                Заметьте, что в той цитате, которую вы столь старательно воспроизвели нет слов x86 — это вы их туда решили добавить. На самой популярной платформа (ARM, если вы вдруг последние 10 лет в коме провели) — регистров SP таки архитектурно не один и не два.

                                                                                                С программной (втч системной) точки зрения, ядро x86/64 имеет единственный регистр стека, перезагружаемый в зависимости от уровня привилегий, событий, и выполнения задач.
                                                                                                В разрезе обсуждаемой проблемы отличие этого варианта от «много регистров SP» (который, как бы вам ни хотелось обратного, тоже существует) — несущественно.
                                                                                                  0
                                                                                                  Я не сомневаюсь что в глобальном смысле все ок.
                                                                                                  Но иногда интересны только частности. Меня заинтересовало это:
                                                                                                  Один регистр SP и один стек — это реальный режим, его перестали использовать до того ...

                                                                                                  Т.е. «реальный режим» (real mode), который перестали использовать — это ARM. Если я вдруг последние 10 лет в коме провел, не затруднит ли вас дать мне ссылочку на режим ARM, который бы назывался real mode?

                                                                                                  А вот еще интересный вопрос касаемо «перестали использовать». В каком режиме современные CPU x86/64 производства 2018 года стартуют после power-on? (подмигивает)

                                                                                        +1
                                                                                        Если вы про TSS, эта структура находится в памяти.
                                                                                          –1
                                                                                          Плачь шёл про то, что если SP задействовать не под стек, а под что-то ещё, то прерывания невозможно будет обрабатывать.

                                                                                          Но прерывания в защищённой системе ну никак не могут обрабатываться на пользовательском стеке — иначе вся защита насмарку.

                                                                                          Загружается ли «системный» стек из памяти (x86, TSS) или из «теневого регистра» (ARM)… не принципиально.
                                                                                        0
                                                                                        Что жертвовать регистром общего назначения ради отказа от использования памяти на стеке — ошибка.

                                                                                        Поясните, почему?
                                                                                        С-но, выше вам уже ответили про то, что в реальности, на современных архитектурах и в современных ОС в один момент времени существует много разных стеков. И ничего не ломается.

                                                                              –1
                                                                              На дворе 2018й, а вы про реальный режим и MS DOS. Зачем заниматься некрофилией?
                                                                                0
                                                                                > Но без стека вы всё равно не переживёте, потому что первое же прерывание потребует куда-то «всё это» сохранить.

                                                                                Вот пример, как это совсем без аппаратно определённого стека делается на S/360 и её потомках вплоть до z/Arch:

                                                                                1. При приходе прерывания процессор сохраняет PSW (это, грубо говоря, IP + Flags) по фиксированному адресу, назовём X1 (зависящему от типа прерывания) и читает новое значение из другого фиксированного адреса (X2) для этого прерывания.

                                                                                2. Код по новому адресу в первую очередь сохраняет один регистр, например, R1, по фиксированному адресу X3 в памяти (позволяется абсолютная адресация от 0 до 4095 до S/390, и в пределах мегабайта — после), читает из X4 новое значение для R1 (пусть это X5), а затем одной командой STM сохраняет все остальные регистры по этому адресу (15 общих регистров => заняты адреса от X5 до X5+119).

                                                                                3. Теперь он свободен в использовании всех общих регистров, кроме R1. Юзерское значение R1 читается из X3 в любой другой регистр и пишется в область сохранения (например, по X5+120). Значение в X3 больше не нужно: это была одноразовая временная ячейка.

                                                                                Теперь по необходимости точно так же сохраняются регистры плавающей точки.

                                                                                4. Инициализируется обстановка для работы обработчика прерывания: при этом может создаваться и стек, если надо (много софта работает в таком режиме). В userland обычно стек адресуется через R13, операции доступа к нему просто пользуются доступом в формате регистр+смещение.

                                                                                5. Если требуется реентерабельность для прерывания, то выполняются дополнительные действия:
                                                                                1) сохранённый адрес возврата (в X1) кладётся на стек (или в аналог — это может быть область из динамической кучи);
                                                                                2) выделяется новая область сохранения и её адрес (новый X5) кладётся по адресу X4; точно так же, это выделение может быть и на стеке, и где-то в другом месте;
                                                                                3) разрешается прерывание в PSW (до этого оно должно было быть запрещено).

                                                                                Все описанные операции банальные и укладываются в десяток команд. При выходе из прерывания делается то же самое в обратном порядке. Финальной операцией является LPSWE — аналог iret, но с указанием, по какому адресу находится PSW для восстановления.
                                                                              0
                                                                              В ARM, например, регистр стека ничем не выделяется в этом смысле от других регистров, относительно которых можно адресоваться. (В AArch64 есть тонкости, что есть регистр 31 в данной команде, но я не об этом.) И есть много других подобных архитектур. Даже в PDP-11 особые свойства SP существенны только на переключениях уровней привилегий.
                                                                              Call и ret на многих RISC и не только (например, на z/Arch) делаются не через стек, а через регистр связи.
                                                                              И на x86 есть аргументы за использование смещения относительно esp/rsp вместо push/pop — так полностью делает текущий компилятор Go (в его выхлопе вы не найдёте ни одной push или pop); так делает GCC, если у целевого процессора плохо с оптимизацией последовательностей push/pop, как было в P4.
                                                                              Про pusha/popa лучше бы вообще не вспоминать, их сейчас не используют даже в ядре.
                                                                                0
                                                                                Про pusha/popa лучше бы вообще не вспоминать, их сейчас не используют даже в ядре.
                                                                                Как можно использовать команды, которых не существует??? Их выпилили при переходе на x86-64 (поддерживаются только в 32-битном режиме для совместимости и работают весьма медленно на современных CPU).
                                                                      0
                                                                      Вам надо двигать указатель на сам стек, что эквивалентно движению указателя в nurcery.
                                                                      Раз уж придираемся, то в случае стека мы двигаем значение в регистре, а в случае GC мы пишем в память, и скорее всего interlocked'ом — разница очень велика.
                                                                      При этом сброс nurcery происходит быстрее, чем сброс стека.
                                                                      С чего бы это вдруг? Копированием релевантных данных можно пренебречь?
                                                                      Если бы в том же хаскеле было не так а выделялись бы куски по стандартному new то оно бы по сути было неюзабельно.
                                                                      А кто заставляет использовать самый примитивный способ менеджмента памяти?
                                                                      в случае ФП, когда вам надо выделять огромное количество короткоживущих, «одноразовых» объектов (гигабайты в секунду), эта техника незаменима.
                                                                      Не эксперт в хаскеле и ФП, но насколько я знаю, функциональщина всегда stateless. Так зачем тогда в принципе что-либо кроме стековых аллокаторов?
                                                                        0
                                                                        Раз уж придираемся, то в случае стека мы двигаем значение в регистре, а в случае GC мы пишем в память

                                                                        Вообще-то стек — это часть памяти. Когда вы пишите в стек, вы тоже пишите в память. В ту же самую память. Другой нет.


                                                                        С чего бы это вдруг? Копированием релевантных данных можно пренебречь?

                                                                        Релевантных данных практически никогда нет, с-но нечего копировать.


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

                                                                        Ну, чтобы способ был не примитивный — вам надо реализовать алгоритм gc.


                                                                        Не эксперт в хаскеле и ФП, но насколько я знаю, функциональщина всегда stateless. Так зачем тогда в принципе что-либо кроме стековых аллокаторов?

                                                                        Ни зачем, мы же как раз и обсуждаем тот факт, что аллокация в nurcery и в стеке — это практически одно и то же.

                                                                          0
                                                                          Вообще-то стек — это часть памяти. Когда вы пишите в стек, вы тоже пишите в память. В ту же самую память. Другой нет.
                                                                          Я говорил про аллокацию/деаллокацию, а не про само использование. И кстати, это не точно та же память, а наиболее интенсивно используемая память, которая следовательно практически гарантировано будет в кэше.
                                                                          Релевантных данных практически никогда нет, с-но нечего копировать.
                                                                          А проверкой на то что их нет можно пренебречь? А если их нет, чем циклический аллокатор не подходит?
                                                                          Ну, чтобы способ был не примитивный — вам надо реализовать алгоритм gc.
                                                                          Ну GC — это как бэ не единственная альтернатива new/delete.
                                                                          Ни зачем, мы же как раз и обсуждаем тот факт, что аллокация в nurcery и в стеке — это практически одно и то же.
                                                                          Зачем тогда делать функциональную VM с использованием GC?
                                                                            0
                                                                            И кстати, это не точно та же память, а наиболее интенсивно используемая память, которая следовательно практически гарантировано будет в кэше.

                                                                            Поэтому nursing area рекомендуют брать под размер L2-кеша.

                                                                            Зачем тогда делать функциональную VM с использованием GC?

                                                                            Потому что статически распределить память в общем случае нельзя.
                                                                              0
                                                                              В каком смысле статически? Если в смысле того, что не понятно заранее, сколько выделять, то есть alloca. Если распределять между потоками, то кастомный стековый аллокатор и танцы с виртуальной памятью.
                                                                                0
                                                                                А, вы про это.

                                                                                Ну потому что стека тоже нет. Есть сворачивание графа.
                                                                              0
                                                                              И кстати, это не точно та же память, а наиболее интенсивно используемая память, которая следовательно практически гарантировано будет в кэше.

                                                                              Ну так и nursery будет в кеше.


                                                                              Я говорил про аллокацию/деаллокацию, а не про само использование.

                                                                              Вы, видимо не поняли. Еще раз — память под nursery выделяется рантаймом один единственный раз, при старте. После этого никаких аллокаций и деаллокаций (в смысле требования памяти у системы и возвращения ее системе) при работе с nursery не происходит. Происходит исключительно последовательная перезапись этого однажды выделенного куска памяти. Точно так же, как при записи в стек. Фактически, nursery — это и есть своего рода аналог стека.

                                                                                0
                                                                                Я говорю об аллокации/деалокации как о логической операции, а не как о вызове malloc/free или аналогичных API. При аллокации на стандартном стеке потока максимум, что может произойти — операция добавления к регистру. В описанной Вами модели при аллокации нужно как минимум модифицировать значение в памяти, а это намного дольше модификации регистра даже если каким то образом оно окажется в кэше. Уже на этом этапе GC проигрывает, а впереди еще собственно сборка мусора, которой на стеке нет вообще.
                                                                                  0
                                                                                  В описанной Вами модели при аллокации нужно как минимум модифицировать значение в памяти

                                                                                  Какое и зачем, в общем случае?
                                                                                    0
                                                                                    В описанной Вами модели при аллокации нужно как минимум модифицировать значение в памяти

                                                                                    Зачем? Точно так же инкрементируете регистр.


                                                                                    GC проигрывает, а впереди еще собственно сборка мусора, которой на стеке нет вообще.

                                                                                    Сборка мусора из nurcery — это просто изменение значения в регистре с текущего на начало nurcery.

                                                                              0
                                                                              Раз уж придираемся, то в случае стека мы двигаем значение в регистре, а в случае GC мы пишем в память, и скорее всего interlocked'ом — разница очень велика.

                                                                              Interlocked что? У каждого ядра свой кусок nursing area, не нужно думать о многопоточности.

                                                                              А так как всё иммутабельное, о многопоточности вообще думать не нужно.

                                                                              С чего бы это вдруг? Копированием релевантных данных можно пренебречь?

                                                                              Весь чанк уходит в из gen0 (который и есть nursing area) в gen1, под gen0 выделяется новый чанк, а с тем, ушедшим, потом большой параллельный GC в gen1 разберётся.

                                                                              Не эксперт в хаскеле и ФП, но насколько я знаю, функциональщина всегда stateless. Так зачем тогда в принципе что-либо кроме стековых аллокаторов?

                                                                              Конкретно в хаскеле есть, например, pinned memory для всяких bytestring, больших массивов и всего такого. Но в среднем да, об этом можно не заморачиваться и думать в терминах стекоподобных аллокаторов. Просто не на стеке в смысле как вам в сишечке, скажем, glibc выделит.

                                                                              Помогает скорее не stateless, а immutability.
                                                                                0
                                                                                > У каждого ядра свой кусок nursing area, не нужно думать о многопоточности.

                                                                                У ядра или треда?
                                                                                В первом случае, как решается вопрос при миграции треда на другое ядро?
                                                                              0
                                                                              В GC тоже ее нет. Один раз выделяется nursery (цельный кусок памяти), сохраняется указатель на его начало.

                                                                              Вам надо двигать указатель на сам стек, что эквивалентно движению указателя в nursery.

                                                                              вам уже указали разницу между увеличением регистра и указателем на блок, отмечу также, что там как минимум должна быть проверка на выход за границы nursery.
                                                                              но в случае ФП, когда вам надо выделять огромное количество короткоживущих, «одноразовых» объектов (гигабайты в секунду), эта техника незаменима.

                                                                              проблема не в том, чтобы много памяти выделять/освобождать, а в том, чтобы эту память инициализировать. Для ФП, завязанном на иммутабельности, данные либо постоянно копируются («гигабайты в секунду» эффективно не покопируешь), либо используются специальные COW структуры данных, с собственными накладными расходами. Компилируемым императивным языкам иммутабельность не нужна, и там можно вручную управлять памятью куда эффективнее, даже если она будет выделена через стандартный аллокатор
                                                                                0
                                                                                вам уже указали разницу между увеличением регистра и указателем на блок, отмечу также

                                                                                Нет, разницы нет.


                                                                                там как минимум должна быть проверка на выход за границы nursery.

                                                                                А в случае стека должна быть проверка на пробой стека.


                                                                                проблема не в том, чтобы много памяти выделять/освобождать, а в том, чтобы эту память инициализировать.

                                                                                Ну то есть просто не создавать новых объектов, тогда и память не понадобится. Но мы же немного не то сейчас обсуждаем.


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

                                                                                Управлять — да, а выделять и освобождать — нет.

                                                                                  0
                                                                                  Нет, разницы нет.
                                                                                  Разницы нет, пока вы не понимаете устройство современных процессоров.
                                                                                  А в случае стека должна быть проверка на пробой стека.
                                                                                  В стандартном стеке да, но кастомный стековый аллокатор можно сделать «бесконечным» с помощью виртуальной памяти.
                                                                                    0
                                                                                    Разницы нет, пока вы не понимаете устройство современных процессоров.

                                                                                    Ну расскажите мне про устройство современным процессоров в данном контексте.


                                                                                    В стандартном стеке да, но кастомный стековый аллокатор можно сделать «бесконечным» с помощью виртуальной памяти.

                                                                                    Тогда соответствующая проверка будет в логике этого аллокатора. Вы же не можете довыделить память под стек, не убедившись, что имеющаяся закончилась?

                                                                                      0
                                                                                      Ну расскажите мне про устройство современным процессоров в данном контексте.
                                                                                      Разница в том, модифицировать ли регистр, или память. Даже закэшированное значение модифицируется не бесплатно.
                                                                                      Тогда соответствующая проверка будет в логике этого аллокатора. Вы же не можете довыделить память под стек, не убедившись, что имеющаяся закончилась?
                                                                                      Вообще то могу) Просто проверки будут делаться на уровне ОС. Это делается правильным менеджментом виртуальной памяти. Правда, ОСшное выделение будет производиться по 4KB, что маловато, так что не факт, что такая экономия одного if'a того стоит.

                                                                                      Вообще, лично меня смущает то, что я так и не понял, чем именно простые стековые аллокаторы не подходят в функциональщине. Ведь по сути и речи не идет о том, что GC может быть лучше стека, лишь отстаивается то, что он может работать не сильно медленнее. Так почему бы не использовать стек, который заведомо не менее производительный, и гораздо более тривиальный в реализации?
                                                                                        0
                                                                                        Так почему бы не использовать стек, который заведомо не менее производительный, и гораздо более тривиальный в реализации?

                                                                                        Аллоцировать-то ладно. Как вы его освобождать будете?

                                                                                        Вы выделили на стеке место под объекты A и B, потом сделали объекты A' и B', ссылающиеся на A и B соответственно. В итоге в стеке у вас что? Скорее всего, A B A' B'? А теперь пусть у вас A' умер, а B' всё ещё нужен. Что делать?
                                                                                          +1
                                                                                          Разница в том, модифицировать ли регистр, или память.

                                                                                          В обоих случаях можно модифицировать регистр.


                                                                                          Вообще то могу) Просто проверки будут делаться на уровне ОС.

                                                                                          Ну, то есть не можете, т.к. ОС все равно их сделает :)


                                                                                          Вообще, лично меня смущает то, что я так и не понял, чем именно простые стековые аллокаторы не подходят в функциональщине.

                                                                                          nurcery — это и есть стек в фп. Но он не может быть смоделирован классическим стеком, т.к.:


                                                                                          1. из-за замыканий стек становится деревом фреймов, а не их списком
                                                                                          2. из-за лени он становится произвольным графом

                                                                                          в итоге вы не сможете освободить память прямым раскручиванием стека, если там окажутся достижимые данные.

                                                                                      0
                                                                                      Нет, разницы нет.

                                                                                      почитайте про инвалидацию кеша процессора
                                                                                      А в случае стека должна быть проверка на пробой стека.

                                                                                      делается на уровне железа.
                                                                                      Ну то есть просто не создавать новых объектов, тогда и память не понадобится. Но мы же немного не то сейчас обсуждаем.

                                                                                      Управлять — да, а выделять и освобождать — нет.

                                                                                      Хорошо, с другой стороны. Прикрутив джавовский или любой другой аллокатор к приложению на c++/rust, мы получаем ту же скорость выделения/освобождения (с теми же накладными по памяти), но меньше копируем данные
                                                                                        0
                                                                                        почитайте про инвалидацию кеша процессора

                                                                                        С точки зрения кеша в nursery все точно так же как со стеком.


                                                                                        делается на уровне железа.

                                                                                        Нет, не делается. Этим занимается ОС, т.к. именно ОС выделяет процессам стек.


                                                                                        Хорошо, с другой стороны. Прикрутив джавовский или любой другой аллокатор к приложению на c++/rust, мы получаем ту же скорость выделения/освобождения (с теми же накладными по памяти)

                                                                                        Ну, я, вроде, об этом и сказал — вы можете переизобрести (или использовать уже написанный) gc.

                                                                                          0
                                                                                          С точки зрения кеша в nursery все точно так же как со стеком.

                                                                                          Нет, не делается. Этим занимается ОС, т.к. именно ОС выделяет процессам стек.

                                                                                          Я про аппаратную поддержку. amarao вам уже про это писал
                                                                                          Ну, я, вроде, об этом и сказал — вы можете переизобрести (или использовать уже написанный) gc.

                                                                                          не путайте автоматическую сборку мусора с деаллокацией
                                                                                            0
                                                                                            Я про аппаратную поддержку. amarao вам уже про это писал

                                                                                            Ну аппаратная поддержка — это использование конструкций вроде pop/call/etc. Если вы их не используете, то и проблем от отсутствия аппаратной поддержки у вас нет.


                                                                                            не путайте автоматическую сборку мусора с деаллокацией

                                                                                            Я и не путаю.

                                                                                      0
                                                                                      отмечу также, что там как минимум должна быть проверка на выход за границы nursery.

                                                                                      Это уже есть в ОС в виде виртуальной памяти и page fault'ов.


                                                                                      Для ФП, завязанном на иммутабельности, данные либо постоянно копируются («гигабайты в секунду» эффективно не покопируешь), либо используются специальные COW структуры данных, с собственными накладными расходами.

                                                                                      Если вы в записи на 10 полей поменяли одно поле, то вам не нужно копировать все поля этой записи, вы просто создаёте новую запись с 9 старыми и одным новым указателем (это если без {-# UNPACK #-} всяких, но тогда вы знаете, что делаете).


                                                                                      Кроме того, если у вас есть tight loop с кучей ручной работы с памятью, вы всегда можете завернуть это в монаду ST, где компилятор снова вам гарантирует, что мутабельные ресурсы у вас не утекут наружу, и всё такое.

                                                                                      0
                                                                                      Хехе, всё почти ровно то же хотел написать.

                                                                                      Иммутабельность очень сильно помогает GC. А с небольшой ручной помощью рантайму в виде compact regions вообще чудеса случаются.

                                                                                      Если бы в том же хаскеле было не так а выделялись бы куски по стандартному new то оно бы по сути было неюзабельно.

                                                                                      Да, через nursing area там гигабайты проходят очень шустренько, +RTS -sstderr поначалу пугает. И оно всё из кеша может и не вылезать толком.
                                                                                        0
                                                                                        Иммутабельность очень сильно помогает GC.

                                                                                        Вообще, на практике с иммутабельностью в хаскеле дело несколько сложнее, чем "старые данные не указывают на новые", т.к. благодаря лени можно вязать узлы произвольной сложности (и при завязывании узла на низком уровне происходит мутация указателя). Но там уже дело за конкретными оптимизациями и эвристиками, так что концептуально это дела не меняет.

                                                                          +1
                                                                          А если разобрать несколько иначе (людоедо_едо_ед = тот, кто ест еду людоеда = собственно, людоед), то его обед это человек, а еда обеда — обычная человеческая еда. Которую ученая, изучающая людей, пригласила с очевидной целью — съесть. )
                                                                            0
                                                                            В таком случае вы промежуточно имеете разбиение людоедо_едоед, а слово «едоед» в русском языке отсутствует.
                                                                              0
                                                                              Формально да. При первом прочтении стишка у меня оно в голове само построилось по аналогии с «мясоед» и подобными.
                                                                              +8
                                                                              Вполне может быть, что людоед — лев, людоедоед — блоха, людоедоедоед — лягушка.
                                                                              Тогда людоедоедоед != людоеду.
                                                                              Ну а энтомолог Иванова пригласила льва, чтобы посчитать блох ;)
                                                                                0
                                                                                Блоха львов всё же не ест. Так, надкусывает.
                                                                                  0
                                                                                  «Любую проблему можно решить путём введения дополнительного уровня абстракции, кроме проблемы слишком большого количества уровней абстракции»
                                                                                +2
                                                                                А в чем парадокс?
                                                                                  0
                                                                                  людоедоедоеда», нам нужно произвести лингвистический анализ последнего слова. Проще всего это сделать, читая корни справа налево:

                                                                                  Людоед = тот, кто ест людей.
                                                                                  Людоедоед = тот, кто ест людоедов = тот, кто ест тех, кто ест людей.

                                                                                  Простите, но сразу стало непонятно. Самый правый корень "ед". Может слева направо?

                                                                                    0
                                                                                    Как раз справа налево. Правый корень «ед» заменяем на фразу «тот, кто ест», словарная основа остаётся. Также как «T*» читается как «указатель на T», то есть, справа налево.
                                                                                      +1

                                                                                      Вы сейчас пытаетесь объяснить рекурсивно, через указатели :). Я же говорю о логике объяснения в статье.
                                                                                      Если мы разбиваем слово людоедоедоед, тогда первая строчка (по Вашему описанию) должна быть


                                                                                      1. людоедоедоед = людоедоедо (лево) + ед (право)
                                                                                        То есть у вас словесный алгоритм не соответствует написанному коду. А для вот таких вот объяснений-аналогий это как раз самое важное.
                                                                                        0
                                                                                        Вы имеете в виду, что строки в другом порядке должны быть? Так эти строки — не пошаговое выполнение метода, а просто иллюстрация его на всё более сложных примерах.
                                                                                      +3
                                                                                      Забудьте. Гораздо проще разобрать эту загадку, используя указатели из C, чем наоборот.
                                                                                      +18

                                                                                      А что, обьяснения, что указатель — это адрес в памяти, где лежит объект не достаточно? Подход в статье ну совсем какой-то мутный.

                                                                                        0
                                                                                        Кому-то достаточно. Лингвистическая аналогия — исключительно для тех, кто не понял с первого раза.
                                                                                          +5
                                                                                          подавляющее большинство с первого раза не поймет ни сухое объяснение через адреса/номера ячеек, ни тем более вашу эм… аналогию. ~90% — визуалы, и объяснять в большинстве случаев надо через рисунок; остальные же редко идут в точные науки, требующие пространственного мышления.
                                                                                            +3

                                                                                            А если непонимающему просто дать задачу, где указатели реально нужны и он сам придет к их необходимости.
                                                                                            Мне кажется, нет смысла объяснять указатели дальше одного уровня.
                                                                                            Вещи типа TObject* objects[] должны как-то сами приходить.

                                                                                              0
                                                                                              Я и говорю: нужен щелчок.
                                                                                            +4
                                                                                            Нет конечно, отсюда и все эти бесконечные статьи. Указатель — это переменная, содержащая адрес, а не сам адрес. Упрощая, вы вводите новичка в заблуждение. Отсюда всякие непонятки с арифметикой над указателями и пр. ((int*)55555+1 = 55563 на 64-х битных платформах). Лучше сказать так: указатель — это некая абстракция над местоположением некоторой сущности в памяти (зависит от реализации, это может быть вообще какой-то дескриптор на экзотических архитектурах, а на интелах — это смещение внутри сегмента, даже здесь не назовешь это просто адресом).
                                                                                              +1
                                                                                              На самом деле как ни говори, а проблема в том, что указатель — это вещь, которая объединяет несколько разных сущностей, ни об одной из которых новочёк понятия не имеет. Вот все эти «адреса», «память» и прочее — для него «тёмный лес и куча дров».

                                                                                              Лучшее, что я видел — это «отодвинуть» изучение указателей за ту точку, когда человек уже знает для чего они нужны.

                                                                                              То есть вначале мы изучаем массивы, структуры, дальше изучаем алгоритмы (деревья, очереди с приоритетами). А потом, когда человек уже привык оперировать с индексами, которые указывают на ячейки, в которых тоже лежат индексы — объяснить ему, что указатель — это такой «синтаксический сахар» для большого массива с названием «опереативная память» — дело пяти минут.

                                                                                              И всё. И нет никакой магии и никакого «щелчка» в голове, всё буднично и банально.
                                                                                                0
                                                                                                подскажите, как сделать дерево без указателей?
                                                                                                  +3
                                                                                                  Пр изучении программирования деревья (да и списки, стеки, деки, очереди) обычно вводят на базе массива. Заодно показывается принцип сборки мусора.
                                                                                                    0
                                                                                                    Это не «обычно». Это «как надо». Потому что «обычно» стремяться перескочить через все «скучные» вещи и научить какие-нибудь картинки рисовать. Или web-страничку генерировать.

                                                                                                    Почему-то никого не удручает тот факт, что для того, чтобы научиться рассказы писать нужно потратить не один год, рисуя палочки и изучая как подлежащее со сказуемым согласуется.

                                                                                                    А потратить пару месяцев на то, чтобы понять как устроены базовые, простейшие структуры данных (и на их основе понять как работают указатели и рекурсия) — нам влом.
                                                                                                      +1
                                                                                                      Да даже через русский язык стремятся перескочить, благо там «собирается» даже с ошибками.
                                                                                                    +1
                                                                                                    Бинарное дерево без указателей, на массиве длиной в 2^n, описано у Кнута, ЕМНИП. Там примерно так: в массиве лежит по индексу 1 корневой элемент, потом оба его дочерние, за ними — 4 их дочерних, и т.д. Нулевой и отсутствующие элементы помечаются как пустые. Для элемента по индексу idx: переход к родителю — idx/2, к левому/правому потомку — 2*idx и 2*idx+1. В каких-то (редких?) случаях так даже может быть экономнее и быстрее, чем на указателях. Disclaimer: я сам всегда на указателях деревья строю, но из песни слова не выкинешь)
                                                                                                      +1
                                                                                                      То, что вы описали — это то, как реально устроена куча. Тоже интересный вариант, но для обычного дерева — очень плохой, если у вас там дерево не сбалансировано потеряете кучу места. Для реализации очередей с приоритетами — то, что доктор прописал.
                                                                                                        0
                                                                                                        Вот поэтому я и написал, что в редких случаях. Если дерево заполняется так, что перебалансировка не происходит, оно (почти) полностью заполнено, и используется только для поиска элементов, то поиск может быть довольно быстрым, за счет высокой локальности — промахов процессорного кэша будет поменьше, чем для разбросанного в памяти дерева на указателях.
                                                                                                          +1
                                                                                                          за счет высокой локальности — промахов процессорного кэша будет поменьше, чем для разбросанного в памяти дерева на указателях.
                                                                                                          Вот только никакой локальности в этом представлении нет и в помине, так что реально выигрыш происходит только за счёт экономии памяти.
                                                                                                            0
                                                                                                            Поясните?
                                                                                                              +2
                                                                                                              При обработке деревьев, как правило, нужно переходить к левому и правому потомкам, иногда наверх. И крайне редко — к «соседу» слева или справа. А при хранении дерева как вы описали — близко расположены именно «соседи», а полезные ячейки (все три) — очень и очень далеко. На таком дереве разве что «поиск в ширину» хорошо организовывается.
                                                                                                                0
                                                                                                                Я писал про поиск — там только сверху вниз, и чем ближе элемент к корню, тем чаще по нему бегается; но чем ближе к корню, тем компактнее они размещены. Соответственно, в кэш попадает меньше мусора, и в результате он будет использоваться лучше, чем при размазанной структуре. Но если дерево сильно больше размеров кэша, эффект будет невелик, да.
                                                                                                                  0
                                                                                                                  Это интересное замечание, но, боюсь, неиспользуемые ноды засорят кеш. Хотя, да, было бы неплохо провести исследование. C AVL деревьями даже, может, какой-то выигрыш будет. С красно-чёрными — вряд ли…
                                                                                                                    0

                                                                                                                    Если надо, то можно сделать под дерево кастомный аллокатор и обеспечить себе любую требуемую локальность, вообще говоря. Так что особо не важно что там и как сорит.

                                                                                                                      0
                                                                                                                      Если бы вы удосужились прочитать про то, что тут обсужадется, то вы бы поняли, что никакой аллокатор ничего не изменит, так как ему всё равно придётся выделать память одним куском по условию задачи.
                                                                                                                        0

                                                                                                                        Не обязательно большим куском, можно кусками поменьше. Сборщики мусора же как-то работают.

                                                                                                                          0
                                                                                                                          Сборщики мусора работают за счёт дополнительной информации. А если вы вы всё-таки заглянули в начало дискуссии, вместо того, чтобы бредить, то обнаружили бы, что обсуждается хранение дерева, когда ссылки left и right отсутствуют, являются виртуальными…
                                                                                                                            0

                                                                                                                            Вы уже сами запутались. Давайте по порядку:


                                                                                                                            1. Если дерево сбалансировано, то вы можете выделить элементы любом наперед заданном порядке и расположить их последовательно, обеспечив локальность для любого наперед заданного метода обхода. Не важно со ссылками или без.
                                                                                                                            2. Если дерево несбалансировано, то вы так же можете выделить ноды в любом наперед заданном порядке и расположить их последовательно, обеспечивая локальность, но уже используя указатели, чтобы компенсировать "дырки". Толку от неиспользования указателей в этом случае нет, т.к вам "дырки" сожрут всю сэкономиленную память.
                                                                                                    +1
                                                                                                    Очень просто. Заводите массив размером с максимальное количество элементов в этом дереве. Вместо указателей — индексы.

                                                                                                    На самом деле проще всего начать с такой структуры данных, как «ассоциативный массив» на базе хеш-функции.

                                                                                                    Вначале — простой массив пар «ключ/значение», в случае если случаются коллизии… у нас беда.

                                                                                                    Потом — начинаем записывать в соседние ячейки… и на какое-то время можно на этом продержаться.

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

                                                                                                    Ну а после этого — можно уже и деревья устроить.
                                                                                                  0
                                                                                                  Вы уверены, что 55555 и 55563 — допустимые значения для адреса целого в ILP64 системах?! ;)
                                                                                                    0
                                                                                                    На большинстве современных процессоров — да. Но на Alpha, почившей в бозе — нет.
                                                                                                      0
                                                                                                      SPARK64? POWER*?