乐趣区

关于c++:三种stdvector并发安全的设计思路

jiezi

vector 的并发读写问题

家喻户晓，C++ 规范库中的 vector 不保障线程平安。当咱们在并发读写 vector 时，往往会面临两方面的危险：

  1. 内容读取异样：例如两个线程一个在读，一个在写，或者两个线程同时在写，都会导致单个数据外部呈现不统一的状况。
  2. vector 扩容时，内存地位产生扭转导致 Segmentation fault 谬误。因为 vector 在扩容时会将内容全副拷贝到新的内存区域中，原有的内存区域被开释，此时如果有线程仍然在向旧的内存区域读或写就会出问题。

举一个简略的例子：

vector<int> vec;
void add_vector(int range, unsigned int seed){srand(seed);
    for(int i = 0 ; i < range; i++){vec.push_back(rand());
    }
}
int main(){vec.reserve(100);
    thread t1 = thread(add_vector, 1000, 2);
    thread t2 = thread(add_vector, 1000, 1);

    t1.join();
    t2.join();}

两个线程都在向 vec 中增加元素，如果没有任何解决，很容易解体，就是因为第二个起因。而这种并发写的状况，在很多业务场景中都是很可能呈现的，例如：在举荐零碎中，为了进步运算效率每个线程都依照不同的策略生产举荐召回，这些线程产生召回后就会向同一个数组中合并。而后依据这些召回中选出最好的举荐后果。

在文章中提出了三种向 vector 并发增加元素的计划，目标是保障多线程并发条件下能正确向 vector 中。我的项目放在了 safe_vector。

多线程平安的 vector 设计 — 有锁的设计

对于解决并发问题中的最简略的设计就是加锁。在这里咱们应用规范库为咱们提供的 mutex 来对 push_back 临界区加锁。

template<typename T>
class lock_vector{
    std::mutex mlock;
    vector<T> mvec;

public:
    T operator[](unsigned int idx){return mvec[idx];
    }
    lock_vector()=default;
    lock_vector(lock_vector<T>& vec){vec.getVector(mvec);
    };
    lock_vector(lock_vector<T>&& vec){vec.getVector(mvec);
    };

    void push_back(const T& value) noexcept{mlock.lock();
        mvec.push_back(value);
        mlock.unlock();}

    void getVector(vector<T> & res){res = mvec;}
};

多线程平安的 vector 设计 — 无锁设计

除了应用互斥锁，还能够通过无锁的设计来实现线程同步。其中一种常见的思路就是 CAS(compare-and-swap)。C++ 的原子变量（atomic）就提供了 compare_exchange_weak 和 compare_exchange_strong 来实现 CAS 机制。上面的代码是基于 CAS 实现的多线程平安计划。

template<typename T>
class cas_vector{
    std::atomic<bool> flag;
    vector<T> mvec;

    void lock(){
        bool expect = false;
        while(!flag.compare_exchange_weak(expect, true)){expect = false;}
    }

    void unlock(){flag.store(false);
    }

public:
    T operator[](unsigned int idx){return mvec[idx];
    }
    cas_vector(){flag.store(false);
    };
    cas_vector(const cas_vector& vec){
        mvec = vec;
        flag.store(false);
    };
    cas_vector(cas_vector&& vec){
        mvec = vec;
        flag.store(false);
    };

    void replace(const int idx, const T& value) noexcept{lock();
        mvec[idx] = value;
        unlock();}

    void push_back(const T& value) noexcept{lock();
        mvec.push_back(value);
        unlock();}
};

多线程平安的 vector 设计 — 借助 thread_local 变量

thread_local 变量简介

thread_local 是 C ++11 之后才引入的关键字。thread_local 变量与其所在线程同步创立和销毁，并且只能被创立它的线程所拜访，也就是说 thread_local 变量是线程平安的。每个线程在本身 TIB(Thread Information Block) 中存储 thread_local 变量的正本。

基于 thread_local 变量实现的计划

该计划的代码实现如下，vector_thl 就是多线程增加元素平安的类型。在我的实现中，每个类别离存在两个 vector，一个是 thread_local 类型，每次调用 push_back 时，都会向其中增加元素。因为该变量在每个线程中都存在一个正本，因而不须要进行线程同步，但同时，为了获取最终后果，必须将这些扩散在各个线程的正本合并到一起。因而在 vector_thl 减少了 merge 接口来合并这些线程部分的 vector。

template<typename T>
class vector_thl{
    vector<T> mvec;
    mutex lock;
public:

    thread_local static vector<T> vec;

    vector_thl()=default;
    vector_thl(const vector_thl& vec){
        mvec = vec;
        vec = vec;
    };
    vector_thl(vector_thl&& vec){
        mvec = vec;
        vec = vec;
    };


    void push_back(const T& value) noexcept{vec.push_back(value);
    }

    void merge(){mvec.insert(mvec.end(), vec.begin(), vec.end());
    }

    void getVector(vector<T>& res){res = mvec;}
};

template<typename T>
thread_local vector<T> vector_thl<T>::vec(0);

性能比拟

对三种实现计划进行基准测试，失去以下后果：

Run on (12 X 2994.27 MHz CPU s)
CPU Caches:
  L1 Data 32 KiB (x6)
  L1 Instruction 32 KiB (x6)
  L2 Unified 512 KiB (x6)
  L3 Unified 4096 KiB (x1)
Load Average: 0.00, 0.09, 0.22
--------------------------------------------------------
Benchmark              Time             CPU   Iterations
--------------------------------------------------------
BM_VEC_LOC/10    4574464 ns      1072230 ns          639
BM_VEC_LOC/2     6627843 ns       176688 ns         1000
BM_VEC_CAS/10    9280705 ns      1027921 ns          683
BM_VEC_CAS/2     7537580 ns       180541 ns         1000
BM_VEC_THL/10    1108654 ns       993997 ns          687
BM_VEC_THL/2      693148 ns       123333 ns         5723

可见借助 thread_local 实现的计划是运行效率最高的，大略是互斥计划的 4 倍，是无锁计划的 8 倍。同时也是 CPU 利用效率最高的计划。

总结

在文章中咱们实现了三种多线程并发增加元素平安的 vector。其中利用 thread_local 实现的计划效率最高，次要起因是 thread_local 变量在每个线程中都有一个正本，不会并发写，防止了锁竞争。

然而这种计划并非完满，因为每个线程的 thread_local 变量都是不残缺的，因而在增加元素阶段并不能正确的读取元素，只有在每个增加元素的线程都讲元素合并到之后能力进行读。

退出移动版