0CCh Blog

Qt的隐式共享和写时拷贝

不得不说Qt为了提高代码的运行效率做了很多伟大的工作,引入隐式共享和写时拷贝技术就是其中之一。该技术十分值得我们学习,一方面是因为它也可以运用到我们的代码中提高代码的运行效率,另一方面我们在理解其原理之后才能够更加高效的使用Qt。

Qt中的隐式共享是指类中存在一个共享数据块指针,改数据块由数据和引用技术组成。

  • 当类型对象被创建时,共享数据块也被创建,并且设置引用技术为1。
  • 当类型对象发生拷贝时,共享数据块共享其指针,并且递增引用计数(+1)。
  • 当类型对象销毁时,共享数据块引用技术递减(-1),当引用计数归零时销毁数据块。
  • 当类型对象调用方法有可能被修改时,采用写时拷贝机制,创建真正对象副本。

使用隐式共享和写时拷贝的好处非常明显,在只读的情况下,拷贝对象的内存和CPU计算成本非常低。只有在真正修改对象的时候,才会发生对象拷贝。除了Qt中的普通类型以外,Qt的容器类型也大量采用了这种技术,这也是Qt容器和STL容器的一个显著的区别。

来看一个简单的例子:

// class QPenPrivate *d

QPen::QPen(const QPen &p) noexcept
{
d = p.d;
if (d)
d->ref.ref();
}

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

void QPen::detach()
{
if (d->ref.loadRelaxed() == 1)
return;

QPenData *x = new QPenData(*static_cast<QPenData *>(d));
if (!d->ref.deref())
delete d;
x->ref.storeRelaxed(1);
d = x;
}

void QPen::setStyle(Qt::PenStyle s)
{
if (d->style == s)
return;
detach();
d->style = s;
QPenData *dd = static_cast<QPenData *>(d);
dd->dashPattern.clear();
dd->dashOffset = 0;
}

可以看到Pen的拷贝构造函数只是将共享数据块指针从p赋值到当前对象,然后增加其引用计数。当对象析构时,首先减少引用计数,然后判断引用计数是否归零,如果条件成立则释放对象。当调用setStyle函数修改对象的时候,函数调用了一个detach函数,这个detach函数检查当前的引用计数,若引用计数为1,证明没有共享数据块,可以直接修改数据。反之引用计数不为1,则证明存在共享改数据块的类,无法直接修改数据,需要拷贝一份新的数据。

现在看来,Qt似乎已经为我们考虑的十分周到了,不调用修改对象的函数是不会发生真正的拷贝的。那么需要我们做什么呢?答案是,Qt的使用者应该尽可能的避免误操作导致的数据拷贝。前面提到过,Qt认为可能发生写对象的操作都会真实的拷贝对象,其中要给典型的情况是:

QVector<int> test1{ 1,2,3 };
QVector<int> test2 = test1;
int* p = test2.data();

这里看起来并没有发生对象的写操作,但是数据拷贝还是发生了,因为Qt认为这是一个可能发生写数据的操作,所以在调用data()的时候就调用了detach()函数。

inline T *data() { detach(); return d->begin(); }

如果确定不会修改对象的数据应该明确告知编译器:

QVector<int> test1{ 1,2,3 };
const QVector<int> test2 = test1;
QVector<int> test3 = test1;
const int* p = test2.data();
const int* q = test3.constData();

其中

inline const T *data() const { return d->begin(); }
inline const T *constData() const { return d->begin(); }

它们都不会调用detach函数拷贝对象。还是C++编程老生常谈那句话:在确定不修改对象的时候总是使用const来声明它,以便编译器对其做优化处理。

有时候我们并不是完全弄清楚编程环境中具体发生了什么,比如你可能不知道Qt的隐式共享和写时拷贝,但是保持良好的编程习惯,比如对于不修改的对象声明为const,有时候可以在不经意间优化了编写的代码,何乐而不为呢。

值得注意的是,我们应该尽量避免直接引用并通过引用修改Qt容器中的对象。千万不要这么做,因为可能会得到你不想看到的结果,例如:

QVector<int> test1{ 1,2,3 };
QVector<int> test2 = test1;
int& v = test1[1];
v = 20;

这份代码不会出现问题,因为当表达式test2 = test1运行时,共享数据的引用计数递增为2,当调用operator []的时候由于test1不是const,所以会为test1拷贝一份副本。最后结果是:

test1[1] == 20;
test2[1] == 2;

这样看来没有问题,但不幸的是我们有时候也会这样写:

QVector<int> test1{ 1,2,3 };
int& v = test1[1];
QVector<int> test2 = test1;
v = 20;

上面这份代码会带来一个意想不到的结果:

test1[1] == 20;
test2[1] == 20;

因为在运行int& v = test1[1];这句代码的时候,数据块的引用计数为1,detach函数认为数据块没有共享,所以无需拷贝数据。当执行test2 = test1的时候,Qt并不知道之前发生了什么,所以仅仅增加了引用计数,所以修改v同时修改了test1test2。这不是我们想看到的结果,所以我们应该怎么做?注意代码执行的顺序么?得了吧,即使能保证自己会注意到代码的执行顺序问题,也不能保证其他人修改你的代码时会怎么做,最好的做法是告诉大家,我们的项目有一条规则——禁止直接引用并通过引用修改Qt容器中的对象!或者干脆,使用STL的容器吧。

最后,如果觉得Qt的隐式共享和写时拷贝技术很不错,碰巧你的项目的编写环境中也有Qt,那么使用QSharedDataQSharedDataPointer会让你的工作轻松很多。

使用Q_DECLARE_TYPEINFO让Qt优化容器算法

