公开(公告)号：US07660961B2

公开(公告)日：2010-02-09

申请号：US11732785

申请日：2007-04-03

申请人： Antonios Printezis ,  Alexander T. Garthwaite

发明人： Antonios Printezis ,  Alexander T. Garthwaite

IPC分类号： G06F12/00

CPC分类号： G06F12/0276

摘要： The invention relates to a method for performing generational garbage collection on a heap comprising a plurality of generations. The method involves dividing a young generation of the heap into a first young generation and a second young generation, evacuating the first young generation concurrently with allocating the second young generation, and evacuating the second young generation concurrently with allocating the first young generation and subsequent to fully evacuating the first young generation.

摘要翻译： 本发明涉及一种在包含多代的堆上执行代数垃圾收集的方法。 这种方法包括将年轻一代的小朋友分成第一个年轻一代和第二个年轻一代，同时分配第一个年轻一代，分配第二个年轻一代，同时分配第二个年轻一代，分配第一个年轻一代， 完全疏散第一代青年。

公开(公告)号：US07539713B2

公开(公告)日：2009-05-26

申请号：US10287930

申请日：2002-11-05

申请人： Alexander T. Garthwaite

发明人： Alexander T. Garthwaite

IPC分类号： G06F12/00 ,  G06F17/30

CPC分类号： G06F12/0276 ,  Y10S707/99953 ,  Y10S707/99957

摘要： A garbage collector for reclaiming computer-memory space occupied by unreachable data objects operates incrementally in accordance with the train algorithm. Although most objects share car sections with other objects, objects found to be referred to by a large number of references are placed in their own individual car sections so that the “popular” object's train membership can be changed without relocating the object and thus requiring the numerous references to it to be updated. The collector keeps track of different object classes to have instances that are popular. If a class exhibits a strong tendency to have popular instances, the collector initially places instances of that class into respective single-object cars even if those objects have not yet been identified as popular.

摘要翻译： 用于回收由不可达数据对象占用的计算机存储器空间的垃圾收集器根据列车算法递增地进行操作。 虽然大多数对象与其他对象共享汽车部分，但是由大量参考文献发现的对象被放置在其各自的车辆部分中，使得可以改变“流行”对象的列车成员资格而不重新定位对象，因此需要 许多参考它被更新。 收集器跟踪不同的对象类以具有受欢迎的实例。 如果一个班级表现出很受欢迎的实例倾向，那么收藏家最初会把这个类别的实例放在相应的单一物体汽车中，即使这些物体尚未被识别为受欢迎的。

公开(公告)号：US07389395B1

公开(公告)日：2008-06-17

申请号：US11169983

申请日：2005-06-26

申请人： Alexander T. Garthwaite ,  David P. Stoutamire ,  Peter B. Kessler ,  Y Srinivas Ramakrisha ,  David L. Detlefs ,  Antonios Printezis ,  Jon A. Masamitsu ,  John W. Coomes

发明人： Alexander T. Garthwaite ,  David P. Stoutamire ,  Peter B. Kessler ,  Y Srinivas Ramakrisha ,  David L. Detlefs ,  Antonios Printezis ,  Jon A. Masamitsu ,  John W. Coomes

IPC分类号： G06F12/00

CPC分类号： G06F12/0269 ,  G06F12/0253 ,  Y10S707/99953 ,  Y10S707/99957

摘要： A heap may be marked and compacted while performing only two passes over the objects and object references in the heap. Specifically, objects and object references are traversed once during a marking phase and again during a compaction phase of split-reference, two-pass mark-compaction. Object references are updated in two steps. First, during marking, each object reference may be updated to include the relative offset within its block of the referenced object and-during compaction that offset may be added to the block's destination address resulting in a reference that points to the actual post-compaction location for the referenced object. Objects of a particular block may be rearranged, or permuted, with respect to each other within the block. However, the order between groups of objects in different blocks may be preserved across compaction.

