笔记列表

《提高C++性能的编程技术》笔记:总结
《提高C++性能的编程技术》笔记:跟踪
《提高C++性能的编程技术》笔记:构造函数、析构函数
《提高C++性能的编程技术》笔记:临时对象
《提高C++性能的编程技术》笔记:内存池(单线程、多线程)
《提高C++性能的编程技术》笔记:内联
《提高C++性能的编程技术》笔记:STL
《提高C++性能的编程技术》笔记:引用计数
《提高C++性能的编程技术》笔记:编码优化
《提高C++性能的编程技术》笔记:设计优化/可扩展性/系统体系结构

引用计数(reference counting):基本思想是将销毁对象的职责从客户端代码转移到对象本身。对象跟踪记录自身当前被引用的数目,在引用计数达到零时自行销毁。换句话说,对象不再被使用时自行销毁。

引用计数和执行速度之间的关系是与上下文紧密关联的。该关系取决于以下几个因素:

(1). 目标对象的资源消耗量集中于哪些方面?如果目标对象使用过多内存,比如未保护内存,将使可用内存受限,并导致显著的性能损失,表现为缓存命不中和页面错误。

(2). 分配(释放)目标对象所使用资源的代价有多高?即便从堆中分配1字节空间也需要执行数百条指令。释放时亦然。

(3). 可能有多少对象共享目标对象的单个实例?通过使用赋值操作符和拷贝构造函数可以提升共享率。

(4). 创建(销毁)第一个(最后一个)目标对象引用的额度有多高?使用构造函数而不是拷贝构造函数创建新的引用计数对象时,会产生对目标对象的初次引用。这种操作代价高昂。与创建一个新的目标对象相比,这种方法包含更多开销。移除最后一次引用时也是如此。

对于预先存在且无法修改的类,引用计数依然可以实现,只不过,这种情况需要对设计进行一些修改。也可以在多线程执行环境下处理引用计数。在这种情况下,多个线程可能会并发访问同一个引用计数对象。因此必须对维持引用计数的变量进行保护,使其对进行的更新是原子操作。原子更新操作要求有一个锁定机制。

引用计数在性能上并非无往不胜。引用计数、执行时间和资源维护会产生微妙的相互作用,如果对性能方面的考虑很重要,就必须对这几个方面仔细进行评估。引用计数是提升还是损害性能取决于其使用方式。下面的任意一种情况都可以使引用计数变得更为有效:目标对象是很大的资源消费者;资源分配和释放的代价很高;高度共享,由于使用赋值操作符和拷贝构造函数,引用计数的性能可能会很高;创建和销毁引用的代价低廉。反之,则应跳出引用计数而转为使用更加有效的简单非计数对象。

以下是测试代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
#include <iostream>
#include <chrono>
#include <string>
#include <string.h>

