Kaffe's garbage collector is a classical conservative collector that follows the tricolor scheme, and it is not very sophisticated. However, by tweaking its parameters, it is sometimes possible to speed up applications significantly. This FAQ explains an gc strategy I implemented for Kaffe and it should answer the following questions: + How does Kaffe decide when to garbage collect and when to get more memory from the operating system instead? + How does Kaffe use the parameters specified by the -ms and -mx switches? What's that -as switch for? What values should I choose for what applications? Kaffe recognizes the following three switches, which can be followed by a numerical argument (either immediately following the switch, as in ``-mx32M'', or separated by a space as in ``-mx 32M'') specifying a byte amount. K/k and M/m suffixes denote Kilo and Mega bytes, respectively. Default -ms: 5M This value specifies the initial heap size. When Kaffe starts up, it will request this amount of memory upfront from the operating system and add it to the heap it manages. -mx: 64M This value specifies the maximum heap size. Kaffe will never request more memory than that from the operating system. Note that the total memory usage of kaffe may be higher since libraries such as Xlib may obtain memory from the operating system without consulting Kaffe's allocator. Note further that Kaffe's internal data structures will be allocated from that heap as well (not only the garbage collectable objects produced by your application.) -as: 1M This value specifies the heap increment. The heap increment is the amount of memory Kaffe will request from the operating system to add to the heap it manages if it decides to postpone a collection. See below what ``postponing'' means. If kaffe's allocator is asked to provide some memory, it follows a simple strategy. First, it checks whether there is some free memory of the corresponding size in the heap it manages. If so, this memory is returned. This means that kaffe won't ever invoke the garbage collector until it uses more memory than the initial heap size specified using the -ms switch! Therefore, increasing the initial heap size using -ms will make short-lived applications, such as kjc, run faster. Garbage collection can be avoided if an application does not allocate more memory than the initial heap size during its lifetime. If there is no memory left in the heap when an allocation is attempted, Kaffe will invoke the garbage collector. The collector uses a heuristics to decide whether it should perform a collection or whether it should postpone it. Postponing a collection means that Kaffe asks the operating system for more memory, growing its heap. Every time it decides to postpone a collection, it will ask for the amount of memory specified by the heap increment (-as) cmdline switch, which defaults to 1MB. Of course, postponing gc is only an option if the current size of the heap is less than the maximum heap size specified. If the maximum heap size has already been reached, a collection will be performed. If the maximum heap size has not been reached, how does Kaffe decide whether to grow its heap or whether to garbage collect? Like many things in CS, it's a classical space-time trade-off. Consider the two extremes: First, suppose Kaffe always postponed collection until it obtained the maximum amount of memory from the system. This would mean that collections would occur less frequently, but it would also mean that most long-running applications will actually require the full amount of memory specified as the maximum heap size. This would mean to trade memory for speed. Trading memory for speed is not always desirable, for instance if the machine on which you're running has little memory, or if you can't afford to set the necessary amount of memory aside. In systems using virtual memory, specifying heap sizes that are too large may lead to the well-known thrashing effect. On the other hand, if Kaffe always collected if it ran out, it would collect more often, but it won't ever use much more memory than the amount of memory occupied by long-lived and fixed data. This would mean to trade speed for memory. Let's look at a hypothetical example: Suppose an application uses 16MB of long-lived data, and produces 160 MB of short-lived data. Suppose the initial heap size is 5MB and the maximum heap size is 64MB. The heap increment is also the default, 1MB. If we always collected, then this application won't ever take more than 17MB, but it will perform 160/(17-16) = 160 collections! On the other hand, if we used all the available memory, then the application would use 64MB, but only perform 160/(64-16) = 4 collections. [ You might say: but wait, the cost of each of the 160 collections will be lower than the cost of the 4 collections in the second case. This is not true, however. The costs of Kaffe's mark-and-sweep algorithm is the sum of the costs of marking the heap and sweeping it. The costs of sweeping is linear in the total number of objects freed --- which is the same no matter how frequently you collect. However, the costs of marking only depends on the amount of live data, which is roughly equivalent to the amount of long-lived data. Hence, this cost is the same in both cases, but since this cost must be paid per collection, fewer collections will be faster. ] So, what does Kaffe do to find the sweet spot between not collecting too often and not using too much memory? It looks at how much memory has been allocated since the last time a collection happened. If this amount of memory is less than 1/3 of the total amount of memory in use, then the collection is skipped. In our hypothetical example above, Kaffe would use 24MB (since it will grow to 24MB in 1MB increments.) Every time 8MB of short-lived data have been added to the long-lived data occupying 16MB, kaffe will collect and free 8MB. Hence, it will perform 160/(24-16) = 20 collections instead of 160 or 4. Of course, if you have 64MB to spare, running Kaffe with '-ms 64M' is always your option and will require only 4 collections. Why 1/3? It's just a number I pulled out of my hat. Asymptotically, the number means that Kaffe's heap will always have 33% free memory after a gc. Using the -verbosegc option will tell you how much it actually is. If you know of a better heuristics --- maybe one that takes other factors than the amount of memory allocated since the last collection into account, we'd certainly all like to know about it. Possible candidates for such factors are the time elapsed since the start of the program, the time it takes to mark the heap, the time it takes to sweep freed objects, the length of the finalizer list, and the phase of the moon. Note that the discussion and the number in this FAQ are somewhat hypothetical and do not take various overheads into account. In particular, they do not account for Kaffe's unfortunate tendency to keep more temporary garbage afloat than it probably should. However, we're still working on improving Kaffe's collector. Thanks to Jason Baker and Archie Cobbs for contributing to the discussion above. Any comments and suggestions for improvements are welcome. - Godmar Back <gback@cs.utah.edu> 1/5/99