Implementation of swift's value types

[Johannes_Neubauer1 (Johannes Neubauer)]

Dear Devs,

I saw the WWDC 2016 video [Understanding Swift Performance][0] as well as some others regarding value types in swift of WWDC2015. I think there are a few ambiguities which make it hard both to decide which weapon to choose and to give proposition how to evolve this implementations to the better (swift-evolution).

Is there a place, where low-level decisions in the language are documented? Is there an adequate place/forum where we can ask questions regarding low-level implementations? It would be great if you add a (moderated) comment section to each of the WWDC videos, so that we can discuss the contents (with transcript-like links) as well as an errata section containing a list of Apple-Approved mistakes/ambiguities in a given video/talk.

# So, here come my questions

In the talk [Understanding Swift Performance][0] Kyle says, that value types are put stored in the stack and copied. He uses a point and a line which are both copied. Lateron Arnold uses a similar example with protocols. Then the Existential Container is used, which either uses the value buffer (for small values like `Point`) or allocates some memory on the heap and adds a pointer to this value (e.g. for a `Line`):

1. If I have an object (instance of a class) in a variable (or a container like an array) of a protocol type, will it be stored into an Existential Container, too? Or are reference types always stored as a reference (storing it in an Existential Container makes more sense to me).
2. If I use a variable of the concrete type (although it implements a protocol), will it always be copied (no matter its size) or does the compiler choose an existential container if it is greater than some given size (or perhaps even always, because it gives a good tradeoff?)
3. Then Arnold says that four existential containers pointing to the same value (greater than the value buffer) use 4 heap allocations. He proposes copy-on-write (using a local storage class), but **does he mean this should be implemented by hand or is this an optimization that the swift compiler does on its own?** The issue here is, that the switch between "swift subscript" for showing an abstraction of internals and real swift code that one should write is sometimes not clear. Doing this by hand has some clear disadvantages as this would add a reference to each usage of `Line` (and reference counting) even in the first examples of Kyle. Doing this as a compiler optimization would allow to use a struct in different scenarios and always the best tradeoff is used. Otherwise, I would perhaps even need to create two different types for different situations and choose it wisely. This would add a big burden on the developer.
4. If Arnold really means *manually* (see *3.*) and reference types are not stored in existential containers (see *1.*) the slides are wrong, because there a existential container is still used and the instance on the heap is named `Line` instead of `Line._storage`. So what is the case?
5. The implementations of `String` and `Array` seem to follow the copy-on-write strategy "manually", but I think they do that because this behavior is wanted even if the values would be copied automatically (if this is true, the answer for *3.* would be *manually*). Or am I wrong here?
6. Is the Value-Witness-Table a (kind of) dictionary for all values of a given value type (bigger than the value buffer), so that you do not store any value twice on the heap, but share the reference? If this is the case the answer of *3.* should be *automatically*. But then again, the "manual" implementation of `String` and `Array` (see *4.*) make no sense anymore, does it? Or are `Array` and `String` implemented only on the lower-level and the copy-on-write implementation is not visible in their Swift implementation?
7. If you want to have a reference-type (like `NSData`) with value semantics, then I need to implement my own copy-on-write of course, but if I want to have it only on the swift-value-type level the compiler should be able to do it all by itself, shouldn't it?

I read some [posts like this one][1] describing how Swift implements value types in a manner, that is conflicting with some of the things Kyle and Arnold said on WWDC 2016 (see above). Did Swift’s implementation change here between v2 and v3 or what do you think? The articles interpretation of the changes of the memory address (and the padding ints for the address struct; see the post) suggest, that always an existential container is used for structs (see *2.*) and copy-on-write is done automatically (see *3.*)…

It would be great, if someone could give me the answers to these questions :). Thanks in advance.

All the best
Johannes

[0]: Understanding Swift Performance - WWDC16 - Videos - Apple Developer
[1]: Reference vs. Value Types in Swift | raywenderlich.com

···

--
Dr. Johannes Neubauer
E-Mail: neubauer@kingsware.de
WWW : http://www.kingsware.de

[Arnold (Arnold Schwaighofer)]

Hi Johannes,

thank you for your questions. Answers inline.

Dear Devs,

