Add "trailing elements" module with facilities for tail-allocated storage#513
Add "trailing elements" module with facilities for tail-allocated storage#513glessard merged 6 commits intoapple:mainfrom
Conversation
…rage Introduce new types `IntrusiveManagedBuffer` and `PaddedStorage` that consist of a fixed-sized header followed by variable-sized storage. The design of these types is inspired by the existing `ManagedBuffer` type in the standard library, but has been adjusted both to make them non-copyable and to eliminate the requirement for heap allocation.
lorentey
left a comment
There was a problem hiding this comment.
Nice!
This may end up sharing the same module as Box and other ownership utility constructs, but we'll have plenty of opportunities to set that up after this lands.
| { | ||
| /// The underlying storage. | ||
| @usableFromInline | ||
| var pointer: UnsafeMutablePointer<Header> |
There was a problem hiding this comment.
Nit: please underscore internal declarations, especially ones that are destined to eventually get exposed in ABI.
| var pointer: UnsafeMutablePointer<Header> | |
| var _pointer: UnsafeMutablePointer<Header> |
| /// the information in the header (via the `trailingCount` property), so that | ||
| /// it is not stored separately. | ||
| @frozen | ||
| public struct IntrusiveManagedBuffer<Header: TrailingElements>: ~Copyable |
There was a problem hiding this comment.
I don't like Managed in the name here -- in the stdlib's existing use of this term, "managed" usually indicates reference counting. We've avoided using that term for constructs that are built on ownership features, like this one.
It also makes this uncomfortably close to ManagedBuffer, which is a far more general construct than this one -- in particular, ManagedBuffer supports (and encourages) uninitialized slots, whereas this one requires its storage to be fully initialized.
How about TrailingBuffer? Or perhaps TrailingArray, to avoid associating the word "buffer" with fixed-size, fully-initialized storage contexts? InlineArray has set a recent precedent of using "array" this way.
There was a problem hiding this comment.
Hmm. I'm okay with TrailingArray. Does that mean it should go into the ArrayModule?
There was a problem hiding this comment.
Hrm. Now that I do this, I also want to rename PaddedStorage to TrailingPadding, which fits the scheme better.
| /// that memory. The underlying storage will not be freed by this buffer; | ||
| /// it is the responsibility of the caller. | ||
| @_alwaysEmitIntoClient | ||
| public consuming func takePointer() -> UnsafeMutablePointer<Header> { |
There was a problem hiding this comment.
This feels like an unsafe version of Box.leak() -- would something like leakPointer be a better name? Cc @Azoy
There was a problem hiding this comment.
I'm happy to go with that precedent, sure.
There was a problem hiding this comment.
Actually, I feel like leakStorage would be slightly better, because it's the storage that we're leaking and the type already has "pointer" into it.
| UnsafeMutableBufferPointer( | ||
| start: UnsafeMutableRawPointer(pointer.advanced(by: 1)) | ||
| .assumingMemoryBound(to: Element.self), | ||
| count: header.trailingCount | ||
| ) |
There was a problem hiding this comment.
Element may have stronger alignment than Header here -- the advanced pointer has to be explicitly rounded up to a suitable boundary.
There was a problem hiding this comment.
Handled this with the latest commit, thank you!
| /// Determine the allocation size needed for the given header value. | ||
| @_alwaysEmitIntoClient | ||
| public static func allocationSize(header: borrowing Header) -> Int { | ||
| MemoryLayout<Header>.size + MemoryLayout<Element>.stride * header.trailingCount |
There was a problem hiding this comment.
This needs to make sure the allocation size is large enough to cover padding bytes if Element has stricter alignment than Header.
ea5dfaa to
d240c10
Compare
…alignment than the header When this happens, we over-allocate and use the alignment of the elements, and then move the start of the header after the point of allocation such that the properly-aligned elements follow it immediately.
d240c10 to
43367db
Compare
|
I force-pushed a mostly-identical copy of the latest commit to force the actions pick up the latest state of the main branch. |
glessard
left a comment
There was a problem hiding this comment.
Nice! We could improve the test coverage in followup work.
| @_lifetime(self) | ||
| mutating get { | ||
| let elements = self.rawElements.mutableSpan | ||
| return _overrideLifetime(elements, mutating: &self) |
There was a problem hiding this comment.
I think this could be a one-liner since _overrideLifetime consumes its 1st argument.
Description
Introduce new types
TrailingArrayandTrailingPaddingthat consist of a fixed-sized header followed by variable-sized storage. The design of these types is inspired by the existingManagedBuffertype in the standard library, but has been adjusted both to make them non-copyable and to eliminate the requirement for heap allocation.Detailed Design
It's several new types. Here's a sketch of the API for the primary type,
IntrusiveManagedBuffer:Documentation
The new types and protocol have full documentation in the source. The module itself has tutorial-like overview to guide users to the functionality they need.
Testing
New tests of the major functionality of the feature.
Performance
I did not. Everything is
@frozen/@_alwaysEmitIntoClientand uses noncopyable types so there should be no extraneous runtime overhead.Source Impact
No source impact. This is a new module with new API.
Checklist