Какие-либо достоверные данные о GC против явной производительности управления памятью?

Question

Недавно я прочитал отличную статью Дэна Гроссмана "1001 * Транзакционная память / аналог сборки мусора ". Одно предложение действительно привлекло мое внимание:

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

До этого мое чувство всегда было очень расплывчатым. Снова и снова вы видите заявления о том, что GC может быть более эффективным, поэтому я всегда держал это понятие в затылке. Однако после прочтения этого у меня начались серьезные сомнения.

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

Это все экспериментально для меня. Кто-нибудь, особенно в контексте C ++, выполнил всеобъемлющий тест производительности GC по сравнению с явным управлением памятью?

Особенно интересно было бы сравнить, как различные крупные проекты с открытым исходным кодом, например, работают с GC или без него. Кто-нибудь слышал о таких результатах раньше?

РЕДАКТИРОВАТЬ: И пожалуйста, обратите внимание на проблему производительности , а не на то, почему существует GC или почему это выгодно.

Приветствия

Карл

PS. Если вы уже вытаскиваете огнемет: я не пытаюсь дисквалифицировать GC, я просто пытаюсь получить окончательный ответ на вопрос о производительности.

Answer 1

Это превращается в еще одну огненную войну с большим количеством "моего внутреннего чувства". Некоторые достоверные данные для изменения (документы содержат детали, тесты, графики и т. Д.):

http://www.cs.umass.edu/~emery/pubs/04-17.pdf говорит:

"Заключение. Спор о влиянии на производительность сборки мусора долгое время омрачал блага, предоставляемые разработчиками программного обеспечения. В этом документе представлен менеджер оракулярной памяти на основе трассировки и моделирования. Используя эту платформу, мы выполняем ряд неизмененных тестов Java с использованием обоих сборка мусора и явное управление памятью. Сравнивая время выполнения, потребление пространства и объем виртуальной памяти, мы обнаруживаем, что при наличии достаточного пространства производительность сборки мусора во время выполнения может быть конкурентоспособной с явным управлением памятью и даже превзойти его до 4%. Мы полагаем, что для копирования сборки мусора может потребоваться в шесть раз больше физической памяти, чем для распределителей Lea или Kingsley, чтобы обеспечить сопоставимую производительность. "

Когда у вас достаточно памяти, копирование GC становится быстрее, чем явно free() - http://www.cs.ucsb.edu/~grze/papers/gc/appel87garbage.pdf

Это также зависит от того, какой язык вы используете - Java придется много переписывать (стек, объекты, поколения) для каждой коллекции и писать многопоточный GC, который не должен останавливать мир в JVM, будет большое достижение С другой стороны, вы получаете это почти бесплатно в Haskell, где время GC редко будет> 5%, а время выделения - почти 0. Это действительно зависит от того, что вы делаете и в какой среде.

Answer 2

Стоимость выделения памяти, как правило, намного ниже в модели памяти с сборкой мусора, чем при явном использовании new или malloc, поскольку сборщики мусора обычно предварительно выделяют эту память. Однако явные модели памяти также могут делать это (используя пулы памяти или области памяти); сделав стоимость выделения памяти эквивалентной добавке указателя.

Как отметили Рэймонд Чен и Рико Мариани , управляемые языки обычно не выполняют неуправляемые языки в общем случае. Однако после его нажатия неуправляемый язык может и в конечном итоге превзойдет язык GC / Jinted.

То же самое видно и в Shootout Computer Language Shootout , потому что, хотя C ++ имеет тенденцию занимать более высокие места, чем Java, большую часть времени, вы часто будете видеть реализации C ++, проходящие через различные циклы (такие как объект бассейны) для достижения оптимальной производительности. Однако языки для сборки мусора, как правило, имеют более простые для понимания и более простые реализации, поскольку GC лучше выделяет (небольшие куски) памяти.

Тем не менее, производительность не самая большая разница, когда дело доходит до GC и не GC; возможно, именно детерминированная финализация (или RIIA) не-GC (и подсчитанных ссылок) языков является основным аргументом для явного управления памятью, потому что это обычно используется для целей, отличных от управления памятью (таких как снятие блокировок, закрытие файловых или оконных дескрипторов) и так далее). «Недавно», однако C # представил конструкцию using / IDisposable, чтобы сделать именно это.

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

С другой стороны, язык сборки мусора может выполнять самые оптимальные действия в самое оптимальное время (или приблизительно), не обременяя разработчика этой задачей. Это означает, что разработка для языка GC может быть более естественной, поэтому вы можете сосредоточиться на проблеме real .

Answer 3

Вот эксперимент, который мне нравится проводить:

1. Запустите программу, написанную в среде сборки мусора (например, .NET или Java).
2. Запустите аналогичную программу, написанную в среде без сбора мусора (например, C или C ++).
3. Используйте программы и посмотрите, какая из них более отзывчива.

Улучшение объективности: попросите бабушку выполнить шаг 3.

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

