Comments 244
А может это и не плохо?
Java хороший пример. (Да, знаю что можно использовать ссылки)
Представьте, что вы веган, что бы вы говорили людям?
Все мои потуги что-то написать напоминают мне попытки забить шуруп молотком. У моих объектов в программах есть состояния, которые надо хранить — и то, что я прочел о ф-ных языках напоминает мне костыли.
Ну так естественно в этом случае у вас будет ощущение забивания шурупом молотка. Функциональщина нужна не за тем, чтоб описывать состояние, а за тем, чтобы состояния не было.
Мои проги пишутся для реального мира — embedded.
Тогда вам точно функциональщина не нужна. Ее смысл в итоге сводится к декларативности (вместо того, чтобы описывать процесс получения результата, описываем сам результат, а уже компуктер догадается, как его получить). В embedded вам нужно описывать процесс by design.
Неа. Если достаточно упороться монадками, то наступает просветление и понимание, что чистоты нет, стейта нет, эффектов нет, потому что это сами по себе не дискриминирующие термины.
Ну так стейта нет — это то, о чем я и говорю. Если же у вас стейт есть, и вы пытаетесь его делать на ФП — то что-то не так. В смысле самого мышления.
Не вижу препятствий в eDSL для этого эмбеддеда (см. вышеупомянутый Ivory), статически тайпчекаемого и верифицируемого, описывающего при этом вполне императивный процесс.
Только DSL и верификация ортогональны функциональному программированию. Вообще, конечно, термин сейчас сильно размыт и следует по-хорошему уточнять, что под фп подразумевается. Я подразумеваю в базе чистую лямбда с надстройками. То есть какой-нибудь Scheme без макросов — сферическое ФП в вакууме.
Вот вы fold или unfoldr делаете, аккумулятор — это стейт?
Стейт — это не то, что в коде написано, а то, как код воспринимается (от кода при этом может зависит насколько сложно описываемые им вещи рассматривать в рамках той или иной парадигмы). Если вы рассуждаете об аккумуляторе фолда как о стейте — это стейт. Если нет — то нет. Аналогично с монадами. Если вы монадический код в IO воспринимаете как просто императивный код — ну, у вас тут стейт.
ФП такого толку — это про типы, ИМХО. Лямбда-исчисление я вам и на плюсах замутить могу.
А можно типы в императивщину добавить. И верифицировать. Или верифицировать без типов. Все-таки тут речь надо вести не просто о типах, а об определенном способе мышления и использования этих типов. В этом контексте правильно говорить не "фп — это когда есть А и Б", а, скорее, "фп — это когда нету А и Б" (и аналогично для любой другой парадигмы). Потому что именно отсутствие альтернатив вынуждает строить программу и рассуждать о ней определенным способом. Наличие же фич — лишь дает возможность.
Одно и то же можно сказать разными способами. То, что можно сказать в ФП, можно сказать и в ООП. И наоборот.
Есть ЯП в которых нет объектов.
Но это не мешает в них объекты использовать, моделируя на имеющихся примитивах. Точно так же как в ООП нет функций, но вы можете их использовать, моделируя при помощи объектов.
Нет, если по парадигмам, то это ближе всего к ФП, наверное. От ООП там вроде и вовсе ничего нету.
К тому что массивы еще как то в объекты собрать можно, а вот функции нет. На уровне компилятора. И классы кстати тоже
Можно, т.к. язык тьюринг-полный. Только, думаю, кодировка вам откровенно не понравится :)
Ждет пакет инфы с радиоэфира. По получении должен сделать то, потом то, все со строгой времянкой и в зависимости от состоянии кучи датчиков. Как тут описать результат — непонятно.
Ну видите, "должен сделать" — это уже не ФП. С точки зрения ФП — будет понятие некоего абстрактного действия. Вы можете создать действие, скомбинировать это действие вместе с какими-то другими действиями каким-то способом и получить новое действие. Пакет инфы и показания датчиков — это данные. Вы описываете, действие какого вида должно получится из каких данных, то есть описываете ф-ю (в математическом смысле) perform: Data -> Action, при этом не специфицируете, как эту ф-ю требуется вычислять. Далее вы можете ввести какие-то проверки на тот факт, что построенный на указанных данных Action удовлетворяет определенным условиям, например, у вас есть ф-я time Action -> int и вам надо убедиться, что time(perform(data)) < n. При этом если вы свой Action составляли из других экшонов при помощи некоторых комбинаторов, то у вас могут быть разные утверждения вроде (time(action1) = a, time(action2) = b => time(sequence(action1, action2)) = a + b); Вот если вы так все будете воспринимать — вы пишете на фп, при этом в качестве языка можете хоть сишку использовать.
боюсь что просмотр итогового кода (в дизасме) может привести к инфаркту, не?
Ну почему? Вы же можете выбрать комбинаторы близкие по смыслу к композиции существующих блоков кода на асме. В пределе — вообще совпадающими, тогда рассматриваемая штука будет просто средой метапрограммирования над асмом.
Что это даёт? Подобные функции не зависят ни от чего, кроме как своих входных параметров. И поэтому, если каждый раз перезапускать их с одними и теми же аргументами, мы будем получать на выходе один и тот же результат.
Эмбедщику можно это понять так, что данные словно бы передаются в регистрах, и в регистрах же возвращаются назад, ничего более не меняя.
Это очень удобно и для отладки и для написания стабильных программ — проблемы отладки чаще всего заключаются в том что при работе программы меняется какое-то внутреннее состояние (память, переменные, стек итд) и нет возможности сделать «шаг назад». А при ФП парадигме — достаточно подать на «вход» программы одни и те же предварительно записанные данные, и она выдаст один и тот же результат, пока мы не поправим саму программу.
Парадигма такова, что программа как бы «воздействует» на проходящие через нее данные или их потоки, сама же являя собой «чистый закон».
Что интересно, правильная и рекомендуемая методология *NIX программирования это, в некотором смысле, ФП: мелкие отдельные утилиты, каждая выполняющая свою функцию, принимающие данные на вход, и выдающие детерминированно одно и то же, при том что их можно объединять друг за другом, т.е. выход одной утилиты/команды по-цепочке передавать на вход другой.
Пиксельные шейдеры тоже при определенном приближении являют собой ФП-стиль, вместе с реактивным.
Часть существующих программ и так уже написана приближаясь к функциональному стилю.
Реальное ФП, конечно, подразумевает собой гораздо большее, но кое-какие полезные элементы почерпнуть из ФП, как видим, можно.
То есть я могу примерно это представить, но совершенно не понимаю, как в ФП реализуется что-то асинхронное, завязанное на время, возникающее от случая к случаю…
В ФП функции — это тоже данные. С-но, действия, процессы, которые при помощи каких-то примитивов комбинируются в их наборы, ивент лупы с хендлерами и любые подобные вещи — это все данные.
Спасибо, достаточно понятно объяснили, хотя реальная применимость мне пока туманна.Важным преимуществом ФП является параллелизм. Поскольку все функции для вычислений используют только свои параметры, можно организовать вычисление независимых функций в произвольном порядке или параллельно, на результат вычислений это не повлияет. Следование элементам ФП-парадигмы упрощает построение многозадачности (в т.ч. для 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, при этом можно будет заметить что переданные аргументы (втч данные по указателям/ссылкам) не модифицируются. Будет заметна однократная инициализация без пере-присваивания. Повторюсь, это в самом общем, генеральном смысле, не погружаясь в явные отличия которые порождают компиляторы и их оптимизации.
Как это, а Ptr/ForeignPtr/StablePtr? ;)
Вот надо в картинке изменить пару пикселей — не создавать же полную её копию?
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
В зависимости от того, как сложатся звезды у вас первое сравнение в примере со String может выдать true.
А может и false.
ideone.com/BkxRUq
Дело в том, что компилятор одинаковые строковые константы в пределах класса может записывать в class-файл как одну константу (и делает это в данном частном случае). По ссылке из комментария выше это и происходит.
Не так страшны указатели, как их арифметика.
Правильный подход: богатая система типов, запрещающая творить фигню (Rust!), но сохраняющая указатели в полном объёме.
Теоретически, языки более высокого уровня могут позволить применить гораздо более эффективные оптимизации, вроде многопоточности или вообще — менять применяемый алгоритм по мере накопления данных прямо во время выполнения.
менять применяемый алгоритм по мере накопления данных прямо во время выполнения
Чем JVM уже некоторое время успешно занимается.
Основная же проблема в том, что GC всё равно должен «узнать» о том, что объект больше не нужен. Если это решение принимается в runtime, да ещё и асинхронно с приложением, то это плохо.
При работе с переменными на стеке нет аллокации и деаллокации.
В GC тоже ее нет. Один раз выделяется nursery (цельный кусок памяти), сохраняется указатель на его начало. Когда рантайму нужна память, то возвращается текущее значение указателя и сам указатель смещается на величину, которая, с-но, требуется для выделения. После исчерпывания nursery указатель просто сбрасывается на начало и процесс повторяется.
И даже указатель на стеке двигать не надо — lifetimes определяют размер области на стеке на этапе компиляции (я про Rust).
Вам надо двигать указатель на сам стек, что эквивалентно движению указателя в nursery. При этом сброс nursery происходит быстрее, чем сброс стека. Именно по-этому без кастомных аллокаторов с той же логикой вы никогда не достигнете в расте той же скорости работы с памятью, что и в, например, хаскеле.
Основная же проблема в том, что GC всё равно должен «узнать» о том, что объект больше не нужен.
В определенных предположениях можно гарантировать что объекты в nursery недостижимы, с-но ничего узнавать не надо, просто сбрасываем указатель на начало и все (при этом все объекты так и остаются в nursery но они потом перезапишутся). Это не очень хорошо работает в случае, например, ООП, но в случае ФП, когда вам надо выделять огромное количество короткоживущих, "одноразовых" объектов (гигабайты в секунду), эта техника незаменима. Если бы в том же хаскеле было не так а выделялись бы куски по стандартному new то оно бы по сути было неюзабельно.
А каким образом GC знает, где один кусок начинается, а где заканчивается? Где-то же нужно будет записать объект в список, либо использовать какие-то дополнительные пометки, иначе каким образом GC может перенести выживший объект дальше?
Смысл в том, что поскольку у вас практически никогда нет выживших объектов, то и переносить ничего не приходится. При этом определить, что выживших объектов нет, очень просто — поскольку данные иммутабельны, то более молодые данные могут ссылаться на более старые, но более старые не могут ссылаться на более новые. Если в текущем контексте нет ссылок на другие объекты в nurcery, значит, все, что левее — недоступные данные.
В том случае, когда ссылки есть — конечно, приходится проводить скан дальше и перемещать данные в основную память. Но это, еще раз, происходит очень редко.
Когда у вас происходит аллокация на стеке, то смещения на стеке (относительно SP) уже захардкожены компилятором в программу.
В функциональном рантайме все точно так же, у вас в хипе хранятся стекфреймы, относительно начала которых указываются смещение. И вам никто даже не мешает использовать SP в качестве регистра для хранения указателя.
В контексте nursery — это всё равно heap, а heap означает, что программа работает с динамическим указателем.
А чем по-вашему стек отличается от выделенного в хипе куска памяти, указатель на который лежит в SP?
Любые операции с heap'ом требуют использовать адрес heap'а. Его можно хранить либо в регистре общего назначения (программисты любят раскидываться регистрами общего назначения), либо в переменной — т.е. в памяти.
Хранить указатель на heap в SP — это восхитительно. call и ret как делать тогда?
Стек от выделенного куска в heap'е отличается тем, что положение ячейки памяти в heap'е не определено в compile time, а в хороших языках программирования, вроде Rust, смещение относительно SP точно известно. Сам же стек обслуживается процессором, быстрее, чем обычные операции с памятью (аппаратная поддержка).
Когда указатели в других объектах, их надо писать и читать (указатели) — это обращения к памяти. Чтение по фиксированному смещению от SP всегда быстрее, чем heap->data, потому что само значение heap тоже надо прочитать.
Чтение по фиксированному смещению от SP всегда быстрее, чем heap->data
А зачем читать heap->data, если можно читать register->data?
на i386 на вас конкретно обидятся.
Почему i386, а не БЭСМ-1? Ну и на самом деле всегда можно использовать сам SP.
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 не вижу.
А какое отношение данный список имеет к предмету разговора? Вдруг у меня вот свой личный список без i386-х смердящих и с БЭСМами бодрящими!
Он же ничем не хуже вашего списка из ряда архитектур, выбранных случайным образом.
Стек от выделенного куска в heap'е отличается тем, что положение ячейки памяти в heap'е не определено в compile time, а в хороших языках программирования, вроде Rust, смещение относительно SP точно известно.
Положение аргументов относительно стекфрейма тоже известно в компайлтайме.
Сам же стек обслуживается процессором, быстрее, чем обычные операции с памятью (аппаратная поддержка).
Какая аппаратная поддержка? Стек — это обычная область памяти, которую ОС выделяет процессу. Неизвестно положение стекфрейма. Но оно и в расте неизвестно.
Аппаратная поддержка — это SP, call, ret, popa, pusha, pop и push инструкции.
С-но, если вы не используете call, ret, push, pop, то вам и не нужна эта аппаратная поддержка.
Но без стека вы всё равно не переживёте, потому что первое же прерывание потребует куда-то «всё это» сохранить.
Сохраняйте. В чем проблема? Вам же никто не запрещает стек использовать.
а его аналог потребует пожертвовать одним из регистров.
Что, вообще говоря, не проблема.
в этой ситуации вы не можете использовать SP для другого (прерывания), а его аналог потребует пожертвовать одним из регистров.
Почему не могу? ОС же как-то использует и регистрами не жертвует.
и
www.youtube.com/watch?v=nc2q4OOK6K8
Ос не использует никакие регистры общего назначения когда исполняется userspace. Для этого стек (в частности) и нужен — сохранить регистры.
Ос не использует никакие регистры общего назначения когда исполняется userspace. Для этого стек (в частности) и нужен — сохранить регистры.
И какой вывод вы из этого делаете?
Да, представьте себе — у процессора много регистров SP. И много стеков. Один регистр SP и один стек — это реальный режим, его перестали использовать до того, как большинство посетителей Хабре родились…
Правильно ли я вас понимаю, что вы говорите не о переключаемых контекстах, а прямиком о нескольких hardware регистрах E®SP в x86/64?
Можно ссылку на эту информацию?
В x86 регистр, строго говоря, один (на самом деле нет)
Речь шла про x86/64.
Так один регистр стека хардварно, или нет?
Можно ссылку, откуда вы взяли информацию про несколько?
Так один регистр стека хардварно, или нет?Архитектурно в x86 — он один. На уровне железа — их много. Но это совсем другая история.
Архитектурно в x86 — он один. На уровне железа — их много. Но это совсем другая история.
Как многое можно еще придумать. Вспомнить m68K, CPU SMT/HT, многоядерность, виртуализацию… Смысл вопроса был, конечно, иной. Про количество регистров стека x86/64 с программной точки зрения (для одного, конечно же, ядра):
Да, представьте себе — у процессора много регистров SP. И много стеков. Один регистр SP и один стек — это реальный режим, его перестали использовать до того, как большинство посетителей Хабре родились…
С программной (втч системной) точки зрения, ядро x86/64 имеет единственный регистр стека, перезагружаемый в зависимости от уровня привилегий, событий, и выполнения задач. О случаях © «много регистров SP» всё же не известно…
О случаях © всё же не известно…Серьёзно?
Смысл вопроса был, конечно, иной. Про количество регистров стека x86/64 с программной точки зрения (для одного, конечно же, ядра):Заметьте, что в той цитате, которую вы столь старательно воспроизвели нет слов x86 — это вы их туда решили добавить. На самой популярной платформа (ARM, если вы вдруг последние 10 лет в коме провели) — регистров SP таки архитектурно не один и не два.
Да, представьте себе — у процессора много регистров SP. И много стеков. Один регистр SP и один стек — это реальный режим, его перестали использовать до того, как большинство посетителей Хабре родились…
С программной (втч системной) точки зрения, ядро x86/64 имеет единственный регистр стека, перезагружаемый в зависимости от уровня привилегий, событий, и выполнения задач.В разрезе обсуждаемой проблемы отличие этого варианта от «много регистров SP» (который, как бы вам ни хотелось обратного, тоже существует) — несущественно.
Но иногда интересны только частности. Меня заинтересовало это:
Один регистр SP и один стек — это реальный режим, его перестали использовать до того ...
Т.е. «реальный режим» (real mode), который перестали использовать — это ARM. Если я вдруг последние 10 лет в коме провел, не затруднит ли вас дать мне ссылочку на режим ARM, который бы назывался real mode?
А вот еще интересный вопрос касаемо «перестали использовать». В каком режиме современные CPU x86/64 производства 2018 года стартуют после power-on? (подмигивает)
Но прерывания в защищённой системе ну никак не могут обрабатываться на пользовательском стеке — иначе вся защита насмарку.
Загружается ли «системный» стек из памяти (x86, TSS) или из «теневого регистра» (ARM)… не принципиально.
Что жертвовать регистром общего назначения ради отказа от использования памяти на стеке — ошибка.
Поясните, почему?
С-но, выше вам уже ответили про то, что в реальности, на современных архитектурах и в современных ОС в один момент времени существует много разных стеков. И ничего не ломается.
Вот пример, как это совсем без аппаратно определённого стека делается на 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 для восстановления.
Call и ret на многих RISC и не только (например, на z/Arch) делаются не через стек, а через регистр связи.
И на x86 есть аргументы за использование смещения относительно esp/rsp вместо push/pop — так полностью делает текущий компилятор Go (в его выхлопе вы не найдёте ни одной push или pop); так делает GCC, если у целевого процессора плохо с оптимизацией последовательностей push/pop, как было в P4.
Про pusha/popa лучше бы вообще не вспоминать, их сейчас не используют даже в ядре.
Вам надо двигать указатель на сам стек, что эквивалентно движению указателя в nurcery.Раз уж придираемся, то в случае стека мы двигаем значение в регистре, а в случае GC мы пишем в память, и скорее всего interlocked'ом — разница очень велика.
При этом сброс nurcery происходит быстрее, чем сброс стека.С чего бы это вдруг? Копированием релевантных данных можно пренебречь?
Если бы в том же хаскеле было не так а выделялись бы куски по стандартному new то оно бы по сути было неюзабельно.А кто заставляет использовать самый примитивный способ менеджмента памяти?
в случае ФП, когда вам надо выделять огромное количество короткоживущих, «одноразовых» объектов (гигабайты в секунду), эта техника незаменима.Не эксперт в хаскеле и ФП, но насколько я знаю, функциональщина всегда stateless. Так зачем тогда в принципе что-либо кроме стековых аллокаторов?
Раз уж придираемся, то в случае стека мы двигаем значение в регистре, а в случае GC мы пишем в память
Вообще-то стек — это часть памяти. Когда вы пишите в стек, вы тоже пишите в память. В ту же самую память. Другой нет.
С чего бы это вдруг? Копированием релевантных данных можно пренебречь?
Релевантных данных практически никогда нет, с-но нечего копировать.
А кто заставляет использовать самый примитивный способ менеджмента памяти?
Ну, чтобы способ был не примитивный — вам надо реализовать алгоритм gc.
Не эксперт в хаскеле и ФП, но насколько я знаю, функциональщина всегда stateless. Так зачем тогда в принципе что-либо кроме стековых аллокаторов?
Ни зачем, мы же как раз и обсуждаем тот факт, что аллокация в nurcery и в стеке — это практически одно и то же.
Вообще-то стек — это часть памяти. Когда вы пишите в стек, вы тоже пишите в память. В ту же самую память. Другой нет.Я говорил про аллокацию/деаллокацию, а не про само использование. И кстати, это не точно та же память, а наиболее интенсивно используемая память, которая следовательно практически гарантировано будет в кэше.
Релевантных данных практически никогда нет, с-но нечего копировать.А проверкой на то что их нет можно пренебречь? А если их нет, чем циклический аллокатор не подходит?
Ну, чтобы способ был не примитивный — вам надо реализовать алгоритм gc.Ну GC — это как бэ не единственная альтернатива new/delete.
Ни зачем, мы же как раз и обсуждаем тот факт, что аллокация в nurcery и в стеке — это практически одно и то же.Зачем тогда делать функциональную VM с использованием GC?
И кстати, это не точно та же память, а наиболее интенсивно используемая память, которая следовательно практически гарантировано будет в кэше.
Ну так и nursery будет в кеше.
Я говорил про аллокацию/деаллокацию, а не про само использование.
Вы, видимо не поняли. Еще раз — память под nursery выделяется рантаймом один единственный раз, при старте. После этого никаких аллокаций и деаллокаций (в смысле требования памяти у системы и возвращения ее системе) при работе с nursery не происходит. Происходит исключительно последовательная перезапись этого однажды выделенного куска памяти. Точно так же, как при записи в стек. Фактически, nursery — это и есть своего рода аналог стека.
В описанной Вами модели при аллокации нужно как минимум модифицировать значение в памяти
Зачем? Точно так же инкрементируете регистр.
GC проигрывает, а впереди еще собственно сборка мусора, которой на стеке нет вообще.
Сборка мусора из nurcery — это просто изменение значения в регистре с текущего на начало nurcery.
В GC тоже ее нет. Один раз выделяется nursery (цельный кусок памяти), сохраняется указатель на его начало.
…
Вам надо двигать указатель на сам стек, что эквивалентно движению указателя в nursery.
вам уже указали разницу между увеличением регистра и указателем на блок, отмечу также, что там как минимум должна быть проверка на выход за границы nursery.
но в случае ФП, когда вам надо выделять огромное количество короткоживущих, «одноразовых» объектов (гигабайты в секунду), эта техника незаменима.
проблема не в том, чтобы много памяти выделять/освобождать, а в том, чтобы эту память инициализировать. Для ФП, завязанном на иммутабельности, данные либо постоянно копируются («гигабайты в секунду» эффективно не покопируешь), либо используются специальные COW структуры данных, с собственными накладными расходами. Компилируемым императивным языкам иммутабельность не нужна, и там можно вручную управлять памятью куда эффективнее, даже если она будет выделена через стандартный аллокатор
вам уже указали разницу между увеличением регистра и указателем на блок, отмечу также
Нет, разницы нет.
там как минимум должна быть проверка на выход за границы nursery.
А в случае стека должна быть проверка на пробой стека.
проблема не в том, чтобы много памяти выделять/освобождать, а в том, чтобы эту память инициализировать.
Ну то есть просто не создавать новых объектов, тогда и память не понадобится. Но мы же немного не то сейчас обсуждаем.
Компилируемым императивным языкам иммутабельность не нужна, и там можно вручную управлять памятью куда эффективнее, даже если она будет выделена через стандартный аллокатор
Управлять — да, а выделять и освобождать — нет.
Нет, разницы нет.Разницы нет, пока вы не понимаете устройство современных процессоров.
А в случае стека должна быть проверка на пробой стека.В стандартном стеке да, но кастомный стековый аллокатор можно сделать «бесконечным» с помощью виртуальной памяти.
Разницы нет, пока вы не понимаете устройство современных процессоров.
Ну расскажите мне про устройство современным процессоров в данном контексте.
В стандартном стеке да, но кастомный стековый аллокатор можно сделать «бесконечным» с помощью виртуальной памяти.
Тогда соответствующая проверка будет в логике этого аллокатора. Вы же не можете довыделить память под стек, не убедившись, что имеющаяся закончилась?
Ну расскажите мне про устройство современным процессоров в данном контексте.Разница в том, модифицировать ли регистр, или память. Даже закэшированное значение модифицируется не бесплатно.
Тогда соответствующая проверка будет в логике этого аллокатора. Вы же не можете довыделить память под стек, не убедившись, что имеющаяся закончилась?Вообще то могу) Просто проверки будут делаться на уровне ОС. Это делается правильным менеджментом виртуальной памяти. Правда, ОСшное выделение будет производиться по 4KB, что маловато, так что не факт, что такая экономия одного if'a того стоит.
Вообще, лично меня смущает то, что я так и не понял, чем именно простые стековые аллокаторы не подходят в функциональщине. Ведь по сути и речи не идет о том, что GC может быть лучше стека, лишь отстаивается то, что он может работать не сильно медленнее. Так почему бы не использовать стек, который заведомо не менее производительный, и гораздо более тривиальный в реализации?
Разница в том, модифицировать ли регистр, или память.
В обоих случаях можно модифицировать регистр.
Вообще то могу) Просто проверки будут делаться на уровне ОС.
Ну, то есть не можете, т.к. ОС все равно их сделает :)
Вообще, лично меня смущает то, что я так и не понял, чем именно простые стековые аллокаторы не подходят в функциональщине.
nurcery — это и есть стек в фп. Но он не может быть смоделирован классическим стеком, т.к.:
- из-за замыканий стек становится деревом фреймов, а не их списком
- из-за лени он становится произвольным графом
в итоге вы не сможете освободить память прямым раскручиванием стека, если там окажутся достижимые данные.
Нет, разницы нет.
почитайте про инвалидацию кеша процессора
А в случае стека должна быть проверка на пробой стека.
делается на уровне железа.
Ну то есть просто не создавать новых объектов, тогда и память не понадобится. Но мы же немного не то сейчас обсуждаем.
…
Управлять — да, а выделять и освобождать — нет.
Хорошо, с другой стороны. Прикрутив джавовский или любой другой аллокатор к приложению на c++/rust, мы получаем ту же скорость выделения/освобождения (с теми же накладными по памяти), но меньше копируем данные
почитайте про инвалидацию кеша процессора
С точки зрения кеша в nursery все точно так же как со стеком.
делается на уровне железа.
Нет, не делается. Этим занимается ОС, т.к. именно ОС выделяет процессам стек.
Хорошо, с другой стороны. Прикрутив джавовский или любой другой аллокатор к приложению на c++/rust, мы получаем ту же скорость выделения/освобождения (с теми же накладными по памяти)
Ну, я, вроде, об этом и сказал — вы можете переизобрести (или использовать уже написанный) gc.
С точки зрения кеша в nursery все точно так же как со стеком.
…
Нет, не делается. Этим занимается ОС, т.к. именно ОС выделяет процессам стек.
Я про аппаратную поддержку. amarao вам уже про это писал
Ну, я, вроде, об этом и сказал — вы можете переизобрести (или использовать уже написанный) gc.
не путайте автоматическую сборку мусора с деаллокацией
Иммутабельность очень сильно помогает GC.
Вообще, на практике с иммутабельностью в хаскеле дело несколько сложнее, чем "старые данные не указывают на новые", т.к. благодаря лени можно вязать узлы произвольной сложности (и при завязывании узла на низком уровне происходит мутация указателя). Но там уже дело за конкретными оптимизациями и эвристиками, так что концептуально это дела не меняет.
Тогда людоедоедоед != людоеду.
Ну а энтомолог Иванова пригласила льва, чтобы посчитать блох ;)
людоедоедоеда», нам нужно произвести лингвистический анализ последнего слова. Проще всего это сделать, читая корни справа налево:
Людоед = тот, кто ест людей.
Людоедоед = тот, кто ест людоедов = тот, кто ест тех, кто ест людей.
Простите, но сразу стало непонятно. Самый правый корень "ед". Может слева направо?
Вы сейчас пытаетесь объяснить рекурсивно, через указатели :). Я же говорю о логике объяснения в статье.
Если мы разбиваем слово людоедоедоед, тогда первая строчка (по Вашему описанию) должна быть
- людоедоедоед = людоедоедо (лево) + ед (право)
То есть у вас словесный алгоритм не соответствует написанному коду. А для вот таких вот объяснений-аналогий это как раз самое важное.
А что, обьяснения, что указатель — это адрес в памяти, где лежит объект не достаточно? Подход в статье ну совсем какой-то мутный.
А если непонимающему просто дать задачу, где указатели реально нужны и он сам придет к их необходимости.
Мне кажется, нет смысла объяснять указатели дальше одного уровня.
Вещи типа TObject* objects[]
должны как-то сами приходить.
Лучшее, что я видел — это «отодвинуть» изучение указателей за ту точку, когда человек уже знает для чего они нужны.
То есть вначале мы изучаем массивы, структуры, дальше изучаем алгоритмы (деревья, очереди с приоритетами). А потом, когда человек уже привык оперировать с индексами, которые указывают на ячейки, в которых тоже лежат индексы — объяснить ему, что указатель — это такой «синтаксический сахар» для большого массива с названием «опереативная память» — дело пяти минут.
И всё. И нет никакой магии и никакого «щелчка» в голове, всё буднично и банально.
Почему-то никого не удручает тот факт, что для того, чтобы научиться рассказы писать нужно потратить не один год, рисуя палочки и изучая как подлежащее со сказуемым согласуется.
А потратить пару месяцев на то, чтобы понять как устроены базовые, простейшие структуры данных (и на их основе понять как работают указатели и рекурсия) — нам влом.
за счет высокой локальности — промахов процессорного кэша будет поменьше, чем для разбросанного в памяти дерева на указателях.Вот только никакой локальности в этом представлении нет и в помине, так что реально выигрыш происходит только за счёт экономии памяти.
Если надо, то можно сделать под дерево кастомный аллокатор и обеспечить себе любую требуемую локальность, вообще говоря. Так что особо не важно что там и как сорит.
Не обязательно большим куском, можно кусками поменьше. Сборщики мусора же как-то работают.
left
и right
отсутствуют, являются виртуальными…Вы уже сами запутались. Давайте по порядку:
- Если дерево сбалансировано, то вы можете выделить элементы любом наперед заданном порядке и расположить их последовательно, обеспечив локальность для любого наперед заданного метода обхода. Не важно со ссылками или без.
- Если дерево несбалансировано, то вы так же можете выделить ноды в любом наперед заданном порядке и расположить их последовательно, обеспечивая локальность, но уже используя указатели, чтобы компенсировать "дырки". Толку от неиспользования указателей в этом случае нет, т.к вам "дырки" сожрут всю сэкономиленную память.
На самом деле проще всего начать с такой структуры данных, как «ассоциативный массив» на базе хеш-функции.
Вначале — простой массив пар «ключ/значение», в случае если случаются коллизии… у нас беда.
Потом — начинаем записывать в соседние ячейки… и на какое-то время можно на этом продержаться.
Потом — учимся обходить занятые места и устраивать «дыры», если нам это нужно (тут у нас уже получаются вначале односвязные, а потом и двусвязные списки).
Ну а после этого — можно уже и деревья устроить.
Получается, что есть какой-то абстрактый человек, который понимает сегменты и смещения в них процессоров Intel, он знает про разницу 32-х и 64-х битной адресации, а когда ему сказали, что '&' берет адрес переменной, а '*' возвращает значение по адресу, он такой:«Нет, вы знаете, не догнал». Странно это как-то.
Интересно, а эти самые люди ссылки в С++ понимают?
Похожая история и с байтом происходит. Его упрощают до 8-ми бит т.к. количество архитектур где он другого размера крайне мало.
Это довольно избитая и обмусоленная тема, вот тут почитайте.А что я там должен увидеть? Что люди, не знающие о том, как устроен современный C пишут о нём всякие домыслы? Беглый поиск показал, что никто из спорщих о вкусе устриц с теми, кто их ел, не подозревает о том, что с C99 (а стало быть и с C11) есть такая штука, как
intptr_t
, которая «закрывает тему»: да, теоритечески указатели в C (и C++) могут быть много чем (intptr_t
, строго говоря, опционален), но практически — вы можете просто игнорировать подобные компиляторы.Если как раз почитать стандарты, на которые вы ссылаетесь, то однозначный ответ — нет. Да, численно указатель равен смещению в сегменте данных, но на этом все сходство с offset ptr заканчивается (кстати, даже в оригинальных ассемблерах не употребляют слово адрес, а именно offset — смещение).
В высокоуровневых языках, где вообще нет указателей, не нужно забивать голову низкоуровневой ерундой, но в С извольте называть вещи своими именами и понимать из каких частей и как именно формируется адрес в памяти.
Осталось определиться, какую тему закрывает intptr_t, и отсылок к стандарту в той теме как раз предостаточно.Вопрос «является ли указатель числом».
The following type designates a signed integer type with the property that any valid pointer to void can be converted to this type, then converted back to pointer to void, and the result will compare equal to the original pointer:Если мы можем сконевртировать указатель в число, проделать с этим числом всем операции, какие можно производить с числом (в файл, например, записать, или по сетке на другой компьютер послать), то всё, тема закрыта: этот указатель — таки и есть число.
intptr_t
The following type designates an unsigned integer type with the property that any valid pointer to void can be converted to this type, then converted back to pointer to void, and the result will compare equal to the original pointer:
intptr_t
Предмет текущего спора, напомню, можно ли утверждать, что указатель (pointer в оригинальном стандарте) — это адрес.А что такое адрес, извините?
Да, численно указатель равен смещению в сегменте данных, но на этом все сходство с offset ptr заканчивается (кстати, даже в оригинальных ассемблерах не употребляют слово адрес, а именно offset — смещение).Если вы таки про 8086, то там ещё и сегмент был. И указателей было… много разных:
near
, far
, hure
…В высокоуровневых языках, где вообще нет указателей, не нужно забивать голову низкоуровневой ерундой, но в С извольте называть вещи своими именами и понимать из каких частей и как именно формируется адрес в памяти.Это, в общем-то, нужно только при взаимодействии с ассемблером. Из-за вышеописанного свойства intptr_t указатель — это число. А уж как они связано с тем, что на шину адреса выставиться — дело десятое. Может со сдвигом, может инверсно, может ещё как-нибудь. Но так или иначе — это должно проивходить как-то, иначе указатель свою роль не сможет играть.
P.S. Собственно на это наткнулись эльбрусовцы, когда завели теги в памяти, чтобы указатели перестали быть просто числами и стали чем-то что OS выделяет и на корректность чего, соотвественно, можно положиться. Вот в тот момент, когда выяснилось, что указатель можно превратить в число и потом — обратно в указатель… вся схема и «провисла:»…
А вот в C (по крайней мере в современном C) — это таки «просто число», то есть «просто адрес».
Вспомните про .NET! Там указатель — это не просто себе последовательность битов. За ним учёт нужен. Превратить его в число, а потом обратно — низзя. Не положено. А в C/C++ — как раз положено! И всё — в .NET встроить C/C++ нельзя. Недаром Micrososft спецподелие изобрёл. Не потому, что ему больше нечем заняться…
В итоге человек, который не до конца понимает, что делает синтаксис, который он использует, начинает писать код, который выглядит как пример, который я дал в самом начале. Подобную ситуацию приходилось видеть не раз и не два, даже если человек честно читал учебник — увы, не все они написаны последовательно, а багаж знаний, накопленных в таких языках, как JavaScript, ещё более усложняет понимание.
Получается, что есть какой-то абстрактый человек, который понимает сегменты и смещения в них процессоров Intel, он знает про разницу 32-х и 64-х битной адресации, а когда ему сказали, что '&' берет адрес переменной, а '*' возвращает значение по адресу, он такой:«Нет, вы знаете, не догнал».Нет такого астрактного человека. Есть человек, которому написали как получить данные из формочки и «нарисовать» на основе этих данных HTML.
Всё равно как если бы математику учили не со сложения и таблицы умножения, а с задач по составлению диффуров и нахождения экстремумов. Понятно, что это полезнее, но без основ — оно всё у вас «провиснет в воздухе» и вы будете делать совершенно идиотские ошибки на ровном месте.
А потом вот с этим багажом — хотят изучить C/C++. Причём в том же стиле. А он, зараза, понимания требует. Комбинаторным программированием в нём даже программу в 1000 строк не сделать. Вот беда-огорчение…
Да ладно вам, перекладывание байтиков по когнитивной нагрузке от дерганья формочек ничем существенно не отличается. И на стековерфлоу точно так же есть куча готового кода для разных кейсов.
Да ладно вам, перекладывание байтиков по когнитивной нагрузке от дерганья формочек ничем существенно не отличается.Отличиается. Тем, что если вы «не так» переложите формочки — то вы это сразу увидите или, в худшем случае, вам прилетит понятный exception.
Если вы «не так» переложите байтики — вам никто худого слова не скажет, просто программа будет вываливаться с невразумительными дампами (да, я знаю, есть много способов во всём этот разобраться — но для этого всё равно нужно какое-то понимание того, что вы делаете).
Отличиается. Тем, что если вы «не так» переложите формочки — то вы это сразу увидите или, в худшем случае, вам прилетит понятный exception.
Ну, во-первых, можете увидеть и спустя несколько лет после эксплуатации, если проблема в логике.
Во-вторых — для того, чтобы разобраться в невразумительном стектрейсе какого-нибудь эксцепшена из гуевого фреймворка, точно так же требуется понимание того, как все в этом фреймворке работает.
Во-вторых — для того, чтобы разобраться в невразумительном стектрейсе какого-нибудь эксцепшена из гуевого фреймворка, точно так же требуется понимание того, как все в этом фреймворке работает.Нет. Достаточно понять как меняется программа «методом малых шевелений».
Ну, во-первых, можете увидеть и спустя несколько лет после эксплуатации, если проблема в логике.Те, кто могут писать нетривиальную логику — уже и в указателях могут разобраться.
Достаточно понять как меняется программа «методом малых шевелений».
exception от этого понятным не станет
Те, кто могут писать нетривиальную логику — уже и в указателях могут разобраться.
Так я об этом и сказал с самого начала. Перекладывание формочек от перекладывания байтиков ничем не отличается. И там и там — перекладывание. Сложность возникает тогда, когда процесс перекладывания становится нетривиальным, и не важно, формочки это или байтики. Если же процесс тривиален — то, опять же, разницы нет, формочки у вас или байтики, в обоих случаях можно будет справиться "малыми шевелениями" и прочим стековерфлоу-программированием.
Здесь справедливости ради стоит заметить, что "глубина абстракции" в случае формочек несравнимо выше. То есть — вы можете, в принципе, досконально хорошо понимать, как работает ваш алгоритм, перекладывающий байтики, но не можете досконально хорошо понимать, как работает алгоритм, перекладывающий формочки. Так что потенциальная когнитивная сложность задач с формочками выше. Но только потенциальная.
И? Задачу после некоторого количества случаных измнений вы решите, эксепшн изгоните — значит вы уже программист. Всё как у классика.Достаточно понять как меняется программа «методом малых шевелений».exception от этого понятным не станет
А вы сюда с каким-то «пониманием» лезете.
Сложность возникает тогда, когда процесс перекладывания становится нетривиальным, и не важно, формочки это или байтики.Важно. Формочка с тремя полями и база с двумя стобцами — это уже что-то за что можно какую-то денежку, если повезёт получить. А три байта в C++ — этого даже чтобы светодиодом поморгать, скорее всего, не хватит.
Количество переходит в качество и комбинаторное программирование перестаёт работать…
Важно. Формочка с тремя полями и база с двумя стобцами — это уже что-то за что можно какую-то денежку, если повезёт получить. А три байта в C++ — этого даже чтобы светодиодом поморгать, скорее всего, не хватит.
Мне кажется, то, что в байтоперекладывании за "сложность" платят меньше — факт ортогональный обсуждаемым вопросам.
Она просто развалится под собственной тяжестью. И этот размер — особо от языка не зависит.
Но в случае с web-программированием программы подобного размера можно продавать, а в случае с C++ — нет.
А это кардинально меняет всю динамику.
Подход в статье ну совсем какой-то мутный.
Мне эти «людоедоедоеды» вообще напомнили цитатку с башорга:
Извините, не удержался)
void do_something(MyObj *input[], int count)
{
MyObj **copy = new MyObj*[count];
for (int i = 0; i < count; ++i)
*copy[i] = *input[i];
...
}
В коде ошибка. copy — это массив указателей.
В выражении:
*copy[i] = *input[i];
происходит разъименование указателя copy[i], который никуда не указывает. Это UB.
P.s. я понимаю, что в it много самоучек. В вузе на курсе С нас год муштровали машинной арифметикой, СДиА, битовыми операциями и пр. Считаю, это надо понимать, а если вы пишите на языке, где есть указатели — то тем более. И если в вузе не отложилось, надо наверстать.
А понимание пришло откуда не ждали — когда в качестве хобби решил заняться программированием под AVR и для этого освоил ассемблер. Все сразу стало куда понятнее. Я не утверждаю что студентам нужно в обязательном порядке вдалбливать ассемблер, но как лирическое отступление при объяснении указателей можно было бы.
Примерно так нам и объясняли в вузе. И не припомню проблем с пониманием.
Имхо, объяснять указатели на каких-то мутных лингвистических аналогиях, а не на предельно ясном устройстве абстрактного процессора — очень странная идея.
Но зла не хватает. Все языки используют указатели, но не все в этом признаются.
С ними было бы что-то вроде:
Не проказничали чтобы
Гомофобофилофобы,
Скоро всех возьмут на вилы
Гомофилофобофилы.
Для объяснения темы указателей как таковых существует множество более удачных аналогий, часть из которых приведена комментаторами выше (хотя мне искренне не понятно, что может быть непонятного в определении из условной Викидепии).
Для объяснения же синтаксиса существуют документация, туториалы и т.д.
Объяснять синтаксис технического языка на примере конструкции из живого — это, как минимум, странно и долго. Как максимум — отпугнёт и разочарует.
Но за попытку спасибо)
С одной стороны, да, всё всегда упирается в синтаксис, поскольку работаем мы [программисты] с кодом; понятие «переменная» и «указатель» справедливы только для кода, непосредственно железо в этих понятиях не нуждается и ими не оперирует.
Поэтому формально я с вами согласен, да.
С другой же стороны, если посмотреть на ситуацию комплексно, то мы сможем свести все причины проблем с указателями всего-то к двум:
- Непонимание сути указателей;
- Незнание синтаксиса.
Так вот суть в том, что решить первую проблему лингвистическими аналогиями — невозможно. Здесь нужно просто объяснять человеку, что есть память, что есть переменная. Когда
Но здесь мы сталкиваемся со второй проблемой: вы можете зубрить что угодно и сколько угодно, но пока вы не поймёте сути темы — толку ноль.
Именно поэтому у людей и возникают проблемы с такими казалось бы несложными вещами как указатели: они либо путают порядок, в котором должно обучаться, либо выполняют лишь одно из двух действий.
Резюмируя, статья интересная, правда. Для тех, кто итак всё понимает.
Новичкам же от неё толку будет ноль, поскольку она не решает ни одной из вышеперечисленных проблем)
Это, кстати, да, тому, кто придумал одним и тем же символом (*) обозначать и операцию разыменовывания и спецификатор типа (и вдобавок тот факт, что спецификатор типа принадлежит переменной, а не типу, что откровенная шизофрения), нужно обеспечить пожизненный цик с гвоздями. Да и взятие адреса с побитовым "и" недалеко ушло.
Спасибо за статью, очень познавательно и очень интересно.
Если надо дело доходит до ** или не дай бог Страуструп *** гораздо читабельней сделать
typedef Object* ObjectPtr
Особенно удобно если потом это всё еще и в массив кладется, и не надо думать что будет когда операторы []
и *
стоят в одном выражении.
людоведаедовед
При условии, что людоведа зовут например Вася, а его жену не Люда.
Указатели C как лингвистический парадокс