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

[Dave Abrahams]

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

> 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 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).
>> 
>> 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 at swift.org
>> https://lists.swift.org/mailman/listinfo/swift-evolution
>
> _______________________________________________
> swift-evolution mailing list
> swift-evolution at swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution
>

-- 
-Dave