如果需要使用Qt容器,那么使用Q_DECLARE_TYPEINFO让Qt了解容器内元素的类型特征是一个不错的做法。因为Qt可以通过识别Q_DECLARE_TYPEINFO给定的类型特征,在容器中采用不同的算法和内存模型以达到计算速度和内存使用上的优化。

Q_DECLARE_TYPEINFO(Type, Flags)的使用非常简单,在定义了数据结构之后,通过指定类型名和枚举标识来指定这个类型特征,例如:

struct Point2D
{
int x;
int y;
};

Q_DECLARE_TYPEINFO(Point2D, Q_PRIMITIVE_TYPE);
  • Q_PRIMITIVE_TYPE指定Type是没有构造函数或析构函数的POD(plain old data) 类型,并且memcpy()可以这种类型创建有效的独立副本的对象。
  • Q_MOVABLE_TYPE指定Type具有构造函数或析构函数,但可以使用memcpy()在内存中移动。注意:尽管有叫做move,但是这个和移动构造函数或移动语义无关。
  • Q_COMPLEX_TYPE(默认值)指定Type具有构造函数和析构函数,并且可能不会在内存中移动。

再来看看Q_DECLARE_TYPEINFO的具体实现:

template <typename T>
class QTypeInfo
{
public:
enum {
isSpecialized = std::is_enum<T>::value, // don't require every enum to be marked manually
isPointer = false,
isIntegral = std::is_integral<T>::value,
isComplex = !qIsTrivial<T>(),
isStatic = true,
isRelocatable = qIsRelocatable<T>(),
isLarge = (sizeof(T)>sizeof(void*)),
isDummy = false,
sizeOf = sizeof(T)
};
};