I saw the WWDC 2016 video [Understanding Swift Performance][0] as well as some others regarding value types in swift of WWDC2015. I think there are a few ambiguities which make it hard both to decide which weapon to choose and to give proposition how to evolve this implementations to the better (swift-evolution).

Is there a place, where low-level decisions in the language are documented? Is there an adequate place/forum where we can ask questions regarding low-level implementations?

I think here is a good place to ask such questions.

It would be great if you add a (moderated) comment section to each of the WWDC videos, so that we can discuss the contents (with transcript-like links) as well as an errata section containing a list of Apple-Approved mistakes/ambiguities in a given video/talk.

# So, here come my questions

In the talk [Understanding Swift Performance][0] Kyle says, that value types are put stored in the stack and copied. He uses a point and a line which are both copied. Lateron Arnold uses a similar example with protocols. Then the Existential Container is used, which either uses the value buffer (for small values like `Point`) or allocates some memory on the heap and adds a pointer to this value (e.g. for a `Line`):

1. If I have an object (instance of a class) in a variable (or a container like an array) of a protocol type, will it be stored into an Existential Container, too? Or are reference types always stored as a reference (storing it in an Existential Container makes more sense to me).

Yes, the reference to the instance is stored inside the existential container. It fits into the three word value buffer and not out of line allocation for the existential container’s value buffer is necessary.

2. If I use a variable of the concrete type (although it implements a protocol), will it always be copied (no matter its size) or does the compiler choose an existential container if it is greater than some given size (or perhaps even always, because it gives a good tradeoff?)

Assuming you talk about value types like “struct Line”. Yes it will be copied. If you want to make the storage of a struct type indirect you have to wrap it in a class (similar to the IndirectStorage example).

3. Then Arnold says that four existential containers pointing to the same value (greater than the value buffer) use 4 heap allocations. He proposes copy-on-write (using a local storage class), but **does he mean this should be implemented by hand or is this an optimization that the swift compiler does on its own?**

No the swift compiler does not do this on its own.

The issue here is, that the switch between "swift subscript" for showing an abstraction of internals and real swift code that one should write is sometimes not clear.

Sorry about this.

Doing this by hand has some clear disadvantages as this would add a reference to each usage of `Line` (and reference counting) even in the first examples of Kyle.

Yes, it is a tradeoff. Either, in the type erased context (as an instance of protocol value) copies are expensive for large value types and in the non generic/existential concrete context it is fast. Or you make the type have indirect storage with copy on write to preserve value semantics and then you have an overhead for reference counting.

You can get the best of both worlds if you write a wrapper.

All of this comes at the cost of a lot of boiler plate code and discussions are taking place how-to improve this situation.

Doing this as a compiler optimization would allow to use a struct in different scenarios and always the best tradeoff is used. Otherwise, I would perhaps even need to create two different types for different situations and choose it wisely. This would add a big burden on the developer.

There are things that we can do in the compiler (change the representation of generics and protocol values) that will improve the situation.

These would be future changes ...

4. If Arnold really means *manually* (see *3.*) and reference types are not stored in existential containers (see *1.*) the slides are wrong, because there a existential container is still used and the instance on the heap is named `Line` instead of `Line._storage`. So what is the case?

Yes the suggestion was do manually do this. Reference types are stored in existential container.

5. The implementations of `String` and `Array` seem to follow the copy-on-write strategy "manually", but I think they do that because this behavior is wanted even if the values would be copied automatically (if this is true, the answer for *3.* would be *manually*). Or am I wrong here?

The answer to 3. is manually.

6. Is the Value-Witness-Table a (kind of) dictionary for all values of a given value type (bigger than the value buffer), so that you do not store any value twice on the heap, but share the reference? If this is the case the answer of *3.* should be *automatically*. But then again, the "manual" implementation of `String` and `Array` (see *4.*) make no sense anymore, does it? Or are `Array` and `String` implemented only on the lower-level and the copy-on-write implementation is not visible in their Swift implementation?

I don’t full understand the question.

The value-witness-table exists per type and contains functions that describe how to copy, allocate, and deallocate values of that type.

The copy-on-write implementation is visible in standard library code for Array and String: array really calls isUniquelyReference for example before it does a subscript set.

7. If you want to have a reference-type (like `NSData`) with value semantics, then I need to implement my own copy-on-write of course, but if I want to have it only on the swift-value-type level the compiler should be able to do it all by itself, shouldn't it?