摘要翻译： 堆可以被标记和压缩，同时仅在堆中的对象和对象引用执行两次传递。 具体来说，在标记阶段期间遍历一次对象和对象引用，并在分割参考，二次标记压缩的压缩阶段再次遍历对象和对象引用。 对象引用有两个步骤更新。 首先，在标记期间，可以更新每个对象引用以包括其引用对象的块内的相对偏移量，并且 - 在压缩期间，该偏移可以被添加到块的目的地地址，导致指向实际的后压缩位置的引用 为引用的对象。 特定块的对象可以在块内相对于彼此重新布置或排列。 但是，不同块中的对象组之间的顺序可以在压缩之间保留。

公开(公告)号：US20070294499A1

公开(公告)日：2007-12-20

申请号：US11452533

申请日：2006-06-14

申请人： Alexander T. Garthwaite

发明人： Alexander T. Garthwaite

IPC分类号： G06F12/00

CPC分类号： G06F12/0253 ,  Y10S707/99953 ,  Y10S707/99957

摘要： Reference updating in a sliding compaction garbage collector may involve maintaining, for each logical region of the heap to be compacted, values that represent the range of addresses referenced by individual regions of the heap. For example, a highest-referenced address (HRA) represents the maximum address referenced by any object references in the respective region. Similarly, a lowest-reference address (LRA) represents the minimum address referenced by a region. When updating references during compaction, if the HRA and/or LRA for a particular region indicate that all references within the region point to addresses within a region of memory that will not be relocated during compaction, such as a dense prefix, the references with the particular region need not be updated. Maintaining HRAs and/or LRAs for region of heap memory may simplify determining whether or not references within individual regions require updating.

摘要翻译： 滑动式压缩垃圾回收器中的参考更新可能涉及为堆的每个逻辑区域维护代表堆的各个区域引用的地址范围的值。 例如，最高参考地址（HRA）表示相应区域中任何对象引用引用的最大地址。 类似地，最低参考地址（LRA）表示由一个区域引用的最小地址。 在压缩期间更新引用时，如果特定区域的HRA和/或LRA指示区域内的所有引用指向在压缩期间将不会重定位的内存区域内的地址（例如密集前缀），则引用具有 特定区域不需要更新。 维护堆存储区域的HRAs和/或LRA可以简化确定各个区域内的引用是否需要更新。

公开(公告)号：US07089272B1

公开(公告)日：2006-08-08

申请号：US10464371

申请日：2003-06-18

申请人： Alexander T. Garthwaite ,  David L. Detlefs

发明人： Alexander T. Garthwaite ,  David L. Detlefs

IPC分类号： G06F17/30

CPC分类号： G06F12/0276 ,  Y10S707/99944 ,  Y10S707/99957

摘要： A technique is provided for reducing the number of write barriers executed in mutator code without compromising garbage collector performance. Advantageously, a compiler generates two forms of a mutator code—a first version with write barriers and a second version substantially without write barriers. In operation, the first version of the code may be accessed by a vtable in a “mature” near-class and the second version may be accessed by a vtable in a “nascent” near-class. According to the invention, mapping of functionally equivalent points in the first and second versions of the mutator code may be facilitated by an associated pcmap. Further, each of the first and second versions may also be associated with a respective nr_map that facilitates mapping functionally equivalent points within different branches of guard code sequences corresponding to reference-writes to non-receiver objects.

摘要翻译： 提供了一种技术，用于减少在mutator代码中执行的写入障碍的数量，而不会影响垃圾收集器的性能。 有利地，编译器生成两种形式的变异器代码 - 具有写入障碍的第一版本和基本上没有写入障碍的第二版本。 在操作中，代码的第一个版本可能被“成熟”近级的vtable访问，第二个版本可能被“新生”的近级中的vtable访问。 根据本发明，可以通过相关联的pcmap来促进变换器代码的第一和第二版本中的功能等效点的映射。 此外，第一和第二版本中的每一个也可以与相应的nr_map相关联，这些nr_map有助于将对应于对非接收器对象的引用写入的保护码序列的不同分支内的功能等效点进行映射。

