Мысли о эффективном автоматическом управлении памятью - Философия программирования

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

Предпосылки

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

Понятно, что обязательным слагаемым быстрой и безопасной разработки является автоматическое управление памятью. На сегодня в этой области есть только:
1. Автоматический подсчет ссылок — ARC.
2. Сборка мусора — GC.

Методы вроде "умных указателей" из С++ могут только немного упростить жизнь, но не в силах ни гарантировать корректной работы с памятью, ни существенно упростить написание программ.

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

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

Теперь немного "крамолы" (для не посвященных). На самом деле скорость GC существенно выше чем скорость ARC или ручного управления памятью на базе malloc/free, так как выделение памяти требует всего лишь одного приращения указателя, а освобождение не стоит ничего (мортвые объекты просто игнорируются). Платим мы только за поиск живых объектов и за дефрагментацию кучи. Поиск живых объектов дешевле чем подсчет ссылок (точнее приблизительно равен, но подсчетом ссылок нужно заниматься чаще). А дефрагментации в системах отличных от GC попросту нет. Так что тут и сравнивать не чего. Можно же было просто возвращать объекты в список свободных и выделять повторно. Просто дефрагментация избавляет от ряда проблем. Особенно от фрагментации кучи (ваш КО).

Так почему же языки вроде С и С++ зачастую быстрее управляемых (т.е. использующих GC)?

Ответ не так прост:
1. Примитивные техники GC дают довольно заметные остановки всего приложения для подсчета живых ссылок и дефрагментации кучи. Чтобы этого избежать применяются разные продвинутые техники вроде бэкграунд-пометки живых объктов и даже икрементальной дефрагментации. А чтобы это было возможно код связанный с присвоением указателей заменяют специальными перехватчиками которые отлавливают изменение уже помеченных объектов и т.п. Вот этот то код и создает основной оверхэд от GC, а вовсе не сам GC. В серверных GC этого кода может и не быть, но они могут давать заметные даже не глаз задержки. Причем в некоторых приложениях (где графы объектов малы) задержек не видно. А в некоторых они могут быть вдины.
2. Качество оптимизаций компилятора (джита или нгена для дотнета). Это отставание обусловлено двумя факторами. Во-первых, очевидным лидерством плюсовых компиляторов (в них вложено уже очень много денег и сил). Во-вторых, некоторыми особенностями управляемых языков которые препятствуют агресивным оптимизациям. Эту тему я затрагивать не буду, так как мой спичь о GC. Но учитывать это надо. Так как во многом отставание GC-языков определяется вовсе не наличием GC.
4. В С/С++ можно использовать ряд хаков для более эффективного управления памятью выделенной в куче. Но они лишь чуть-чуть могут опередить GC, так как в нем и так применяются найэфективнейший алгоритмы.
5. И, наконец, главное! Тем что в С и С++ большая часть данных размещается вовсе в куче, а на стеке!
6. Гранулярностью куч и необходимостью защиты их от многопоточной среды. Многие GC-среды имеют одну или две кучи (не считая поколений). Так в дотнете по умолчанию используется две кучи SOH и LOH. Одна — SOH — используется для объектов до 85 000 байт (в ней есть поколения и производится дефрагментация). Другая — LOH — используется для размещения больших объектов. В ней не производится дефрагментации (хотя в 4.5 вроде бы начали что-то делать) и все объекты в ней сразу же причисляются к второму (последнему) поколению.

Так вот вот эффективность управления памятью и размеры пауз связанных с GC зависят от двух факторов:
1. Малому размещению объектов на стеке. Это связано с тем, что языки спроектированные в расчете на GC, на сегодня, размещают объекты имеющие виртуальные таблицы и на которые можно дать ссылки, только в куче.
2. Сваливанию всех объектов в одну кучу. В больших приложениях графы объектов достигают гигантских размеров, так что сборка последних (не эфемерных) поколений может вызывать заметную на глаз задержку.

Альтернативы GC

На сегодня я знаком с двумя безопасными альтернативы GC:
1. ARC (автоматический подсчет ссылок).
2. Ручное управление временем жизни объектов с контролем со стороны компилятора.

На практике второй пункт без ARC или GC попросту не живет. Да и представитель у такого подхода по сути ровно один — Rust.

В двух словах идея управления жизни в Rust сводится к тому, что объекты можно размещать на стеке или в куче (как в С/С++). Но при этом есть специальный вид размещения в куче:
Box — которая обеспечивает условие одиночного владения объектом в единицу времени (т.е. это уникальная ссылка, но контролируемая компилятором).
ARC — ну, с ней все ясно.

