[Pitch] Buffer Partial Initialization / Better Buffer Slices

Hello,

Here is the fourth in a series of pitches related to improvements the Pointer and BufferPointer family. This pitch is about making slices of buffers more useful, especially with respect to partial initialization of buffers.

Partial Buffer Initialization / Better Buffer Slices

Introduction

Sub-sequences of the UnsafeBufferPointer family have all the [Mutable]Collection API of UnsafeBufferPointer, but have none of their buffer-specific API. This makes partial initialization of a buffer difficult, among other tasks.

Motivation

An example of partial initialization is inserting elements in the middle of a collection, one of the possible operations needed in an implementation of RangeReplaceableCollection.replaceSubrange(_:with:). Given a RangeReplaceableCollection whose unique storage can be represented by a partially-initialized UnsafeMutableBufferPointer:

mutating func replaceSubrange<C>(_ subrange: Range<Index>, with newElements: C)
  where C: Collection, Element == C.Element {

  // obtain unique storage as UnsafeMutableBufferPointer
  let buffer: UnsafeMutableBufferPointer<Element> = self.myUniqueStorage()
  let oldCount = self.count
  let growth = newElements.count - subrange.count
  let newCount = oldCount + growth
  if growth > 0 {
    assert(newCount < buffer.count)
    let oldTail = subrange.upperBound..<oldCount
    let newTail = subrange.upperBound+growth..<newCount
    let oldTailBase = buffer.baseAddress!.advanced(by: oldTail.lowerBound)
    let newTailBase = buffer.baseAddress!.advanced(by: newTail.lowerBound)
    newTailBase.moveInitialize(from: oldTailBase,
                               count: oldCount - subrange.upperBound)

    // Update still-initialized values in the original subrange
    var j = newElements.startIndex
    for i in subrange {
      buffer[i] = newElements[j]
      newElements.formIndex(after: &j)
    }
    // Initialize the remaining range
    for i in subrange.upperBound..<newTail.lowerBound {
      buffer.baseAddress!.advanced(by: i).initialize(to: newElements[j])
      newElements.formIndex(after: &j)
    }
    assert(newElements.distance(from: newElements.startIndex, to: j) == newElements.count)
  }
  ... // other situations
}

Here, we had to convert to UnsafeMutablePointer to use some of its API, as well as resort to element-by-element copying and initialization. With API enabling buffer operations on the slices of buffers, we could simplify things greatly:

mutating func replaceSubrange<C>(_ subrange: Range<Index>, with newElements: C)
  where C: Collection, Element == C.Element {

  // obtain unique storage as UnsafeMutableBufferPointer
  let buffer: UnsafeMutableBufferPointer<Element> = self.myUniqueStorage()
  let oldCount = self.count
  let growth = newElements.count - subrange.count
  let newCount = oldCount + growth
  if growth > 0 {
    assert(newCount < buffer.count)
    let oldTail = subrange.upperBound..<count
    let newTail = subrange.upperBound+growth..<newCount
    var m = buffer[newTail].moveInitialize(fromElements: buffer[oldTail])

    // Update still-initialized values in the original subrange
    m = buffer[subrange].update(fromElements: newElements)
    // Initialize the remaining range
    m = buffer[m..<newTail.lowerBound].initialize(
      fromElements: newElements.dropFirst(m - subrange.lowerBound)
    )
    assert(m == newTail.lowerBound)
  }
  ... // other situations
}

In addition to simplifying the implementation, the new methods have the advantage of having the same bounds-checking behaviour as UnsafeMutableBufferPointer, relieving the client code from being required to do its own bounds checking.

Proposed solution

We propose to add to slices of Unsafe[Mutable][Raw]BufferPointer all the BufferPointer-specific methods of their Base.

Note: many of these methods were recently pitched here.

Addition to Slice<UnsafeBufferPointer<T>>:

public func withMemoryRebound<T, Result>(
  to type: T.Type,
  _ body: (UnsafeBufferPointer<T>) throws -> Result
) rethrows -> Result

Additions to Slice<UnsafeMutableBufferPointer<T>>:

func initialize(repeating repeatedValue: Element)

func initialize<S: Sequence>(from source: S) -> (S.Iterator, Index)
  where S.Element == Element

func initialize<C: Collection>(fromElements: C) -> Index
  where C.Element == Element

func update(repeating repeatedValue: Element)

func update<S: Sequence>(
  from source: S
) -> (iterator: S.Iterator, updated: Index) where S.Element == Element

