2

I have a rather large class that contains a number of related member variables. These member variables can be grouped into related sections. We've noticed that the pattern of use of the class is to make a copy of an existing instance, change only a few of the member variables, and then do work with the resulting instance. There are 2 problems we've hit.

  1. Instances of the class are large and often on the stack, so it would be nice to reduce its size
  2. Copying all the member variables is somewhat slow.

So one idea we had was to group related member variables into their own objects. This is just a good idea for making the code easier to understand. But if we did this and had each of these objects be merely a shared pointer to an existing instance, it would reduce the size of the main class as several member variables would be replaced with a single shared pointer. It would also speed up copying, as the copy would just be creating a new shared pointer pointing to the existing instance.

The problem is that now whenever we have to write to anything in one of these shared objects, we need to make a copy of it on first write. (And we need to check on every write whether it needs to be copied or not.) We don't write very often, so I don't think it will be a performance hit. But implementing this seems problematic.

Is there a way to make a class be copy-on-write when one of its member variables needs to be changed? The class itself is written in C++, though I could also use C or Objective-C to implement this. I don't want to have to manually write the check of the shared pointer's reference count in every setter, for example. Is there any way to avoid that?

  • If your class needs copy-on-write semantics, then you need to implement that yourself. There are no facilities in C, C++ or Objective-C to do automatic copy-on-write for user-defined classes. – Bart van Ingen Schenau Nov 2 '17 at 7:15
  • I didn't think there was any built-in copy-on-write functionality, but was curious if there were either existing implementations like the one @Kane mentioned, or if there were ways to implement it that I hadn't thought of. – user1118321 Nov 3 '17 at 2:29
5

C++ does not have built-in copy on write semantics. You can implement such semantics with a smart pointer class, or can choose a design-level approach that makes copies unnecessary, e.g. by using the decorator pattern. However, you may find that these optimizations are not worth their effort.

Copy on Write Smart Pointer

The idea is that your members are stored in a smart pointer that manages their ownership. When the smart pointer is copied, it will not copy the managed object. However, once write-access is required, a copy is made.

This is not entirely trivial to get right, especially if there may be other pointers into the managed object. Some CoW implementations trigger only when a copy wants to write to the object, other implementations also perform a copy when the original owner writes to the (shared) object.

You will therefore have to write your own smart pointer that implements your desired semantics. Likely, this can be implemented with moderate effort on top of std::shared_ptr.

A significant drawback of CoW is that these lazy copies can make your code much harder to debug. Copying a C++ object may have observable side effects, but may now happen at unexpected times. Also, every write access must first check the state of the smart pointer and must possibly dereference multiple pointers.

Decorator Pattern

The decorator pattern can be used to overlay parts of an object with a different implementation. For example, you might want to overlay parts of a struct { A a; B b; C c; }. First, we need to define an interface so that we can combine our Decorators:

class Data {
public:
  virtual A& get_a() = 0;
  virtual B& get_b() = 0;
  virtual C& get_c() = 0;
};

Now we can implement this interface with a base storage class:

class BaseStorage : public Data {
  A a; B b; C c;
public:
  BaseStorage(A const& a, B const& b, C const& c) : a(a), b(b), c(c) {}
  A& get_a() override { return a; }
  B& get_b() override { return b; }
  C& get_c() override { return c; }
};

If we want to overlay the value of A, we can define a class that delegates all calls to a base object, except for requests of the A data:

class OverlayA : public Data {
  Data& base;
  A a;
public:
  OverlayA(Data& base, A&& a) : base(base), a(std::move(a)) {}
  A& get_a() override { return a; }
  B& get_b() override { return base.get_b(); }
  C& get_c() override { return base.get_c(); }
};

Instead of performing a copy of some Data, we can now overlay the part of it we are going to change:

Data& orig = ...;
// call a function with a copied A
will_change_a(OverlayA(orig, A(orig.get_a())));

Unfortunately, these decorators make it really really difficult to write const-correct code – you may want the Data& base to be a const reference in order to prevent writes to the base storage, but the interface may also describe overlaid data where writes are necessary. This could possibly be expressed through templates.

If behaviour of any Data interface implementation changes the private fields directly rather than going through the virtual methods, that may not write to the overlaid data. Therefore, the Data interface should not contain extra behaviour. You can implement such behaviour in a separate class that wraps a Data&.

This technique requires you to know in advance which parts of the object must be overlaid with copied data. As such, it is potentially error-prone.

The decorator pattern constructs a linked list of overlays. If the list grows many levels deep, this pointer chasing may hurt performance.

Copies are good

In many cases, creating a copy is preferable to cleverness like CoW. In particular, if the objects in question are not very large and are trivially copyable, then doing a copy each time may turn out to be cheaper than the alternatives. Because of caching, chasing pointers tends to be expensive compared to operations on contiguous objects. Both CoW and Decorators have continuous per-read overhead, whereas copies only have a predictable per-copy overhead.

