Having 64-bit swift_retain/release ignore all negative pointer values

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.

-Joe

We can't do that unless we can get a guarantee from the OS folks that a "negative" pointer will never be a valid userspace pointer in any future OS version.

···

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.

--
Greg Parker gparker@apple.com Runtime Wrangler

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.

-Joe

···

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.

We have that guarantee, actually. The top eight bits are guaranteed to be clear in the user space on both ARM64 and x86-64.

John.

···

On Mar 1, 2016, at 3:05 PM, Greg Parker 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.

We can't do that unless we can get a guarantee from the OS folks that a "negative" pointer will never be a valid userspace pointer in any future OS version.

This makes sense to me. if (x <= 0) return; should be just as cheap as is (x == 0) return;

John.

···

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 <mailto: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.

Correct me if I’m wrong, but aren’t all kernel addresses negative on x64 and AArch64? Would this then mean any attempt to use Swift in kernel-space requires a distinct ABI?

···

On Oct 13, 2016, at 12:04 PM, 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 <mailto: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.

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

This may be the case currently on Linux (even for non-x86 architectures),
but what I have heard is that the kernel architecture allows using more
levels of page tables, and the full 64-bit address space. The "guarantee"
may not hold true in the future.

Negative pointer values are also used on other operating systems, so I
would suggest not relying on this assumption for the sake of portability.

Bryan

···

John McCall via swift-dev <swift-dev@swift.org> wrote on 2016-03-01 06:23:24 PM:

> On Mar 1, 2016, at 3:05 PM, Greg Parker 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.
>
> We can't do that unless we can get a guarantee from the OS folks
that a "negative" pointer will never be a valid userspace pointer in
any future OS version.

We have that guarantee, actually. The top eight bits are guaranteed
to be clear in the user space on both ARM64 and x86-64.

Sorry, I spoke too generally. Obviously, this is a platform/kernel-specific
decision. *Darwin* guarantees that the top eight bits are clear on userspace
data pointers on both ARM64 and x86-64. If Linux makes weaker guarantees,
which seems likely to me, then we should make weaker assumptions on Linux.

John.

···

On Mar 8, 2016, at 2:24 AM, Bryan Chan <bryan.chan@ca.ibm.com> wrote:
John McCall via swift-dev <swift-dev@swift.org> wrote on 2016-03-01 06:23:24 PM: > > > > On Mar 1, 2016, at 3:05 PM, Greg Parker 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.
> >
> > We can't do that unless we can get a guarantee from the OS folks
> that a "negative" pointer will never be a valid userspace pointer in
> any future OS version.
>
> We have that guarantee, actually. The top eight bits are guaranteed
> to be clear in the user space on both ARM64 and x86-64.

This may be the case currently on Linux (even for non-x86 architectures),
but what I have heard is that the kernel architecture allows using more
levels of page tables, and the full 64-bit address space. The "guarantee"
may not hold true in the future.

Negative pointer values are also used on other operating systems, so I
would suggest not relying on this assumption for the sake of portability.

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.

···

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 <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:

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;

--
Greg Parker gparker@apple.com <mailto:gparker@apple.com> Runtime Wrangler

That's correct, but we'd likely already have to have a separate "kernel" ABI due to our assumptions about spare bits in pointers. It also seems unlikely to me that kernel developers would want to use our refcounting scheme as is.

-Joe

···

On Oct 13, 2016, at 2:04 PM, Alexis <abeingessner@apple.com> wrote:

Correct me if I’m wrong, but aren’t all kernel addresses negative on x64 and AArch64? Would this then mean any attempt to use Swift in kernel-space requires a distinct ABI?

This is exactly my thinking.

John.

···

On Oct 13, 2016, at 2:14 PM, Joe Groff via swift-dev <swift-dev@swift.org> wrote:

On Oct 13, 2016, at 2:04 PM, Alexis <abeingessner@apple.com> wrote:

Correct me if I’m wrong, but aren’t all kernel addresses negative on x64 and AArch64? Would this then mean any attempt to use Swift in kernel-space requires a distinct ABI?

That's correct, but we'd likely already have to have a separate "kernel" ABI due to our assumptions about spare bits in pointers.

True, but the types being discussed here seem to mostly be language features that are implicitly falling back to reference counting when escape analysis fails. And specifically the tagging you’re proposing is for the cases where some special analysis passes and we can avoid the ref-counting machinery, right? Sounds like exactly the things they want. Although perhaps if they want to always avoid the ref-counting machinery, then we can actually have more aggressive pointer tagging tricks in the kernel ABI.

Well, as long as we’re aware that this is more complexity we’re adopting, seems fine.

···

