Compaction planning

An illustrative embodiment of a computer-implemented process for compaction planning selects a source region from a set of regions to form a selected source region, initializes process data using information from the selected source region and responsive to a determination that a current destination is not NULL and not full, determines whether to atomically consume from a destination. Responsive to a determination to atomically consume from a destination, the computer-implemented process plans to evacuate into a consumed extent and updates the process data and responsive to a determination that the source region is empty, determines whether more work remains. Responsive to a determination that more work does not remain, the computer-implemented process generates a relocation table.

BACKGROUND

1. Technical Field

This disclosure relates generally to memory management in a data processing system and more specifically to compaction planning in a memory manager of the data processing system.

2. Description of the Related Art

A memory management system, which does not move objects, may be affected by memory fragmentation. One typical mechanism for resolving memory fragmentation is compaction.

Abuaiadh et al (Abuaiadh, Ossia, Petrank and Silbershtein, “An efficient parallel heap compaction algorithm”, Proceedings of the 19th annual ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, 2004) described, at the time, a state of the art compactor which is currently used in IBM® Java® Virtual Machines (IBM is a registered trademark of IBM in the United States, other countries or both; Java and all Java-based trademarks and logos are trademarks or registered trademarks of Oracle and/or its affiliates). The compactor uses a small amount of auxiliary storage, and claims to achieve “(almost) perfect compaction”. However, in practice, “perfection” of the compaction typically decreases as parallelism increases. Each compactor thread must lock an associated destination area while the compactor thread evacuates into the respective destination area. While the respective destination area is locked, the area is not eligible to be an evacuation destination for other compactor threads, and the other compactor threads by-pass locked destination area and select a next available destination. The compactor may, therefore, leave some fragmentation as destination areas may become incompletely consumed.

