A Wednesday puzzler

[QuinceyMorris]

Here’s a simple problem involving unsafe pointers, presented as a puzzle to be solved for the “best” solution that Swift has to offer. Consider a function with the following signature:

	func fill<T>(_ buffer: UnsafeMutableRawPointer, with array: [T]) { … }

The rules of the game are:

1. The semantics of the function are that it copies the contents of the array into the given buffer.

2. You can assume that buffer points to memory that has been allocated at a suitable size, and has a lifetime longer than the call to fill(_:with:). If you wish, you can further assume that the buffer has been initialized to all 0 bits.

3. T is a trivial type. It can be a simple integer or float type, or a struct with trivial members, or a SIMD generic over a trivial numeric type.

4. The buffer parameter is passed in as an immutable variable. You aren’t allowed to make it inout (in case that matters to the solution).

5. APIs used in the implementation are limited to the Swift language and the standard library.

The game is:

— Complete the function by writing the “best” implementation.

Obviously, “best” is going to be somewhat subjective (so the planned $1,000,000 cash prize isn’t going to be awarded, for ethical reasons), but here are some criteria:

• Swifty-est. A casual reader of the implementation should tend to think, “Oh, I didn’t realize Swift could handle that so neatly.” The reader should ideally learn something about Swift from this.

• Proper-est. The implementation shouldn’t abuse Swift features designed for other purposes, but can be opinionated about what features are relevant here. For example, “binding” of unsafe pointers doesn’t really do anything for trivial types (AFAIK). A solution will have to take a stand on whether to avoid APIs that mention bind or assumingBound because it’s a distraction for trivial types, or to embrace binding because it’s formally required even if it doesn’t do anything here.

• Un-hacky-est. The more directly the solution expresses what is actually going on, the better.

The judges will be a panel of international semioticists and impartial language lawyers — blindfolded, of course, and prepared by 3 days of immersion in sensory deprivation tanks. The judges’ decision will be final and cannot be overridden.

[Jens]

func fill<T>(_ buffer: UnsafeMutableRawPointer, with array: [T]) {
  array.withUnsafeBufferPointer { arrayPtr in
    buffer.assumingMemoryBound(to: T.self)
      .assign(from: arrayPtr.baseAddress!, count: arrayPtr.count)
  }
}

[Jens]

Or:

func fill<T>(_ buffer: UnsafeMutableRawPointer, with array: [T]) {
  array.withUnsafeBytes { arRawPtr in
    buffer.copyMemory(from: arRawPtr.baseAddress!, byteCount: arRawPtr.count)
  }
}

[Nevin]

func fill<T>(_ buffer: UnsafeMutableRawPointer, with array: [T]) {
  buffer.copyMemory(from: array, byteCount: array.count * MemoryLayout<T>.stride)
}

[Jens]

func fill<T>(_ buffer: UnsafeMutableRawPointer, with array: [T]) {
  buffer.initializeMemory(as: T.self, from: array, count: array.count)
}

[Andrew_Trick]

@QuinceyMorris

• Swifty-est. A casual reader of the implementation should tend to think, “Oh, I didn’t realize Swift could handle that so neatly.” The reader should ideally learn something about Swift from this.

UnsafeMutableRawPointer is already extremely unswifty because it is (a) not memory managed (b) not bounds checked, and (c) a reference type. It's also "untyped", but I don't think that's necessarily unswifty. We just have a ways to go to provide swifty APIs on top of raw bytes. There's been very little effort to do that.

• Proper-est. The implementation shouldn’t abuse Swift features designed for other purposes, but can be opinionated about what features are relevant here. For example, “binding” of unsafe pointers doesn’t really do anything for trivial types (AFAIK). A solution will have to take a stand on whether to avoid APIs that mention bind or assumingBound because it’s a distraction for trivial types, or to embrace binding because it’s formally required even if it doesn’t do anything here.

Any solution that mentions bind or assumingBound fails because those APIs have extremely subtle semantics that can introduce undefined behavior even for trivial types. There's almost no legitimate reason to introduce binding memory in pure swift code. They show up with alarming frequency because of common impedance mismatches between imported C types and C functions that operate on those types.

---

There are two issues with the question

1. Unfortunately, there is currently no way to constrain T to be a trivial type. So we can't express your constraints programmatically, and that effects the generality of the answer.

2. We need to assume buffer is either uninitialized or initialized to some trivial type. Stating "initialized to 0" implies that--there's no conceivable way to enforce it. But there's also no information about whether the buffer is expected to contain elements of type T after calling it.

From @Nevin

   func fill<T>(_ buffer: UnsafeMutableRawPointer, with array: [T]) {
      buffer.copyMemory(from: array, byteCount: array.count * MemoryLayout<T>.stride)
   }

This is the solution with minimal assumptions. It's just a flat-out byte copy. If the buffer was previously bound to a different type, U, it remains bound to that type and can continue to be accessed via UnsafePointer<U>.

From @Jens

 func fill<T>(_ buffer: UnsafeMutableRawPointer, with array: [T]) {
  buffer.initializeMemory(as: T.self, from: array, count: array.count)
}