On Oct 13, 2016, at 5:14 PM, Joe Groff <jgroff@apple.com> wrote:

On Oct 13, 2016, at 2:04 PM, Alexis <abeingessner@apple.com> wrote:

Correct me if I’m wrong, but aren’t all kernel addresses negative on x64 and AArch64? Would this then mean any attempt to use Swift in kernel-space requires a distinct ABI?

That's correct, but we'd likely already have to have a separate "kernel" ABI due to our assumptions about spare bits in pointers. It also seems unlikely to me that kernel developers would want to use our refcounting scheme as is.

Yeah, this would be a platform-specific decision. Linux x86-64 userspace at least still keeps to the positive side, since IIRC that's specified by the x86-64 SysV ABI, isn't it Bryan?

-Joe

···

On Mar 8, 2016, at 1:04 PM, John McCall via swift-dev <swift-dev@swift.org> wrote:

On Mar 8, 2016, at 2:24 AM, Bryan Chan <bryan.chan@ca.ibm.com <mailto:bryan.chan@ca.ibm.com>> wrote:
John McCall via swift-dev <swift-dev@swift.org <mailto:swift-dev@swift.org>> wrote on 2016-03-01 06:23:24 PM: >> >>>> On Mar 1, 2016, at 3:05 PM, Greg Parker 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.

We can't do that unless we can get a guarantee from the OS folks

that a "negative" pointer will never be a valid userspace pointer in
any future OS version.

We have that guarantee, actually. The top eight bits are guaranteed
to be clear in the user space on both ARM64 and x86-64.

This may be the case currently on Linux (even for non-x86 architectures),
but what I have heard is that the kernel architecture allows using more
levels of page tables, and the full 64-bit address space. The "guarantee"
may not hold true in the future.

Negative pointer values are also used on other operating systems, so I
would suggest not relying on this assumption for the sake of portability.

Sorry, I spoke too generally. Obviously, this is a platform/kernel-specific
decision. *Darwin* guarantees that the top eight bits are clear on userspace
data pointers on both ARM64 and x86-64. If Linux makes weaker guarantees,
which seems likely to me, then we should make weaker assumptions on Linux.

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. 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.

-Joe

···

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.

This could be further constrained to *refcountable* pointers if necessary. Even if the kernel for some reason decided to vend kernel-space addresses to userspace, it seems highly unlikely to me that address would point to a Swift-refcountable object.

-Joe

···

On Mar 8, 2016, at 1:48 PM, Joe Groff via swift-dev <swift-dev@swift.org> wrote:

On Mar 8, 2016, at 1:04 PM, John McCall via swift-dev <swift-dev@swift.org <mailto:swift-dev@swift.org>> wrote:

On Mar 8, 2016, at 2:24 AM, Bryan Chan <bryan.chan@ca.ibm.com <mailto:bryan.chan@ca.ibm.com>> wrote:
John McCall via swift-dev <swift-dev@swift.org <mailto:swift-dev@swift.org>> wrote on 2016-03-01 06:23:24 PM: >>> >>>>> On Mar 1, 2016, at 3:05 PM, Greg Parker via swift-dev <swift- >>>> dev@swift.org <mailto:dev@swift.org>> wrote:

On Mar 1, 2016, at 1:33 PM, Joe Groff via swift-dev <swift- >>>> dev@swift.org <mailto: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.

We can't do that unless we can get a guarantee from the OS folks

that a "negative" pointer will never be a valid userspace pointer in
any future OS version.

We have that guarantee, actually. The top eight bits are guaranteed
to be clear in the user space on both ARM64 and x86-64.

This may be the case currently on Linux (even for non-x86 architectures),
but what I have heard is that the kernel architecture allows using more
levels of page tables, and the full 64-bit address space. The "guarantee"
may not hold true in the future.

Negative pointer values are also used on other operating systems, so I
would suggest not relying on this assumption for the sake of portability.

Sorry, I spoke too generally. Obviously, this is a platform/kernel-specific
decision. *Darwin* guarantees that the top eight bits are clear on userspace
data pointers on both ARM64 and x86-64. If Linux makes weaker guarantees,
which seems likely to me, then we should make weaker assumptions on Linux.

Yeah, this would be a platform-specific decision. Linux x86-64 userspace at least still keeps to the positive side, since IIRC that's specified by the x86-64 SysV ABI, isn't it Bryan?

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.

···

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 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.

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

--
-Dave

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.

-Joe

···

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 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.

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

--
-Dave

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

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.

···

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

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.

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

--
-Dave

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

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

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.

···

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:

-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.

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

--
-Dave

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

--
-Dave

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.

-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:

-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.

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

--
-Dave

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

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