I read some [posts like this one][1] describing how Swift implements value types in a manner, that is conflicting with some of the things Kyle and Arnold said on WWDC 2016 (see above). Did Swift’s implementation change here between v2 and v3 or what do you think? The articles interpretation of the changes of the memory address (and the padding ints for the address struct; see the post) suggest, that always an existential container is used for structs (see *2.*) and copy-on-write is done automatically (see *3.*)…

It would be great, if someone could give me the answers to these questions :). Thanks in advance.

This blog post draws the wrong conclusion from what it observes. Plain struct types are not copy on write. But really create a copy.

The test case in the blog post really shows that the string stored in the variable “streetAddress” changes. He overlays the memory of “struct Address” with “struct AddressBits”. If you read "bits1.underlyingPtr” you get whatever is the first 4/8bytes (32bit/64bit pointer platform) of the String struct instance stored in Address.streetAddress. If you dig deep enough into the implementation of Swift’s string https://github.com/apple/swift/blob/master/stdlib/public/core/StringCore.swift\. You will see that this is a variable that holds a pointer (the pointer to the String’s storage).

Best,
Arnold

···

On Jul 14, 2016, at 12:39 PM, Johannes Neubauer via swift-dev <swift-dev@swift.org> wrote:

[Andrew_Trick]

Dear Devs,

I saw the WWDC 2016 video [Understanding Swift Performance][0] as well as some others regarding value types in swift of WWDC2015. I think there are a few ambiguities which make it hard both to decide which weapon to choose and to give proposition how to evolve this implementations to the better (swift-evolution).

Is there a place, where low-level decisions in the language are documented? Is there an adequate place/forum where we can ask questions regarding low-level implementations? It would be great if you add a (moderated) comment section to each of the WWDC videos, so that we can discuss the contents (with transcript-like links) as well as an errata section containing a list of Apple-Approved mistakes/ambiguities in a given video/talk.

# So, here come my questions

In the talk [Understanding Swift Performance][0] Kyle says, that value types are put stored in the stack and copied. He uses a point and a line which are both copied. Lateron Arnold uses a similar example with protocols. Then the Existential Container is used, which either uses the value buffer (for small values like `Point`) or allocates some memory on the heap and adds a pointer to this value (e.g. for a `Line`):

1. If I have an object (instance of a class) in a variable (or a container like an array) of a protocol type, will it be stored into an Existential Container, too? Or are reference types always stored as a reference (storing it in an Existential Container makes more sense to me).

In that case the value stored in the existential container is just the reference. There’s no additional heap allocation.

Promoting objects to the stack is a separate thing that I think will only happen if the existential container is already optimized away.

2. If I use a variable of the concrete type (although it implements a protocol), will it always be copied (no matter its size) or does the compiler choose an existential container if it is greater than some given size (or perhaps even always, because it gives a good tradeoff?)

A value's representation starts off as the representation for whatever type is in the declaration. For something declared as a struct, it’s irrelevant whether the type also conforms to a protocol. We don’t yet provide a language feature or optimization for indirect copy-on-write struct storage.

3. Then Arnold says that four existential containers pointing to the same value (greater than the value buffer) use 4 heap allocations. He proposes copy-on-write (using a local storage class), but **does he mean this should be implemented by hand or is this an optimization that the swift compiler does on its own?** The issue here is, that the switch between "swift subscript" for showing an abstraction of internals and real swift code that one should write is sometimes not clear. Doing this by hand has some clear disadvantages as this would add a reference to each usage of `Line` (and reference counting) even in the first examples of Kyle. Doing this as a compiler optimization would allow to use a struct in different scenarios and always the best tradeoff is used. Otherwise, I would perhaps even need to create two different types for different situations and choose it wisely. This would add a big burden on the developer.

It needs be done by hand because the compiler doesn’t do it. The compiler *should* do it in the sense that it would make the world a better place.

4. If Arnold really means *manually* (see *3.*) and reference types are not stored in existential containers (see *1.*) the slides are wrong, because there a existential container is still used and the instance on the heap is named `Line` instead of `Line._storage`. So what is the case?

I don’t have the slides in front of me, but the instance is always on the heap (modulo stack promotion, which doesn’t happen for existentials). The reference to the instance is in the container.

