Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2000-07-19
2003-07-15
Shah, Sanjiv (Department: 2172)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000
Reexamination Certificate
active
06594678
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates generally to computer software. More particularly, the present invention relates to improving the placement of data in memory to increase the speed with which the data may be accessed.
2. Discussion of Related Art
Cache memory is often used in conjunction with a main memory to provide an increased memory speed. Typically, portions of data are copied from the main memory so that the cache contains a copy of these portions of main memory. When the CPU attempts to read a word, a check is made to determine if the word is in the cache. If the word is in the cache, the word is read from the cache. Otherwise, a number of words are read from the main memory to be stored in the cache and the word is provided to the CPU.
When a word is not in the cache, it must be read from main memory, which increases memory access time. In order to increase the probability that requested data is present in the cache, caches typically use heuristics to guess which data will be accessed and copy this data into the cache. Thus, computer memory systems often rely on caches to keep the most frequently accessed items close to processors.
Since multiple words are simultaneously stored in the cache, the placement of data in memory can affect the efficiency of caches, thereby affecting the overall speed at which a computer system operates. It is therefore important to efficiently lay out data (e.g., objects) in memory to maximize speed. Previously proposed techniques have large overheads or cannot be used in a dynamic environment such as that executing Java bytecodes.
In order to eliminate objects that are no longer referenced from memory, garbage collection is often performed. Two commonly used methods of performing garbage collection are the “mark and sweep” method and the “copying garbage collection” method. As will be described in further detail below, the relocation of data in memory may be performed to some degree during the garbage collection process.
FIG. 1A
is an exemplary block diagram illustrating the placement of objects in memory during a conventional mark and sweep garbage collection process. As shown in
FIG. 1A
, objects
102
,
104
,
106
, and
108
are illustrated. More particularly, the object
102
references both the objects
104
and
106
, and is referenced by a thread of execution. Mark and sweep garbage collection is typically performed in two passes. During the first pass, each object that is not referenced by any objects is marked. For instance, object
108
is not referenced by any of the objects
102
,
104
, or
106
and is therefore marked for deletion. During the second pass, the memory for each object that is not marked is reclaimed.
FIG. 1B
is a block diagram illustrating the memory of
FIG. 1A
upon completion of a conventional mark and sweep garbage collection process. As shown, the object
108
, marked in
FIG. 1A
, is deleted and therefore not shown in FIG.
1
B. The objects
102
,
104
, and
106
remain after completion of the garbage collection process. It is important to note that objects are not usually relocated during mark and sweep garbage collection.
Another method of garbage collection, copying garbage collection, is also commonly used.
FIG. 2A
is an exemplary block diagram illustrating objects in memory during a conventional copying garbage collection process. As shown, within memory
200
are multiple objects. For instance, a first object
202
, “A”, a second object
204
, “B”, and a third object
206
, “D”, are stored in memory and all are reachable from a root. In addition, a fourth object
208
, “C”, is stored in the memory
200
but is not referenced by any other objects in memory.
FIG. 2B
is a block diagram illustrating the memory of
FIG. 2A
upon completion of a conventional copying garbage collection process. During copying garbage collection, all objects that are referenced by one or more objects are copied while those objects that are not referenced by any other objects are not copied. Thus, all objects that are not copied are garbage. For instance, as shown in
FIG. 2B
, the fourth object
208
, “C”, is not copied. Once copied, the memory for the original objects shown in
FIG. 2A
may then be reclaimed.
During copying garbage collection, the objects may be placed in various orders during the copying process.
FIG. 3A
is a block diagram illustrating an exemplary configuration of objects in memory. As shown, a memory
300
stores a first object
302
, “A”, a second object
304
, “B”, a third object
306
, “D”. The first object
302
references both the second object
304
and the third object
306
. A fourth object
308
, “C”, is referenced by none of the objects.
Since the first object
302
references both the second and third objects
304
and
306
, the objects may be placed in two different orders.
FIG. 3B
is a block diagram illustrating one possible configuration of the objects of
FIG. 3A
upon completion of copying garbage collection. As shown, the second object
304
may be placed adjacent to the first object
302
while the third object
306
may be placed adjacent to the second object
304
.
FIG. 3C
is a block diagram illustrating another possible configuration of the objects of
FIG. 3A
upon completion of copying garbage collection. As shown, rather than placing the second object
304
adjacent to the first object
302
, the third object
306
is placed adjacent to the first object
302
. In the simplified examples illustrated in FIG.
3
B and
FIG. 3C
, the objects may be placed in two different orders. It would be beneficial if a mechanism were designed to enable the objects to be ordered while maximizing the speed of access of the objects in memory.
In object-oriented programming, code and data are merged into objects. Each object is defined via its class, which determines the properties of an object. In other words, objects are individual instances of a class. Moreover, each object may include various fields as well as methods.
As disclosed in the article entitled “Using Generational Garbage Collection To Implement Cache-Conscious Data Placement” by Trishul M. Chilimbi and James R. Larus, which appeared in International Symposium on Memory Management (ISMM '98), October, 1998, objects accessed closely together in time may be stored in memory so that they will be fetched in the same cache line. The process disclosed in Chilimbi will be briefly described with reference to
FIGS. 4A
,
4
B, and
4
C.
FIG. 4A
is a block diagram illustrating an exemplary set of objects stored in memory and associated fields. As shown, a first object
400
, “A”, includes a first field
402
, “x”, and a second field
404
, “y”. Similarly, a second object
406
, “B”, includes a first field
408
, “w”, and a second field
410
, “z”. A third object
412
, “C”, includes a field
414
, “e”, and a fourth object
416
, “D”, includes a field
418
, “f”.
FIG. 4B
is a block diagram illustrating an exemplary log of memory accesses that may be produced during the execution of a computer application accessing the objects and fields shown in FIG.
4
A. In Chilimbi, a computer application is instrumented such that memory references (e.g., load and store commands) are logged. When the instrumented computer application is executed, a log of memory accesses
420
is produced. More specifically, an object
422
is logged for each memory access. For instance, when a field (e.g., the first field
402
) of the first object
400
, “A”, is fetched from memory, this memory access is logged as shown in entry
426
.
The memory access log is then used to create a temporal reference graph modeling the reference locality between objects.
FIG. 4C
is an exemplary temporal reference graph illustrating the accesses of objects in memory and the temporal relationships of these memory accesses that may be produced from the log of memory accesses shown in FIG.
4
B. As shown in temporal reference graph
428
, accesses of the objects are placed in the graph according to the temporal relationsh
Grarup Steffen
Stoutamire David P.
Beyer Weaver & Thomas LLP
Shah Sanjiv
Sun Microsystems Inc.
LandOfFree
Methods and apparatus for improving locality of reference... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Methods and apparatus for improving locality of reference..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Methods and apparatus for improving locality of reference... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3101393