- Title
- monotonic_buffer_resource growth policy is unclear
- Status
- new
- Section
- [mem.res.monotonic.buffer]
- Submitter
- Jonathan Wakely

Created on **2018-07-20.00:00:00**,
last changed **2019-01-20.16:20:00**.

Date: 2019-01-20.00:00:00

*[ 2019-01-20 Reflector prioritization ]*

Set Priority to 2

Date: 2018-07-20.00:00:00

During the discussion of LWG 3120 it was pointed out that the current
wording in [mem.res.monotonic.buffer] is contradictory. The introductory text for
the class says "Each additional buffer is larger than the previous one, following
a geometric progression" but the spec for `do_allocate` doesn't agree.

Firstly, it's impossible for the implementation to ensure a single geometric progression,
because the size of the next buffer can be arbitrarily large. If the caller asks for an
allocation that is `N` times bigger than the previous buffer, the next buffer will be at
least `N` times larger than the previous one. If `N` is larger than the
implementation-defined growth factor it's not a geometric progression.

Secondly, it's not even clear that each additional buffer will be larger than the previous one.
Given a `monotonic_buffer_resource` object with little remaining space in `current_buffer`,
a request to allocate `10*next_buffer_size` will:

"set `current_buffer` to `upstream_rsrc->allocate(n, m)`, where `n` is not
less than `max(bytes, next_buffer_size)` and `m` is not less than `alignment`,
and increase `next_buffer_size` by an implementation-defined growth factor (which need not
be integral), then allocate the return block from the newly-allocated `current_buffer`."

The effects are to allocate a new buffer of at least `max(10*next_buffer_size, next_buffer_size)`
bytes, and then do `next_buffer_size *= growth_factor`. If `growth_factor < 10` then
the next allocated buffer might be smaller than the last one. This means that although
`next_buffer_size` itself follows a geometric progression, the actual size of any single
allocated buffer can be much larger than `next_buffer_size`. A graph of the allocated sizes looks
like a geometric progression with spikes where an allocation size is larger than `next_buffer_size`.

If the intention is to set `next_buffer_size = max(n, next_buffer_size * growth_factor)` so
that every allocation from upstream is larger than the previous one, then we need a change to the
*Effects:* to actually say that. Rather than a geometric progression with anomalous spikes,
this would produce a number of different geometric progressions with discontinuous jumps between them.

If the spiky interpretation is right then we need to weaken the "Each additional buffer is larger" statement. Either way, we need to add a caveat to the "following a geometric progression" text because that isn't true for the spiky interpretation or the jumpy interpretation.

Thirdly, the *Effects:* says that the size of the allocated block, `n`, is not less than
`max(bytes, next_buffer_size)`. This seems to allow an implementation to choose to do
`n = ceil2(max(bytes, next_buffer_size))` if it wishes (maybe because allocating sizes that
are a power of 2 simplifies the `monotonic_buffer_resource` implementation, or allows reducing
the bookkeeping overhead). This still results in an approximate geometric progression (under either
the spiky or jumpy interpretation) but the graph has steps rather than being a smooth curve (but
always above the curve). This is another way that "Each additional buffer is larger than the previous
one" is not guaranteed. Even if `max(bytes, next_buffer_size)` is greater on every call, for a
growth factor between `1.0` and `2.0` the result of `ceil2` might be the same
for two successive buffers. I see no reason to forbid this, but Pablo suggested it's not allowed
because it doesn't result in exponential growth (which I disagree with). If this is supposed to be
forbidden, the wording needs to be fixed to forbid it.

History | |||
---|---|---|---|

Date | User | Action | Args |

2019-01-20 16:20:00 | admin | set | messages: + msg10290 |

2018-07-20 00:00:00 | admin | create |