[idle] COW wrapper in 30 lines


(Jordan Rose) #1

Just for fun, I wrote a wrapper for COW types that don't need the flexible inline storage of ManagedBuffer. It turned out to be pretty straightforward, though I didn't bother with materializeForSet and thus am incurring the cost of many extra value copies on mutation. The major downside is having to forward all operations through, something I'm sure the implementers of Array and Dictionary are very used to!

Disclaimer: This is not performant; don't use it in your app.

Jordan

cow.swift (982 Bytes)


(Nadav Rotem) #2

HI Jordan,

Very Nice!

There is a similar implementation and discussion about performance here:

https://github.com/apple/swift/blob/master/docs/OptimizationTips.rst#advice-use-copy-on-write-semantics-for-large-values

-Nadav

···

On Mar 9, 2016, at 9:39 AM, Jordan Rose via swift-dev <swift-dev@swift.org> wrote:

Just for fun, I wrote a wrapper for COW types that don't need the flexible inline storage of ManagedBuffer. It turned out to be pretty straightforward, though I didn't bother with materializeForSet and thus am incurring the cost of many extra value copies on mutation. The major downside is having to forward all operations through, something I'm sure the implementers of Array and Dictionary are very used to!

Disclaimer: This is not performant; don't use it in your app.

Jordan

<cow.swift>
_______________________________________________
swift-dev mailing list
swift-dev@swift.org
https://lists.swift.org/mailman/listinfo/swift-dev


(Dave Abrahams) #3

Several issues with this:

1. a performant CoW type will often *not* want to start by copying
   itself when there is a mutation. A trivial example: when you clear
   an Array. So a simpleminded “always make a copy when I write the
   value” approach is not going to scale.

2. The thing in your box has to be a value type for this to work. It's
   pretty uncommon that a thing that's already a value type benefits
   from being CoW-ified in this way. That could usually only happen
   when it is quite atypically large. It's a fine optimization to make
   when you can use it, but it doesn't change the programming model.
   The more interesting case for CoW is to produce value semantics where
   you otherwise wouldn't have it (e.g. Array).

···

on Wed Mar 09 2016, Jordan Rose <swift-dev-AT-swift.org> wrote:

Just for fun, I wrote a wrapper for COW types that don't need the flexible inline storage of ManagedBuffer. It turned
out to be pretty straightforward, though I didn't bother with materializeForSet and thus am incurring the cost of
many extra value copies on mutation. The major downside is having to forward all operations through, something I'm
sure the implementers of Array and Dictionary are very used to!

Disclaimer: This is not performant; don't use it in your app.

--
-Dave


(Jordan Rose) #4

Ha, I remember this document, but forgot it included an implementation. Encouraging to see that it's pretty much identical.

The concrete type forwarding logic is something we ought to be able to simplify somehow (with new language features).

Jordan

···

On Mar 9, 2016, at 9:50 , Nadav Rotem <nrotem@apple.com> wrote:

HI Jordan,

Very Nice!

There is a similar implementation and discussion about performance here:

https://github.com/apple/swift/blob/master/docs/OptimizationTips.rst#advice-use-copy-on-write-semantics-for-large-values

-Nadav

On Mar 9, 2016, at 9:39 AM, Jordan Rose via swift-dev <swift-dev@swift.org> wrote:

Just for fun, I wrote a wrapper for COW types that don't need the flexible inline storage of ManagedBuffer. It turned out to be pretty straightforward, though I didn't bother with materializeForSet and thus am incurring the cost of many extra value copies on mutation. The major downside is having to forward all operations through, something I'm sure the implementers of Array and Dictionary are very used to!

Disclaimer: This is not performant; don't use it in your app.

Jordan

<cow.swift>
_______________________________________________
swift-dev mailing list
swift-dev@swift.org
https://lists.swift.org/mailman/listinfo/swift-dev


(Joe Groff) #5

It doesn't need to be particularly large—if your value type contains two or more refcounted fields, it becomes cheaper to retain/release a single indirect box than to copy around the entire value inline.

-Joe

···

On Mar 10, 2016, at 3:54 PM, Dave Abrahams via swift-dev <swift-dev@swift.org> wrote:

2. The thing in your box has to be a value type for this to work. It's
  pretty uncommon that a thing that's already a value type benefits
  from being CoW-ified in this way.


(Arnold Schwaighofer) #6

Nice!

As you have mentioned, unfortunately, this does not work on nested types without spurious copies (e.g. for foo.left.value.right.value = …). You would need to implement this with a mutableAddressor. Unfortunately, doing so requires Builtins and so this can’t currently be done outside of the standard library (without nasty flags).

0001-A-copy-on-write-data-type.patch (4.06 KB)


(Dave Abrahams) #7

You do have to trade that off against the cost of the allocation, but
you make a good point. I'd guess that value instances are probably
copied more often than they're created in other ways.

···

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

On Mar 10, 2016, at 3:54 PM, Dave Abrahams via swift-dev <swift-dev@swift.org> wrote:

2. The thing in your box has to be a value type for this to work. It's
  pretty uncommon that a thing that's already a value type benefits
  from being CoW-ified in this way.

It doesn't need to be particularly large—if your value type contains
two or more refcounted fields, it becomes cheaper to retain/release a
single indirect box than to copy around the entire value inline.

--
-Dave


(Jordan Rose) #8

Wouldn't materializeForSet be good enough? I guess that's one extra copy if you don't want to rely on things not guaranteed by the language (i.e. "fields of classes have stable addresses").

Jordan

···

On Mar 10, 2016, at 7:43 , Arnold Schwaighofer <aschwaighofer@apple.com> wrote:

Nice!

As you have mentioned, unfortunately, this does not work on nested types without spurious copies (e.g. for foo.left.value.right.value = …). You would need to implement this with a mutableAddressor. Unfortunately, doing so requires Builtins and so this can’t currently be done outside of the standard library (without nasty flags).

<0001-A-copy-on-write-data-type.patch>

I agree with you that some interface forwarding would be an awesome language feature to have.

It would allow for implementing an indirect storage wrapper without lots of boilerplate.

Consider an example where you have value types that implement a protocol:

public _MyProtoWithoutAsscociatedType {
}

public protocol MyProtocol : MyProtoWithoutAsscociatedType {
associatedtype Assoc

public func doThis(v : Assoc)
public func doThat()

public static func initAssocType() -> Assoc

}

struct MyProtocolImplementation : MyProtocol {
typealias Assoc = Int
var a : AReference
var b : AReference
var c : AReference
var d : Double

func doThis(v: Assoc) {…}
func doThat() {…}

static func initAssocType() -> Assoc {
   return 0
}
}

Your application passes those value types as existential values or as generic values because the architecture requires that. This can incur lots of allocations at every value copy for this example value type because we don’t fit in the inline buffer (three pointer words) which would be allocated inline (on the stack or as a stored property for existentials).

One way to work around this is today is make your value type’s storage indirect via a wrapper such that it will always fit in inline storage.

class _BoxStorage<T> {
   final var value: T

   init(_ elt: T) {
       value = elt
   }
}

public struct Indirect<V : MyProtocol> : MyProcotol {

   public typealias Assoc = V.Assoc

   final var _storage: _BoxStorage<V>

   public init(_ elt: V) {
       _storage = _BoxStorage(elt)
   }

   internal var value: V {
       get {
           return _storage.value
       }
       mutableAddressWithNativeOwner {
           if !isUniquelyReferencedNonObjC(&_storage) {
               _storage = _BoxStorage(_storage.value)
           }
           return (
               UnsafeMutablePointer(Builtin.addressof(&_storage.value)),
               Builtin.castToNativeObject(_storage))
       }
   }

   public static func initAssocType() -> Assoc {
       return Assoc.initAssocType()
   }

   public func doThis(v: Assoc) {
     value.doThis(v)
   }
   public func doThat() {
     value.doThat()
   }
}

Indeed, doing so would require a lot of boiler plate.

Instead the following would be much nicer:

public struct Indirect<V : MyProtocol> : MyProcotol {

   public typealias Assoc = V.Assoc

   final var _storage: _BoxStorage<V>

   public init(_ elt: V) {
       _storage = _BoxStorage(elt)
   }

   internal forwarding var value: V as MyProtocol {
       typealias Assoc = V.Assoc

       get {
           return _storage.value
       }
       mutableAddressWithNativeOwner {
           if !isUniquelyReferencedNonObjC(&_storage) {
               _storage = _BoxStorage(_storage.value)
           }
           return (
               UnsafeMutablePointer(Builtin.addressof(&_storage.value)),
               Builtin.castToNativeObject(_storage))
       }
   }

}

On Mar 9, 2016, at 9:53 AM, Jordan Rose via swift-dev <swift-dev@swift.org> wrote:

Ha, I remember this document, but forgot it included an implementation. Encouraging to see that it's pretty much identical.

The concrete type forwarding logic is something we ought to be able to simplify somehow (with new language features).

Jordan

On Mar 9, 2016, at 9:50 , Nadav Rotem <nrotem@apple.com> wrote:

HI Jordan,

Very Nice!

There is a similar implementation and discussion about performance here:

https://github.com/apple/swift/blob/master/docs/OptimizationTips.rst#advice-use-copy-on-write-semantics-for-large-values

-Nadav

On Mar 9, 2016, at 9:39 AM, Jordan Rose via swift-dev <swift-dev@swift.org> wrote:

Just for fun, I wrote a wrapper for COW types that don't need the flexible inline storage of ManagedBuffer. It turned out to be pretty straightforward, though I didn't bother with materializeForSet and thus am incurring the cost of many extra value copies on mutation. The major downside is having to forward all operations through, something I'm sure the implementers of Array and Dictionary are very used to!

Disclaimer: This is not performant; don't use it in your app.

Jordan

<cow.swift>
_______________________________________________
swift-dev mailing list
swift-dev@swift.org
https://lists.swift.org/mailman/listinfo/swift-dev

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