forked from ldct/isicp
-
Notifications
You must be signed in to change notification settings - Fork 0
/
5-3-storage.html
550 lines (423 loc) · 37.7 KB
/
5-3-storage.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.1//EN" "http://www.w3.org/TR/xhtml11/DTD/xhtml11.dtd">
<html>
<head>
<meta charset="UTF-8">
<link rel="stylesheet" type="text/css" href="web-worker-interpreter/deps/codemirror/lib/codemirror.css" />
<link rel="stylesheet" type="text/css" href="css/isicp.css" />
<link rel="stylesheet" type="text/css" href="css/footnotes.css" />
<link rel="stylesheet" type="text/css" href="css/theme.css" />
<script src="js/helper.js"></script>
<script src="js/jquery.min.js"></script>
<script src="web-worker-interpreter/deps/codemirror/lib/codemirror.js"></script>
<script src="web-worker-interpreter/deps/codemirror/mode/scheme/scheme.js"></script>
<script src="web-worker-interpreter/coding.js"> </script>
<script>
set_interpreter_path("web-worker-interpreter/");
set_language("scheme");
</script>
<script src="js/footnotes.js"></script>
<script type="text/x-mathjax-config">
MathJax.Hub.Config({
tex2jax: {inlineMath: [['$','$']]}
});
</script>
<script type="text/javascript" src="http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML"></script>
<title> iSICP 2.4 - Multiple Representations for Abstract Data </title>
<script type="text/javascript">
var _gaq = _gaq || [];
_gaq.push(['_setAccount', 'UA-36868476-1']);
_gaq.push(['_trackPageview']);
(function() {
var ga = document.createElement('script'); ga.type = 'text/javascript'; ga.async = true;
ga.src = ('https:' == document.location.protocol ? 'https://ssl' : 'http://www') + '.google-analytics.com/ga.js';
var s = document.getElementsByTagName('script')[0]; s.parentNode.insertBefore(ga, s);
})();
</script>
</head>
<body>
<div id="sidebox">
<div class="tab"></div>
<div class="content">
<p>
<a href="index.html" class="navlink"> <img src='images/home.svg' width=32 height=32> </a>
<span id="toc-link" class="navlink"> <img src='images/list.svg' width=32 height=32> </span>
<span id="currently-editing-link" class="navlink"> <img src='images/file-edit.svg' width=32 height=32> </span>
<script src="http://cdn.jotfor.ms/static/feedback2.js?3.2.310" type="text/javascript">
new JotformFeedback({
formId:'40222623177447',
base:'http://jotform.me/',
windowTitle:'Notify Me',
background:'#FFA500',
fontColor:'#FFFFFF',
type:false,
height:500,
width:700
});
</script>
<a class="lightbox-40222623177447" style="cursor:pointer;color:blue;text-decoration:underline;"><img src='images/envelope.svg' width=32 height=32></a>
<p>
<div id="currently-editing"> </div>
<script>
function hideAll() {
$("#currently-editing").hide();
$("#toc").hide();
}
$("#currently-editing-link").click(function() {
hideAll();
$("#currently-editing").show();
});
$("#toc-link").click(function() {
hideAll();
$("#toc").show();
});
</script>
<div id="toc"> </div>
<p style='font-size:12px'> (Click on the left edge of this green box to hide it!)
<script>
hideAll();
$("#toc").show();
</script>
</div>
</div>
<script>
$('#sidebox .tab').toggle(function(){
$('#sidebox').animate({'right':'0%'});
}, function(){
$('#sidebox').animate({'right':'-30%'});
});
$(document).ready(createTOC);
</script>
<div id="main">
<h2> Storage Allocation and Garbage Collection </h2>
<p> In section 5-4, we will show how to implement a Scheme evaluator as a register machine. In order to simplify the discussion, we will assume that our register machines can be equipped with a <tt>list-structured memory</tt> , in which the basic operations for manipulating list-structured data are primitive. Postulating the existence of such a memory is a useful abstraction when one is focusing on the mechanisms of control in a Scheme interpreter, but this does not reflect a realistic view of the actual primitive data operations of contemporary computers. To obtain a more complete picture of how a Lisp system operates, we must investigate how list structure can be represented in a way that is compatible with conventional computer memories.
<p> There are two considerations in implementing list structure. The first is purely an issue of representation: how to represent the ``box-and-pointer''structure of Lisp pairs, using only the storage and addressing capabilities of typical computer memories. The second issue concerns the management of memory as a computation proceeds. The operation of a Lisp system depends crucially on the ability to continually create new data objects. These include objects that are explicitly created by the Lisp procedures being interpreted as well as structures created by the interpreter itself, such as environments and argument lists. Although the constant creation of new data objects would pose no problem on a computer with an infinite amount of rapidly addressable memory, computer memories are available only in finite sizes (more's the pity). Lisp systems thus provide an <tt>automatic storage allocation</tt> facility to support the illusion of an infinite memory. When a data object is no longer needed, the memory allocated to it is automatically recycled and used to construct new data objects. There are various techniques for providing such automatic storage allocation. The method we shall discuss in this section is called <tt>garbage collection</tt>
.
@menu
* 5-3-1:: Memory as Vectors
* 5-3-2:: Maintaining the Illusion of Infinite Memory
@end menu
<h3> Memory as Vectors </h3>
<p> A conventional computer memory can be thought of as an array of cubbyholes, each of which can contain a piece of information. Each cubbyhole has a unique name, called its <tt>address</tt> or <tt>location</tt> . Typical memory systems provide two primitive operations: one that fetches the data stored in a specified location and one that assigns new data to a specified location. Memory addresses can be incremented to support sequential access to some set of the cubbyholes. More generally, many important data operations require that memory addresses be treated as data, which can be stored in memory locations and manipulated in machine registers. The representation of list structure is one application of such <tt>address arithmetic</tt>.
<p> To model computer memory, we use a new kind of data structure called a <tt>vector</tt> . Abstractly, a vector is a compound data object whose individual elements can be accessed by means of an integer index in an amount of time that is independent of the index.@footnote{We could represent memory as lists of items. However, the access time would then not be independent of the index, since accessing the nth element of a list requires n - 1 <tt>cdr</tt> operations.} In order to describe memory operations, we use two primitive Scheme procedures for manipulating vectors:
<ul>
@item
<tt>(vector-ref <vector</tt>> <@var{n>)} returns the nth
element of the vector.
@item
<tt>(vector-set! <vector</tt>> <@var{n> <value>)}
sets the nth element of the vector to the designated value.
</ul>
<p> For example, if <tt>v</tt> is a vector, then <tt>(vector-ref v 5)</tt> gets the fifth entry in the vector <tt>v</tt> and <tt>(vector-set! v 5 7)</tt> changes the value of the fifth entry of the vector <tt>v</tt> to 7.@footnote{For completeness, we should specify a <tt>make-vector</tt> operation that constructs vectors. However, in the present application we will use vectors only to model fixed divisions of the computer memory.} For computer memory, this access can be implemented through the use of address arithmetic to combine a <tt>base address</tt> that specifies the beginning location of a vector in memory with an <tt>index</tt> that specifies the offset of a particular element of the vector.
<h4> Representing Lisp data </h4>
<p> We can use vectors to implement the basic pair structures required for a list-structured memory. Let us imagine that computer memory is divided into two vectors: <tt>the-cars</tt> and <tt>the-cdrs</tt>. We will represent list structure as follows: A pointer to a pair is an index into the two vectors. The <tt>car</tt> of the pair is the entry in <tt>the-cars</tt> with the designated index, and the <tt>cdr</tt> of the pair is the entry in <tt>the-cdrs</tt> with the designated index. We also need a representation for objects other than pairs (such as numbers and symbols) and a way to distinguish one kind of data from another. There are many methods of accomplishing this, but they all reduce to using <tt>typed pointers</tt> , that is, to extending the notion of ``pointer''to include information on data type.@footnote{This is precisely the same ``tagged data'' idea we introduced in Chapter 2 for dealing with generic operations. Here, however, the data types are included at the primitive machine level rather than constructed through the use of lists.} The data type enables the system to distinguish a pointer to a pair (which consists of the ``pair'' data type and an index into the memory vectors) from pointers to other kinds of data (which consist of some other data type and whatever is being used to represent data of that type). Two data objects are considered to be the same (<tt>eq?</tt>) if their pointers are identical.@footnote{Type information may be encoded in a variety of ways, depending on the details of the machine on which the Lisp system is to be implemented. The execution efficiency of Lisp programs will be strongly dependent on how cleverly this choice is made, but it is difficult to formulate general design rules for good choices. The most straightforward way to implement typed pointers is to allocate a fixed set of bits in each pointer to be a <tt>type field</tt> that encodes the data type. Important questions to be addressed in designing such a representation include the following: How many type bits are required? How large must the vector indices be? How efficiently can the primitive machine instructions be used to manipulate the type fields of pointers? Machines that include special hardware for the efficient handling of type fields are said to have <tt>tagged architectures</tt> .} Figure 5-14 illustrates the use of this method to represent the list <tt>((1 2) 3 4)</tt>, whose box-and-pointer diagram is also shown. We use letter prefixes to denote the data-type information. Thus, a pointer to the pair with index 5 is denoted <tt>p5</tt>, the empty list is denoted by the pointer <tt>e0</tt>, and a pointer to the number 4 is denoted <tt>n4</tt>. In the box-and-pointer diagram, we have indicated at the lower left of each pair the vector index that specifies where the <tt>car</tt> and <tt>cdr</tt> of the pair are stored. The blank locations in <tt>the-cars</tt> and <tt>the-cdrs</tt> may contain parts of other list structures (not of interest here).
<div class="exercise">
<p> <b>Figure 5.14:</b> Box-and-pointer and memory-vector representations of the list <tt>((1 2) 3 4)</tt>.
<pre>
+---+---+ +---+---+ +---+---+
((1 2) 3 4) -->| * | *-+-------------->| * | *-+--->| * | / |
+-|-+---+ +-|-+---+ +-|-+---+
1 | 2 | 4 |
V V V
+---+---+ +---+---+ +---+ +---+
| * | *-+--->| * | / | | 3 | | 4 |
+-|-+---+ +-|-+---+ +---+ +---+
5 | 7 |
V V
+---+ +---+
| 1 | | 2 |
+---+ +---+
Index 0 1 2 3 4 5 6 7 8 ...
+----+----+----+----+----+----+----+----+----+----
the-cars | | p5 | n3 | | n4 | n1 | | n2 | | ...
+----+----+----+----+----+----+----+----+----+----
the-cdrs | | p2 | p4 | | e0 | p7 | | e0 | | ...
+----+----+----+----+----+----+----+----+----+----
</pre>
</div>
<p> A pointer to a number, such as <tt>n4</tt>, might consist of a type indicating numeric data together with the actual representation of the number 4.@footnote{This decision on the representation of numbers determines whether <tt>eq?</tt>, which tests equality of pointers, can be used to test for equality of numbers. If the pointer contains the number itself, then equal numbers will have the same pointer. But if the pointer contains the index of a location where the number is stored, equal numbers will be guaranteed to have equal pointers only if we are careful never to store the same number in more than one location.} To deal with numbers that are too large to be represented in the fixed amount of space allocated for a single pointer, we could use a distinct <tt>bignum</tt> data type, for which the pointer designates a list in which the parts of the number are stored.@footnote{This is just like writing a number as a sequence of digits, except that each ``digit'' is a number between 0 and the largest number that can be stored in a single pointer.}
<p> A symbol might be represented as a typed pointer that designates a sequence of the characters that form the symbol's printed representation. This sequence is constructed by the Lisp reader when the character string is initially encountered in input. Since we want two instances of a symbol to be recognized as the ``same'' symbol by <tt>eq?</tt> and we want <tt>eq?</tt> to be a simple test for equality of pointers, we must ensure that if the reader sees the same character string twice, it will use the same pointer (to the same sequence of characters) to represent both occurrences. To accomplish this, the reader maintains a table, traditionally called the <tt>obarray</tt> , of all the symbols it has ever encountered. When the reader encounters a character string and is about to construct a symbol, it checks the obarray to see if it has ever before seen the same character string. If it has not, it uses the characters to construct a new symbol (a typed pointer to a new character sequence) and enters this pointer in the obarray. If the reader has seen the string before, it returns the symbol pointer stored in the obarray. This process of replacing character strings by unique pointers is called <tt>interning</tt> symbols.
<h4> Implementing the primitive list operations </h4>
<p> Given the above representation scheme, we can replace each ``primitive'' list operation of a register machine with one or more primitive vector operations. We will use two registers, <tt>the-cars</tt> and <tt>the-cdrs</tt>, to identify the memory vectors, and will assume that <tt>vector-ref</tt> and <tt>vector-set!</tt> are available as primitive operations. We also assume that numeric operations on pointers (such as incrementing a pointer, using a pair pointer to index a vector, or adding two numbers) use only the index portion of the typed pointer.
<p> For example, we can make a register machine support the instructions
<div id="">
(assign <reg_1> (op car) (reg <reg_2>))
(assign <reg_1> (op cdr) (reg <reg_2>))
</div>
<script>
prompt();
</script>
<p> if we implement these, respectively, as
<div id="">
(assign <reg_1> (op vector-ref) (reg the-cars) (reg <reg_2>))
(assign <reg_1> (op vector-ref) (reg the-cdrs) (reg <reg_2>))
</div>
<script>
prompt();
</script>
<p> The instructions
<div id="">
(perform (op set-car!) (reg <reg_1>) (reg <reg_2>))
(perform (op set-cdr!) (reg <reg_1>) (reg <reg_2>))
</div>
<script>
prompt();
</script>
<p> are implemented as
<div id="">
(perform
(op vector-set!) (reg the-cars) (reg <reg_1>) (reg <reg_2>))
(perform
(op vector-set!) (reg the-cdrs) (reg <reg_1>) (reg <reg_2>))
</div>
<script>
prompt();
</script>
<p> <tt>Cons</tt> is performed by allocating an unused index and storing the arguments to <tt>cons</tt> in <tt>the-cars</tt> and <tt>the-cdrs</tt> at that indexed vector position. We presume that there is a special register, <tt>free</tt>, that always holds a pair pointer containing the next available index, and that we can increment the index part of that pointer to find the next free location.@footnote{There are other ways of finding free storage. For example, we could link together all the unused pairs into a <tt>free list</tt> . Our free locations are consecutive (and hence can be accessed by incrementing a pointer) because we are using a compacting garbage collector, as we will see in section 5-3-2.} For example, the instruction
<div id="">
(assign <reg_1> (op cons) (reg <reg_2>) (reg <reg_3>))
</div>
<script>
prompt();
</script>
<p> is implemented as the following sequence of vector operations:@footnote{This is essentially the implementation of <tt>cons</tt> in terms of <tt>set-car!</tt> and <tt>set-cdr!</tt>, as described in section 3-3-1. The operation <tt>get-new-pair</tt> used in that implementation is realized here by the <tt>free</tt> pointer.}
<div id="">
(perform
(op vector-set!) (reg the-cars) (reg free) (reg <reg_2>))
(perform
(op vector-set!) (reg the-cdrs) (reg free) (reg <reg_3>))
(assign <reg_1> (reg free))
(assign free (op +) (reg free) (const 1))
</div>
<script>
prompt();
</script>
<p> The <tt>eq?</tt> operation
<div id="">
(op eq?) (reg <reg_1>) (reg <reg_2>)
</div>
<script>
prompt();
</script>
<p> simply tests the equality of all fields in the registers, and predicates such as <tt>pair?</tt>, <tt>null?</tt>, <tt>symbol?</tt>, and <tt>number?</tt> need only check the type field.
<h4> Implementing stacks </h4>
<p> Although our register machines use stacks, we need do nothing special here, since stacks can be modeled in terms of lists. The stack can be a list of the saved values, pointed to by a special register <tt>the-stack</tt>. Thus, <tt>(save <reg</tt>>) can be implemented as
<div id="">
(assign the-stack (op cons) (reg <reg>) (reg the-stack))
</div>
<script>
prompt();
</script>
<p> Similarly, <tt>(restore <reg</tt>>) can be implemented as
<div id="">
(assign <reg> (op car) (reg the-stack))
(assign the-stack (op cdr) (reg the-stack))
</div>
<script>
prompt();
</script>
<p> and <tt>(perform (op initialize-stack))</tt> can be implemented as
<div id="">
(assign the-stack (const ()))
</div>
<script>
prompt();
</script>
<p> These operations can be further expanded in terms of the vector operations given above. In conventional computer architectures, however, it is usually advantageous to allocate the stack as a separate vector. Then pushing and popping the stack can be accomplished by incrementing or decrementing an index into that vector.
<div class="exercise">
<p> <b>Exercise 5.20:</b> Draw the box-and-pointer representation and the memory-vector representation (as in Figure 5-14) of the list structure produced by
<div id="">
(define x (cons 1 2))
(define y (list x x))
</div>
<script>
prompt();
</script>
<p> with the <tt>free</tt> pointer initially <tt>p1</tt>. What is the final value of <tt>free</tt> ? What pointers represent the values of <tt>x</tt> and <tt>y</tt> ?
</div>
<div class="exercise">
<p> <b>Exercise 5.21:</b> Implement register machines for the following procedures. Assume that the list-structure memory operations are available as machine primitives.
<ul>
<li>
Recursive <tt>count-leaves</tt>:
<div id="">
(define (count-leaves tree)
(cond ((null? tree) 0)
((not (pair? tree)) 1)
(else (+ (count-leaves (car tree))
(count-leaves (cdr tree))))))
</div>
<script>
prompt();
</script>
</li>
<li>
Recursive <tt>count-leaves</tt> with explicit counter:
<div id="">
(define (count-leaves tree)
(define (count-iter tree n)
(cond ((null? tree) n)
((not (pair? tree)) (+ n 1))
(else (count-iter (cdr tree)
(count-iter (car tree) n)))))
(count-iter tree 0))
</div>
<script>
prompt();
</script>
</li>
</ul>
</div>
<div class="exercise">
<p> <b>Exercise 5.22:</b> Exercise 3-12 of section 3-3-1 presented an <tt>append</tt> procedure that appends two lists to form a new list and an <tt>append!</tt> procedure that splices two lists together. Design a register machine to implement each of these procedures. Assume that the list-structure memory operations are available as primitive operations.
</div>
<h3> Maintaining the Illusion of Infinite Memory </h3>
<p> The representation method outlined in section 5-3-1 solves the problem of implementing list structure, provided that we have an infinite amount of memory. With a real computer we will eventually run out of free space in which to construct new pairs.@footnote{This may not be true eventually, because memories may get large enough so that it would be impossible to run out of free memory in the lifetime of the computer. For example, there are about 3*(10^13), microseconds in a year, so if we were to <tt>cons</tt> once per microsecond we would need about 10^15 cells of memory to build a machine that could operate for 30 years without running out of memory. That much memory seems absurdly large by today's standards, but it is not physically impossible. On the other hand, processors are getting faster and a future computer may have large numbers of processors operating in parallel on a single memory, so it may be possible to use up memory much faster than we have postulated.} However, most of the pairs generated in a typical computation are used only to hold intermediate results. After these results are accessed, the pairs are no longer needed---they are <tt>garbage</tt> . For instance, the computation
<div id="">
(accumulate + 0 (filter odd? (enumerate-interval 0 n)))
</div>
<script>
prompt();
</script>
<p> constructs two lists: the enumeration and the result of filtering the enumeration. When the accumulation is complete, these lists are no longer needed, and the allocated memory can be reclaimed. If we can arrange to collect all the garbage periodically, and if this turns out to recycle memory at about the same rate at which we construct new pairs, we will have preserved the illusion that there is an infinite amount of memory.
<p> In order to recycle pairs, we must have a way to determine which allocated pairs are not needed (in the sense that their contents can no longer influence the future of the computation). The method we shall examine for accomplishing this is known as <tt>garbage collection</tt> . Garbage collection is based on the observation that, at any moment in a Lisp interpretation, the only objects that can affect the future of the computation are those that can be reached by some succession of <tt>car</tt> and <tt>cdr</tt> operations starting from the pointers that are currently in the machine registers.@footnote{We assume here that the stack is represented as a list as described in section 5-3-1, so that items on the stack are accessible via the pointer in the stack register.} Any memory cell that is not so accessible may be recycled.
<p> There are many ways to perform garbage collection. The method we shall examine here is called <tt>stop-and-copy</tt> . The basic idea is to divide memory into two halves: ``working memory'' and ``free memory.'' When <tt>cons</tt> constructs pairs, it allocates these in working memory. When working memory is full, we perform garbage collection by locating all the useful pairs in working memory and copying these into consecutive locations in free memory. (The useful pairs are located by tracing all the <tt>car</tt> and <tt>cdr</tt> pointers, starting with the machine registers.) Since we do not copy the garbage, there will presumably be additional free memory that we can use to allocate new pairs. In addition, nothing in the working memory is needed, since all the useful pairs in it have been copied. Thus, if we interchange the roles of working memory and free memory, we can continue processing; new pairs will be allocated in the new working memory (which was the old free memory). When this is full, we can copy the useful pairs into the new free memory (which was the old working memory).@footnote{This idea was invented and first implemented by Minsky, as part of the implementation of Lisp for the PDP-1 at the @acronym{MIT} Research Laboratory of Electronics. It was further developed by Fenichel and Yochelson (1969) for use in the Lisp implementation for the Multics time-sharing system. Later, Baker (1978) developed a ``real-time''version of the method, which does not require the computation to stop during garbage collection. Baker's idea was extended by Hewitt, Lieberman, and Moon (see Lieberman and Hewitt 1983) to take advantage of the fact that some structure is more volatile and other structure is more permanent.
<p> An alternative commonly used garbage-collection technique is the <tt>mark-sweep</tt> method. This consists of tracing all the structure accessible from the machine registers and marking each pair we reach. We then scan all of memory, and any location that is unmarked is ``swept up'' as garbage and made available for reuse. A full discussion of the mark-sweep method can be found in Allen 1978.
<p> The Minsky-Fenichel-Yochelson algorithm is the dominant algorithm in use for large-memory systems because it examines only the useful part of memory. This is in contrast to mark-sweep, in which the sweep phase must check all of memory. A second advantage of stop-and-copy is that it is a <tt>compacting</tt> garbage collector. That is, at the end of the garbage-collection phase the useful data will have been moved to consecutive memory locations, with all garbage pairs compressed out. This can be an extremely important performance consideration in machines with virtual memory, in which accesses to widely separated memory addresses may require extra paging operations.}
<h4> Implementation of a stop-and-copy garbage collector </h4>
<p> We now use our register-machine language to describe the stop-and-copy algorithm in more detail. We will assume that there is a register called <tt>root</tt> that contains a pointer to a structure that eventually points at all accessible data. This can be arranged by storing the contents of all the machine registers in a pre-allocated list pointed at by <tt>root</tt> just before starting garbage collection.@footnote{This list of registers does not include the registers used by the storage-allocation system---<tt>root</tt>, <tt>the-cars</tt>, <tt>the-cdrs</tt>, and the other registers that will be introduced in this section.} We also assume that, in addition to the current working memory, there is free memory available into which we can copy the useful data. The current working memory consists of vectors whose base addresses are in registers called <tt>the-cars</tt> and <tt>the-cdrs</tt>, and the free memory is in registers called <tt>new-cars</tt> and <tt>new-cdrs</tt>.
<p> Garbage collection is triggered when we exhaust the free cells in the current working memory, that is, when a <tt>cons</tt> operation attempts to increment the <tt>free</tt> pointer beyond the end of the memory vector. When the garbage-collection process is complete, the <tt>root</tt> pointer will point into the new memory, all objects accessible from the <tt>root</tt> will have been moved to the new memory, and the <tt>free</tt> pointer will indicate the next place in the new memory where a new pair can be allocated. In addition, the roles of working memory and new memory will have been interchanged---new pairs will be constructed in the new memory, beginning at the place indicated by <tt>free</tt>, and the (previous) working memory will be available as the new memory for the next garbage collection. Figure 5-15 shows the arrangement of memory just before and just after garbage collection.
<div class="exercise">
<p> <b>Figure 5.15:</b> Reconfiguration of memory by the garbage-collection process.
<pre>
Just before garbage collection
+------------------------------------+
the-cars | | working
| mixture of useful data and garbage | memory
the-cdrs | |
+------------------------------------+
^
| free
+------------------------------------+
new-cars | | free
| free memory | memory
new-cdrs | |
+------------------------------------+
Just after garbage collection
+------------------------------------+
new-cars | | new
| discarded memory | free
new-cdrs | | memory
+------------------------------------+
+------------------+-----------------+
the-cars | | | new
| useful data | free area | working
the-cdrs | | | memory
+------------------+-----------------+
^
| free
</pre>
</div>
<p> The state of the garbage-collection process is controlled by maintaining two pointers: <tt>free</tt> and <tt>scan</tt>. These are initialized to point to the beginning of the new memory. The algorithm begins by relocating the pair pointed at by <tt>root</tt> to the beginning of the new memory. The pair is copied, the <tt>root</tt> pointer is adjusted to point to the new location, and the <tt>free</tt> pointer is incremented. In addition, the old location of the pair is marked to show that its contents have been moved. This marking is done as follows: In the <tt>car</tt> position, we place a special tag that signals that this is an already-moved object. (Such an object is traditionally called a <tt>broken heart</tt> .)@footnote{The term <em>broken heart</em> was coined by David Cressey, who wrote a garbage collector for MDL, a dialect of Lisp developed at @acronym{MIT} during the early 1970s.} In the <tt>cdr</tt> position we place a <tt>forwarding address</tt> that points at the location to which the object has been moved.
<p> After relocating the root, the garbage collector enters its basic cycle. At each step in the algorithm, the <tt>scan</tt> pointer (initially pointing at the relocated root) points at a pair that has been moved to the new memory but whose <tt>car</tt> and <tt>cdr</tt> pointers still refer to objects in the old memory. These objects are each relocated, and the <tt>scan</tt> pointer is incremented. To relocate an object (for example, the object indicated by the <tt>car</tt> pointer of the pair we are scanning) we check to see if the object has already been moved (as indicated by the presence of a broken-heart tag in the <tt>car</tt> position of the object). If the object has not already been moved, we copy it to the place indicated by <tt>free</tt>, update <tt>free</tt>, set up a broken heart at the object's old location, and update the pointer to the object (in this example, the <tt>car</tt> pointer of the pair we are scanning) to point to the new location. If the object has already been moved, its forwarding address (found in the <tt>cdr</tt> position of the broken heart) is substituted for the pointer in the pair being scanned. Eventually, all accessible objects will have been moved and scanned, at which point the <tt>scan</tt> pointer will overtake the <tt>free</tt> pointer and the process will terminate.
<p> We can specify the stop-and-copy algorithm as a sequence of instructions for a register machine. The basic step of relocating an object is accomplished by a subroutine called <tt>relocate-old-result-in-new</tt>. This subroutine gets its argument, a pointer to the object to be relocated, from a register named <tt>old</tt>. It relocates the designated object (incrementing <tt>free</tt> in the process), puts a pointer to the relocated object into a register called <tt>new</tt>, and returns by branching to the entry point stored in the register <tt>relocate-continue</tt>. To begin garbage collection, we invoke this subroutine to relocate the <tt>root</tt> pointer, after initializing <tt>free</tt> and <tt>scan</tt>. When the relocation of <tt>root</tt> has been accomplished, we install the new pointer as the new <tt>root</tt> and enter the main loop of the garbage collector.
<div id="">
begin-garbage-collection
(assign free (const 0))
(assign scan (const 0))
(assign old (reg root))
(assign relocate-continue (label reassign-root))
(goto (label relocate-old-result-in-new))
reassign-root
(assign root (reg new))
(goto (label gc-loop))
</div>
<script>
prompt();
</script>
<p> In the main loop of the garbage collector we must determine whether there are any more objects to be scanned. We do this by testing whether the <tt>scan</tt> pointer is coincident with the <tt>free</tt> pointer. If the pointers are equal, then all accessible objects have been relocated, and we branch to <tt>gc-flip</tt>, which cleans things up so that we can continue the interrupted computation. If there are still pairs to be scanned, we call the relocate subroutine to relocate the <tt>car</tt> of the next pair (by placing the <tt>car</tt> pointer in <tt>old</tt>). The <tt>relocate-continue</tt> register is set up so that the subroutine will return to update the <tt>car</tt> pointer.
<div id="">
gc-loop
(test (op =) (reg scan) (reg free))
(branch (label gc-flip))
(assign old (op vector-ref) (reg new-cars) (reg scan))
(assign relocate-continue (label update-car))
(goto (label relocate-old-result-in-new))
</div>
<script>
prompt();
</script>
<p> At <tt>update-car</tt>, we modify the <tt>car</tt> pointer of the pair being scanned, then proceed to relocate the <tt>cdr</tt> of the pair. We return to <tt>update-cdr</tt> when that relocation has been accomplished. After relocating and updating the <tt>cdr</tt>, we are finished scanning that pair, so we continue with the main loop.
<div id="">
update-car
(perform
(op vector-set!) (reg new-cars) (reg scan) (reg new))
(assign old (op vector-ref) (reg new-cdrs) (reg scan))
(assign relocate-continue (label update-cdr))
(goto (label relocate-old-result-in-new))
update-cdr
(perform
(op vector-set!) (reg new-cdrs) (reg scan) (reg new))
(assign scan (op +) (reg scan) (const 1))
(goto (label gc-loop))
</div>
<script>
prompt();
</script>
<p> The subroutine <tt>relocate-old-result-in-new</tt> relocates objects as follows: If the object to be relocated (pointed at by <tt>old</tt>) is not a pair, then we return the same pointer to the object unchanged (in <tt>new</tt>). (For example, we may be scanning a pair whose <tt>car</tt> is the number 4. If we represent the <tt>car</tt> by <tt>n4</tt>, as described in section 5-3-1, then we want the ``relocated'' <tt>car</tt> pointer to still be <tt>n4</tt>.) Otherwise, we must perform the relocation. If the <tt>car</tt> position of the pair to be relocated contains a broken-heart tag, then the pair has in fact already been moved, so we retrieve the forwarding address (from the <tt>cdr</tt> position of the broken heart) and return this in <tt>new</tt>. If the pointer in <tt>old</tt> points at a yet-unmoved pair, then we move the pair to the first free cell in new memory (pointed at by <tt>free</tt>) and set up the broken heart by storing a broken-heart tag and forwarding address at the old location. <tt>Relocate-old-result-in-new</tt> uses a register <tt>oldcr</tt> to hold the <tt>car</tt> or the <tt>cdr</tt> of the object pointed at by <tt>old</tt>.@footnote{The garbage collector uses the low-level predicate <tt>pointer-to-pair?</tt> instead of the list-structure <tt>pair?</tt> operation because in a real system there might be various things that are treated as pairs for garbage-collection purposes. For example, in a Scheme system that conforms to the @acronym{IEEE} standard a procedure object may be implemented as a special kind of ``pair'' that doesn't satisfy the <tt>pair?</tt> predicate. For simulation purposes, <tt>pointer-to-pair?</tt> can be implemented as <tt>pair?</tt>.}
<div id="">
relocate-old-result-in-new
(test (op pointer-to-pair?) (reg old))
(branch (label pair))
(assign new (reg old))
(goto (reg relocate-continue))
pair
(assign oldcr (op vector-ref) (reg the-cars) (reg old))
(test (op broken-heart?) (reg oldcr))
(branch (label already-moved))
(assign new (reg free)) ; new location for pair
;; Update <tt>free</tt> pointer.
(assign free (op +) (reg free) (const 1))
;; Copy the <tt>car</tt> and <tt>cdr</tt> to new memory.
(perform (op vector-set!)
(reg new-cars) (reg new) (reg oldcr))
(assign oldcr (op vector-ref) (reg the-cdrs) (reg old))
(perform (op vector-set!)
(reg new-cdrs) (reg new) (reg oldcr))
;; Construct the broken heart.
(perform (op vector-set!)
(reg the-cars) (reg old) (const broken-heart))
(perform
(op vector-set!) (reg the-cdrs) (reg old) (reg new))
(goto (reg relocate-continue))
already-moved
(assign new (op vector-ref) (reg the-cdrs) (reg old))
(goto (reg relocate-continue))
</div>
<script>
prompt();
</script>
<p> At the very end of the garbage-collection process, we interchange the role of old and new memories by interchanging pointers: interchanging <tt>the-cars</tt> with <tt>new-cars</tt>, and <tt>the-cdrs</tt> with <tt>new-cdrs</tt>. We will then be ready to perform another garbage collection the next time memory runs out.
<div id="">
gc-flip
(assign temp (reg the-cdrs))
(assign the-cdrs (reg new-cdrs))
(assign new-cdrs (reg temp))
(assign temp (reg the-cars))
(assign the-cars (reg new-cars))
(assign new-cars (reg temp))
</div>
<script>
prompt();
</script>
<br>
<br>
<hr>
<div id="footnotes">
<h3 id='Notes'> Notes </h3>
</div>
<hr>
<p> <a rel="license" href="http://creativecommons.org/licenses/by-sa/3.0/deed.en_US" target="_blank"><img alt="Creative Commons License" style="border-width:0" src="http://i.creativecommons.org/l/by-sa/3.0/88x31.png" /></a><br /> Based on Structure and Interpretation of Computer Programs, a work at <a xmlns:dct="http://purl.org/dc/terms/" href="http://mitpress.mit.edu/sicp/" rel="dct:source" target="_blank">http://mitpress.mit.edu/sicp/</a>.
</div>
<a href="https://github.com/zodiac/isicp" target="_blank"><img style="position: absolute; top: 0; right: 0; border: 0;" src="https://s3.amazonaws.com/github/ribbons/forkme_right_green_007200.png" alt="Fork me on GitHub"></a>
</body>
</html>