Другим, возможно, нелогичным примером этого является Eclipse IDE. Хотя это может быть написано на Java , вся графическая подсистема должна была быть переписана для получения приемлемой производительности. Решение: сделать элементы GUI облегченными оболочками вокруг собственных (C / C ++) компонентов ( SWT ).

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

Answer 4

Статья Бергера часто цитируется, но она сравнивает реальные сборщики мусора с чисто теоретическим, автономным, оптимальным алгоритмом. Так что, хотя он может рассказать вам кое-что о теоретических ограничениях, очень мало говорит о производительности реальных сборщиков мусора по сравнению с настоящими реализациями malloc и free. Исследование, которое мне больше нравится, взяло реальные программы и сравнило явные malloc и free с консервативным сборщиком мусора Ханса Бема:

Измеренная стоимость консервативного сбора мусора , Бен Цорн

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

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

Answer 5

Здесь приведено довольно много разных аргументов. Я хочу начать с пояснения, что вы не можете сделать сравнение 1: 1. У каждого есть свои плюсы и минусы, и любой фрагмент кода будет более подходящим для той или иной системы. Напротив, это означает, что вы должны знать, имеете ли вы GC или нет для написания эффективного кода.

Мой аргумент вы должны знать свою среду и код соответственно . Это сделает ваш код эффективным. Переход от одной парадигмы к другой и кодирование того же стиля сделают ваш код более неэффективным, чем то, что GC действительно помогает / убирает.

Корпус:

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

В среде без GC для каждого выделения вы в конечном итоге вызываете malloc, что требует поиска в списке свободных фрагментов памяти наиболее подходящего (в соответствии с конкретной реализацией malloc). Память используется, а затем освобождается бесплатно [или new / delete в C ++ ...]. Стоимость управления памятью - это стоимость размещения фрагментов.

В среде GC с подвижным GC, как java или .net, после каждого запуска GC вся свободная память является непрерывной. Стоимость приобретения памяти для объекта дешевая, действительно дешевая (инструкции <10 cpu в Java VM). При каждом запуске GC только живые объекты находятся и перемещаются в начало соответствующей области памяти (обычно это другая область, чем исходная). Стоимость управления памятью - это, прежде всего, стоимость перемещения всех достижимых (живых) объектов. Теперь предпосылка состоит в том, что большинство объектов недолговечны, поэтому в итоге стоимость может быть меньше, чем у системы без GC. Один миллион объектов, выделенных и освобожденных (забытых) за один прогон ГХ, не требует дополнительных затрат. </p>

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

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

Наглядным примером является неуправляемый программист, который используется для выделения объекта и повторного использования (для сброса его внутренних указателей с новыми элементами по мере необходимости) используется такой способ мышления: распределение дорого, повторное использование дешево. Теперь, если тот же самый точный код перемещен в среду GC поколений (Java, .net - оба являются Move-generational-GC), вы получите забавный эффект. В Java поколения GC система будет выполнять второстепенные коллекции только для младших поколений, обрабатывая только старшие поколения в полных коллекциях. Но объект в молодом поколении может упоминаться объектами в старшем поколении, поэтому необходимо выполнить дополнительную работу, чтобы отследить эти ссылки от старого к молодому. В частности, в сборщик мусора Java 1.4.1 система пометит карту памяти (часть страницы), где находится старый объект, и затем включит все отмеченные карты для обработки во время второстепенного сбора, эффективно увеличивая объем работы, которую должен выполнять GC и, возможно, влияющий на производительность.

Объект был жив во время 1, 2, 3 ... запусков ГХ, и его много раз перемещали, в конце концов перемещают в старое поколение, где его не будут перемещать при каждом прогоне ГК, а можно просто стоять там ... но увы, программист заставляет объект становиться моложе. Он перемещается еще раз и будет снова перемещаться каждый раз, когда GC подходит к тому моменту, когда он снова становится старым.

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

Answer 6

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

В системе GC, когда ваш симпатичный O (N) -код оказывается патологическим, что делает его O (размер кучи), может быть сложнее разобраться, что идет не так.

Во-первых, это часто случается, когда размер рабочего набора близок к максимальному размеру кучи. GC вызывается слишком часто, и поэтому все замедляется. Установите плагин Scala для Eclipse, и вы почувствуете это.

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

Вот пример исключения из этого: давайте возьмем «список карт f» и предположим, что каждое приложение f потребляет оперативную память, сохраняя ссылку на возвращенное значение в хеш-таблице. Здесь асимптотическая сложность все равно должна быть O (1).

Поколение GC не сможет освободить память, собирая детскую, поэтому основная коллекция (O (содержимое кучи)) вызывается несколько периодически. Следовательно, мы получаем, что время выполнения по крайней мере пропорционально (размер содержимого кучи) * n * (пространство, занимаемое каждым вызовом f) / (размер детской).

