Safe memory optimization: explicit stack allocation, static arrays, ascii

Evolution Discussion
, ,
1

Are there any plans to add for example stack and heap keywords to explicitly force a variable to be allocated in a specific way? :slight_smile:
Ideally with the ability to declare a fixed size array like in other systems languages?
something like:

stack let array: FixedSizeArray<Character, 3> = [ 'a', 'b', 'c']

It would be really nice to stop worrying about what Swift might be doing to my variables. I would prefer to get a compilation error when trying to do something that requires heap allocation rather than Swift silently making my code slower

This is also related to having a lighter stack allocated String type; I probably don't need emoji support etc when I'm writing a server application or game.

I'd like to mention this discussion:

I find myself learning things that should be unnecessary to use the language, watching a lot of wwdc sessions only to have a very uncertain understanding of where my variable might be allocated, or having to debug my code to check if it actually does what I want.

1 Like
2

Why do you care about where things are allocated ?

3

You can make fixed size array using tuples or structs. Search for fixed size array in the forum IIRC there are multiples discutions about this. For strings you can use the utf8 view or use byte array for manipulating ascii. Do you have a benchmark showing unreasonable memory use ?
As a simple rule when using primitives in struct itā€™s allocated on the stack while using classes make it goes to the heap. Thought there are exceptions notably cow types like arrays or strings.
You donā€™t need swift strings capabilities until you need it. Letā€™s say you implement search on server, string abstractions will be of great help when using languages using things as simple as Ā“Ć©ā€™.

Now Iā€™m in unverified territory but swift string is actually quite smart and depending on the size and content of it it can be stored on the stack. Iā€™ll let more knowledgeable people correct me.

4

String will be stored inline if itā€™s <= 15 bytes long, yeah

5

I have searched for this a lot, I know I can use a tuple and that it has the memory layout of a C array. It's not reasonable for a large array, and it's not comfortable to use in general. I already tried horrible tricks like manually using ascii, it makes Swift less readable than C++

Let's say I have a folder of textures. I can load them all with a single loop into a dictionary, using the file name as the key and the raw data as value. This makes it extremely nice to use, because I can just refer to textures by their name in my code, no additional boilerplate required. Because it's a Swift String however, a complicated unicode type, it will affect performance when there's only milliseconds to handle a frame.

Am I going to need any of the functionality of the Swift String? not really :confused:

This is exactly what I'm talking about :pensive: Why do I need to know obscure compiler optimisations to allocate memory efficiently? A simple stack keyword that explicitly tells the compiler and people reading the code how a variable is meant to be stored is so much nicer. It's great that Swift does things automatically, makes it really simple to learn in the beginning, but there's seemingly no tools to take control when necessary.

1 Like
6

Not a compiler optimization, fwiw. The standard library implements that all by hand in pure Swift. String is internally either (UInt64, UInt64) or a struct with a pointer to malloc'd storage.

11 Likes
7

There is also:

2 Likes
8

Either way, the point is that there's no way to explicitly allocate memory on the stack, not that String is too heavy.

9

Davidā€™s point is that there isnā€™t some ā€œobscureā€ compiler magic that String uses to allocate on the stack; itā€™s just (UInt64, UInt64), which is available for your use too.

What is the use case you have in mind for a heap keyword?

1 Like
10

Strictly speaking, C doesnā€™t guarantee that memory is allocated on the stack either. It only specifies that local variables have automatic storage duration. Thatā€™s effectively the same behavior that Swift specifies for value types.

3 Likes
11