This looks nicer, but adds some semantics to the function: fill will initialize the buffer type elements of type T. If the caller accesses buffer with a typed pointer, it must be UnsafePointer<T>.

Ideally, the caller would never access the buffer using a typed pointer, so we're just looking for the correct sequence of raw bytes. In that case, might as well go with the nicer-looking one.

[Jens]

@Andrew_Trick

If the caller accesses buffer with a typed pointer, it must be UnsafePointer<T>

What will/can happen if the caller accesses buffer with UnsafePointer<U>, assuming both T and U are trivial types?

[Lantua]

The judge has appeared! (sorry, can't help )

[Andrew_Trick]

What will/can happen if the caller accesses buffer with UnsafePointer<U> , assuming both T and U are trivial types?

The initialization of the memory could be reordered with the caller's reads. It may seem dumb at first glance that the compiler would do this, but remember that pointers can be stored and loaded and obscured in all sorts of ways. UnsafePointer<T> implements strict aliasing because it is the C interop pointer type.

Anyone can easily build a non-strict-aliasing pointer-to-element-type on top of UnsafeRawPointer's API if they want. The standard library just does not vend such a pointer type yet.

[QuinceyMorris]

Thanks to everyone who participated so far. It looks like @Jens and @Nevin are co-winners. (Somehow, @Jens was also competing with himself, and managed to beat himself soundly. Not sure how that could happen. Maybe it's a quantum entanglement effect.) These are the winning implementations:

func fill<T>(_ buffer: UnsafeMutableRawPointer, with array: [T]) {
      buffer.copyMemory(from: array, byteCount: array.count * MemoryLayout<T>.stride)
   }

func fill<T>(_ buffer: UnsafeMutableRawPointer, with array: [T]) {
  buffer.initializeMemory(as: T.self, from: array, count: array.count)
}

It seems to me that these solutions are pretty compact, but don't really make Swift look good (not Jens or Nevin's fault in any way). The problem for me is that pesky and redundant-looking count. If array can be coerced to produce an unsafe pointer of some kind without any additional source code decoration, then surely it can produce an unsafe buffer pointer that has the count built in. It seems like the correct answers ought to be:

func fill<T>(_ buffer: UnsafeMutableRawPointer, with array: [T]) {
      buffer.copyMemory(from: array)
   }

func fill<T>(_ buffer: UnsafeMutableRawPointer, with array: [T]) {
  buffer.initializeMemory(as: T.self, from: array)
}

Apart from anything else, in this simple use-case, there'd be no reason to define this fill function at all, since the single line of implementation could just as well be written at the call site, with excellent readability.

Looking at this at a slightly higher conceptual level, I'm beginning to think that it's actively harmful to have Unsafe…Pointer and Unsafe…BufferPointer both floating around as peers in Swift's conceptual space. We only really need Unsafe…BufferPointer because — still at the conceptual level — an Unsafe…Pointer could adequately be represented as a buffer pointer with a count of 1 element.

(Yes, I know that Unsafe…Pointer is for direct interop with C, and I understand that we might still want it to exist. I'm just thinking we should try to hide it better. Maybe with a leading underscore.)

If we could get Unsafe…Pointer out of our day-to-day thinking, we'd eliminate the perceived need to force-cast between Unsafe…Pointer and Unsafe…BufferPointer, which is currently awkward to say the least. We'd also be able to leverage the buffer pointer's count attribute to make APIs safer and more readable, as I've shown in the hypothetical examples above. Most importantly, we'd significantly reduce the complexity of the unsafe pointer types' conceptual space.

[xwu (Xiaodi Wu)]

@QuinceyMorris

We only really need Unsafe…BufferPointer because — still at the conceptual level — an Unsafe…Pointer could adequately be represented as a buffer pointer with a count of 1 element.

Usability of pointers in Swift

That's true, but here's a mind bender: why not a buffer pointer with length zero as the default? This actually definitionally does follow the collection semantics, in that it doesn't promise any valid elements. As @Lantua notes, the biggest downside of any of these ideas is that they awkwardly overload subscripting and make that harder. But if we had to make all pointers buffer pointers with default sizes, it seems like the right default size is 0.

[QuinceyMorris]

FWIW, I hadn't noticed that @lukasa had said that, and I originally intended to suggest 0 instead of 1 for the count. However, I changed my mind before posting, because the semantics would be ambiguous. If the count is 0, is it allowable to access the value at the location pointed to? Well, it depends, doesn't it? Arrays can have 0 elements.

The "real" solution, if we're designing API, would be to have a value for the count that means "unspecified". (It could be an optional Int, but I personally detest solutions that force you to unwrap optionals everywhere.)

Aside from real (source breaking) solutions, a count of 1 seems to better match the semantics of use cases where there's an actual pointer.

[xwu (Xiaodi Wu)]

@QuinceyMorris

However, I changed my mind before posting, because the semantics would be ambiguous. If the count is 0, is it allowable to access the value at the location pointed to?

Usability of pointers in Swift

I mean, not really. Any attempt to define reasonableness in programming tends to fall apart in the face of the reality of programming. For example, consider this hypothetical C data structure library: #include <stdio.h> #include <stdlib.h> #include <string.h> typedef struct { size_t count; size_t capacity; char bytes[]; } MyTailAllocArray; MyTailAllocArray *MakeArray(size_t size) { MyTailAllocArray *array = malloc(sizeof(MyTailAllocArray) + size); if (array == NULL) { ret…

[xwu (Xiaodi Wu)]

@QuinceyMorris

The "real" solution, if we're designing API, would be to have a value for the count that means "unspecified". (It could be an optional Int , but I personally detest solutions that force you to unwrap optionals everywhere.)

Usability of pointers in Swift

The problem is that whether something is a collection or not is not a runtime concern, it's a compile-time concerning. Being a collection is inherent in the type: a type either is or is not a collection, it cannot be decided later. It could be arranged that using the collection methods crashes, but that's pretty unfriendly, and requires larger lifetime analysis of the program to know if any operation will be safe. It's easier to have the type system encode whether you concretely know the lengt…

[lukasa (Cory Benfield)]

@QuinceyMorris

The "real" solution, if we're designing API, would be to have a value for the count that means "unspecified". (It could be an optional Int , but I personally detest solutions that force you to unwrap optionals everywhere.)

You can’t do that and be a collection. How do the collection APIs behave in the face of “I don’t know what the count is?”. They must behave as though the count is 0, so let’s just make it zero.

The actual way you fix this is to not make the Index type Int but instead to have it opaque, and have a separate subscripting set that use Int-based offsets. Arbitrary subscripts are not required to pass through the Collection Index type, so they can do whatever.

But we’ve skipped a problem with this idea anyway. Suppose we only have UnsafeBufferPointer. What’s the type of baseAddress?

[lukasa (Cory Benfield)]

I should also say, again, that I think BufferPointer is IMO simply not a problem in the pointer APIs. OpaquePointer is far worse. BufferPointer is an extremely straightforward compositional type: I really struggle to believe that it’s adding substantial mental overhead at all.

[Hacksaw]

I prefer this one because it's blinding obvious what's happening, and I can sort imagine what the assembly code might look like. Solutions with anonymous closures seem like they'd have somewhat pointless overhead.

Though I wonder, is it possible to dispatch such a thing? I could see the use of asking another core to fill a gigantic hunk of RAM while other things were being set up.

[lukasa (Cory Benfield)]

@Hacksaw

Solutions with anonymous closures seem like they'd have somewhat pointless overhead.

They don't. Here's a godbolt comparing the two. If we look at the specialised implementations, here's the assembly for each:

generic specialization <Swift.Int> of output.fillWithClosure<A>(_: Swift.UnsafeMutableRawPointer, with: [A]) -> ():
        push    rbp
        mov     rbp, rsp
        imul    rdx, qword ptr [rsi + 16], 8
        jo      .LBB1_3
        test    rdx, rdx
        js      .LBB1_4
        add     rsi, 32
        pop     rbp
        jmp     memmove@PLT
.LBB1_3:
        ud2
.LBB1_4:
        ud2

generic specialization <Swift.Int> of output.fillWithoutClosure<A>(_: Swift.UnsafeMutableRawPointer, with: [A]) -> ():
        push    rbp
        mov     rbp, rsp
        mov     rdx, qword ptr [rsi + 16]
        add     rsi, 32
        shl     rdx, 3
        pop     rbp
        jmp     memcpy@PLT

These two are basically identical. The assembly is a bit different (fillWithClosure uses imul idx, word ptr [rsi + 16], 8 whereas fillWithoutClosure uses mov rdx, qword ptr [rsi + 16]; shl rdx, 3. These two have the same effect but the pattern in fillWithClosure allows a precondition, presumably because copyMemory includes a checked multiplication somewhere while initializeMemory does not. copyMemory also has null-pointer precondition. Then copyMemory calls memmove while initialiseMemory calls memcpy, a minor distinction that might be valuable in some rare cases.

None of these distinctions have anything to do with the closure though: only the fact they call different copying functions. The closure is entirely free.

[BigSur ({ @MainActor  in M1.Ultra }(Swift))]

@lukasa

These two have the same effect but the pattern in fillWithClosure allows a precondition, presumably because copyMemory includes a checked multiplication somewhere while initializeMemory does not. copyMemory also has null-pointer precondition. Then copyMemory calls memmove while initialiseMemory calls memcpy , a minor distinction that might be valuable in some rare cases.

Does that mean initialiseMemory is lighter and a little bit more efficient(no precondition checking) than copyMemory ?

[lukasa (Cory Benfield)]

@BigSur

Is that means initialiseMemory is lighter and a little bit more efficient(no precondition checking) than copyMemory ?

Probably not. A mistake or two on my part here: the null-pointer check is in the code itself, where we force unwrap the base address. The only difference then is the count check, which is almost certainly coming from Array's withUnsafeBytes code. That code is elided in the transparent conversion of array to pointer and instead some less safe code is used.

This means the only difference between the two is memmove vs memcpy. Not worth worrying about.