Re-pitch: Initializing an Array with Uninitialized Capacity

Hi everyone,

Another re-pitch with similar motivations to this one.

SE-223 was returned for revision due to concerns about the part of the proposal that allowed modification of the partially-initialized buffer of an existing array in the case of a throwing closure.

Since these concerns applied specifically to the partially-initialized case, this is a repitch that focuses only on the specific functionality of the init. The need for this particular feature is much greater than for the partially-initialized case IMO so it is worth getting that through a clean review and then possibly revisiting the deferred part, rather than tying them together.

Proposal PR is here


Accessing an Array's Uninitialized Buffer

Introduction

This proposal suggests a new initializer for Array and ContiguousArray that provide access to an array's uninitialized storage buffer.

Swift-evolution thread: https://forums.swift.org/t/array-initializer-with-access-to-uninitialized-buffer/13689

Motivation

Some collection operations require working on a fixed-size buffer of uninitialized memory.
For example, one O(n) algorithm for performing a stable partition of an array is as follows:

  1. Create a new array the same size as the original array.
  2. Iterate over the original array, copying matching elements to the beginning of the new array and non-matching elements to the end.
  3. When finished iterating, reverse the slice of non-matching elements.

Unfortunately, the standard library provides no way to create an array of a particular size without allocating and initializing every element. Even if we avoid initialization by manually allocating the memory using an UnsafeMutableBufferPointer, there's no way to convert that buffer into an array without copying the contents. There simply isn't a way to implement this particular algorithm with maximum efficiency in Swift.

We also see this limitation when working with C APIs that fill a buffer with an unknown number of elements and return the count. The workarounds are the same as above: either initialize an array before passing it or copy the elements from an unsafe mutable buffer into an array after calling.

Proposed solution

Adding a new Array initializer that lets a program work with an uninitialized buffer.

The new initializer takes a closure that operates on an UnsafeMutableBufferPointer and an inout count of initialized elements. This closure has access to the uninitialized contents of the newly created array's storage, and must set the intialized count of the array before exiting.

var myArray = Array<Int>(unsafeUninitializedCapacity: 10) { buffer, initializedCount in
    for x in 1..<5 {
        buffer[x] = x
    }
    buffer[0] = 10
    initializedCount = 5
}
// myArray == [10, 1, 2, 3, 4]

With this new initializer, it's possible to implement the stable partition as an extension to the Collection protocol, without any unnecessary copies:

func stablyPartitioned(by belongsInFirstPartition: (Element) throws -> Bool) rethrows -> [Element] {
    return try Array<Element>(unsafeUninitializedCapacity: count) { 
        buffer, initializedCount in
        var low = buffer.baseAddress!
        var high = low + buffer.count
        do {
            for element in self {
                if try belongsInFirstPartition(element) {
                    low.initialize(to: element)
                    low += 1
                } else {
                    high -= 1
                    high.initialize(to: element)
                }
            }
            
            let highIndex = high - buffer.baseAddress!
            buffer[highIndex...].reverse()
            initializedCount = buffer.count
        } catch {
            let lowCount = low - buffer.baseAddress!
            let highCount = (buffer.baseAddress! + buffer.count) - high
            buffer.baseAddress!.deinitialize(count: lowCount)
            high.deinitialize(count: highCount)
            throw error
        }
    }
}

This also facilitates efficient interfacing with C functions. For example, suppose you wanted to wrap the function vDSP_vsadd in a Swift function that returns the result as an array. This function requires you give it an unsafe buffer into which it writes results. This is easy to do with an array, but you would have to initialize the array with zeroes first. With a function like vDSP_vsadd, this unnecessary zeroing out would eat into the slight speed edge that the function gives you, defeating the point. This can be neatly solved by unsafeUninitializedCapacity:

extension Array where Element == Float {
  func dspAdd(scalar: Float) -> [Float] {
    let n = self.count
    return self.withUnsafeBufferPointer { buf in
      var scalar = scalar
      return Array<Float>(unsafeUninitializedCapacity: n) { rbuf, count in
        vDSP_vsadd(buf.baseAddress!, 1, &scalar, rbuf.baseAddress!, 1, UInt(n))
        count = n
      }
    }
  }
}

Detailed design

The new initializer and method are added to both Array and ContiguousArray.

/// Creates an array with the specified capacity, then calls the given closure
/// with a buffer covering the array's uninitialized memory.
///
/// The closure must set its second parameter to a number `c`, the number 
/// of elements that are initialized. The memory in the range `buffer[0..<c]`  
/// must be initialized at the end of the closure's execution, and the memory 
/// in the range `buffer[c...]` must be uninitialized.
///
/// - Note: While the resulting array may have a capacity larger than the
///   requested amount, the buffer passed to the closure will cover exactly
///   the requested number of elements.
///
/// - Parameters:
///   - unsafeUninitializedCapacity: The number of elements to allocate space
///     for in the new array.
///   - initializer: A closure that initializes elements and sets the count of
///     the new array.
///     - Parameters:
///       - buffer: A buffer covering uninitialized memory with room
///         for the specified number of of elements.
///       - initializedCount: The count of the array's initialized elements.
///         After initializing any elements inside `initializer`, update 
///         `initializedCount` with the new count for the array.
public init(
    unsafeUninitializedCapacity: Int,
    initializingWith initializer: (
        _ buffer: inout UnsafeMutableBufferPointer<Element>,
        _ initializedCount: inout Int
    ) throws -> Void
) rethrows