公开(公告)号：US07062518B2

公开(公告)日：2006-06-13

申请号：US10287852

申请日：2002-11-05

申请人： Alexander T. Garthwaite

发明人： Alexander T. Garthwaite

IPC分类号： G06F17/30

CPC分类号： G06F12/0276 ,  Y10S707/99957

摘要： A garbage collector that divides a dynamically allocated heap into car sections grouped into trains in accordance with the train algorithm subdivides large trains into subtrains. When an object that is reachable from the train-algorithm-managed generation of the heap is evacuated from a car being collected during a collection increment, it is placed into the last car in the subtrain in which the reference to it resides, even if that car is not the last car in the train to which the reference's subtrain belongs. The train-algorithm test for dead trains is performed not only on top-level trains but also on sub-trains.

摘要翻译： 将动态分配的堆分为根据列车算法分组到列车的汽车部分的垃圾收集器将大列车分为子列车。 当从堆积的火车算法管理的一代可达到的物体在收集增量期间从被收集的汽车中撤出时，它被放置在其所引用的子列车中的最后一个车厢中，即使是 汽车不是参考的子列车所属列车的最后一辆车。 无人火​​车的列车算法测试不仅在顶级列车上，而且在次列车上进行。

公开(公告)号：US07031990B2

公开(公告)日：2006-04-18

申请号：US10313254

申请日：2002-12-06

申请人： Alexander T. Garthwaite

发明人： Alexander T. Garthwaite

IPC分类号： G06F17/30

CPC分类号： G06F12/0276 ,  Y10S707/99957

摘要： A garbage collector collects at least a generation of a dynamically allocated heap in increments. In each increment, it identifies references located outside a collection set that refer to objects that belong to the collection set, and it evacuates the objects thus referred to before it reclaims the memory space that the collection set occupies. In some collection increments, references to collection-set objects are located both inside and outside the generation. The collector locates all such references, both those inside the generation and those outside it, before it evacuates any objects in response to any of them. By doing so, it is able to reduce the cost of locating references and evacuating objects.

摘要翻译： 垃圾收集器以增量收集至少一代动态分配的堆。 在每个增量中，它标识位于集合集外部的引用属于集合集合的对象的引用，并且在引用收集集所占据的存储空间之前，撤销所引用的对象。 在一些集合增量中，对集合对象的引用位于生成的内部和外部。 收集者在撤回任何对象以回应任何对象之前，将所有这些引用定位在一代和外部的引用之外。 通过这样做，能够降低定位参考和撤离对象的成本。

公开(公告)号：US07017160B2

公开(公告)日：2006-03-21

申请号：US09837669

申请日：2001-04-18

申请人： Paul A. Martin ,  David L. Detlefs ,  Alexander T. Garthwaite ,  Guy L. Steele, Jr. ,  Mark S. Moir

发明人： Paul A. Martin ,  David L. Detlefs ,  Alexander T. Garthwaite ,  Guy L. Steele, Jr. ,  Mark S. Moir

IPC分类号： G06F9/44 ,  G06F9/54

CPC分类号： G06F7/785 ,  G06F9/30032 ,  G06F9/526 ,  G06F9/544 ,  G06F2205/064 ,  G06F2209/521

摘要： The Hat Trick deque requires only a single DCAS for most pushes and pops. The left and right ends do not interfere with each other until there is one or fewer items in the queue, and then a DCAS adjudicates between competing pops. By choosing a granularity greater than a single node, the user can amortize the costs of adding additional storage over multiple push (and pop) operations that employ the added storage. A suitable removal strategy can provide similar amortization advantages. The technique of leaving spare nodes linked in the structure allows an indefinite number of pushes and pops at a given deque end to proceed without the need to invoke memory allocation or reclamation so long as the difference between the number of pushes and the number of pops remains within given bounds. Both garbage collection dependent and explicit reclamation implementations are described.

