Open xunboo opened 11 months ago
我的理解是,从理论上讲vector可以直接把首尾迭代器相减算出元素数量,然后在实际开始计算之前就可以指定每个线程计算哪一部分元素,这样就只有最后求总和的时候需要把各个线程的结果加起来,其他时候各个线程之间完全不需要通信和同步,所以并行比串行快是有可能的。但如果是非随机访问迭代器,比如链表的迭代器,这时候无法事先知道总共有多少元素,就只能一个个遍历所有元素然后动态分给不同线程来计算,这时候不同线程之间就需要用原子操作来进行同步以确保不同线程不会重复计算同一个元素,如果每前进一个元素都要进行一次原子操作的话,那么原子操作的开销远大于判定一个数是不是 2 的倍数的开销,所以这种情况下不管有多少个元素,并行肯定比串行慢。
我的经验是,在Linux,gcc 11,使用了TBB作为线程库的时候,当每个元素要处理的任务量太小的时候,TBB创建线程的开销会远大于计算的开销。MSVC这边可能有别的优化?
似乎这个理论有问题,实际测试:
std::count_if (seq, long) sum: 100,000,007 time: 51.5 ms std::count_if (par, long) sum: 100,000,007 time: 13.3 ms