namespace reference_counting_ {

// reference: 《提高C++性能的编程技术》:第十二章:引用计数
namespace {

// 为使引用计数更加方便,我们需要为每个BigInt对象关联一个引用计数。
// 实现这一操作的方式有两种,为BigInt直接添加refCount成员或使其继承自基类RCObject
// RCObject是引用计数对象的基类,并且封装了所有引用计数变量以及针对这些变量的操作
class RCObject {
public:
void addReference() { ++refCount; }
void removeReference() { if (--refCount == 0) delete this; }

void markUnshareable() { shareable = false; }
bool isShareable() const { return shareable; }
bool isShared() const { return refCount > 1; }

protected:
RCObject() : refCount(0), shareable(true) {}
RCObject(const RCObject& rhs) : refCount(0), shareable(true) {}
RCObject& operator=(const RCObject& rhs) { return *this; }
virtual ~RCObject() {}

private:
int refCount;
bool shareable;
};

// BigInt类的功能是将正整数表示成用二进制编码的十进制形式
class BigInt : public RCObject {
friend BigInt operator+ (const BigInt&, const BigInt&);

public:
BigInt(const char*);
BigInt(unsigned = 0);
BigInt(const BigInt&);
BigInt& operator= (const BigInt&);
BigInt& operator+= (const BigInt&);
~BigInt();

char* getDigits() const { return digits; }
unsigned getNdigits() const { return ndigits; }
void print() { fprintf(stdout, "digits: %s\n", digits); }

private:
char* digits;
unsigned ndigits;
unsigned size; // 分配的字符串的大小
BigInt(const BigInt&, const BigInt&);
char fetch(unsigned i) const;
};

BigInt::BigInt(unsigned u)
{
unsigned v = u;
for (ndigits = 1; (v/=10) > 0; ++ndigits) {
;
}

digits = new char[size=ndigits];
for (unsigned i = 0; i < ndigits; ++i) {
digits[i] = u%10;
u /= 10;
}
}

BigInt::~BigInt()
{
delete [] digits;
}

BigInt& BigInt::operator=(const BigInt& rhs)
{
if (this == &rhs) return *this;

ndigits = rhs.ndigits;
if (ndigits > size) {
delete [] digits;
digits = new char[size = ndigits];
}

for (unsigned i = 0; i < ndigits; ++i) {
digits[i] = rhs.digits[i];
}

return *this;
}

BigInt::BigInt(const char* s)
{
if (s[0] == '\0') {
s = "0";
}

size = ndigits = strlen(s);
digits = new char[size];
for (unsigned i = 0; i < ndigits; ++i) {
digits[i] = s[ndigits-1-i] - '0';
}
}

BigInt::BigInt(const BigInt& copyFrom)
{
size = ndigits = copyFrom.ndigits;
digits = new char[size];

for (unsigned i = 0; i < ndigits; ++i) {
digits[i] = copyFrom.digits[i];
}
}

// BigInt = left + right
BigInt::BigInt(const BigInt& left, const BigInt& right)
{
size = 1 + (left.ndigits > right.ndigits ? left.ndigits : right.ndigits);
digits = new char[size];
ndigits = left.ndigits;
for (unsigned i = 0; i < ndigits; ++i) {
digits[i] = left.digits[i];
}

*this += right;
}

inline char BigInt::fetch(unsigned i) const
{
return i < ndigits ? digits[i] : 0;
}

BigInt& BigInt::operator+=(const BigInt& rhs)
{
unsigned max = 1 + (rhs.ndigits > ndigits ? rhs.ndigits : ndigits);
if (size < max) {
char* d = new char[size=max];
for (unsigned i = 0; i < ndigits; ++i) {
d[i] = digits[i];
}

delete [] digits;
digits = d;
}

while (ndigits < max) {
digits[ndigits++] = 0;
}

for (unsigned i = 0; i < ndigits; ++i) {
digits[i] += rhs.fetch(i);
if (digits[i] >= 10) {
digits[i] -= 10;
digits[i+1] = 1;
}
}

if (digits[ndigits-1] == 0) {
--ndigits;
}

return *this;
}

std::ostream& operator<<(std::ostream& os, BigInt& bi)
{
char c;
const char* d = bi.getDigits();

for (int i = bi.getNdigits() - 1; i >= 0; i--) {
c = d[i] + '0';
os << c;
}

os << std::endl;
return os;
}

inline BigInt operator+(const BigInt& left, const BigInt& right)
{
return BigInt(left, right);
}

// 智能指针:这种特殊指针的任务是对引用计数进行登记
template<class T>
class RCPtr {
public:
RCPtr(T* realPtr = 0) : pointee(realPtr) { init(); }
RCPtr(const RCPtr& rhs) : pointee(rhs.pointee) { init(); }
~RCPtr() { if (pointee) pointee->removeReference(); }

RCPtr& operator=(const RCPtr& rhs);
T* operator->() const { return pointee; }
T& operator*() const { return *pointee; }

private:
T* pointee;
void init();
};

template<class T>
void RCPtr<T>::init()
{
if (0 == pointee) return;
if (false == pointee->isShareable()) {
pointee = new T(*pointee);
}

pointee->addReference();
}

template<class T>
RCPtr<T>& RCPtr<T>::operator=(const RCPtr& rhs)
{
if (pointee != rhs.pointee) {
if (pointee) pointee->removeReference();
pointee = rhs.pointee;
init();
}

return *this;
}

// RCBigInt:构造BigInt的引用计数实现,RCBigInt需要指向一个真正的BigInt对象
// 如果是频繁赋值和复制RCBigInt对象的工作,RCBigInt会大显身手。另外,与直接使用简单BigInt相比,
// 由于创建了对新BigInt对象的初次引用,使用新RCBigInt对象的代价要更高一些。每当RCBigInt产生了
// 对BigInt的初次引用时,就会在堆内存中创建一个BigInt对象并指向它。对于基于堆栈(局部变量)的简单
// BigInt对象而言,则不必付出这种代价。此类的情况在移除最后一次BigInt引用时也会发生。这是因为
// 底层的BigInt对象被释放并还给堆内存。
class RCBigInt {
friend RCBigInt operator+(const RCBigInt&, const RCBigInt&);

public:
RCBigInt(const char* p) : value(new BigInt(p)) {}
RCBigInt(unsigned u = 0) : value(new BigInt(u)) {}
RCBigInt(const BigInt& bi) : value(new BigInt(bi)) {}

void print() const { value->print(); }

private:
RCPtr<BigInt> value;
};

inline RCBigInt operator+(const RCBigInt& left, const RCBigInt& right)
{
return RCBigInt(*(left.value) + *(right.value));
}

} // namespace

} // namespace reference_counting_
using namespace reference_counting_;

