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
.. Sources:

    `<https://info.ravenbrook.com/project/mps/master/design/poolmvt/>`_

.. index::
   single: MVT pool class
   single: pool class; MVT

.. _pool-mvt:

MVT (Manual Variable Temporal)
==============================

**MVT** :term:`manually manages <manual memory management>`
variable-sized, unformatted objects. It uses the :dfn:`temporal fit`
:term:`allocation policy`.


.. index::
   pair: MVT pool class; temporal fit
   single: allocation policy; temporal fit

Temporal fit
------------

Temporal fit attempts to place consecutive allocations next to each
other. It relies on delaying re-use as long as possible to permit freed
blocks to :term:`coalesce`, thus maximizing the number of consecutive
allocations that can be co-located. Temporal fit permits a very fast
allocator and a deallocator competitive in speed with all other known
policies.

Temporal fit is intended to take advantage of knowledge of object
:term:`lifetimes`: either *a priori* knowledge, or knowledge acquired
by profiling. The best performance will be achieved by allocating
objects with similar expected death times together.

A simple policy can be implemented to take advantage of MVT. Object
size is typically well-correlated with object life-expectancy, and
birth time plus lifetime gives death time, so allocating objects of
similar size sequentially from the same pool instance should result in
objects allocated close to each other dying at about the same time.

An application that has several classes of objects of widely differing
life expectancy will best be served by creating a different MVT pool
instance for each life-expectancy class. A more sophisticated policy
can use either the programmer's knowledge of the expected lifetime of
an object, or any characteristic of objects that correlates with
lifetime, to choose an appropriate pool to allocate in.

Allocating objects with unknown or very different death times together
will pessimize the space performance of MVT.


.. index::
   single: MVT pool class; properties

MVT properties
--------------

* Does not support allocation via :c:func:`mps_alloc`.

* Supports allocation via :term:`allocation points` only. If an
  allocation point is created in an MVT pool, the call to
  :c:func:`mps_ap_create_k` takes no keyword arguments.

* Supports deallocation via :c:func:`mps_free`.

* Supports :term:`allocation frames` but does not use them to improve
  the efficiency of stack-like allocation.

* Does not support :term:`segregated allocation caches`.

* There are no garbage collections in this pool.

* Blocks may not contain :term:`references` to blocks in automatically
  managed pools (unless these are registered as :term:`roots`).

* Allocations may be variable in size.

* The :term:`alignment` of blocks is configurable, but may not be
  smaller than ``sizeof(void *)``.

* Blocks do not have :term:`dependent objects`.

* Blocks are not automatically :term:`reclaimed`.

* Blocks are not :term:`scanned <scan>`.

* Blocks are not protected by :term:`barriers (1)`.

* Blocks do not :term:`move <moving garbage collector>`.

* Blocks may not be registered for :term:`finalization`.

* Blocks must not belong to an :term:`object format`.


.. index::
   single: MVT pool class; interface

MVT interface
-------------

::

   #include "mpscmvt.h"

.. c:function:: mps_pool_class_t mps_class_mvt(void)

    Return the :term:`pool class` for an MVT (Manual Variable
    Temporal) :term:`pool`.

    When creating an MVT pool, :c:func:`mps_pool_create_k` accepts six
    optional :term:`keyword arguments`:

    * :c:macro:`MPS_KEY_ALIGN` (type :c:type:`mps_align_t`, default is
      :c:macro:`MPS_PF_ALIGN`) is the :term:`alignment` of the
      addresses allocated (and freed) in the pool. The minimum
      alignment supported by pools of this class is ``sizeof(void *)``
      and the maximum is the arena grain size
      (see :c:macro:`MPS_KEY_ARENA_GRAIN_SIZE`).

    * :c:macro:`MPS_KEY_MIN_SIZE` (type :c:type:`size_t`, default is
      :c:macro:`MPS_PF_ALIGN`) is the
      predicted minimum size of blocks that will be allocated from the
      pool.

    * :c:macro:`MPS_KEY_MEAN_SIZE` (type :c:type:`size_t`, default 32) is the
      predicted mean size of blocks that will be allocated from the
      pool.

    * :c:macro:`MPS_KEY_MAX_SIZE` (type :c:type:`size_t`, default 8192) is the
      predicted maximum size of blocks that will be allocated from the
      pool. Partial freeing is not supported for blocks larger than
      this; doing so will result in the storage of the block never
      being reused.

    The three ``SIZE`` arguments above are *hints* to the MPS: the
    pool will be less efficient if they are wrong, but the only thing
    that will break is the partial freeing of large blocks.

    * :c:macro:`MPS_KEY_MVT_RESERVE_DEPTH` (type
      :c:type:`mps_word_t`, default 1024) is the expected hysteresis
      of the population of the pool. When blocks are freed, the pool
      will retain sufficient storage to allocate this many blocks of the
      mean size for near term allocations (rather than immediately
      making that storage available to other pools).

      If a pool has a stable population, or one which only grows over
      the lifetime of the pool, or one which grows steadily and then
      shrinks steadily, use a reserve depth of 0.

      It is always safe to use a reserve depth of 0, but if the
      population typically fluctuates in a range (for example, the
      client program repeatedly creates and destroys a subset of
      blocks in a loop), it is more efficient for the pool to retain
      enough storage to satisfy that fluctuation. For example, if a
      pool has an object population that typically fluctuates between
      8,000 and 10,000, use a reserve depth of 2,000.

      The reserve will not normally be available to other pools for
      allocation, even when it is not used by the pool. If this is
      undesirable, a reserve depth of 0 may be used for a pool whose
      object population does vary, at a slight cost in efficiency. The
      reserve does not guarantee any particular amount of allocation.

    * :c:macro:`MPS_KEY_MVT_FRAG_LIMIT` (type ``double``, default 0.3)
      may range from 0.0 to 1.0 (inclusive). It sets an upper limit on
      the space overhead of an MVT pool, in case block death times and
      allocations do not correlate well. If the free space managed by
      the pool as a ratio of all the space managed by the pool exceeds
      the fragmentation limit, the pool falls back to a first fit
      allocation policy, exploiting space more efficiently at a cost
      in time efficiency. A fragmentation limit of 0.0 would cause the
      pool to operate as a first-fit pool, at a significant cost in
      time efficiency: therefore this is not permitted.

      A fragmentation limit of 1.0 causes the pool to always use
      temporal fit (unless resources are exhausted). If the objects
      allocated in the pool have similar lifetime expectancies, this
      mode will have the best time- and space-efficiency. If the
      objects have widely varying lifetime expectancies, this mode
      will be time-efficient, but may be space-inefficient. An
      intermediate setting can be used to limit the space-inefficiency
      of temporal fit due to varying object life expectancies.

    For example::

        MPS_ARGS_BEGIN(args) {
            MPS_ARGS_ADD(args, MPS_KEY_MIN_SIZE, 4);
            MPS_ARGS_ADD(args, MPS_KEY_MEAN_SIZE, 32);
            MPS_ARGS_ADD(args, MPS_KEY_MAX_SIZE, 1024);
            MPS_ARGS_ADD(args, MPS_KEY_MVT_RESERVE_DEPTH, 256);
            MPS_ARGS_ADD(args, MPS_KEY_MVT_FRAG_LIMIT, 0.5);
            res = mps_pool_create_k(&pool, arena, mps_class_mvt(), args);
        } MPS_ARGS_END(args);