This is an archive of the discontinued LLVM Phabricator instance.

[libc++] Implement P0401R6 (allocate_at_least)
ClosedPublic

Authored by philnik on Apr 1 2022, 12:42 AM.

Details

Diff Detail

Event Timeline

philnik created this revision.Apr 1 2022, 12:42 AM
Herald added a project: Restricted Project. · View Herald TranscriptApr 1 2022, 12:42 AM
philnik requested review of this revision.Apr 1 2022, 12:42 AM
Herald added a project: Restricted Project. · View Herald TranscriptApr 1 2022, 12:42 AM
Herald added a reviewer: Restricted Project. · View Herald Transcript
var-const requested changes to this revision.Apr 4 2022, 12:32 PM
var-const added inline comments.
libcxx/include/__memory/allocate_at_least.h
58

Nit: can it be just return {__alloc.allocate(__n), __n}; like above? I think braced-list initialization should be supported in old language modes.

64

Nit: remove one extra blank line (there currently are two blank lines next to each other).

libcxx/include/__memory/allocator.h
16

Nit: I think it would be easier to just follow "include-what-you-use". It's not obvious that allocate_at_least.h should guarantee to include <cstddef>.

112

Hmm, if I'm reading this correctly, this is exactly equivalent to the old behavior -- even though we implement an interface that would allow an allocator to overallocate, the actual standard allocators never overallocate. Does this require a TODO? Or is this feature only for user-provided allocators?

libcxx/include/string
3293

Question: this is to account for the terminating null, right? Would it be cleaner to remove the subtraction here and the + 1 addition below, instead of having to adjust the value twice?

libcxx/include/vector
2346

Is this line equivalent to this->__cap() = __n; (where __n = __external_cap_to_internal(__n);)? In other words, does __allocation.count require the external->internal adjustment or not?

libcxx/test/std/utilities/memory/allocator.traits/allocate_at_least.pass.cpp
1

I think there also needs to be a test for std::allocator<T>::allocate_at_least. This test essentially checks that std::allocate_at_least is correctly forwarded to the allocator's allocate_at_least.

21

Nit: make it a struct and avoid the public: label?

30

Nit: since these helpers are always instantiated with int, they probably don't need to be templates at all.

47

Nit: decltype(auto).

This revision now requires changes to proceed.Apr 4 2022, 12:32 PM
philnik marked 2 inline comments as done.Apr 4 2022, 1:09 PM
philnik added inline comments.
libcxx/include/__memory/allocator.h
112

I don't think there is anything preventing an implementation from over-allocating, but I don't know of a standard C API for over-allocating. We can of course special-case this for malloc implementations that have an API for over-allocating.

libcxx/include/string
3293

Feel free to review D119628! But maybe you should wait until I land D110598.

libcxx/include/vector
2346

AFAICT the number of size_types is stored, so no, this doesn't require translation. The allocator returns the number of allocated objects, so the same number that is saved internally.

var-const added inline comments.Apr 4 2022, 3:19 PM
libcxx/include/__memory/allocator.h
112

Maybe I'm misreading the paper (I wasn't aware of it before seeing this patch), but it seemed like the whole purpose of allocate_at_least is to avoid wasting capacity in case an allocator overallocates. I'm not clear, however, if this only applies to user-provided allocators, or if it's meant specifically for std::allocator, but given the wording changes for std::allocator, I presume the latter.

I don't know if the underlying allocator machinery we're currently using is overallocating and if there's a way to query the actual allocated size. However, I think that:

  • if our underlying allocations never overallocate, we should add a comment to that effect to std::allocator<T>::allocate_at_least;
  • otherwise, we should add a TODO.

In short, if I'm reading the paper correctly, it's meant to bring a behavioral change, whereas with the current implementation in this patch, the behavior will be exactly equivalent. Once again, I might well be missing or misreading something -- please point it out if I do.

libcxx/include/string
3293

Interesting, thanks for the link. I didn't realize there's a much bigger discussion hidden here.

philnik updated this revision to Diff 420481.Apr 5 2022, 6:03 AM
philnik marked 9 inline comments as done.
  • Address comments
libcxx/include/__memory/allocator.h
112

I think you are right that the implementation is allowed to return more memory than was requested. The problem is that we have no way to tell if the underlying allocator ever over-allocates. We don't have an API that can tell us that. There is no C-version of allocate_at_least. The only way to support this currently is through extensions. But I don't think we should add a TODO there. This TODO would never be removed, and what's the point of a TODO then? We also don't have a // TODO: optimize sort.

libcxx/test/std/utilities/memory/allocator.traits/allocate_at_least.pass.cpp
30

I think you have to be able to rebind an allocator, so making this a non-template class would make this technically not an allocator.

var-const added inline comments.Apr 5 2022, 2:32 PM
libcxx/include/__memory/allocator.h
112

I feel that we would have to use compiler-internal functions, so it's okay that there is no C-version. I wouldn't call it an extension, though -- some library functionality can only be implemented using magical compiler intrinsics.