Собственно интерес в Rust представляет, в первую очередь, идея явного управления временем жизни объектов и ручной связи с ними времени жизни указателей. Идея простая как пробка — указатель должен жить не больше чем объект на/в который он указывает. Так чтобы возвратить указатель указывающий внутрь некоторого объекта переданного в функцию, возвращаемый указатель должен быть ассоциирован с временем жизни параметров на который он может указывать. Тогда компилятор сам отследит чтобы пользователь функции не использовал указатель когда кончится время жизни объекта.

Идея интересная, но уж слишком много, при этом, ложится на плечи программиста.

Причем у этого подхода есть и ограничения. Так указатель в Rust не отслеживается, а значит он не должен сдвигаться. Это значит, что точный GC (GC поддерживающий дефрагментацию) вряд ли может быть использован в Rust.

Еще одна проблема — автоматическое управление объектами в куче на которые нужно иметь более одной ссылки делается через ARC.

Собственно, а чем плох ARC? ARC, ведь, можно рассматривать как вид GC.

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

Можно ли улучшить языки рассчитанные на GC

Я думаю, что это вполне возможно. Каковы средства оптимизации программ в управляемом мире? Да очень просты! Программисты стараются по меньше занимать памяти в куче!

Собственно именно это и делают С++-программисты. Причем даже не потому, что это медленно, а потому что это неудобно (память на стеке ведь освобождается автоматом, а в хипе нужно придумывать сложные стратегии).

Если каким-то образом позволить (в GC-языках) размещать большую часть объектов на стеке, то производительность существенно увеличится.

В современных управляемых средах (точнее в яве) используются техники (эскейп анализ) для автоматического вычисления информации о том, что время жизни объекта совпадает с его областью видимости, и что ссылки на объект не помещаются в какие-то там поля и т.п. Это позволяет разместить объект на стеке и отдать указатель а функцию. Казалось бы проблема решена! На на практике есть масса факторов препятствующих подобному анализу. Так что далеко не все объекты могут быть переложены в стек. Кроме того эскейп анализ не является гарантированной оптимизацией. Ее можно включить только в ряде ява-машин и она вообще не доступна в дотнете.

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

Предложения по сокращению оверхэда от GC

1. Нужно сделать очень простую модификацию в языках (и рантайме) — ввести ссылку которую нельзя а) помещать в поля обычных объектов или массивы; б) которую нельзя возвращать за пределы области видимости где она создана. Это позволит описывать большинство функций как принимающие такие указатели, т.е. гарантированно их не прикапывающие ссылки или прикапывающие в объектах чье время жизни меньше или равно объекту на который делается ссылка.
2. Ввести уникальные указатели, позволяющие владеть объектом только одному объекту (это позволит так же упростить мнонопоточное программирование).
3. Увеличить количество куч в управляемых программах. Тут возможны варианты, но мне больше нравится идея акторов:
* Вводим по одной кучи на поток. Запрещаем обращение к памяти из этой кучи из других потоков.
* Вводим специальную обменную кучу в которой разрешаем размещать исключительно неизменяемые объекты.
* Вводим для каждого потока очередь в которой можно помещать объекты из обменной кучи.
Так же ввести глобальную кучу рэйдонли-объектов куда можно помещать совместно используемые объекты и константы.
Еще можно позволить вводить специальные локальные кучи с фиксированным временем жизни (по стеку или с ручным уничтожением). После уничтожения кучи можно просто пометить все ссылки на нее нулями или даже выкидывать исключение, если таковые ссылки имеются. В прочем, и без этого варианта предлагаемые изменения должны снять проблемы которые обычно ассоциируют с GC.

Заключение

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

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

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

VD>1. Нужно сделать очень простую модификацию в языках (и рантайме) — ввести ссылку которую нельзя а) помещать в поля обычных объектов или массивы; б) которую нельзя возвращать за пределы области видимости где она создана. Это позволит описывать большинство функций как принимающие такие указатели, т.е. гарантированно их не прикапывающие ссылки или прикапывающие в объектах чье время жизни меньше или равно объекту на который делается ссылка.

Со всем остальным согласен, но вот этот пункт, ИМХО, не очень хорош. Потому что сходу не ясно, какие ссылки нужно помечать этим атрибутом и почему. Особенно в библиотечном коде, который просто так изменить не удастся.

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

VD>На мой взгляд введение "неприкапываемых" ссылок и увеличение количества GC-куч должны сравнять GC-среды/языки с их неуправляемыми языками и позволить при этом иметь ясную, простую, безопасную и автоматическую модель управления памятью приложения.

VD>В такой среде производительность будет увеличиваться за счет того, что большая часть объектов сможет размещаться в стеке.

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

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

1. Как отдельные кучи на поток будут уживаться с асинхронным кодом, который как раз допускает передачу контекста из потока в поток? Как пример возьмём тот же рослин, который работает с очень большим immutable tree и активно его тасует между разными потоками (при компиляции емнип это сейчас не используется, в студии — используется на 100%).

