ЕЗЫГ МОЙ. Брейн-дамп номер 1. Короткий, но про войну c GC.

GC сегодня не только GC, а ещё и иллюзия решения проблем lifetime-а.

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

GC масштабируется за счёт непредсказуемой производительности и\или неочевидных расходов памяти. GC бывает «все встали и теперь collect» и «долго лазить в указатель». GC стоит памяти, скорости, а обычно оба. Hint-ы проблему не решают, только откладывают.

C GC трудно, но хуже без GC. Будем думать и делать выводы. Итак спеки.

Для real-time приложений предсказуемость производительности критична. GC не должен создавать никаких подводных камней, т.е никакой алгоритм не должен менять O(N) из за GC – ещё проще, allocate\free\assign должны быть O(1) операциями с малым С. Дереференс указателя должен быть бесплатный. Операция Collect должна жестко фиксироваться по времени – т-е либо быть достаточно быстрой O(nBlock), либо должна фрагментироваться на куски гарантированно малого размера, либо как-то жить асинхронно (во что я не верю).

Для внятного lifetime нужны не только strong, но и weak указатели. Для временных объектов нужно уметь выделять их на стеку – впрочем компилятор очевидно способен отличать временный объект от постоянного, это не требует hint-ов. Изжить null pointer exception не получится, но not-null policy очевидно позволяет ловить такое рано, особенно на weak указателях – часть таких случаев может вылечить компилятор.

Мне больше всего нравится гибридная модель – refcount + mark&sweep. В ней большинство объектов будет умирать за счёт refcount-а ещё до того, как дело дойдёт до collect. Адаптивный free-list обеспечивает O(1) для free, и практически всегда O(1) для allocate. Модель легко масштабируется «вниз» за счёт компилятора, т-е для объектов без циклических ссылок можно откатываться на голый refcount.

Все эти «радости» могут наступать исключительно за счёт расходов памяти. 24 байт на тяжелый указатель, 28 байта на объект – я не знаю насколько допустимы такие расходы памяти. Ниже немножко драфтов