Kermany and Petrank (Kermany and Petrank, “The Compressor: Concurrent, Incremental, and Parallel Compaction”, PLDI'06, pp. 354-363, 2006) recently disclosed an advance in compactor design, which improves upon the compactor of Abuaiadh et al. The stop-the-world compactor of Kermany and Petrank divides compaction into two phases, which may be referred to as term “plan” and “move.” During a planning phase, a new location of each object (or group of objects) is determined and recorded in a concise manner in an offset table. Once planning is complete, the data in a mark vector and the offset table can be combined to determine a destination of any object. The determination capability allows the move phase to move objects to predetermined destinations and fix up associated references to other objects at the same time. Thus the move phase is the only phase of the compactor, which reads or writes the heap. Planning and external fix-up do not need to read or write heap memory. The collector of Kermany and Petrank also includes a concurrent and incremental aspect, which is not considered in the present disclosure.

The plan task in the compactor of Kermany and Petrank is single threaded. While this does result in optimal planning, the single thread is typically a performance bottleneck. Kermany and Petrank claim the plan task can be parallelized using “simple tricks”, but the tricks are not described nor do they describe the optimality of the resulting plan. Those skilled in the art of implementing parallel planning typically view parallelizing the planning stage as more than a simple trick involving non-obvious algorithms. For example, a simple solution mimics the algorithm used by Abuaiadh et al. However this results in suboptimal planning, with the problem becoming worse as parallelism increases.

In another prior example, a system designates each segregated area as the responsibility of a single thread and does not deal with cross-region compaction to provide ideal compaction. Further, the system is directed toward solving a problem of references between the segregated areas and how to track the areas thereby treating inter-region references different from references within the same region.

Another example system describes how to choose pages for compaction and relocate objects concurrently. The example system needs to perform reference fix-up operations. Optimizing object reference fix-up is typically an expensive part of a compaction operation in a garbage collected heap as is using thread locks.

Another prior example of a system deals primarily with how to determine and store information corresponding to pre-compaction location and size of a set of objects in a given extent of a heap (as well as how to avoid moving “dense prefixes” of objects).

In another example, a system relies on building a static dependency graph between blocks, which requires a pass to realize and build the dependency graph. Building the dependency graph typically causes a minimal set of concrete dependencies to be found (with few enough threads or a sufficiently shallow plan, it is possible for no thread to ever be blocked on another: thus, no dependencies are discovered). Secondly, the algorithm used in the example system requires single-threaded copying into a given destination block. Further, the algorithm typically relies on being able to slide objects to lower blocks in the address space, which creates unavoidable contention points in the dependency graph. There is therefore a need for a more effective compaction planning mechanism.

SUMMARY

According to one embodiment, a computer-implemented process for compaction planning selects a source region from a set of regions to form a selected source region, initializes process data using information from the selected source region and responsive to a determination that a current destination is not NULL and not full, determines whether to atomically consume from a destination. Responsive to a determination to atomically consume from a destination, the computer-implemented process plans to evacuate into a consumed extent and updates the process data and responsive to a determination that the source region is empty, determines whether more work remains. Responsive to a determination that more work does not remain, the computer- implemented process generates a relocation table.

According to another embodiment, a computer program product for compaction planning comprises a computer recordable-type media containing computer executable program code stored thereon. The computer executable program code comprises computer executable program code for selecting a source region from a set of regions to form a selected source region, computer executable program code for initializing process data using information from the selected source region, computer executable program code responsive to a determination that a current destination is not NULL and not full, for determining whether to atomically consume from destination, computer executable program code responsive to a determination to atomically consume from destination, for planning to evacuate into a consumed extent and updating the process data, computer executable program code responsive to a determination that the source region is empty, for determining whether more work remains and computer executable program code responsive to a determination that more work does not remain, for generating a relocation table.

According to another embodiment, an apparatus for compaction planning comprises a communications fabric, a memory connected to the communications fabric, wherein the memory contains computer executable program code, a communications unit connected to the communications fabric, an input/output unit connected to the communications fabric, a display connected to the communications fabric and a processor unit connected to the communications fabric. The processor unit executes the computer executable program code to direct the apparatus to select a source region from a set of regions to form a selected source region, initialize process data using information from the selected source region and responsive to a determination that a current destination is not NULL and not full, determines whether to atomically consume from a destination. The processor unit executes the computer executable program code to further direct the apparatus responsive to a determination to atomically consume from destination, to plan to evacuate into a consumed extent and updating the process data, and responsive to a determination that the source region is empty, to determine whether more work remains; and responsive to a determination that more work does not remain, generate a relocation table.

DETAILED DESCRIPTION

Although an illustrative implementation of one or more embodiments is provided below, the disclosed systems and/or methods may be implemented using any number of techniques. This disclosure should in no way be limited to the illustrative implementations, drawings, and techniques illustrated below, including the exemplary designs and implementations illustrated and described herein, but may be modified within the scope of the appended claims along with their full scope of equivalents.

A computer-readable signal medium may include a propagated data signal with the computer-readable program code embodied therein, for example, either in baseband or as part of a carrier wave. Such a propagated signal may take a variety of forms, including but not limited to electro-magnetic, optical or any suitable combination thereof. A computer readable signal medium may be any computer readable medium that is not a computer readable storage medium and that can communicate, propagate, or transport a program for use by or in connection with an instruction execution system, apparatus, or device.

Program code embodied on a computer-readable medium may be transmitted using any appropriate medium, including but not limited to wireless, wire line, optical fiber cable, RF, etc. or any suitable combination of the foregoing.

Turning now toFIG. 1a block diagram of an exemplary data processing system operable for various embodiments of the disclosure is presented. In this illustrative example, data processing system100includes communications fabric102, which provides communications between processor unit104, memory106, persistent storage108, communications unit110, input/output (I/O) unit112, and display114.

Memory106and persistent storage108are examples of storage devices116. A storage device is any piece of hardware that is capable of storing information, such as, for example without limitation, data, program code in functional form, and/or other suitable information either on a temporary basis and/or a permanent basis. Memory106, in these examples, may be, for example, a random access memory or any other suitable volatile or non-volatile storage device. Persistent storage108may take various forms depending on the particular implementation. For example, persistent storage108may contain one or more components or devices. For example, persistent storage108may be a hard drive, a flash memory, a rewritable optical disk, a rewritable magnetic tape, or some combination of the above. The media used by persistent storage108also may be removable. For example, a removable hard drive may be used for persistent storage108.

Communications unit110, in these examples, provides for communications with other data processing systems or devices. In these examples, communications unit110is a network interface card. Communications unit110may provide communications through the use of either or both physical and wireless communications links.

Input/output unit112allows for input and output of data with other devices that may be connected to data processing system100. For example, input/output unit112may provide a connection for user input through a keyboard, a mouse, and/or some other suitable input device. Further, input/output unit112may send output to a printer. Display114provides a mechanism to display information to a user.

Instructions for the operating system, applications and/or programs may be located in storage devices116, which are in communication with processor unit104through communications fabric102. In these illustrative examples the instructions are in a functional form on persistent storage108. These instructions may be loaded into memory106for execution by processor unit104. The processes of the different embodiments may be performed by processor unit104using computer-implemented instructions, which may be located in a memory, such as memory106.

These instructions are referred to as program code, computer usable program code, or computer readable program code that may be read and executed by a processor in processor unit104. The program code in the different embodiments may be embodied on different physical or tangible computer readable media, such as memory106or persistent storage108.

Program code118is located in a functional form on computer readable media120that is selectively removable and may be loaded onto or transferred to data processing system100for execution by processor unit104. Program code118and computer readable media120form computer program product122in these examples. In one example, computer readable media120may be in a tangible form, such as, for example, an optical or magnetic disc that is inserted or placed into a drive or other device that is part of persistent storage108for transfer onto a storage device, such as a hard drive that is part of persistent storage108. In a tangible form, computer readable media120also may take the form of a persistent storage, such as a hard drive, a thumb drive, or a flash memory that is connected to data processing system100. The tangible form of computer readable media120is also referred to as computer recordable storage media. In some instances, computer readable media120may not be removable.

Alternatively, program code118may be transferred to data processing system100from computer readable media120through a communications link to communications unit110and/or through a connection to input/output unit112. The communications link and/or the connection may be physical or wireless in the illustrative examples. The computer readable media also may take the form of non-tangible media, such as communications links or wireless transmissions containing the program code.

In some illustrative embodiments, program code118may be downloaded over a network to persistent storage108from another device or data processing system for use within data processing system100. For instance, program code stored in a computer readable storage medium in a server data processing system may be downloaded over a network from the server to data processing system100. The data processing system providing program code118may be a server computer, a client computer, or some other device capable of storing and transmitting program code118.

As another example, a storage device in data processing system100may be any hardware apparatus that may store data. Memory106, persistent storage108and computer readable media120are examples of storage devices in a tangible form.

According to an illustrative embodiment, a computer-implemented process for compaction planning selects a source region from a set of regions to form a selected source region, initializes process data using information from the selected source region and responsive to a determination that a current destination is not NULL and not full, determines whether to atomically consume from a destination. Responsive to a determination to atomically consume from a destination, the computer-implemented process plans to evacuate into a consumed extent and updates the process data and responsive to a determination that the source region is empty, determines whether more work remains. Responsive to a determination that more work does not remain, the computer-implemented process generates a relocation table.

Using data processing system100ofFIG. 1as an example, an illustrative embodiment provides the computer-implemented process stored in memory106, executed by processor unit104, for compaction planning. Processor unit104selects a source region from a set of regions to form a selected source region. The set of regions may be obtained from communications unit110, storage devices116or input/output unit112. Processor unit104initializes process data using information from the selected source region and responsive to a determination that a current destination is not NULL and not full, determines whether to atomically consume from a destination. Responsive to a determination by processor unit104to atomically consume from a destination, processor unit104plans to evacuate into a consumed extent and updates the process data contained in memory106. Responsive to a determination that the source region is empty, processor unit104determines whether more work remains. Responsive to a determination that more work does not remain, processor unit104generates a relocation table.

In an alternative embodiment, program code118containing the computer-implemented process may be stored within computer readable media120as computer program product122. In another illustrative embodiment, the process for compaction planning may be implemented in an apparatus comprising a communications fabric, a memory connected to the communications fabric, wherein the memory contains computer executable program code, a communications unit connected to the communications fabric, an input/output unit connected to the communications fabric, a display connected to the communications fabric, and a processor unit connected to the communications fabric. The processor unit of the apparatus executes the computer executable program code to direct the apparatus to perform the process.

With reference toFIG. 2, a block diagram of a compaction planning system, in accordance with various embodiments of the disclosure is presented. Compaction planning system200is an example of an embodiment of the disclosed compaction planning process.

An embodiment of compaction planning system200is supported by a data processing system, for example, data processing system100ofFIG. 1. Compaction planning system200comprises an number of components working in combination with the components of the data processing including mark vector202, set of source regions204, current destination206, evacuate pointer208, occupied space210, and available space212.

Mark vector202is a data structure containing an entry for each live object within a memory space that is to be processed. Mark vector202provides information for a live object including a size that is used in further space calculations.

Set of source regions204is a data structure containing areas of the memory to be processed. The defined separate memory areas can be processed separately and concurrently using the disclosed process. The disclosed process operates on each source region of the set of source regions in parallel. The computational resources available determine the degree of parallelism but the operational granularity is limited to a single region. Although a number of threads may be executing to compact a number of source regions a source region is not locked during processing because the source region is viewed as a local resource to an executing thread.

Current destination206is a data structure containing an atomically modified pointer to a region currently used as a compact destination for all threads. Current destination206is a global data item visible to all threads. The value of current destination206is NULL when a destination has not yet been selected or when a previous destination was filled and another destination has not yet been selected.

Per region data comprises a set of data items including evacuate pointer208, occupied space210, and available space212. Each set of data items is associated with a specific region of set of source regions204. Evacuate pointer208is a data structure containing a pointer to the first object to be copied from a region. Initially evacuate pointer208points to the first object in the region. Occupied space210is a data structure containing a value of the number of bytes that must be copied from a source region. The value represents the size of objects that will be planned to move. Available space212is a data structure containing a value of the number of bytes that remain for a copy destination in a region.

With reference toFIG. 3, a block diagram of regions, in accordance with one embodiment of the disclosure is presented. Regions300is an example of a set of source regions204of compaction planning system200ofFIG. 2.

In one example, region302contains a number of elements of used space and free space. Free space308indicates areas within region302that are available for storage use. Used space310represents areas of region302that are presently used for storage and have been occupied by data and are no longer available. Compaction attempts to consolidate used space310within region302typically causing free space308to be redistributed and consolidated but not reduced. In the example, total used space, n bytes occupied, may be determined by a sum of the entries for used space310(represented as a+b+c).

The compaction planning system of the disclosure records information about the size of all live objects in the mark vector as a first phase of planning for each region, such as region302. The total live object size of the region is recorded as the total number of bytes that all of the objects in this region will occupy once compacted.

In the example of region304the region has used space310and a number of available bytes. The number of bytes available is represented as m bytes available, comprising the sum of object space312and free space308. The m bytes available represent space available as a copy destination for object relocation.

In the example of region306, the region has used space308, object space312and a failed space314. As before m bytes available represent space available as a copy destination for object relocation. However in this example m bytes was consumed by object space312. Failed space314represents n−m bytes remaining, typically a space into which no object can be copied and therefore another region must be used as a destination.

With reference toFIG. 4, a block diagram of cross-region compaction, in accordance with one embodiment of the disclosure is presented. Regions400and regions402are examples of a set of source regions204of compaction planning system200ofFIG. 2.

Regions400depicts an example of object movements in a set of regions comprising region404, region406and region408during a first step of a compaction process. An attempted move to relocate object410and object412from region406to space in region404occurs in the first step. Movement of object410is successful however movement of object412failed. The status of a compaction of elements of region406into region404is noted as evacuate partial success. An element was relocated while another element was not. Region404has a portion of space remaining unused. Region408contains object414and object416awaiting a next thread for processing.

Regions402continues the example of regions400. In the example of regions402, region404is full for the remainder of the process of the example. Region404is full as a result of previous use to contain objects and the relocation of object410.

Having evacuated object410from region406, space is available to slide object412forward to the base of region406in a retry operation. Object414and object416can be relocated into region406from region408as indicated by arrows from region408to region406.

Embodiments of the disclosed process enable a compaction phase to be planned in parallel without waits. The compaction plan resulting from using embodiments of the disclosed process is near optimal. Limited fragmentation can exist at the end of a compaction area when using embodiments of the disclosed process, but the fragmentation can typically be bounded to arbitrarily small values.

The disclosed process is designed for a region-based garbage collector (see, for example, Detlefs et al Detlefs, D., Flood, C., Heller, S., Printezis, T., “Garbage-First Garbage Collection”, ISMM'04, pp. 37-48, 2004). Rather than attempting to move all objects to the lowest area of a large, unified heap, embodiments of the disclosed process divide the heap into a number of regions, for example, region404, region406and region408and only attempts to achieve optimal compaction within defined regions, as seen in the process example using regions400and regions402. Embodiments of the disclosed process can be easily modified to operate on a unified heap by virtualizing region semantics.

Embodiments of the disclosed process collect the size of all the objects in a region prior to planning the movement destinations of the objects in a region to be compacted. Embodiments of the disclosed process thus enable determination of the amount of memory that will be consumed by combining any set of regions whereby selecting a region as the destination of another region requires only one atomic operation to consume from the free memory counter of the destination. The work of planning the precise destinations of all objects in the source region can then proceed, in parallel, without locking the destination. The absence of locking enables other regions to use the same region as a destination without compromising parallelism. Embodiments of the disclosed process also enable regions to be grouped together into “compact groups” ensuring certain properties of regions are preserved. For example, regions may be grouped together by age, by allocating thread, or by NUMA affinity as an optional feature.

With reference toFIG. 5, a block diagram of cross-region compaction, in accordance with one embodiment of the disclosure is presented. Regions500and regions512are examples of a set of source regions204of compaction planning system200ofFIG. 2.

Regions500represent an initial view of object placement before a compaction planning process involving object relocation occurs. Regions500is a set of regions comprising region502, region504, region506and region508in which a combination of free space and used space may be found forming mixed space514. Destination pointer510is directed toward region502indicating region502is a destination for object relocation as a result of compaction processing for region502as well as remaining region504, region506and region508.

Planning occurs for objects currently located in mixed space514of region502, region504, region506and region508for relocation to proposed locations516. Movement of the objects occurs after the planning phase. An arrow associated with each source region of region502, region504, region506and region508indicates a respective object movement to a corresponding planned position within a destination region of region502.

Regions512represent a view of object placement after a compaction planning process involving object relocation occurs. Regions512is a set of regions comprising region502, region504, region506and region508however mixed space514in has been replaced by free space516in region504, region506and region508. Destination pointer510indicates region502as a destination for object relocation during compaction processing for region502as well as the remaining regions region504, region506and region508as before.

The planning for objects previously located in mixed space514of region502, region504, region506and region508for new locations in proposed locations516enables the relocation portion of compaction to occur. Evacuated objects520represents the result of movement of objects from previous positions in respective locations of region502, region504, region506and region508into the destination region of region502.

The example indicates a capability for multiple regions comprising region502, region504, region506and region508to participate in the compaction operation sharing destination region of region502. In the example region502is a destination for compaction of objects within region502as well as hosting a destination for compaction relocation of objects from other regions including region504, region506and region508.

With reference toFIG. 6, a flowchart of a compaction planning process, in accordance with one embodiment of the disclosure is presented. Process600is an example of a process using compaction-planning system200ofFIG. 2. Process600begins (step602) and selects a source region from a set of regions to form a selected source region (step604). Process600receives and records information about the size of all live objects in a mark vector as a first phase of planning for each source region. The total live object size of the region is recorded as the total number of bytes that all of the objects in the selected region will occupy once compacted. Process600accordingly initializes process data using information from the selected source region (step606). The initialization comprises receiving a count of occupied bytes, sets available space, and sets an evacuation candidate using the selected source region.

Once the occupied size is set, process600determines whether a current destination exists (not NULL) and is not full (step608). When a determination is made that a current destination exists and is not full process600attempts to atomically subtract the occupied size from the available space of the destination region (this atomic is a “saturating subtract” so that the available space is never negative). In doing so, process600determines whether it is capable to atomically consume from destination (step610).

When process600determines it is not capable to atomically consume from destination, process600loops back to perform step608as before. When process600determines it is capable to atomically consume from destination, the thread of process600now “owns” the available space, which was decremented and can use the space as a copy destination (since the base of the region and total region size are known, the old and new available space describe a unique extent of memory). Since the decrement was atomic, there is no locking required to reserve this memory and there is no possibility of another thread consuming an overlapping extent since that would have caused the atomic to fail. When the available space of a destination is reduced to zero with the atomic, the destination is considered “full.”

Since consuming from the destination succeeds (a failure restarts from the top), process600plans to evacuate in a consumed extent, updates the process data (step614). The process data being updated comprises information containing evacuation candidate, occupied bytes and available space information. Process600begins calculating per-object destinations of all objects in the selected source region (starting at “evacuate pointer”) in the memory extent consumed from the destination region. When all of the objects cannot fit (due to the occupied size of the source being greater than the available space of the destination—see previous point regarding the “saturating subtract”), the occupied size is decremented by a number of bytes for which a move was planned, the evacuate pointer is updated to point to the first object which could not be copied, and process600retries to find a destination with a reduced occupied size.

Process600determines whether the source region is empty (step616). When a determination is made that the source region is not empty, process600loops back to perform step608as before. When a determination is made that the source region is empty, process600skips ahead to step620.

When a determination is made that the current destination region is NULL or already full in step608, process600sets available space of the selected source region to be the total region size minus occupied bytes, atomically installs the selected source region as the current destination and determines whether atomically set source as destination (step612). When a determination is made that atomically set source as destination did not succeed, process600loops back to perform step608as before. When a determination is made that atomically set source as destination succeeded, process600begins planning the destinations of each object in its region, given that process600consumed the “first required bytes” of the region, process600“owns” the beginning of the region and uses that as a destination to plan to slide to the base of the region (step618). Thread contention can cause the installation of this region as the destination to fail but that case is handled by attempting to consume from this new destination as though the destination had never been observed as NULL. When the available space of a region has been decremented by an amount of the remaining memory in the region, the internal compaction (within the region) and the compaction of other regions into this region can be freely planned in parallel because installing the region as the current destination is the point where the region becomes exposed to other threads (of other process600processes) these counters need to be updated first.

Process600determines whether more work remains (step620). When a determination is made that more work remains process600loops back to perform step604as before. When a determination is made that more work does not remain process600generates a relocation table (step622) and terminates thereafter (step624). The relocation table is a data structure providing precise destinations of all objects in the selected source region.

Typical existing systems for object movement do not scale well across many logical processors because each thread executing the compaction planning process must acquire an exclusive lock on both of the source and destination areas of memory while relocating (or at least planning) the objects within. Further, the systems typically use the locking mechanism to determine when to evacuate one area into another area rather than to determine when to slide objects within an area. As thread contention increases, the determination tends to increase the number of areas compacted using sliding (since only one lock could be acquired) which typically results in a given contiguous free memory extent less likely to be larger than the size of a compaction area. The less aggressive compaction result tends to negate the purpose of a compaction.

In contrast, embodiments of the compaction planning process just described only require locking a source area (the lock is “implied” in that a single source region is the granule of parallelism of the thread). Using embodiments of the compaction planning process reduces contention, enabling a worst-case number of work units, which can be executed in parallel for n memory areas to double from n/2to n. Furthermore, consuming memory from a destination area requires only an atomic operation which enables an immediate decision regarding which objects will be evacuated from an area compared with which objects will slide within the area (this atomic makes the decision and then the actual planning can be done without locking the destination). The absence of locking means aggressiveness of compaction work is no longer dependent upon thread contention and is now purely an artifact of the geometry of objects within the compacted areas. Large objects mixed with smaller objects can sometimes still result in waste at the end of destination regions but this possibility does not change, no matter how many threads are executing the compaction planning process.

The compaction planning process typically produces a “near-optimal” compaction since there are still a few opportunities (depending on object representation implementation) for wasted memory. In one example, an amount of memory is wasted at the very end of a destination region, which is less than the total size of the largest object in the source region. While typical workloads result in the amount being an insignificantly small amount of memory (usually less than 1% of the total region size), a workload with several large objects dispersed throughout the heap could allow the waste to become appreciably large. In another example, in object representations where instances can change size when moving, the compaction planning process must pessimistically choose the larger of the sizes. However, given that most applications of object resizing typically only involve growth on a move and the compaction planning process will move almost all the objects provided (only the first few objects of the first region to be made a destination will tend to not move), the pessimistic sizing is almost always the correct one. A small amount of space could be wasted at the end of the extent consumed in the destination when the pessimistic sizing is not correct, however.

The compaction planning process assumes that the heap is broken into “regions” of objects, which can be used as logical units of compact work. The compaction planning process could be modified to operate on a unified heap by virtualizing region semantics. This would likely involve a single-threaded pre-pass to build a virtual region table subject to constraints. For example, regions can never start in the middle of an object (ideally regions start at the beginning of an object but this is not required). In another example, an object inside a region cannot extend beyond the end of a region (always starting a region at the beginning of an object trivially ensures that this requirement holds). In another example, region size determination has trade-offs including where larger regions result in lower worst-case fragmentation and less contention on the destination region but also less parallel work so an increase in idleness and a reduction in scalability.

Thus in one illustrative embodiment, a computer-implemented process for compaction planning selects a source region from a set of regions to form a selected source region, initializes process data using information from the selected source region and responsive to a determination that a current destination is not NULL and not full, determines whether to atomically consume from a destination. Responsive to a determination to atomically consume from a destination, the computer-implemented process plans to evacuate into a consumed extent and updates the process data and responsive to a determination that the source region is empty, determines whether more work remains. Responsive to a determination that more work does not remain, the computer-implemented process generates a relocation table.