This poses an interesting question for the semantic ARC model with enums. It seems to me that, if switching or projecting the payload of an enum was a consuming operation, that we could avoid this optimization pitfall. Switching the enum { case Big(Class), Small(Trivial) } or similar case would semantically eliminate the nontrivial enum value and leave only the trivial payload behind.
-Joe
···
On Oct 17, 2016, at 9:57 AM, Michael Gottesman <mgottesman@apple.com> wrote:
On Oct 17, 2016, at 9:42 AM, Joe Groff via swift-dev <swift-dev@swift.org> wrote:
On Oct 16, 2016, at 1:10 PM, Dave Abrahams via swift-dev <swift-dev@swift.org> wrote:
on Thu Oct 13 2016, Joe Groff <swift-dev-AT-swift.org> wrote:
On Oct 13, 2016, at 1:18 PM, Greg Parker <gparker@apple.com> wrote:
On Oct 13, 2016, at 10:46 AM, John McCall via swift-dev <swift-dev@swift.org> wrote:
On Oct 13, 2016, at 9:04 AM, Joe Groff via swift-dev <swift-dev@swift.org> wrote:
On Mar 1, 2016, at 1:33 PM, Joe Groff via swift-dev <swift-dev@swift.org> wrote:
In swift_retain/release, we have an early-exit check to pass
through a nil pointer. Since we're already burning branch, I'm
thinking we could pass through not only zero but negative pointer
values too on 64-bit systems, since negative pointers are never
valid userspace pointers on our 64-bit targets. This would give
us room for tagged-pointer-like optimizations, for instance to
avoid allocations for tiny closure contexts.
I'd like to resurrect this thread as we look to locking down the
ABI. There were portability concerns about doing this unilaterally
for all 64-bit targets, but AFAICT it should be safe for x86-64
and Apple AArch64 targets. The x86-64 ABI limits the userland
address space, per section 3.3.2:
Although the AMD64 architecture uses 64-bit pointers,
implementations are only required to handle 48-bit
addresses. Therefore, conforming processes may only use addresses
from 0x00000000 00000000 to 0x00007fff ffffffff.
Apple's ARM64 platforms always enable the top-byte-ignore
architectural feature, restricting the available address space to
the low 56 bits of the full 64-bit address space in
practice. Therefore, "negative" values should never be valid
user-space references to Swift-refcountable objects. Taking
advantage of this fact would enable us to optimize small closure
contexts, Error objects, and, if we move to a reference-counted
COW model for existentials, small `Any` values, which need to be
refcountable for ABI reasons but don't semantically promise a
unique identity like class instances do.
This makes sense to me. if (x <= 0) return; should be just as cheap as is (x == 0) return;
Conversely, I wanted to try to remove such nil checks. Currently
they look haphazard: some functions have them and some do not.
Allowing ABI space for tagged pointer objects is a much bigger
problem than the check in swift_retain/release. For example, all
vtable and witness table dispatch sites to AnyObject or any other
type that might someday have a tagged pointer subclass would need to
compile in a fallback path now. You can't dereference a tagged
pointer to get its class pointer.
True. I don't think we'd want to use this optimization for class
types; I was specifically thinking of other things for which we use
nullable refcounted representations, particularly closure
contexts. The ABI for function types requires the context to be
refcountable by swift_retain/release, but it doesn't necessarily have
to be a valid pointer, if the closure formation site and invocation
function agree on a tagged-pointer representation.
Well, but we'd like to take advantage of the same kind of optimization
for the small string optimization. It doesn't seem like this should be
handled differently just because the string buffer is a class instance
and not a closure context.
String is a struct, and small strings don't have to be modeled as class instances. An enum { case Big(StringStorage), Small(Int63) } or similar layout should be able to take advantage of swift_retain/release ignoring negative values too.
I need to catch up on this thread, but there is an important thing to remember. If you use an enum like this there are a few potential issues:
1. In the implementation, you will /not/ want to use the enum internally. This would prevent the optimizer from eliminating all of the Small Case reference counting operations. This means you would rewrap the internal value when you return one and when you enter into an internal implementation code path try to immediately switch to a specialized small case path if you can.
Yeah, I figured we would still need some variant of Builtin.BridgeObject around to give the standard library the control it needs. My only point was that we don't necessarily need to support a concept of tagged-pointer class instances, with all the runtime complexity that entails, to be able to take advantage of tagged pointer optimizations for non-class refcounted types in Swift.
-Joe
···
On Oct 17, 2016, at 10:54 AM, Dave Abrahams <dabrahams@apple.com> wrote:
on Mon Oct 17 2016, Joe Groff <jgroff-AT-apple.com> wrote:
On Oct 16, 2016, at 1:10 PM, Dave Abrahams via swift-dev <swift-dev@swift.org> wrote:
on Thu Oct 13 2016, Joe Groff <swift-dev-AT-swift.org> wrote:
On Oct 13, 2016, at 1:18 PM, Greg Parker <gparker@apple.com> wrote:
On Oct 13, 2016, at 10:46 AM, John McCall via swift-dev <swift-dev@swift.org> wrote:
On Oct 13, 2016, at 9:04 AM, Joe Groff via swift-dev <swift-dev@swift.org> wrote:
On Mar 1, 2016, at 1:33 PM, Joe Groff via swift-dev <swift-dev@swift.org> wrote:
In swift_retain/release, we have an early-exit check to pass
through a nil pointer. Since we're already burning branch, I'm
thinking we could pass through not only zero but negative pointer
values too on 64-bit systems, since negative pointers are never
valid userspace pointers on our 64-bit targets. This would give
us room for tagged-pointer-like optimizations, for instance to
avoid allocations for tiny closure contexts.
I'd like to resurrect this thread as we look to locking down the
ABI. There were portability concerns about doing this unilaterally
for all 64-bit targets, but AFAICT it should be safe for x86-64
and Apple AArch64 targets. The x86-64 ABI limits the userland
address space, per section 3.3.2:
Although the AMD64 architecture uses 64-bit pointers,
implementations are only required to handle 48-bit
addresses. Therefore, conforming processes may only use addresses
from 0x00000000 00000000 to 0x00007fff ffffffff.
Apple's ARM64 platforms always enable the top-byte-ignore
architectural feature, restricting the available address space to
the low 56 bits of the full 64-bit address space in
practice. Therefore, "negative" values should never be valid
user-space references to Swift-refcountable objects. Taking
advantage of this fact would enable us to optimize small closure
contexts, Error objects, and, if we move to a reference-counted
COW model for existentials, small `Any` values, which need to be
refcountable for ABI reasons but don't semantically promise a
unique identity like class instances do.
This makes sense to me. if (x <= 0) return; should be just as cheap as is (x == 0) return;
Conversely, I wanted to try to remove such nil checks. Currently
they look haphazard: some functions have them and some do not.
Allowing ABI space for tagged pointer objects is a much bigger
problem than the check in swift_retain/release. For example, all
vtable and witness table dispatch sites to AnyObject or any other
type that might someday have a tagged pointer subclass would need to
compile in a fallback path now. You can't dereference a tagged
pointer to get its class pointer.
True. I don't think we'd want to use this optimization for class
types; I was specifically thinking of other things for which we use
nullable refcounted representations, particularly closure
contexts. The ABI for function types requires the context to be
refcountable by swift_retain/release, but it doesn't necessarily have
to be a valid pointer, if the closure formation site and invocation
function agree on a tagged-pointer representation.
Well, but we'd like to take advantage of the same kind of optimization
for the small string optimization. It doesn't seem like this should be
handled differently just because the string buffer is a class instance
and not a closure context.
String is a struct, and small strings don't have to be modeled as
class instances. An enum { case Big(StringStorage), Small(Int63) } or
similar layout should be able to take advantage of
swift_retain/release ignoring negative values too.
That would be nice. Historically I've had to bypass enums either
because the codegen or the optimizer wasn't smart enough.
We *had* wanted to use some of the same tagged pointer representations
as Cocoa does for NSString, and if we give up layout to the enum codegen
machinery we won't get that. That would be a very minor
performance win, though, so it probably doesn't matter.
In swift_retain/release, we have an early-exit check to pass
through a nil pointer. Since we're already burning branch, I'm
thinking we could pass through not only zero but negative pointer
values too on 64-bit systems, since negative pointers are never
valid userspace pointers on our 64-bit targets. This would give
us room for tagged-pointer-like optimizations, for instance to
avoid allocations for tiny closure contexts.
I'd like to resurrect this thread as we look to locking down the
ABI. There were portability concerns about doing this unilaterally
for all 64-bit targets, but AFAICT it should be safe for x86-64
and Apple AArch64 targets. The x86-64 ABI limits the userland
address space, per section 3.3.2:
Although the AMD64 architecture uses 64-bit pointers,
implementations are only required to handle 48-bit
addresses. Therefore, conforming processes may only use addresses
from 0x00000000 00000000 to 0x00007fff ffffffff.
Apple's ARM64 platforms always enable the top-byte-ignore
architectural feature, restricting the available address space to
the low 56 bits of the full 64-bit address space in
practice. Therefore, "negative" values should never be valid
user-space references to Swift-refcountable objects. Taking
advantage of this fact would enable us to optimize small closure
contexts, Error objects, and, if we move to a reference-counted
COW model for existentials, small `Any` values, which need to be
refcountable for ABI reasons but don't semantically promise a
unique identity like class instances do.
This makes sense to me. if (x <= 0) return; should be just as cheap as is (x == 0) return;
Conversely, I wanted to try to remove such nil checks. Currently
they look haphazard: some functions have them and some do not.
Allowing ABI space for tagged pointer objects is a much bigger
problem than the check in swift_retain/release. For example, all
vtable and witness table dispatch sites to AnyObject or any other
type that might someday have a tagged pointer subclass would need to
compile in a fallback path now. You can't dereference a tagged
pointer to get its class pointer.
True. I don't think we'd want to use this optimization for class
types; I was specifically thinking of other things for which we use
nullable refcounted representations, particularly closure
contexts. The ABI for function types requires the context to be
refcountable by swift_retain/release, but it doesn't necessarily have
to be a valid pointer, if the closure formation site and invocation
function agree on a tagged-pointer representation.
Well, but we'd like to take advantage of the same kind of optimization
for the small string optimization. It doesn't seem like this should be
handled differently just because the string buffer is a class instance
and not a closure context.
String is a struct, and small strings don't have to be modeled as class instances. An enum { case Big(StringStorage), Small(Int63) } or similar layout should be able to take advantage of swift_retain/release ignoring negative values too.
I need to catch up on this thread, but there is an important thing to remember. If you use an enum like this there are a few potential issues:
1. In the implementation, you will /not/ want to use the enum internally. This would prevent the optimizer from eliminating all of the Small Case reference counting operations. This means you would rewrap the internal value when you return one and when you enter into an internal implementation code path try to immediately switch to a specialized small case path if you can.
2. {Retain,Release}Values will be created outside. We are talking about some ways of fixing this from a code-size perspective by using a value witness, but in the present this may cause additional code-size increase.
This is exactly the case that would be improved, since retain/release_value on such an enum would boil down to a single swift_retain/release call if the runtime functions ignored the tagged small case values.
I am saying something stronger. What I am saying is that, you could have 0 retain/release operations on the SmallString path.
···
On Oct 17, 2016, at 10:00 AM, Joe Groff <jgroff@apple.com> wrote:
On Oct 17, 2016, at 9:57 AM, Michael Gottesman <mgottesman@apple.com> wrote:
On Oct 17, 2016, at 9:42 AM, Joe Groff via swift-dev <swift-dev@swift.org> wrote:
On Oct 16, 2016, at 1:10 PM, Dave Abrahams via swift-dev <swift-dev@swift.org> wrote:
on Thu Oct 13 2016, Joe Groff <swift-dev-AT-swift.org> wrote:
On Oct 13, 2016, at 1:18 PM, Greg Parker <gparker@apple.com> wrote:
On Oct 13, 2016, at 10:46 AM, John McCall via swift-dev <swift-dev@swift.org> wrote:
On Oct 13, 2016, at 9:04 AM, Joe Groff via swift-dev <swift-dev@swift.org> wrote:
On Mar 1, 2016, at 1:33 PM, Joe Groff via swift-dev <swift-dev@swift.org> wrote:
-Joe
-Joe
We could also do interesting things with enums; if one payload type is
a class reference and the rest are trivial, we could lay the enum out
in such a way that we can use swift_retain/release on it by setting
the high bit when tagging the trivial representations, saving us the
need to emit a switch. We wouldn't actually dereference the pointer
representation without checking it first.
I know we've discussed taking the nil check out of
swift_retain/release, and possibly having separate variants that do
include the null check for when we know we're working with
Optionals. How much of difference would that really make, though? I'd
expect it to be a fairly easily predictable branch, since most objects
are likely to be nonnull in practice.
In swift_retain/release, we have an early-exit check to pass
through a nil pointer. Since we're already burning branch, I'm
thinking we could pass through not only zero but negative pointer
values too on 64-bit systems, since negative pointers are never
valid userspace pointers on our 64-bit targets. This would give
us room for tagged-pointer-like optimizations, for instance to
avoid allocations for tiny closure contexts.
I'd like to resurrect this thread as we look to locking down the
ABI. There were portability concerns about doing this unilaterally
for all 64-bit targets, but AFAICT it should be safe for x86-64
and Apple AArch64 targets. The x86-64 ABI limits the userland
address space, per section 3.3.2:
Although the AMD64 architecture uses 64-bit pointers,
implementations are only required to handle 48-bit
addresses. Therefore, conforming processes may only use addresses
from 0x00000000 00000000 to 0x00007fff ffffffff.
Apple's ARM64 platforms always enable the top-byte-ignore
architectural feature, restricting the available address space to
the low 56 bits of the full 64-bit address space in
practice. Therefore, "negative" values should never be valid
user-space references to Swift-refcountable objects. Taking
advantage of this fact would enable us to optimize small closure
contexts, Error objects, and, if we move to a reference-counted
COW model for existentials, small `Any` values, which need to be
refcountable for ABI reasons but don't semantically promise a
unique identity like class instances do.
This makes sense to me. if (x <= 0) return; should be just as cheap as is (x == 0) return;
Conversely, I wanted to try to remove such nil checks. Currently
they look haphazard: some functions have them and some do not.
Allowing ABI space for tagged pointer objects is a much bigger
problem than the check in swift_retain/release. For example, all
vtable and witness table dispatch sites to AnyObject or any other
type that might someday have a tagged pointer subclass would need to
compile in a fallback path now. You can't dereference a tagged
pointer to get its class pointer.
True. I don't think we'd want to use this optimization for class
types; I was specifically thinking of other things for which we use
nullable refcounted representations, particularly closure
contexts. The ABI for function types requires the context to be
refcountable by swift_retain/release, but it doesn't necessarily have
to be a valid pointer, if the closure formation site and invocation
function agree on a tagged-pointer representation.
Well, but we'd like to take advantage of the same kind of optimization
for the small string optimization. It doesn't seem like this should be
handled differently just because the string buffer is a class instance
and not a closure context.
String is a struct, and small strings don't have to be modeled as class instances. An enum { case Big(StringStorage), Small(Int63) } or similar layout should be able to take advantage of swift_retain/release ignoring negative values too.
I need to catch up on this thread, but there is an important thing to remember. If you use an enum like this there are a few potential issues:
1. In the implementation, you will /not/ want to use the enum internally. This would prevent the optimizer from eliminating all of the Small Case reference counting operations. This means you would rewrap the internal value when you return one and when you enter into an internal implementation code path try to immediately switch to a specialized small case path if you can.
This poses an interesting question for the semantic ARC model with enums. It seems to me that, if switching or projecting the payload of an enum was a consuming operation, that we could avoid this optimization pitfall. Switching the enum { case Big(Class), Small(Trivial) } or similar case would semantically eliminate the nontrivial enum value and leave only the trivial payload behind.
Sure. I thought that switch_enum was always a consuming operation semantically (that the optimizer just chose to ignore). I agree with you here that this fits the enum model better (definitely for optionals which are used more like tuples than like classes).
···
On Oct 17, 2016, at 10:19 AM, Joe Groff <jgroff@apple.com> wrote:
On Oct 17, 2016, at 9:57 AM, Michael Gottesman <mgottesman@apple.com> wrote:
On Oct 17, 2016, at 9:42 AM, Joe Groff via swift-dev <swift-dev@swift.org> wrote:
On Oct 16, 2016, at 1:10 PM, Dave Abrahams via swift-dev <swift-dev@swift.org> wrote:
on Thu Oct 13 2016, Joe Groff <swift-dev-AT-swift.org> wrote:
On Oct 13, 2016, at 1:18 PM, Greg Parker <gparker@apple.com> wrote:
On Oct 13, 2016, at 10:46 AM, John McCall via swift-dev <swift-dev@swift.org> wrote:
On Oct 13, 2016, at 9:04 AM, Joe Groff via swift-dev <swift-dev@swift.org> wrote:
On Mar 1, 2016, at 1:33 PM, Joe Groff via swift-dev <swift-dev@swift.org> wrote:
We can't make it *exclusively* a consuming operation; it has to be possible to switch on a borrowed value.
John.
···
On Oct 17, 2016, at 10:19 AM, Joe Groff via swift-dev <swift-dev@swift.org> wrote:
On Oct 17, 2016, at 9:57 AM, Michael Gottesman <mgottesman@apple.com> wrote:
On Oct 17, 2016, at 9:42 AM, Joe Groff via swift-dev <swift-dev@swift.org> wrote:
On Oct 16, 2016, at 1:10 PM, Dave Abrahams via swift-dev <swift-dev@swift.org> wrote:
on Thu Oct 13 2016, Joe Groff <swift-dev-AT-swift.org> wrote:
On Oct 13, 2016, at 1:18 PM, Greg Parker <gparker@apple.com> wrote:
On Oct 13, 2016, at 10:46 AM, John McCall via swift-dev <swift-dev@swift.org> wrote:
On Oct 13, 2016, at 9:04 AM, Joe Groff via swift-dev <swift-dev@swift.org> wrote:
On Mar 1, 2016, at 1:33 PM, Joe Groff via swift-dev <swift-dev@swift.org> wrote:
In swift_retain/release, we have an early-exit check to pass
through a nil pointer. Since we're already burning branch, I'm
thinking we could pass through not only zero but negative pointer
values too on 64-bit systems, since negative pointers are never
valid userspace pointers on our 64-bit targets. This would give
us room for tagged-pointer-like optimizations, for instance to
avoid allocations for tiny closure contexts.
I'd like to resurrect this thread as we look to locking down the
ABI. There were portability concerns about doing this unilaterally
for all 64-bit targets, but AFAICT it should be safe for x86-64
and Apple AArch64 targets. The x86-64 ABI limits the userland
address space, per section 3.3.2:
Although the AMD64 architecture uses 64-bit pointers,
implementations are only required to handle 48-bit
addresses. Therefore, conforming processes may only use addresses
from 0x00000000 00000000 to 0x00007fff ffffffff.
Apple's ARM64 platforms always enable the top-byte-ignore
architectural feature, restricting the available address space to
the low 56 bits of the full 64-bit address space in
practice. Therefore, "negative" values should never be valid
user-space references to Swift-refcountable objects. Taking
advantage of this fact would enable us to optimize small closure
contexts, Error objects, and, if we move to a reference-counted
COW model for existentials, small `Any` values, which need to be
refcountable for ABI reasons but don't semantically promise a
unique identity like class instances do.
This makes sense to me. if (x <= 0) return; should be just as cheap as is (x == 0) return;
Conversely, I wanted to try to remove such nil checks. Currently
they look haphazard: some functions have them and some do not.
Allowing ABI space for tagged pointer objects is a much bigger
problem than the check in swift_retain/release. For example, all
vtable and witness table dispatch sites to AnyObject or any other
type that might someday have a tagged pointer subclass would need to
compile in a fallback path now. You can't dereference a tagged
pointer to get its class pointer.
True. I don't think we'd want to use this optimization for class
types; I was specifically thinking of other things for which we use
nullable refcounted representations, particularly closure
contexts. The ABI for function types requires the context to be
refcountable by swift_retain/release, but it doesn't necessarily have
to be a valid pointer, if the closure formation site and invocation
function agree on a tagged-pointer representation.
Well, but we'd like to take advantage of the same kind of optimization
for the small string optimization. It doesn't seem like this should be
handled differently just because the string buffer is a class instance
and not a closure context.
String is a struct, and small strings don't have to be modeled as class instances. An enum { case Big(StringStorage), Small(Int63) } or similar layout should be able to take advantage of swift_retain/release ignoring negative values too.
I need to catch up on this thread, but there is an important thing to remember. If you use an enum like this there are a few potential issues:
1. In the implementation, you will /not/ want to use the enum internally. This would prevent the optimizer from eliminating all of the Small Case reference counting operations. This means you would rewrap the internal value when you return one and when you enter into an internal implementation code path try to immediately switch to a specialized small case path if you can.
This poses an interesting question for the semantic ARC model with enums. It seems to me that, if switching or projecting the payload of an enum was a consuming operation, that we could avoid this optimization pitfall. Switching the enum { case Big(Class), Small(Trivial) } or similar case would semantically eliminate the nontrivial enum value and leave only the trivial payload behind.
In swift_retain/release, we have an early-exit check to pass
through a nil pointer. Since we're already burning branch, I'm
thinking we could pass through not only zero but negative pointer
values too on 64-bit systems, since negative pointers are never
valid userspace pointers on our 64-bit targets. This would give
us room for tagged-pointer-like optimizations, for instance to
avoid allocations for tiny closure contexts.
I'd like to resurrect this thread as we look to locking down the
ABI. There were portability concerns about doing this unilaterally
for all 64-bit targets, but AFAICT it should be safe for x86-64
and Apple AArch64 targets. The x86-64 ABI limits the userland
address space, per section 3.3.2:
Although the AMD64 architecture uses 64-bit pointers,
implementations are only required to handle 48-bit
addresses. Therefore, conforming processes may only use addresses
from 0x00000000 00000000 to 0x00007fff ffffffff.
Apple's ARM64 platforms always enable the top-byte-ignore
architectural feature, restricting the available address space to
the low 56 bits of the full 64-bit address space in
practice. Therefore, "negative" values should never be valid
user-space references to Swift-refcountable objects. Taking
advantage of this fact would enable us to optimize small closure
contexts, Error objects, and, if we move to a reference-counted
COW model for existentials, small `Any` values, which need to be
refcountable for ABI reasons but don't semantically promise a
unique identity like class instances do.
This makes sense to me. if (x <= 0) return; should be just as cheap as is (x == 0) return;
Conversely, I wanted to try to remove such nil checks. Currently
they look haphazard: some functions have them and some do not.
Allowing ABI space for tagged pointer objects is a much bigger
problem than the check in swift_retain/release. For example, all
vtable and witness table dispatch sites to AnyObject or any other
type that might someday have a tagged pointer subclass would need to
compile in a fallback path now. You can't dereference a tagged
pointer to get its class pointer.
True. I don't think we'd want to use this optimization for class
types; I was specifically thinking of other things for which we use
nullable refcounted representations, particularly closure
contexts. The ABI for function types requires the context to be
refcountable by swift_retain/release, but it doesn't necessarily have
to be a valid pointer, if the closure formation site and invocation
function agree on a tagged-pointer representation.
Well, but we'd like to take advantage of the same kind of optimization
for the small string optimization. It doesn't seem like this should be
handled differently just because the string buffer is a class instance
and not a closure context.
String is a struct, and small strings don't have to be modeled as class instances. An enum { case Big(StringStorage), Small(Int63) } or similar layout should be able to take advantage of swift_retain/release ignoring negative values too.
I need to catch up on this thread, but there is an important thing to remember. If you use an enum like this there are a few potential issues:
1. In the implementation, you will /not/ want to use the enum internally. This would prevent the optimizer from eliminating all of the Small Case reference counting operations. This means you would rewrap the internal value when you return one and when you enter into an internal implementation code path try to immediately switch to a specialized small case path if you can.
2. {Retain,Release}Values will be created outside. We are talking about some ways of fixing this from a code-size perspective by using a value witness, but in the present this may cause additional code-size increase.
This is exactly the case that would be improved, since retain/release_value on such an enum would boil down to a single swift_retain/release call if the runtime functions ignored the tagged small case values.
I am saying something stronger. What I am saying is that, you could have 0 retain/release operations on the SmallString path.
Let me elaborate a little bit, and then I am going to drop my point here since as Joe pointed out to me offlist, this is orthogonal to the ABI discussion.
What I am trying to say is that the optimizer will eliminate all retain, release operations on trivial values. Any code path which uses the top level enum can not take advantage of this property since the top level enum /could/ have the BigString contained in it. So what you want to do to get rid of the most retain/release operations is to move the enum switch to the entrances of the API so that one has the largest region of code where the optimizer can clearly see that it has a small string.
Now we /could/ specialize on enum cases. I will file a radar for this.
Michael
···
On Oct 17, 2016, at 11:53 AM, Michael Gottesman via swift-dev <swift-dev@swift.org> wrote:
On Oct 17, 2016, at 10:00 AM, Joe Groff <jgroff@apple.com <mailto:jgroff@apple.com>> wrote:
On Oct 17, 2016, at 9:57 AM, Michael Gottesman <mgottesman@apple.com <mailto:mgottesman@apple.com>> wrote:
On Oct 17, 2016, at 9:42 AM, Joe Groff via swift-dev <swift-dev@swift.org <mailto:swift-dev@swift.org>> wrote:
On Oct 16, 2016, at 1:10 PM, Dave Abrahams via swift-dev <swift-dev@swift.org <mailto:swift-dev@swift.org>> wrote:
on Thu Oct 13 2016, Joe Groff <swift-dev-AT-swift.org <http://swift-dev-at-swift.org/>> wrote:
On Oct 13, 2016, at 1:18 PM, Greg Parker <gparker@apple.com <mailto:gparker@apple.com>> wrote:
On Oct 13, 2016, at 10:46 AM, John McCall via swift-dev <swift-dev@swift.org <mailto:swift-dev@swift.org>> wrote:
On Oct 13, 2016, at 9:04 AM, Joe Groff via swift-dev <swift-dev@swift.org <mailto:swift-dev@swift.org>> wrote:
On Mar 1, 2016, at 1:33 PM, Joe Groff via swift-dev <swift-dev@swift.org <mailto:swift-dev@swift.org>> wrote:
-Joe
-Joe
We could also do interesting things with enums; if one payload type is
a class reference and the rest are trivial, we could lay the enum out
in such a way that we can use swift_retain/release on it by setting
the high bit when tagging the trivial representations, saving us the
need to emit a switch. We wouldn't actually dereference the pointer
representation without checking it first.
I know we've discussed taking the nil check out of
swift_retain/release, and possibly having separate variants that do
include the null check for when we know we're working with
Optionals. How much of difference would that really make, though? I'd
expect it to be a fairly easily predictable branch, since most objects
are likely to be nonnull in practice.
In swift_retain/release, we have an early-exit check to pass
through a nil pointer. Since we're already burning branch, I'm
thinking we could pass through not only zero but negative pointer
values too on 64-bit systems, since negative pointers are never
valid userspace pointers on our 64-bit targets. This would give
us room for tagged-pointer-like optimizations, for instance to
avoid allocations for tiny closure contexts.
I'd like to resurrect this thread as we look to locking down the
ABI. There were portability concerns about doing this unilaterally
for all 64-bit targets, but AFAICT it should be safe for x86-64
and Apple AArch64 targets. The x86-64 ABI limits the userland
address space, per section 3.3.2:
Although the AMD64 architecture uses 64-bit pointers,
implementations are only required to handle 48-bit
addresses. Therefore, conforming processes may only use addresses
from 0x00000000 00000000 to 0x00007fff ffffffff.
Apple's ARM64 platforms always enable the top-byte-ignore
architectural feature, restricting the available address space to
the low 56 bits of the full 64-bit address space in
practice. Therefore, "negative" values should never be valid
user-space references to Swift-refcountable objects. Taking
advantage of this fact would enable us to optimize small closure
contexts, Error objects, and, if we move to a reference-counted
COW model for existentials, small `Any` values, which need to be
refcountable for ABI reasons but don't semantically promise a
unique identity like class instances do.
This makes sense to me. if (x <= 0) return; should be just as cheap as is (x == 0) return;
Conversely, I wanted to try to remove such nil checks. Currently
they look haphazard: some functions have them and some do not.
Allowing ABI space for tagged pointer objects is a much bigger
problem than the check in swift_retain/release. For example, all
vtable and witness table dispatch sites to AnyObject or any other
type that might someday have a tagged pointer subclass would need to
compile in a fallback path now. You can't dereference a tagged
pointer to get its class pointer.
True. I don't think we'd want to use this optimization for class
types; I was specifically thinking of other things for which we use
nullable refcounted representations, particularly closure
contexts. The ABI for function types requires the context to be
refcountable by swift_retain/release, but it doesn't necessarily have
to be a valid pointer, if the closure formation site and invocation
function agree on a tagged-pointer representation.
Well, but we'd like to take advantage of the same kind of optimization
for the small string optimization. It doesn't seem like this should be
handled differently just because the string buffer is a class instance
and not a closure context.
String is a struct, and small strings don't have to be modeled as class instances. An enum { case Big(StringStorage), Small(Int63) } or similar layout should be able to take advantage of swift_retain/release ignoring negative values too.
I need to catch up on this thread, but there is an important thing to remember. If you use an enum like this there are a few potential issues:
1. In the implementation, you will /not/ want to use the enum internally. This would prevent the optimizer from eliminating all of the Small Case reference counting operations. This means you would rewrap the internal value when you return one and when you enter into an internal implementation code path try to immediately switch to a specialized small case path if you can.
This poses an interesting question for the semantic ARC model with enums. It seems to me that, if switching or projecting the payload of an enum was a consuming operation, that we could avoid this optimization pitfall. Switching the enum { case Big(Class), Small(Trivial) } or similar case would semantically eliminate the nontrivial enum value and leave only the trivial payload behind.
We can't make it *exclusively* a consuming operation; it has to be possible to switch on a borrowed value.
Yes. Perhaps the right way to think about it is in the context of considering putting conventions on SILArguments/Terminators. Then you have a natural way to express this and could optimize (potentially) in between such forms.
···
On Oct 17, 2016, at 12:40 PM, John McCall <rjmccall@apple.com> wrote:
On Oct 17, 2016, at 10:19 AM, Joe Groff via swift-dev <swift-dev@swift.org> wrote:
On Oct 17, 2016, at 9:57 AM, Michael Gottesman <mgottesman@apple.com> wrote:
On Oct 17, 2016, at 9:42 AM, Joe Groff via swift-dev <swift-dev@swift.org> wrote:
On Oct 16, 2016, at 1:10 PM, Dave Abrahams via swift-dev <swift-dev@swift.org> wrote:
on Thu Oct 13 2016, Joe Groff <swift-dev-AT-swift.org> wrote:
On Oct 13, 2016, at 1:18 PM, Greg Parker <gparker@apple.com> wrote:
On Oct 13, 2016, at 10:46 AM, John McCall via swift-dev <swift-dev@swift.org> wrote:
On Oct 13, 2016, at 9:04 AM, Joe Groff via swift-dev <swift-dev@swift.org> wrote:
On Mar 1, 2016, at 1:33 PM, Joe Groff via swift-dev <swift-dev@swift.org> wrote:
In swift_retain/release, we have an early-exit check to pass
through a nil pointer. Since we're already burning branch, I'm
thinking we could pass through not only zero but negative pointer
values too on 64-bit systems, since negative pointers are never
valid userspace pointers on our 64-bit targets. This would give
us room for tagged-pointer-like optimizations, for instance to
avoid allocations for tiny closure contexts.
I'd like to resurrect this thread as we look to locking down the
ABI. There were portability concerns about doing this unilaterally
for all 64-bit targets, but AFAICT it should be safe for x86-64
and Apple AArch64 targets. The x86-64 ABI limits the userland
address space, per section 3.3.2:
Although the AMD64 architecture uses 64-bit pointers,
implementations are only required to handle 48-bit
addresses. Therefore, conforming processes may only use addresses
from 0x00000000 00000000 to 0x00007fff ffffffff.
Apple's ARM64 platforms always enable the top-byte-ignore
architectural feature, restricting the available address space to
the low 56 bits of the full 64-bit address space in
practice. Therefore, "negative" values should never be valid
user-space references to Swift-refcountable objects. Taking
advantage of this fact would enable us to optimize small closure
contexts, Error objects, and, if we move to a reference-counted
COW model for existentials, small `Any` values, which need to be
refcountable for ABI reasons but don't semantically promise a
unique identity like class instances do.
This makes sense to me. if (x <= 0) return; should be just as cheap as is (x == 0) return;
Conversely, I wanted to try to remove such nil checks. Currently
they look haphazard: some functions have them and some do not.
Allowing ABI space for tagged pointer objects is a much bigger
problem than the check in swift_retain/release. For example, all
vtable and witness table dispatch sites to AnyObject or any other
type that might someday have a tagged pointer subclass would need to
compile in a fallback path now. You can't dereference a tagged
pointer to get its class pointer.
True. I don't think we'd want to use this optimization for class
types; I was specifically thinking of other things for which we use
nullable refcounted representations, particularly closure
contexts. The ABI for function types requires the context to be
refcountable by swift_retain/release, but it doesn't necessarily have
to be a valid pointer, if the closure formation site and invocation
function agree on a tagged-pointer representation.
Well, but we'd like to take advantage of the same kind of optimization
for the small string optimization. It doesn't seem like this should be
handled differently just because the string buffer is a class instance
and not a closure context.
String is a struct, and small strings don't have to be modeled as class instances. An enum { case Big(StringStorage), Small(Int63) } or similar layout should be able to take advantage of swift_retain/release ignoring negative values too.
I need to catch up on this thread, but there is an important thing to remember. If you use an enum like this there are a few potential issues:
1. In the implementation, you will /not/ want to use the enum internally. This would prevent the optimizer from eliminating all of the Small Case reference counting operations. This means you would rewrap the internal value when you return one and when you enter into an internal implementation code path try to immediately switch to a specialized small case path if you can.
2. {Retain,Release}Values will be created outside. We are talking about some ways of fixing this from a code-size perspective by using a value witness, but in the present this may cause additional code-size increase.
This is exactly the case that would be improved, since retain/release_value on such an enum would boil down to a single swift_retain/release call if the runtime functions ignored the tagged small case values.
I am saying something stronger. What I am saying is that, you could have 0 retain/release operations on the SmallString path.
Let me elaborate a little bit, and then I am going to drop my point here since as Joe pointed out to me offlist, this is orthogonal to the ABI discussion.
What I am trying to say is that the optimizer will eliminate all retain, release operations on trivial values. Any code path which uses the top level enum can not take advantage of this property since the top level enum /could/ have the BigString contained in it. So what you want to do to get rid of the most retain/release operations is to move the enum switch to the entrances of the API so that one has the largest region of code where the optimizer can clearly see that it has a small string.
Now we /could/ specialize on enum cases. I will file a radar for this.
rdar://28805035
···
On Oct 17, 2016, at 12:01 PM, Michael Gottesman <mgottesman@apple.com> wrote:
On Oct 17, 2016, at 11:53 AM, Michael Gottesman via swift-dev <swift-dev@swift.org <mailto:swift-dev@swift.org>> wrote:
On Oct 17, 2016, at 10:00 AM, Joe Groff <jgroff@apple.com <mailto:jgroff@apple.com>> wrote:
On Oct 17, 2016, at 9:57 AM, Michael Gottesman <mgottesman@apple.com <mailto:mgottesman@apple.com>> wrote:
On Oct 17, 2016, at 9:42 AM, Joe Groff via swift-dev <swift-dev@swift.org <mailto:swift-dev@swift.org>> wrote:
On Oct 16, 2016, at 1:10 PM, Dave Abrahams via swift-dev <swift-dev@swift.org <mailto:swift-dev@swift.org>> wrote:
on Thu Oct 13 2016, Joe Groff <swift-dev-AT-swift.org <http://swift-dev-at-swift.org/>> wrote:
On Oct 13, 2016, at 1:18 PM, Greg Parker <gparker@apple.com <mailto:gparker@apple.com>> wrote:
On Oct 13, 2016, at 10:46 AM, John McCall via swift-dev <swift-dev@swift.org <mailto:swift-dev@swift.org>> wrote:
On Oct 13, 2016, at 9:04 AM, Joe Groff via swift-dev <swift-dev@swift.org <mailto:swift-dev@swift.org>> wrote:
On Mar 1, 2016, at 1:33 PM, Joe Groff via swift-dev <swift-dev@swift.org <mailto:swift-dev@swift.org>> wrote:
Michael
-Joe
-Joe
We could also do interesting things with enums; if one payload type is
a class reference and the rest are trivial, we could lay the enum out
in such a way that we can use swift_retain/release on it by setting
the high bit when tagging the trivial representations, saving us the
need to emit a switch. We wouldn't actually dereference the pointer
representation without checking it first.
I know we've discussed taking the nil check out of
swift_retain/release, and possibly having separate variants that do
include the null check for when we know we're working with
Optionals. How much of difference would that really make, though? I'd
expect it to be a fairly easily predictable branch, since most objects
are likely to be nonnull in practice.