C++之写时复制(CopyOnWrite)原理详解

1.简介

CopyOnWrite (COW) 是一种编程思想用于优化内存使用和提高性能。COW 的基本思想是如果多个对象或变量共享相同的数据那么它们最初可以共享同一份数据而不是为每个对象创建独立的数据副本。如果任何一个对象想要修改数据就会创建数据的副本然后在副本上进行修改而原始数据保持不变。

这种技术在处理不可变数据结构或很少修改数据的情况下特别有用。通过最初共享数据COW 避免了不必要的复制以减少内存占用和提高性能。它还减少了对共享数据的修改对其他对象的影响因为它们继续引用原始数据直到进行修改。例如在 Linux 系统中调用 fork 系统调用创建子进程时并不会把父进程所有占用的内存页复制一份而是与父进程共用相同的内存页而当子进程或者父进程对内存页进行修改时才会进行复制这样在两者都不对内存修改的场景下会有很好的性能表现。

Qt 的 QString 正是采用了 COW 思想它是如何工作的呢简单来说就是平时查询的时候都不需要加锁随便访问只有在更新的时候才会从原来的数据复制一个副本出来然后修改这个副本最后把原数据替换成当前的副本。修改操作的同时读操作不会被阻塞而是继续读取旧的数据。

2.实现原理

写时复制的原理就是浅拷贝加引用计数。 当只是进行读操作时就进行浅拷贝如果需要进行写操作的时候再进行深拷贝再加一个引用计数多个指针指向同一块空间记录同一块空间的对象个数。

1) QString之写时复制

当两个QString发生复制或者赋值时不会复制字符串内容而是增加一个引用计数然后字符串指针进行浅拷贝其执行效率为O(1)。只有当修改其中一个字符串内容时才执行真正的复制。

2) 引用计数

堆区为了好获取将将引用计数与数据放在一起并且最好在数据前面这样当数据变化的时候不会移动引用计数的位置

3.QString的实现分析

3.1.内部结构

QString 内部的数据结构是 QTypedArrayData

template <class T>
struct QTypedArrayData
    : QArrayData
{
    ...
};

typedef QTypedArrayData<ushort> QStringData;

class Q_CORE_EXPORT QString
{
public:
    typedef QStringData Data;

    ...

    Data*  d;  //真正存储QString数据的对象
};

而 QTypedArrayData 继承自 QArrayData。

struct Q_CORE_EXPORT QArrayData
{
    QtPrivate::RefCount ref;  //引用计数
    int size;
    uint alloc : 31;
    uint capacityReserved : 1;

    qptrdiff offset; // in bytes from beginning of header

    void *data()
    {
        Q_ASSERT(size == 0
                || offset < 0 || size_t(offset) >= sizeof(QArrayData));
        return reinterpret_cast<char *>(this) + offset;
    }

    const void *data() const
    {
        Q_ASSERT(size == 0
                || offset < 0 || size_t(offset) >= sizeof(QArrayData));
        return reinterpret_cast<const char *>(this) + offset;
    }
    
    ...
};

QArrayData 有个 QtPrivate::RefCount 类型的成员变量 ref该成员变量记录着该内存块的引用。也就是说QString 采用了 Copy On Write 的技术优化了存放字符串的内存块。

3.2.写入时复制

QtPrivate::RefCount的作用就是保存计数从它的源码可以看出

class RefCount
{
public:
    inline bool ref() Q_DECL_NOTHROW {  //增加引用计数
        int count = atomic.load();
#if !defined(QT_NO_UNSHARABLE_CONTAINERS)
        if (count == 0) // !isSharable
            return false;
#endif
        if (count != -1) // !isStatic
            atomic.ref();
        return true;
    }

    inline bool deref() Q_DECL_NOTHROW { //减少引用计数
        int count = atomic.load();
#if !defined(QT_NO_UNSHARABLE_CONTAINERS)
        if (count == 0) // !isSharable
            return false;
#endif
        if (count == -1) // isStatic
            return true;
        return atomic.deref();
    }

