10 января 2017 г.

GC: golang и прочие

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

Последний месяц-два много шума из-за go. Команда разработчиков go рапортует о том, что в версии 1.5 их GC работает со средними паузами в районе сотен микросекунд, и максимальными < 10 миллисекунд ну и типа это "прорывное решение", "сборщик мусора для следующего десятилетия" и другие громкие заявления. В связи с этим хорошая статья Mike Hearn на medium: Modern Garbage Collection разбирает ситуацию (пока я писал, ее уже перевели на хабре).

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

В частности, нынешний "прорывной" сборщик мусора в go — это concurrent mark-sweep, прямой родственник и аналог OpenJDK-CMS в java. С той только разницей, что нет поколений — да, да, прямо сейчас в go (1.5) не используется сборка по поколениям (хотя это запланировано), собирается вся куча, как единый кусок. При этом, как и в OpenJDK-CMS, в асинхронном режиме нет compaction — куча дефрагментируется только в режим stop-the-world. Как результат: нужен довольно большой запас памяти, чтобы противостоять фрагментации (желательно примерно вдвое больше реально используемой), и на обход кучи тратится довольно заметная часть ресурсов CPU.

CMS в OpenJDK используется для старого поколения, в паре с копирующим сборщиком для молодого поколения. И наибольшие паузы (при правильной настройке), это паузы на сборку молодого поколения. Собирать молодое поколение в асинхронном режиме сложно, потому что сборщик молодого поколения — перемещающий (чтобы отслеживать асинхронно перемещаемые объекты понадобятся read barrier-ы). Но именно сборка молодого поколения позволяет снизить нагрузку на сам CMS — лишь небольшая доля объектов доживают до зрелости. Поэтому в джаве CMS (точнее, комбинация CMS + ParNew) в среднем более эффективен с точки зрения накладных расходов: какой избыток памяти нужен, и какую часть CPU time заберет GC.

В мире realtime java в свое время предлагался Metronome — сборщик мусора для систем реального времени, для которого можно доказать ограничения на величину вносимых им пауз (правда, паузы там все равно были в районе миллисекунд, но это 2003 год). Платить за это приходилось серьезными затратами CPU: сборка мусора съедала аж 50% процессорного времени. В go, вроде бы, все не настолько плохо, но и их GC отъедает десятки процентов CPU в нормальном режиме работы. В джаве нормально настроенный GC обычно ест ~5%

Gil Tene в дискуссии на mechanical sympathy справедливо замечает, что любому техническому решению нужно время, чтобы созреть. Неразумно выносить какие-то окончательные суждения про go GC сейчас, когда весь проект go еще очень молод — он еще 100 раз успеет мутировать. С его точки зрения, пока что главная опасность в нынешнем сборщике мусора go — это отсутствие перемещений объектов. Без перемещения объектов сборка мусора неизбежно будет приводить ко фрагментации, и это станет серьезным камнем преткновения по мере развития платформы. Опасность в том, что такое решение может оказаться зафиксированным просто де-факто — пока это так в нынешней реализации, авторы сторонних библиотек успеют заложиться на фиксированные адреса объектов в памяти, и уже нельзя будет поменять это, не поломав обратной совместимости для большого количества существующего кода.

Чтобы больше погрузиться в тему компромиссов при сборке мусора: хорошая статья A Unified Theory of Garbage Collection. Авторы задались целью показать, как различные подходы к автоматическому управлению памятью на на самом деле представляют собой полюса одного непрерывного спектра решений. И изначально различные реализации по мере обретения зрелости обрастают эвристиками, оптимизациями, становятся все более гибридными, и все меньше отличаются друг от друга. Авторы рассматривают подсчет ссылок (reference counting) и трассировку (tracing) объектов как своего рода взаимо-дополняющие методы управления памятью: где один из них хорош — другой плох. И любая зрелая реализация трассировки со временем обрастет оптимизациями, представляющими собой, по-сути, ограниченный подсчет ссылок — и наоборот. Например, card marking, который используется в generational GC чтобы отслеживать ссылки из старого поколения в молодое — это ни что иное, как вырожденная форма reference counting. Вообще, write barrier-ы — это прямое указание на какую-то форму подсчета ссылок.

