Swift's manual memory management is done using unsafe pointers and unsafe buffer pointers. Which, as you pointed out, are quite inconvenient in use.
So a solution could be to write a wrapper around this, to at least abstract away the manual allocation and deallocation of the buffer and the objects inside it. This would still leave one with having to use UnsafePointers or UnsafeMutablePointers to interact with these objects in the buffer.
To circumvent that, one could implement a 'reference wrapper', that would allow for a more convenient access to the underlying object. But since we cannot write perfect wrapper types yet (AFAIK) due to key paths not being able to refer to methods, we do need some additional way to access these methods.
But I believe that these 2 strategies combined could be a viable option for a more abstracted way for manual memory management in Swift.
Here is a small example of that binary tree benchmark program, that uses this form of memory management. Here, we assume that these are part of a hypothetical module called 'SwiftMemoryResource'.
import SwiftMemoryResource
struct Node {
var left, right: UnsafeRef<Node>
func check() -> Int {
// End of tree is signalized by left and right node being
// indentical.
guard left != right else {
return 1
}
return 1 + left.ref.check() + right.ref.check()
}
}
func makeTree(depth: Int, pool: inout MonotonicBuffer) -> UnsafeRef<Node> {
guard let node = pool.allocate(Node.self) else {
fatalError("Not enough memory available!")
}
if depth > 0 {
node.initialize(to: Node(left: makeTree(depth: depth-1, pool: &pool),
right: makeTree(depth: depth-1, pool: &pool)))
} else {
node.initialize(to: Node(left: node, right: node))
}
return node
}
struct BinaryTree {
init(depth: Int, initialize: Bool = true) {
pool = MonotonicBuffer.create(
size: MemoryLayout<Node>.size * (1 << (depth + 1)))
self.depth = depth
root = makeTree(depth: initialize ? depth : 0, pool: &pool)
}
init(from oldTree: BinaryTree, depth: Int) {
pool = oldTree.pool
pool.reset()
self.depth = oldTree.depth
root = makeTree(depth: depth, pool: &pool)
}
var root: UnsafeRef<Node>
var pool: MonotonicBuffer
let depth: Int
}
let cmdLineDepth = Int(CommandLine.arguments.count > 1 ? CommandLine.arguments[1] : "10")
let minDepth = 4
let maxDepth = max(cmdLineDepth!, minDepth + 1)
let stretchDepth = maxDepth + 1
// Allocate stretch tree
do {
let tree = BinaryTree(depth: stretchDepth)
print("Stretch tree of depth \(stretchDepth)\t check: \(tree.root.ref.check())")
}
let longLivingTree = BinaryTree(depth: maxDepth)
var bufferTree = BinaryTree(depth: maxDepth, initialize: false)
for currentDepth in stride(from: minDepth, through: maxDepth, by: 2) {
let iterations = 1 << (maxDepth - currentDepth + minDepth)
var checkSum = 0
for _ in 1...iterations {
let tree = BinaryTree(from: bufferTree, depth: currentDepth)
checkSum += tree.root.ref.check()
}
print("\(iterations)\t trees of depth \(currentDepth)\t check: \(checkSum)")
}
// Check long living tree and print out check info
print("long lived tree of depth \(maxDepth)\t check: \(longLivingTree.root.ref.check())")
Here, we use a memory resource called 'MonotonicBuffer', which allocates one pool of the requested size. It is only deallocated when the MonotonicBuffer instance goes out of scope. New objects can be allocated inside the pool using the methods 'allocate' or 'construct'. 'allocate' will simply allocate memory for the new object in the pool, however, it will not initialize the memory. This can be done in an second step by calling 'initialize' on the returned reference. 'construct' allows to allocate and initialize an object in the memory pool directly ('construct' is not used in the example as the order of nodes would be different, resulting in worse layout for this traversal). The buffer is not limited to a single type of elements that it can hold. The functions 'allocate' and 'construct' determine which type of object is created.
Also, as one can see, accessing methods through the reference wrapper requires using the computed property 'ref', which returns a reference to the actual memory. If one was only interested in properties (both stored and computed), one can directly access or modify them through the reference wrapper.
As for the performance, here are the measurements for the different binary tree benchmarks on my machine (MacBook Pro M2 Max).
Swift #1 is the above shown program.
Swift #2 is your initial version (both multithreaded and single threaded).
Swift #3 is your final version (both multithreaded and single threaded without workers).
C++ #1 is the fastest C++ program from CLBG, compiled with gcc 13.2.
| Program |
Threads |
Time |
Time Total |
| Swift #1 |
single |
1.80 s |
- |
| Swift #1 no module |
single |
1.67 s |
- |
| Swift #2 |
single |
1.81 s |
- |
| Swift #2 |
multi |
260 ms |
2.14 s |
| Swift #3 |
single |
1.01 s |
- |
| Swift #3 |
multi |
160 ms |
1.32 s |
| C++ #1 |
single |
1.68 s |
- |
| C++ #1 |
multi |
321 ms |
2.26 s |
This shows the performance is comparable to your initial array-based implementation, but allows working on a higher abstraction layer and is suitable for different tasks. If the buffers are not loaded from a module but implemented directly inside the project, the performance reached is quite similar to the C++ version using pmr's monotonic buffer resources.
The MonotonicBuffer does not allocate new memory when it runs out, instead, the methods 'allocate' and 'construct' will return nil. So one must know which amount of memory will be used beforehand.
If it is not possible to know the required capacity before, this module offers a growable buffer, called 'GrowableMonotonicBuffer'. When this buffer runs out of memory, it will allocate a new block of memory, so one can keep creating new objects.
Memory safety is important in Swift. Allocations in a memory pool and using pointers or references to these objects is not really safe. The memory pool could be deallocated while there are still live pointers or references to the objects inside the buffer. Or a buffer reset would allow overwriting the data still in use.
In order to prevent this, I have also implemented safe versions of the buffers. When allocating or constructing objects, the functions return safe references of type 'Ref<T>'. Safe references will keep the underlying memory pool alive even if the buffer itself goes out of scope. Also, they lock the buffer, which prevents it from being reset.
Here is how an implementation of the binary tree program could look like using a safe buffer. Only the tree root will be a safe reference, otherwise, we end up with a cycle condition. If safe references are stored in the buffer (in this example as part of the Node type), they will not be destroyed automatically once the safe reference to them goes out of scope. One would have to manually overwrite the data in the buffer. Therefore, having only the root node be a safe node offers enough safety for the entire tree, while the child nodes can be regarded as weak references.
Binary trees using a safe buffer
import SwiftMemoryResource
struct Node {
var left, right: UnsafeRef<Node>?
func check() -> Int {
// End of tree is signalized by left and right node being
// nil.
guard let leftNode = left else {
return 1
}
return 1 + leftNode.ref.check() + right!.ref.check()
}
}
func makeTree(depth: Int, pool: inout SafeMonotonicBuffer) -> UnsafeRef<Node>? {
guard let node = pool.allocateUnsafe(Node.self) else {
return nil
}
if depth > 0 {
node.initialize(to: Node(left: makeTree(depth: depth-1, pool: &pool),
right: makeTree(depth: depth-1, pool: &pool)))
} else {
node.initialize(to: Node(left: nil, right: nil))
}
return node
}
struct BinaryTree {
init(depth: Int, initialize: Bool = true) {
pool = SafeMonotonicBuffer.create(
size: MemoryLayout<Node>.size * (1 << (depth + 1)))
self.depth = depth
if initialize {
root = pool.construct(Node())
root!.left = makeTree(depth: depth-1, pool: &pool)
root!.right = makeTree(depth: depth-1, pool: &pool)
}
}
init(from oldTree: inout BinaryTree, depth: Int) {
pool = oldTree.pool
if !pool.reset() {
fatalError("Pool is locked!")
}
self.depth = oldTree.depth
root = pool.construct(Node())
root!.left = makeTree(depth: depth-1, pool: &pool)
root!.right = makeTree(depth: depth-1, pool: &pool)
}
var root: Ref<Node>?
var pool: SafeMonotonicBuffer
let depth: Int
}
let cmdLineDepth = Int(CommandLine.arguments.count > 1 ? CommandLine.arguments[1] : "10")
let minDepth = 4
let maxDepth = max(cmdLineDepth!, minDepth + 1)
let stretchDepth = maxDepth + 1
// Allocate stretch tree
do {
let tree = BinaryTree(depth: stretchDepth)
print("Stretch tree of depth \(stretchDepth)\t check: \(tree.root!.ref.check())")
}
let longLivingTree = BinaryTree(depth: maxDepth)
var bufferTree = BinaryTree(depth: maxDepth, initialize: false)
for currentDepth in stride(from: minDepth, through: maxDepth, by: 2) {
let iterations = 1 << (maxDepth - currentDepth + minDepth)
var checkSum = 0
for _ in 1...iterations {
let tree = BinaryTree(from: &bufferTree, depth: currentDepth)
checkSum += tree.root!.ref.check()
}
print("\(iterations)\t trees of depth \(currentDepth)\t check: \(checkSum)")
}
// Check long living tree and print out check info
print("long lived tree of depth \(maxDepth)\t check: \(longLivingTree.root!.ref.check())")
Growable and safe buffers require additional logic or safety checks, leading to some performance penalties. But the tradeoffs are manageable.
These are the benchmarks for the different buffer types, all in single threaded tests.
| Memory Resource Type |
Time |
| Monotonic Buffer |
1.80 s |
| Growable Monotonic Buffer |
1.84 s |
| Safe Monotonic Buffer |
2.12 s |
| Safe Growable Monotonic Buffer |
2.18 s |
Here are the implementations for the buffers:
Unsafe Buffer Implementations
@dynamicMemberLookup
public struct UnsafeRef<T> {
public var ref: T {
@_transparent unsafeAddress {
return UnsafePointer(self.pointer)
}
@_transparent nonmutating unsafeMutableAddress {
return self.pointer
}
}
public func initialize(to obj: T) {
self.pointer.initialize(to: obj)
}
public subscript<U>(dynamicMember keyPath: WritableKeyPath<T, U>) -> U {
get {
return ref[keyPath: keyPath]
}
set {
return ref[keyPath: keyPath] = newValue
}
}
public static func == (lhs: UnsafeRef<T>, rhs: UnsafeRef<T>) -> Bool {
return lhs.pointer == rhs.pointer
}
public static func != (lhs: UnsafeRef<T>, rhs: UnsafeRef<T>) -> Bool {
return lhs.pointer != rhs.pointer
}
init(pointer: UnsafeMutablePointer<T>) {
self.pointer = pointer
}
@usableFromInline
var pointer: UnsafeMutablePointer<T>
}
public class Pool {
init(size: Int) {
buffer = UnsafeMutableRawBufferPointer.allocate(
byteCount: size, alignment: MemoryLayout<UInt8>.alignment)
}
deinit {
buffer.deallocate()
}
var buffer: UnsafeMutableRawBufferPointer
var offset: Int = 0
}
public struct MonotonicBuffer {
public mutating func allocate<T>(_ type: T.Type) -> UnsafeRef<T>? {
let requiredSize = MemoryLayout<T>.size
guard pool.offset + requiredSize <= pool.buffer.count else {
return nil
}
let pointer = (pool.buffer.baseAddress! + pool.offset)
.bindMemory(to: T.self, capacity: 1)
pool.offset += requiredSize
return UnsafeRef(pointer: pointer)
}
public mutating func construct<T>(_ object: T) -> UnsafeRef<T>? {
let requiredSize = MemoryLayout<T>.size
guard pool.offset + requiredSize <= pool.buffer.count else {
return nil
}
let pointer = (pool.buffer.baseAddress! + pool.offset)
.bindMemory(to: T.self, capacity: 1)
pointer.initialize(to: object)
pool.offset += requiredSize
return UnsafeRef(pointer: pointer)
}
public mutating func reset() {
pool.offset = 0
}
public static func create(size: Int) -> MonotonicBuffer {
return MonotonicBuffer(size: size)
}
init(size: Int) {
pool = Pool(size: size)
}
var pool: Pool
}
public struct GrowableMonotonicBuffer {
public mutating func allocate<T>(_ type: T.Type) -> UnsafeRef<T> {
let requiredSize = MemoryLayout<T>.size
if currentPool.offset + requiredSize > currentPool.buffer.count {
getNextPool(requiredSize: requiredSize)
}
let pointer = (currentPool.buffer.baseAddress! + currentPool.offset)
.bindMemory(to: T.self, capacity: 1)
currentPool.offset += requiredSize
return UnsafeRef(pointer: pointer)
}
public mutating func construct<T>(_ object: T) -> UnsafeRef<T> {
let requiredSize = MemoryLayout<T>.size
if currentPool.offset + requiredSize > currentPool.buffer.count {
getNextPool(requiredSize: requiredSize)
}
let pointer = (currentPool.buffer.baseAddress! + currentPool.offset)
.bindMemory(to: T.self, capacity: 1)
pointer.initialize(to: object)
currentPool.offset += requiredSize
return UnsafeRef(pointer: pointer)
}
mutating func getNextPool(requiredSize: Int) {
for pool in pools {
if pool.offset + requiredSize <= pool.buffer.count {
currentPool = pool
return
}
}
pools.append(Pool(size: max(newPoolSize, requiredSize)))
currentPool = pools.last!
}
public mutating func reset() {
for pool in pools {
pool.offset = 0
}
currentPool = pools.first!
}
public mutating func reset(poolId: Int) {
if pools.indices.contains(poolId) {
pools[poolId].offset = 0
}
}
public static func create(size: Int) -> GrowableMonotonicBuffer {
return GrowableMonotonicBuffer(size: size, newPoolSize: size)
}
public static func create(size: Int, newPoolSize: Int)
-> GrowableMonotonicBuffer {
return GrowableMonotonicBuffer(size: size, newPoolSize: newPoolSize)
}
init(size: Int, newPoolSize: Int) {
pools = [Pool(size: size)]
currentPool = pools.first!
self.newPoolSize = newPoolSize
}
var pools: [Pool]
var currentPool: Pool
var newPoolSize: Int
}
Safe Buffer Implementations
@dynamicMemberLookup
public struct Ref<T> {
public var ref: T {
@_transparent unsafeAddress {
return UnsafePointer(self.pointer)
}
@_transparent nonmutating unsafeMutableAddress {
return self.pointer
}
}
public func initialize(to obj: T) {
self.pointer.initialize(to: obj)
}
public subscript<U>(dynamicMember keyPath: WritableKeyPath<T, U>) -> U {
get {
return ref[keyPath: keyPath]
}
set {
return ref[keyPath: keyPath] = newValue
}
}
public static func == (lhs: Ref<T>, rhs: Ref<T>) -> Bool {
return lhs.pointer == rhs.pointer
}
public static func != (lhs: Ref<T>, rhs: Ref<T>) -> Bool {
return lhs.pointer != rhs.pointer
}
init(pointer: UnsafeMutablePointer<T>, lock: SafePool.Lock) {
self.pointer = pointer
self.lock = lock
}
@usableFromInline
var pointer: UnsafeMutablePointer<T>
private let lock: SafePool.Lock
}
public class SafePool {
class Lock {
init(_ pool: SafePool) {
self.pool = pool
self.pool.locked = true
}
deinit {
pool.locked = false
}
var pool: SafePool
}
init(size: Int) {
buffer = UnsafeMutableRawBufferPointer.allocate(
byteCount: size,alignment: MemoryLayout<UInt8>.alignment)
}
deinit {
buffer.deallocate()
}
var buffer: UnsafeMutableRawBufferPointer
var offset: Int = 0
var locked: Bool = false
unowned var lock: Lock = unsafeBitCast(0, to: Lock.self)
}
public struct SafeMonotonicBuffer {
public mutating func allocate<T>(_ type: T.Type) -> Ref<T>? {
let requiredSize = MemoryLayout<T>.size
guard pool.offset + requiredSize <= pool.buffer.count else {
return nil
}
let pointer = (pool.buffer.baseAddress! + pool.offset)
.bindMemory(to: T.self, capacity: 1)
pool.offset += requiredSize
if !pool.locked {
let lock = SafePool.Lock(pool)
pool.lock = lock
return Ref(pointer: pointer, lock: lock)
}
return Ref(pointer: pointer, lock: pool.lock)
}
public mutating func allocateUnsafe<T>(_ type: T.Type) -> UnsafeRef<T>? {
let requiredSize = MemoryLayout<T>.size
guard pool.offset + requiredSize <= pool.buffer.count else {
return nil
}
let pointer = (pool.buffer.baseAddress! + pool.offset)
.bindMemory(to: T.self, capacity: 1)
pool.offset += requiredSize
return UnsafeRef(pointer: pointer)
}
public mutating func construct<T>(_ object: T) -> Ref<T>? {
let requiredSize = MemoryLayout<T>.size
guard pool.offset + requiredSize <= pool.buffer.count else {
return nil
}
let pointer = (pool.buffer.baseAddress! + pool.offset)
.bindMemory(to: T.self, capacity: 1)
pointer.initialize(to: object)
pool.offset += requiredSize
if !pool.locked {
let lock = SafePool.Lock(pool)
pool.lock = lock
return Ref(pointer: pointer, lock: lock)
}
return Ref(pointer: pointer, lock: pool.lock)
}
public mutating func constructUnsafe<T>(_ object: T) -> UnsafeRef<T>? {
let requiredSize = MemoryLayout<T>.size
guard pool.offset + requiredSize <= pool.buffer.count else {
return nil
}
let pointer = (pool.buffer.baseAddress! + pool.offset)
.bindMemory(to: T.self, capacity: 1)
pointer.initialize(to: object)
pool.offset += requiredSize
return UnsafeRef(pointer: pointer)
}
@discardableResult
public func reset() -> Bool {
if !pool.locked {
pool.offset = 0
return true
}
return false
}
public static func create(size: Int) -> SafeMonotonicBuffer {
return SafeMonotonicBuffer(size: size)
}
init(size: Int) {
pool = SafePool(size: size)
}
var pool: SafePool
}
public struct SafeGrowableMonotonicBuffer {
public mutating func allocate<T>(_ type: T.Type) -> Ref<T> {
let requiredSize = MemoryLayout<T>.size
if currentPool.offset + requiredSize > currentPool.buffer.count {
getNextPool(requiredSize: requiredSize)
}
let pointer = (currentPool.buffer.baseAddress! + currentPool.offset)
.bindMemory(to: T.self, capacity: 1)
currentPool.offset += requiredSize
if !currentPool.locked {
let lock = SafePool.Lock(currentPool)
currentPool.lock = lock
return Ref(pointer: pointer, lock: lock)
}
return Ref(pointer: pointer, lock: currentPool.lock)
}
public mutating func allocateUnsafe<T>(_ type: T.Type) -> UnsafeRef<T> {
let requiredSize = MemoryLayout<T>.size
if currentPool.offset + requiredSize > currentPool.buffer.count {
getNextPool(requiredSize: requiredSize)
}
let pointer = (currentPool.buffer.baseAddress! + currentPool.offset)
.bindMemory(to: T.self, capacity: 1)
currentPool.offset += requiredSize
return UnsafeRef(pointer: pointer)
}
public mutating func construct<T>(_ object: T) -> Ref<T> {
let requiredSize = MemoryLayout<T>.size
if currentPool.offset + requiredSize > currentPool.buffer.count {
getNextPool(requiredSize: requiredSize)
}
let pointer = (currentPool.buffer.baseAddress! + currentPool.offset)
.bindMemory(to: T.self, capacity: 1)
pointer.initialize(to: object)
currentPool.offset += requiredSize
if !currentPool.locked {
let lock = SafePool.Lock(currentPool)
currentPool.lock = lock
return Ref(pointer: pointer, lock: lock)
}
return Ref(pointer: pointer, lock: currentPool.lock)
}
public mutating func constructUnsafe<T>(_ object: T) -> UnsafeRef<T> {
let requiredSize = MemoryLayout<T>.size
if currentPool.offset + requiredSize > currentPool.buffer.count {
getNextPool(requiredSize: requiredSize)
}
let pointer = (currentPool.buffer.baseAddress! + currentPool.offset)
.bindMemory(to: T.self, capacity: 1)
pointer.initialize(to: object)
currentPool.offset += requiredSize
return UnsafeRef(pointer: pointer)
}
@discardableResult
public mutating func reset() -> Bool {
var didReset = false
for pool in pools {
if !pool.locked {
pool.offset = 0
didReset = true
}
}
return didReset
}
@discardableResult
public mutating func reset(poolId: Int) -> Bool {
if pools.indices.contains(poolId) && !pools[poolId].locked {
pools[poolId].offset = 0
return true
}
return false
}
public static func create(size: Int) -> SafeGrowableMonotonicBuffer {
return SafeGrowableMonotonicBuffer(size: size, newPoolSize: size)
}
public static func create(size: Int, newPoolSize: Int)
-> SafeGrowableMonotonicBuffer {
return SafeGrowableMonotonicBuffer(size: size, newPoolSize: newPoolSize)
}
mutating func getNextPool(requiredSize: Int) {
for pool in pools {
if pool.offset + requiredSize <= pool.buffer.count {
currentPool = pool
return
}
}
pools.append(SafePool(size: max(newPoolSize, requiredSize)))
currentPool = pools.last!
}
init(size: Int, newPoolSize: Int) {
pools = [SafePool(size: size)]
currentPool = pools.first!
self.newPoolSize = newPoolSize
}
var pools: [SafePool]
var currentPool: SafePool
var newPoolSize: Int
}
Does this approach meet what you were looking for? I welcome any thoughts or feedback you might have.