2. В ту же степь, как быть с замыканиями?
Как пример, вот такую штуку

class A
{
  int x;

  public IEnumerable<int> Get() { return Enumerable.Range(1,100).Where(i => i < x); }
}

в общем случае уже нельзя аллоцировать на стеке. Причём решение "можно/низзя" для untrusted-кода надо принимать во время джита (что отнимает время на оптимизацию), ну, или переходить к прекомпиляции аля .net native.

3. Списки/словари/массивы и библиотечный код. Как я понимаю, решение о том, где будет аллоцироваться список — в разделяемой куче или в локальной — отдаётся на откуп разработчику. Что делать с биз-классами типа

class Order { List<Detail> Details; }

которые по логике должны шастать из метода в метод по всему коду?

В общем, что-то я не уверен, что идея сработает без изменения стиля, в котором пишется код. Точнее сработает, но простая разметка безопасного для аллоцирования на стеке кода как [Pure] даст примерно тот же эффект. А агрессивная оптимизация из .net native ещё и усугубит

С другой стороны, на язык с синтаксисом для пайпов/акторов аля axum/sign# из singularity схема ложится как родная. Собственно, в axum что-то подобное и было:
http://blogs.msdn.com/b/maestroteam/archive/2009/02/27/we-haven-t-forgotten-about-other-models-honest.aspx
и
http://blogs.msdn.com/b/maestroteam/archive/2009/02/27/isolation-in-maestro.aspx

ну и из относительно свежего от MS — orleans. Идея всё та же: куча акторов, каждый работает в изолированном домене (вплоть до переезда акторов с машины на машину наживую).

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

VD>1. Примитивные техники GC дают довольно заметные остановки всего приложения для подсчета живых ссылок и дефрагментации кучи. Чтобы этого избежать применяются разные продвинутые техники вроде бэкграунд-пометки живых объктов и даже икрементальной дефрагментации. А чтобы это было возможно код связанный с присвоением указателей заменяют специальными перехватчиками которые отлавливают изменение уже помеченных объектов и т.п. Вот этот то код и создает основной оверхэд от GC, а вовсе не сам GC. В серверных GC этого кода может и не быть, но они могут давать заметные даже не глаз задержки.

Даже без инкрементальной или конкурентной сборки нужны write barriers по очень простой причине: если у тебя GC с поколениями, и язык разрешает менять указатели в объектах старших поколений (в отличие от Эрланга, например, где все иммутабельно и такой проблемы нет), то чтобы можно было собирать лишь молодое/эфемерное поколение надо отлавливать все возникающие указатели на молодые объекты из старых, для этого нужны барьеры в том или ином виде. Т.е. этот вот оверхед неизбежен при наличии generational GC. А без поколений GC настолько медленный, что и говорить не о чем.

Подробнее о проблеме, с картинками:
http://www.infognition.com/blog/2014/the_real_problem_with_gc_in_d.html

VD>Собственно интерес в Rust представляет, в первую очередь, идея явного управления временем жизни объектов и ручной связи с ними времени жизни указателей. Идея простая как пробка — указатель должен жить не больше чем объект на/в который он указывает. Так чтобы возвратить указатель указывающий внутрь некоторого объекта переданного в функцию, возвращаемый указатель должен быть ассоциирован с временем жизни параметров на который он может указывать. Тогда компилятор сам отследит чтобы пользователь функции не использовал указатель когда кончится время жизни объекта.

VD>Идея интересная, но уж слишком много, при этом, ложится на плечи программиста.

А много ты на Расте написал кода, чтобы так говорить? Этот пункт вызывает сомнения.

VD>Причем у этого подхода есть и ограничения. Так указатель в Rust не отслеживается, а значит он не должен сдвигаться. Это значит, что точный GC (GC поддерживающий дефрагментацию) вряд ли может быть использован в Rust.

Мне думается, что проблему фрагментации ты несколько преувеличиваешь. Если аллокатор, как какой-нибудь tcmalloc, имеет разные free-list'ы для объектов разных размеров, то никакой особой фрагментации и не возникает. Впрочем, здесь я могу и ошибаться.

VD>1. Нужно сделать очень простую модификацию в языках (и рантайме) — ввести ссылку которую нельзя а) помещать в поля обычных объектов или массивы; б) которую нельзя возвращать за пределы области видимости где она создана.

И вот мы и получили Rust. Твое предложение, совершенно оправданное и разумное, полностью эквивалентно (с т.з. компилятора и усложнения языка для программиста) той системе контроля лайфтаймов, что есть в Расте.

VD>2. Ввести уникальные указатели, позволяющие владеть объектом только одному объекту (это позволит так же упростить мнонопоточное программирование).

Ага, Box в Rust'e.

