Re: [swift-dev] Dictionary Collision Resolution Guarantees

[Dave Abrahams via swift-dev]

on Thu Oct 13 2016, Alexis  wrote:

>>> This is effectively assuming that the open-addressing scheme being
>>> used is first-come-first-serve (FCFS). That is, any element being
>>> inserted can *only* be inserted into vacant buckets, rather than
>>> displacing existing elements. This is currently only internal docs,
>>> but do we actually want to guarantee this? 
>> 
>> No, not to users.  But "//" comments are not user-level comments and
>> don't imply any guarantees.
>
> OK cool, is there any reason it’s even written down? I don’t see any code
> that’s obviously relying on it. (seems fine to delete it?)

It's written down because we've never formalized our index invalidation
rules.  I didn't realize that this comment was related to index
invalidation.  The guarantee mentioned is one we might want to give, at
least under some circumstances.  We'll have to think about that more
carefully.  In any case, it's not time to delete it yet.

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

Re: [swift-dev] Dictionary Collision Resolution Guarantees

[Alexis via swift-dev]

> On Oct 13, 2016, at 6:09 PM, Dave Abrahams via swift-dev 
>  wrote:
> 
> 
> on Thu Oct 13 2016, Alexis  > wrote:
> 
>> I’m currently cleaning up the docs on Dictionary to reflect the new indexing 
>> model, and I stumbled
>> across the note that the following code should work assuming no 
>> reallocations occur:
>> 
>> //
>> //   var (i, found) = d.find(k) // i is associated with d's buffer
>> //   if found {
>> //  var e = d// now d is sharing its data with e
>> //  e[newKey] = newValue // e now has a unique copy of the data
>> //  return e[i]  // use i to access e
>> //   }
>> //
>> 
>> This is effectively assuming that the open-addressing scheme being
>> used is first-come-first-serve (FCFS). That is, any element being
>> inserted can *only* be inserted into vacant buckets, rather than
>> displacing existing elements. This is currently only internal docs,
>> but do we actually want to guarantee this? 
> 
> No, not to users.  But "//" comments are not user-level comments and
> don't imply any guarantees.

OK cool, is there any reason it’s even written down? I don’t see any code
that’s obviously relying on it. (seems fine to delete it?)

> 
>> The popular alternative of robin hood (RH) doesn’t follow this.
>> 
>> Some background: One interesting optimization avenue worth exploring
>> is to tweak Dictionary to store hashes, rather than bits, to identify
>> occupied slots (with some careful masking so that 0 still means
>> “unoccupied”). Then searching for elements can be implemented as
>> follows:
>> 
>> let hash = hashFromKey(key)
>> var i = indexFromHash(hash)
>> while true {
>>  if hashes[i] == 0 {
>>// vacant, not contained
>>  } else if hashes[i] == hash {
>>// maybe already exists?
>>if keys[i] == key {
>>  // actually exists
>>}
>>  }
>>  i = nextIndex(i)
>> }
>> 
>> The interesting property of this is that it almost all of the search
>> time is spent linearly walking through an array and doing simple
>> comparisons on integers, which is of course really easy to optimize
>> (potentially even SIMD). 
> 
> Yep, that's cool.  It does cost a lot more storage, though.  Tradeoffs.
> 
>> 99.% of the time, if the element isn’t stored in the Dictionary,
>> then you’ll just hit a 0 hash, and never look at the keys. Similarly,
>> 99.% of the time, if the element *is* stored in the Dictionary,
>> you’ll only do a single key comparison (on the actually equal
>> element). So this is also really great for cache — pretty much all of
>> your access are just linear scans of the hashes.
>> 
>> The main downside is you’re now “wasting” more memory to store hashes,
>> but you can potentially compensate for this by truncating the hashes
>> to 8/16 bits for small Dictionaries (which will be better for SIMD
>> anyway).
> 
> Hey, cool.
> 
>> So what does this have to do with the RH scheme? Compared to FCFS, RH
>> generally leads to lower variance on search distances, and provides a
>> mechanism to short-circuit long runs if you have the hashes handy. If
>> you find hashes which want to live later in the array than where you
>> started, then the current element definitely isn’t contained. This
>> means you can increase the load factor on your dictionary and further
>> improve cache/memory usage (compensating for the memory-usage loss
>> from storing hashes). However it will be prohibitively expensive if
>> you require hashes to be recomputed on-the-fly.
> 
> Sounds like a worthy optimization!
> 
> -- 
> -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

