[swift-evolution] Contiguous Memory and the Effect of Borrowing on Safety

Dave Abrahams dabrahams at apple.com
Fri Nov 11 11:26:42 CST 2016

on Fri Nov 11 2016, Alexis <abeingessner-AT-apple.com> wrote:

>> On Nov 10, 2016, at 8:17 PM, Dave Abrahams via swift-evolution <swift-evolution at swift.org> wrote:
>> on Thu Nov 10 2016, Joe Groff <jgroff-AT-apple.com <http://jgroff-at-apple.com/>> wrote:
>>>> On Nov 10, 2016, at 1:02 PM, Dave Abrahams <dabrahams at apple.com> wrote:
>>>> on Thu Nov 10 2016, Stephen Canon <scanon-AT-apple.com> wrote:
>>>>>> On Nov 10, 2016, at 1:30 PM, Dave Abrahams via swift-evolution <swift-evolution at swift.org> wrote:
>>>>>> on Thu Nov 10 2016, Joe Groff <jgroff-AT-apple.com> wrote:
>>>>>>>> On Nov 8, 2016, at 9:29 AM, John McCall <rjmccall at apple.com> wrote:
>>>>>>>>> On Nov 8, 2016, at 7:44 AM, Joe Groff via swift-evolution <swift-evolution at swift.org> wrote:
>>>>>>>>>> On Nov 7, 2016, at 3:55 PM, Dave Abrahams via swift-evolution <swift-evolution at swift.org> wrote:
>>>>>>>>>> on Mon Nov 07 2016, John McCall <swift-evolution at swift.org> wrote:
>>>>>>>>>>>> On Nov 6, 2016, at 1:20 PM, Dave Abrahams via swift-evolution <swift-evolution at swift.org> wrote:
>>>>>>>>>>>> Given that we're headed for ABI (and thus stdlib API) stability, I've
>>>>>>>>>>>> been giving lots of thought to the bottom layer of our collection
>>>>>>>>>>>> abstraction and how it may limit our potential for efficiency.  In
>>>>>>>>>>>> particular, I want to keep the door open for optimizations that work on
>>>>>>>>>>>> contiguous memory regions.  Every cache-friendly data structure, even if
>>>>>>>>>>>> it is not an array, contains contiguous memory regions over which
>>>>>>>>>>>> operations can often be vectorized, that should define boundaries for
>>>>>>>>>>>> parallelism, etc.  Throughout Cocoa you can find patterns designed to
>>>>>>>>>>>> exploit this fact when possible (NSFastEnumeration).  Posix I/O bottoms
>>>>>>>>>>>> out in readv/writev, and MPI datatypes essentially boil down to
>>>>>>>>>>>> identifying the contiguous parts of data structures.  My point is that
>>>>>>>>>>>> this is an important class of optimization, with numerous real-world
>>>>>>>>>>>> examples.
>>>>>>>>>>>> If you think about what it means to build APIs for contiguous memory
>>>>>>>>>>>> into abstractions like Sequence or Collection, at least without
>>>>>>>>>>>> penalizing the lowest-level code, it means exposing UnsafeBufferPointers
>>>>>>>>>>>> as a first-class part of the protocols, which is really
>>>>>>>>>>>> unappealing... unless you consider that *borrowed* UnsafeBufferPointers
>>>>>>>>>>>> can be made safe.  
>>>>>>>>>>>> [Well, it's slightly more complicated than that because
>>>>>>>>>>>> UnsafeBufferPointer is designed to bypass bounds checking in release
>>>>>>>>>>>> builds, and to ensure safety you'd need a BoundsCheckedBuffer—or
>>>>>>>>>>>> something—that checks bounds unconditionally... but] the point remains
>>>>>>>>>>>> that
>>>>>>>>>>>> A thing that is unsafe when it's arbitrarily copied can become safe if
>>>>>>>>>>>> you ensure that it's only borrowed (in accordance with well-understood
>>>>>>>>>>>> lifetime rules).
>>>>>>>>>>> UnsafeBufferPointer today is a copyable type.  Having a borrowed value
>>>>>>>>>>> doesn't prevent you from making your own copy, which could then escape
>>>>>>>>>>> the scope that was guaranteeing safety.
>>>>>>>>>>> This is fixable, of course, but it's a more significant change to the
>>>>>>>>>>> type and how it would be used.
>>>>>>>>>> It sounds like you're saying that, to get static safety benefits from
>>>>>>>>>> ownership, we'll need a whole parallel universe of safe move-only
>>>>>>>>>> types. Seems a cryin' shame.
>>>>>>>>> We've discussed the possibility of types being able to control
>>>>>>>>> their "borrowed" representation. Even if this isn't something we
>>>>>>>>> generalize, arrays and contiguous buffers might be important enough
>>>>>>>>> to the language that your safe BufferPointer could be called
>>>>>>>>> 'borrowed ArraySlice<T>', with the owner backreference optimized
>>>>>>>>> out of the borrowed representation. Perhaps Array's own borrowed
>>>>>>>>> representation would benefit from acting like a slice rather than a
>>>>>>>>> whole-buffer borrow too.
>>>>>>>> The disadvantage of doing this is that it much more heavily
>>>>>>>> penalizes the case where we actually do a copy from a borrowed
>>>>>>>> reference — it becomes an actual array copy, not just a reference
>>>>>>>> bump.
>>>>>>> Fair point, though the ArraySlice/Array dichotomy strikes me as
>>>>>>> already kind of encouraging this—you might pass ArraySlices down into
>>>>>>> your algorithm, but we encourage people to use Array at storage and
>>>>>>> API boundaries, forcing copies.
>>>>>>> From a philosophical perspective of making systems Swift feel like
>>>>>>> "the same language" as Swift today, it feels better to me to try to
>>>>>>> express this as making our high-level safe abstractions efficient
>>>>>>> rather than making our low-level unsafe abstractions safe. 
>>>>>> +1, or maybe 10
>>>>>> What worries me is that if systems programmers are trying to get static
>>>>>> guarantees that there's no ARC traffic, they won't be willing to handle
>>>>>> a copyable thing that carries ownership.
>>>>> FWIW, we (frequently) only need a static guarantee of no ARC traffic
>>>>> *within a critical section*. If we can guarantee that whatever ARC
>>>>> operations need to be done happen in a precisely-controlled manner at
>>>>> a known interface boundary, that’s often good enough.
>>>> I don't think you can get those guarantees without static protection
>>>> against escaping borrowed references, though, can you?
>>> You shouldn't be able to do that without copying it, and copying a
>>> borrow seems like it ought to at least be explicit.
>> I don't think that's true for all types (e.g. Int).
>> But regardless, we've come full circle, because I'm talking
>> about needing to do something explicit to copy a a borrowed type when
>> copying it will be unsafe.
> I’m a bit confused by this. Presumably 99.999% of string slices would
> be an immutable view. Almost no unicode correct code has any business
> mutating the contents of a fixed-sized string buffer. (data point: the
> `&mut str` type exists in Rust, but literally every interface I’ve
> ever seen handles `&str`). If the views are immutable, they’re safe to
> copy as long as every copy “remembers” that it’s noescape or whatever
> you want to call it.

If copies can do that, they are the moral equivalent of borrows.  The
unsafe copies are the ones that can escape.


More information about the swift-evolution mailing list