Contiguous Memory and the Effect of Borrowing on Safety


(Dave Abrahams) #1

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

And this leads me to wonder about our practice of embedding the word
"unsafe" in names. A construct that is only conditionally unsafe
shouldn't be spelled "unsafe" when used in a safe way, right? So this
*seems* to argue for an "unsafe" keyword that can be used to label
the constructs that actually add unsafety (as has been previously
suggested on this list). Other ideas are of course most welcome.

···

--
-Dave


(Daniel Duan) #2

A construct that is only conditionally unsafe
shouldn't be spelled "unsafe" when used in a safe way, right? So this
*seems* to argue for an "unsafe" keyword that can be used to label
the constructs that actually add unsafety (as has been previously
suggested on this list). Other ideas are of course most welcome.

How would “unsafe” coexist with memory ownership model? It seems to me that there’s some overlapping concepts here (borrowed/moved). I haven’t formulated any complete thoughts on this topic. Just had a feeling that we should take the ownership model in mind as we tackle this.

···

On Nov 6, 2016, at 1:20 PM, Dave Abrahams via swift-evolution <swift-evolution@swift.org> wrote:

--
-Dave

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution


(Hooman Mehr) #3

Yes, this is a very important issue to consider before we freeze them.

As part of my Swift hobby, I have worked a bit on a Swifty wrapper for linear algebra packages and also toyed a bit with the merits of a Swift implementation of some of the related algorithms and data structures (such as banded or sparse matrices)

It is really difficult to come up with efficient and generic solutions in these spaces. I had a brush with Julia <http://julialang.org/> as well. Have you looked at their work and the recent reworking of their similar data structures?

···

On Nov 6, 2016, at 1:20 PM, Dave Abrahams via swift-evolution <swift-evolution@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).

And this leads me to wonder about our practice of embedding the word
"unsafe" in names. A construct that is only conditionally unsafe
shouldn't be spelled "unsafe" when used in a safe way, right? So this
*seems* to argue for an "unsafe" keyword that can be used to label
the constructs that actually add unsafety (as has been previously
suggested on this list). Other ideas are of course most welcome.

--
-Dave

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution


(John McCall) #4

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.

John.

···

On Nov 6, 2016, at 1:20 PM, Dave Abrahams via swift-evolution <swift-evolution@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).


(Alexis) #5

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

And this leads me to wonder about our practice of embedding the word
"unsafe" in names. A construct that is only conditionally unsafe
shouldn't be spelled "unsafe" when used in a safe way, right? So this
*seems* to argue for an "unsafe" keyword that can be used to label
the constructs that actually add unsafety (as has been previously
suggested on this list). Other ideas are of course most welcome.

Yes, I’ve always found this more appealing (“operations are unsafe, not types”). This allows you to make more subtle distinctions, and expose “low level” APIs for otherwise safe types (e.g. unchecked indexing on Array). I believe Graydon made a draft proposal for this a while back, but neither of us can recall what became of it.

That said, in this particular case the distinction isn’t very helpful: basically everything you can do with an Unsafe(Buffer)Pointer is truly unsafe today, and I wouldn’t really expect this to change with ownership stuff. You need a completely unchecked pointer type for the very lowest levels of abstractions, where scoped lifetimes can’t capture the relationships that are involved.

I would expect there to be two types of interest, one with safe borrowed semantics (Pointer/BufferPointer?), and one with unsafe unchecked semantics (today’s UnsafePointer/UnsafeBufferPointer). For those familiar with Rust, this is roughly equivalent to: &T, &[T], *mut T, and *mut [T] respectively. Most APIs should operate in terms of the safe types, requiring the holder of an unsafe type to do some kind of cast, asserting that the whatever guarantees the safe types make will be upheld.

99% of code should subsequently never actually interact with the Unsafe types, instead using the safe ones. Anything using the Unsafe types should subsequently try to get into the world of safe types as fast as possible. For instance, much of Rust’s growable array type (Vec) is implemented as “convert my unsafe pointer into a safe, borrowed slice, then operate on the slice”. Similarly, any API which is interested in passing around a non-growable pile of memory communicates in terms of these slices.

···

On Nov 6, 2016, at 4:20 PM, Dave Abrahams via swift-evolution <swift-evolution@swift.org> wrote:

--
-Dave

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution


(Dave Abrahams) #6

A construct that is only conditionally unsafe
shouldn't be spelled "unsafe" when used in a safe way, right? So this
*seems* to argue for an "unsafe" keyword that can be used to label
the constructs that actually add unsafety (as has been previously
suggested on this list). Other ideas are of course most welcome.

How would “unsafe” coexist with memory ownership model? It seems to me
that there’s some overlapping concepts here (borrowed/moved).

Yes, the ownership model covers borrowing.

I haven’t formulated any complete thoughts on this topic. Just had a
feeling that we should take the ownership model in mind as we tackle
this.

That was a main point of my posting. Apologies if that wasn't made
clear.

···

on Sun Nov 06 2016, Daniel Duan <daniel-AT-duan.org> wrote:

On Nov 6, 2016, at 1:20 PM, Dave Abrahams via swift-evolution >> <swift-evolution@swift.org> wrote:

--
-Dave


(Dave Abrahams) #7

Yes, this is a very important issue to consider before we freeze them.

As part of my Swift hobby, I have worked a bit on a Swifty wrapper for
linear algebra packages

That domain makes an excellent test case.

and also toyed a bit with the merits of a Swift implementation of some
of the related algorithms and data structures (such as banded or
sparse matrices)

It is really difficult to come up with efficient and generic solutions
in these spaces.

I'm not surprised. The generics system in Swift has a lot of growing up
to do, and until it does that, it's hard to even contemplate the library
abstractions that will be needed.

I had a brush with Julia <http://julialang.org/> as well. Have you
looked at their work

It's been a while, to be honest.

and the recent reworking of their similar data structures?

Links would be appreciated.

···

on Sun Nov 06 2016, Hooman Mehr <swift-evolution@swift.org> wrote:

On Nov 6, 2016, at 1:20 PM, Dave Abrahams via swift-evolution >> <swift-evolution@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).

And this leads me to wonder about our practice of embedding the word
"unsafe" in names. A construct that is only conditionally unsafe
shouldn't be spelled "unsafe" when used in a safe way, right? So this
*seems* to argue for an "unsafe" keyword that can be used to label
the constructs that actually add unsafety (as has been previously
suggested on this list). Other ideas are of course most welcome.

--
-Dave

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

--
-Dave


(Dave Abrahams) #8

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.

···

on Mon Nov 07 2016, John McCall <swift-evolution@swift.org> wrote:

On Nov 6, 2016, at 1:20 PM, Dave Abrahams via swift-evolution <swift-evolution@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.

--
-Dave


(Hooman Mehr) #9

Start with this blog post, if you haven’t already seen it: http://julialang.org/blog/2016/03/arrays-iteration

···

On Nov 6, 2016, at 8:03 PM, Dave Abrahams via swift-evolution <swift-evolution@swift.org> wrote:

I had a brush with Julia <http://julialang.org/> as well. Have you
looked at their work

It's been a while, to be honest.

and the recent reworking of their similar data structures?

Links would be appreciated.


(John McCall) #10

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.

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. There would be annotation problems, though, since existing functions
operating on pointers would be allowed to escape them.

John.

···

On Nov 7, 2016, at 3:55 PM, Dave Abrahams via swift-evolution <swift-evolution@swift.org> wrote:
on Mon Nov 07 2016, John McCall <swift-evolution@swift.org> wrote:

On Nov 6, 2016, at 1:20 PM, Dave Abrahams via swift-evolution <swift-evolution@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.


(Joe Groff) #11

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.

-Joe

···

On Nov 7, 2016, at 3:55 PM, Dave Abrahams via swift-evolution <swift-evolution@swift.org> wrote:

on Mon Nov 07 2016, John McCall <swift-evolution@swift.org> wrote:

On Nov 6, 2016, at 1:20 PM, Dave Abrahams via swift-evolution <swift-evolution@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.


(Dave Abrahams) #12

Thanks!

* It's interesting that they seem to consider every important data
  structure to be some variety of array.