GC фактически увеличит размер питомника до указанного максимума, и затем вышеупомянутое произойдет снова для достаточно большого n. Однако если указанный максимум равен Big-Theta (максимальный размер кучи) и, следовательно, Omega (размер содержимого кучи), крупные коллекции становятся нечастыми, а стоимость небольших коллекций пропорциональна произведенным данным (и, следовательно, времени выполнения, необходимому для создания их). Это похоже на случай, когда вам нужно скопировать контейнер для изменения его размера: достаточно увеличить его, вы можете амортизировать стоимость копирования (или GC) и сделать его сопоставимым со стоимостью, необходимой для создания копии.

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

Наконец, речь идет не о дополнительных сборщиках мусора. Они решают проблему в корне, но они используются в основном для GC в реальном времени, из-за накладных расходов, которые они добавляют к чтению памяти. Azul System решила эту проблему на своем собственном HW с помощью GC Pauseless, благодаря поддержке HW для оптимизации этих накладных расходов. Они также недавно утверждают, что решили проблему и для x86, см. этот «пресс-релиз» и эту статью . Но он определенно находится в стадии разработки и не работает без изменений в ОС. Когда это будет сделано, и если производительность будет такой, как они предполагают, возможно, проблема будет решена и для нас, обычных смертных.

Answer 7

GC всегда будет медленнее, чем крайняя альтернатива: совершенное недетерминированное управление памятью.

Вопросы:

• Достаточно ли велики различия, чтобы их можно было оспорить?
• Достаточно ли недостатков одной техники, чтобы заставить нас серьезно рассмотреть другую?

Существуют и другие области, в которых управляемые подсистемы победили неуправляемые:

Как правило, программа всегда будет работать медленнее в многозадачной операционной системе, чем в однозадачной или на компьютере без ОС.

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

За исключением экстремальных обстоятельств, серьезно ли мы рассматриваем компьютерные системы без ВМ и без ОС?

Answer 8

В качестве эксперимента по измерению воздействия на языки GC некоторые люди взяли несколько программ на Java, отследили выполнение, а затем заменили сборку мусора на явное управление памятью. Согласно этому обзору статьи о Lambda, они обнаружили, что GC всегда был медленнее.

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

У меня нет проблем ни с чем из этого: их результаты немного интересны, но меня это не удивляет (Java для этого исключительно плохой язык, и алгоритмы GC, которые они использовали, были игрушками по сравнению с современными производственными виртуальными машинами, такими как Hotspot или .СЕТЬ). Тем не менее, они делали вид, что эти результаты обобщают, что абсолютно нелепо. Нет никаких оснований полагать, что их игрушечные ГХ являются репрезентативными производственными ГХ или что ООП является репрезентативным для всех программ или что их «оракулярное» управление памятью представляет собой ручное управление памятью.

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

Да. Не делай этого.

Это все экспериментально для меня. Кто-нибудь, особенно в контексте C ++, выполнил всеобъемлющий тест производительности GC по сравнению с явным управлением памятью?

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

Особенно интересно было бы сравнить, как различные крупные проекты с открытым исходным кодом, например, работают с GC или без него. Кто-нибудь слышал о таких результатах раньше?

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

Answer 9

Принципиальное отличие gc от любой реализации malloc заключается в том, что gc отслеживает выделенные объекты, в то время как malloc в основном отслеживает de выделенные объекты (через «свободные списки» и т. Д.). ., который должен был собирать освобожденные блоки памяти, чтобы быстро возвращать их после следования malloc) - некоторые реализации malloc даже не имеют (во внутренних структурах) возможности перечислить все выделенные блоки по конструкции. Как следствие, любая возможная реализация gc (независимо от того, насколько хорошей она может быть) всегда будет иметь сложность O (somefunc (N)), где N - количество выделенных объектов, в то время как большинство реализаций malloc имеют сложность O (1). Таким образом, когда количество (одновременно стоящих) выделенных объектов увеличивается все больше и больше, снижение производительности любого gc неизбежно (но, конечно, производительность можно обменять на дополнительное потребление памяти). [В конце концов очевидно, что свободные блоки памяти всегда имеют нулевые накладные расходы на обслуживание в отличие от выделенных блоков / объектов.] Это фундаментальный недостаток любого gc, так как он собирает поддерживает мусор :) , в то время как malloc поддерживает nongarbage (:.

P.S. Под malloc я подразумеваю не просто конкретную так называемую функцию C, а скорее любую явную процедуру выделения памяти. Кроме того, я хотел бы отметить, что языки программирования без встроенного gc предлагают много способов обернуться вокруг явных вызовов malloc / free (new / delete) (например, std :: shared_ptr в C ++ или ARC в Obj-C) это делает программный код похожим на языки на платформе gc, но с точки зрения производительности он намного ближе (почти эквивалентен) к явному распределению памяти. (Я знаю, что даже простой подсчет ссылок можно рассматривать как форму сборки мусора, но в этом посте под gc я имею в виду любую более функциональную реализацию (по крайней мере, с автоматическим определением циклов ссылок), которая требует отслеживания всех выделенные объекты, поэтому я не рассматриваю оболочки типа std :: shared_ptr как gc (по крайней мере, в этом посте)).

Answer 10

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

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