Re: [swift-dev] copy-on-write proposal

[Erik Eckstein via swift-dev]

> On Oct 13, 2016, at 10:36 AM, Joe Groff  wrote:
> 
> 
>> On Oct 11, 2016, at 4:48 PM, Erik Eckstein via swift-dev 
>>  wrote:
>> 
>> This is a proposal for representing copy-on-write buffers in SIL. Actually 
>> it’s still a draft for a proposal. It also heavily depends on how we move 
>> forward with SIL ownership.
>> 
>> If you have any comments, please let me know.
> 
> The SIL-level design seems sensible to me at a glance. At the language level, 
> I think it would make more sense to treat this as an attribute on class types 
> rather than on properties in structs using the class. I don't think many 
> people reuse class definitions as both shared reference types and as value 
> type payloads, but beyond that, I think that making it an attribute of 
> classes would put us into a better position to leverage the borrow model to 
> enforce the "mutable-only-when-unique" aspect of COW implementations.

I think this makes sense. Although we would need an attribute on the field as 
well (what John called the @copied attribute).

> John alluded to this in the "SIL address types and borrowing" thread:
> 
>> I wonder if it would make more sense to make copy-on-write buffer references 
>> a move-only type, so that as long as you were just working with the raw 
>> reference (as opposed to the CoW aggregate, which would remain copyable) it 
>> wouldn't get implicitly copied anymore.  You could have mutable and 
>> immutable buffer reference types, both move-only, and there could be a 
>> consuming checkUnique operation on the immutable one that, I dunno, returned 
>> an Either of the mutable and immutable versions.
>> 
>> For CoW aggregates, you'd need some @copied attribute on the field to make 
>> sure that the CoW attribute was still copyable.  Within the implementation 
>> of the type, though, you would be projecting out the reference immediately, 
>> and thereafter you'd be certain that you were borrowing / moving it around 
>> as appropriate.
> 
> If 'copy-on-write' were a trait on classes, then we could distinguish unique 
> and nonunique references to the class. A unique reference would act like a 
> move-only type to prevent accidental loss of uniqueness. We can also allow a 
> copy-on-write class to have "mutating" methods, and only allow mutation on 
> unique references.

The only way to get a unique reference would then be to use the 
isUnique-builtin - or to create a new buffer. This is good, because we could 
statically check that the programmer can only modify uniquely referenced 
buffers (although to get full memory safety we would probably have  to 
invalidate the original buffer reference between the is_unique - end_unique 
scope, e.g. by storing a null pointer into it).

Thinking about this in detail I believe we have to change how a COW is 
implemented. For example we could not write back the unique reference and use 
it afterwards:

if let uniqueRef = isUnique(&cow.buffer) {
} else {
  uniqueRef = Buffer()
  cow.buffer = uniqueRef // <- this would not work. It’s a copy of a unique 
buffer
}
uniqueRef.someData = ...

Instead this could be done like

if let uniqueRef = isUnique(&cow.buffer) {
} else {
  uniqueRef = Buffer()
}
uniqueRef.someData = ...
cow.buffer = uniqueRef // OK, end of lifetime of uniqueRef

It would mean that we write back the buffer even in the unique-case, But I 
think this is ok.

For the implementation we would need two different reference types in the AST 
(unique and nonunique), right? Could this be just a different StorageType?

> It seems to me like, exploring this direction, we could also come up with a 
> way for the high-level value-semantics operations on the struct to statically 
> indicate which methods are known to leave the value's buffers in a unique 
> state, or which return values that are uniquely owned, which would give the 
> optimizer more ability to avoid uniqueness checks across calls without 
> relying on inlining and IPO.
> 
> -Joe

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

Re: [swift-dev] Dictionary Collision Resolution Guarantees

[Dave Abrahams via swift-dev]

on Thu Oct 13 2016, Alexis  wrote:

> I’m currently cleaning up the docs on Dictionary to reflect the new indexing 
> model, and I stumbled
> across the note that the following code should work assuming no reallocations 
> occur:
>
> //
> //   var (i, found) = d.find(k) // i is associated with d's buffer
> //   if found {
> //  var e = d// now d is sharing its data with e
> //  e[newKey] = newValue // e now has a unique copy of the data
> //  return e[i]  // use i to access e
> //   }
> //
>
> This is effectively assuming that the open-addressing scheme being
> used is first-come-first-serve (FCFS). That is, any element being
> inserted can *only* be inserted into vacant buckets, rather than
> displacing existing elements. This is currently only internal docs,
> but do we actually want to guarantee this? 

