Насколько я понимаю есть два принципиально разных видов сборщиков мусора:
- mark and sweep
- reference counting.
Время работы mark and sweep пропорционально размеру кучу и количеству живых объектов в этой куче.
Reference counting не зависит от размера кучи, может зависеть только от размера удаляемой структуры (например, если есть дерево и количество ссылок на вершину дерева становится 0, то, как я понимаю, должно удалиться все дерево).
Но у reference counting есть недостаток, что он не может удалять циклические структуры.
Если этот недостаток как-нибудь обойти, то думаю, сборщик мусора на основе reference counting был бы быстрее, чем mark and sweep на больших объёмах памяти и с большим количеством объектов.