That would be an interesting although quite a niche feature, e.g. we then would be able using arrays within real time code (although in many cases on top of that we'd also need related realtime-safe guarantees from data structures / compiler code).

Note that "Character" type can live on heap if it's a large multibyte character, but I got your idea. E.g. this:

stack let array: FixedSizeArray = [ 1, 2, 3]

Why the keyword, could it be just this:

var array: FixedSizeStackArray = [ 1, 2, 3]

Note that other languages have alloca that allows allocating memory from stack, so it may even be a variable length structure (up to a reasonable limit).

And if it was indeed based on the "stack" keyword or its absence then I'd expect it working with normal data types:

stack let array = [1, 2, 3]

Emoji's and other non ascii characters can be in user generated content / user names, file names, etc. But indeed there are situations when stack allocated values would be enough and desired.

1 Like
12

True, heap doesn't seem particularly useful.
I thought it would allocate the memory on the heap and give you a reference to it, kind of how classes work but without reference counting.

Okay, but does that mean to allocate memory the programmer should read not just the documentation and watch all the Swift WWDC videos now, but understand the standard library itself at a low level? It doesn't really matter if it's a compiler optimisation or how String is implemented, this is not a good learning experience.
Swift is a great language to learn in the beginning, you can learn new features at your own pace. At the point where you want more control however, you're on your own.

This is the opposite problem to Rust, which throws everything at you at the start, but once you figure it out it's fine, and the documentation is very detailed.

1 Like
13

Yeah, it would be more intuitive if the compiler could deduce a fixed size array type from this if the stack keyword is used, however sometimes you need the ability to explicitly declare the type like this:

FixedSizeArray<ofType, Capacity>

Then you can for example easily declare a fixed size array with a capacity, even when it's empty:

stack var buffer: FixedSizeArray<Int8, 128> = []

Keyword

I think a keyword is a good idea, then most people can just ignore this functionality and let Swift decide.

I think features like this are necessary if Swift is to someday be used for embedded programming, performance critical server applications, games, or "an entire operating system"

1 Like
14

Interesting. Such implementation would be a hassle to deal with from realtime C programmer's perspective.

What guarantee swift gives about POD struct / tuple types? Is it safe to assume that a small struct like this will be on stack?

struct P {
    var x: Int
    var y: Int
}

What about the same struct of Ints just with 10K of Int fields (assuming this compiles fine)?

When I wrap a reasonably small POD struct (say, 100 Ints) into Any and pass it that Any around there'll be heap allocation, right? And ditto if I pass that struct value around in existential form? I'd also assume heap promotion happening for closures closures' captured variables (even for values like Int). ā€ 

ā€  this is no different from C, where you can put anything on heap consciously even if the value in question allows stack storage, e.g. "int x[10].

1 Like
15

I just want to point out here that in the context of real time algorithms you have to be careful with all kinds of allocations, that definitely includes stack allocations. The pages backing the stack still have to be faulted in on first use, and the use of (especially large) stack-allocated structures only exacerbates this problem. It is far better to operate on pre-allocated data in these contexts, calling well-known functions with well-known (ideally constant-time) complexities that make no allocations and take no locks. For these, Swift provides some experimental attributes @_noLocks and @_noAllocation.

13 Likes
16

the compiler understands a lot about Array that it doesn't about collection types in general, so i wouldnā€™t be surprised if it already figured out it could allocate the 3 elements on the stack. (not at a computer but maybe you could godbolt it?)

when i write custom collections i always try to make them transparently backed by an Array and @inlinable all the way through so they can also get high-level SIL optimizations

17

But that can be said about any memory unless it is pinned, IIUC. You preallocate memory somewhere (e.g. using block = malloc(1000_000), initialise it, didn't use it for some time, then access "block[8192]" - this location happens to be already wired in ā€“ so far so good ā€“ then you access the next byte: "block[8193]" - and here you are not so lucky, page fault occurs. To some extent the issue is less prominent for stack memory as stack is typically "hot", i.e. it can shrink / expand rapidly from, say, 1K to 100K and back, sometimes many times a second, such hot memory tends to be in RAM.

Very true.

18

While I do think a stack keyword might be a nice feature, it wouldn't help with strings, because String is not a simple array of characters like in C, it's a wrapper around a reference counted object that implements CoW semantics, all of which is implemented in the stdlib, not by the compiler. A stack allocated string would require a completely different implementation.

3 Likes
19

You could look into using alloca for your needs or the Swift preferred API: withUnsafeTemporaryAllocation

1 Like
20

This is why I mentioned having a different, simple C like string implementation; it is possible currently by manually writing the ascii values into a tuple, (or by converting everything to ascii but thatā€™s equally hard to read) however this is probably the most boilerplate way to use strings ever.

One idea would be to have new ascii String and Character types, that could be used manually by declaring the type as something like AsciiString and AsciiCharacter, kind of how thereā€™s the ability to explicitly declare a ContiguousArray.

The cool way this could interact with the stack keyword, and why I mentioned both, is that if you were to write something like:

stack var string = ā€œHello, worldā€

This makes sense to infer an AsciiString, and should probably show an error if a special character or emote is used.
Thanks to the keyword, using the high performance string type would be as easy as using a normal string.

This also applies to characters, it would be nice to declare ascii characters like this:

stack let char = ā€˜aā€™

And one more type that was already mentioned and makes sense to be affected by stack in this way is an array, declaring a stack array should infer a static array; this would be great for C interoperability as well as performance.

So essentially, the stack keyword could be a way to not only tell the compiler to allocate on the stack, but also change which types are inferred. I think this would fit in with the design of Swift, itā€™s intuitive and powerful, and most importantly an optional feature that can just be ignored when first learning the language.