Additionally, I report the results of experimental studies measuring the effectiveness of each of my improvements. I also report the results of an experiment suggesting that priority-based coloring requires 0(n2) time and that the Yorktown allocator requires only 0(n log n) time. Finally, I include a chapter describing many implementation details and including further measurements designed to provide an accurate intuition about the time and space requirements of coloring allocators."

A booklet for a winter solstice tasting of dry white sparkling wines on December 21, 2010. Includes famous quotes, the wine selection, and blank tasting notes.

Abstract: "We describe two improvements to Chaitin-style graph coloring register allocators. The first, optimistic coloring, uses a stronger heuristic to find a k-coloring for the interference graph. The second extends Chaitin's treatment of rematerialization to handle a larger class of values. These techniques are complimentary. Optimistic coloring increases the number of procedures that color without spilling and lowers total spill costs when spilling is unavoidable. Rematerialization lowers the cost of spilling some values. This paper describes both the techniques themselves and our experience building and using register allocators that incorporate them. It provides a detailed description of optimistic coloring and rematerialization. It presents experimental data to show the performance of several versions of the register allocator on a suite of FORTRAN programs. It discusses several insights that we discovered only after repeated implementation of these allocators."