http://www.everfall.com/paste/id.php?v9ivatukaam9

  • IronPeter

    Оффтопиковый,флудовый коммент. Для исходников хочется SVN репо на ресурсе. Потому что выкладывать код на everfall – очевидно gay.

  • look4awhile

    ага. а сувать в текст сообщения – ещё противнее.
    впрочем проекту “езыг мой” очевидно нужен свой репозиторий.

  • http://aruslan.livejournal.com/ aruslan

    еще более оффтопик – Боря, свяжись со мной.

  • look4awhile

    2 aruslan: перед отъездом ещё заслал. не получил???

  • http://_gvozdoder_.livejournal.com gvozdoder

    Еще часть объектов может убить сам компилятор. Например auto объекты, в самом простом случае. В более сложном случае можно посмотреть на Region Inference (http://en.wikipedia.org/wiki/Region_inference). Вроде как есть реализации ЯП, в которых память управляется исключительно с помощью Region Inference.

  • http://aruslan.livejournal.com/ aruslan

    2 look4awhile – нет.

  • http://alexwwolf.livejournal.com/ alexwwolf

    Так. А теперь, если можно, поподробней. Берем мой любимый C#, запускаем в отдельном потоке GC.Collect(). Для большего эффекта предположим, что работаем в системе с двухядерным процем и поток с Collect ухитрились запустить на втором ядре (на первом – остальные потоки приложения). И почему в этом случае должна быть потеря производительности? Не понимаю… Если есть какие-нибудь ссылки, просьба кинуть их мне – буду разбираться. Спрашивал у коллег – все пожимают плечами :)

  • look4awhile

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

  • IronPeter

    Хех, ну если коллеги пожимают плечами – то они не специалисты по низкоуровнему С#. Система сборки мусора в C# дает пищу для десятка блогеров в MS. Все пишут, пишут…

    Region Inference это крайне странная забава. Слабо представляю, как можно управлять памятью в динамическом мире за счет статического анализа кода. Верю немного в другое – в явный алиасинг объектов в регионы. Скажем, тот же кусок статического игрового уровня может быть рожден на непрерывном куске памяти, все gc указатели внутрь региона переправляются на его начало. Если делаем так, то GC граф получается тоньше. И при выделении памяти можно быть проще.

    Что до конкретной реализации – то я не вижу в ней какой-то особенной религиозности. Вот мне было бы интересно отделить объекты от GC графа, то есть сделать template class GCObject { T * rawObject; GC_STUFF; }. Сам GC граф тонкий, его ноды выделяются в пуле, наружу торчат ссылки на объекты на хипе. Причем не просто на объекты – а на регионы.

    Еще у тебя указатели жирные, Боря.

  • look4awhile

    указатели очевидно жирные. потому что очевидный драфт
    можно сделать чуть тоньше почти без потерь. можно сделать сильно тоньше – с потерями в производительности
    вообщем “высоких полон дум”

  • IronPeter

    кстати да, а зачем тебе счетчик?

  • IronPeter

    я в том смысле – что он дублирует и так известную инфу про длину кольца ссылок на объект.

  • look4awhile

    счётик нужен для того, чтобы те кто может сдохнуть сразу – дохли сразу

  • IronPeter

    ну вроде у нас есть интрузивный список ссылок на объект, если его длина 0 – то дохнуть надо?

  • http://alexwwolf.livejournal.com/ alexwwolf

    Нашел таки статью на русском про реализацию GC в .NET. Там, кстати, и ответ на мой вопрос – про попытку собирать мусор на отдельном ядре/процессоре. Все, оказывается, просто:
    1) проблемы синхронизации можно (отчасти) избежать, заведя по куче на каждый проц
    2) это не слишком поможет, поскольку при сборке мусора все равно производится полная остановка всех управляемых потоков. Вот он – момент истины! :)

  • IronPeter

    Ты плохо читал. В платформе .NET есть режим concurrent gc, без заморозки потоков но с примитивами синхронизации.

  • http://nesnausk.org ReJ

    А ваще зачем garbage collector для С++ в контексте геймдева? Почему не просто комбинация С++/Lua или С++/Python – каждый со своими плюсами для задач на разных уровнях?

  • look4awhile

    из багобазы. все мои мысли растут из трёх документов

    один это расписание работ
    второй это багобаза
    третий это обзор игры

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

  • http://users.livejournal.com/_zerg/ _zerg

    alexwwolf, вы несколько противоречите сами себе
    “Для большего эффекта предположим, что работаем в системе с двухядерным процем и поток с Collect ухитрились запустить на втором ядре (на первом – остальные потоки приложения).”
    и
    “проблемы синхронизации можно (отчасти) избежать, заведя по куче на каждый проц”

  • http://virtul.livejournal.com virtul

    Кстати вот наткнулся в сети. Может пригодится.
    http://en.wikipedia.org/wiki/Boehm_GC

  • http://nesnausk.org ReJ

    look4awhile: Перефразирую свой вопрос – а нужен ли ГЦ для тех задач которые под С++ пишуться?

    Например: рендеринг, анимация, физика – тут в принципе ничего особого нового, memory access паттерны достаточно ясны, об динамической алокации памяти разговора ваще недолжно быть (хотя бы даже из-за причин по СЕМЕНовому посту об memory и latency), да и ненужно – lifetime большинства объектов 1 фрейм (фрейм аллокаторы и статические буффера) либо оно shared ресурс (refcount).

    Более высокие модули тоже могли бы стать стабильнее и может даже случайно быстрее, если уменьшать в них динамические алокации – конечно не с самого начала, но так, в процессе рефакторинга – по пути анализируя своиственным им memory access паттерны.

    А там, где в коде полный креатив с памятью творим – так может пусть оно в Петоне и живёт с часа 0?

  • Knives

    В С++ ГЦ, действительно, нафиг не уперсо. ГЦ это лишь побочный эфект реализации абстрактной идеи о бесконечной памяти, противоречивой самой по себе (не только реальная память конечна, но и никакого разумного сценария действий при упирании в этот конец нет), но и противоречащей целям, для которых С++ обычно применяется, а именно – программирование высокопроизводительных и нераскидывающихся ресурсами систем. Про игры я вообще промолчу, всерьез размышлять о бесконечной памяти на системе с 32М оной и датасетом на 9гигов или, даже 512М/50Г, это за гранью добра и зла.

  • look4awhile

    В С++ GC очевидно не упёрся.
    Буду отсылать опять к брейндампам с 0-го и дальше – на предмет “зачем”.
    Никакой бесконечной памяти совсем никак не предвидится.
    Смысл GC в языке – трейдофф времени разработки. А именно лечить проблемы lifetime в сложных зависимостях.
    Т-е чтобы быстро писать разумно быстрый игровой код.
    Петон к “быстро” не относится, к сожалению, никак.

  • look4awhile

    Читал исчо. GC как побочный эффект “бесконечной памяти”. Задумался :) Всё чудесатее и чудесатее.
    Если вернуться к истокам лиспа, то, наверное, так оно и было.

  • Knives

    А ничего и не поменялось, насколько мне известно, в современных языках с ГЦ, даже если существование ГЦ делаеццо видимым для программиста (типо можно поставить колбэк на ГЦ для конкретного объекта или вызывать ГЦ вручную) это самое ГЦ не гарантируеццо и корректная программа должна работать в предположении, что ни один объект, ни одна аллокация, не будут уничтожены, как если бы ее запустили в бесконечной памяти. Тут, видимо, дело привычки, и, наверное, тому, кого учили программировать на яве, так же трудно занимаццо менеджментом ресурсов, как программистам, переходящим с бейсика на паскаль было трудно декларировать переменные перед использованием, так что я не вижу никакого принципиального ускорения разработки. Я вообще не верю в “языковое ускорение”, о котором поклонники “нетрадиционных” языков постоянно заявляют. То есть курсовик какой-нибудь или халтурку, действительно, можно, на хаскеле там или форте написать быстрее, чем на С++, а вот реальную программку, за которую можно получать серьезное бабло – нельзя. Обращаю внимание, ключевое слово здесь “быстрее”. То есть существуют, конечно, серьезные программки написаные не на С/С++, однако никаких чудес производительности труда, при их создании не было зарегистрировано.

  • look4awhile

    у меня строго противоположный пример перед глазами.
    это goal, который лисп от naughty dog – на нём сильно другая производительность труда; сравнения с последним проектом (который на С++) показательные.
    скорость там очевидно не напрямую из-за GC, а из-за скорости итерации; GC при этом просто один из механизмом, который такую скорость обеспечивает.

  • Knives

    у меня строго противоположный пример перед глазами.
    это goal, который лисп от naughty dog – на нём сильно другая производительность труда; сравнения с последним проектом (который на С++) показательные.

    Я его как раз и имел ввиду, когда говорил, что в принципе можно чегой-то написать, но быстрее не получиццо, чего там “противоположного”? Три года, на игру и потом по году на сиквел, без малтиплатформы – ацкая производительность? По-моему: еще медленее и они бы закрылись даже не смотря на СКЕА,

  • look4awhile

    три года на игру + компилятор + отладчик итп. начальные вложения очевидно крайне злые.
    а год на сиквел – такого объёма – давольно таки быстро.
    малтиплатформ очевидно никакой. медленне – не сказал-бы.
    закрылись – тут тонко всё. скорее нет чем да. всё очень хорошо продавалось.

  • Knives

    три года на игру + компилятор + отладчик итп. начальные вложения очевидно крайне злые.
    Они кому-то этот отладчик с компилятором продали? Они их сейчас используют? Весь выхлоп, что у них получился – игра. Вот Фактор 5 за 9 месяцев сделал игрушку для кубика без всяких компиляторов и прочих лиспов, это я понимаю производительность.

    а год на сиквел – такого объёма – давольно таки быстро.
    За год можно игру сделать совсем новую, а не сиквел. Малтиплатформеную если постараццо. Но, в общем, если ты считаешь такие сроки чем-то экстраординарным то чего мне тебя убеждать?

  • look4awhile

    они продали контору в SCEA. большей частью из-за тека. сейчас используют, на PSP.
    ещё тот-же тек попал в ratchet&clank – рендерящая его часть.
    выхлоп – 8 или 9 игр. в трёх, что-ли, разных конторах

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

  • Knives

    они продали контору в SCEA. большей частью из-за тека.
    Можно, конечно, думать, что Сони купила владельца одной из самых успешных американских АйПи из за крютого лиспа, если хочеццо жить в мире илюзий =)

    На ПСП я очень сомневаюсь, НД нирожна для ПСП не сделала. Кто-то еще их лиспом пользовался? То что они дали инсоманьяку – скорее всего просто библиотечки режим экрана ставить да дма чейны собирать, никакого лиспа там не было да и Инсоманьяк в здравом уме не взял бы. И никто не взял. И сам НД его выкинул. Ибо убедились на собственном опыте, чем это вышло.

  • look4awhile

    IP ( в то время Crash ) продали в юниверсал, отдельно от конторы. до того как.
    покупал не лисп а джейсона и энди.

    почему НД выкинул – отдельная история.

    впрочем дальше беспредметно.

  • deemetrius

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

  • deemetrius

    {[
    ага. а сувать в текст сообщения - ещё противнее.
    впрочем проекту “езыг мой” очевидно нужен свой репозиторий.
    ]}
    Появился репозиторий? Или нет пока?