摘要翻译： 帽子技巧deque只需要一个单一的DCAS大多数按钮和弹出。 在队列中有一个或多个项目之前，左右两端不会相互干扰，然后DCAS在竞争弹出之间进行裁决。 通过选择大于单个节点的粒度，用户可以通过使用添加的存储的多个推送（和弹出）操作来分摊添加附加存储的成本。 合适的清除策略可以提供类似的摊销优势。 在结构中链接的备用节点的技术允许在给定的deque端的无限数量的推送和弹出进行，而不需要调用内存分配或回收，只要推送次数和流量数之间的差异保持不变 在给定范围内。 描述垃圾收集相关和显式回收实现。

公开(公告)号：US06839725B2

公开(公告)日：2005-01-04

申请号：US09855453

申请日：2001-05-15

申请人： Ole Agesen ,  Alexander T. Garthwaite ,  Timothy L. Harris

发明人： Ole Agesen ,  Alexander T. Garthwaite ,  Timothy L. Harris

IPC分类号： G06F12/02 ,  G06F12/00

CPC分类号： G06F12/0276 ,  Y10S707/99957

摘要： Run time sampling techniques have been developed whereby representative object lifetime statistics may be obtained and employed to adaptively affect tenuring decisions, memory object promotion and/or storage location selection. In some realizations, object allocation functionality is dynamically varied to achieve desired behavior on an object category-by-category basis. In some realizations, phase behavior affects sampled lifetimes e.g., for objects allocated at different phases of program execution, and the dynamic facilities described herein provide phase-specific adaptation tenuring decisions, memory object promotion and/or storage location selection. In some realizations, reversal of such decisions is provided.

公开(公告)号：US06799191B2

公开(公告)日：2004-09-28

申请号：US09855454

申请日：2001-05-15

申请人： Ole Agesen ,  Alexander T. Garthwaite ,  Timothy L. Harris

发明人： Ole Agesen ,  Alexander T. Garthwaite ,  Timothy L. Harris

IPC分类号： G06F1200

CPC分类号： G06F12/0276 ,  G06F11/3447 ,  G06F11/3466 ,  Y10S707/99957

摘要： With better knowledge of the behavior of objects in a running application, it is possible to improve execution environment decisions that affect management of such objects. For example, if available, object lifetime statistics could be employed in decisions that affect how and where objects are placed, e.g., on allocation or during operation of automatic dynamic memory management facilities such as a garbage collector. Typically, instrumenting all objects to sample lifetimes or other characteristics would impose an impractical level of overhead. We present a technique for dynamic sampling of a subset of allocated objects that incurs low runtime overheads. Coupled with automatic memory management or collection facilities, this technique allows us to improve the efficiency of a collector by segregating objects, sampled and non-sampled alike, based on observed characteristics such as object lifetime. The sampling techniques facilitate tracking of many kinds of object information. For purposes of illustration, an exemplary implementation is described in which such sampling techniques are exploited to improve performance of generational garbage collectors.

摘要翻译： 通过更好地了解正在运行的应用程序中对象的行为，可以改进影响这些对象管理的执行环境决策。 例如，如果可用，则可以在影响如何以及在何处放置对象的决策中使用对象生命周期统计，例如在诸如垃圾收集器的自动动态存储器管理设备的分配或操作期间。 通常，将所有对象检测到样本生命周期或其他特征将会产生不切实际的开销级别。 我们提出了一种用于动态采样分配对象的子集的技术，从而导致低运行时开销。 结合自动记忆管理或收集设备，这种技术使我们能够根据诸如对象寿命等观察特征，通过分离对象，采样和非抽样等来提高收集器的效率。 采样技术有助于跟踪多种物体信息。 为了说明的目的，描述了一种示例性实现，其中利用这种采样技术来改善代代垃圾收集器的性能。