1Trading off Garbage Collector Speed vs Memory Use 2------------------------------------------------- 3 4Garbage collection inherently involves a space vs. time trade-off: The less frequently we collect, 5the more memory we will use. This is true both for average heap memory use, and also maximum heap 6memory use, measured just before GC completion. (We're assuming that the application's behavior 7doesn't change depending on GC frequency, which isn't always true, but ideally should be.) 8 9Android provides primarily one knob to control this trade-off: the `HeapTargetUtilization` option. 10This is a fraction between 0 and 1, normally between 0.3 and 0.8 or so. The collector aims to 11ensure that just before a collection completes and memory is reclaimed, the ratio of live data in 12the heap to the allocated size of the heap is `HeapTargetUtilization`. With a non-concurrent GC, 13we would trigger a GC when the heap size reaches the estimated amount of live data in the heap 14divided by `HeapTargetUtilization`. In the concurrent GC case, this is a bit more complicated, but 15the basic idea remains the same. 16 17Note that *lower* values of `HeapTargetUtilization` correspond to more memory use and less 18frequent GC. A high memory device (relative to memory requirements, which will usually depend on 19screen size, etc.) might use a value of 0.5, where a low memory device might use 0.75. 20 21This scheme is designed to keep GC cost per byte allocated roughly constant, independent of the 22heap size required by the application: 23 24GC cost is usually dominated by the cost of visiting live data in the heap. Assume that the GC 25cost is *cL*, where *L* is the number of live bytes in the heap, which we assume remains roughly 26fixed, and *c* is the cost of processing a byte of live data. If we abbreviate 27`HeapTargetUtilization` as *u*, we will collect whenever the heap has grown to *L/u* bytes. Thus 28between collections, we can allocate *L/u - L* or *L(1/u - 1)* bytes. This means the cost per 29byte allocated is *cL / L(1/u - 1)* or just *c / (1/u - 1)*, and thus independent of *L*, the 30amount of live data. 31 32(It's not clear whether we should really try to keep per-byte GC cost constant on a system running 33many ART instances. For a counter-argument, see [Marisa Kirisame et al, "Optimal heap limits for 34reducing browser memory use"](https://dl.acm.org/doi/10.1145/3563323). The current ART approach is 35more traditional among garbage collectors, and reasonably defensible, especially if we only have 36process-local information.) 37 38In fact GCs have some constant cost independent of heap size. With very small heaps, the above 39rule would constantly trigger GCs, and this constant cost would dominate. With a zero-sized heap, 40we would GC on every allocation. This would be slow, so a minimimum number of allocations between 41GCs, a.k.a. `HeapMinFree`, makes sense. Ideally it should be computed based on the 42heap-size-invariant GC cost, which is basically the cost of scanning GC roots, including the cost 43of "suspending" threads to capture references on thread stacks. Currently we approximate that with 44a constant, which is suboptimal. It would be better to have the GC compute this based on actual 45data, like the number of threads, and the current size of the remaining root set. 46 47`HeapMinFree` should really reflect the characteristics of the Java implementation, given data 48about the application known to ART. It is currently configurable. But we would like to move away 49from that, and have ART use more sophisticated heuristics in setting it. 50 51There used to be some argument that once application heaps get too large, we may want to limit 52their heap growth even at the expense of additional GC cost. That could be used to justify 53`HeapMaxFree`, which limits the amount of allocation between collections in applications with a 54very large heap. Given that in most cases device memory has grown faster than our support for 55huge Java heaps, it is unclear this still has a purpose at all. We recommend it be set to 56something like the maximum heap size, so that it no longer has an effect. We may remove it, or at 57least make it ineffective, in the future. However, we still need to confirm that this is 58acceptable for very low memory devices. 59 60Favoring Latency Sensitive Processes 61------------------------------------ 62 63For particularly sensitive processes, such as the foreground application or Android's system 64server, the bytes we allocate between consecutive GCs, as computed via the above controls, are 65multiplied by `ForegroundHeapGrowthMultiplier` + 1. Such applications thus use more memory 66in order to reduce GC time. 67 68When an application moves into the background, we normally trigger a GC to reduce its memory 69footprint before doing so. 70 71Interaction with Compacting Garbage Collectors 72---------------------------------------------- 73ART normally uses one of two compacting garbage collectors. These also have compile-time-specified 74heap density targets. These are in effect for collections other than those that prepare the 75application for moving into the background: 76 77'kEvacuateLivePercentThreshold', currently 75% is used for the CC collector, 78`kBlackDenseRegionThreshold`, currently 95%, is used for the CMC collector. Roughly speaking, we 79don't try to compact pages or regions that already exceed these occupancy thresholds, and we 80cannot reallocate the "holes" in uncompacted memory. This effectively prevents us from reclaiming 81some memory that remains fragmented after a GC. 82 83Some heap areas, e.g. those used for non-movable objects, are also subject to (usually very small 84amounts of) fragmentation, and are treated similarly. 85 86`HeapTargetUtilization` should thus be appreciably less than the relevant density target above, to 87ensure that, even in the presence of fragmentation, we generate enough compacted heap space to not 88instantly trigger another GC. (In the long run, we will probably compute these density thresholds 89from `HeapTargetUtilization` instead.) 90