#define Q_DECLARE_TYPEINFO_BODY(TYPE, FLAGS) \
class QTypeInfo<TYPE > \
{ \
public: \
enum { \
isSpecialized = true, \
isComplex = (((FLAGS) & Q_PRIMITIVE_TYPE) == 0) && !qIsTrivial<TYPE>(), \
isStatic = (((FLAGS) & (Q_MOVABLE_TYPE | Q_PRIMITIVE_TYPE)) == 0), \
isRelocatable = !isStatic || ((FLAGS) & Q_RELOCATABLE_TYPE) || qIsRelocatable<TYPE>(), \
isLarge = (sizeof(TYPE)>sizeof(void*)), \
isPointer = false, \
isIntegral = std::is_integral< TYPE >::value, \
isDummy = (((FLAGS) & Q_DUMMY_TYPE) != 0), \
sizeOf = sizeof(TYPE) \
}; \
static inline const char *name() { return #TYPE; } \
}

#define Q_DECLARE_TYPEINFO(TYPE, FLAGS) \
template<> \
Q_DECLARE_TYPEINFO_BODY(TYPE, FLAGS)

可以看出Q_DECLARE_TYPEINFO是一个典型的模板特化和模板enum hack结合的例子,代码使用宏Q_DECLARE_TYPEINFO_BODY定义了一个QTypeInfo的特化版本class QTypeInfo<TYPE >,并且使用定义给定的标志,计算出了一系列枚举值,例如isComplexisStatic等。

Qt预定义了自己类型的QTypeInfo以便让它们在容器中获得更高的处理效率,例如:

// 基础类型
Q_DECLARE_TYPEINFO(bool, Q_PRIMITIVE_TYPE);
Q_DECLARE_TYPEINFO(char, Q_PRIMITIVE_TYPE);
Q_DECLARE_TYPEINFO(signed char, Q_PRIMITIVE_TYPE);
Q_DECLARE_TYPEINFO(uchar, Q_PRIMITIVE_TYPE);
Q_DECLARE_TYPEINFO(short, Q_PRIMITIVE_TYPE);
Q_DECLARE_TYPEINFO(ushort, Q_PRIMITIVE_TYPE);
Q_DECLARE_TYPEINFO(int, Q_PRIMITIVE_TYPE);
Q_DECLARE_TYPEINFO(uint, Q_PRIMITIVE_TYPE);
Q_DECLARE_TYPEINFO(long, Q_PRIMITIVE_TYPE);
Q_DECLARE_TYPEINFO(ulong, Q_PRIMITIVE_TYPE);
Q_DECLARE_TYPEINFO(qint64, Q_PRIMITIVE_TYPE);
Q_DECLARE_TYPEINFO(quint64, Q_PRIMITIVE_TYPE);
Q_DECLARE_TYPEINFO(float, Q_PRIMITIVE_TYPE);
Q_DECLARE_TYPEINFO(double, Q_PRIMITIVE_TYPE);
Q_DECLARE_TYPEINFO(long double, Q_PRIMITIVE_TYPE);
Q_DECLARE_TYPEINFO(char16_t, Q_PRIMITIVE_TYPE);
Q_DECLARE_TYPEINFO(char32_t, Q_PRIMITIVE_TYPE);
Q_DECLARE_TYPEINFO(wchar_t, Q_PRIMITIVE_TYPE);
Q_DECLARE_TYPEINFO(long double, Q_PRIMITIVE_TYPE);

// Qt类型
Q_DECLARE_TYPEINFO(QFileSystemWatcherPathKey, Q_MOVABLE_TYPE);
Q_DECLARE_TYPEINFO(QLoggingRule, Q_MOVABLE_TYPE);
Q_DECLARE_TYPEINFO(QProcEnvKey, Q_MOVABLE_TYPE);
Q_DECLARE_TYPEINFO(QProcEnvValue, Q_MOVABLE_TYPE);
Q_DECLARE_TYPEINFO(QResourceRoot, Q_MOVABLE_TYPE);
Q_DECLARE_TYPEINFO(QConfFileCustomFormat, Q_MOVABLE_TYPE);
Q_DECLARE_TYPEINFO(QSettingsIniKey, Q_MOVABLE_TYPE);
Q_DECLARE_TYPEINFO(QSettingsIniSection, Q_MOVABLE_TYPE);
Q_DECLARE_TYPEINFO(QSettingsKey, Q_MOVABLE_TYPE);
Q_DECLARE_TYPEINFO(QSettingsGroup, Q_MOVABLE_TYPE);
Q_DECLARE_TYPEINFO(QModelIndex, Q_MOVABLE_TYPE);
Q_DECLARE_TYPEINFO(QItemSelectionRange, Q_MOVABLE_TYPE);
Q_DECLARE_TYPEINFO(QBasicTimer, Q_MOVABLE_TYPE);
Q_DECLARE_TYPEINFO(pollfd, Q_PRIMITIVE_TYPE);
Q_DECLARE_TYPEINFO(QSocketNotifierSetUNIX, Q_PRIMITIVE_TYPE);
Q_DECLARE_TYPEINFO(Variable, Q_MOVABLE_TYPE);
Q_DECLARE_TYPEINFO(QMetaMethod, Q_MOVABLE_TYPE);
Q_DECLARE_TYPEINFO(QMetaEnum, Q_MOVABLE_TYPE);
Q_DECLARE_TYPEINFO(QMetaClassInfo, Q_MOVABLE_TYPE);
Q_DECLARE_TYPEINFO(QArgumentType, Q_MOVABLE_TYPE);
Q_DECLARE_TYPEINFO(QCustomTypeInfo, Q_MOVABLE_TYPE);
...

// Qt容器类型
Q_DECLARE_MOVABLE_CONTAINER(QList);
Q_DECLARE_MOVABLE_CONTAINER(QVector);
Q_DECLARE_MOVABLE_CONTAINER(QQueue);
Q_DECLARE_MOVABLE_CONTAINER(QStack);
Q_DECLARE_MOVABLE_CONTAINER(QSet);
Q_DECLARE_MOVABLE_CONTAINER(QMap);
Q_DECLARE_MOVABLE_CONTAINER(QMultiMap);
Q_DECLARE_MOVABLE_CONTAINER(QHash);
Q_DECLARE_MOVABLE_CONTAINER(QMultiHash);

最后让我们来看看Qt容器如何利用QTypeInfo来优化容器算法的。以我们之前介绍过的QList为例,QList会因为类型大小的不同采用不同的内存布局和构造方法:

template <typename T>
Q_INLINE_TEMPLATE void QList<T>::node_construct(Node *n, const T &t)
{
if (QTypeInfo<T>::isLarge || QTypeInfo<T>::isStatic) n->v = new T(t);
else if (QTypeInfo<T>::isComplex) new (n) T(t);
#if (defined(__GNUC__) || defined(__INTEL_COMPILER) || defined(__IBMCPP__)) && !defined(__OPTIMIZE__)
else *reinterpret_cast<T*>(n) = t;
#else
else ::memcpy(n, static_cast<const void *>(&t), sizeof(T));
#endif
}

template <typename T>
Q_INLINE_TEMPLATE void QList<T>::node_destruct(Node *n)
{
if (QTypeInfo<T>::isLarge || QTypeInfo<T>::isStatic) delete reinterpret_cast<T*>(n->v);
else if (QTypeInfo<T>::isComplex) reinterpret_cast<T*>(n)->~T();
}

template <typename T>
Q_INLINE_TEMPLATE void QList<T>::node_copy(Node *from, Node *to, Node *src)
{
Node *current = from;
if (QTypeInfo<T>::isLarge || QTypeInfo<T>::isStatic) {
QT_TRY {
while(current != to) {
current->v = new T(*reinterpret_cast<T*>(src->v));
++current;
++src;
}
} QT_CATCH(...) {
while (current-- != from)
delete reinterpret_cast<T*>(current->v);
QT_RETHROW;
}

} else if (QTypeInfo<T>::isComplex) {
QT_TRY {
while(current != to) {
new (current) T(*reinterpret_cast<T*>(src));
++current;
++src;
}
} QT_CATCH(...) {
while (current-- != from)
(reinterpret_cast<T*>(current))->~T();
QT_RETHROW;
}
} else {
if (src != from && to - from > 0)
memcpy(from, src, (to - from) * sizeof(Node));
}
}

根据以上代码可以看出,QList根据QTypeInfoisLargeisStaticisComplex的不同采用不同的构造析构和拷贝方法。以构造为例,当表达式QTypeInfo<T>::isLarge || QTypeInfo<T>::isStatic计算结果为true时,QList从堆里分配新内存并且构造对象存储在node中。当QTypeInfo<T>::isComplex的计算结果为true时,QList采用Placement new的方式直接使用node内存构造对象。除此之外则简单粗暴的拷贝内存到node内存上。析构和拷贝也有相似处理,阅读代码很容易理解其中的含义。

我们应该怎么做?Qt默认情况下会认为类型特征isStatictrue,这会导致一些不必要的性能下降,例如QList会无视类型大小,采用从堆重新分配内存构造对象。所以我们应该做的是充分理解我们的对象类型是否可以安全的移动,如果可以移动请使用Q_DECLARE_TYPEINFO(TYPE, Q_MOVABLE_TYPE);告知Qt,这样当对象长度小于指针长度的时候,Qt可以避免访问堆来分配内存,并且直接利用已有内存,对于频繁发生的小尺寸对象的操作这种优化是非常巨大的。

Run on (8 X 3600 MHz CPU s)
CPU Caches:
L1 Data 32 KiB (x4)
L1 Instruction 32 KiB (x4)
L2 Unified 256 KiB (x4)
L3 Unified 8192 KiB (x1)
-----------------------------------------------------------------------------------
Benchmark Time CPU Iterations
-----------------------------------------------------------------------------------
BM_QListPushString/iterations:10000000 152 ns 150 ns 10000000
BM_QVectorPushString/iterations:10000000 102 ns 102 ns 10000000
BM_QListPushChar/iterations:10000000 12.2 ns 12.5 ns 10000000
BM_QVectorPushChar/iterations:10000000 4.92 ns 4.69 ns 10000000

详细可以阅读前面的文章《QList 的工作原理和运行效率浅析》。

QList 的工作原理和运行效率浅析

我们知道Qt为了在一些没有STL的环境中运作,开发了一套相对完整的容器。大部分Qt的容器我们都能够招到对应STL容器,例如QVector对应std::vector, QMap对应std::map,不过这其中也有一些特例,例如QList在STL中就没有应该的容器,std::list对应的Qt容器实际上是QLinkedList。所以在使用QList的时候请务必弄清楚这一点,否则可能会导致程序的运行效率的低下,让我们先看一份代码:

#include <benchmark/benchmark.h>
#include <qlist>
#include <qvector>

const std::string test_buffer{ "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz" };
const int ITER_COUNTS = 10000000;

static void BM_QListPushString(benchmark::State& state) {
QList<std::string> test_qlist;
for (auto _ : state) {
test_qlist.push_back(test_buffer);
}
}
BENCHMARK(BM_QListPushString)->Iterations(ITER_COUNTS);

static void BM_QVectorPushString(benchmark::State& state) {
QVector<std::string> test_qvector;
for (auto _ : state) {
test_qvector.push_back(test_buffer);
}
}
BENCHMARK(BM_QVectorPushString)->Iterations(ITER_COUNTS);

static void BM_QListPushChar(benchmark::State& state) {
QList<char> test_qlist;
for (auto _ : state) {
test_qlist.push_back('x');
}
}
BENCHMARK(BM_QListPushChar)->Iterations(ITER_COUNTS);

static void BM_QVectorPushChar(benchmark::State& state) {
QVector<char> test_qvector;
for (auto _ : state) {
test_qvector.push_back('x');
}
}
BENCHMARK(BM_QVectorPushChar)->Iterations(ITER_COUNTS);

BENCHMARK_MAIN();

以上代码使用google benchmark统计QListQVector的运行效率,代码采用的最简单的push_back函数测试两种容器对于小数据和相对较大数据的处理性能。结果如下:

Run on (8 X 3600 MHz CPU s)
CPU Caches:
L1 Data 32 KiB (x4)
L1 Instruction 32 KiB (x4)
L2 Unified 256 KiB (x4)
L3 Unified 8192 KiB (x1)
-----------------------------------------------------------------------------------
Benchmark Time CPU Iterations
-----------------------------------------------------------------------------------
BM_QListPushString/iterations:10000000 152 ns 150 ns 10000000
BM_QVectorPushString/iterations:10000000 102 ns 102 ns 10000000
BM_QListPushChar/iterations:10000000 12.2 ns 12.5 ns 10000000
BM_QVectorPushChar/iterations:10000000 4.92 ns 4.69 ns 10000000

可以发现QVector在两种情况下的性能都占优,尤其是PushChar的情况优势更加明显。原因就要从QList的原理说起了。前面说过QList并不是一个链表链接的结构,它的实际结构如下:

       QListData                                 +--------------------+
| |
+------------------------+ | obj buffer 1 |
| | | |
| ptr to buffer 1 +-----------------------> |
| | +--------------------+
+------------------------+
| | +--------------------+
| ptr to buffer 2 | | |
| +-----------------------> obj buffer 2 |
+------------------------+ | |
| | | |
| . | +--------------------+
| . |
| . |
| |
+------------------------+
| | +--------------------+
| | | |
| ptr to buffer N +-----------------------> |
| | | obj buffer N |
+------------------------+ | |
+--------------------+

它的内部维护了一个指针(void*)的数组,该数组指向了真正的对象,它就像是一个vectorlist的结合体一样。在对象占用内存大的时候(大于sizeof(void*)),它每次会从堆中分配内存。然后将内存的起始地址放入数组中。相对于QVector慢的原因是它每次都要经过堆分配内存,而QVector可以预分配内存从而提高push_back的运行效率。而对于小内存对象,他直接将其存储到数组中,这样不需要经过堆分配内存,所以相对于大内存QList本身也有很大的性能提升,但是由于它每次需要用到sizeof(void*)的内存,也会导致更多的内存分配,所以运行效率还是不如QVector

当然,QList也有自己的优势,例如当对占用大内存对象进行重新排续的时候,QVector只能进行大量内存移动,而QList则只需要移动对象指针即可。相对于std::listQList在单纯的push_back和枚举的时候也有不错的表现。

STL中并行算法

C++17标准的一个重大突破是让标准库中的部分算法支持了并行计算,这对于无处不在的多线程环境来说无疑是一个非常不错的消息。具体支持并行计算的算法可以参考提案文档p0024r2

接下来将会选取两个典型算法函数对STL的并行算法进行介绍:

#include <vector>
#include <algorithm>
#include <execution>

int main()
{
std::vector<int> coll;
coll.reserve(10000);
for (int i = 0; i < 10000; ++i) {
coll.push_back(i);
}

std::for_each(std::execution::par,
coll.begin(), coll.end(),
[](auto& val) {
val *= val;
});
}

以上是一个最简单的并行计算例子,例子中使用了for_each函数,该函数并不是新加入到标准库的。只不过现在多了一个并行计算的版本,其中第一个参数是并行计算的策略。实际上,大部分并行计算的算法都是在原有算法的基础做了新增,它们的共同特点是第一个参数改为了并行计算策略,当然老的算法也依然存在。在这个例子中,策略std::execution::par是并行计算其中的一种策略。在这个策略中函数会使用多线程执行算法,并且线程在执行算法的单个步骤是不会被打断的。为了看清线程的执行情况,我们可以将线程id输出到控制台:

#include <iostream>
#include <vector>
#include <algorithm>
#include <execution>
#include <thread>
int main()
{
std::vector<int> coll;
coll.reserve(10000);
for (int i = 0; i < 10000; ++i) {
coll.push_back(i);
}

std::for_each(std::execution::par,
coll.begin(), coll.end(),
[](auto& val) {
std::cout << std::this_thread::get_id() << std::endl;
val *= val;
});
}

运行这份代码就会发现线程id交替输出到控制台上,可见确实是多线程执行for_each函数。让我们再看看排序函数std::sort

#include <iostream>
#include <vector>
#include <algorithm>
#include <execution>
#include <thread>
int main()
{
std::vector<int> coll;
coll.reserve(10000);
for (int i = 0; i < 10000; ++i) {
coll.push_back(i);
}

std::sort(std::execution::par,
coll.begin(), coll.end(),
[](const auto& val1, const auto& val2) {
std::cout << std::this_thread::get_id() << std::endl;
return val1 > val2;
});
}

执行这份代码同样的会发现多个线程交替输出线程id到控制台上,实际上它们正在并行计算排续该容器。并行计算的优势在数据量足够大的时候是非常明显的,比如:

#include <iostream>
#include <chrono>
#include <vector>
#include <algorithm>
#include <execution>

int main()
{
std::vector<int> coll;
coll.reserve(100000);
for (int i = 0; i < 100000; ++i) {
coll.push_back(i);
}

auto start = std::chrono::high_resolution_clock::now();
std::sort(std::execution::par,
coll.begin(), coll.end(),
[](const auto& val1, const auto& val2) {
return val1 > val2;
});
auto end = std::chrono::high_resolution_clock::now();
std::chrono::duration<double> diff = end - start;
std::cout << "elapsed time = " << diff.count();
}

逆向排序100000个数,使用并行算法在我的机器上消耗了0.48秒。如果删除第一个参数使用传统单线程排续,在我的机器上消耗0.89秒,并行计算性能提升近1倍。

最后来介绍一下C++17中的3种并行计算策略:

  • std::execution::seq 该策略与非并行算法一样,当前执行线程逐个元素依次执行必要的操作。 使用该策略的行为类似于使用完全不接受任何执行策略的非并行调用算法的方式。

  • std::execution::par 该策略会让多个线程执行元素的必要操作。 当算法开始执行必要的操作时,它会一直执行到操作结束,不会被打断。

  • std::execution::par_unseq 该策略会让多个线程执行元素的必要操作,但是与std::execution::par不同的是,该策略不能保证一个线程执行完该元素的所有步骤而不被打断。在提案文档中也指出了错误示例:

    int x = 0;
    std::mutex m;
    int a[] = {1,2};
    std::for_each(std::execution::par_unseq,
    std::begin(a), std::end(a), [&](int) {
    std::lock_guard<mutex> guard(m); // Error: lock_guard constructor calls m.lock()
    ++x;
    });

    这里由于std::execution::par_unseq 无法保证执行lambda表达式的时候不被打断,可能会造成同一个线程两次次进入lambda表达式,并且调用m.lock()导致死锁。

C++在线工具

这篇博客打算介绍4个C++在线工具,当手头没有设备或者没有开发环境的时候可以用它们做一些研究性质的工作。

  1. https://wandbox.org/

    该网站可以在线编辑以及编译C++源代码并且运行编译后的程序。在C++类别它支持GCC和CLANG,另外除了C++,C、C#、Java、GO等等都有支持。

  2. https://quick-bench.com/

    这也是一个可以在线编辑以及编译C++源代码并且运行编译后的程序的网站,但是与上面网站不同的是它运行程序并非用来输出结果,而是对函数做基准检测,采用的是Google Benchmark。同样它支持GCC和CLANG。

  3. https://godbolt.org/

    这是我很喜欢的一个网站,它可以在线编辑和编译C++源代码,但是不可以运行程序。但是这并不能掩盖其优秀的地方,它支持C++各种编译器的各种版本,跨度非常大也非常全面。同时还可以自由设置编译器的编译参数并且查看输出的中间文件,对于研究C++编译过程十分有用。

  4. https://cppinsights.io/

    这是一个非常有趣的网站,它能够将源代码展开,使用一种容易理解的方式展示编译器做了哪些自动化工作。用它自己的话来说,就是从编译器的视角看到的源代码。例如:

    #include <cstdio>
    int main()
    {
    const char arr[10]{2,4,6,8};
    for(const char& c : arr)
    {
    printf("c=%c\n", c);
    }
    }

    会被网站展开为:

    int main()
    {
    const char arr[10] = {2, 4, 6, 8, '\0', '\0', '\0', '\0', '\0', '\0'};
    {
    char const (&__range1)[10] = arr;
    const char * __begin1 = __range1;
    const char * __end1 = __range1 + 10L;
    for(; __begin1 != __end1; ++__begin1)
    {
    const char & c = *__begin1;
    printf("c=%c\n", static_cast<int>(c));
    }
    }
    }

解决vs2019编译qt5.15.2的错误

记录一下编译qt-everywhere-src-5.15.2中qtwebengine遇到的问题。

第一、在windows上用vs2019编译qtwebengine的时候需要patch其中的3个文件,否则会报错。错误看起来好像是:

ninja: build stopped: subcommand failed. 
NMAKE : fatal error U1077: 'call' : return code '0x1'
NMAKE : fatal error U1077: '"...\nmake.exe"' : return code '0x2' Stop.
NMAKE : fatal error U1077: '(' : return code '0x2' Stop.
NMAKE : fatal error U1077: 'cd' : return code '0x2' Stop.
NMAKE : fatal error U1077: 'cd' : return code '0x2' Stop

但实际问题是代码在vs2019的cl里编译出错了,C4244警告被当成错误报出:

FAILED: obj/third_party/angle/angle_common/mathutil.obj
...
../../3rdparty/chromium/third_party/angle/src/common/mathutil.cpp(75): error C4244: '=': conversion from 'double' to 'float', possible loss of data
../../3rdparty/chromium/third_party/angle/src/common/mathutil.cpp(77): error C4244: '=': conversion from 'double' to 'float', possible loss of data
../../3rdparty/chromium/third_party/angle/src/common/mathutil.cpp(79): error C4244: '=': conversion from 'double' to 'float', possible loss of data

所以需要打个补丁,手动修改也行吧,代码量很少:
https://codereview.qt-project.org/c/qt/qtwebengine-chromium/+/321741

From 138a7203f16cf356e9d4dac697920a22437014b0 Mon Sep 17 00:00:00 2001
From: Peter Varga <[email protected]>
Date: Fri, 13 Nov 2020 11:09:23 +0100
Subject: [PATCH] Fix build with msvc2019 16.8.0


Fixes: QTBUG-88708
Change-Id: I3554ceec0437801b4861f68edd504d01fc01cf93
Reviewed-by: Allan Sandfeld Jensen <[email protected]>
---


diff --git a/chromium/third_party/angle/src/common/mathutil.cpp b/chromium/third_party/angle/src/common/mathutil.cpp
index 306cde1..d4f1034 100644
--- a/chromium/third_party/angle/src/common/mathutil.cpp
+++ b/chromium/third_party/angle/src/common/mathutil.cpp
@@ -72,11 +72,11 @@
const RGB9E5Data *inputData = reinterpret_cast<const RGB9E5Data *>(&input);
*red =
- inputData->R * pow(2.0f, (int)inputData->E - g_sharedexp_bias - g_sharedexp_mantissabits);
+ inputData->R * (float)pow(2.0f, (int)inputData->E - g_sharedexp_bias - g_sharedexp_mantissabits);
*green =
- inputData->G * pow(2.0f, (int)inputData->E - g_sharedexp_bias - g_sharedexp_mantissabits);
+ inputData->G * (float)pow(2.0f, (int)inputData->E - g_sharedexp_bias - g_sharedexp_mantissabits);
*blue =
- inputData->B * pow(2.0f, (int)inputData->E - g_sharedexp_bias - g_sharedexp_mantissabits);
+ inputData->B * (float)pow(2.0f, (int)inputData->E - g_sharedexp_bias - g_sharedexp_mantissabits);
}
} // namespace gl
diff --git a/chromium/third_party/blink/renderer/platform/graphics/lab_color_space.h b/chromium/third_party/blink/renderer/platform/graphics/lab_color_space.h
index 78c316e..136c796 100644
--- a/chromium/third_party/blink/renderer/platform/graphics/lab_color_space.h
+++ b/chromium/third_party/blink/renderer/platform/graphics/lab_color_space.h
@@ -130,7 +130,7 @@
// https://en.wikipedia.org/wiki/CIELAB_color_space#Forward_transformation.
FloatPoint3D toXYZ(const FloatPoint3D& lab) const {
auto invf = [](float x) {
- return x > kSigma ? pow(x, 3) : 3 * kSigma2 * (x - 4.0f / 29.0f);
+ return x > kSigma ? (float)pow(x, 3) : 3 * kSigma2 * (x - 4.0f / 29.0f);
};
FloatPoint3D v = {clamp(lab.X(), 0.0f, 100.0f),
diff --git a/chromium/third_party/perfetto/src/trace_processor/timestamped_trace_piece.h b/chromium/third_party/perfetto/src/trace_processor/timestamped_trace_piece.h
index 02363d0..8860287 100644
--- a/chromium/third_party/perfetto/src/trace_processor/timestamped_trace_piece.h
+++ b/chromium/third_party/perfetto/src/trace_processor/timestamped_trace_piece.h
@@ -198,6 +198,20 @@
return *this;
}
+#if PERFETTO_BUILDFLAG(PERFETTO_COMPILER_MSVC)
+ TimestampedTracePiece& operator=(TimestampedTracePiece&& ttp) const
+ {
+ if (this != &ttp) {
+ // First invoke the destructor and then invoke the move constructor
+ // inline via placement-new to implement move-assignment.
+ this->~TimestampedTracePiece();
+ new (const_cast<TimestampedTracePiece*>(this)) TimestampedTracePiece(std::move(ttp));
+ }
+
+ return const_cast<TimestampedTracePiece&>(*this);
+ }
+#endif // PERFETTO_BUILDFLAG(PERFETTO_COMPILER_MSVC)
+
~TimestampedTracePiece() {
switch (type) {
case Type::kInvalid:

第二、在Windows上编译blink的pch也会有些问题,报错找不到头文件:

qt5/qtwebengine/src/3rdparty/chromium/third_party/WebKit/Source/core/win/Precompile-core.cpp: fatal error C1083: Cannot open include file: 
'../../../../../qt5srcgit/qt5/qtwebengine/src/3rdparty/chromium/third_party/WebKit/Source/core/Precompile-core.h': No such file or directory

需要patch两个文件blink/renderer/platform/BUILD.gn 和 blink/renderer/core/BUILD.gn

--- qtwebengine/src/3rdparty/chromium/third_party/blink/renderer/platform/BUILD.gn
+++ qtwebengine/src/3rdparty/chromium/third_party/blink/renderer/platform/BUILD.gn
@@ -204,7 +204,7 @@


config("blink_platform_pch") {
if (enable_precompiled_headers) {
- if (is_win) {
+ if (false) {
# This is a string rather than a file GN knows about. It has to match
# exactly what's in the /FI flag below, and what might appear in the
# source code in quotes for an #include directive.

使用std::any代替std::shared_ptr<void>和void *

大家在编写程序的时候应该遇到过这样一个场景,该场景需要传递某种数据,但是数据类型和数据大小并不确定,这种时候我们常用void *类型的变量来保存对象指针。例如:

struct SomeData { 
// ...
void* user_data;
};

上面的结构体只是一个示例,代表有的数据是用户产生的。当用户数据是一个字符串时,可能的代码是:

SomeData sd{};
sd.user_data = new std::string{ "hello world" };

另外,使用void*存储数据需要了解数据类型,并且需要自己维护数据的生命周期:

std::string *str = static_cast<std::string *>(sd.user_data);
delete str;
str = nullptr;

使用std::shared_ptr<void>可以解决生命周期的问题:

struct SomeData {
// ...
std::shared_ptr<void> user_data;
};

SomeData sd{};
sd.user_data = std::make_shared<std::string>("hello world");

auto ud = std::static_pointer_cast<std::string>(sd.user_data);

虽然std::shared_ptr<void>可以用于管理生命周期,但是类型安全的问题却无法解决。比如当user_data销毁时,由于缺乏类型信息会导致对象无法正确析构。

为了解决以上这些问题,C++17标准库引入std::any。顾名思义就是可以存储任意类型,我们可以将其理解为带有类型信息的void*。例如:

struct any {
void* object;
type_info tinfo;
};

当然,std::any的实现比这个要复杂的多,我们后面再讨论类型是如何被记录下来的。先来看看std::any的用法:

#include <iostream>
#include <string>
#include <any>

int main()
{
std::any a;
a = std::string{ "hello world" };
auto str = std::any_cast<std::string>(a);
std::cout << str;
}

除了转换为对象本身,还可以转换为引用:

auto& str1 = std::any_cast<std::string&>(a);
auto& str2 = std::any_cast<const std::string&>(a);

当转换类型不正确时,std::any_cast会抛出异常std::bad_any_cast

try {
std::cout << std::any_cast<double>(a) << "\n";
}
catch (const std::bad_any_cast&) {
std::cout << "Wrong Type!";
}

如果转换的不是对象而是对象指针,那么std::any_cast不会抛出异常,而是返回空指针

auto* ptr = std::any_cast<std::string>(&a);
if(ptr) {
std::cout << *ptr;
} else {
std::cout << "Wrong Type!";
}

请注意,使用std::any_cast转换类型必须和std::any对象的存储类型完全一致,否则同样会抛出异常,即使两者是继承关系。原因很简单,std::any_cast是直接使用type_info作比较:

const type_info* const _Info = _TypeInfo();
if (!_Info || *_Info != typeid(_Decayed)) {
return nullptr;
}

最后简单描述一下std::any保证类型安全的原理:

首先是类型转换,刚刚已经提到了,std::any会记录对象的type_infostd::any_cast使用type_info作比较,只有完全一致才能进行转换。

其次为了保证类型正确的拷贝,移动以及生命周期结束时能够正确析构,在创建std::any对象时生成一些函数模板实例,这些函数模板调用了类型的拷贝,移动以及析构函数。std::any只需要记录这些函数模板实例的指针即可。拿析构简单举例:

template <class T>
void destroy_impl(void* const p)
{
delete static_cast<T*>(p);
}

using destory_ptr = void (*)(void* const);

struct AnyMetadata {
destory_ptr func;
...
};

template<class T>
void create_anymeta(AnyMetadata &meta)
{
meta.func = destroy_impl<T>;
}

// any构造时知道目标对象类型,此时可以保存函数指针
AnyMetadata metadata;
create_anymeta<std::string>(metadata);

// any销毁时调用
metadata.func(obj);

使用std::sample获取随机样本

C++17标准库提供了一个std::sample函数模板用于获取随机样本,该样本是输入全体样本的一个子集。具体例子如下:

#include <iostream>
#include <vector>
#include <iterator>
#include <algorithm>
#include <random>
int main()
{
std::vector<int> data;
for (int i = 0; i < 10000; ++i) {
data.push_back(i);
}

std::sample(data.begin(),
data.end(),
std::ostream_iterator<int>{std::cout, "\n"},
10,
std::default_random_engine{});
}

可以看到std::sample需要5个参数,其中前2个参数是全体样本的合计的beginend迭代器,它定义了全体样本的范围。第3个参数则是输出迭代器,第4个参数是需要样本的数量,最后是随机数引擎。注意这里std::default_random_engine没有设置seed,这必然导致每次运行获取的样本相同。

以上代码的输出结果为:

0
488
963
1994
2540
2709
2835
3518
5172
7996

我们可以为随机数引擎设置seed

std::random_device rd;
std::default_random_engine eng{ rd() };
std::sample(data.begin(),
data.end(),
std::ostream_iterator<int>{std::cout, "\n"},
10,
eng);

这样每次样本就会发生变化。另外std::sample是有返回值的,返回的是最后一个随机样本之后的迭代器。它的作用是确定随机样本在输出容器中的范围,例如:

#include <iostream>
#include <vector>
#include <iterator>
#include <algorithm>
#include <random>
int main()
{
std::vector<int> data;
for (int i = 0; i < 10000; ++i) {
data.push_back(i);
}

std::vector<int> out_data;
out_data.resize(100);
std::random_device rd;
std::default_random_engine eng{ rd() };
auto end = std::sample(data.begin(),
data.end(),
out_data.begin(),
10,
eng);

std::cout << "coll size: "
<< out_data.size()
<< std::endl;
for (auto it = out_data.begin(); it != end; ++it) {
std::cout << *it << std::endl;
}
}

以上代码的输出结果为:

coll size: 100
1708
1830
2803
3708
5146
7376
7867
8059
8271
9448

可以看到,虽然容器的大小是100,但是我们只填充10个随机样本。最后需要说明一下std::sample对于两个迭代器参数的要求,首先源迭代器至少是一个输入迭代器的时候,目标迭代器至少可以是一个输出迭代器。但是当源迭代器不是一个向前迭代器,那么目标迭代器必须是一个随机迭代器。这一点很好理解,当源迭代器不能确保随机的情况下,只能将目的迭代器随机以确保样本的随机性。

实现一个类似std::bind的功能

前两天有朋友问我std::bind是如何实现的,对照STL讲述原理后朋友表示还是很难理解,这可以理解,因为STL涉及到的东西太多,很难清晰的将核心部分显式出来。为了解释清楚这个问题,我自己实现了一个bind功能。当然了,比std::bind要简单非常非常多,缺少很多有用的特性,但是也能展示bind的核心原理了。

template<int _Nx>
struct _MyPh
{
};

constexpr _MyPh<0> _0;
constexpr _MyPh<1> _1;
constexpr _MyPh<2> _2;
constexpr _MyPh<3> _3;
constexpr _MyPh<4> _4;

template<typename R, typename F, typename ... Arg>
class _MyBind {
public:
_MyBind(F f, Arg ... arg) : _MyList(arg...), _f(f) {}
template<typename ... CallArg>
R operator()(CallArg... arg)
{
_MyBind<R, F, CallArg...> c(0, arg...);
std::size_t constexpr tSize
= std::tuple_size<std::tuple<Arg...>>::value;
return call_tuple(_f, _MyList,
c, std::make_index_sequence<tSize>());
}

template<typename F, typename Tuple, typename C, size_t ...S>
R call_tuple(F f, Tuple t, C c, std::index_sequence<S...>)
{
return f(c[std::get<S>(_MyList)]...);
}

template<typename T> T operator[] (T &t) { return t; }
template<int N> typename std::tuple_element<N,
std::tuple<Arg...>>::type operator[] (_MyPh<N>)
{
return std::get<N>(_MyList);
}
private:
std::tuple<Arg...> _MyList;
F _f;
};
template<typename R, typename F, typename ... Arg>
_MyBind<R, F, Arg...> mybind(F f, Arg ... arg)
{
return _MyBind<R, F, Arg...>(f, arg...);
}

int sum(int a, int b, int c)
{
std::cout << a << b << c;
return a + b + c;
}

int main()
{
auto myfunc = mybind<int>(sum, _0, 2, _1)(1, 5);
}

首先占位符其实就是一个空类型,我们不需要类型里有什么,只是想要一个类型标识符。

然后看到最关键的_MyBind类模板,该类模板有数据成员_MyList_f,用于存放绑定的函数和参数。在构造对象的时候数据成员会被填充,并且在调用template<typename ... CallArg> R operator()(CallArg... arg)的时候使用这两个数据成员。这里比较难理解的是call_tuple函数模板,该函数需要将绑定的参数列表和后续调用的参数列表传入函数,

最后使用SFINAE的技巧有选择的通过operator[]获取对应的值。如果std::get<S>(_MyList)返回的是绑定的具体值,那么通过template<typename T> T operator[] (T &t) { return t; }返回值本身,注意这里的t是最外层_MyList中的元素;如果std::get<S>(_MyList)返回的是占位符,那么将通过template<int N> typename std::tuple_element<N, std::tuple<Arg...>>::type operator[] (_MyPh<N>) { return std::get<N>(_MyList); }返回c_MyList的元素,请注意这里的this对象是c

当然为了使用方便需要一个函数模板mybind,它只需要指定一个返回类型就可以使用了。

使用std::span代替数组指针传参

我们知道std::string_view可以创建std::string的一个视图,视图本身并不拥有实例,它只是保持视图映射的状态。在不修改实例的情况下,使用std::string_view会让字符串处理的性能大幅提升。实际上,对于那些连续的序列对象我们都可以创建这样一份视图,对于std::vector这样的对象可以提高某些操作中的性能,另外对原生数组可以提高其访问的安全性。

过去如果一个函数想接受无法确定数组长度的数组作为参数,那么一定需要声明两个参数:数组指针和长度:

void set_data(int *arr, int len) {}

int main()
{
int buf[128]{ 0 };
set_data(buf, 128);
}

这种人工输入增加了编码的风险,数组长度的错误输入会引发程序的未定义行为,甚至是成为可被利用的漏洞。C++20标准库为我们提供了一个很好解决方案std::span,通过它可以定义一个基于连续序列对象的视图,包括原生数组,并且保留连续序列对象的大小。例如:

#include <iostream>
#include <span>
void set_data(std::span<int> arr) {
std::cout << arr.size();
}

int main()
{
int buf[128]{ 0 };
set_data(buf);
}

除了原生数组,std::vectorstd::array也在std::span的处理之列:

std::vector<int> buf1{ 1,2,3 };
std::array<int, 3> buf2{ 1, 2, 3 };
set_data(buf1);
set_data(buf2);

值得注意的是,std::span还可以通过构造函数设置连续序列对象的长度:

int buf[128]{ 0 };
set_data({ buf, 16 });

std::string_viewstd::span,我们可以看出C++标准库很乐于这种视图设计,因为这种设计和抽象的实现可以提高C ++程序的可靠性而又不牺牲性能和可移植性。