* “I in eachindex(A)” sounds like “for i in A.indices.” But, as I
  presume they are traversing integer indices (or tuples thereof)
  that's really inadequate to deal with sparse arrays if you want
  optimal efficiency, since you end up needing to do (at minimum) a
  binary search to access the array elements.

  IMO, the MTL (https://en.wikipedia.org/wiki/Matrix_Template_Library)
  approach is better: use enhanced iterators that only traverse the
  non-zeroes and can report their coordinates in the underlying matrix.

I don't understand everything written in that post as I lack context
from that community, but my overall impression is that the problems
they're dealing with have well-known solutions and they're somewhat
hamstrung by the idea that indices are fundamentally integers (despite
the fact that they do mention the existence of arrays indexed by
non-integers).

I think one of the most interesting related areas that they don't cover
at all is explored in http://lafstern.org/matt/segmented.pdf (related
video: https://meetingcpp.com/index.php/tv15/items/20.html) which among
other things is applicable to ATLAS-style blocking techniques.

···

on Sun Nov 06 2016, Hooman Mehr <swift-evolution@swift.org> wrote:

On Nov 6, 2016, at 8:03 PM, Dave Abrahams via swift-evolution > <swift-evolution@swift.org> wrote:

I had a brush with Julia <http://julialang.org/> as well. Have you
looked at their work

It's been a while, to be honest.

and the recent reworking of their similar data structures?

Links would be appreciated.

Start with this blog post, if you haven’t already seen it:
http://julialang.org/blog/2016/03/arrays-iteration

--
-Dave


(Dave Abrahams) #13

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.

···

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@swift.org> wrote:
on Mon Nov 07 2016, John McCall <swift-evolution@swift.org> wrote:

On Nov 6, 2016, at 1:20 PM, Dave Abrahams via swift-evolution <swift-evolution@swift.org> wrote:

--
-Dave


(John McCall) #14

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.

John.

···

On Nov 8, 2016, at 7:44 AM, Joe Groff via swift-evolution <swift-evolution@swift.org> wrote:

On Nov 7, 2016, at 3:55 PM, Dave Abrahams via swift-evolution <swift-evolution@swift.org> wrote:

on Mon Nov 07 2016, John McCall <swift-evolution@swift.org> wrote:

On Nov 6, 2016, at 1:20 PM, Dave Abrahams via swift-evolution <swift-evolution@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.


(John McCall) #15

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.

···

On Nov 7, 2016, at 4:59 PM, Dave Abrahams <dabrahams@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@swift.org> wrote:
on Mon Nov 07 2016, John McCall <swift-evolution@swift.org> wrote:

On Nov 6, 2016, at 1:20 PM, Dave Abrahams via swift-evolution <swift-evolution@swift.org> wrote:

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


(Joe Groff) #16

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. Given our short-term goals for the borrow model as I understand them, I don't think we can really make a BufferPointer-like type safe in the way Dave is suggesting, since the pointer fields *inside* the struct need to be first class lifetime-qualified rather than the value of the struct itself. Since Array and ArraySlice already communicate an ownership stake in the memory they reference, a borrowed Array or ArraySlice value *would* safely and efficiently provide access to contiguous memory with only support for first-order borrowed/consumed property declarations and not full first class lifetime support.

-Joe

···

On Nov 8, 2016, at 9:29 AM, John McCall <rjmccall@apple.com> wrote:

On Nov 8, 2016, at 7:44 AM, Joe Groff via swift-evolution <swift-evolution@swift.org> wrote:

On Nov 7, 2016, at 3:55 PM, Dave Abrahams via swift-evolution <swift-evolution@swift.org> wrote:

on Mon Nov 07 2016, John McCall <swift-evolution@swift.org> wrote:

On Nov 6, 2016, at 1:20 PM, Dave Abrahams via swift-evolution <swift-evolution@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.


(Dave Abrahams) #17

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.

Given our short-term goals for the borrow model as I understand them,
I don't think we can really make a BufferPointer-like type safe in the
way Dave is suggesting, since the pointer fields *inside* the struct
need to be first class lifetime-qualified rather than the value of the
struct itself.

Well now, those fields don't have to be public API, and it would be fine
for the implementation of this thing to use unsafe constructs.

···

on Thu Nov 10 2016, Joe Groff <jgroff-AT-apple.com> wrote:

On Nov 8, 2016, at 9:29 AM, John McCall <rjmccall@apple.com> wrote:

On Nov 8, 2016, at 7:44 AM, Joe Groff via swift-evolution <swift-evolution@swift.org> wrote:

On Nov 7, 2016, at 3:55 PM, Dave Abrahams via swift-evolution <swift-evolution@swift.org> wrote:
on Mon Nov 07 2016, John McCall <swift-evolution@swift.org> wrote:

On Nov 6, 2016, at 1:20 PM, Dave Abrahams via swift-evolution <swift-evolution@swift.org> wrote:

Since Array and ArraySlice already communicate an ownership stake in
the memory they reference, a borrowed Array or ArraySlice value
*would* safely and efficiently provide access to contiguous memory
with only support for first-order borrowed/consumed property
declarations and not full first class lifetime support.

--
-Dave


(John McCall) #18

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.

Fair point. In practice, though, I think most algorithms won't need to "escape" that array slice.

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. Given our short-term goals for the borrow model as I understand them, I don't think we can really make a BufferPointer-like type safe in the way Dave is suggesting, since the pointer fields *inside* the struct need to be first class lifetime-qualified rather than the value of the struct itself. Since Array and ArraySlice already communicate an ownership stake in the memory they reference, a borrowed Array or ArraySlice value *would* safely and efficiently provide access to contiguous memory with only support for first-order borrowed/consumed property declarations and not full first class lifetime support.

I agree.

John.

···

On Nov 10, 2016, at 9:31 AM, Joe Groff <jgroff@apple.com> wrote:

On Nov 8, 2016, at 9:29 AM, John McCall <rjmccall@apple.com> wrote:

On Nov 8, 2016, at 7:44 AM, Joe Groff via swift-evolution <swift-evolution@swift.org> wrote:

On Nov 7, 2016, at 3:55 PM, Dave Abrahams via swift-evolution <swift-evolution@swift.org> wrote:
on Mon Nov 07 2016, John McCall <swift-evolution@swift.org> wrote:

On Nov 6, 2016, at 1:20 PM, Dave Abrahams via swift-evolution <swift-evolution@swift.org> wrote:


(Stephen Canon) #19

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.

– Steve

···

On Nov 10, 2016, at 1:30 PM, Dave Abrahams via swift-evolution <swift-evolution@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@apple.com> wrote:

On Nov 8, 2016, at 7:44 AM, Joe Groff via swift-evolution <swift-evolution@swift.org> wrote:

On Nov 7, 2016, at 3:55 PM, Dave Abrahams via swift-evolution <swift-evolution@swift.org> wrote:

on Mon Nov 07 2016, John McCall <swift-evolution@swift.org> wrote:

On Nov 6, 2016, at 1:20 PM, Dave Abrahams via swift-evolution <swift-evolution@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.


(Dave Abrahams) #20

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.

Fair point. In practice, though, I think most algorithms won't need
to "escape" that array slice.

I disagree. I'm working on some generic matching algorithms (to lay the
foundation for String search and regexes). There's going to be a broad
category of functions in this area that work on Strings and return
SubStrings, or work on Collections and return slices thereof. Often
they'll be called from a context where the resultant slices don't
outlive the collection, but they still do need to be returned.

