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

[John McCall]

> On Nov 7, 2016, at 4:59 PM, Dave Abrahams <dabrahams at apple.com> wrote:
> on Mon Nov 07 2016, John McCall <rjmccall-AT-apple.com> 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.
>> 
>> Well, if we can eliminate the unsafe, copyable types, that would be
>> great, of course.  I don't know whether that's achievable given our C
>> interop goals.
> 
> I'm not suggesting we can do that.  
> 
> I'm suggesting that in order to get a copy of some borrowed thing, you
> might have to utter the word "unsafe" because it's a thing that can't
> escape without compromising static safety guarantees, e.g. (strawman
> syntax):
> 
>   interop_with_c(unsafe { someBuffer })

Hmm.  We might be able to to do this.

John.

>> Another option is to attack escapes directly.  The safety guarantee
>> you're looking for is just that the value doesn't escape its scope,
>> and while it's true that move-only borrowed values aren't allowed to
>> escape, that constraint doesn't *require* borrowing or move-only-ness
>> to work.  We already have non-escaping values in the language —
>> noescape functions — and there's nothing stopping us from applying
>> that same logic to other types.  
> 
> Sure, but if a copyable version of a type is unsafe to handle, and
> “unsafe” is encoded into the type's name, we end up with no way to
> represent in code the fact that an instance that's been statically
> constrained to be borrowed and non-escaping is actually safe.
> 
> Look, today we have 
> 
>   a.withUnsafeBufferPointer {
>      ...
>   }
> 
> Now, if we had a version of UnsafeBufferPointer that included bounds
> checking, we'd still need to spell that 
> 
>   a.withUnsafeBoundsCheckedBufferPointer {
>      ...
>   }
> 
> today.  With first-class ownership, it could be
> 
>   a.withBoundsCheckedBufferPointer {
>      ...
>   }
> 
> totally safe!  So what does that imply about the name we'll use for the
> type of the closure parameter?
> 
>> There would be annotation problems, though, since existing functions
>> operating on pointers would be allowed to escape them.
> 
> Not sure what you have in mind here.
> 
> -- 
> -Dave