3143. monotonic_buffer_resource growth policy is unclear

Section: 20.4.6 [mem.res.monotonic.buffer] Status: C++23 Submitter: Jonathan Wakely Opened: 2018-07-20 Last modified: 2023-11-22

Priority: 2

View all issues with C++23 status.

Discussion:

During the discussion of LWG 3120 it was pointed out that the current wording in 20.4.6 [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.

[2019-01-20 Reflector prioritization]

Set Priority to 2

[2020-02-13, Prague]

LWG looked at the issue and a suggestion was presented to eliminate most of 20.4.6 [mem.res.monotonic.buffer] to solve the problem the current requirements impose.

[2020-02-16; Prague]

Reviewed revised wording and moved to Ready for Varna.

[2020-11-09 Approved In November virtual meeting. Status changed: Ready → WP.]

Proposed resolution:

This wording is relative to N4849.

1. Modify 20.4.6 [mem.res.monotonic.buffer], as indicated:

   -1- A monotonic_buffer_resource is a special-purpose memory resource intended for very fast memory allocations in situations where memory is used to build up a few objects and then is released all at once when the memory resource object is destroyed. It has the following qualities:

   1. (1.1) — A call to deallocate has no effect, thus the amount of memory consumed increases monotonically until the resource is destroyed.

   2. (1.2) — The program can supply an initial buffer, which the allocator uses to satisfy memory requests.

   3. (1.3) — When the initial buffer (if any) is exhausted, it obtains additional buffers from an upstream memory resource supplied at construction. Each additional buffer is larger than the previous one, following a geometric progression.

   4. (1.4) — It is intended for access from one thread of control at a time. Specifically, calls to allocate and deallocate do not synchronize with one another.

   5. (1.5) — It frees the allocated memory on destruction, even if deallocate has not been called for some of the allocated blocks.