    ...

    QBasicAtomicInt atomic;  //原子变量
};

在

QString::QString(const QString &other)复制构造函数

中

QString &QString::operator=(const QString &other) Q_DECL_NOTHROW
{
    other.d->ref.ref();    //other增加引用计数 [1]
    if (!d->ref.deref())    //自己减少引用计数 [2]
        Data::deallocate(d); //如果自己计数为0则释放内存 [3]
    d = other.d;            //直接指针赋值 [4]
    return *this;
}

通过4步完成了拷贝构造函数相比深拷贝

class String{
public:
   String(const String &rhs):m_pstr(new char[strlen(rhs) + 1]()){
   }
private:
   char* m_pstr;
};

减少了内存申请和拷贝的过程从而大大的提高了运行效率。

在追加内容函数

QString::append(const QString &str)

的实现也看出的确是采用了 COW 技术

QString &QString::append(const QString &str)
{
    if (str.d != Data::sharedNull()) {
        if (d == Data::sharedNull()) {
            operator=(str);
        } else {
            if (d->ref.isShared() || uint(d->size + str.d->size) + 1u > d->alloc)
                reallocData(uint(d->size + str.d->size) + 1u, true); //
            memcpy(d->data() + d->size, str.d->data(), str.d->size * sizeof(QChar));
            d->size += str.d->size;
            d->data()[d->size] = '';
        }
    }
    return *this;
}

void QString::reallocData(uint alloc, bool grow)
{
    auto allocOptions = d->detachFlags();
    if (grow)
        allocOptions |= QArrayData::Grow;

    if (d->ref.isShared() || IS_RAW_DATA(d)) {
        Data *x = Data::allocate(alloc, allocOptions);
        Q_CHECK_PTR(x);
        x->size = qMin(int(alloc) - 1, d->size);
        ::memcpy(x->data(), d->data(), x->size * sizeof(QChar));
        x->data()[x->size] = 0;
        if (!d->ref.deref())
            Data::deallocate(d);
        d = x;
    } else {
        Data *p = Data::reallocateUnaligned(d, alloc, allocOptions);
        Q_CHECK_PTR(p);
        d = p;
    }
}

从上述代码可以看出reallocData函数在重新写入数据时会重新分配内存在新的内存上增加计数并减少原有内存技术这正是COW的思想所在。

4.QImage中的写时拷贝分析

对于 QImage 这样通常占用内存较大的数据类型写时拷贝还是很有必要的下图是 QImage 写时拷贝的状态过程

图中可以看出

• 当第一次创建 imgA 的时候会创建一个 QImage 壳和一份真正的 QImageData。在 Qt 中这个壳就是 QImage 类本身真正的数据是 QImageData 类型。QImage 中通过 d_ptr 指向 imgdata。
• 当 imgB 需要拷贝 imgA 时并不会对 imagedata 进行拷贝只会创建 imgB 对应的 wrapperimgB然后将 d_ptr 指向 imgA 对应的 imagedata并将计数 ref 加 1。此时两个 img 指向了同一份 imgdata。
• 当 imgB 进行图像数据写操作时会首先发生 detach 操作将 imgdata 拷贝一份然后将 wrapperimgB 中的 d_ptr 指向新的 imgdata并对 ref 进行关联操作。这时两个 img 就被解耦开来可以进行写操作。

关键函数

//QImage 的构造函数第一次构造 QImage 时被调用内部通过 ``QImageData::create()` 接口创建一份 //imgdata。

QImage::QImage(uchar* data, int width, int height, Format format, QImageCleanupFunction cleanupFunction, void *cleanupInfo)
    : QPaintDevice()
{
    d = QImageData::create(data, width, height, 0, format, false, cleanupFunction, cleanupInfo);
}