VD>3. Увеличить количество куч в управляемых программах. Тут возможны варианты, но мне больше нравится идея акторов:
VD> * Вводим по одной кучи на поток. Запрещаем обращение к памяти из этой кучи из других потоков.
VD> * Вводим специальную обменную кучу в которой разрешаем размещать исключительно неизменяемые объекты.

Где я это уже видел. Ах да, Rust.

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

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

VD>На практике второй пункт без ARC или GC попросту не живет. Да и представитель у такого подхода по сути ровно один — Rust.
Как на счёт Cyclone? Да, он не взлетел и уже не взлетит, но тем не менее. Разработчики Раста, кстати, указывали, что вдохновлялись, в том числе, этим языком.

VD>Идея интересная, но уж слишком много, при этом, ложится на плечи программиста.
По моему, это "не проблема". В смысле, писать не сложнее, чем на С++ и это уже здорово. Собственно, для этого он и предназначался. Если писать будет удобнее, чем на С/С++ и ошибок допускаться будет меньше, то цель выполнена. По "удобству" языки с "полным GC" вряд ли перегнать удастся.

Признаю — я (пока) ничего обьёмного на Расте не писал, но активно его изучаю и пока мне многое нравится.

Ну и я честно говоря, не особо понимаю почему часто ARC преподносится как что-то ужасное. Да, решение не идеальное, но "проверенное временем" и вполне рабочее. По моему (С++) опыту оно не так часто требуется. А когда требуется, то опять же, уследить за отсутствием зацикливания не особо сложно, при правильном дизайне.

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

Здравствуйте, D. Mon, Вы писали:

DM>Даже без инкрементальной или конкурентной сборки нужны write barriers по очень простой причине: если у тебя GC с поколениями, и язык разрешает менять указатели в объектах старших поколений (в отличие от Эрланга, например, где все иммутабельно и такой проблемы нет), то чтобы можно было собирать лишь молодое/эфемерное поколение надо отлавливать все возникающие указатели на молодые объекты из старых, для этого нужны барьеры в том или ином виде. Т.е. этот вот оверхед неизбежен при наличии generational GC. А без поколений GC настолько медленный, что и говорить не о чем.

DM>Подробнее о проблеме, с картинками:
DM>http://www.infognition.com/blog/2014/the_real_problem_with_gc_in_d.html

Ты и автор этого блока просто не знаешь, что в 21 веке эту работу можно переложить на ОС, которая отследит изменение памяти с помощью прерываний. В Винде для этого используется флаг MEM_WRITE_WATCH при вызове функции VirtualAlloc() и GetWriteWatch() для того чтобы получить список измененных страниц.

Так что слушайте что вам опытный дядя говорит

. Эта проблема решена аппаратно. Барьеры нужны только в конкурентных GC.

DM>А много ты на Расте написал кода, чтобы так говорить? Этот пункт вызывает сомнения.

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

Кроме того я спрашивал у Киберакса о том насколько это гиморно. Он сказал, что примерно как в С++.

VD>>Причем у этого подхода есть и ограничения. Так указатель в Rust не отслеживается, а значит он не должен сдвигаться. Это значит, что точный GC (GC поддерживающий дефрагментацию) вряд ли может быть использован в Rust.

DM>Мне думается, что проблему фрагментации ты несколько преувеличиваешь. Если аллокатор, как какой-нибудь tcmalloc, имеет разные free-list'ы для объектов разных размеров, то никакой особой фрагментации и не возникает. Впрочем, здесь я могу и ошибаться.

Во-первых, ничего кроме дефрагментации с перенесением объектов не решает проблему фрагментации на 100%.
Во-вторых, за все нужно платить. Продвинутая логика по спасанию и объединению/разбиению свободных блоков замедляет алгоритм выделения и освобождения память. Стало быть мы платим скоростью. Более простые алгоритмы ведут к фрагментации — значит мы можем нарваться на атофмемори, получаем худшую локальность данных (промахи мимо кэша) и прочими проблемам.

DM>И вот мы и получили Rust. Твое предложение, совершенно оправданное и разумное, полностью эквивалентно (с т.з. компилятора и усложнения языка для программиста) той системе контроля лайфтаймов, что есть в Расте.

Не совсем. В Расте, во-первых, отказались от GC, а во-вторых, предлагают возиться с временем жизни явно, что заставляет программиста уделять этому слишком много времени.

А та я и не скрываю, что присматриваюсь к тому что они там творят.

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

S>Не в порядке спора. А речь идёт о классическом языке общего назначения, или о затачивании языка под определённый паттерн использования?

Смысла в специализированных языках общего назначения нет, на мой взгляд.

S>1. Как отдельные кучи на поток будут уживаться с асинхронным кодом, который как раз допускает передачу контекста из потока в поток? Как пример возьмём тот же рослин, который работает с очень большим immutable tree и активно его тасует между разными потоками (при компиляции емнип это сейчас не используется, в студии — используется на 100%).

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