If your profiling determines that the copies are a performance problem, then it may be sensible to try out one of these approaches or a combination of them (e.g. performing a copy but using CoW for expensive to copy members like vectors might be sensible). Where possible, avoid ownership of expensive to copy data in your object.

  • 2
    Copies are not good. There comes a point when it's just easier to create a copy, and it's fine for guaranteeing immutability. However a far better solution is to guarantee immutability because it is immutable and not because it's just a copy. Though, your decorator pattern has some merit. – Neil Nov 2 '17 at 10:59
  • Thanks! This is quite helpful. I do need to do some more analysis to determine if CoW would be a win, and this gives me a few things to think about. – user1118321 Nov 3 '17 at 2:26
  • @Neil Copies are not good when the object is immutable. I agree with that. But consider the alternative. How do you find the one instance that allows you to avoid making a copy of the object? You have to use interning, which has its own set of problems. I should mention this problem only occurs when creating new values, not when passing an immutable object by reference. – Frank Hileman Nov 7 '17 at 22:27
  • @FrankHileman To that I would argue that the difficulty of sticking with an immutable instance in your program means the program is structured badly. Copying instances is a quick fix when the real solution means refactoring the program. Again, I've been there, and I understand everything completely. But don't put lipstick on a pig. Copying instances is a sign that something else is wrong at the conceptual level in the program. – Neil Nov 8 '17 at 8:29
3

You could check how this is done in Qt's QSharedDataPointer.

The idea is to have a smart pointer which implements operator->() and operator->() const. The former one will do a copy before returning the data, whereas the latter one will not.

  • A bit implicit for my taste (I'd prefer an explicit method to return a unique writable reference), but conceptually a CoW smartpointer that creates a copy when you ask for a writable reference is the right approach. – CodesInChaos Nov 2 '17 at 10:06
  • Thank you, this looks interesting. I agree with @CodesInChaos that the implicitness of it makes me a little hesitant to do it the same way, but seeing an implementation will be useful nonetheless. – user1118321 Nov 3 '17 at 2:27
1

I've built a framework around immutability through something like partial COW which I really like (found it really eliminated a lot of sources of former state management errors I made, especially with multiple threads wanting to touch the same data), but the basic answer to your question is "no", C++ doesn't provide the language features necessary to automate and simplify the process of creating an immutable type where some of its fields can be changed without deep copying the entire type. You have to roll up your sleeves and devise your own solution.

To be able to provide an efficient immutable type with only parts of it being deep copied on write and with thread safety, you can no longer work with it with simple scalar logic. Let's take an array as a simple example:

enter image description here

Let's imagine the actual array is a lot bigger (just to avoid making a massive diagram) or that each individual element in the array is huge and expensive to copy. In that case, we need to split up the array into smaller contiguous blocks to be able to partially transform the array and partially copy it without copying the entire thing:

enter image description here

Now we can modify just the elements in range [0, 4), like so:

enter image description here

However, what does this mean for the client code? It generally means we can't manipulate the array with simple scalar logic anymore, otherwise there would be a thread lock and a deep copy of elements 0 to 3 for every single individual manipulation of a single array element in the range, [0, 4). As a result we have to design an interface where clients start to request changes in bulky transactions, like so as a overly simplistic example:

immutable_array<int> transform(immutable_array<int> data)
{
    // @return A new array with elements in the range
    // [0, 4) replaced with new values.
    const int new_values[] = {666, 666, 666, 69};
    return data.modified(0, 4, new_values);
}

So it becomes a bit cumbersome working with such immutable types, at least in C++, though a worthwhile trade-off if the benefits are good enough as far as safety (I especially find immutability of this sort with partial COW useful for multithreading to achieve parallel code that is reasonably efficient with easy guarantees and reasoning about safety I can't get with mutable types that want to be touched by many threads at once).

Similar type of thing with this example:

class Cyborg
{
public:
   ...
private:
   shared_ptr<Head> head;
   shared_ptr<Arms> torso;
   shared_ptr<Arms> arms;
   shared_ptr<Arms> legs;
};

In this case we can't efficiently provide functions, at least in C++, to just modify a part of the cyborg's torso. We have to create a new torso, manipulate that, and commit a replacement of the cyborg's torso as an individual transaction. Again we have to transform things in a chunkier, bulkier way.

That said, if immutability of this sort is beneficial enough for you (I found it definitely to be the case for complex structures used in multithreaded context and for undo systems), then the elbow grease necessary to do this both in terms of implementation and client code to use the interface can really be worthwhile.

I don't want to have to manually write the check of the shared pointer's reference count in every setter, for example. Is there any way to avoid that?

If you apply things the way I did above, then every single function which transforms your immutable type and returns a new partial copy will not need to perform this check. Instead it's done like so for the cyborg example above:

void Cyborg::replace_arm(const Arm& new_arm)
{
    // Perform thread lock as needed.
    arm = make_shared(new_arm);
}

If you want to guarantee that cyborgs are immutable, then you do this instead and all member functions will be read-only:

Cyborg Cyborg::replace_arm(const Arm& new_arm) const
{
    // Perform thread lock as needed.
    Cyborg new_cyborg = *this;
    new_cyborg.arm = make_shared(new_arm);
    return new_cyborg;
}

It's a different kind of COW approach from old versions of std::string which have to flag when the string as a whole is copied, but requires an interface which modifies reasonably large chunks of data in bulk as an atomic transaction for thread safety and efficiency. Your interface can't consist of simple setters to modify teeny pieces of data like a small scalar element (ex: a single character of a string or a single nut and bolt on a cyborg's arm). If you're going to set/replace something, it should be something big because every single member function which modifies state, if you have any, will be creating a new modified copy of something big as a bulky transaction.

I'm not sure if this is even worth calling copy-on-write anymore so much as implementations of immutable types, but it's a solution to your problem of having to copy around every piece of data of a massive object repeatedly when only parts of it need to be made unique. Of course you can design intermediary classes, like Arm, which allow you to modify small parts of it prior to committing an arm replacement as an atomic transaction to a cyborg or to create a new immutable version of it with a different arm.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.