Can I allocate indirect enum on stack?

Using Swift
1

I really really don't want to allocate it on the heap - but due to the domain limitations, I can not make it non-indirect.

My objects are used only in a very local scope, inside one single function. I just calculate some stuff and then release everything.

I have a setup like this:

struct Foo {}

struct Bar {
     let somethings: [Something]
} 

indirect enum Something {
     case foo(Foo)
     case bar(Bar) 
}

Soooo can somebody tell me, how do I know, where the compiler will decide to allocate?

2

I’m not sure from the code you’ve provided the use of indirect enum anywhere. This example stores enums inline (on stack… kinda). The only thing that allocates is the somethings array.

Since arrays allocate their storage on the heap, there is no need for an additional indirection. An indirect enum it would be needed to make the type’s memory layout non-recursive.

If you wanted to optimize allocations (utilize a temporary fixed-size on-stack buffer or an arena allocator) this is a lot more tricky in swift. AFAIK swift doesn’t support plugging-in custom allocators for the arrays. You can do UnsafeBuffer trickery yourself to do that (all of the C knowledge of memory management apply here). Just don’t expect standard library containers to help you there.

3

I have updated the example

4

The simple answer is no.

2 Likes
5

As long as the size of the data structure isn't known until run time, you can't eliminate the heap allocation, but you could conceivably store all of your enum values in an array, and replace the indirect cases with indices into this array. If the enum type then becomes BitwiseCopyable, it should be pretty efficient to fill this array and then destroy it at the end.

5 Likes
6

As written – yes, you can, just remove indirect.

As for avoiding the heap allocation (that's due to array) if you really want to do that – do those arrays have an upper bound of the item count? Is that max count small?

Provided the maximum depth of your structures is small enough you'd be able "allocating" the somethings on stack, e.g. for the list of a few items you'd call some function recursively a few times. A sketch implementation that avoids heap allocation:

struct Foo {
    let payload: Int
}

struct Bar {
    let something: UnsafePointer<Something>?
    let payload: Int
}

enum Something {
    case foo(Foo)
    case bar(Bar)
}

Usage:

for _ in 0 ..< 10 {
    Something.random { something in
        print(something)
    }
}
Details 
extension Foo: CustomStringConvertible {
    static func random(execute: (Self) -> Void) {
        execute(Foo(payload: .random(in: 0 ... 100)))
    }
    public var description: String {
        "\(payload) "
    }
}

extension Bar: CustomStringConvertible {
    static func notSoRandom(something: UnsafePointer<Something>?, execute: (Self) -> Void) {
        execute(Bar(something: something, payload: .random(in: 0 ... 100)))
    }
    public var description: String {
        if let something {
            " \(payload) -> \(something.pointee)"
        } else {
            " \(payload) -> nil "
        }
    }
}

extension Something: CustomStringConvertible {
    static func random(execute: (Self) -> Void) {
        if .random() {
            Foo.random { foo in
                execute(.foo(foo))
            }
        } else {
            if .random() {
                Something.random { something in
                    var something = something
                    Bar.notSoRandom(something: &something) { bar in
                        execute(.bar(bar))
                    }
                }
            } else {
                Bar.notSoRandom(something: nil) { bar in
                    execute(.bar(bar))
                }
            }
        }
    }
    public var description: String {
        switch self {
            case .foo(let foo):
                "Foo \(foo) "
            case .bar(let bar):
                "Bar \(bar) "
        }
    }
}

Example that generates and plots random data structures:

Bar  92 -> Bar  85 -> Foo 86    
Foo 50  
Foo 66  
Foo 93  
Bar  29 -> Bar  70 -> Bar  78 -> nil    
Foo 7  
Foo 75  
Foo 31  
Bar  24 -> nil  
Bar  7 -> nil

Key points:

  • no heap allocation! †
  • using linked lists instead of arrays
  • callback-style API
  • a non-callback style API is possible but more tricky.
  • UnsafePointer's are used"safely" here, i.e. the app won't be able to crash due to unsafety of those UnsafePointer's ††. Unfortunately there is no way in current Swift to express this without using "Unsafe" word †††.

† no heap allocation "for the data structures themselves" I mean. In this app there will be obvious heap allocation due to usage of strings for logging

†† the app could still crash e.g. due to stack overflow unless you put some limits on the data structure depth

††† or is there a way to express this without Unsafe?

2 Likes