80% данных все равно не должны разделяться между потоками. А сейчас это невозможно проконтролировать.

S>2. В ту же степь, как быть с замыканиями?
S>Как пример, вот такую штуку
S>

S>class A
S>{
S>  int x;
S>  public IEnumerable<int> Get() { return Enumerable.Range(1,100).Where(i => i < x); }
S>}
S>

А какие тут проблемы? Если весь объект распологается на стеке и мы это знаем, то замыкание (его объект) и итератор (его объект) тоже прекрасно будут жить на стеке.

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

Внешних ссылок на int очевидно нет (он хранится в приватном поле по значению).

Далее остается проконтролировать, что никто не сможет увести во вне ссылку на сам объект A. Это выражается в том, что объект не попадает в какие-либо поля и передается в параметры только как "неприкапываемая ссылка".

Складываем эти знания и делаем вывод, что объект типа А можно смело размещать на стеке.

S>в общем случае уже нельзя аллоцировать на стеке. Причём решение "можно/низзя" для untrusted-кода надо принимать во время джита (что отнимает время на оптимизацию), ну, или переходить к прекомпиляции аля .net native.

Решение может принимать компилятор на основе анализа использования ссылки на объект и дополнительных аннотаций.

Аннотации дают там возможность просчитать время жизни объектов. Точнее гарантировать, что оно совпадает с областью видимости.

S>3. Списки/словари/массивы и библиотечный код. Как я понимаю, решение о том, где будет аллоцироваться список — в разделяемой куче или в локальной — отдаётся на откуп разработчику.

Не совсем. Данные List<T>-а изменяемые. В него ведь можно добавлять элементы. Значит внутренний массив List<T>-а нужно заводить в куче (в С++ — это так же). Но для него можно использовать специальный вид объектов на который имеется только одна ссылка. Тогда при перезаеме памяти под внутренний массив можно детерминировано уничтожить старый массив и завести новый.

S>Что делать с биз-классами типа
S>

S>class Order { List<Detail> Details; }
S>

S>которые по логике должны шастать из метода в метод по всему коду?

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

S>В общем, что-то я не уверен, что идея сработает без изменения стиля, в котором пишется код. Точнее сработает, но простая разметка безопасного для аллоцирования на стеке кода как [Pure] даст примерно тот же эффект. А агрессивная оптимизация из .net native ещё и усугубит

Стиль несомненно будет отличаться от стиля принятого в чистых GC-языках. Но не очень сильно. Просто нужно будет давать компилятору обещания:
1. Не прикапывать указатель на объект полученный в качестве параметра. Это и сейчас так для большинства параметров, но мы не выражаем эту информацию явно.
2. Вложенный объект имеет ровно одну ссылку инкапсулированную внутри внешнего объекта.

и т.п.

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

DM>>чтобы можно было собирать лишь молодое/эфемерное поколение надо отлавливать все возникающие указатели на молодые объекты из старых, для этого нужны барьеры в том или ином виде.

VD>Ты и автор этого блока просто не знаешь, что в 21 веке эту работу можно переложить на ОС, которая отследит изменение памяти с помощью прерываний. В Винде для этого используется флаг MEM_WRITE_WATCH при вызове функции VirtualAlloc() и GetWriteWatch() для того чтобы получить список измененных страниц.

Это и есть барьер в одном из видов, об этом я (автор того блога) там упомянул явно. Фишка в том, что это очень недешевая штука.
first write access to a page allocated with VirtualAlloc+MEM_WRITE_WATCH: 1800 cycles
.. page allocated with VirtualAlloc+ResetWriteWatch: 1100 cycles
Ты думаешь, что если переложить на ОС, то все внезапно бесплатно и мгновенно? Наивный какой.

VD>Так что слушайте что вам опытный дядя говорит

. Эта проблема решена аппаратно. Барьеры нужны только в конкурентных GC.

Ню-ню. Опытный дядя хоть один GC написал в своей жизни? Или аллокатор хотя бы?

VD>Более простые алгоритмы ведут к фрагментации — значит мы можем нарваться на атофмемори, получаем худшую локальность данных (промахи мимо кэша) и прочими проблемам.

Напомнить тебе типичный размер кэш-линии? Есть ли разница с т.з. кэша, лежат ли два объекта в 200 байтах друг от друга или в 200 килобайтах? (ответ — нет)

DM>>И вот мы и получили Rust. Твое предложение, совершенно оправданное и разумное, полностью эквивалентно (с т.з. компилятора и усложнения языка для программиста) той системе контроля лайфтаймов, что есть в Расте.

VD>Не совсем. В Расте, во-первых, отказались от GC, а во-вторых, предлагают возиться с временем жизни явно, что заставляет программиста уделять этому слишком много времени.

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

