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
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
.. _glossary-s:

=============================
Memory Management Glossary: S
=============================

.. include:: alphabet.txt

.. glossary::

    sbrk

        ``sbrk`` is a Unix library function that adjusts the limit of
        the data segment; this limit is known as the *break*.

        ``sbrk`` and its companion :term:`brk` are obsolete on Unix
        systems that support :term:`virtual memory`.

        ``sbrk`` returns the previous value of the break, so
        ``sbrk(0)`` was a common idiom for getting the current value.

    scalar data type

        A scalar data type is a type that is representable in a single
        dimension and whose objects have only magnitude as value.

        Examples of scalar data types include: integers,
        floating-point numbers, enumerations, and characters.

        .. relevance::

            The objects of a scalar data type are :term:`leaf
            objects`. Scalar data types with bounded magnitude can be
            represented compactly using :term:`value objects`.

        .. historical::

            Because compact representation solves many memory
            management issues, many older programming languages only
            offered bounded scalar data types. For example, the
            ``int`` type in :term:`C` is defined to have a magnitude
            that can be represented by a :term:`word`.

        .. seealso:: :term:`algebraic data type`, :term:`leaf object`, :term:`value object`, :term:`vector data type`.

    scan

        The examination of an :term:`object` or an area of
        :term:`memory (2)` to find :term:`references`,
        typically as part of :term:`tracing <trace>`.

        Scanning examines memory that has been decided to be
        non-:term:`garbage`, to find references to objects that have
        been :term:`condemned <condemned set>`.

        .. mps:specific::

            See :ref:`topic-scanning`.

    scan method

        .. mps:specific::

            A function that examines a block of memory to find
            :term:`references` and indicate them to the
            MPS. A scan method forms part of an :term:`object format`.
            See :c:type:`mps_fmt_scan_t`.

    scan state

        .. mps:specific::

            A scan state represents the state of the current
            :term:`scan`. The MPS passes a scan state to the
            :term:`scan method` of an :term:`object format` when it
            needs to :term:`scan` for :term:`references`
            within a region of memory. Scan states belong to the type
            :c:type:`mps_ss_t`.


    scavenging garbage collection

        .. see:: :term:`copying garbage collection`.

    SDRAM

        Synchronous Dynamic Random Access Memory. A high performance
        variant of :term:`DRAM <dynamic memory>`.

        SDRAM uses an external clock signal to synchronize its data
        input and output. It is capable of achieving very high data
        rates for linear access to memory.

    segmentation violation

        A segmentation violation occurs when an attempt is made to
        access :term:`memory (2)` whose :term:`address` is
        well-formed, but to which access cannot be granted. This might
        be due to either a :term:`protection fault` or an
        :term:`invalid page fault`.

        The term is sometimes used more loosely as a synonym for any
        memory access error, including a :term:`bus error`.

        .. similar:: :term:`general protection fault`, :term:`read fault`, :term:`write fault`.

    segmented addressing

        In segmented addressing, :term:`addresses` are in
        two parts: a segment identifier and an offset into that
        segment.

        Each segment has a base address and a limit. If the offset is
        greater than the limit, the address is invalid (see
        :term:`segmentation violation`). Otherwise, the offset is
        added to the segment's base address, giving the unsegmented
        address. Segment identifiers may be implicit; for instance,
        they may be obtained from a *current segment* register.

        Segmentation may be layered on top of :term:`virtual memory`,
        in which case the unsegmented address is a :term:`virtual
        address`, or not, in which case it is a :term:`physical
        address`.

        Note that, in segmented architectures, you can have a
        two-dimensional :term:`address space`.

        Segments are a feature of some processor architectures and
        operating systems. This description does not cover all
        possible variations on segmentation.

        .. historical::

            Segment terminology may be used on unsegmented systems for
            historical reasons. For instance, Unix processes have
            *text segments*, even when running on an unsegmented
            system.

        .. opposite:: :term:`linear addressing`.

    segregated allocation cache

        .. mps:specific::

            A mechanism for adding a :term:`segregated free list` to a
            :term:`manual <manual memory management>` :term:`pool
            class`. See :ref:`topic-cache`.

    segregated fit

        One of the :term:`segregated free list` class of
        :term:`allocation mechanisms`. There is
        an array of :term:`free lists`, each holding
        :term:`free blocks` of a particular range of
        sizes. The :term:`allocator` identifies the appropriate free
        list and allocates from it (often using a :term:`sequential
        fit` mechanism such as :term:`first fit`). If this fails, a
        larger block is taken from another list and split.

        The details of the mechanism depend on the division of sizes
        between free lists. See :term:`exact segregated fit` and
        :term:`strict segregated fit`.

        This implements a :term:`good fit` :term:`allocation policy`.

        .. seealso:: :term:`allocation mechanism`, :term:`exact segregated fit`, :term:`free list`, :term:`segregated free list`, :term:`strict segregated fit`.

        .. bibref:: :ref:`Wilson et al. (1995) <WIL95>`.

    segregated free list
    segregated free-list

        A class of :term:`allocation mechanism` which divides the
        :term:`free list` into several subsets, according to the size
        of the :term:`free blocks`. A :term:`freed <free
        (1)>` or :term:`coalesced <coalesce>` block is placed on the
        appropriate list. An allocation request is serviced from the
        appropriate list.

        This class of mechanism implements a :term:`good fit` or
        :term:`best fit` policy.

        Variations within this class include :term:`simple segregated
        storage`, :term:`segregated fit`, and :term:`buddy systems`.

        .. bibref:: :ref:`Wilson et al. (1995) <WIL95>`.

        .. mps:specific::

            :term:`Segregated allocation caches` are a general
            mechanism for adding a segregated free list to any
            manually managed pool. See :ref:`topic-cache`.

    semi-conservative garbage collection

        .. aka:: *mostly-exact garbage collection*, *mostly-precise garbage collection*.

        A variant of :term:`conservative garbage collection` which
        deals with :term:`exact references` as well
        as :term:`ambiguous references`.

        For example, references from the :term:`root set` might be
        ambiguous, but :term:`objects` on the :term:`heap`
        might be fully described and precisely :term:`scanned <scan>`.

        .. seealso:: :term:`mostly-copying garbage collection`.

        .. bibref:: :ref:`Bartlett (1988) <BARTLETT88>`.

    semi-space

        When an area of :term:`memory (2)` is divided into two parts
        for the purposes of :term:`copying garbage collection`, the
        parts are known as *semi-spaces*, or sometimes just *spaces*.

        Each semi-space is a contiguous area of memory. Semi-spaces
        are usually used for :term:`two space collection <two-space
        collector>`, but can be used for :term:`generational
        collection <generational garbage collection>`.

        The semi-space where :term:`objects` reside at the start of
        the collection is known as the :term:`fromspace`; the
        :term:`tospace` is where objects will reside, and where new
        objects will be :term:`allocated`, when the collection is
        complete.

        .. seealso:: :term:`two-space collector`.

    semi-space collector

        .. see:: :term:`two-space collector`.

    sequential fit

        A class of :term:`allocation mechanisms` that maintain the
        :term:`free list` as a single linear list of :term:`free
        blocks` (a :term:`free block chain`). Sequential fit
        mechanisms include :term:`first fit` and :term:`next fit`.

        To quote :ref:`Wilson et al. (1995) <WIL95>`:

            The list is often doubly-linked and/or circularly linked.
            Typically, sequential fit algorithms use Knuth's boundary
            tag technique, and a doubly-linked list to make
            :term:`coalescing <coalesce>` simple and fast. […] In
            considering sequential fits, it is probably most important
            to keep strategy and policy issues in mind. The classic
            linear-list implementations may not scale well to large
            :term:`heaps`, in terms of time costs; as the
            number of free blocks grows the time to search the list
            may become unacceptable. More efficient and scalable
            techniques are available, using totally or partially
            ordered trees, or :term:`segregated fits`.

        .. seealso:: :term:`bitmapped fit`, :term:`indexed fit`.

    sequential store buffer

        .. aka:: *SSB*.

        A sequential store buffer is a technique for dividing the cost
        of a :term:`write barrier` by remembering which
        :term:`objects` are modified and updating :term:`remembered
        sets` (and so on) at a later stage.

        This turns out to be extremely efficient on pipelined
        architectures with branch prediction.

    shared memory

        :term:`Memory locations` are *shared* if
        they are in the range of multiple :term:`address spaces`.

    simple object

        In the :term:`PostScript` language, *simple objects* are the
        :term:`unboxed` objects.

        Unlike a :term:`composite object`, a simple object contains
        all its data in the object itself.

        .. similar:: :term:`unboxed`.

        .. opposite:: :term:`composite object`.

    simple segregated storage

        A :term:`segregated free list` :term:`allocation mechanism`
        which divides :term:`memory (1)` into :term:`pages` or
        other areas and only allocates :term:`objects` of a
        single size, or small range of sizes, within each area. This
        makes allocation fast and avoids :term:`headers <in-band
        header>`, but may lead to high :term:`external fragmentation`,
        as unused parts of areas cannot be reused for other object
        sizes.

        .. bibref:: :ref:`Wilson et al. (1995) <WIL95>`.

    size

        .. mps:specific::

            The term *size* in the documentation always refers to a
            size that is measured in :term:`bytes (1)`. The term
            *count* is used for the number of elements in an array.

    size class

        .. mps:specific::

            A :term:`segregated allocation cache` maintains a reserve
            of free :term:`blocks` in a set of :term:`sizes`: each
            such size is known as a *size class*. When creating a
            segregated allocation cache by calling
            :c:func:`mps_sac_create`, the :term:`client program`
            describes the desired set of size classes by passing an
            array of structures of type :c:type:`mps_sac_class_s`. See
            :ref:`topic-cache`.

    skip method
    
        .. mps:specific::

             A :term:`format method` that returns the address of the
             "next object" in a block of :term:`formatted objects`. See :c:type:`mps_fmt_skip_t`.

    smart pointer

        A smart pointer is an instance of a :term:`C++` class that
        encapsulates a :term:`pointer` and performs :term:`reference
        counting`.

        By overloading certain operators it is possible for the class
        to present the illusion of being a pointer, so that
        ``operator*``, ``operator->``, etc. can be used as normal.
        Reference counting allows the objects that are referred to
        using the smart pointer class to have their :term:`memory (1)`
        automatically :term:`reclaimed` when they are no longer
        :term:`referenced`. It is a common technique used when trying
        to solve :term:`memory management` problems in C++
        applications.

        However, reference counting is not always an appropriate
        memory management technique and smart pointers can be hard to
        implement properly in C++. A :term:`tracing garbage collector
        <tracing garbage collection>` might be worth considering.

        .. bibref:: :ref:`Edelson (1992a) <EDELSON92A>`.

    snap-out

        .. aka:: *transport snap-out*.

        In a :term:`copying collector <copying garbage collection>`,
        when there is a :term:`reference` to an :term:`object` that
        was :term:`condemned <condemned set>`, but has been
        :term:`transported`, snap-out is the adjustment of that
        reference to point to the preserved copy.

        Typically the first transport leaves a :term:`forwarding
        pointer` that enables the snap-out.

        .. figure:: ../diagrams/snap-out.svg
            :align: center
            :alt: Diagram: Snap-out.

            Snap-out.

        .. seealso:: :term:`broken heart`.

    snapshot at the beginning

        Snapshot-at-the-beginning algorithms for :term:`tracing
        <trace>`, :term:`incremental GC <incremental garbage
        collection>` note changes made by the :term:`mutator` to the
        :term:`graph` of :term:`objects` and update the
        :term:`collector (2)` state to make it trace relevant
        :term:`edges` that the mutator deletes.

        In order for the collector to miss a :term:`reachable`
        :term:`object`, the following two conditions need to hold at
        some point during tracing:

        1. The mutator stores a :term:`reference` to a :term:`white`
           object into a :term:`black` object.

        2. All paths from any :term:`gray` objects to that white
           object are destroyed.

        Snapshot-at-the-beginning algorithms ensure the second
        condition cannot occur, by causing the collector to process
        any reference that the mutator overwrites and that might be
        part of such a path.

        They are so called because they keep track of references that
        existed at the beginning of the :term:`collection cycle`. Note
        that this does not mean all modifications need to be seen by
        the collector, only those needed to complete tracing without
        missing a reachable object (see :ref:`Pirinen (1998)
        <PIRINEN98>` for details), nor does it mean that it won't
        trace some references created during the collection.

        .. historical::

            This distinction between incremental update and
            snapshot at the beginning was first introduced for
            write-barrier algorithms, but it applies to any type of
            tracing algorithm.

        .. opposite:: :term:`incremental update`.

        .. seealso:: :term:`barrier (1)`, :term:`tri-color marking`, :term:`weak tri-color invariant`.

        .. bibref:: :ref:`Wilson (1994) <WIL94>`, :ref:`Pirinen (1998) <PIRINEN98>`.

    soft reference

        In :term:`Java` terminology, *soft reference* is used to mean
        a :term:`reference` encapsulated in a :term:`reference object`
        of class ``SoftReference``.

        Soft references form one of three kinds of :term:`weak
        reference (1)` in Java. They are handy for building
        :term:`caches (3) <caching (3)>` that are automatically
        flushed when memory is low.

        .. seealso:: :term:`softly reachable`.

        .. link::

            `Class java.lang.ref.SoftReference <http://docs.oracle.com/javase/8/docs/api/java/lang/ref/SoftReference.html>`_, `Reference Objects and Garbage Collection <http://pawlan.com/monica/articles/refobjs/>`_.

    softly reachable

        In :term:`Java`, an object is *softly reachable* if it is not
        :term:`strongly reachable` and there is a path from the
        :term:`roots` to it that contains at least one
        :term:`soft reference` but no :term:`weak (2) <weak reference
        (2)>` or :term:`phantom references`.

        When the Java :term:`collector (1)` determines that an object
        is softly reachable, it has the option of clearing the soft
        references involved, which will usually allow the object to be
        :term:`recycled`. The idea is that they will only be cleared
        if the process is running short of :term:`memory (2)`. If it
        is done, all soft references involved are cleared, so that the
        object is no longer softly reachable, and any affected
        :term:`reference objects` which are registered with a queue
        are enqueued.

        .. seealso:: :term:`phantom reachable`, :term:`reachability <reachable>`, :term:`weakly reachable`.

        .. link::

            `Class java.lang.ref.SoftReference <http://docs.oracle.com/javase/8/docs/api/java/lang/ref/SoftReference.html>`_, `Reference Objects and Garbage Collection <http://pawlan.com/monica/articles/refobjs/>`_.

    space leak

        .. see:: :term:`memory leak`.

    spare commit limit

        .. mps:specific::

            The spare commit limit is a limit on the :term:`spare
            committed memory` that the MPS will obtain from the
            operating system. It can be retrieved by calling
            :c:func:`mps_arena_spare` and changed by
            calling :c:func:`mps_arena_spare_set`.

    spare committed memory

        .. mps:specific::

            Memory which is not in use by any :term:`pool` and not
            otherwise in use for internal MPS data structures, but
            which remains :term:`committed <mapped>` (mapped to
            :term:`RAM` by the operating system). It is used by the
            :term:`arena` to (attempt to) avoid calling the operating
            system to repeatedly map and unmap areas of :term:`virtual
            memory` as the amount of memory in use goes up and down.
            It is subject to the :term:`spare commit limit`. The total
            spare committed memory can be retrieved by calling
            :c:func:`mps_arena_spare_committed`.

    spaghetti stack

        .. see:: :term:`cactus stack`.

    splat

        .. mps:specific::

            To overwrite a :term:`weak reference (1)` with a null
            pointer, when the MPS has determined that there are no
            remaining :term:`strong references` to the block referred
            to. See :ref:`topic-weak`.

    split

        To divide a :term:`free block` into two smaller free blocks in
        the process of satisfying an allocation request.

        Deciding when to split a block is an important aspect of an
        :term:`allocation policy`.

        .. opposite:: :term:`coalesce`.

        .. seealso:: :term:`allocation policy`, :term:`coalesce`, :term:`free block`.

    SRAM

        .. see:: :term:`static memory (1)`.

    SSB

        .. see:: :term:`sequential store buffer`.

    stack

        A stack is a LIFO (last in, first out) collection:
        :term:`objects` may be *pushed* onto the stack, and
        *popped* off it in reverse order of pushing.

        When people say "the stack", they usually mean the
        :term:`control stack` supported by the OS and/or the
        processor.

        .. relevance::

            :term:`Stack allocation` is an important technique.
            Control stacks are central to the performance of the
            system and often require special handling.

        .. historical::

            The terms "stack", "push", and "pop" are taken from the
            spring-loaded dish stack found in cafeterias and salad
            bars where removing the top plate causes the others to
            rise up, exposing the next one, and adding a plate causes
            the spring to compress, leaving only that plate
            accessible.

        So originally, the latest item was the "top", "down the stack"
        meant towards earlier items, and "up" towards later ones, but
        today many use "up" and "down" in the opposite sense.

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

        .. seealso:: :term:`cactus stack`, :term:`data stack`.

    stack allocation

        *Stack allocation* means run-time :term:`allocation
        <allocate>` and :term:`deallocation <free (1)>` of
        :term:`memory (1)` in last-in/first-out order.

        Typically, stack allocation is performed on top of the main
        :term:`stack`, but one can have a separate :term:`data stack`
        for this purpose as well, as in Forth, or even multiple ones,
        as in the :term:`PostScript` language.

        Allocation and deallocation are typically fast, since they can
        be done simply by adding or subtracting the size of the
        :term:`block` from the stack pointer.

        Using only stack allocation, without heap allocation, is
        somewhat restrictive, as only objects whose size is known at
        compile-time can be returned from a procedure.

        Some programming languages (such as some versions of
        :term:`Lisp` and :term:`C`) provide program-controlled stack
        :term:`allocation <allocate>` and :term:`deallocation <free
        (1)>` of dynamic extent objects for efficiency, despite its
        being unsafe.

        .. similar:: :term:`automatic storage duration`.

        .. opposite:: :term:`heap allocation`, :term:`static allocation`.

        .. seealso:: :term:`dynamic extent`, :term:`region inference`.

    stack frame

        .. aka:: *stack record*.

        A stack frame or record is an :term:`activation record` that
        is stored on the :term:`stack`.

        In a register-based architecture, where the current activation
        record may be partially stored in registers, there may be
        hardware instructions that facilitate storing registers on the
        stack when another activation record is made current. Such
        instructions may prescribe a particular layout for activation
        records.

        .. relevance::

            Hardware support for saving and restoring registers, for
            stacks and for stack addressing may limit or otherwise
            prescribe the size and type of data that can be stored in
            a stack frame. Knowledge of the layout of each stack frame
            may assist a :term:`garbage collector` in finding
            :term:`roots`.

        .. similar:: :term:`activation record`.

        .. seealso:: :term:`stack`.

    stack record

        .. see:: :term:`stack frame`.

    static allocation

        *Static allocation* means :term:`allocation <allocate>` of
        :term:`memory (1)` before the program starts and retention
        until the end.

        The locations of :term:`objects` are basically
        decided at compile-time, although they might be
        :term:`relocated <relocation>` at load-time. This implies the
        sizes of the objects must be known then.

        Using only static allocation is restrictive, as sizes of data
        structures can't be dynamically varied, and procedures cannot
        be recursive. However, it is also fast and eliminates the
        possibility of running out of memory. For this reason, this
        scheme is sometimes used in real-time systems.

        .. similar:: :term:`static storage duration`.

        .. opposite:: :term:`heap allocation`, :term:`stack allocation`.

        .. seealso:: :term:`region inference`, :term:`static memory (2)`.

    static memory (1)

        .. aka:: *SRAM*, *static RAM*.

        Static :term:`memory (2)` or static RAM (SRAM) is a type of
        :term:`physical memory (2)` that does not need to be refreshed
        periodically to avoid losing state.

        Static memory is typically faster than :term:`dynamic memory`,
        or requires essentially no power to preserve its state, but
        rarely both. These benefits result in static RAM being used
        for :term:`cache (1)` memory, and also in portable, low-power
        applications (such as PDAs). It is, however, more expensive
        than dynamic RAM and requires more transistors, making dynamic
        RAM the choice for large amounts of memory (the :term:`main
        memory` of desktop machines, for example).

        .. opposite:: :term:`dynamic memory`.

    static memory (2)

        The :term:`memory (2)` where :term:`statically allocated
        <static allocation>` objects are stored is sometimes known as
        *static memory*. In the context of :term:`garbage collection`,
        the term is used mean memory used to store :term:`static
        objects`.

        .. seealso:: :term:`static storage duration`.

    static object

        A static :term:`object` is non-:term:`moving <moving garbage
        collector>`. That is, it is not :term:`relocated <relocation>`
        by a :term:`memory manager`; its :term:`address` does not
        change.

    static RAM

        .. see:: :term:`static memory (1)`.

    static storage duration

        In :term:`C` and :term:`C++`, the ``static`` keyword applied
        to a file scope variable or function means it is local to the
        file; the ``static`` keyword applied to a function or a block
        scope variable means it is :term:`allocated` and initialized
        once only.

        Objects declared locally in blocks with the ``static`` keyword
        are :term:`allocated` in :term:`static memory (2)`, and
        initialized once (usually by the compiler/linker) instead of
        each time the block is entered.

        Static variables within functions retain their value between
        function invocations, and therefore must form part of the
        :term:`root set` of any :term:`collector (1)`.

        .. opposite:: :term:`automatic storage duration`.

        .. seealso:: :term:`lifetime`.

    stepper function

        .. aka:: *visitor function*.

        .. mps:specific::

            A function that will be called on each element in a
            collection. For example, a stepper function of type
            :c:type:`mps_roots_stepper_t` can be passed to
            :c:func:`mps_arena_roots_walk` and it will be called on
            all :term:`roots` in an :term:`arena`.

    sticky reference count

        .. see:: :term:`limited-field reference count`.

    stop-and-copy collection

        :term:`Copying garbage collection` that stops the
        :term:`mutator` while the collector runs.

        .. figure:: ../diagrams/two-space.svg
            :align: center
            :alt: Diagram: Two-space collector.

            Stop-and-copy in a :term:`two-space collector`.

        .. opposite:: :term:`incremental garbage collection`, :term:`parallel garbage collection`.

    storage

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

    storage hierarchy

        .. aka:: *memory hierarchy*.

        A typical computer has several different *levels* of
        :term:`storage <memory (1)>`. Each level of storage has a
        different speed, cost, and size. The levels form a *storage
        hierarchy*, in which the topmost levels (those nearest the
        processor) are fastest, most expensive and smallest.

        Levels typically include processor :term:`registers`, possibly some levels of :term:`cache (1)`,
        :term:`main memory`, and possibly some levels of
        :term:`backing store`.

        Each level is commonly used as a :term:`cache (2)` for the
        next level. For instance, :term:`virtual memory` systems
        use main memory as a cache for backing store.

        .. figure:: ../diagrams/storage.svg
            :align: center
            :alt: Diagram: Storage hierarchy with (typical) relative cost, speed, and size.

            Storage hierarchy with (typical) relative cost, speed, and
            size.

    storage level

        One level in a :term:`storage hierarchy`, for instance a
        :term:`cache (1)`, :term:`main memory`, :term:`backing store`,
        and so on.

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

    storage management

        .. see:: :term:`memory management`.

    store (1)

        To transfer data from a processor's :term:`registers` to :term:`memory (2)`.

        Store can also be used in the more general sense of
        transferring data from a part of the :term:`memory hierarchy`
        that is fast to access to one that is slow to access.

        ``STORE`` (or an abbreviation) is also commonly used in many
        processor architectures as the mnemonic for the machine code
        instructions that store data into memory.

        .. opposite:: :term:`load`.

    store (2)

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

    stretchy vector

        A :term:`vector <vector data type>` that may grow or shrink to
        accommodate adding or removing elements. Named after the
        ``<stretchy-vector>`` abstract class in Dylan.

        .. relevance::

            In the presence of an :term:`asynchronous garbage
            collector`, the vector and its size may need to be updated
            atomically.

        .. link::

            `Dylan Reference Manual: Collections <http://opendylan.org/books/drm/Collection_Classes>`_.

        .. mps:specific::

            See :ref:`guide-stretchy-vector`.

    strict segregated fit

        A :term:`segregated fit` :term:`allocation mechanism` which
        has only one block size on each :term:`free list`. A requested
        block size is rounded up to the next provided size, and the
        first block on that list is returned. The sizes must be chosen
        so that any block of a larger size can be :term:`split` into a
        number of smaller sized blocks. :term:`Buddy systems <buddy
        system>` are a special case of strict segregated fit
        allocators.

        .. seealso:: :term:`allocation mechanism`, :term:`buddy system`, :term:`segregated fit`, :term:`segregated free list`.

        .. bibref:: :ref:`Wilson et al. (1995) <WIL95>`.

    strong reference

        In a :term:`tracing garbage collector <tracing garbage
        collection>`, a strong reference is a :term:`reference` that
        keeps the :term:`object` it refers to :term:`alive <live>`.

        A strong reference is the usual sort of reference: the term is
        usually used to draw a contrast with :term:`weak reference
        (1)`.

        .. opposite:: :term:`weak reference (1)`.

        .. seealso:: :term:`strong root`.

    strong root

        A strong root is a :term:`root` such that all
        :term:`references` in it are :term:`strong references`.

        A strong root is the usual sort of root: the term is usually
        used to draw a contrast with :term:`weak root`.

        .. opposite:: :term:`weak root`.

        .. mps:specific::

            Strong roots have :term:`rank` :c:func:`mps_rank_ambig` or
            :c:func:`mps_rank_exact`.

    strong tri-color invariant
    strong tri-colour invariant
    strong tricolor invariant
    strong tricolour invariant

        The strong :term:`tri-color invariant` is the property of a
        :term:`reference` :term:`graph` that there is no :term:`edge`
        from a :term:`black` :term:`node` to a :term:`white` node.

        By preserving this property throughout :term:`tri-color
        marking`, a :term:`tracing <trace>` algorithm can ensure that
        the :term:`collector (2)` will not miss reachable objects,
        even if the :term:`mutator` manipulates the graph during the
        collection. This invariant can also be used to ensure that a
        :term:`copying garbage collector <copying garbage collection>`
        doesn't confuse the mutator. Mutator actions might need to
        change the :term:`color` of the nodes affected in order to
        preserve the invariant.

        Algorithms using this invariant are :term:`incremental update`
        algorithms.

        .. similar:: :term:`tri-color invariant`.

        .. seealso:: :term:`barrier (1)`, :term:`weak tri-color invariant`.

        .. bibref:: :ref:`Johnstone (1997) <JOHNSTONE97>`, :ref:`Pirinen (1998) <PIRINEN98>`.

    strongly reachable

        In :term:`Java`, an object is *strongly reachable*, if there
        is a path from the :term:`roots` to it that contains
        only :term:`strong references`, that is,
        contains no :term:`reference objects`.

        .. seealso:: :term:`phantom reachable`, :term:`reachability <reachable>`, :term:`softly reachable`, :term:`weakly reachable`.

        .. link::

            `Reference Objects and Garbage Collection <http://pawlan.com/monica/articles/refobjs/>`_.

    suballocator

        A *suballocator* is an :term:`allocator` functioning on top of
        another allocator.

        Suballocators work by :term:`allocating <allocate>` large
        :term:`blocks` and :term:`splitting <split>` them for
        use, or by :term:`recycling <recycle>` blocks locally.

        Application programmers sometimes write their own
        suballocators when faced with an inefficient or inadequate
        :term:`memory manager`. Suballocators can take advantage of
        special knowledge of program behavior, but are less efficient
        in general than fixing the underlying allocator, mainly
        because :term:`memory management` is a *global* issue for an
        application, and a global strategy can make a big difference.
        For example, different suballocators can interact
        catastrophically with each other and with the :term:`virtual
        memory` system, causing the application's memory
        requirements to grow unnecessarily due to
        :term:`fragmentation`.

    subgraph

        A subgraph S of a :term:`graph` G is a graph such that all the
        :term:`nodes` in S are also in G and all the
        :term:`edges` in S are also in G; that is, it is a part
        of a graph.

    superpage

        .. see:: :term:`huge page`.

    sure reference

        .. see:: :term:`exact reference`.

    swap space

        :term:`Backing store` used by a :term:`swapping` system.

        .. seealso:: :term:`backing store`, :term:`swapping`.

    swapped in

        A process or :term:`page` is *swapped in* if it is available
        in :term:`physical memory (1)`. This usually applies to the
        entire program image.

        .. similar:: :term:`paged in`.

        .. opposite:: :term:`swapped out`.

        .. seealso:: :term:`swapping`.

    swapped out

        A process or :term:`page` is *swapped out* if it is not
        available in :term:`physical memory (1)`. This usually applies
        to the entire program image.

        .. similar:: :term:`paged out`.

        .. opposite:: :term:`swapped in`.

        .. seealso:: :term:`swapping`.

    swapping

        Historically, swapping was the technique of moving entire
        program images to disk (or drum) and back into :term:`physical
        memory (1)`, an early form of :term:`virtual memory`.
        Nowadays, it is used as a synonym for :term:`paging`.

        .. similar:: :term:`paging`.

        .. seealso:: :term:`swapped in`, :term:`swapped out`.

    sweeping

        Sweeping is the second phase ("the sweep phase") of the
        :term:`mark-sweep` algorithm. It performs a sequential
        (address-order) pass over memory to :term:`recycle` unmarked
        blocks.

        Sweeping typically gathers all unmarked blocks into one or
        more :term:`free lists`.

        .. seealso:: :term:`marking`.

    synchronous garbage collector

        A :term:`collector (2)` is asynchronous with respect to the
        :term:`mutator` if it runs at predictable times, for example
        only when a collection function is called.

        This means that mutator need not ensure that :term:`formatted
        objects` are always :term:`scannable <scan>`, as long as it
        makes them scannable before the collector runs.

        .. opposite:: :term:`asynchronous garbage collector`.