No, not to users.  But "//" comments are not user-level comments and
don't imply any guarantees.

> The popular alternative of robin hood (RH) doesn’t follow this.
>
> Some background: One interesting optimization avenue worth exploring
> is to tweak Dictionary to store hashes, rather than bits, to identify
> occupied slots (with some careful masking so that 0 still means
> “unoccupied”). Then searching for elements can be implemented as
> follows:
>
> let hash = hashFromKey(key)
> var i = indexFromHash(hash)
> while true {
>   if hashes[i] == 0 {
> // vacant, not contained
>   } else if hashes[i] == hash {
> // maybe already exists?
> if keys[i] == key {
>   // actually exists
> }
>   }
>   i = nextIndex(i)
> }
>
> The interesting property of this is that it almost all of the search
> time is spent linearly walking through an array and doing simple
> comparisons on integers, which is of course really easy to optimize
> (potentially even SIMD). 

Yep, that's cool.  It does cost a lot more storage, though.  Tradeoffs.

> 99.% of the time, if the element isn’t stored in the Dictionary,
> then you’ll just hit a 0 hash, and never look at the keys. Similarly,
> 99.% of the time, if the element *is* stored in the Dictionary,
> you’ll only do a single key comparison (on the actually equal
> element). So this is also really great for cache — pretty much all of
> your access are just linear scans of the hashes.
>
> The main downside is you’re now “wasting” more memory to store hashes,
> but you can potentially compensate for this by truncating the hashes
> to 8/16 bits for small Dictionaries (which will be better for SIMD
> anyway).

Hey, cool.

> So what does this have to do with the RH scheme? Compared to FCFS, RH
> generally leads to lower variance on search distances, and provides a
> mechanism to short-circuit long runs if you have the hashes handy. If
> you find hashes which want to live later in the array than where you
> started, then the current element definitely isn’t contained. This
> means you can increase the load factor on your dictionary and further
> improve cache/memory usage (compensating for the memory-usage loss
> from storing hashes). However it will be prohibitively expensive if
> you require hashes to be recomputed on-the-fly.

Sounds like a worthy optimization!

-- 
-Dave

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

Re: [swift-dev] Having 64-bit swift_retain/release ignore all negative pointer values

[Alexis via swift-dev]

> On Oct 13, 2016, at 5:14 PM, Joe Groff  wrote:
> 
> 
>> On Oct 13, 2016, at 2:04 PM, Alexis  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.

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.

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

Re: [swift-dev] Having 64-bit swift_retain/release ignore all negative pointer values

[John McCall via swift-dev]

> On Oct 13, 2016, at 2:14 PM, Joe Groff via swift-dev  
> wrote:
> 
> 
>> On Oct 13, 2016, at 2:04 PM, Alexis  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.

This is exactly my thinking.

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

Re: [swift-dev] Having 64-bit swift_retain/release ignore all negative pointer values

[Joe Groff via swift-dev]

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

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

Re: [swift-dev] Differences between Xcode official toolchains and tagged releases from repository

[Xavier Jurado via swift-dev]

I can confirm that both issues were solved/bypassed by rebuilding the
toolchain with assertions disabled. The provided examples compiled
successfully, so we finally got the same result as the official 2.2
toolchain.

Thank you again for the input!

2016-10-06 9:26 GMT+02:00 Xavier Jurado :

> Thanks for the hint! When I built the toolchain I modified the
> "mixin_lightweight_assertions" preset locally to use "no-assertions" and
> "swift-assertions", thinking it was the appropriate combination based on a
> FIXME comment. I will try building it again with only "no-assertions" and
> report back.
>
> 2016-10-05 18:28 GMT+02:00 Jordan Rose :
>
>> Aha, so the second bug is because home-built toolchains have assertions
>> on by default and Xcode GM toolchains generally have them off. (Not a
>> promise, but true of the last few Xcodes.) Of course, if you hit an
>> assertion failure, there’s no telling what the no-asserts build is actually
>> doing.
>>
>> I’m not so sure the first bug falls into the same category yet, but it
>> might as well.
>>
>> Jordan
>>
>>
>> > On Oct 4, 2016, at 14:05, Jordan Rose via swift-dev <
>> swift-dev@swift.org> wrote:
>> >
>> > Thanks, Xavi. Hopefully these aren't blocking you in Xcode 8 either (in
>> either Swift 2.3 or Swift 3).
>> >
>> >> On Oct 4, 2016, at 8:03, Xavier Jurado via swift-dev <
>> swift-dev@swift.org> wrote:
>> >>
>> >> Hello Jordan,
>> >>
>> >> We have filled two bugs against bugs.swift.org to document two crashes
>> >> that are only reproducible with our toolchain built from the
>> >> swift-2.2.1-RELEASE tag, but that appear fixed in the official
>> >> toolchain bundled with Xcode 7.3.1 (7D1014).
>> >>
>> >> Crashers:
>> >>
>> >> https://bugs.swift.org/browse/SR-2844
>> >> https://bugs.swift.org/browse/SR-2845
>> >>
>> >> Since using the official toolchain somehow fixes the issues we realize
>> >> they are far from critical, but we have reported them in hope of
>> >> finding the discrepancies between the official toolchain and the the
>> >> tagged releases.
>> >>
>> >> Thanks,
>> >> Xavi
>> >> ___
>> >> 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
>>
>>
>
___
swift-dev mailing list
swift-dev@swift.org
https://lists.swift.org/mailman/listinfo/swift-dev

