monotonic_buffer_resource growth policy is unclear
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.

Date User Action Args
2019-01-20 16:20:00adminsetmessages: + msg10290
2018-07-20 00:00:00admincreate