How can I efficiently fill an array with a sequence of objects?

Using Swift
1

In my library, I am creating a series of objects efficiently from data. I then want to put them, in the order that they're created, into an array. I could just use Array.append, but I've measured and this isn't fast enough for my purposes. Also, it needs to be an Array and not some other type, e.g. ContiguousArray. So, I'm using Apple Developer Documentation to set up the array efficiently. However, when I do the first subscript assignment, i.e. buffer[0] = MyType(...), I get an EXC_BAD_ACCESS crash. If I first call memset(buffer.baseAddress, 0, count * MemoryLayout<Element>.stride) though, it won't crash. Here's my code with that memset call:

        let array: [Element] = try Array(unsafeUninitializedCapacity: count) { (buffer, countToAssign) in
            memset(buffer.baseAddress, 0, count * MemoryLayout<Element>.stride)
            var isAtEnd = false
            for i in 0..<count {
                do {
                    buffer[i] = try decoder.unbox(currentValue, as: Element.self)
                    JNTDocumentNextArrayElement(currentValue, &isAtEnd)
                } catch {
                    countToAssign = i
                    throw error
                }
            }
        }

This seems to work, and is substantially faster. As for why it crashes without the memset call, @Lantua has pointed out in the documentation for UnsafeMutablePointer that it says "Do not assign an instance of a nontrivial type through the subscript to uninitialized memory. Instead, use an initializing method, such as initialize(to:count:) .". Is the same true of UnsafeMutable*Buffer*Pointer? If so, is memset enough to be safe? And why does this crash occur in the first place?

FYI, here's another example of it initialized from a Sequence. However, this is also too slow for my purposes:

        let array: [Element] = try Array(unsafeUninitializedCapacity: count) { (buffer, countToAssign) in
            let sequence: ElementSequence<Element> = ElementSequence(decoder: decoder, count: count, value: currentValue)
            let _ = buffer.initialize(from: sequence)
            countToAssign = sequence.i
            if let error = sequence.error {
                throw error
            }
2

Were you using reserveCapacity(_:) up front when you made those measurements?

2 Likes
3

Is it possible for you to post a reduction of your code with sample types that demonstrates the slowness? It could be you've hit a deficiency with the optimizer, or it could be there's something about your implementation not covered in your post that is fixable that's causing the slowdown. You shouldn't need to resort to unsafe ops for something simple like this.

And – just to be sure – we are talking about performance of release not debug builds, right?

Are you reserving capacity in advance via array.reserveCapacity(count) first? That could explain a discrepancy like this.

Array and ContiguousArray share the same backing storage. So if you need to hand off an Array, but are finding that ContiguousArray is faster (which should really only happen with class types) then create a ContiguousArray, then copy it into an Array i.e. let array = Array(temporaryContiguousArray). This ought to be almost-free - the array should just take ownership of the contiguous array's backing buffer.

Yes

No, it isn't. It may be only working by chance. It really depends on the nature of the types involved.

The initialized-ness of the memory is not about needing to zero out the uninitialized memory before assigning to it. It's about the state that Swift believes the memory is currently in, and whether the value previously held in that location needs to be "released" when you overwrite it.

Under the hood, whenever you assign to variables, Swift needs to perform copy/create/destroy operations on the underlying values, including destroying the value overwritten and retaining the value stored. For example, if you have a struct that contains a class stored property, then assigning over that value in the buffer decrements the reference count of that stored property in the old element, potentially releasing it. But if the memory is not initialized it will try and release an uninitialized value, hence the crash. Zeroing out the values first is basically undefined behavior – it might be ok by chance, or it might crash epically. And that can change at any time.

The best way to handle this right now is to get the baseAddress of the buffer, then loop over your count calling initialize.

1 Like
4

It is indeed free (Godbolt). The second version (with __owned) more accurately reflects what you'll see if you write Array(n) as part of a larger function, and it literally does nothing besides create and destroy its own stack frame.

Array even has special hooks which allow this buffer-sharing to work in generic code. So this is something you can rely on.

5

It appears that using ContiguousArray gets it to be almost as fast as the unsafe approach, so I'll go with that.