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

[Alexis]

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

> 
> -- 
> -Dave
> _______________________________________________
> swift-evolution mailing list
> swift-evolution at swift.org <mailto:swift-evolution at swift.org>
> https://lists.swift.org/mailman/listinfo/swift-evolution <https://lists.swift.org/mailman/listinfo/swift-evolution>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20161111/0330152d/attachment.html>