This is an archive of the discontinued LLVM Phabricator instance.

<experimental/memory_resource>: Implement monotonic_buffer_resource.
AbandonedPublic

Authored by Quuxplusone on May 19 2018, 3:47 PM.

Details

Reviewers
EricWF
mclow.lists
ldionne
Group Reviewers
Restricted Project
Summary

(D47090 included this in <memory_resource>; at Eric's request, I've split this out into its own patch applied to the existing <experimental/memory_resource> instead.)

Depends on D46806 D47109 D47344

Diff Detail

Repository
rCXX libc++

Event Timeline

Quuxplusone retitled this revision from Implement monotonic_buffer_resource in <experimental/memory_resource> to <experimental/memory_resource>: Implement monotonic_buffer_resource..
Quuxplusone added 1 blocking reviewer(s): EricWF.

Fix one visibility macro.

FYI I have a full implementation of this laying around as D27402 (https://reviews.llvm.org/D27402). But I have never taken the time to resolve merge conflicts.
Feel free to steal any of the tests if they're still relevant.

include/experimental/memory_resource
428

I can't imagine we'll need more than 1 byte to represent the alignment.

473

Lets add override to these functions.

src/experimental/memory_resource.cpp
215

Drop the braces for conditionals and loops with single statements.

include/experimental/memory_resource
428

Even assuming for the sake of argument that that's right, it wouldn't buy us anything here because of padding, would it?

At the moment, __alignment_ needs to have enough range to store the align parameter passed to monotonic_buffer_resource::do_allocate. In an SSE world we should not blithely assume that align < 256. We could store lg(align) in a single byte since align is always a power of two and less than 2^64 — but then we're back to the first argument, which is that it'll be padded to 8 bytes anyway so what do we gain.

473

I grepped for "override" in include/ and saw exactly one (accidental?) use in experimental/filesystem, so I thought probably libc++ had a policy not to use it for portability reasons. I'll add it throughout, but would like someone to explicitly confirm that

(A) it's okay to use in this header and wouldn't need to be guarded with a _LIBCPP_OVERRIDE macro or anything

(B) Arthur should not bother trying to add it to any other headers, not even "for consistency"

src/experimental/memory_resource.cpp
215

*shiver* but okay.

235

For reference, here is where we ask the upstream for a block aligned according to the user's align.
It occurs to me that the upstream might not be able to satisfy such a request (actually, new_delete_resource works that way for me because libc++ doesn't support aligned new and delete on OSX), which would make the upstream throw bad_alloc. We handle this by passing along the exception. We could conceivably handle it by retrying with

aligned_capacity += align;
__res_->allocate(aligned_capacity, alignof(max_align_t));
header->__alignment_ = alignof(max_align_t);

but I'm not sure that that's any of monotonic_buffer_resource's business. Happy to make the patch if you think it ought to be.

EricWF added inline comments.May 28 2018, 7:46 PM
include/experimental/memory_resource
427

Can't we determine the capacity in most cases simply using static_cast<char*>(this) - static_cast<char*>(__start_)?

428

Even assuming for the sake of argument that that's right, it wouldn't buy us anything here because of padding, would it?

It could. (A) we don't actually need to include the types trailing padding when tail allocating it as a part of a buffer.
and less importantly (B) I'm not sure all ABI's require the trailing padding of a type be included when that type is a data member of another type (I might just be wrong on this).

I'm also looking into other ways of improving the way your implementation packs data, which may cause this to be beneficial.

473

The header already assumes a full C++11 implementation (it uses std::tuple), the override keyword will bi available. No need for a special macro.

test/std/experimental/memory/memory.resource.monotonic.buffer/monotonic_buffer.pass.cpp
1 ↗(On Diff #148542)

Instead of testing the whole of monotonic_buffer in a single file, this test should be broken up into separate files. Roughly one per function, or when it makes sense, one per subsection for the lowest level of heading (For example a single test for all constructors under memory.buffer.ctor ).

EricWF added inline comments.May 28 2018, 7:48 PM
src/experimental/memory_resource.cpp
235

I was initially thinking of storing lg(align).

Add override; disintegrate the unit test; adopt some tests from Eric's D27402.
Also fix one QOI issue discovered by Eric's tests: if the user passes an initial_size to the constructor, then they are probably intending that our first upstream-allocation be big enough to serve at least initial_size 1-byte allocations (or one initial_size-byte allocation with a suitably small alignment). This is explicitly not mandated by the Standard (it merely requires that our next upstream-allocation be of size at least initial_size), but it's probably a healthy choice.

Refactor to remove unused fields from the header structs.

Before this change, sizeof(monotonic_buffer_resource) == 56 and the overhead per allocated chunk was 40 bytes.
After this change, sizeof(monotonic_buffer_resource) == 48 and the overhead per allocated chunk is 24 bytes.

Eric suggests replacing size_t __align_ with uint8_t __log2_align_. I'm amenable to this idea, but I'd want to know what's the best way to compute the log2 of a user-supplied number.

Quuxplusone marked 6 inline comments as done.May 28 2018, 10:36 PM
include/experimental/memory_resource
488

I've discovered that Boost.Container does not bother to preserve this state across calls to release(). If that's legal, then we can save 8 bytes here. I've asked for an LWG issue to be opened on the subject of "what the heck is release() supposed to do anyway."

  • Shrink monotonic_buffer_resource, and make release() not "leak" allocation size.

    Repeatedly calling allocate() and release() in a loop should not blow up. I originally thought this was required by the Standard, and maybe it is, but that was before I discovered this terrible effect, and before Pablo Halpern told me that it was not his actual intent.

    Since the only purpose of storing __next_buffer_size_ in the object was to implement the "looping blows up" misfeature, we can now get rid of that field, which shrinks monotonic_buffer_resource from 56 bytes down to 48 bytes, matching Boost.Container's implementation.
  • Add REQUIRES: c++experimental to all tests (oops).
include/experimental/memory_resource
488

On discussion with Ion Gaztañaga, Pablo Halpern, and Casey Carter, I've come to the conclusion that we *must not* preserve this state across calls to release, no matter what the Standard currently says, because that leads to insanely high memory usage when calling mr.release() in a loop. (Casey implies that MSVC's implementation has this issue; Pablo confirms that he never intended it.)

Fixed my implementation and added a regression test in test/libcxx/experimental/memory/memory.resource.monotonic.buffer/monotonic.buffer.mem/allocate_in_geometric_progression.pass.cpp.

Minor cosmetic changes.

Quuxplusone marked 7 inline comments as done.Jun 21 2018, 11:14 PM
EricWF added a comment.Jul 3 2018, 8:21 PM

Refactor to remove unused fields from the header structs.

Before this change, sizeof(monotonic_buffer_resource) == 56 and the overhead per allocated chunk was 40 bytes.
After this change, sizeof(monotonic_buffer_resource) == 48 and the overhead per allocated chunk is 24 bytes.

Woo! This is looking great!

I'm done looking at the implementation, I'll take a pass at the tests tomorrow. Some pointers in general:

  1. Tests should be named after the component they test, not how they're testing it.
  2. All the tests for a single component should be in the same file.
  3. You can use LIBCPP_ASSERT to check specific implementation details, like exactly how much our allocation sizes grow.

(1) and (2) are important for maintaining the tests. (3) will probably be useful for actually writing meaningful tests despite
most observable behavior being implementation specific.

include/experimental/memory_resource
424

Can these classes be members of monotonic_buffer_resource?

450

Lets keep these constructors inline.

466

Need _LIBCPP_FUNC_VIS

470

I think it would be nice for release to be inline. What do you think?

488

__previous_allocation_size isn't used in the header, so it shouldn't be declared there. We don't want to expose more symbols than we need to.

src/experimental/memory_resource.cpp
210

In general, please wrap to 80 characters.

test/std/experimental/memory/memory.resource.monotonic.buffer/nothing_to_do.pass.cpp
1 ↗(On Diff #153881)

We don't actually need this file, though older libc++ tests will often include it.

It's only needed to keep empty directories around, but this one has children.

Quuxplusone marked 7 inline comments as done.Jul 3 2018, 10:02 PM

I'll take a pass at the tests tomorrow. Some pointers in general:

  • Tests should be named after the component they test, not how they're testing it.
  • All the tests for a single component should be in the same file.

I'm certain I'm doing it fairly wrong and you'll have to give me specific handholds like "merge these two tests into one file", "rename this file to x.cpp", etc.
The current large number of files is only because *last* iteration, you told me to split up the tests from "one big monotonic_buffer.pass.cpp" into one file per test!
The problem with "one file per component" is that I don't understand what a "component" is in this context. From last iteration, I know that "all of monotonic_buffer_resource" is too big of a component! I also know that it's impossible to test deallocate without also calling allocate, but the reverse is not true.

include/experimental/memory_resource
470

Good point. It does pull a ton of stuff into the public header, but it's probably worth it.
I'm also moving the virtual destructor into the public header, so it can be inlined. (do_allocate becomes the new key function.)

test/std/experimental/memory/memory.resource.monotonic.buffer/nothing_to_do.pass.cpp
1 ↗(On Diff #153881)

I was starting to wonder about this! Removed.

Quuxplusone marked 2 inline comments as done.

Massive changes based on Eric's feedback. Moved constructors and destructors of monotonic_buffer_resource into the header so they can be completely inlined. Renamed struct __monotonic_buffer_foo_header to nested types monotonic_buffer_resource::__foo_header. Refactored for 80-column lines.

Quuxplusone marked an inline comment as done.Jul 3 2018, 10:23 PM

I'll take a pass at the tests tomorrow. Some pointers in general:

  • Tests should be named after the component they test, not how they're testing it.
  • All the tests for a single component should be in the same file.

I'm certain I'm doing it fairly wrong and you'll have to give me specific handholds like "merge these two tests into one file", "rename this file to x.cpp", etc.
The current large number of files is only because *last* iteration, you told me to split up the tests from "one big monotonic_buffer.pass.cpp" into one file per test!

I'm sorry, I don't mean to jerk you around. I'm still learning to be a reviewer. I'll provide some specific examples to avoid the ambiguity from before.

The problem with "one file per component" is that I don't understand what a "component" is in this context. From last iteration, I know that "all of monotonic_buffer_resource" is too big of a component! I also know that it's impossible to test deallocate without also calling allocate, but the reverse is not true.

Again, my apologies.

Oops, my previous diff had a stray ) in it, somehow.

Long-delayed ping!

Rebased on master. @EricWF @ldionne ping please?

EricWF accepted this revision.Nov 26 2018, 9:32 PM

LGTM. The tests might need some XFAIL'ing, but otherwise I think this looks good.

Sorry for the wait.

This revision is now accepted and ready to land.Nov 26 2018, 9:32 PM

@EricWF ping? This still needs someone to land it; I don't have commit privs. Thanks!

EricWF requested changes to this revision.Dec 9 2018, 6:00 PM

Some of the tests aren't passing with Trunk clang. Please fix these.

include/experimental/memory_resource
427

constexpr these constants if they're const?

test/std/experimental/memory/memory.resource.monotonic.buffer/monotonic.buffer.mem/allocate_overaligned_request.pass.cpp
33

This check isn't passing with ToT clang.

44

Either remove this or uncomment them. Preferably the latter. More test coverage is better.

This revision now requires changes to proceed.Dec 9 2018, 6:00 PM
Quuxplusone marked 5 inline comments as done.

@EricWF ping!

Updated and addressed review comments.
test/std/experimental/memory/memory.resource.monotonic.buffer/monotonic.buffer.mem/allocate_overaligned_request.pass.cpp is now XFAILed on OSX platforms, using code copied-and-pasted from test/libcxx/language.support/support.dynamic/libcpp_deallocate.sh.cpp.

@EricWF ping!

@EricWF ping!
and oops, I never submitted these comments, I guess.

include/experimental/memory_resource
427

Compare <ios>, which has "constexpr" in the synopsis comment but "static const" in the code.
However, I updated the diff to follow <random>'s example and use static _LIBCPP_CONSTEXPR const everywhere.

test/std/experimental/memory/memory.resource.monotonic.buffer/monotonic.buffer.mem/allocate_overaligned_request.pass.cpp
33

Agreed, it won't pass unless the underlying new_delete_resource supports overaligned alignments, which isn't true unless the underlying runtime supports aligned new. Which isn't true on my MacBook.

I think the fix would be for me to copy all the XFAIL lines from test/libcxx/language.support/support.dynamic/libcpp_deallocate.sh.cpp, is that right?

Quuxplusone added a subscriber: AlisdairM.

Rebased on master. @EricWF (cc @AlisdairM) ping!

Rebased on master. Added _NOEXCEPT to the resource() method (this is OK per [res.on.exception.handling]/5).

@ckennelly ping!

Rebased on master.

strager added inline comments.
include/experimental/memory_resource
427

Nit: Why isn't __default_buffer_alignment set to alignof(max_align_t) (which I think is 16)? I think alignof(max_align_t) is a good, portable default.

431–432

Nit: Would it make sense to use std::byte instead of char?

test/libcxx/experimental/memory/memory.resource.monotonic.buffer/monotonic.buffer.mem/allocate_in_geometric_progression.pass.cpp
32

Nit: This test is named allocate_in_geometric_progression. I don't see any multiplication or anything happening in this test case. Did you mean to call this test something else, like release_deletes_upstream_memory?

test/std/experimental/memory/memory.resource.monotonic.buffer/monotonic.buffer.mem/allocate_deallocate.pass.cpp
28

Nit: What is the purpose of the r1 variable? Why not use mono1 everywhere instead (and rename mono1 to r1 if you like r1 better than mono1 as a name)?

test/std/experimental/memory/memory.resource.monotonic.buffer/monotonic.buffer.mem/allocate_exception_safety.pass.cpp
48–49

Nit: These assertions look unrelated to exception safety to me. (The test is named allocate_exception_safety.) I'd delete these assertions.

52–54

(Same comment as on lines 48-49 above. I'd delete these assertions.)

67–68

Question about the intended behavior of monotonic_buffer_resource:

If line 68 instead allocated 1 byte, and the byte could fit in the original heap allocation (line 51), should monotonic_buffer_resource return a byte from that original resource? In other words, should the following test pass?

repointable_resource upstream(std::experimental::pmr::new_delete_resource());
std::experimental::pmr::monotonic_buffer_resource mono1(&upstream);

globalMemCounter.reset();
mono1.allocate(1, 1);
const size_t first_new_size = globalMemCounter.last_new_size;
bool mono1_has_spare_capacity = first_new_size == 1;

upstream.which = std::experimental::pmr::null_memory_resource();
try {
    mono1.allocate(first_new_size, 1); // Force allocation from upstream.
    assert(false);
} catch (const std::bad_alloc&) {
    // we expect this
}

globalMemCounter.reset();
mono1.allocate(1, 1);
if (mono1_has_spare_capacity) {
  assert(globalMemCounter.checkNewCalledEq(0));
} else {
  assert(globalMemCounter.checkNewCalledEq(1));
}

Similarly, if monotonic_buffer_resource was given a buffer, and that buffer still has spare capacity, should that capacity be reused? In other words, should the following test pass?

int first_allocation_size = 20;
int second_allocation_size = 30;

auto *upstream = std::experimental::pmr::null_memory_resource();
char buffer[64];
assert(sizeof buffer >= first_allocation_size + second_allocation_size);
std::experimental::pmr::monotonic_buffer_resource mono1(buffer, sizeof buffer, upstream);

globalMemCounter.reset();
void *first_allocation = mono1.allocate(first_allocation_size, 1);
assert(first_allocation == &buffer[0]);

try {
    mono1.allocate(sizeof buffer, 1); // Force allocation from upstream.
    assert(false);
} catch (const std::bad_alloc&) {
    // we expect this
}

void *second_allocation = mono1.allocate(second_allocation_size, 1);
assert(second_allocation == &buffer[second_allocation_size]);

I think these scenarios would be useful to test, in addition to the scenario in your test here.

strager added inline comments.Oct 11 2019, 10:45 AM
include/experimental/memory_resource
433

Eric suggests replacing size_t align_ with uint8_t log2_align_. I'm amenable to this idea, but I'd want to know what's the best way to compute the log2 of a user-supplied number.

Perhaps std::log2p1 could help: https://en.cppreference.com/w/cpp/numeric/log2p1

Quuxplusone marked 11 inline comments as done.Oct 16 2019, 12:23 PM
Quuxplusone added inline comments.
include/experimental/memory_resource
427

Will users be more upset if __default_buffer_alignment is 16-instead-of-??? on exotic platform ???; or more upset if __default_buffer_alignment is usually 16 but then sometimes is ???-instead-of-16 on exotic platforms? I tend to think that "usually 16, sometimes something else" is worse behavior software-engineering-wise than "always 16, even when something else might arguably be better on exotic platform ???."

431–432

IMHO "strong no"; char is the standard core-language type that takes up one byte. std::byte is an enum type that we'd have to drag in from a header (cost), and otherwise behaves just like char (no benefit). But it's certainly a non-functional nit and I would not put up a fight if libc++ wanted it that way. :)

433

Yes, but that's C++2a; I imagine some fiddliness would be needed to use it in C++17 library code (which in turn is actually compiled as C++11 or '14, I forget).

test/libcxx/experimental/memory/memory.resource.monotonic.buffer/monotonic.buffer.mem/allocate_in_geometric_progression.pass.cpp
32

Prior to the resolution of LWG 3120, this test had tested something else. I guess now it should be more like "release_resets_initial_buffer.pass.cpp".

test/std/experimental/memory/memory.resource.monotonic.buffer/monotonic.buffer.mem/allocate_deallocate.pass.cpp
28

r1 has a different static type. For example, here it's testing that r1.allocate(50) actually makes a virtual call to monotonic_buffer_resource::do_allocate. But I guess it doesn't really matter; I could use mono1 for everything just as well.

test/std/experimental/memory/memory.resource.monotonic.buffer/monotonic.buffer.mem/allocate_exception_safety.pass.cpp
48–49

Depends on your test-overfitting philosophy. These assertions are still expected to pass 100% of the time — if they fail, then something is definitely wrong. And they're cheap to execute. So IMHO they might as well be there, as "self-documenting code."

67–68

If [the request] could fit in the original heap allocation, should monotonic_buffer_resource return a byte from that original allocation?
Similarly, if monotonic_buffer_resource was given a buffer, and that buffer still has spare capacity, should that capacity be reused?

In both cases, the Standard says "absolutely not": mem.res.monotonic.buffer.mem#5. I can add these tests.

Can we please close this review as it's been superseded by D89057?

ldionne added a reviewer: Restricted Project.Nov 2 2020, 2:23 PM
Quuxplusone abandoned this revision.Nov 2 2020, 3:32 PM
Quuxplusone marked 3 inline comments as done.

Sure; not that D89057 is making any more progress... :)