Editing Tracing garbage collection (section)

== Performance ==
Performance of tracing garbage collectors – both latency and throughput – depends significantly on the implementation, workload, and environment. Naive implementations or use in very memory-constrained environments, notably embedded systems, can result in very poor performance compared with other methods, while sophisticated implementations and use in environments with ample memory can result in excellent performance. {{Citation needed|date=February 2020}}

In terms of throughput, tracing by its nature requires some implicit runtime [[computational overhead|overhead]], though in some cases the amortized cost can be extremely low, in some cases even lower than one instruction per allocation or collection, outperforming stack allocation.<ref>{{cite journal |last=Appel |first=Andrew W. |author-link=Andrew Appel |date=1987-06-17 |df=mdy |title=Garbage collection can be faster than stack allocation |journal=Information Processing Letters |volume=25 |issue=4 |pages=275–279 |citeseerx=10.1.1.49.2537 |doi=10.1016/0020-0190(87)90175-X |s2cid=2575400 |url=https://www.cs.princeton.edu/~appel/papers/45.pdf |access-date=2022-04-25}}</ref> Manual memory management requires overhead due to explicit freeing of memory, and reference counting has overhead from incrementing and decrementing reference counts, and checking if the count has overflowed or dropped to zero.

In terms of latency, simple stop-the-world garbage collectors pause program execution for garbage collection, which can happen at arbitrary times and take arbitrarily long, making them unusable for [[real-time computing]], notably embedded systems, and a poor fit for interactive use, or any other situation where low latency is a priority. However, incremental garbage collectors can provide hard real-time guarantees, and on systems with frequent idle time and sufficient free memory, such as personal computers, garbage collection can be scheduled for idle times and have minimal impact on interactive performance. Manual memory management (as in C++) and reference counting have a similar issue of arbitrarily long pauses in case of deallocating a large data structure and all its children, though these only occur at fixed times, not depending on garbage collection.

; Manual heap allocation:
* search for best/first-fit block of sufficient size
* free list maintenance

; Garbage collection:
* locate reachable objects
* copy reachable objects for moving collectors
* read/write barriers for incremental collectors
* search for best/first-fit block and free list maintenance for non-moving collectors

It is difficult to compare the two cases directly, as their behavior depends on the situation. For example, in the best case for a garbage collecting system, allocation just increments a pointer, but in the best case for manual heap allocation, the allocator maintains freelists of specific sizes and allocation only requires following a pointer. However, this size segregation usually cause a large degree of external fragmentation, which can have an adverse impact on cache behaviour. Memory allocation in a garbage collected language may be implemented using heap allocation behind the scenes (rather than simply incrementing a pointer), so the performance advantages listed above don't necessarily apply in this case. In some situations, most notably [[embedded system]]s, it is possible to avoid both garbage collection and heap management overhead by preallocating pools of memory and using a custom, lightweight scheme for allocation/deallocation.<ref>{{cite mailing list |last=Hopwood |first=David |date=2007-01-01 |df=mdy |title=Memory allocation in embedded systems |mailing-list=cap-talk |publisher=[[EROS (microkernel)|EROS]] |url=http://www.eros-os.org/pipermail/cap-talk/2007-January/006795.html |archive-url=https://web.archive.org/web/20150924001857/http://www.eros-os.org/pipermail/cap-talk/2007-January/006795.html |archive-date=2015-09-24}}</ref>

The overhead of write barriers is more likely to be noticeable in an [[imperative programming|imperative]]-style program which frequently writes pointers into existing data structures than in a [[functional programming|functional]]-style program which constructs data only once and never changes them.

Some advances in garbage collection can be understood as reactions to performance issues. Early collectors were stop-the-world collectors, but the performance of this approach was distracting in interactive applications. Incremental collection avoided this disruption, but at the cost of decreased efficiency due to the need for barriers. Generational collection techniques are used with both stop-the-world and incremental collectors to increase performance; the trade-off is that some garbage is not detected as such for longer than normal.