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

[Dave Abrahams]

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 })

> 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