···

on Thu Nov 10 2016, John McCall <rjmccall-AT-apple.com> wrote:

On Nov 10, 2016, at 9:31 AM, Joe Groff <jgroff@apple.com> wrote:

On Nov 8, 2016, at 9:29 AM, John McCall <rjmccall@apple.com> wrote:

On Nov 8, 2016, at 7:44 AM, Joe Groff via swift-evolution <swift-evolution@swift.org> wrote:

On Nov 7, 2016, at 3:55 PM, Dave Abrahams via swift-evolution <swift-evolution@swift.org> > wrote:
on Mon Nov 07 2016, John McCall <swift-evolution@swift.org> wrote:

On Nov 6, 2016, at 1:20 PM, Dave Abrahams via swift-evolution <swift-evolution@swift.org> wrote:

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. Given our
short-term goals for the borrow model as I understand them, I don't
think we can really make a BufferPointer-like type safe in the way
Dave is suggesting, since the pointer fields *inside* the struct
need to be first class lifetime-qualified rather than the value of
the struct itself. Since Array and ArraySlice already communicate an
ownership stake in the memory they reference, a borrowed Array or
ArraySlice value *would* safely and efficiently provide access to
contiguous memory with only support for first-order
borrowed/consumed property declarations and not full first class
lifetime support.

I agree.

John.

--
-Dave