ptr f(ptr x) { return x; }

ptr g() {
  ptr p = create_scoped_pointer();
  return f(p);
}

Как именно будешь тут бороться с утеканием ссылки наверх?
Тебе придется или вовсе запретить их возвращать (это решит часть проблем, но принесет много неудобств), или добавлять в язык явное указание лайфтаймов, как в Расте.

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

S>>1. Как отдельные кучи на поток будут уживаться с асинхронным кодом
VD>Отлично будут уживаться. Неизменяемые данные можно разделять безболезненно.
Тогда объекты, передаваемые из потока в поток надо будет аллоцировать в разделяемой куче, так? И соответственно, принимать решение где размещать, надо в момент создания объекта, причём это придётся отдавать на откуп программисту. Или я торможу и что-то упустил?

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

В общем, для разделяемой кучи мы по любому возвращаемся к граблям традиционных gc. И что-то я не могу уловить, как свести соотношение "локальные объекты/разделяемые" к минимуму.

VD>А какие тут проблемы? Если весь объект распологается на стеке и мы это знаем, то замыкание (его объект) и итератор (его объект) тоже прекрасно будут жить на стеке.
Так возвращаемый IEnumerable может прожить дольше, чем A. Например, его возвращают как результат функции. Т.е. A на стек кидать можно не всегда.

VD>Решение может принимать компилятор на основе анализа использования ссылки на объект и дополнительных аннотаций.
Угу. Тогда надо будет пожертвовать верификацией недоверенного кода в рантайме, она слишком тяжёлой выходит. Я бы не сказал что это так уж критично, никто не мешает дополнительно проверять недоверенный код на машине клиента, аля peverify или вообще выполнять прекомпиляцию в натив.

Короче, тут никаких принципиальных препятствий нет, идею понял.

Спасибо!

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

VD>Не совсем. В Расте, во-первых, отказались от GC,
Формарльно, они всё-таки не отказались.
Насколько легко нормальный ГЦ будет прикрутить — другой вопрос.

VD>а во-вторых, предлагают возиться с временем жизни явно, что заставляет программиста уделять этому слишком много времени.
Что значит "возиться явно"? В моём понимании это рукопашные new/delete. В расте такого нет, в принципе. Указание лайфтаймов необходимо только в отдельных случаях.

Опять же, ты предлагаешь решение, где точно так же надо будет вручную указывать. Принципиальной разницы не вижу.

Здравствуйте, D. Mon, Вы писали:

DM>Это и есть барьер в одном из видов, об этом я (автор того блога) там упомянул явно. Фишка в том, что это очень недешевая штука.

Барьер (как предполагает само название) — это код в который оборачивается присвоение указателя.

DM>first write access to a page allocated with VirtualAlloc+MEM_WRITE_WATCH: 1800 cycles
DM>.. page allocated with VirtualAlloc+ResetWriteWatch: 1100 cycles
DM>Ты думаешь, что если переложить на ОС, то все внезапно бесплатно и мгновенно? Наивный какой.

А что ты не процитировал предыдущую строчку? Там написано, что VirtualAlloc без MEM_WRITE_WATCH стоит все те же 1800 циклов.

Сброс делается только один раз при сборке не эфемерного (второго) поколения. По сравнению с барьером записи, где время тратится на каждое присвоение, это совершенно бесплатно.

DM>Ню-ню. Опытный дядя хоть один GC написал в своей жизни? Или аллокатор хотя бы?

Написал и не один. Это вы тут любите всех подряд учить сами ничего даже не попробовав.

DM>Напомнить тебе типичный размер кэш-линии? Есть ли разница с т.з. кэша, лежат ли два объекта в 200 байтах друг от друга или в 200 килобайтах? (ответ — нет)

Кэши бывают разных уровней. И разница огромна. Объекты бывают очень маленькие. Замедление кода от фрагментации кучи я наблюдал собственными глазами.

DM>А ты попробуй свою идею сперва додумать до конца.

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

DM>Ты предлагаешь ввести ссылку, которую нельзя заныкать и нельзя "возвращать за пределы области видимости где она создана". Передавать ее в другие функции можно?

Можно.

DM>А возвращать полученную в аргументе? Возьмем такой псевдокод:
DM>

ptr f(ptr x) { return x; }

DM>ptr g() {
DM>  ptr p = create_scoped_pointer();
DM>  return f(p);
DM>}

DM>Как именно будешь тут бороться с утеканием ссылки наверх?
DM>Тебе придется или вовсе запретить их возвращать (это решит часть проблем, но принесет много неудобств), или добавлять в язык явное указание лайфтаймов, как в Расте.

Я же не говорю, что все просто. Подумать есть много над чем. Как в Расте, конечно, можно (раз он работает). Но хотелось бы придумать какой-то менее напряжный для программиста способы возвращать значения.