int main()
{
std::chrono::high_resolution_clock::time_point time_start, time_end;
const int count{10000000};

{ // test BigInt create
time_start = std::chrono::high_resolution_clock::now();
for (int i = 0; i < count; ++i) {
BigInt a = i;
BigInt b = i + 1;
BigInt c = i + 2;
BigInt d = i + 3;
}
time_end = std::chrono::high_resolution_clock::now();
fprintf(stdout, "BigInt create time spend: %f seconds\n",
(std::chrono::duration_cast<std::chrono::duration<double>>(time_end-time_start)).count());
}

{ // test RCBigInt create
// RCBigInt测试会更多地忙于初次引用的创建及之后将其销毁的工作
time_start = std::chrono::high_resolution_clock::now();
for (int i = 0; i < count; ++i) {
RCBigInt a = i;
RCBigInt b = i + 1;
RCBigInt c = i + 2;
RCBigInt d = i + 3;
}
time_end = std::chrono::high_resolution_clock::now();
fprintf(stdout, "RCBigInt create time spend: %f seconds\n",
(std::chrono::duration_cast<std::chrono::duration<double>>(time_end-time_start)).count());
}

{ // test BigInt assign
BigInt a, b, c;
BigInt d = 1;

time_start = std::chrono::high_resolution_clock::now();
for (int i = 0; i < count; ++i) {
a = b = c = d;
}
time_end = std::chrono::high_resolution_clock::now();
fprintf(stdout, "BigInt assign time spend: %f seconds\n",
(std::chrono::duration_cast<std::chrono::duration<double>>(time_end-time_start)).count());
}

{ // test RCBigInt assign
// 对RCBigInt对象的赋值操作效率高于BigInt对象,但是创建和销毁对象时却相反
RCBigInt a, b, c;
RCBigInt d = 1;

time_start = std::chrono::high_resolution_clock::now();
for (int i = 0; i < count; ++i) {
a = b = c = d;
}
time_end = std::chrono::high_resolution_clock::now();
fprintf(stdout, "RCBigInt assign time spend: %f seconds\n",
(std::chrono::duration_cast<std::chrono::duration<double>>(time_end-time_start)).count());
}

return 0;
}

利用 godbolt 执行,相应代码见 点击这里 测试结果如下:

1
2
3
4
BigInt create time spend: 2.138115 seconds
RCBigInt create time spend: 4.180369 seconds
BigInt assign time spend: 0.106073 seconds
RCBigInt assign time spend: 0.021766 seconds