笔记列表
《提高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_ { namespace { 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; }; 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::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 ; } 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)); } } } using namespace reference_counting_;int main () { std::chrono::high_resolution_clock::time_point time_start, time_end; const int count{10000000 }; { 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 ()); } { 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 ()); } { 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 ()); } { 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