Regarding the TODO, I think the full intention of the paper won't be realized until this is implemented, so the TODO is necessary. The optimize sort case is different -- there is always room for optional optimization, but in this case I feel this is almost a mandatory optimization. To continue with the sort analogy, if we had a sort implementation that had a O(N^2) worst-case complexity, a TODO would be in order.

Having said that, I don't know if the actual low-level allocation functions we use support or ever plan to support over-allocating. @ldionne what are your thoughts on this?

libcxx/test/std/utilities/memory/allocator.traits/allocate_at_least.pass.cpp
1

Thanks for expanding the test! What I meant is that since we're adding two new functions to the API (std::allocate_at_least and std::allocator<T>::allocate_at_least), we should have separate test for both of them -- i.e., we can't rely on std::allocate_at_least tests to test std::allocator<T>::allocate_at_least. I know that, at least in the current state, std::allocator<T>::allocate_at_least is equivalent to std::allocator<T>::allocate and there isn't much to test, but I still feel that at least a rudimentary test needs to be added. But please check with @ldionne -- perhaps what I'm suggesting is overkill.

ldionne requested changes to this revision.Apr 6 2022, 12:36 PM

LGTM but I'd like to see the updated tests. Thanks!

libcxx/include/__memory/allocate_at_least.h
48

I don't think this comment is necessary -- IMO it creates confusion where there should be none. Someone looking at this code and going "Hmm, I don't think those identifiers are valid" would easily convince themselves that the world is broken if we can't write that pre-C++23.

libcxx/include/__memory/allocator.h
112

My understanding of the paper's intent is that we add this interface so that user-defined allocators can take advantage of it, *and* system allocators too when possible. However, I agree with @philnik that the C library simply doesn't give us a standard way to take advantage of this at the moment, so I think our implementation is optimal (with one caveat, see below). Because of this, I feel that we *are* implementing the paper faithfully, and there is nothing left to do, so I wouldn't leave any comment. I hope this makes sense.

Caveat: On systems that support it, we could perhaps use malloc_usable_size (https://man7.org/linux/man-pages/man3/malloc_usable_size.3.html) to query how much memory malloc gave us in reality. Doing that in std::allocator is going to create interesting challenges, though, since we use operator new from std::allocator, not std::malloc directly. If it's even possible to do it, I think it will mandate being done in a separate patch as it will certainly be somewhat involved.

In my opinion, where P0401r6 perhaps didn't go far enough is by not adding some sort of operator new where you get a size feedback (oh wait, this is https://wg21.link/p0901r5)! If we had that, then we could use that from std::allocator instead. And from the dylib (where we'd implement that novel operator new), we'd be in a position to call malloc and use malloc_usable_size() on the returned pointer (whenever that's supported).

So I guess I can summarize my opinion by saying that std::allocator is basically a veneer on top of operator new, and so any optimization needs to be made in operator new itself, not in std::allocator.

libcxx/include/memory
101–109

I think we need some // since C++20s?

libcxx/include/string
1862–1863

After we ship this, I would like us to revisit the patch where you modified __recommend's return value (I can't find it ATM). See if it makes that patch any easier.

libcxx/include/vector
683
685

_LIBCPP_HIDE_FROM_ABI?

2337
2340–2348

_LIBCPP_HIDE_FROM_ABI

libcxx/test/libcxx/diagnostics/detail.headers/memory/allocate_at_least.module.verify.cpp
2

Please rebase onto main.

libcxx/test/std/utilities/memory/allocator.traits/allocate_at_least.pass.cpp
1

I agree -- we definitely need to treat std::allocate_at_least and std::allocator<T>::allocate_at_least as if they were different things, since they are different functions in the API. This test seems to be fine for std::allocate_at_least, but I'd like a separate test for std::allocator::allocate_at_least. You probably want to take some inspiration from libcxx/test/std/utilities/memory/default.allocator/allocator.members/allocate.pass.cpp & friends for that one (e.g. testing overaligned types, etc.)

15

Can you also add a simple test like

using AllocationResult = std::allocation_result<int*>;

Just to check the box of testing specifically for that type's existence.

This revision now requires changes to proceed.Apr 6 2022, 12:36 PM
philnik updated this revision to Diff 421171.Apr 7 2022, 5:42 AM
philnik marked 14 inline comments as done.
  • Address comments
ldionne accepted this revision.Apr 8 2022, 1:44 PM

LGTM with added tests for allocator::allocate_at_least.

libcxx/test/std/utilities/memory/default.allocator/allocator.members/allocate_at_least.pass.cpp
59 ↗(On Diff #421171)

I think perhaps you copy-pasted from libcxx/test/std/utilities/memory/default.allocator/allocator.members/allocate.pass.cpp a bit too eagerly :-). We also need to test:

  • The return type of allocator::allocate_at_least
  • That the size member is >= to ptr
var-const accepted this revision.Apr 8 2022, 6:41 PM

LGTM (once the remaining comment is addressed). Thanks!

This revision is now accepted and ready to land.Apr 8 2022, 6:41 PM
philnik updated this revision to Diff 421700.Apr 9 2022, 12:41 AM
  • Address comments
philnik marked an inline comment as done.Apr 9 2022, 12:41 AM
This revision was automatically updated to reflect the committed changes.