Specifying a capacity

The initializer takes the specific capacity that a user wants to work with as a parameter. The buffer passed to the closure has a count that is exactly the same as the specified capacity, even if the ultimate capacity of the new or existing array is larger.

Guarantees after throwing

If the closure parameter to the initializer throws, the initializedCount value at the time an error is thrown is assumed to be correct. This means that a user who needs to throw from inside the closure has one of two options.

Before throwing, they must:

  1. deinitialize any newly initialized instances or re-initialize any deinitialized instances, or
  2. update initializedCount to the new count.

In either case, the postconditions that buffer[0..<initializedCount] are initialized and buffer[initializedCount...] are deinitialized still hold.

Naming considerations

The argument labels on the initializer are definitely a little on the long side!

There are two important details of this API that led to the proposed spelling. First, the initializer is unsafe, in that the user must be sure to properly manage the memory addressed by the closure's buffer pointer parameter. Second, the initializer provides access to the array's uninitialized storage, unlike the other Array.withUnsafe... methods that already exist. Because trailing closures are commonly used, it's important to include those terms in the initial argument label, such that they're always visible at the use site.

Unused terminology

This proposal leaves out wording that would reference two other relevant concepts:

  • reserving capacity: Arrays currently have a reserveCapacity(_:) method, which is somewhat akin to the first step of the initializer. However, that method is used for the sake of optimizing performance when adding to an array, rather than providing direct access to the array's capacity. In fact, as part of the RangeReplaceableCollection protocol, that method doesn't even require any action to be taken by the targeted type. For those reasons, the idea of "reserving" capacity doesn't seem as appropriate as providing a specific capacity that will be used.

  • unmanaged: The proposed initializer is unusual in that it converts the lifetime management of manually initialized instances to be automatically managed, as elements of an Array instance. The only other type that performs this kind of conversion is Unmanaged, which is primarily used at the border of Swift and C interoperability, particularly with Core Foundation. Additionally, Unmanaged can be used to maintain and manage the lifetime of an instance over a long period of time, while this initializer performs the conversion as soon as the closure executes. As above, this term doesn't seem appropriate for use with this new API.

Source compatibility

This is an additive change to the standard library,so there is no effect on source compatibility.

Effect on ABI stability

These methods will need to be gated by OS versions on platforms that ship the standard library in the OS.

Effect on API resilience

The additional APIs will be a permanent part of the standard library, and will need to remain public API.

Alternatives considered

Returning the new count from the initializer closure

An earlier proposal included a method that allowed for access to the uninitialized spare capacity of an array that also contained initialized elements. Handling cases where the passed-in closure throws when there are existing initialized elements is more complicated than in the initializer case, and the proposal was returned for revision. Given the utilility and need of the initializer part of the proposal is far greater, these two proposals are being split out to unblock progress on that.

An earlier proposal had the initializer's closure return the new count, instead of using an inout parameter. This proposal uses the parameter instead, so that the method and initializer use the same closure type.

In addition, the throwing behavior described above requires that the initialized count be set as an inout parameter instead of as a return value. Not every Element type can be trivially initialized, so a user that deinitializes some elements and then needs to throw an error would be stuck. (This is only an issue with the mutating method.) Removing the throws capability from the closure would solve this problem and simplify the new APIs' semantics, but would be inconsistent with the other APIs in this space and would make them more difficult to use as building blocks for higher-level operations like stablyPartitioned(by:).

Creating an array from a buffer

An Array initializer that simply converts an UnsafeMutableBufferPointer into an array's backing storage seems like it would be another solution. However, an array's storage includes information about the count and capacity at the beginning of its buffer, so an UnsafeMutableBufferPointer created from scratch isn't usable.

Addendum

You can Try This At Home™ with this extension, which provides the semantics (but not the copy-avoiding performance benefits) of the proposed additions:

extension Array {
    public init(
        unsafeUninitializedCapacity: Int,
        initializingWith initializer: (
            _ buffer: inout UnsafeMutableBufferPointer<Element>,
            _ initializedCount: inout Int
        ) throws -> Void
    ) rethrows {
        var buffer = UnsafeMutableBufferPointer<Element>
            .allocate(capacity: unsafeUninitializedCapacity)
        var count = 0
        try initializer(&buffer, &count)
        self = Array(buffer[0..<count])
    }
}
16 Likes

Strong +1