Re: [swift-dev] Having 64-bit swift_retain/release ignore all negative pointer values

[Alexis via swift-dev]

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  
> wrote:
> 
> 
>> On Mar 1, 2016, at 1:33 PM, Joe Groff via swift-dev > > 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 0x  to 0x7fff .
> 
> 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

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

Re: [swift-dev] Having 64-bit swift_retain/release ignore all negative pointer values

[Joe Groff via swift-dev]

> On Oct 13, 2016, at 1:18 PM, Greg Parker  wrote:
> 
> 
>> On Oct 13, 2016, at 10:46 AM, John McCall via swift-dev 
>>  wrote:
>> 
>>> On Oct 13, 2016, at 9:04 AM, Joe Groff via swift-dev  
>>> wrote:
>>> 
 On Mar 1, 2016, at 1:33 PM, Joe Groff via swift-dev  
 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 0x  to 0x7fff .
>>> 
>>> 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. 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

Re: [swift-dev] Having 64-bit swift_retain/release ignore all negative pointer values

[Greg Parker via swift-dev]

> On Oct 13, 2016, at 10:46 AM, John McCall via swift-dev  
> wrote:
> 
>> On Oct 13, 2016, at 9:04 AM, Joe Groff via swift-dev > > wrote:
>> 
>>> On Mar 1, 2016, at 1:33 PM, Joe Groff via swift-dev >> > 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 0x  to 0x7fff .
>> 
>> 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. 


-- 
Greg Parker gpar...@apple.com  Runtime 
Wrangler


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

[swift-dev] Dictionary Collision Resolution Guarantees

[Alexis via swift-dev]

I’m currently cleaning up the docs on Dictionary to reflect the new indexing 
model, and I stumbled across the note that the following code should work 
assuming no reallocations occur:

//
//   var (i, found) = d.find(k) // i is associated with d's buffer
//   if found {
//  var e = d// now d is sharing its data with e
//  e[newKey] = newValue // e now has a unique copy of the data
//  return e[i]  // use i to access e
//   }
//

This is effectively assuming that the open-addressing scheme being used is 
first-come-first-serve (FCFS). That is, any element being inserted can *only* 
be inserted into vacant buckets, rather than displacing existing elements. This 
is currently only internal docs, but do we actually want to guarantee this? The 
popular alternative of robin hood (RH) doesn’t follow this.

Some background: One interesting optimization avenue worth exploring is to 
tweak Dictionary to store hashes, rather than bits, to identify occupied slots 
(with some careful masking so that 0 still means “unoccupied”). Then searching 
for elements can be implemented as follows:

let hash = hashFromKey(key)
var i = indexFromHash(hash)
while true {
  if hashes[i] == 0 {
// vacant, not contained
  } else if hashes[i] == hash {
// maybe already exists?
if keys[i] == key {
  // actually exists
}
  }
  i = nextIndex(i)
}

The interesting property of this is that it almost all of the search time is 
spent linearly walking through an array and doing simple comparisons on 
integers, which is of course really easy to optimize (potentially even SIMD). 
99.% of the time, if the element isn’t stored in the Dictionary, then 
you’ll just hit a 0 hash, and never look at the keys. Similarly, 99.% of 
the time, if the element *is* stored in the Dictionary, you’ll only do a single 
key comparison (on the actually equal element). So this is also really great 
for cache — pretty much all of your access are just linear scans of the hashes. 