Я вот, подумываю в сторону следующего подхода. Любая функция всегда возвращает фиксированное значение (через стек или регистр). Если значение не укладывается в фиксированное число бит (скажем, 64), то возвращается указатель на специальную возвратную кучу (верх которой хранится в одном из регистров при возврате). Внешняя функция обязана или освободить все значения помещенные в эту кучу или передать указатель ссылающийся на это значение внешней функции вместе со значением вершины кучи (т.е. опять таки единичное владение). Ну, что-то типа второго стека в котором нет ничего лишнего кроме возвращаемых значений и растущего не по мере входа в функцию, а по мере выхода из нее. Если хочется такой объект поместить куда-то в поле другого объекта или массив, то производится его перемещение в GC-кучу вместе со всеми объектами связанными с ним.

Скажем у нас есть функции:

Func1() : strint * int
{
  // результат помещается в кучу возврата и ссылка на него помещается в 
  // регистр RAX/EAX, а верхушку возвратной кучи в RBX/EBX (например).
  (strung('a', 7) /* динамически создаваемая строка (помещается в возвратную кучу) */, 42) 
}

class A(str : string) { } // предположим наш язык имеет авто-конструктор вводящий поле Str

Func2() : A
{
  // в str ссылка на начало строки в возвратной куче
  def (str, _) = Fanc1(); 
  // в возвратную кучу закладывается объект А в поле Str указатель на 
  // строку из вложенного фрейма выделенного еще функцией Func1.
  // Фрейм Func1 не уничтожается, так как ссылка на его содержимое используется в 
  // возвращаемом результате Func2.
  A(str)
}

Func3() : void
{
  def a = Func3(); // в "a" указатель на начала объекта А в возвратной куче (т.е. на вершину кучи)
  WriteLine(a.Str);
  // здесь возвратный хип автоматически освобождается
}

WriteLine(value : &string) : void { ... } // &string - означает, что ссылка не прикапываемая

Другой вариант Func3:

public Firld : A;

Func3() : void
{
  this.Firld = Func3(); // здесь происходит копирование графа объектов в GC-кучу.
  // В GC-кучу попадает объект A и строка. Фрейм для кортежа (созданный Func1) 
  // теряется, так как на него нет ссылок.
  // Если "прикопать" только строку, то и объект A будет потерян.
}

Короче живем как в случае с GC, но а) имея специальную кучу возврата для каждого потока; б) считая все ссылки на нее ссылками с еденичным владением.

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

Та как куча эта будет очень маленькой и автоматически освобождаемой, скорость ее работы будет не хуже чем у стека.

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

S>Тогда объекты, передаваемые из потока в поток надо будет аллоцировать в разделяемой куче, так?

Да, и только неизменяемыми. Изменяемые объекты можно передавать только по значению (копированием всего графа).

Как вариант, можно автоматизировать превращение изменяемых объектов в неизменяемые. Скажем, создаем АСТ как нам нравится, а когда оно уже создано, тупо публикуем его копию в неизменяемом виде. Эту копию можем распространять между потоками.

В обменной куче вообще могут жить только объекты с единичным владением.

S>И соответственно, принимать решение где размещать, надо в момент создания объекта, причём это придётся отдавать на откуп программисту. Или я торможу и что-то упустил?

Все еще жестче. Никакого размещения изменяемых объектов за пределами собственной кучи. И никакой возможности обращаться к ней из других потоков. Поток == псевдо-процесс.

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

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

Во-первых, потоки не объекты, а субъекты. В них ничего переехать не может. Это они могут обращаться к памяти или не могут. Если им в системе типов запретить обращаться к объектам не из своей или обменной кучи, то они это делать и не смогут. Исключение — рейдонли объекты размещаемые в разделяем[ой|ых] куч[е|ах]. Но эти объекты не могут ссылаться на локальные кучи.

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

S>В общем, для разделяемой кучи мы по любому возвращаемся к граблям традиционных gc. И что-то я не могу уловить, как свести соотношение "локальные объекты/разделяемые" к минимуму.

Не возвращаем. В них могут быть только "замороженные" (рейдонли) объекты.

VD>>А какие тут проблемы? Если весь объект распологается на стеке и мы это знаем, то замыкание (его объект) и итератор (его объект) тоже прекрасно будут жить на стеке.
S>Так возвращаемый IEnumerable может прожить дольше, чем A. Например, его возвращают как результат функции. Т.е. A на стек кидать можно не всегда.

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

S>Угу. Тогда надо будет пожертвовать верификацией недоверенного кода в рантайме, она слишком тяжёлой выходит. Я бы не сказал что это так уж критично, никто не мешает дополнительно проверять недоверенный код на машине клиента, аля peverify или вообще выполнять прекомпиляцию в натив.