I was able to apply the new internal Dictionary version of this concept to great effect in speeding up bridging, I expect the Array one to be just as useful.

1 Like

+1
C interop improvements >>>>

1 Like

+1, long overdue.

1 Like

Big +1.

I am very happy to see this come up again.

Off the top of my head, the only thing that gives me pause is that the “Guarantees after Throwing” section doesn’t address what would happen if you were initializing multiple elements concurrently when the exception was raised. What am I supposed to do if I’m initializing a 10-element array and at the moment I get an exception, elements 2, 4, 6, 8, and 9 are initialized but the others are still pending? The correct value of initializedCount is 5 but will subsequent code incorrectly assume that it’s the first five elements which are initialized?

Come to think of it, the same situation could also arise from initializing an array sequentially in reverse order, or any other order that isn’t just 0..<count.

From a “how to represent the data” POV, returning a [Int : T] instead of a [T] would solve the immediate problem, but I don’t think there’s a straightforward way for that to work within the type. Well, other than doing this all on a Either<[T], [Int : T]> instead of a [T], I suppose, but that seems ungainly.

Instead of a initializedCount: Int variable, should we have a indexIsInitialized: [Bool] variable? We could still get initializedCount by checking how many elements of indexIsInitialized are set to true.

This is really up to the person using the proposed initializer to implement some higher level API. In your example, you would need to keep track of which elements you had already initialized and then deinitialize them before returning. If that's too much burden, then not accepting a throwing closure would probably be the right behavior.

Note that if you have elements 2, 4, 6, 8, and 9 initialized, the correct value for count is not 5, since that would indicate that elements 0..<5 are initialized and 5..<10 are not. You'd need to take some sort of action to satisfy the requirements no matter what.

But the count of initialized elements is 5... What would the correct value of initializedCount be in the situation I gave?

Edit: I mean, I get what you’re saying, I guess I’m just wondering, given that we could find ourselves in a situation where initializedCount does not contain the count of initialized elements, if maybe we should call it something less confusing? (My ideas so far are all way worse... even with autocomplete, variable names shouldn’t be a full sentence that’s just missing the whitespace and punctuation.)

I would tend to say that’s not what this API is for. Every API doesn’t need to cover every use case, and the point of this API is performantly wrapping interfaces that are guaranteed to always init a contiguous range of elements. Attempting to generalize it so broadly to handle other cases makes it unsuitable for that purpose, in which case we shouldn’t be bothering to add it at all.

3 Likes

glad to see this proposal back on its feet. support!

Ok, I rescind my, um, “pause”? Is that right? Seems like an odd wording.

Whatever, the point is I’m +1 now.

+1

I think this is an extremely important interface for all our value-types which have contiguous storage. A similar initialiser is planned for String, and Data already supports custom allocated/deallocated memory (but I think it should also add an initialiser in this style).

1 Like

+1. Do you think this pattern is generally useful for other Collections that prefer storage of their content in contiguous memory, such as Data, ByteBuffer, etc? Any synergy with the previously pitched ContiguousCollection?

For example, I would like to add a similar initializer for String, where it's already needed for performance, albeit over UInt8 rather than Element. This pattern is useful for String for additional reasons. If the user requests <= 15 capacity, then this initializer can yield a stack-allocated buffer, skipping any allocation at all. Also, there's a post-initializingWith validation step to ensure the UTF-8 content is validly encoded, so like String(describing:as:), this would repair the contents afterwards.

3 Likes

Yes, it's a good idea to adopt this pattern in more types.

I don't think we can add it to ContiguousCollection though as the capabilities don't quite line up. UnsafeMutableBufferPointer is a contiguous collection, but it isn't init-able. The closest match would maybe be another refinement, RangeReplaceableContiguousCollection which provided this, similar to MutableContiguousCollection providing mutation. Or we could take the "if available" approach directly on RRC. Whether that's worth it is down to whether it's useful to be able to use this feature generically.

4 Likes

Right. I see this as a useful pattern for types to implement, rather than something that you'd want to program against generically, at least with our current collections. If we were to add other collections that had some of the same characteristics as Array we would want this operation too, but even there we might want something more specific. A deque, for example, might not need to guarantee that the initialized region starts at 0.

@Michael_Ilseman, would the string initializer you're thinking of have the same semantics as this one? It would sort of need to be String.UTF8View that would have this initializer, but we don't treat that view as mutable/range-replaceable at all.

IIUC, the method is no longer being proposed.

String would have the same semantics, but slightly looser post-conditions (which are not explicitly guaranteed anyways). Error-correction can increase the actual size, so the caller shouldn't escape and rely on the exact value of initializedCount after initialization as being equivalent to String.utf8.count. I think it would be on String directly: it's a API pattern that we follow, but it doesn't literally use a UBP<Element> but a UBP<UInt8>.

i think custom collections would be built on top of ManagedBuffer anyway, not Array

Terms of Service

Privacy Policy

Cookie Policy