5. The implementations of `String` and `Array` seem to follow the copy-on-write strategy "manually", but I think they do that because this behavior is wanted even if the values would be copied automatically (if this is true, the answer for *3.* would be *manually*). Or am I wrong here?

There’s no observable behavior to copy-on-write other than the program running much faster.

6. Is the Value-Witness-Table a (kind of) dictionary for all values of a given value type (bigger than the value buffer), so that you do not store any value twice on the heap, but share the reference? If this is the case the answer of *3.* should be *automatically*. But then again, the "manual" implementation of `String` and `Array` (see *4.*) make no sense anymore, does it? Or are `Array` and `String` implemented only on the lower-level and the copy-on-write implementation is not visible in their Swift implementation?

A value witness table is a dictionary for all values of a type regardless of whether it fits in a buffer. The keys are operations that can be done to any value (copy/destroy), the implementation for that type knows where the value is stored.

7. If you want to have a reference-type (like `NSData`) with value semantics, then I need to implement my own copy-on-write of course, but if I want to have it only on the swift-value-type level the compiler should be able to do it all by itself, shouldn't it?

Someone else can provide a better answer. I’ll say that the compiler *should* be able to do it in the sense that the world would be better off for it…

-Andy

···

On Jul 14, 2016, at 12:39 PM, Johannes Neubauer via swift-dev <swift-dev@swift.org> wrote:

I read some [posts like this one][1] describing how Swift implements value types in a manner, that is conflicting with some of the things Kyle and Arnold said on WWDC 2016 (see above). Did Swift’s implementation change here between v2 and v3 or what do you think? The articles interpretation of the changes of the memory address (and the padding ints for the address struct; see the post) suggest, that always an existential container is used for structs (see *2.*) and copy-on-write is done automatically (see *3.*)…

It would be great, if someone could give me the answers to these questions :). Thanks in advance.

All the best
Johannes

[0]: Understanding Swift Performance - WWDC16 - Videos - Apple Developer
[1]: https://www.raywenderlich.com/112029/reference-value-types-in-swift-part-2

--
Dr. Johannes Neubauer
E-Mail: neubauer@kingsware.de
WWW : http://www.kingsware.de

_______________________________________________
swift-dev mailing list
swift-dev@swift.org
https://lists.swift.org/mailman/listinfo/swift-dev

[Johannes_Neubauer1 (Johannes Neubauer)]

Hi Arnold,

Thank you and atrick@apple.com very much for your answers. That helps already a lot. Are you Arnold from the WWDC Video? I removed all the answers that are clear and have some follow-up questions inline.

3. Then Arnold says that four existential containers pointing to the same value (greater than the value buffer) use 4 heap allocations. He proposes copy-on-write (using a local storage class), but **does he mean this should be implemented by hand or is this an optimization that the swift compiler does on its own?**

No the swift compiler does not do this on its own.

Are there corresponding plans? Storing „big“ values (using some statistics to evaluate where the break-even is) as reference types always, storing them in a big table per type (each value occurs only once) should be possible, right? Is this something I should post on the swift-evolution mailing list?

The issue here is, that the switch between "swift subscript" for showing an abstraction of internals and real swift code that one should write is sometimes not clear.

Sorry about this.

This was meant as positive criticism. I really like the video!

Doing this by hand has some clear disadvantages as this would add a reference to each usage of `Line` (and reference counting) even in the first examples of Kyle.

Yes, it is a tradeoff. Either, in the type erased context (as an instance of protocol value) copies are expensive for large value types and in the non generic/existential concrete context it is fast.

Is it really fast in the latter context for „big“ values? All collection types use copy-on-write. Especially if you have a lot of reference type properties copying seems to be slow even in the latter context. And since all collection types (including String) are backed by a reference type, even properties of these type incur additional reference counting.

Or you make the type have indirect storage with copy on write to preserve value semantics and then you have an overhead for reference counting.

You can get the best of both worlds if you write a wrapper.

All of this comes at the cost of a lot of boiler plate code and discussions are taking place how-to improve this situation.

Are there already proposals available or is it still in early discussions? Can you give me a hint where to find more about it?