• QImage 的拷贝构造和赋值构造函数首先判断拷贝的 QImage 是否处于绘制状态如果是在绘制流程中则认为当前 QImage 数据是会变化的所以直接深拷贝一份 imgdata。如果不是则将新的 QImage 中的 d_ptr 指向被拷贝图像中的 imgdata两者共用一份 imgdata。
• 另外赋值构造中还需要处理下等号左边的 QImage 的引用计数需要将之前指向的 imgdata 中的引用计数减一如果此时没有其它引用了则将之前的 imgdata 内存释放。

QImage::QImage(const QImage ℑ)
    : QPaintDevice()
{
    if (image.paintingActive() || isLocked(image.d)) {
        d = 0;
        image.copy().swap(*this);
    } else {
        d = image.d;
        if (d)
            d->ref.ref();
    }
}

QImage &QImage::operator=(const QImage ℑ)
{
    if (image.paintingActive() || isLocked(image.d)) {
        operator=(image.copy());
    } else {
        if (image.d)
            image.d->ref.ref();
        if (d && !d->ref.deref())
            delete d;
        d = image.d;
    }
    return *this;
}

• 析构函数中将引用计数减一如果没有其它引用则释放 imgdata 内存。

QImage::~QImage()
{
    if (d && !d->ref.deref())
        delete d;
}

• detach 函数在其中一个引用发生写数据操作时会调用核心流程是拷贝一份 imgdata让当前需要 detach 的 QImage 中 d_ptr 指向该 imgdata。这里的 executeImageHooks 和 d->ro_data 的逻辑还不太清楚。

void QImage::detach()
{
    if (d) {
        if (d->is_cached && d->ref.load() == 1)
            QImagePixmapCleanupHooks::executeImageHooks(cacheKey());

        if (d->ref.load() != 1 || d->ro_data)
            *this = copy();

        if (d)
            ++d->detach_no;
    }
}

• setDevicePixelRatio会发生数据写操作此时会先进行 detach 操作生成一份独立的 imgdata然后在对数据进行修改这样就不会影响原有的 imgdata。

void QImage::setDevicePixelRatio(qreal scaleFactor)
{
    if (!d)
        return;

    if (scaleFactor == d->devicePixelRatio)
        return;

    detach();
    if (d)
        d->devicePixelRatio = scaleFactor;
}

当需要设计这种大内存数据类型的时候也可以仿照 QImage 实现一套写时拷贝机制帮助我们提高拷贝效率。

5.示例分析

在C++中虽然标准库并没有直接提供写入时复制的实现但你可以通过自定义数据结构来实现这种策略。下面是一个简单的示例展示了如何在C++中实现一个写入时复制的数组

#include <iostream>  
#include <vector>  
#include <memory>  
  
template <typename T>  
class CopyOnWriteArray {  
private:  
    std::shared_ptr<std::vector<T>> data;  
  
public:  
    CopyOnWriteArray() : data(std::make_shared<std::vector<T>>()) {}  
  
    // 获取数组的大小  
    size_t size() const {  
        return data->size();  
    }  
  
    // 获取指定位置的元素只读  
    const T& operator[](size_t index) const {  
        return (*data)[index];  
    }  
  
    // 修改指定位置的元素写入时复制  
    void set(size_t index, const T& value) {  
        if (data.unique()) {  
            // 如果当前是唯一持有者则无需复制  
        } else {  
            // 否则创建一个新的数据副本  
            data = std::make_shared<std::vector<T>>(*data);  
        }  
        (*data)[index] = value;  
    }  
  
    // 添加一个新元素到数组的末尾写入时复制  
    void push_back(const T& value) {  
        if (data.unique()) {  
            // 如果当前是唯一持有者则直接在原数组上添加元素  
            data->push_back(value);  
        } else {  
            // 否则创建一个新的数据副本并在副本上添加元素  
            data = std::make_shared<std::vector<T>>(*data);  
            data->push_back(value);  
        }  
    }  
};  
  