The main downside is you’re now “wasting” more memory to store hashes, but you 
can potentially compensate for this by truncating the hashes to 8/16 bits for 
small Dictionaries (which will be better for SIMD anyway).

So what does this have to do with the RH scheme? Compared to FCFS, RH generally 
leads to lower variance on search distances, and provides a mechanism to 
short-circuit long runs if you have the hashes handy. If you find hashes which 
want to live later in the array than where you started, then the current 
element definitely isn’t contained. This means you can increase the load factor 
on your dictionary and further improve cache/memory usage (compensating for the 
memory-usage loss from storing hashes). However it will be prohibitively 
expensive if you require hashes to be recomputed on-the-fly.
___
swift-dev mailing list
swift-dev@swift.org
https://lists.swift.org/mailman/listinfo/swift-dev

Re: [swift-dev] Validating ABI consistency between runtime C++ and standard library Swift code

[John McCall via swift-dev]

> On Oct 13, 2016, at 9:30 AM, Michael Gottesman  wrote:
>> On Oct 12, 2016, at 4:36 PM, John McCall via swift-dev > > wrote:
>> 
>>> On Oct 12, 2016, at 3:46 PM, Greg Parker >> > wrote:
 On Oct 12, 2016, at 11:11 AM, John McCall via swift-dev 
 mailto:swift-dev@swift.org>> wrote:
 
> On Oct 11, 2016, at 8:10 PM, Joe Groff via swift-dev  > wrote:
> I just tracked down a bug due to C++ code in the Swift runtime code 
> trying to interface with standard library code written in Swift, but 
> getting the ABI slightly wrong and leading to some nasty 
> hard-to-reproduce heisenbugs. While I've narrowed down the bug in this 
> specific case, it seems like this is a potentially continuing source of 
> maintenance bugs, especially as we try to bring up the Swift calling 
> convention in the coming year. I'm wondering if there's anything we could 
> do to help validate that C++ and Swift code in the runtime is correctly 
> interfacing. We could at least check that we're passing the right number 
> of arguments by comparing the LLVM IR of the runtime and stdlib, perhaps, 
> though this would have to be a fuzzy type-level match since Clang and 
> Swift aren't normally going to agree on the exact pointer types of 
> arguments.
 
 One potential approach:  make a def file with the names and (somehow 
 abstracted) expected prototypes of Swift functions defined by the standard 
 library but used by the runtime.  In the runtime, use that to autogenerate 
 a header.  In IRGen, add a +Asserts check before finalizing the module 
 that, if there are any functions with those names, they do match the 
 abstract prototypes.  Hope that all such interactions use only portable 
 IRGen call-lowering patterns.
>>> 
>>> Or perhaps have a swiftc mode that generates a C prototype for every 
>>> function marked with @_silgen_name, and use that to build an autogenerated 
>>> C header. (I.e., skip the def file and use the swift file as the canonical 
>>> description.)
>> 
>> That's nice in theory, but it creates a build dependency between the C++ and 
>> Swift sources wherever we want to do this.
> 
> I have not thought about the build dependency issue, but just off the top of 
> my head, using it for building seems unnecessary. That is we could instead of 
> using the autogenerated C header file for compilation, just generate those 
> files for testing purposes. Then we could still use the .def file normally, 
> but could at least have a bot that checks that things are correct.
> 
> I am not sure if there is a clang mode for diffing/comparing declarations 
> like these though.

If we have to have a .def file, just consuming it for assertions in IRGen seems 
like the way to go.

John.

> 
> Michael
> 
>> 
>> John.
>> ___
>> 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

Re: [swift-dev] Having 64-bit swift_retain/release ignore all negative pointer values

[John McCall via swift-dev]

> On Oct 13, 2016, at 9:04 AM, Joe Groff via swift-dev  
> wrote:
> 
> 
>> On Mar 1, 2016, at 1:33 PM, Joe Groff via swift-dev > > 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 0x  to 0x7fff .
> 
> 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;

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

Re: [swift-dev] copy-on-write proposal

[Joe Groff via swift-dev]

> On Oct 11, 2016, at 4:48 PM, Erik Eckstein via swift-dev 
>  wrote:
> 
> This is a proposal for representing copy-on-write buffers in SIL. Actually 
> it’s still a draft for a proposal. It also heavily depends on how we move 
> forward with SIL ownership.
> 
> If you have any comments, please let me know.