func update<C: Collection>(
  fromElements: C
) -> Index where C.Element == Element

func moveInitialize(fromElements source: UnsafeMutableBufferPointer<Element>) -> Index

func moveInitialize(fromElements source: Slice<UnsafeMutableBufferPointer<Element>>) -> Index

func moveUpdate(fromElements source: UnsafeMutableBufferPointer<Element>) -> Index

func moveUpdate(fromElements source: Slice<UnsafeMutableBufferPointer<Element>>) -> Index

func deinitialize() -> UnsafeMutableRawBufferPointer

func initializeElement(at index: Index, to value: Element)

func updateElement(at index: Index, to value: Element)

func moveElement(at index: Index) -> Element

func deinitializeElement(at index: Index)

func withMemoryRebound<T, Result>(
  to type: T.Type,
  _ body: (UnsafeMutableBufferPointer<T>) throws -> Result
) rethrows -> Result

Additions to Slice<UnsafeRawBufferPointer>:

func bindMemory<T>(to type: T.Type) -> UnsafeBufferPointer<T>

func withMemoryRebound<T, Result>(
  to type: T.Type, _ body: (UnsafeBufferPointer<T>) throws -> Result
) rethrows -> Result

func assumingMemoryBound<T>(to type: T.Type) -> UnsafeBufferPointer<T>

Additions to Slice<UnsafeMutableRawBufferPointer>:

func copyMemory(from source: UnsafeRawBufferPointer)

func copyBytes<C: Collection>(from source: C) where C.Element == UInt8

func initializeMemory<T>(
  as type: T.Type, repeating repeatedValue: T
) -> UnsafeMutableBufferPointer<T>

func initializeMemory<S: Sequence>(
  as type: S.Element.Type, from source: S
) -> (unwritten: S.Iterator, initialized: UnsafeMutableBufferPointer<S.Element>)

func initializeMemory<C: Collection>(
  as type: C.Element.Type, fromElements: C
) -> UnsafeMutableBufferPointer<C.Element>

func moveInitializeMemory<T>(
  as type: T.Type, fromElements: UnsafeMutableBufferPointer<T>
) -> UnsafeMutableBufferPointer<T>

func moveInitializeMemory<T>(
  as type: T.Type, fromElements: Slice<UnsafeMutableBufferPointer<T>>
) -> UnsafeMutableBufferPointer<T>

func bindMemory<T>(to type: T.Type) -> UnsafeMutableBufferPointer<T>

func withMemoryRebound<T, Result>(
  to type: T.Type,
  _ body: (UnsafeMutableBufferPointer<T>) throws -> Result
) rethrows -> Result

func assumingMemoryBound<T>(to type: T.Type) -> UnsafeMutableBufferPointer<T>

Detailed design

Note: please see the draft pull request or the full proposal for details.

Source compatibility

This proposal consists solely of additions and is therefore source compatible.

Effect on ABI stability

The functions proposed here generally small wrappers around existing functionality.
They will be implemented as @_alwaysEmitIntoClient functions,
which means they will have no ABI impact.

Effect on API resilience

All functionality implemented as @_alwaysEmitIntoClient will back-deploy.

Alternatives considered

None.

13 Likes

This seems like a great idea: it removes many of the weird ergonomic issues with holding slices of unsafe buffer pointers.

Most of this seems great. I’m a little worried about the APIs that take an Index, though, because UnsafeBufferPointer is one of the types with Int indices, and Slice<UBP> doesn’t necessarily start at 0. It’s not a new problem, but I wonder if it’d be better to force people to deal with that more explicitly. Then again, the existing operations don’t make that easy either.

Also, updateElement(at:) is the same as the subscript setter, isn’t it?

1 Like

Yes. The doc-comment is even explicit about this:

  /// Updates the initialized element at `index` to the given value.
  ///
  /// The memory underlying the destination element must be initialized,
  /// or `Element` must be a trivial type. This method is equivalent to:
  ///
  ///     self[index] = value

The same is in the other initialization pitch. There, I addressed your question as follows: The proposed changes "include a method to update a single element. Evidently that is a synonym for the subscript(_ i: Index) setter. We hope that documenting the update action specifically will help clarify the requirements of that action which, as experience shows, get muddled when documented along with the subscript getter."

1 Like

We could elect not to add the functions that take Index, but that would be inconsistent with the existence of subscript(_ i: Index). We would also lose the simplicity of having the same API surface on Slice<UBP> as on UBP.