Ну, не управляемый код ССЗБ. Тут должны быть правила маршалинга вроде тех что есть в дотнете.

S>Короче, тут никаких принципиальных препятствий нет, идею понял.

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

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

У меня есть трава покруче

Capabilities for External Uniqueness
http://infoscience.epfl.ch/record/135708/files/capabilities_for_uniqueness_TR.pdf
Никто не мешает нам создавать кучу при создании уникального объекта. И склеивать кучи при локализации.

... << RSDN@Home 1.2.0 alpha 5 rev. 62>>

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

DE>Формарльно, они всё-таки не отказались.
DE>Насколько легко нормальный ГЦ будет прикрутить — другой вопрос.

Если я ничего не пропустил, то невозможно. У них в стеке неуправляемые указатели хранятся.

VD>>а во-вторых, предлагают возиться с временем жизни явно, что заставляет программиста уделять этому слишком много времени.
DE>Что значит "возиться явно"? В моём понимании это рукопашные new/delete. В расте такого нет, в принципе. Указание лайфтаймов необходимо только в отдельных случаях.

Как ты понимаешь даже new/delete вручную не вызывают. Их засовывают в конструкторы и деструкторы.

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

DE>Опять же, ты предлагаешь решение, где точно так же надо будет вручную указывать. Принципиальной разницы не вижу.

Я предлагаю ограничивать указатели, а не вводить явно новую сущность вроде "времени жизни".

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

WH>Никто не мешает нам создавать кучу при создании уникального объекта. И склеивать кучи при локализации.

Что значит "локализация"?

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

DM>>first write access to a page allocated with VirtualAlloc+MEM_WRITE_WATCH: 1800 cycles
DM>>.. page allocated with VirtualAlloc+ResetWriteWatch: 1100 cycles
DM>>Ты думаешь, что если переложить на ОС, то все внезапно бесплатно и мгновенно? Наивный какой.

VD>А что ты не процитировал предыдущую строчку? Там написано, что VirtualAlloc без MEM_WRITE_WATCH стоит все те же 1800 циклов.

Ага, только обычно за это платишь один раз, а не много.

VD>Сброс делается только один раз при сборке не эфемерного (второго) поколения. По сравнению с барьером записи, где время тратится на каждое присвоение, это совершенно бесплатно.

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

DM>>Ню-ню. Опытный дядя хоть один GC написал в своей жизни? Или аллокатор хотя бы?
VD>Написал и не один.

Например?

DM>>Напомнить тебе типичный размер кэш-линии? Есть ли разница с т.з. кэша, лежат ли два объекта в 200 байтах друг от друга или в 200 килобайтах? (ответ — нет)

VD>Кэши бывают разных уровней. И разница огромна. Объекты бывают очень маленькие.

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

VD>Я вот, подумываю в сторону следующего подхода. ... Ну, что-то типа второго стека в котором нет ничего лишнего кроме возвращаемых значений и растущего не по мере входа в функцию, а по мере выхода из нее. Если хочется такой объект поместить куда-то в поле другого объекта или массив, то производится его перемещение в GC-кучу вместе со всеми объектами связанными с ним...

О, это уже интереснее, зря сразу не стал писать.

VD>Короче живем как в случае с GC, но а) имея специальную кучу возврата для каждого потока; б) считая все ссылки на нее ссылками с еденичным владением.

А как быть с:

f() {
  string s = "sss";
  tuple t = (s, 42); // упс, у нас уже две ссылки на s, копируем в GC кучу!
  return t;
}

VD>Та как куча эта будет очень маленькой и автоматически освобождаемой, скорость ее работы будет не хуже чем у стека.

А в какой момент происходит освобождение? Что будет тут:

f () {
  string best;
  for(int i=0; i<100000000000000; i++) {
    string data = g(); //  новый временный объект в возвратной куче
    if (some_condition(data)) best = data;
    net.write(data); // временный объект больше не нужен, если конечно не сохранен в best 
  } 
  return best;
}

И тут:

loop(int n) {
  if (n == 0) return;
  string data = g();
  net.write(data);
  loop(n-1);
} //в конец скоупа попадем лишь после всех итераций с выделением 1000000000000 объектов

От:	VladD2	www.nemerle.org
Дата:	27.10.14 19:16
Оценка:	93 (11) +1 -5

	От:	AlexRK
	Дата:	27.10.14 21:31
	Оценка:

	От:	Sinix
	Дата:	28.10.14 07:06
	Оценка:

От:	D. Mon	http://thedeemon.livejournal.com
Дата:	28.10.14 07:37
Оценка:	4 (2) +3

	От:	DarkEld3r
	Дата:	28.10.14 10:09
	Оценка:

	От:	Sharov
	Дата:	29.10.14 09:39
	Оценка:

	От:	WolfHound
	Дата:	29.10.14 12:45
	Оценка: