Copy-on-write solves the wrong problem

Evolution Discussion
1

In the 2015 WWDC they gave this interesting example demonstrating problems with reference types:

Class Temperature{
var celsius: Double = 0
var fahrenheit: Double{
get{ return celsius * 9 / 5 + 32 }
set{ celsius = (newValue - 32) * 5 / 9 }
}
}

let home = House()
let temp = Temperature()
temp.fahrenheit = 75
home.thermostat.temperature = temp

temp.fahrenheit = 425
home.oven.temperature = temp
home.oven.bake

And then (ignoring the questionable aspects of the code in general) you wonder why your house is on fire. And this is the problem with reference types, or so the argument goes.

However what I see here is just plain old bad code which isn't using encapsulation properly. It doesn't actually represent a realistic problem, which would be more like:

func myFunc(temp: Temperature) -> Temperature {
// do some calculations on temp then return it.
}

var t = myFunc(home.thermostat.temperature)

and now we have a real problem, because it isn't immediately obvious that what was passed into myFunc came from a reference that we really shouldn't have been modifying. So.. copy-on-write, right?

Except if we do that now we've created another problem by exposing the mutator to reference count values. Many reference counts that it was previously possible for the reference counting analysis to eliminate are no longer safe to do so, which kills performance when using reference types.

So what do we do? Make everything into structs? That's the official answer, but it's a really dumb reason for turning something into a struct, and also not practical in a lot of cases. In the remaining cases you're just stuck with bad performance, too bad.

The reality, though, is that we're solving a problem at run time that could have been solved at compile time.

From here on I'm going to ignore the first example above because it's a complete newbie mistake and not something that should dictate language design. Instead I'll focus on the second example and how we can prevent those kinds of issues without resorting to hacking the memory manager and trampling on reference count elimination.

My answer is to create a new visibility type: visible.

So now we have:

Class Thermostat{
visible var temperature: Temperature{
// getter-setter code
}
}

The idea is that declaring a property as 'visible' marks it as public-read-only. If you try to assign it to a var (or pass it to a function as one), it throws an error. Note that we can still do:

house.thermostat.temperature.fahrenheit = 75

because it exports a setter which localizes the direct access for us, but if it didn't then that would also be an error. On the other hand if we try to do, say:

house.oven.temperature = house.thermostat.temperature

we get an error because we've tried to assign a visible type to a var in another object.

Basically it's like throwing "let" in front of it when getting the property, while still allowing conditional write access as long as we provide a setter for it and access that setter directly through the owning object. This prevents what we really wanted to prevent, which is accidental overwriting of reference types, without also preventing intentional overwriting or killing performance.

(No, this doesn't actually work quite right because we have to call the setter 'fahrenheit' to set the value properly, which either requires changing the semantics of setters or changing the way it's written which could be done in any of several different ways. The basic idea still stands though. Checks should be during compile time not run time wherever possible.)

2

How is this not

private(set) var temperature: Temperature
1 Like
3

temperature is a reference type, meaning if you can get it you can modify it directly whether its owner offers a public setter or not. If you have a reference then you have the object.

4

What do you mean by modify it? Your own example shows that the public API of the reference would still be available. How would visible differ from private(set) exactly? What can you do with the latter that you wouldn't with the former?

5

I think this is the core of your argument and I think you’ve missed the crux of the argument:

Some types make sense as a traditional object. They have identity.

Other types are values. A temperature, for example, is something that does not require identity. It represents a conceptual value, something only appropriate when in a wider context.

There is no push in Swift to make all types structs. There is however a push to identify what is a value, eg a list/collection, a setting, a number, a string, and to move these types to become value types to match the way we expect them to behave.

Traditionally a large amount of these types have been reference types for performance/behavioural reasons. We used references to manage dynamic storage, and we need dynamic storage for these objects, so we used reference types. But do they really work as reference types? Is shared mutable state what we expect behaviourally?

We can use Copy on Write structs to get the storage performance of reference, but to get the conceptual design we expect and help relieve the Shared Mutable State problem.

I feel like you’re missing the point that was being made.

10 Likes
6

Hm, no I just misunderstood how reference types behave with let, apparently I read something incorrect somewhere.

The issue with shared mutable state is that sometimes you want it and sometimes you don't, and you may have one class where you want both behaviors in different circumstances. Defining copy-on-write in the class thus may cause you headaches later on (just the same problem we started with, but in reverse), not to mention forcing reference counts where you otherwise would not need any. It would be nice if we could customize the behavior on a case-by-case basis and have the compiler tell us when we've screwed up rather than using runtime hacks into the reference counting system to do that.

The question is, can we statically determine that an access into an objects properties should not be allowed?

For example, if we want to allow direct, but not indirect write for our thermostat temperature, we could allow

house.thermostat.temperature.fahrenheit = 75

but not

var temp = house.thermostat.temperature
foo(temp)

the difference being that in one case we've expressed a clear intention to change the value as house sees it, but in the other we're taking the value and trying to modify it/pass it around on our own, possibly to code that doesn't know where the value came from and which may consider it to be disposable.

In other cases we may want to forbid write access to any alias of house.thermostat.temperature entirely. Copy-on-write doesn't exactly give us that, nor does it give us any obvious feedback about what we're getting. It's opaque and non-performant, and also context-insensitive.

Other types are values. A temperature, for example, is something that does not require identity. It represents a conceptual value, something only appropriate when in a wider context.

Yes, I realize that temperature is not a good case for a reference type. :stuck_out_tongue: It's only a trivial example to demonstrate the behavior.

7

It sounds like what you want is a way for the owner of a reference to control the mutability of the reference's properties.

8

It sounds like what you want is a way for the owner of a reference to control the mutability of the reference's properties.

Precisely. And also to be able to do that contextually.

To give a more concrete example of the issues regarding copy-on-write, consider this:

for a in animals {
// do stuff with a
}

which actually compiles to something more like

for a in animals {
retain(a)
// do stuff with a
release(a)
}

Now normally the compiler could eliminate those reference counts because they're a no-op, but if a even potentially uses copy-on-write then the compiler has to keep them or risk changing the program's behavior.

Worse still, if a actually does use copy-on-write then we can no longer write our loop this way. It now has to be something more like:

for (i, a) in animals.enumerated() {
animals[i] = a.eat(a.favoriteFood)
}

Not only do we end up with full reference counts which could have been eliminated otherwise, but we have to add a full copy on top of that even though in this situation there's no good reason for doing so. In some other situation we may not want shared mutable state, but here it's ridiculous to not just update in place.

We're stuck picking one extreme or the other when what we actually need is a lot more fine grained. I mean calling "a.copy()" when we need a mutable local copy isn't that difficult or even that common to require, whereas setting the entire class to copy-on-write is about like fixing a leaky sink by smashing it to bits with a sledgehammer and installing a whole new one.

9

CoW is an optimization for value types. The reason you need assign back to animals[i] is not because of CoW, but because value types are always copied on mutation.

Your first expansion is incorrect. If a is an instance of a value type, it's never retained. If it's a reference type, CoW has nothing to do with the reference counting.

10

Strictly speaking this is not correct. An array is not a value type.

In swift, most collection types are actually composed of two components, a struct which stores the collection's metadata, and a heap-allocated reference type which stores the actual data. The struct maintains a pointer to the heap-allocated data and that pointer is reference counted.

so for example if you do something like:

var a = [1, 2, 3, 4, 5]
var b = a // <- the array metadata is copied wholesale to b, including the original pointer
b.append(6) // now b copies the entire array's data into a new array on the heap and adds 6 to it, updating its pointer to the new data structure on the heap.

The way it's actually implemented looks like:

struct Box {
var ref : Ref
init(_ x : T) { ref = Ref(x) }

var value: T {
    get { return ref.val }
    set {
      if (!isUniquelyReferencedNonObjC(&ref)) {
        ref = Ref(newValue)
        return
      }
      ref.val = newValue
    }
}

}

The interesting bit being:

if (!isUniquelyReferencedNonObjC(&ref)) {
ref = Ref(newValue)
return
}

isUniquelyReferencedNonObjC(&ref) takes a raw pointer address as input and returns true if the reference count is equal to 1, and false if it's >1. If the reference count is >1 then it copies the data, otherwise not. It cannot work at all without a reference count.

Likewise, any reference type can use this technique as long as it returns self or a copy of self for every setter function, although wrapping it with a struct makes it easier to control the copying without any cooperation from users of the type.

Also worth noting is that no other language that I'm aware of does things in such a convoluted way. For example in Java arrays are reference types, period. Arrays in java are always referenced using pointers with shared mutable state and an array is never copied unless you explicitly copy it, which is something you do virtually never.

As a result reasoning about java's behavior is easy while reasoning about swift's behavior is a nightmare, and I have no idea what the heck they were thinking when they decided to do things this way. The only time I ever screwed up and accidentally modified a reference type when I shouldn't was when I was new to the language and didn't understand how reference types worked, and honestly swift could probably do just fine without copy-on-write or anti-shared-mutable-state contrivances of any kind.

I mean it might be nice to have, since it allows you to control access to Things That Should Not Be Modified Externally, but the performance implications of doing those sorts of checks at run time are headache inducing to say the least. Why bother hoisting a bounds check out of a loop if you're going to add two reference count operations in its place?

11

Do you have some benchmark for performance gotcha? As far as I’ve used it, I (personally) don’t have much performance issue. I’ve probably grown (too) accustomed to the compiler magic at this point.

12

It is. The fact that it uses a reference to heap-allocated memory in its implementation is irrelevant to the fact that arrays in Swift provide value-type semantics to clients of the type.