6. Is the Value-Witness-Table a (kind of) dictionary for all values of a given value type (bigger than the value buffer), so that you do not store any value twice on the heap, but share the reference? If this is the case the answer of *3.* should be *automatically*. But then again, the "manual" implementation of `String` and `Array` (see *4.*) make no sense anymore, does it? Or are `Array` and `String` implemented only on the lower-level and the copy-on-write implementation is not visible in their Swift implementation?

I don’t full understand the question.

The value-witness-table exists per type and contains functions that describe how to copy, allocate, and deallocate values of that type.

OK. I am still a little bit unsure what it is now. Andrew Trick says:

A value witness table is a dictionary for all values of a type regardless of whether it fits in a buffer.
The keys are operations that can be done to any value (copy/destroy), the implementation for
that type knows where the value is stored.

In the example Arnold (you?) used the value witness table to copy the value (see slide 171 last line of code):

pwt.draw(vwt.projectBuffer(&local))

Since I didn’t know that the „storage“-trick is done manually, I thought there is a (hash)table/dictionary of all values of a „big“ value type where each value is uniquely stored (constant time access). For „small“ values it would just point, to the concrete value of this very value. As mentioned above: should I post this on the swift-evolution mailing list?

All the best
Johannes

···

Am 14.07.2016 um 23:02 schrieb Arnold Schwaighofer <aschwaighofer@apple.com>:

[Arnold (Arnold Schwaighofer)]

Hi Arnold,

Thank you and atrick@apple.com very much for your answers. That helps already a lot. Are you Arnold from the WWDC Video?

Yes.

I removed all the answers that are clear and have some follow-up questions inline.

3. Then Arnold says that four existential containers pointing to the same value (greater than the value buffer) use 4 heap allocations. He proposes copy-on-write (using a local storage class), but **does he mean this should be implemented by hand or is this an optimization that the swift compiler does on its own?**

No the swift compiler does not do this on its own.

Are there corresponding plans? Storing „big“ values (using some statistics to evaluate where the break-even is) as reference types always, storing them in a big table per type (each value occurs only once) should be possible, right? Is this something I should post on the swift-evolution mailing list?

No hashed out plans only discussions on hallways. The swift team focuses on finishing up swift 3.

But yes, similar ideas are being discussed.

The issue here is, that the switch between "swift subscript" for showing an abstraction of internals and real swift code that one should write is sometimes not clear.

Sorry about this.

This was meant as positive criticism. I really like the video!

Doing this by hand has some clear disadvantages as this would add a reference to each usage of `Line` (and reference counting) even in the first examples of Kyle.

Yes, it is a tradeoff. Either, in the type erased context (as an instance of protocol value) copies are expensive for large value types and in the non generic/existential concrete context it is fast.

Is it really fast in the latter context for „big“ values?

I was being imprecise. I meant big plain POD types - a struct that contains only non-reference counted values.

As soon as you have more than one reference in your struct indirection will typically be cheaper - just looking at reference counting.

This a simplification that might overlook specific cases where this is not necessarily true. (The swift compiler can flatten structs to its individual member properties -- scalarize the struct -- and that can lead to better optimization ...)

All collection types use copy-on-write. Especially if you have a lot of reference type properties copying seems to be slow even in the latter context. And since all collection types (including String) are backed by a reference type, even properties of these type incur additional reference counting.

Yes. Correct.

Or you make the type have indirect storage with copy on write to preserve value semantics and then you have an overhead for reference counting.

You can get the best of both worlds if you write a wrapper.

All of this comes at the cost of a lot of boiler plate code and discussions are taking place how-to improve this situation.

Are there already proposals available or is it still in early discussions? Can you give me a hint where to find more about it?

No proposals at the moment.

6. Is the Value-Witness-Table a (kind of) dictionary for all values of a given value type (bigger than the value buffer), so that you do not store any value twice on the heap, but share the reference? If this is the case the answer of *3.* should be *automatically*. But then again, the "manual" implementation of `String` and `Array` (see *4.*) make no sense anymore, does it? Or are `Array` and `String` implemented only on the lower-level and the copy-on-write implementation is not visible in their Swift implementation?

I don’t full understand the question.

The value-witness-table exists per type and contains functions that describe how to copy, allocate, and deallocate values of that type.

OK. I am still a little bit unsure what it is now. Andrew Trick says:

A value witness table is a dictionary for all values of a type regardless of whether it fits in a buffer.
The keys are operations that can be done to any value (copy/destroy), the implementation for
that type knows where the value is stored.

This is an abstract description that does not contradict mine.
Conceptually the value witness table is a dictionary (value witness's function kind to implementation). It is implemented as a block of memory (a table) that contains pointers to functions. At offset 2 (made up I would have to lookup what the offset is) say you will find the function that knows how to allocate memory for that type.
For an Int this function will just return a pointer into the inline value buffer.

For a struct of 4 integers this function will malloc memory on the heap store the pointer into the online value buffer and will return that pointer.

In the example Arnold (you?) used the value witness table to copy the value (see slide 171 last line of code):

pwt.draw(vwt.projectBuffer(&local))

Since I didn’t know that the „storage“-trick is done manually, I thought there is a (hash)table/dictionary of all values of a „big“ value type where each value is uniquely stored (constant time access).

No this is not how it works.

Buffers for big values are created when we create a protocol value. This code is not clever. It allocates memory on the heap and copies the value's storage to that heap memory.

···

Sent from my iPhone

On Jul 14, 2016, at 4:04 PM, Johannes Neubauer <neubauer@kingsware.de> wrote:

Am 14.07.2016 um 23:02 schrieb Arnold Schwaighofer <aschwaighofer@apple.com>:

For „small“ values it would just point, to the concrete value of this very value. As mentioned above: should I post this on the swift-evolution mailing list?

All the best
Johannes

[Johannes_Neubauer1 (Johannes Neubauer)]

Hi Arnold,

Hi Arnold,

Thank you and atrick@apple.com very much for your answers. That helps already a lot. Are you Arnold from the WWDC Video?

Yes.

Cool. Thank you for the great answers. Last words to this topic inline:

Are there corresponding plans? Storing „big“ values (using some statistics to evaluate where the break-even is) as reference types always, storing them in a big table per type (each value occurs only once) should be possible, right? Is this something I should post on the swift-evolution mailing list?

No hashed out plans only discussions on hallways. The swift team focuses on finishing up swift 3.

But yes, similar ideas are being discussed.

AFAIK the JVM does such things for Strings (they call it a pool not a table) and they use a pool of values as reference types for inboxing/outboxing of primitive types to their Wrapper class counterparts (in order to speed this process up). So if you put an `int` into a method that expects an `Integer` they lookup the corresponding instance of the Wrapper type and return it.

This a simplification that might overlook specific cases where this is not necessarily true. (The swift compiler can flatten structs to its individual member properties -- scalarize the struct -- and that can lead to better optimization …)

OK. Good to know.

Are there already proposals available or is it still in early discussions? Can you give me a hint where to find more about it?

No proposals at the moment.

Is there some documentation of the current implementation of Existential Container, Protocol Witness Table, and co.? Where do I find it?

This is an abstract description that does not contradict mine.
Conceptually the value witness table is a dictionary (value witness's function kind to implementation). It is implemented as a block of memory (a table) that contains pointers to functions. At offset 2 (made up I would have to lookup what the offset is) say you will find the function that knows how to allocate memory for that type.
For an Int this function will just return a pointer into the inline value buffer.

For a struct of 4 integers this function will malloc memory on the heap store the pointer into the online value buffer and will return that pointer.

OK, so this table contains 4 entries alloc/dealloc, copy, and destroy and is not a table of all values. I got it.

Buffers for big values are created when we create a protocol value. This code is not clever. It allocates memory on the heap and copies the value's storage to that heap memory.

OK. Thanks.

All the best
Johannes

···

Am 15.07.2016 um 02:17 schrieb Arnold <aschwaighofer@apple.com>:

On Jul 14, 2016, at 4:04 PM, Johannes Neubauer <neubauer@kingsware.de> wrote:

[Andrew_Trick]

Arnold’s slides are the best I’ve seen!

There are some internal details here:

apple/swift/blob/main/docs/SIL.rst

https://github.com/apple/swift/blob/master/docs/ABI.rst

-Andy

···

On Jul 15, 2016, at 9:25 AM, Johannes Neubauer via swift-dev <swift-dev@swift.org> wrote:

Is there some documentation of the current implementation of Existential Container, Protocol Witness Table, and co.? Where do I find it?