Почему аллокация памяти в языках со сборкой мусора быстрее, чем в языках без них?

Уже не первый раз слышу, что скорость аллокации в куче в C# или Java быстрее, че
в C++. Я не могу понять, почему это может быть: аллокация в куче подразумевает поиск свободной страницы в памяти. Как это можно ускорить и правдивы ли слухи?
    

Ответы

Ответ 1

Да, эти слухи правдивы и имеют под собой основания.

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

В языках наподобие C# аллокация намного проще. Для нового элемента память выделяется просто на верху heap-памяти, и таким образом, аллокация сводится к простому

Interlocked.Increment(heapPtr, requestedSize);


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

В чём же разница? Дело в том, что сборщик мусора в .NET выполняет кроме самой сборк
ещё и уплотнение кучи (heap compaction): дыры в куче, возникающие на месте собранного мусора, заполняются другими объектами, и все указатели на них сдвигаются. Пример:

Аллоцированные объекты:

[ объект №1 ] [ объект №2       ] [ о. №3 ] [ о. №4                   ] [ о. №5     ]
                                                                                     ^
                                                                                     |
                                                                                  heapptr


Первая фаза сборки мусора (собраны объекты №1 и №4):

              [ объект №2       ] [ о. №3 ]                             [ о. №5     ]
                                                                                     ^
                                                                                     |
                                                                                  heapptr


Уплотнение:

[ объект №2       ] [ о. №3 ] [ о. №5     ]
                                           ^
                                           |
                                        heapptr


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

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



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



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