15 Likes
13

In Swift, it is a value type. This is defined by how it behaves, not how it's implemented.

How is it a nightmare? If you mutate the array, you get a copy. If you don't mutate it, you don't care if it's a copy or the original.

It sounds like you don't like value types in general, but you haven't clarified why this is.

5 Likes
14

This is kind of a 'read the fine print' deal, since a lot of the competing implementations use all kinds of horrible hacks (and external high-performance libraries, etc) to boost performance, but there are also cases where swift does horribly in spite of using the most horrible hacks possible in the language.

ex: fasta Swift #2 program (Benchmarks Game)

In a few cases the performance is so bad I can't even guess what's going on under the hood. For a lot of cases I suspect that atomic updates on reference counts are killing threading performance, and for others no idea at all.

1 Like
15

That example was last updated for Swift 3, and it uses all sorts of unsafe operations. Have you instrumented this to identify the bottlenecks?

2 Likes
16

The issue is more 'what triggers a reference count vs what doesn't'. If I create an array and then pass it to a function that modifies it, is it going to copy the whole array? If I run it through a loop is it going to reference count every item as it's accessed? Given some of the examples from various WWDCs I'd have to say that the safe answer is usually "yes" (from about 28 minutes forward, if the link here doesn't respect that):

If you scroll down to the " notes, command-line, and program output" bit, it says:

64-bit Ubuntu quad core
Swift version 5.1.1-dev (LLVM b47beb8a70, Swift 7e43e9bcfd)
Target: x86_64-unknown-linux-gnu

MAKE:
/opt/src/swift-5.1-DEVELOPMENT-SNAPSHOT-2019-10-23-a-ubuntu18.04/usr/bin/swiftc fasta.swift-2.swift -Ounchecked -o fasta.swift-2.swift_run

And no, I don't really have the best tools for that on satan's OS. I mean if you want to try giving it a shot they accept implementations. The 44 seconds it takes on binary trees is probably a more interesting problem though.

17

The binary tree test uses a reference type for its data structure. I don't see how it's representative of Array's performance.

How is this a CoW problem, versus an ARC problem? Without CoW, you either get the bad-old-days of NSArray, or you get a pure value type which is copied every single time it is passed or assigned. That is not the way to high-performance code.

It seems like your issues are entirely hypothetical, as you've done nothing to identify the performance bottlenecks in anything you've discussed.

18

Yes to the first and "who cares?" to the second. If the array contains value types, there's nothing to reference count. If the compiler can determine that nothing will release the object for the duration of the access, no call to retain will be emitted. But this is an ARC issue, not a CoW issue.

19

Well, calling it an ARC problem might be fair, but I don't see how ARC can be expected to eliminate refcounts when any class or struct could potentially call isUniquelyReferencedNonObjC() for whatever reason. If it does, eliminating the refcount breaks the program. I suppose you could check for that, but such a check just seems horribly hackish to me, and might require following an entire call chain if a function calls another function and so on.

Which NSArray are we talking about here? Like native objective-C? Obj-C was an abomination in so many ways. :expressionless:

What's so bad about how java/C# handles things like arrays/dicts/etc? I mean sure swift's syntax is more convenient in a lot of ways, but that has literally no bearing on the implementation or the value/reference dichotomy.

Well, coming from java I have plenty of experience with bounds checking overheads (since unlike swift java doesn't hoist them on principle) and they're Bad. Refcounts are also Bad, and can potentially interfere with things like auto-vec, which is a major performance killer.

Looking at the benchmarks on that link I posted you see a lot of cases where there's a 2:1 performance gap between, say, C++ and swift, which accounts exactly for the manual insertion of AVX/SSE code in the C++ version and indicates a failure of auto-vec in swift. Of course it could be auto-vec, but my guess is that it's more likely something legitimately blocking that optimization instead, refcounts being a prime contender since bounds checks are hoisted in any case where autovec could be applied.

20

FWIW, my understanding is the OOP way to solve this is Encapsulation. Your Class is responsible for handling this kind of edge case.

E.g. with your house example

class House {

    private var thermostat: Thermostat = Thermostat(temperature: Temperature(fahrenheit: 65))
    private let maxFahrenheit = 100
    private let minFahrenheit = 40
    var temperature: Temperature {
        set {
            if newValue.fahrenheit < minFahrenheit {
                thermostat.temperature = Temperature(fahrenheit: minFahrenheit)
            }
            else if newValue.fahrenheit > newValue.fahrenheit {
                thermostat.temperature = Temperature(fahrenheit: minFahrenheit)
            }
            else {
                thermostat.temperature = Temperature(fahrenheit: newValue.fahrenheit)
            }
        }
    }

    var temperatureCopy {
        Temperature(fahrenheit: thermostat.temperature.fahrenheit)
    }
}