Другая весьма старая (но не менее интересная) статья Hans Boehm-а на тему компромиссов: Mark-sweep vs. copying collection and asymptotic complexity. Ханс рассматривает Mark-Sweep и копирующий сборщики, и задается вопросом, насколько их общеизвестные теоретические свойства действительно реализуются в реальных условиях.

Например: считается, что время работы копирующего сборщика пропорционально количеству живых объектов, в то время как для Mark-Sweep это время пропорционально общему объему кучи. Такая оценка Mark-Sweep основана на том, что в sweep-фазе нужно обойти все "мертвые" объекты, чтобы добавить их во free-set. Ханс замечает, что sweep-фаза вообще не является обязательной: можно ставить пометки только на живых объектах, а при аллокации сканировать кучу напропалую, ищя первый кусок памяти без пометки "живой". Этот алгоритм будет эффективен, если значительная (бОльшая) часть кучи после сборки окажется пустой — но ровно же в этом случае и копирующий сборщик становится эффективным!

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

12 комментариев:

  1. Хм... Ну все-таки мне кажется что надо смотреть не на go 1.5 а на 1.8 там все немного интереснее. К примеру я не знаю как настроить newgc в Яве чтобы он укладывался в миллисекунду, про сотню микросекунд даже мечтать не приходится... И получаем "хвосты" в верхних percentiles с которыми ничего не сделать

    ОтветитьУдалить
    Ответы
    1. Я тоже думаю, что никак не настроить -- ниже 5-7мс уже практически не опуститься.

      Но об этом и речь -- OpenJDK просто не целится в этот регион, вот никто и не торопится оптимизировать StringTable.purge, который занимает под миллисекунду, и зачем-то выполняется на каждой малой сборке.

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

      Удалить
    2. да, все верно 5-7мс... и вообще нет альтернативы - широко распиаренный азул убивает latency (медиану) почти в два (два!!!) раза или вообще валится.
      поэтому и получается, что в убогом (в смысле языковых возможностей) go медиана сдвигается на 10-15% но при этом хвосты срезаются больше чем в 10 раз. При этом нам продолжают петь про varhandles, immutable и performance. Хочется уже не слышать этот цирк, потому что 95% софта (jira like) вообще до лампочки на longAdders, putOrdered, scalarization и тому подобные вещи... А там где это важно, там newgc со своими неубиваемыми 5мс, которые чаще или реже но будет случаться регулярно

      Удалить
    3. очень интересные данные - у меня есть весьма поверхностный опыт с shenandoah - и там медиана тоже слезла где-то в 2 раза

      Удалить
    4. @nevgeniev я не очень понимаю всех этих стонов про GC. У меня тут уже была дискуссия с одним знакомым на эту тему: мой поинт в том, что джаву кормят и растят вовсе не единицы процентов low-latency, а миллионы websphere/tomcat/resin/etc. И им на неустранимые паузы в 5мс насрать. Это не значит, что в том мире нет проблем с GC, но там нет _неустранимых_ проблем с GC.

      А longadders/varhandle/т.д. -- это, вообще-то, часть самой платформы, в первую очередь -- инструменты делать саму джаву быстрее. В том числе удерживать за джавой роль одного из лучших языков для эффективной реализации многопоточных алгоритмов. Тех самых алгоритмов, которые внутри вебсферы/томката/акки. Именно для их разработчиков и есть "весь этот цирк" -- потому что именно разработчики таких систем вносят существенный вклад в экосистему джавы, обеспечивая работой миллионы менее квалифицированных программистов.

      А единицы процентов разработчиков low-latency trading систем -- вряд ли приносят ораклу хоть сколько-то существенные деньги. Большинство из них еще и обложены NDA по самые гланды, поэтому и известности платформе они тоже не приносят. Так смысл в них вкладываться?

      Другими словами: да, с неустранимыми паузами на сборку мусора в джаве есть проблемы. Да, эти проблемы стали более актуальными последние годы. Но если бы эти проблемы начали решать заранее -- то не успели бы решить другие проблемы (throughput), которые актуальны гораздо бОльшему числу людей, делающих джаву той джавой, которую мы знаем.

      @Vladimir Dolzhenko: ну, это не очень удивительно -- и в азуле, и в shenandoah же используются барьеры на чтение. В цинке что-то хитрое, в shenandoah -- forwarding pointers. Получается, что каждое чтение через ссылку становится медленнее -- неудивительно, что это дает заметный эффект. Правда вдвое я не ожидал, я видел касательно азула более скромные цифры, ну а shenandoah еще все-таки молодой...

      Удалить
    5. @Vladimir Dolzhenko: не хочешь про свой опыт с shenandoah написать пост?

      Удалить
    6. я не то чтоб "стенаю по гц", но да для 2017года пауза 5млс это как секунда где-нибудь в 2005м... и да, я понимаю что lowlatency системы на фоне армий томкатов меркнут и гораздо важней соптимайзить String.hashCode()... но по части throughput тоже ведь не совсем "фонтан" avx-а нет, arrays 2.0 будут к нашей пенсии... Т.е. мой поинт в том что оракл вообще КАТАСТРОФИЧЕСКИ недоинвестирует в java и гэп между потребностями и реализацией он скорей растет чем сокращается

      Удалить
    7. @nevgeniev

      А кто и во что инвестирует достаточно? Есть какой-то пример, на котором видно, как компания Х достаточно инвестирует в свой продукт У -- так, что не придраться?

      У джавы есть 100500 сценариев использования. И у каждого из них -- свои гэпы между потребностями и реализацией. В какие из этих гэпов инвестировать?

      Этим-то система возрастом уже в четверть века отличается от новоделов типа go/rust/etc. go решают текущую задачу, которая пока что достаточно узкая. Сколько проектов живет на этом go? Сколько разных сценариев использования? Да нисколько. Лет через 15 go огребет такие же проблемы с поддержкой всего этого легаси.

      Другой хороший вопрос: причем здесь Оракл? В смысле: почему именно оракл должен инвестировать во все хотелки сообщества? Оракл делает на джаве свой кусок хлеба с ветчиной, и принимает инвестиционные решения исходя из этого. Рассуждать о том, во что Оракл инвестирует достаточно, а во что -- недостаточно это заглядывать в чужой карман.

      Удалить
    8. поднятые вопросы тянут на тему для поста :), но постараюсь кратко:
      1. почему оракл? потому что он ЕДИНСТВЕННЫЙ product owner, он уже это всем объяснил в суде. никакая крупная компания не будет инвестировать в разработку java платформы - ни гугл, ни ibm, ни интел, ни amd (последних как-то даже жаль, потому что оракл их "прокинул" два раза - сначала с aparapi потом с hsa.

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

      2. 100500 сценариев... не совсем согласен - 100500 полезных библиотек и фреймвоков - да. но к развитию jvm платформы они отношения никакого не имеют и оракл там не тратит ни копейки

      3. кто инвестирует достаточно или "правильно"? не знаю... но возьмем, к примеру с#, который ничего кроме улыбки не вызывал. И что мы видим?
      a) точки зрения языковых возможностей ява обогнана уже видимо навсегда
      b) "прямая" и дешевая интеграция с нативным кодом
      c) массивы структур
      d) нормальные generics
      да, там дофига еще проблем в рантайме и нет такого набора библиотек, но динамика развития радует

      Я прошу понять меня правильно - я не агитирую никого бросаться в go, rust, c# или еще чего.. Посыл в том, что ява находится в глубокой стагнации и света в конце тоннеля не видно

      Удалить
    9. @nevgeniev

      >поднятые вопросы тянут на тему для поста

      You're welcome :)

      >потому что он ЕДИНСТВЕННЫЙ product owner. никакая крупная компания не будет инвестировать в разработку java платформы

      То есть Azul, IBM, RedHat -- они не инвестируют? Или вы что-то конкретное понимаете под инвестициями в платформу?

      >о рациональности развития платформы заглядыванием в чей бы то ни было карман...

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

      Я погорячился с чужим карманом -- это в карман Ларри заглядывать нехорошо, а в карман публично торгуемой компании вполне себе нормально. Дело тут в другом: если уж заглядывать в карман, то квалифицированно. Я вот не знаю, как именно и сколько оракл зарабатывает на своих эксклюзивных правах на джаву -- поэтому я и не могу оценить, как поменяются их доходы, если они реализуют Arrays2/StructuredArray вместо, например, VarHandles/Graal. Вы можете оценить? Сомневаюсь.

      Оракл не делает добро. Оракл не делает даже джава-платформу. Оракл делает деньги. Платформа -- это один из способов делать деньги. Пока arrays2 не звучат как способ серьезно увеличить доходы -- их реализация ораклом это просто благотворительность.

      >2. 100500 сценариев... не совсем согласен - 100500 полезных библиотек и фреймвоков - да. но к развитию jvm платформы они отношения никакого не имеют и оракл там не тратит ни копейки

      Тратит, конечно. Все эти 100500 библиотек и сценариев должны продолжать работать -- это называется обратная совместимость. Она очень даже много ресурсов стоит.


      >a) точки зрения языковых возможностей ява обогнана уже видимо навсегда
      >b) "прямая" и дешевая интеграция с нативным кодом
      >c) массивы структур
      >d) нормальные generics
      >да, там дофига еще проблем в рантайме и нет такого набора библиотек, но динамика развития радует

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

      > Посыл в том, что ява находится в глубокой стагнации и света в конце тоннеля не видно

      Любая зрелая технология находится в глубокой стагнации по сравнению с новоделом. Потому что если бы она не была в стагнации -- она была бы новоделом.

      Удалить
    10. не флэйма ради, но в яве нет 100% обратной совместимости - нельзя просто так взять приложение из 2003 года откомпилировать и запустить под jdk8. менялся api, контракты методов итп... да не так стремительно как это делает .net или кто-нибудь еще. но это факт

      т.е. абсолютной 100% совместимости нет ни у кого. дальше вопрос, является ли совместимость самоцелью, или мы признаем fail fast подход правильным и подходим к ней с прагматической точки зрения... в яве обратная совместимость - это догмат вбитый всем в голову, но это не значит что он верен. Вот к примеру ну есть в jdk8 класс Vector, а зачем? Кто-то действительно считает что без него в 2017-v никуда, потому что не скомпилируется библиотека 2001 года? так она если и скомпилируется, то работать будет неправильно.

      про разницу развития платформ и количество библиотек - так ведь тоже можно поспорить... вот возьмем экосистему (платформу) javascript там npm пакетов уже больше чем в мавене, при этом динамика развития наверное на порядок выше явы - т.е. получается что это не особо-то связанные вещи

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

      оракл понятно никакого дискомфорта не испытвает, потому что он (в отличии от sun) делает не платформу а деньги, тут вы все правильно подметили

      Удалить
    11. >нельзя просто так взять приложение из 2003 года откомпилировать и запустить под jdk8. менялся api, контракты методов

      Я бы сказал -- не всегда можно. Но часто -- можно, и перекомпилировать не потребуется. А если речь не о приложении, а о библиотеке -- так и часто можно. Какой-нибудь trove не обновлялся с 2003, но вполне себе работает, и приносит пользу.

      >это догмат вбитый всем в голову, но это не значит что он верен

      Это не догмат, это выбор. Design choice. Чтобы говорить, верен он или нет -- надо выбрать какую-то метрику, и смотреть на нее. По метрике "популярность и распространенность", например, ява уже лет 15 как стабильно в лидерах. Конечно, по метрике "популярность среди хипстеров-стартаперов" результат будет другой :)

      >возьмем экосистему (платформу) javascript там npm пакетов уже больше чем в мавене

      Проектов масштаба JBoss/tomcat там тоже больше, чем в джаве? Или вы имеете в виду пакеты типа небезызвестного trim, или как он там назывался?

      -----

      Моя точка зрения простая, я ее уже излагал: каждая платформа это совокупность всех ее design decisions, явных, не явных, и случайных. Они работают вместе, а не по отдельности -- формируя платформе историю, сообщество, инфраструктуру и клиентов. Когда мы мечтаем о каких-то изменениях, мы обычно грезим о каких-то конкретных последствиях -- удобных для нас. Но последствий будет гораздо больше, и не все они будут для нас так же удобны.

      Мне тоже не хватает нормальных массивов и массивов структур, например. Но я представляю себе масштабы изменений, потребных для этого. Я представляю себе масштабы тестирования, потребного чтобы _даже сейчас_ просто обновить версию джавы с 1.7 на 1.8 -- мы потратили несколько месяцев на переход.

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

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

      Удалить