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
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
.. _glossary-c:

=============================
Memory Management Glossary: C
=============================

.. include:: alphabet.txt

.. glossary::

    C89

        .. see:: :term:`C90`.

    C90

        .. aka:: *C89*.

        A revision of the ANSI/ISO Standard for the :term:`C`
        programming language. Although more than twenty years old, it
        remains the only form of Standard C that is supported by all
        the major compilers, including Microsoft Visual C.

        .. mps:specific::

            The public interface conforms to this standard. See
            :ref:`topic-interface`.

        .. bibref:: :ref:`ISO/IEC 9899:1990 <C1990>`.

    C99

        A revision of the ANSI/ISO Standard for C the :term:`C`
        programming language.

        .. mps:specific::

            :term:`Keyword arguments` can be conveniently passed to
            functions using C99's compound literal syntax. See
            :ref:`topic-keyword`.

        .. bibref:: :ref:`ISO/IEC 9899:1999 <C1999>`.

    cache (1)

        .. aka:: *cache memory*, *memory cache*.

        A processor's memory cache is a small piece of fast, but more
        expensive memory, usually :term:`static memory (1)`, used for
        copies of parts of :term:`main memory`. The cache is
        automatically used by the processor for fast access to any
        data currently :term:`resident` there. Access to the cache
        typically takes only a few processor clock cycles, whereas
        access to :term:`main memory` may take tens or even hundreds
        of cycles.

        What part of main memory is resident in a cache, and the
        mechanisms by which it is kept consistent, are quite varied.
        See :term:`cache policy`.

        Some systems have more than one level of cache. "Level 1
        cache" is the fastest, smallest :term:`storage level`, "level
        2" the next fastest, and so on.

        .. seealso:: :term:`cache (2)`, :term:`storage hierarchy`.

    cache (2)

        A cache is any small, fast piece of :term:`memory (1)`, used
        for copies of data that normally reside in a larger, slower
        piece of storage. The cache is used to speed up access to data
        :term:`resident` in the slower storage.

        In a typical cache, recently used data is :term:`resident` in
        the cache (although the details of this depend on the
        :term:`cache policy`). A :term:`cache (1)` is the most common
        example of a cache(2).

        .. seealso:: :term:`storage hierarchy`.

    cache memory

        .. see:: :term:`cache (1)`.

    cache policy

        Any :term:`cache (3) <caching (3)>` uses a *cache policy* to
        decide which data to store. A cache policy is an attempt to
        predict the future, so that the cache will provide swift
        responses to future requests.

        Cache policy may be implemented in hardware, software, or a
        combination of both. Some systems allow programs to influence
        cache policy, by giving hints or directions about future use
        of data.

        There are three main aspects of cache behavior which the cache
        policy can affect:

        1. Fetch policy. This determines which data is fetched into
           the cache, usually as a result of receiving a request for
           data that isn't cached.

        2. Eviction policy. This determines which data is discarded
           from the cache to provide space for newly fetched data.

        3. Write policy This determines how and when modifications to
           cached data are synchronized with the underlying storage.

        .. seealso:: :term:`cache (1)`, :term:`cache (2)`, :term:`cache (3) <caching (3)>`.

        .. bibref:: :ref:`Baker (1991) <BAKER91>`, :ref:`Wilson et al. (1992) <WLM92>`, :ref:`Zorn (1991) <ZORN91>`.

    caching (3)

        .. aka:: *memoization*, *tabling*.

        *Caching* is a heuristic that stores answers to questions
        asked in the past in a *cache* or a *table*, in order that
        they may be more quickly answered in the future. This process
        is also called memoization and tabling (by the :term:`Prolog`
        community).

        A "look-ahead cache" attempts to store answers to questions
        that will be asked soon. A :term:`cache (2)` is a common
        example of a cache(3).

    cactus stack

        .. aka:: *spaghetti stack*.

        A cactus stack is a :term:`stack` with branches. When
        diagrammed, its shape resembles that of a `saguaro cactus
        <https://en.wikipedia.org/wiki/Saguaro>`_.

        In languages that support :term:`continuations`,
        :term:`activation records` can have :term:`indefinite extent`.
        One technique for implementing continuations is not to copy
        the activation records that are captured, but rather to create
        a fork in the stack below the captured :term:`stack frames`,
        so that new frames appear as a parallel branch. Often the
        process of forking is done lazily: captured frames are only
        duplicated if they are modified.

    card

        A card is a division of memory, all cards being of equal size
        (in a particular area of discourse). A card is usually bigger
        than a :term:`word` and smaller than a :term:`page`. Cards are
        used in a technique called :term:`card marking` whereby
        :term:`dirty bits` (which record which portions of old
        generations have been written into) are maintained for each
        card. Often the use of cards will also entail the use of a
        :term:`crossing map`.

    card marking

        A technique for managing :term:`pointer` :term:`stores (1)`
        into old :term:`generations` (which in turn is used to track
        :term:`inter-generational pointers`). Each generation is
        divided into a number of equal-sized :term:`cards`, and when a
        generation is written into, the particular card written to is
        recorded (often by using a :term:`bitmap`). Subsequently, when
        :term:`scanning <scan>` an older generation in order to
        collect a younger generation, only the recorded cards (in the
        old generation) need to be scanned.

        .. seealso:: :term:`generational garbage collection`.

        .. bibref:: :ref:`Azagury et al. (1998) <AKPY98>`, :ref:`Hosking & Hudson (1993) <HH93>`, :ref:`Sobalvarro (1988) <SOBALVARRO88>`.

    cell

        .. see:: :term:`object`.

    Cheney collector

        .. aka:: *Cheney scan*.

        A Cheney collector uses the :term:`tospace` of a
        :term:`two-space collector` as a queue of objects remaining to
        be :term:`scanned <scan>`, thus eliminating the need for
        recursion when :term:`tracing <trace>` the :term:`graph` of
        :term:`objects`.

        .. bibref:: :ref:`Cheney (1970) <CHENEY70>`.

    Cheney scan

        .. see:: :term:`Cheney collector`.

    clamped state

        .. mps:specific::

            One of the four states an :term:`arena` can be in (the
            others being the :term:`unclamped state`, the
            :term:`parked state`, and the :term:`postmortem state`).
            In the clamped state, no object motion occurs and the
            staleness of :term:`location dependencies` does not
            change. However, a :term:`garbage collection` may be in
            progress. Call :c:func:`mps_arena_clamp` to put an arena
            into the clamped state.

    client arena

        .. mps:specific::

            An :term:`arena class` that gets its :term:`memory (2)`
            from the :term:`client program`. See
            :ref:`topic-arena-client`.

    client object

        .. mps:specific::

            A :term:`formatted object` that contains data from the
            :term:`client program`. One of three types of formatted
            objects, the other two being :term:`forwarding objects`
            and :term:`padding objects`.

    client pointer

        .. mps:specific::

            A pointer to the first word in an object that's not part
            of the :term:`in-band header`. See
            :ref:`topic-format-headers`.

        .. seealso:: :term:`base pointer`.

    client program

        .. see:: :term:`mutator`

    closure

        A closure is a function or procedure that is saved along with
        the current bindings from enclosing blocks for later
        invocation.

        Some programming languages, such as :term:`ALGOL`, permit
        nested blocks to access the local variables of enclosing
        blocks. :term:`Lisp`-like languages further permit such an
        inner block (in particular a function or procedure) to be
        saved for later invocation. The act of saving such an inner
        block along with the current bindings of variables in the
        enclosing blocks that are referenced by the inner block, is
        called *closing over* or *capturing* those variables. The
        object created is termed *a closure*. A closure is invoked
        just like the function from which it was built, passing
        whatever parameters the function accepts, but when the
        function executes, the variables that belong to enclosing
        blocks will have the bindings that were in effect when the
        closure was created.

        .. relevance::

            A closure is typically implemented by saving both the
            function and any :term:`activation records` that contain
            variables referenced by the function. The closure creates
            additional implicit :term:`references` to the bindings
            closed over and hence must be accounted for in any memory
            management scheme. The closure itself is an object that
            must be managed and may have either :term:`dynamic extent`
            or :term:`indefinite extent` depending on whether it is
            only used by inner blocks of the creating block or passed
            out of the creating block.

        .. seealso:: :term:`continuation`.

    coalesce

        Coalescing is the act of merging two adjacent :term:`free
        blocks`.

        Coalescing reduces :term:`external fragmentation`, but is not
        totally effective.

        Coalescing can be done as soon as blocks are freed, or it can
        be deferred until some time later (known as :term:`deferred
        coalescing`), or it might not be done at all.

        :ref:`Wilson et al. (1995) <WIL95>` has details about
        fragmentation, and which coalescing strategies are effective
        under what circumstances.

    cold end

        A :term:`control stack` has two ends: the oldest items are at
        the *cold end* and the newest items are at the *hot end*.
        Sometimes the cold end is called the "bottom" of the stack,
        but that is misleading when the stack grows downwards, as it
        does on common computing platforms.

        .. mps:specific::

            In order for the MPS to be able to :term:`scan`
            :term:`references` on the stack, the :term:`client
            program` must pass the location of the cold end of the
            stack (or the part of the stack that might contain
            references to memory managed by the MPS) to
            :c:func:`mps_root_create_thread`.

        .. opposite:: :term:`hot end`

    collect

        An :term:`object` is collected when it is :term:`reclaimed` by
        a :term:`garbage collector`.

        .. similar:: :term:`reclaim`.

    collection

        .. see:: :term:`collection cycle`.

    collection cycle

        .. aka:: *collection*.

        A collection cycle is a single complete execution of a
        :term:`tracing garbage collection` algorithm.

        Each collection cycle includes (not necessarily in strict
        order) choosing a :term:`condemned set`; :term:`scanning
        <scan>` :term:`roots` and :term:`objects` that have not been
        condemned; :term:`tracing <trace>` the object graph to find
        all condemned objects that are :term:`reachable`; and
        :term:`reclaiming <reclaim>` those that were not reachable.

        In non-incremental garbage collection, the :term:`mutator`
        pauses at the start of a collection cycle and cannot continue
        until it is complete. In :term:`incremental <incremental
        garbage collection>` and :term:`parallel <parallel garbage
        collection>` garbage collection, a collection cycle can be
        interleaved with, or simultaneous to, mutator activity.

    collector (1)

        .. see:: :term:`garbage collector`.

    collector (2)

        In a :term:`garbage-collected <garbage collection>` system,
        the part that executes the garbage collection code, which
        discovers unused :term:`memory (1)` and :term:`reclaims` it.

        For purposes of describing :term:`incremental garbage
        collection`, the system is divided into the :term:`mutator`
        and the *collector*. These can be separate threads of
        computation, or interleaved within the same thread.

        .. historical::

            This term is due to :ref:`Dijkstra et al. (1976)
            <DLMSS76>`.

        .. opposite:: :term:`mutator`.

    color
    colour

        In a :term:`tri-color marking` scheme, each :term:`node` has a
        one of three colors: :term:`black`, :term:`white`, or
        :term:`gray`. In a :term:`treadmill`, nodes may also be
        colored :term:`off-white`.

    commit limit

        .. mps:specific::

            The commit limit is a limit on the :term:`committed
            <mapped>` :term:`memory (2)` that the :term:`arena` will
            obtain from the operating system. It can be changed by
            calling :c:func:`mps_arena_commit_limit_set`.

    committed (1)

        .. see:: :term:`mapped`.

    committed (2)

        .. mps:specific::

            A block has been *committed* if it is fully initialized
            and is under the management of the MPS, as opposed to a
            block that is merely *reserved*. See
            :ref:`topic-allocation-point-protocol`.

    compactifying

        .. see:: :term:`compaction`.

    compaction

        .. aka:: *compactifying*.

        Compaction is the process of :term:`moving <moving garbage
        collector>` :term:`live` :term:`objects` to eliminate
        :term:`dead` space between them. Some people call this
        *compactifying*, to distinguish it from techniques for
        compressing data structures.

        Compaction is used to avoid :term:`external fragmentation` and
        to increase :term:`locality of reference`.

    composite object

        In the :term:`PostScript` language, *composite objects* are
        the :term:`boxed` objects.

        Unlike a :term:`simple object`, the main data (what PostScript
        calls *the value*) in a composite object are stored
        separately, in :term:`VM (2)`. Several composite objects can
        share the same value.

        .. similar:: :term:`boxed`.

        .. opposite:: :term:`simple object`.

    comprehensive

        A :term:`collector (1)` is *comprehensive* if all
        :term:`garbage` (or, all :term:`unreachable` :term:`objects`)
        is :term:`reclaimed` in one :term:`collection cycle`.

        .. seealso:: :term:`garbage collection`.

    concurrent garbage collection

        .. see:: :term:`parallel garbage collection`.

    condemned set

        .. aka:: *threatened set*.

        *Condemned* :term:`objects` are those which are
        candidates for :term:`recycling <recycle>` within a
        :term:`collection cycle`.

        At the start of a collection cycle, the :term:`collector (1)`
        may choose to condemn some objects (the *condemned set* or
        *threatened set*) but not to condemn others (the :term:`immune
        set`). Objects that are not condemned are assumed to be
        :term:`live` and behave as :term:`roots` for the
        purposes of that collection cycle.

        Many simple :term:`tracing garbage collection` algorithms
        begin by condemning all objects, but :term:`generational
        garbage collectors <generational garbage collection>` will
        condemn individual :term:`generations` or
        combinations of generations. Often young generations are
        condemned but older ones are not, because objects in older
        generations are less likely to have become
        :term:`unreachable`.

        In collectors using :term:`tri-color marking`, at the start of
        a collection cycle the condemned set is exactly the set of
        objects that the collector colors :term:`white`.

        .. opposite:: :term:`immune set`.

    connected

        :term:`Objects` are connected if and only if one
        contains a :term:`reference` to the other.

        .. seealso:: :term:`graph`.

    cons (1)

        In :term:`Lisp`, ``cons`` is a primitive operation creating a
        list element (from English "CONStruct"). By extension, a
        *cons* is the element created.

        .. link::

            `Function CONS in the Common Lisp HyperSpec <http://www.lispworks.com/documentation/lw60/CLHS/Body/f_cons.htm>`_.

    cons (2)

        .. see:: :term:`allocate`.

    conservative garbage collection

        In conservative :term:`garbage collection`, the layout of
        :term:`objects` and :term:`roots` is not
        known, instead the :term:`collector (1)` assumes that any
        field that looks like a :term:`pointer` *might* be a
        :term:`reference`.

        Conservative collectors can work with programs where
        information about the :term:`memory (2)` layout is not
        available, because, for example, the language doesn't support
        :term:`garbage collection`.

        A conservative collector doesn't need to know the
        :term:`format` of the objects, it just needs some idea of
        where the object boundaries are. It regards any field value
        that looks like a pointer to an object (or, sometimes, into
        the middle of one), as preventing the :term:`recycling
        <recycle>` of that object. It can't :term:`move <moving
        garbage collector>` objects, because then the references to
        the moved objects would need to be updated, and such
        :term:`ambiguous references` must not be modified, in case
        they weren't pointers after all. Therefore, conservative
        collectors are usually :term:`mark-sweep collectors
        <mark-sweep>`.

        Because references are ambiguous, some objects may be retained
        despite being actually :term:`unreachable`. In practice, this
        happens rarely, and refinements such as :term:`black-listing
        <blacklisting>` can further reduce the odds.

        .. opposite:: :term:`exact garbage collection`.

        .. seealso:: :term:`ambiguous root`, :term:`interior pointer`, :term:`semi-conservative garbage collection`.

        .. bibref:: :ref:`Boehm & Weiser (1988) <BW88>`, :ref:`Boehm (1993) <BOEHM93>`.

    constant root

        .. mps:specific::

            A :term:`root` that the :term:`client program` promises
            not change after it is registered, by specifying the
            :term:`root mode` :c:macro:`MPS_RM_CONST` when calling a
            registration function such as :c:func:`mps_root_create`.

    constructor (1)

        A constructor is a function or method that :term:`allocates` and initializes an :term:`object`.

        .. opposite:: :term:`destructor (1)`.

    constructor (2)

        In :term:`C++`, a *constructor* is a member function that is
        used to initialize a newly-:term:`allocated` object.

        The actual allocation of :term:`memory (2)` is performed by
        ``operator new`` or the compiler (for :term:`static <static
        allocation>` and :term:`stack allocation`), and the new
        :term:`block` is then passed to the appropriate constructor.

        .. seealso:: :term:`destructor (2)`.

    continuation

        A continuation is the data required to restore an execution
        context after invocation of another context, typically as a
        subroutine.

        .. relevance::

            If continuations can be represented as first-class
            objects, as in :term:`Scheme`, the execution contexts can
            no longer be stored on a :term:`stack`, instead, (at least
            some) :term:`activation records` have
            to be :term:`heap-allocated <heap allocation>`.

        .. seealso:: :term:`closure`.

    control stack

        .. aka:: *activation stack*, *execution stack*.

        A :term:`stack` that stores :term:`activation records`, particularly subroutine return
        information, is known as a *control stack*.

        Typically the control stack is supported and used by the
        hardware architecture and the operating system, limiting the
        types and sizes of :term:`objects` that can be stored
        on it. Often, only one type of object, a :term:`stack frame`,
        is permitted, and the layout of that is defined by the
        hardware architecture.

        .. relevance::

            Theoretically, a control stack is simply an array of
            activation records, and hence just another object managed
            by the :term:`memory manager`. In practice, the control
            stack is central to the performance of the hardware
            architecture and may require special treatment. In
            particular, it may not be accessible as ordinary
            :term:`memory (2)`, or it may have its own :term:`cache
            (2)` with specific updating requirements.

        .. similar:: :term:`stack`.

        .. seealso:: :term:`cold end`, :term:`data stack`, :term:`hot end`.

    cool

        .. mps:specific::

            A :term:`variety` in which most MPS functions
            :term:`assert <assertion>` that their data structures are
            valid, even functions on the :term:`critical path`. See
            :ref:`guide-build`. Compare :term:`hot` and :term:`rash`.

    copying garbage collection

        .. aka:: *scavenging garbage collection*.

        Copying garbage collection is a kind of :term:`tracing garbage
        collection` that operates by :term:`relocating <relocation>`
        :term:`reachable` :term:`objects` (this is sometimes called
        *scavenging*) and then :term:`reclaiming <reclaim>` objects
        that are left behind, which must be :term:`unreachable` and
        therefore :term:`dead`.

        A copying garbage collection relies on being able to find and
        correct all :term:`references` to copied objects.

        .. figure:: ../diagrams/copying.svg
            :align: center
            :alt: Diagram: Copying garbage collection.

            Copying garbage collection.

        .. similar:: :term:`moving <moving garbage collector>`.

        .. seealso:: :term:`broken heart`, :term:`forwarding pointer`, :term:`two-space collector`.

        .. mps:specific::

            The :ref:`pool-amc` pool class implements copying garbage
            collection (more precisely, :term:`mostly-copying garbage
            collection`).

    core

        A historical synonym for :term:`main memory`, deriving from
        the *cores* or ferrite rings which were once the main
        technology used to implement it.

        .. similar:: :term:`main memory`.

    creation space

        In :term:`generational garbage collection`, when
        :term:`generations` are divided into
        :term:`buckets`, the creation space is where new
        :term:`objects` are created in each generation.

        This term is sometimes used as a synonym for :term:`nursery space`.

        .. opposite:: :term:`aging space`.

        .. seealso:: :term:`generational garbage collection`.

    critical path

        .. mps:specific::

            The sequence of operations on which the MPS spends the
            majority of its time, consisting of :term:`scanning
            <scan>`, :term:`fixing <fix>`, :term:`marking` and
            :term:`copying <copying garbage collection>`. See
            :ref:`design-critical-path`.

    crossing map

        Where :term:`memory (2)` has already been divided into some
        fixed-sized unit (for example, :term:`pages` or
        :term:`cards`), a crossing map records where
        :term:`objects` lie across the boundaries of the
        fixed-sized units. In other words, which fixed-sized units do
        not start with the beginning of an object.

        A system which implements :term:`remembered sets` by
        :term:`page marking` or :term:`card marking` needs to scan all
        the :term:`pointers` in the page or card. If the system can
        not :term:`scan` partial objects (or requires information in
        the object :term:`header <in-band header>` in order to scan a
        partial object), a crossing map is necessary to find the
        beginning of the first object in the unit.

        .. relevance::

            In a sense, a crossing map is an optimization of
            :term:`tagged architecture`. It represents the minimum
            information necessary to determine how to interpret any
            word of memory.

    cyclic data structure

        A data structure is cyclic if some of its :term:`references`
        form a loop; that is, there's an :term:`object` that can be
        reached by following references from itself.