The SIL-level design seems sensible to me at a glance. At the language level, I 
think it would make more sense to treat this as an attribute on class types 
rather than on properties in structs using the class. I don't think many people 
reuse class definitions as both shared reference types and as value type 
payloads, but beyond that, I think that making it an attribute of classes would 
put us into a better position to leverage the borrow model to enforce the 
"mutable-only-when-unique" aspect of COW implementations. John alluded to this 
in the "SIL address types and borrowing" thread:

> I wonder if it would make more sense to make copy-on-write buffer references 
> a move-only type, so that as long as you were just working with the raw 
> reference (as opposed to the CoW aggregate, which would remain copyable) it 
> wouldn't get implicitly copied anymore.  You could have mutable and immutable 
> buffer reference types, both move-only, and there could be a consuming 
> checkUnique operation on the immutable one that, I dunno, returned an Either 
> of the mutable and immutable versions.
> 
> For CoW aggregates, you'd need some @copied attribute on the field to make 
> sure that the CoW attribute was still copyable.  Within the implementation of 
> the type, though, you would be projecting out the reference immediately, and 
> thereafter you'd be certain that you were borrowing / moving it around as 
> appropriate.

If 'copy-on-write' were a trait on classes, then we could distinguish unique 
and nonunique references to the class. A unique reference would act like a 
move-only type to prevent accidental loss of uniqueness. We can also allow a 
copy-on-write class to have "mutating" methods, and only allow mutation on 
unique references. It seems to me like, exploring this direction, we could also 
come up with a way for the high-level value-semantics operations on the struct 
to statically indicate which methods are known to leave the value's buffers in 
a unique state, or which return values that are uniquely owned, which would 
give the optimizer more ability to avoid uniqueness checks across calls without 
relying on inlining and IPO.

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

Re: [swift-dev] Validating ABI consistency between runtime C++ and standard library Swift code

[Michael Gottesman via swift-dev]

> On Oct 12, 2016, at 4:36 PM, John McCall via swift-dev  
> wrote:
> 
>> On Oct 12, 2016, at 3:46 PM, Greg Parker > > wrote:
>>> On Oct 12, 2016, at 11:11 AM, John McCall via swift-dev 
>>> mailto:swift-dev@swift.org>> wrote:
>>> 
 On Oct 11, 2016, at 8:10 PM, Joe Groff via swift-dev >>> > wrote:
 I just tracked down a bug due to C++ code in the Swift runtime code trying 
 to interface with standard library code written in Swift, but getting the 
 ABI slightly wrong and leading to some nasty hard-to-reproduce heisenbugs. 
 While I've narrowed down the bug in this specific case, it seems like this 
 is a potentially continuing source of maintenance bugs, especially as we 
 try to bring up the Swift calling convention in the coming year. I'm 
 wondering if there's anything we could do to help validate that C++ and 
 Swift code in the runtime is correctly interfacing. We could at least 
 check that we're passing the right number of arguments by comparing the 
 LLVM IR of the runtime and stdlib, perhaps, though this would have to be a 
 fuzzy type-level match since Clang and Swift aren't normally going to 
 agree on the exact pointer types of arguments.
>>> 
>>> One potential approach:  make a def file with the names and (somehow 
>>> abstracted) expected prototypes of Swift functions defined by the standard 
>>> library but used by the runtime.  In the runtime, use that to autogenerate 
>>> a header.  In IRGen, add a +Asserts check before finalizing the module 
>>> that, if there are any functions with those names, they do match the 
>>> abstract prototypes.  Hope that all such interactions use only portable 
>>> IRGen call-lowering patterns.
>> 
>> Or perhaps have a swiftc mode that generates a C prototype for every 
>> function marked with @_silgen_name, and use that to build an autogenerated C 
>> header. (I.e., skip the def file and use the swift file as the canonical 
>> description.)
> 
> That's nice in theory, but it creates a build dependency between the C++ and 
> Swift sources wherever we want to do this.

I have not thought about the build dependency issue, but just off the top of my 
head, using it for building seems unnecessary. That is we could instead of 
using the autogenerated C header file for compilation, just generate those 
files for testing purposes. Then we could still use the .def file normally, but 
could at least have a bot that checks that things are correct.

I am not sure if there is a clang mode for diffing/comparing declarations like 
these though.

Michael

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

Re: [swift-dev] Having 64-bit swift_retain/release ignore all negative pointer values

[Joe Groff via swift-dev]

> On Mar 1, 2016, at 1:33 PM, Joe Groff via swift-dev  
> 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 0x  to 0x7fff .

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