int main() {  
    CopyOnWriteArray<int> array;  
    array.push_back(1);  
    array.push_back(2);  
    array.push_back(3);  
    std::cout << "Size: " << array.size() << std::endl;  
    std::cout << "Element at index 1: " << array[1] << std::endl;  
    array.set(1, 100); // 写入时复制发生在这里  
    std::cout << "Element at index 1 after modification: " << array[1] << std::endl;  
    return 0;  
}

这个示例中CopyOnWriteArray 类使用 std::shared_ptr 来管理底层数据的生命周期。当多个 CopyOnWriteArray 对象共享同一个 std::vector 时如果其中一个对象尝试修改数据就会触发写入时复制。这是因为修改操作会检查 std::shared_ptr 的引用计数如果计数大于1就创建一个新的 std::vector 副本并在副本上进行修改。这样其他仍然引用原始 std::vector 的对象不会受到影响。

6.使用场景

写入时复制CopyOnWrite的使用场景主要集中在需要高并发读操作而写操作相对较少的场景。这种策略特别适用于那些读操作远多于写操作且写操作不会频繁发生的情况。下面是一些具体的使用场景

• 并发容器当需要实现线程安全的容器并且读操作远多于写操作时可以使用基于写入时复制的并发容器。这种容器可以确保在读取数据时不需要加锁从而提供高效的并发读取性能。只有在写入数据时才会复制底层数据并进行修改从而保持线程安全。
• 共享不可变数据在某些情况下多个线程或进程需要共享一些不可变的数据。当这些数据需要更新时可以使用写入时复制策略来创建一个新的数据副本并在副本上进行修改。这样其他线程或进程仍然可以安全地访问原始数据而不会受到修改的影响。
• 事件处理系统在事件驱动的系统中事件处理函数通常需要读取事件数据并进行处理。如果多个事件处理函数可以同时处理不同的事件并且事件数据在事件处理过程中不会被修改那么可以使用写入时复制的容器来存储事件数据。这样每个事件处理函数都可以安全地读取事件数据而不需要担心数据竞争或一致性问题。
• 日志记录在日志记录系统中通常需要记录大量的日志信息并且这些日志信息主要是被读取和分析的而不是被修改的。使用写入时复制的容器来存储日志信息可以提高并发写入的性能因为多个线程可以同时写入不同的日志条目而不需要进行复杂的同步操作。

需要注意的是写入时复制策略在写操作频繁或数据量非常大的情况下可能会导致较高的内存开销和性能下降。因此在选择使用写入时复制时需要仔细评估应用场景的读写比例、数据量和性能要求以确保其适用性。此外还需要注意在实现写入时复制策略时正确管理内存和引用计数以避免内存泄漏和其他问题。

7.总结

使用CopyOnWrite思想有以下几个好处

• 内存效率CopyOnWrite允许多个对象共享相同的数据避免了不必要的数据复制。这对于大型数据结构或多个对象需要引用相同数据的情况下可以节省大量的内存。
•  性能优化对于很少修改数据的情况下CopyOnWrite可以显著提高性能。由于读操作不需要加锁多个线程可以同时访问共享数据提高并发访问的效率。对于一些读多写少的数据写入时复制的做法就很不错例如配置、黑名单、物流地址等变化非常少的数据这是一种无锁的实现。可以帮我们实现程序更高的并发。
• 减少数据拷贝CopyOnWrite只在写操作时进行数据拷贝而在读操作时共享数据。这减少了不必要的数据拷贝开销提高了性能。

尽管CopyOnWrite有一些优点但也存在一些缺点或不足之处

• 写操作开销当有写操作发生时CopyOnWrite需要进行数据的复制这会引入一定的开销。复制大型数据结构可能会消耗较多的时间和内存并且频繁的写操作可能会影响性能
• 不适合频繁修改的场景由于CopyOnWrite需要进行数据复制所以频繁的写操作会导致性能下降。对于需要频繁修改数据的场景可能有更适合的数据结构或算法选择

总的来说CopyOnWrite适用于多个读操作、少量写操作的场景可以提供高效的内存使用和线程安全的并发访问。但需要权衡其开销和适用性根据具体情况选择使用。