Выделение кучи Java быстрее, чем в C ++

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

Я читал комментарии к этому ответу и увидел эту цитату.

Инстанцирование объектов и объектно-ориентированные функции работают очень быстро (во многих случаях быстрее, чем C ++), потому что они разработаны с самого начала. и коллекции быстрые. Стандарт Java превосходит стандарт C / C ++ в этой области, даже для наиболее оптимизированного кода C.

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

1. Распределение кучи в Java лучше, чем в C ++

2. и добавил это заявление, защищая коллекции в Java

   И коллекции Java быстры по сравнению с коллекциями C ++ в основном из-за различной подсистемы памяти.

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

Это интересный вопрос, и ответ сложный.

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

C ++ может превзойти GV JVM с помощью специализированных распределителей памяти , которые предназначены для определенных целей. Примеры могут быть:

• Распределители памяти для каждого кадра, которые периодически стирают всю область памяти. Они часто используются в играх C ++, например, где временная область памяти используется один раз за кадр и сразу отбрасывается.
• Пользовательские распределители, управляющие пулом объектов фиксированного размера
• Распределение на основе стека (хотя обратите внимание, что JVM также делает это в различных обстоятельствах, например, посредством анализа побега )

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

Сборка мусора также дает некоторые существенные преимущества с точки зрения производительности:

• Реализация объекта действительно очень быстрая. Из-за того, что новые объекты размещаются последовательно в памяти, часто требуется чуть более одного добавления указателя, что, безусловно, быстрее, чем типичные алгоритмы выделения кучи C ++.
• Вы избегаете необходимости затрат на управление жизненным циклом - например, подсчет ссылок (иногда используемый в качестве альтернативы GC) чрезвычайно плох с точки зрения производительности, поскольку частое увеличение и уменьшение количества ссылок увеличивает нагрузку на производительность (обычно намного больше, чем GC) ,
• Если вы используете неизменяемые объекты, вы можете воспользоваться структурным разделением для экономии памяти и повышения эффективности кэширования. Это активно используется функциональными языками в JVM, такими как Scala и Clojure. Это очень трудно сделать без GC, потому что чрезвычайно трудно управлять временем жизни общих объектов. Если вы верите (как и я), что неизменность и совместное использование структуры являются ключевыми для создания больших параллельных приложений, то это, вероятно, самое большое преимущество в производительности GC.
• Вы можете избежать копирования, если все типы объектов и соответствующие им жизненные циклы управляются одной и той же системой сбора мусора. В отличие от C ++, где вам часто приходится делать полные копии данных, поскольку в месте назначения требуется другой подход к управлению памятью или другой жизненный цикл объекта.

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

Это не научное утверждение. Я просто даю пищу для размышлений по этому вопросу.

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

Ответ: просто сверните старый ковер; выбросить; и раскатать новый ковер.

Что мы здесь пренебрегаем?

• Стоимость перемещения существующих личных вещей, а затем переезда.
  • Это известно как «остановка мира» стоимость сборки мусора.
• Стоимость нового ковра.
  • Который, по совпадению для оперативной памяти, бесплатен.

Сборка мусора - огромная тема, и есть много вопросов как в Programmers.SE, так и в StackOverflow.

С другой стороны, менеджер распределения C / C ++, известный как TCMalloc, вместе со счетчиком ссылок на объекты теоретически способен удовлетворить требования к наилучшей производительности любой системы GC.

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

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

Это одна из причин, почему тесты Java / .NET показывают такую ​​хорошую производительность, а реальные приложения показывают такую ​​плохую производительность. У меня есть только взглянуть на приложения на моем телефоне - действительно быстро, реагирующие из них все написаны с использованием NDK, так сильно, даже я был удивлен.

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

Теперь с C / C ++ вы можете стать лучше, чем распределители по умолчанию, которые были разработаны для экономии памяти и ее эффективного использования. Вы можете заменить распределитель набором пулов фиксированных блоков, чтобы вы всегда могли найти блок, который точно соответствует размеру выделенного объекта. Прогулка по куче просто становится вопросом поиска растрового изображения, чтобы увидеть, где находится свободный блок, и перераспределение просто переустанавливает бит в этом растровом изображении. Стоимость состоит в том, что вы используете больше памяти при распределении в блоках фиксированного размера, поэтому у вас есть куча 4-байтовых блоков, другая для 16-байтовых блоков и т. Д.

Райское пространство

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

Я немного изучил, как работает Java GC, так как он мне очень интересен. Я всегда пытаюсь расширить свою коллекцию стратегий выделения памяти в C и C ++ (интересуюсь попыткой реализовать что-то подобное в C), и это очень, очень быстрый способ распределить множество объектов в пакетном режиме из практическая перспектива, но в первую очередь из-за многопоточности.

Способ распределения Java GC работает с использованием чрезвычайно дешевой стратегии выделения для первоначального размещения объектов в пространстве «Eden». Насколько я могу судить, он использует последовательный распределитель пулов.

Это намного быстрее с точки зрения алгоритма и уменьшения количества обязательных отказов страниц, чем общего назначения mallocв C или по умолчанию, operator newв C ++.

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

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

Коллекция

Как и в приведенном выше примере структуры данных / последовательного пула, было бы огромной проблемой, если бы Java GC выделял только этот путь, даже если он очень быстр для пакетного распределения многих отдельных блоков. Он не сможет ничего освободить, пока программное обеспечение не будет закрыто, и в этот момент оно сможет освободить (очистить) все пулы памяти одновременно.

Таким образом, вместо этого, после одного цикла GC, выполняется проход через существующие объекты в пространстве «Eden» (последовательно выделяемые), и те, на которые все еще ссылаются, затем выделяются с использованием распределителя более общего назначения, способного освобождать отдельные фрагменты. Те, на кого больше нет ссылок, будут просто освобождены в процессе очистки. Так что в основном это «копирование объектов из пространства Eden, если на них все еще есть ссылки, а затем очистка».

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

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

скорость

Таким образом, грубо говоря, причина, по которой Java GC может значительно превзойти C или C ++ при прямом выделении кучи, заключается в том, что он использует самую дешевую, полностью вырожденную стратегию выделения в потоке, запрашивающем выделение памяти. Тогда это экономит более дорогую работу, которую мы обычно должны выполнять при использовании более общего распределителя, такого как прямой mallocпоток для другого потока.

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

В этом главное отличие, и именно поэтому Java может очень выиграть у C или C ++, используя просто наивные вызовы mallocили operator newвыделять кучу маленьких кусочков по отдельности. Конечно, когда цикл GC запускается, как правило, будут некоторые атомарные операции и некоторая потенциальная блокировка, но, вероятно, он немного оптимизирован.

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

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

Все зависит от того, кто измеряет скорость, какую скорость реализации они измеряют и что они хотят доказать. И с чем они сравнивают.

Если вы просто посмотрите на распределение / освобождение, в C ++ у вас может быть 1 000 000 вызовов malloc и 1 000 000 вызовов free (). В Java у вас было бы 1 000 000 вызовов new () и сборщик мусора, работающий в цикле поиска 1 000 000 объектов, которые он может освободить. Цикл может быть быстрее, чем вызов free ().

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

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