C++的设计优化

发表于 2012-12-17 分类于编程语言， C++ 阅读次数： Valine：
本文字数： 1.4k 阅读时长 ≈ 1 分钟

设计优化是一种全局的优化，是比代码优化更难判断的东西。本文只以提高c++性能的编程技术一书的说法再自己的理解为例子。性能和灵活性本来就是相互冲突的东西。将两者结合得很好的例子一般能想到STL，但是STL在特定的场合肯定比不上专用代码的性能。比如，用stl里面的accmulate累加int能够与自己的实现效果一样，但是累加string的话就会比手动实现效果差很多。所以作者提出了个这样的观点，软件库是通用的，但是软件不是，所以没必要让软件太通用，视野应该窄一点。

例子一，还是利用缓存机制。
比如，一个web服务器经常要计算时间戳，而且是在1s内要计算不少次。由于时间戳没必要以ms进行区分，那么可以只计算一次时间戳，然后将时间戳保存起来，或者作为参数传递给后面的调用。

例子二，扩展数据类型。
比如，使用字符串的时候假如经常要计算字符串长度，那么可以定义一个结构体，内部有个成员用于保存长度。这样在很多需要长度的场合就可以避免重复计算长度了。

例子三，避免公共代码陷阱。
比如，在一个公共函数中，需要处理ipv4和ipv6两种情况，那么你就必须在函数中进行判断当前处理的是ipv4还是ipv6。但是，这种判断并不是必须的，如果你不使用公共函数的话。最重要的问题是，如果有很多这样的公共函数，那么就会出现成千上万这样其实没必要的判断，无疑对于性能是一个重大的损失。

例子四，使用高效的数据结构和算法。
当然这点需要扎实的算法知识。

例子五，使用缓式计算。
同上一篇文章中描述的一样，将计算延缓到真正需要的时候。比如，调用getpeername获得对方ip地址和调用getsockname获得本地服务器ip地址都是些昂贵的调用，那么我们还是把这些调用延迟到真正需要的时候吧。而且对方ip地址可以在accept函数调用的时候就得到了，这个时候保存起来就可以了。
缓式计算类似于下面的类定义，

class X
{
    X() {veryExpensive = NULL;}
    ~X() { if (veryExpensive) delete veryExpensive; }
    Z* get_veryExpensive()
    {
        if (NULL == veryExpensive)
        {
            set_veryExpensive();
        }
        return veryExpensive;
    }

    void set_veryExpensive
    {
        veryExpensive = new Z;//do some expensive thing
        //...
    }
private:
    Z* veryExpensive;
};

例子六，避免无用计算。
比如，很多时候memset并不是必须的，那么就应该避免，尤其memset大块内存的时候。类中对成员的默认构造函数调用有的时候也是浪费，应该使用成员初始化列表。这种情况，应该还有很多其它的例子。

例子七，删除已经失效的代码。
已经失效的代码是只不会再使用的代码，你应该将其删除掉，否则那些代码还是会造成性能损失。

总之，设计上面的优化是个太难的题目了，我觉得这本书上面很多例子都有点和代码上的优化重复了。不过，性能和灵活性确实是相反的方向，有的时候牺牲灵活性是非常必须的。</pre>

C++的代码优化

发表于 2012-12-13 分类于编程语言， C++ 阅读次数： Valine：
本文字数： 2k 阅读时长 ≈ 2 分钟

代码优化这种东西，肯定是经验之谈，即使你对代码的执行细节理解的很清楚，没有实际的经验体会也不会对之有多大的感觉。看书本人虽然觉得是揠苗助长，但是这估计就类似于打疫苗吧。要是艾滋有疫苗现在估计就没有世界艾滋日了。所以，看看书打打疫苗还是很有好处的。
代码优化很多就是些避免冗余计算，但是场合不同，有些可能你都从没有考虑过需要这样的优化。我打算把我从提高c++性能的编程技术上面看到的代码优化总结一下，随便扯几下。

例子一，用缓存计算结果优化循环。

原始代码，

1	for (...; !done; ...) done = patternMatch(pat1, pat2, isCaseSenstive());

优化代码,

1 2	bool isSenstive = isCaseSenstive(); for (...; !done; ...) done = patternMatch(pat1, pat2, isSenstive);

这个例子比较简单，一般情况大家都能优化循环，去掉循环内部的重复的函数调用和计算等。

例子二，预先计算某些结果以优化后面的计算。
比如，你需要将一个字符串转换为大写的，你是对字符串循环一次，循环内部调用toupper了，还是预先计算出toupper的结果，以后每次查表了。
优化后的代码应该是类似于这样的。
for (char p = header; p; ++p) p = uppercaseTable[p];
你所需要做的就是在初始化时候构造出uppercaseTable这张大小为256的表，如果你需要经常做大写转换无疑能不错的提高性能。

例子三，降低灵活性来换取速度。
书上只举了一个例子，为ip地址分配内存。我们知道ip4的地址不会超过15个字节，即使ip6的地址也不是很长。如果每次，我们动态分配内存去容纳地址，这肯定是非常浪费的事情。如果你需要容纳的地址数目是有限的，那么我们完全可以静态分配数组来容纳地址。全局new和delete的操作是非常昂贵的，这不仅仅在堆内存分配过程的复制上，线程同步机制也消耗了很多cpu周期。这只是个小小的例子而已，灵活性有的时候根本没必要。

例子四，用80-20规则优化常用代码路径速度。
这个例子的内容说起来比较麻烦，其实就是利用c语言的短路逻辑判断，执行较少的代码。
比如，if (e1 || e2)和if (e1 e2)这样的代码。通过，优化可以提高速度。
假设c1为e1执行的代价，p1为e1为真的概率，c2为e1执行的代价，p2为e2为真的概率。
那么可以计算出if (e1 || e2)的代价期望，同样可以计算出if (e2 || e1)的代价期望，选择较小的即可了。

例子五，延迟计算。
有些计算你可能并不需要，那么就请等到你真正需要的时候再计算吧。

int route(Msg* msg)
{
	ExpensiveClass upstream(msg);
	if (goingUpstream)
	{
	...//use upstream
	}

	return SUCCESS;
}

这种代码明显应该把对象upstream的定义放在if内部，因为有些对象的构造和析构可能会花费很大代价。
不过，我好像记得有公司内部的代码规范禁止在构造函数和析构函数作有意义的初始化和释放，而是自己再写个Init和UnInit函数来代替构造函数和析构函数的本职作用。我也不知道哪样好点，如果是那样的话，本例子就对他们没有意义了。呵呵。

例子六，去掉无用计算。
例子的内容是用成员初始化列表代替成员的默认构造函数的调用，没有什么多说的。

例子七，恰当利用系统的缓存机制。
比如，下面结构体的定义。
struct X { int a; char b[4096]; int c;};
应该改成struct X { int a; int c;char b[4096]; };
原因是cpu缓存可能就128个字节，那么加载a的时候可能一次缓存了连在一起的128个字节。由于a和c之间距离比较远，那么c就不在缓存行里面了。如果，你需要再访问c就会造成缓存失败，就需要重新加载缓存。这种降低缓存命中率的事情确实不怎么好。但是，你也不知道编译器会不会调整内存结果，把a和c默认连在一起了。我觉得还是不要做这种假设吧，这完全是改变编程者的意图了。

例子八，去掉没必要的堆内存使用，改为堆栈内存。

例子九，谨慎使用库。
比如，string的使用很多情况就比默认的char数组慢很多。其内部七七八八的实现不知道做了多少工作了，而作为调用者可能你都不怎么清楚。就比如很多时候我们根部不需要线程同步，但是string的内部实行可能考虑了线程同步，那么对于我们这完全就是个浪费了。string.h内部的那些字符串操作函数，应该是没有考虑线程同步的，这个时候显然就快很多了。

例子十，请打开编译器优化选项。
因为很多编译器优化选项不是默认打开的，如果你没有打开，那么编译器是不可能为你做全力的优化的。

引用计数

发表于 2012-12-11 分类于编程语言， C++ 阅读次数： Valine：
本文字数： 28k 阅读时长 ≈ 25 分钟

引用计数说得直接点就是不同的对象内部共享同样的内容(内存)，同时对象能够自己跟踪自己被引用多少次，能够在没有被继续引用的时候删除自己，保证了没有内存泄漏的出现。看起来貌似java里面的垃圾回收机制了。很多事物都有两面性，引用计数也不例外。看起来牛逼的东西必然有它的弱点，总有一些地方它比不过最原始的东西。

书上说了两种极端的情况，一种是大量的对象共享少数的相同的内容，一种是同样的内容只被共享少数几次，也就是基本没多少共享。显然前者是利用引用计数的典型情况。一般来说，下面的一些条件有利于引用计数的使用。比如说，目标对象消耗大量的资源;资源的分配和释放很昂贵;高度共享:由于使用复制构造函数和赋值操作符,所以引用计数可能比较大;引用的创建和清除相对低廉。如果程序中出现大量的对象创建和释放的操作，使用引用计数的效果反而会更差，而出现大量的对象的赋值操作则适合于引用计数的使用。

一般来说主要有两种实现方式。一种是你能够修改目标类的代码的情况，一种是你不能够得到目标类代码的情况。另外，还有给这些实现加上线程同步的情况。我分别实现了相关的代码，你也可以从提高c++性能的编程计数上面找到相关的代码。

情况1的类设计图如下，

从类设计图中可以看到要实现一个引用计数需要额外的三个类。RCObject是存储引用计数变量的基类，RCPtr是一个智能指针类，RCBigInt类里面包含一个RCPtr成员，该类相当于BigInt的代理类，和BigInt向外提供同样的接口。BigInt的实现稍微复杂了点，你也可以用任何简单的类替换它。

代码如下:

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>
#include <iostream>
using namespace std;

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;
    }

private:
    int refCount;
    bool shareable;
};

class BigInt : public RCObject
{
    friend BigInt operator+(const BigInt, const BigInt);
public:
    BigInt(const char*);
    BigInt(unsigned u = 0);
    BigInt(const BigInt);
    BigInt operator=(const BigInt);
    BigInt operator+=(const BigInt);
    ~BigInt()
    {
        delete [] digits;
    }

    char* getDigits() const
    {
        return digits;
    }
    unsigned getNdigits() const
    {
        return ndigits;
    }

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

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(unsigned u)
{
    unsigned v = u;

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

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::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;
        d = digits;
    }

    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]++;
        }
    }

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

    return *this;
}

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 BigInt operator+(const BigInt left, const BigInt right)
{
    return BigInt(left, right);
}

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

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

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

    return *this;
}

ostream operator<<(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 << endl;

    return os;
}

template <typename T> class RCPtr
{
public:
    RCPtr(T* realPtr = NULL) : pointee(realPtr) { Init(); }
    RCPtr(const RCPtr rhs) : pointee(rhs.pointee) { Init(); }
    ~RCPtr() { if (pointee) pointee->removeReference(); }
    T* operator->() const { return pointee; }
    T operator*() const { return * pointee; }
    RCPtr operator=(const RCPtr rhs);

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

template <typename T> void RCPtr<T>::Init()
{
    if (pointee == 0) return;

    if (pointee->isShareable() == false)
    {
        pointee = new T(*pointee);
    }
    pointee->addReference();
}

template <typename 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)) {}

private:
    RCPtr<BigInt> value;
};

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

void TestBigIntCreate(int n)
{
    printf("TestBigIntCreate:%d\n", n);
    clock_t beg = clock();
    for (int i = 0; i < n; ++i)
    {
        BigInt a = i;
        BigInt b = i + 1;
        BigInt c = i + 2;
        BigInt d = i + 3;
    }
    clock_t end = clock();
    printf("use %f second(s).\n", 1.0 * (end - beg) / CLOCKS_PER_SEC);
}

void TestRCBigIntCreate(int n)
{
    printf("TestRCBigIntCreate:%d\n", n);
    clock_t beg = clock();
    for (int i = 0; i < n; ++i)
    {
        RCBigInt a = i;
        RCBigInt b = i + 1;
        RCBigInt c = i + 2;
        RCBigInt d = i + 3;
    }
    clock_t end = clock();
    printf("use %f second(s).\n", 1.0 * (end - beg) / CLOCKS_PER_SEC);
}

void TestBigIntAssign(int n)
{
    printf("TestBigIntAssign:%d\n", n);
    BigInt a, b, c, d;
    clock_t beg = clock();
    for (int i = 0; i < n; ++i)
    {
        a = b = c = d;
    }
    clock_t end = clock();
    printf("use %f second(s).\n", 1.0 * (end - beg) / CLOCKS_PER_SEC);
}

void TestRCBigIntAssign(int n)
{
    printf("TestRCBigIntAssign:%d\n", n);
    RCBigInt a, b, c, d;
    clock_t beg = clock();
    for (int i = 0; i < n; ++i)
    {
        a = b = c = d;
    }
    clock_t end = clock();
    printf("use %f second(s).\n", 1.0 * (end - beg) / CLOCKS_PER_SEC);
}

int main()
{
    const int NUM = 1000000;

    TestBigIntCreate(NUM);
    TestRCBigIntCreate(NUM);
    TestBigIntAssign(NUM);
    TestRCBigIntAssign(NUM);

    return 0;
}

运行结果:

情况2的类设计图如下所示，

从图中可以看到，由于无法修改BigInt的实现，引入了一个新类CounterHolder作为引用计数的中间类。该类继承自RCObject，智能指针类RCIPtr包含一个CounterHolder的指针，而CounterHolder里面才包含一个BigInt的指针。
这就相当于多了一次间接操作，因此在RCIBigInt的创建和删除操作中会增加时间，这可以从运行结果中可以看到。

代码如下:

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>
#include <iostream>
using namespace std;

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;
    }

private:
    int refCount;
    bool shareable;
};

class BigInt
{
    friend BigInt operator+(const BigInt, const BigInt);
public:
    BigInt(const char*);
    BigInt(unsigned u = 0);
    BigInt(const BigInt);
    BigInt operator=(const BigInt);
    BigInt operator+=(const BigInt);
    ~BigInt()
    {
        delete [] digits;
    }

    char* getDigits() const
    {
        return digits;
    }
    unsigned getNdigits() const
    {
        return ndigits;
    }

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

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(unsigned u)
{
    unsigned v = u;

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

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::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;
        d = digits;
    }

    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]++;
        }
    }

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

    return *this;
}

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 BigInt operator+(const BigInt left, const BigInt right)
{
    return BigInt(left, right);
}

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

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

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

    return *this;
}

ostream operator<<(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 << endl;

    return os;
}

template <typename T> class RCIPtr
{
public:
    RCIPtr(T* realPtr = NULL) : counter(new CountHolder)
    {
        counter->pointee = realPtr;
        Init();
    }
    RCIPtr(const RCIPtr rhs) : counter(rhs.counter) { Init(); }
    ~RCIPtr() { if (counter) counter->removeReference(); }
    T* operator->() const { return counter->pointee; }
    T operator*() const { return *(counter->pointee); }
    RCIPtr operator=(const RCIPtr rhs);

private:
    struct CountHolder : public RCObject
    {
        ~CountHolder() { delete pointee; }
        T* pointee;
    };

    CountHolder* counter;
    void Init();
};

template <typename T> void RCIPtr<T>::Init()
{
    if (counter == 0) return;

    if (counter->isShareable() == false)
    {
        counter = new CountHolder;
        counter->pointee = new T(*counter->pointee);

    }
    counter->addReference();
}

template <typename T> RCIPtr<T> RCIPtr<T>::operator=(const RCIPtr rhs)
{
    if (counter != rhs.counter)
    {
        if (counter) counter->removeReference();
        counter = rhs.counter;
        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)) {}

private:
    RCIPtr<BigInt> value;
};

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

void TestBigIntCreate(int n)
{
    printf("TestBigIntCreate:%d\n", n);
    clock_t beg = clock();
    for (int i = 0; i < n; ++i)
    {
        BigInt a = i;
        BigInt b = i + 1;
        BigInt c = i + 2;
        BigInt d = i + 3;
    }
    clock_t end = clock();
    printf("use %f second(s).\n", 1.0 * (end - beg) / CLOCKS_PER_SEC);
}

void TestRCBigIntCreate(int n)
{
    printf("TestRCBigIntCreate:%d\n", n);
    clock_t beg = clock();
    for (int i = 0; i < n; ++i)
    {
        RCBigInt a = i;
        RCBigInt b = i + 1;
        RCBigInt c = i + 2;
        RCBigInt d = i + 3;
    }
    clock_t end = clock();
    printf("use %f second(s).\n", 1.0 * (end - beg) / CLOCKS_PER_SEC);
}

void TestBigIntAssign(int n)
{
    printf("TestBigIntAssign:%d\n", n);
    BigInt a, b, c, d;
    clock_t beg = clock();
    for (int i = 0; i < n; ++i)
    {
        a = b = c = d;
    }
    clock_t end = clock();
    printf("use %f second(s).\n", 1.0 * (end - beg) / CLOCKS_PER_SEC);
}

void TestRCBigIntAssign(int n)
{
    printf("TestRCBigIntAssign:%d\n", n);
    RCBigInt a, b, c, d;
    clock_t beg = clock();
    for (int i = 0; i < n; ++i)
    {
        a = b = c = d;
    }
    clock_t end = clock();
    printf("use %f second(s).\n", 1.0 * (end - beg) / CLOCKS_PER_SEC);
}

int main()
{
    const int NUM = 1000000;

    TestBigIntCreate(NUM);
    TestRCBigIntCreate(NUM);
    TestBigIntAssign(NUM);
    TestRCBigIntAssign(NUM);

    return 0;
}

运行结果：

最后给出的是多线程版本的代码，在Windows下可以用临界区或者互斥体实现。互斥体实现的版本比较慢，但是临界区的版本为什么在gcc的release版本中运行出现内存错误了，而debug版本中没有问题，在vc6下运行也没有问题。

临界区版本代码如下：

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>
#include <iostream>
#include <windows.h>
using namespace std;

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;
    }

private:
    int refCount;
    bool shareable;
};

class BigInt
{
    friend BigInt operator+(const BigInt, const BigInt);
public:
    BigInt(const char*);
    BigInt(unsigned u = 0);
    BigInt(const BigInt);
    BigInt operator=(const BigInt);
    BigInt operator+=(const BigInt);
    ~BigInt()
    {
        delete [] digits;
    }

    char* getDigits() const
    {
        return digits;
    }
    unsigned getNdigits() const
    {
        return ndigits;
    }

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

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(unsigned u)
{
    unsigned v = u;

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

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::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;
        d = digits;
    }

    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]++;
        }
    }

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

    return *this;
}

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 BigInt operator+(const BigInt left, const BigInt right)
{
    return BigInt(left, right);
}

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

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

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

    return *this;
}

ostream operator<<(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 << endl;

    return os;
}

class CriticalSectionLock
{
public:
    CriticalSectionLock()
    {
        InitializeCriticalSection(csMyCriticalSection);
    }
    ~CriticalSectionLock()
    {
        DeleteCriticalSection(csMyCriticalSection);
    }
    void lock()
    {
        EnterCriticalSection(csMyCriticalSection);
    }
    void unlock()
    {
        LeaveCriticalSection(csMyCriticalSection);
    }
private:
    CRITICAL_SECTION csMyCriticalSection;
};

template <typename T, typename LOCK> class RCIPtr
{
public:
    RCIPtr(T* realPtr = NULL) : counter(new CountHolder)
    {
        counter->pointee = realPtr;
        Init();
    }
    RCIPtr(const RCIPtr rhs) : counter(rhs.counter)
    {
        if (rhs.counter) rhs.counter->key.lock();
        Init();
        if (rhs.counter) rhs.counter->key.unlock();
    }
    ~RCIPtr()
    {
        if (counter)
        {
            counter->key.lock();
            counter->removeReference();
            counter->key.unlock();
        }
    }
    T* operator->() const { return counter->pointee; }
    T operator*() const { return *(counter->pointee); }
    RCIPtr operator=(const RCIPtr rhs);

private:
    struct CountHolder : public RCObject
    {
        ~CountHolder() { delete pointee; }
        T* pointee;
        LOCK key;
    };

    CountHolder* counter;
    void Init();
};

template <typename T, typename LOCK> void RCIPtr<T, LOCK>::Init()
{
    if (counter == 0) return;

    if (counter->isShareable() == false)
    {
        counter = new CountHolder;
        counter->pointee = new T(*counter->pointee);

    }
    counter->addReference();
}

template <typename T, typename LOCK>
RCIPtr<T, LOCK> RCIPtr<T, LOCK>::operator=(const RCIPtr rhs)
{
    if (counter != rhs.counter)
    {
        if (counter)
        {
            counter->key.lock();
            counter->removeReference();
            counter->key.unlock();
        }
        counter = rhs.counter;
        if (rhs.counter) rhs.counter->key.lock();
        Init();
        if (rhs.counter) rhs.counter->key.unlock();
    }

    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)) {}

private:
    RCIPtr<BigInt, CriticalSectionLock> value;
};

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

void TestBigIntCreate(int n)
{
    printf("TestBigIntCreate:%d\n", n);
    clock_t beg = clock();
    for (int i = 0; i < n; ++i)
    {
        BigInt a = i;
        BigInt b = i + 1;
        BigInt c = i + 2;
        BigInt d = i + 3;
    }
    clock_t end = clock();
    printf("use %f second(s).\n", 1.0 * (end - beg) / CLOCKS_PER_SEC);
}

void TestRCBigIntCreate(int n)
{
    printf("TestRCBigIntCreate:%d\n", n);
    clock_t beg = clock();
    for (int i = 0; i < n; ++i)
    {
        RCBigInt a = i;
        RCBigInt b = i + 1;
        RCBigInt c = i + 2;
        RCBigInt d = i + 3;
    }
    clock_t end = clock();
    printf("use %f second(s).\n", 1.0 * (end - beg) / CLOCKS_PER_SEC);
}

void TestBigIntAssign(int n)
{
    printf("TestBigIntAssign:%d\n", n);
    BigInt a, b, c, d;
    clock_t beg = clock();
    for (int i = 0; i < n; ++i)
    {
        a = b = c = d;
    }
    clock_t end = clock();
    printf("use %f second(s).\n", 1.0 * (end - beg) / CLOCKS_PER_SEC);
}

void TestRCBigIntAssign(int n)
{
    printf("TestRCBigIntAssign:%d\n", n);
    RCBigInt a, b, c, d;
    clock_t beg = clock();
    for (int i = 0; i < n; ++i)
    {
        a = b = c = d;
    }
    clock_t end = clock();
    printf("use %f second(s).\n", 1.0 * (end - beg) / CLOCKS_PER_SEC);
}

int main()
{
    const int NUM = 1000000;

    TestBigIntCreate(NUM);
    TestRCBigIntCreate(NUM);
    TestBigIntAssign(NUM);
    TestRCBigIntAssign(NUM);

    return 0;
}

在vc6下的运行结果,

从结果中可以看出RCIBigInt的赋值操作情况在性能上已经没有多少优势了，在vc6下反而更慢，这主要是因为线程同步操作的原因。

互斥体版本代码如下：

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>
#include <iostream>
#include <windows.h>
using namespace std;

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;
    }

private:
    int refCount;
    bool shareable;
};

class BigInt
{
    friend BigInt operator+(const BigInt, const BigInt);
public:
    BigInt(const char*);
    BigInt(unsigned u = 0);
    BigInt(const BigInt);
    BigInt operator=(const BigInt);
    BigInt operator+=(const BigInt);
    ~BigInt()
    {
        delete [] digits;
    }

    char* getDigits() const
    {
        return digits;
    }
    unsigned getNdigits() const
    {
        return ndigits;
    }

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

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(unsigned u)
{
    unsigned v = u;

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

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::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;
        d = digits;
    }

    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]++;
        }
    }

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

    return *this;
}

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 BigInt operator+(const BigInt left, const BigInt right)
{
    return BigInt(left, right);
}

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

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

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

    return *this;
}

ostream operator<<(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 << endl;

    return os;
}

class MutexLock
{
public:
    MutexLock()
    {
        hMutex = CreateMutex(NULL, FALSE, NULL);
    }
    ~MutexLock()
    {
        CloseHandle(hMutex);
    }
    void lock()
    {
        WaitForSingleObject(hMutex, INFINITE);
    }
    void unlock()
    {
        ReleaseMutex(hMutex);
    }
private:
    HANDLE hMutex;
};

template <typename T, typename LOCK> class RCIPtr
{
public:
    RCIPtr(T* realPtr = NULL) : counter(new CountHolder)
    {
        counter->pointee = realPtr;
        Init();
    }
    RCIPtr(const RCIPtr rhs) : counter(rhs.counter)
    {
        if (rhs.counter) rhs.counter->key.lock();
        Init();
        if (rhs.counter) rhs.counter->key.unlock();
    }
    ~RCIPtr()
    {
        if (counter)
        {
            counter->key.lock();
            counter->removeReference();
            counter->key.unlock();
        }
    }
    T* operator->() const { return counter->pointee; }
    T operator*() const { return *(counter->pointee); }
    RCIPtr operator=(const RCIPtr rhs);

private:
    struct CountHolder : public RCObject
    {
        ~CountHolder() { delete pointee; }
        T* pointee;
        LOCK key;
    };

    CountHolder* counter;
    void Init();
};

template <typename T, typename LOCK> void RCIPtr<T, LOCK>::Init()
{
    if (counter == 0) return;

    if (counter->isShareable() == false)
    {
        counter = new CountHolder;
        counter->pointee = new T(*counter->pointee);

    }
    counter->addReference();
}

template <typename T, typename LOCK>
RCIPtr<T, LOCK> RCIPtr<T, LOCK>::operator=(const RCIPtr rhs)
{
    if (counter != rhs.counter)
    {
        if (counter)
        {
            counter->key.lock();
            counter->removeReference();
            counter->key.unlock();
        }
        counter = rhs.counter;
        if (rhs.counter) rhs.counter->key.lock();
        Init();
        if (rhs.counter) rhs.counter->key.unlock();
    }

    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)) {}

private:
    RCIPtr<BigInt, MutexLock> value;
};

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

void TestBigIntCreate(int n)
{
    printf("TestBigIntCreate:%d\n", n);
    clock_t beg = clock();
    for (int i = 0; i < n; ++i)
    {
        BigInt a = i;
        BigInt b = i + 1;
        BigInt c = i + 2;
        BigInt d = i + 3;
    }
    clock_t end = clock();
    printf("use %f second(s).\n", 1.0 * (end - beg) / CLOCKS_PER_SEC);
}

void TestRCBigIntCreate(int n)
{
    printf("TestRCBigIntCreate:%d\n", n);
    clock_t beg = clock();
    for (int i = 0; i < n; ++i)
    {
        RCBigInt a = i;
        RCBigInt b = i + 1;
        RCBigInt c = i + 2;
        RCBigInt d = i + 3;
    }
    clock_t end = clock();
    printf("use %f second(s).\n", 1.0 * (end - beg) / CLOCKS_PER_SEC);
}

void TestBigIntAssign(int n)
{
    printf("TestBigIntAssign:%d\n", n);
    BigInt a, b, c, d;
    clock_t beg = clock();
    for (int i = 0; i < n; ++i)
    {
        a = b = c = d;
    }
    clock_t end = clock();
    printf("use %f second(s).\n", 1.0 * (end - beg) / CLOCKS_PER_SEC);
}

void TestRCBigIntAssign(int n)
{
    printf("TestRCBigIntAssign:%d\n", n);
    RCBigInt a, b, c, d;
    clock_t beg = clock();
    for (int i = 0; i < n; ++i)
    {
        a = b = c = d;
    }
    clock_t end = clock();
    printf("use %f second(s).\n", 1.0 * (end - beg) / CLOCKS_PER_SEC);
}

int main()
{
    const int NUM = 1000000;

    TestBigIntCreate(NUM);
    TestRCBigIntCreate(NUM);
    TestBigIntAssign(NUM);
    TestRCBigIntAssign(NUM);

    return 0;
}

在codeblocks配gcc的环境下的运行结果，

从图里面还是能看到，在Windows下用互斥体同步确实比较慢。

使用STL容器的一些常识

发表于 2012-11-28 分类于编程语言， C++ ， STL 阅读次数： Valine：
本文字数： 1.3k 阅读时长 ≈ 1 分钟

stl这种东西这几年确实用得不少了，大一暑假刚开始看c++primer的时候就知道有这么个东西，当时觉得非常神奇的样子。不过，我用stl最多的地方还是在做acm的一些题目的时候。很多时候为了方便，为了代码简洁性就用stl了。我还是比较喜欢stl这个东西的。

我只打算讲点简单的东西。比如大致的实现原理和使用的一些注意情况，另外讲下我对迭代器失效的理解。

vector是一个动态数组，既然是数组，那么在末尾增加和删除是很快的，复杂度是O(1)。但是，在其它位置增加和删除复杂度就跟位置有关系了，复杂度是O(n)。默认情况对vector的查找是不会应用二分的，所以你用stl里面的find查找复杂度也是O(n)。当vector的容量大小需要经常改变时候，你可以预估计容量的最大大小，然后调用reserve函数预分配一块大内存，这样就可以避免频繁的内存分配释放造成的性能损失了。

deque类似于vector。但是在头部增加和删除复杂度也是O(1)，不过我没看过stl的实现，也不知道为什么。

list的内部实现大概是双向链表。那么在任意位置的插入和删除复制度都是O(1)。对于查找的话，虽然理论复杂度也是O(n)。不过，list的查找肯定会比vector慢的，因为多了一次取地址的间接操作。而且，数组因为地址是连续的，可以来个地址的缓存。

set和map内部是用红黑树实现的。红黑树也就是一棵平衡查找树吧，大家都学过二叉平衡树，红黑树大概类似这种东西。算法导论里面有对红黑树的详细介绍，不过看得让我很头晕，而且我也不想去实现一个红黑树，光是二叉平衡树的旋转已经很无语了。反正红黑树类似二叉平衡查找树就行了。那么，红黑树的插入删除都可能改变原有结点的位置之间的关系，意思是不仅仅是破坏或者增加一个结点的位置。但是原有结点的地址肯定是没有变化的。增删查改的复杂度都是log(n)。还有，对set和map的查找要应用容器内部的成员函数find，而不是全局的stl函数find。前者是二分查找，而后者是顺序查找。

下面我讲讲我对stl迭代器失效的理解。其实，大致知道了stl容器的实现，这个问题就很好理解了。

vector是动态数组，那么插入和删除元素都会改变该元素后面元素的地址，那么先前获取的指向后面位置元素的迭代器就会失效了。而且即使你插入在最后，也可能使所有的迭代器失效，因为可能这个时候刚好vector必须增加容量来容纳你新插入的元素了。你再访问这些迭代器的话，不是访问到错误的内容就是内存错误了。

list的话，由于结点是孤立的，是用指针把所有结点串起来的，那么原有结点的地址一直都不会改变。只要不对结点进行了删除，那么原来获取的迭代器就不会失效。但是，++和—的结果可能会和原来不一致的。

deque类似于vector吧。不过，我还是不是很清楚。

set和map的话，类似于list。它们的结点地址也一直不会变化，但是插入和删除会改变整棵树的布局，所以原来的迭代器++或者—之后可能就会指向乱七八糟的东西了。但是，你获取原来的元素还是可以的。

总之，对容器进行插入和删除之后一定要注意迭代器失效的情况，最好是从写法上避免这种可能性吧，而不是利用迭代器不失效的可能性。

关于函数内联的一些理解

发表于 2012-11-22 分类于编程语言， C++ 阅读次数： Valine：
本文字数： 1.7k 阅读时长 ≈ 2 分钟

最近在看提高C++性能的编程技术一书，居然发现里面有三章是专门讲述内联的。看来内联在作者心中占据了非常重要的位置，内联在作者心里是最有效的改进性能的策略了。

阅读完这三章内容之后，我对内联的理解更加模糊了。因为到最后作者也说你内联性能不一定变好，你不内联性能也不一定变坏。能跟内联牵扯上关系的东西太多了。

我记得有人曾经问过我这个问题，内联和宏替换的区别是什么。当时我还是大三的时候，准备找个实习，是电面的时候被别人问到的。还是国内著名的IT企业，我就这样的水水的跟人家乱扯。现在回忆起来我好像什么也没说出来的样子。说实话，我那个时候感觉内联和宏替换区别不大，一样的对待也没什么大不了的。第三次电面的时候我就彻底悲剧了，最主要的原因还是因为C++功底不扎实。想想那个时候也挺可爱的，把简历写的那么好笑那么烂，他们居然也给我机会进到最后一轮。最后一轮我实在表现的太烂了。

那么区别到底是什么了。我说说现在的理解吧。首先，宏替换不能算编译器的时候，应该算预处理器的工作，而内联属于编译器的工作，阶段都不同了。其次，宏替换很白痴就是简单的应用些规则进行代码替换而已，而内联是很高级的功能吧，inline只是对编译器的指示，内联不内联是编译器自己的决定，有可能你不写inline函数也被内联了，不过我觉得可能性比较小，而且内联不仅仅是在调用位置替换上被调用函数的代码，编译器还会对替换之后的新代码整个进行优化，也就是能够跨越函数调用进行优化，这一点据说是内联提高性能的关键。最后，宏的可读性很差，什么机制都没有，而内联就不同，函数还是函数，参数和返回类型，编译器对函数的检查等等都还在，而宏就没有这些优待。我能说出来的也就这么些了。。。

关于什么是内联的话应该就不需要我进行解释了。内联能避免函数调用的代价这一点也不需要解释了。函数调用的代价说简单点就是保存现场，主要是一些寄存器的内容，一般会把这些寄存器的内容压栈保存起来，还有就是传递参数，参数的传递是通过改变堆栈指针达到的。函数调用完成之后还需要恢复现场，就是从栈里面恢复一些寄存器的内容，还有恢复原来的栈指针。但是，具体起来函数调用需要做些什么还是比较难说清楚的，不同的体系结构做的事情都不一样，再说写c++代码的时候谁又想过多的考虑底层具体发生了什么了。

那么来思考下为什么要使用内联和为什么又不要使用内联吧。大家都知道函数调用会造成一定的代价，既然内联可以避免这个代价那么为什么我们不用内联了。好吧，那么我们就用内联把函数调用的代价消去。那么为什么我们只内联比较小的函数了，而超过一定规模的函数就不内联了。首先，如果一个函数规模较大，那么函数调用的代价在整个代价里面的比例就较小了。其次，内联较大规模的函数会造成编译后的二进制代码增大，如果函数非叶子位置函数(只会被别的函数调用的函数)那么这个可能性更大，很可能就会到达无法忍受的地步，内联造成编译时间变长也是一方面。最后，内联也会损失某种性能，比如缓存和页交换之类的，如果是函数调用，机器可以运用指令和数据缓存之类的，但是如果是内联，那么不同的调用位置其在映像里面的位置是不一样的，那么机器是不会缓存的。所以，内联也不是能随便用的。

其实说了这么多了，我们还是不知道什么时候该内联什么时候不该内联。我们只了解到，如果函数足够小就内联吧，那么小的标准是什么，代码五行以内没有循环？什么时候不该内联，函数规模太大了？反正内联是一件太纠结的事情了，有可能你用编译器测试一下内联和不内联性能是没有变化的，因为可能编译器在幕后就内联了。

根据我所看的这本书的说法，我有一些建议。对少于五行的代码和调用频率大于80%的函数一定内联，其余的你还是仔细考虑下吧。你可以再分解调用频率大于80%的函数，使其规模变小，然后再考虑是否内联它。其实，这本书的思想还是对整个系统进行测试之后才进行内联选择，毕竟性能优化也是最后阶段的事情。你需要找出系统执行的关键路径，其实也就是执行频率最高的一些函数，根据整个系统的流程图，你就会发现一条系统执行频率最高的路径，内联应该只发生在这条路径上面。

好了，这就是我对内联的一些理解，这本书关于内联的内容实在太多了，我觉得还是下次再写一篇文章扯扯吧。

多线程内存池

发表于 2012-11-19 分类于编程语言， C++ 阅读次数： Valine：
本文字数： 8k 阅读时长 ≈ 7 分钟

如果一个内存池需要线程同步了，估计和默认的内存操作也差不了多远了。现在对内存操作的优化只是在优化线程同步操作上面了。默认的lock和unlock可能实现得过于完美，因而要求更多的cpu周期。如果选择更原子的lock和unlock实现，还是可以加快内存操作的速度的。

多线程内存池在实现上也就是在申请和释放外面包裹了一对加锁和解锁操作而已。

如果我们采用模板编程，就可以实现一个功能强悍的模板类，该模板类有两个参数，单线程内存池和锁。这样的话，可以组合出很多情况。比如说，单线程内存池有对象大小固定和不固定两种实现，锁在Windows下可以用临界区，互斥体，信号量，事件实现。这样最多可以组合出8种不同的实例化。

一般说来互斥体比临界区慢很多，在这里可以进行很好的测试。我实现了临界区和互斥体版本的锁，经过测试发现前者比后者快30多倍。因为互斥体据说是内核对象，而临界区是用户态对象，那么互斥体的使用就需要系统在用户态和内核态之间进行切换，肯定会消耗更多的时间。

互斥体版本代码如下，

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <windows.h>

template <typename T> class MemoryPool
{
public:
    MemoryPool(size_t size = EXPANSION_SIZE)
    {
        expandTheFreeList(size);
    }
    ~MemoryPool();
    //allocate a T element from the free list.
    void* alloc(size_t size)
    {
        if (next == NULL)
        {
            expandTheFreeList();
        }
        MemoryPool<T>* head = next;
        next = head->next;
        return head;
    }
    //return a T element to the free list.
    void free(void* doomed)
    {
        MemoryPool<T>* head = static_cast< MemoryPool<T>* > (doomed);
        head->next = next;
        next = head;
    }

private:
    //next element on the free list.
    MemoryPool<T>* next;
    //if the freelist is empty, expand it by this amount.
    enum {EXPANSION_SIZE = 32};
    //add free elements to the free list
    void expandTheFreeList(int howMany = EXPANSION_SIZE);
};

template <typename T> MemoryPool<T> :: ~MemoryPool()
{
    MemoryPool<T>* nextPtr = NULL;
    while (nextPtr)
    {
        nextPtr = next;
        next = next->next;
        delete [] nextPtr;
    }
}

template <typename T> void MemoryPool<T> :: expandTheFreeList(int howMany)
{
    //we must allocate an object enough to contain the next pointer
    size_t size = sizeof(T) > sizeof(MemoryPool<T>*) ? sizeof(T) :
                  sizeof(MemoryPool<T>*);

    MemoryPool<T>* runner = (MemoryPool<T>*) new char[size];
    next = runner;
    for (int i = 0; i < howMany; ++i)
    {
        runner->next = (MemoryPool<T>*) new char[size];
        runner = runner->next;
    }
    runner->next = NULL;
}

class ABClock //abstract base class
{
public:
    virtual ~ABClock() {}
    virtual void lock() = 0;
    virtual void unlock() = 0;
};

class MutexLock : public ABClock
{
public:
    MutexLock()
    {
        hMutex = CreateMutex(NULL, FALSE, NULL);
    }
    ~MutexLock()
    {
        CloseHandle(hMutex);
    }
    void lock()
    {
        WaitForSingleObject(hMutex, INFINITE);
    }
    void unlock()
    {
        ReleaseMutex(hMutex);
    }
private:
    HANDLE hMutex;
};

template <typename POOLTYPE, typename LOCK>
class MTMemoryPool
{
public:
    //allocate an element from the freelist.
    void* alloc(size_t size)
    {
        void* mem;
        theLock.lock();
        mem = stPool.alloc(size);
        theLock.unlock();
        return mem;
    }

    //return an element to the freelist
    void free(void* someElement)
    {
        theLock.lock();
        stPool.free(someElement);
        theLock.unlock();
    }

private:
    POOLTYPE stPool;//Single-threaded pool.
    LOCK theLock;
};

class Rational
{
public:
    Rational(int a = 0, int b = 1) : n(a), d(b) {}
    void* operator new(size_t size)
    {
        return memPool->alloc(size);
    }
    void operator delete(void* doomed, size_t size)
    {
        memPool->free(doomed);
    }
    static void newMemPool()
    {
        memPool = new MTMemoryPool< MemoryPool<Rational>, MutexLock>;
    }
    static void deleteMemPool()
    {
        delete memPool;
    }

private:
    int n;
    int d;
    static MTMemoryPool< MemoryPool<Rational>, MutexLock>* memPool;
};
MTMemoryPool< MemoryPool<Rational>, MutexLock>* Rational::memPool = NULL;

int main()
{
    const int ARRAY_SIZE = 1000;
    const int LOOP_TIMES = 5000;

    Rational* array[ARRAY_SIZE];
    clock_t beg = clock();
    Rational::newMemPool();
    for (int i = 0; i < LOOP_TIMES; ++i)
    {
        for (int j = 0; j < ARRAY_SIZE; ++j)
        {
            array[j] = new Rational(j);
        }
        for (int j = 0; j < ARRAY_SIZE; ++j)
        {
            delete array[j];
        }
    }
    clock_t end = clock();
    printf("use %f second(s).\n", 1.0 * (end - beg) / CLOCKS_PER_SEC);
    system("pause");
    Rational::deleteMemPool();

    return 0;
}

运行结果，

临界区版本代码如下，

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <windows.h>

template <typename T> class MemoryPool
{
public:
    MemoryPool(size_t size = EXPANSION_SIZE)
    {
        expandTheFreeList(size);
    }
    ~MemoryPool();
    //allocate a T element from the free list.
    void* alloc(size_t size)
    {
        if (next == NULL)
        {
            expandTheFreeList();
        }
        MemoryPool<T>* head = next;
        next = head->next;
        return head;
    }
    //return a T element to the free list.
    void free(void* doomed)
    {
        MemoryPool<T>* head = static_cast< MemoryPool<T>* > (doomed);
        head->next = next;
        next = head;
    }

private:
    //next element on the free list.
    MemoryPool<T>* next;
    //if the freelist is empty, expand it by this amount.
    enum {EXPANSION_SIZE = 32};
    //add free elements to the free list
    void expandTheFreeList(int howMany = EXPANSION_SIZE);
};

template <typename T> MemoryPool<T> :: ~MemoryPool()
{
    MemoryPool<T>* nextPtr = NULL;
    while (nextPtr)
    {
        nextPtr = next;
        next = next->next;
        delete [] nextPtr;
    }
}

template <typename T> void MemoryPool<T> :: expandTheFreeList(int howMany)
{
    //we must allocate an object enough to contain the next pointer
    size_t size = sizeof(T) > sizeof(MemoryPool<T>*) ? sizeof(T) :
                  sizeof(MemoryPool<T>*);

    MemoryPool<T>* runner = (MemoryPool<T>*) new char[size];
    next = runner;
    for (int i = 0; i < howMany; ++i)
    {
        runner->next = (MemoryPool<T>*) new char[size];
        runner = runner->next;
    }
    runner->next = NULL;
}

class ABClock //abstract base class
{
public:
    virtual ~ABClock() {}
    virtual void lock() = 0;
    virtual void unlock() = 0;
};

class CriticalSectionLock : public ABClock
{
public:
    CriticalSectionLock()
    {
        InitializeCriticalSection(csMyCriticalSection);
    }
    ~CriticalSectionLock()
    {
        DeleteCriticalSection(csMyCriticalSection);
    }
    void lock()
    {
        EnterCriticalSection(csMyCriticalSection);
    }
    void unlock()
    {
        LeaveCriticalSection(csMyCriticalSection);
    }
private:
    CRITICAL_SECTION csMyCriticalSection;
};

template <typename POOLTYPE, typename LOCK>
class MTMemoryPool
{
public:
    //allocate an element from the freelist.
    void* alloc(size_t size)
    {
        void* mem;
        theLock.lock();
        mem = stPool.alloc(size);
        theLock.unlock();
        return mem;
    }

    //return an element to the freelist
    void free(void* someElement)
    {
        theLock.lock();
        stPool.free(someElement);
        theLock.unlock();
    }

private:
    POOLTYPE stPool;//Single-threaded pool.
    LOCK theLock;
};

class Rational
{
public:
    Rational(int a = 0, int b = 1) : n(a), d(b) {}
    void* operator new(size_t size)
    {
        return memPool->alloc(size);
    }
    void operator delete(void* doomed, size_t size)
    {
        memPool->free(doomed);
    }
    static void newMemPool()
    {
        memPool = new MTMemoryPool< MemoryPool<Rational>, CriticalSectionLock>;
    }
    static void deleteMemPool()
    {
        delete memPool;
    }

private:
    int n;
    int d;
    static MTMemoryPool< MemoryPool<Rational>, CriticalSectionLock>* memPool;
};
MTMemoryPool< MemoryPool<Rational>, CriticalSectionLock>* Rational::memPool = NULL;

int main()
{
    const int ARRAY_SIZE = 1000;
    const int LOOP_TIMES = 5000;

    Rational* array[ARRAY_SIZE];
    clock_t beg = clock();
    Rational::newMemPool();
    for (int i = 0; i < LOOP_TIMES; ++i)
    {
        for (int j = 0; j < ARRAY_SIZE; ++j)
        {
            array[j] = new Rational(j);
        }
        for (int j = 0; j < ARRAY_SIZE; ++j)
        {
            delete array[j];
        }
    }
    clock_t end = clock();
    printf("use %f second(s).\n", 1.0 * (end - beg) / CLOCKS_PER_SEC);
    system("pause");
    Rational::deleteMemPool();

    return 0;
}

运行结果，

两个版本的代码只在线程同步锁的实现上有差别，但是速度却相差了30多倍。

单线程环境中对象大小可变的内存池

发表于 2012-11-18 分类于编程语言， C++ 阅读次数： Valine：
本文字数： 3.5k 阅读时长 ≈ 3 分钟

很多系统中申请的内存大小都不是固定的，而是变化的，比如一个http服务器。http服务器获得的请求不同，不同的请求需要不同大小的内存块。那么如何构造一个可以申请不同大小内存的内存池了。其实，构造方法类似vs2008下面的debug模式中的全局new和delete的实现。思路大致是申请很多不同大小的内存块，链接起来，根据需求从内存块链的头部申请指定大小内存。
注意，本文代码中的内存池只在内存块链的头部申请内存，而且从不进行内存释放，一直到内存池使用完毕。这样的设计确实可以尽可能得提高全局的速度，只要能保证系统的使用过程中不会把内存耗光就行了。不过，我觉得如果耗光内存的可能性还是太大了。但是，你想想实现一个允许对象大小可变的内存池本来就不那么容易，而且得在充分考虑效率的前提下了。如果效率太差了，为什么不直接使用默认的new和delete表达式了。
不过，其实有一个更好的办法，我们只使用内存池一段时间，就马上删除这个内存池，再重新申请一次内存池。也就是我们不能一次使用内存池的时间太长了。困难的是我们如何确定一次使用内存池的时间，什么需要删除内存池，时间太久了也许内存会耗光的，删除频繁了点又得不到想要的效率。这些也许就需要具体情况具体对待了，也许这个内存池的实现根本不能用。

内存池代码如下，

#include <stdio.h>
#include <time.h>
#include <stdlib.h>

class MemoryChunk
{
public:
    MemoryChunk(MemoryChunk* nextChunk, size_t reqSize)
    {
        chunkSize = reqSize > DEFAULT_CHUNK_SIZE ? reqSize :
                    DEFAULT_CHUNK_SIZE;
        next = nextChunk;
        byteAlreadyAllocated = 0;
        mem = new char[chunkSize];
    }

    ~MemoryChunk()
    {
        delete [] mem;
    }

    void* alloc(size_t size)
    {
        void* addr = (void*)(mem + byteAlreadyAllocated);
        byteAlreadyAllocated += size;
        return addr;
    }

    //不需要释放内存块
    void free(void* doomed)
    {

    }

    MemoryChunk* nextMemChunk() { return next; }
    size_t spaceAvailable()
    {
        return chunkSize - byteAlreadyAllocated;
    }
    enum {DEFAULT_CHUNK_SIZE = 4096};
private:
    MemoryChunk* next;//下一个内存块
    char* mem;//该内存块地址
    size_t chunkSize; //该内存块的大小
    size_t byteAlreadyAllocated;//该内存块被申请使用的大小
};

class ByteMemoryPool
{
public:
    ByteMemoryPool(size_t initSize = MemoryChunk::DEFAULT_CHUNK_SIZE)
    {
        expandStorage(initSize);
    }
    ~ByteMemoryPool();

    void* alloc(size_t reqSize)
    {
        size_t space = listOfMemoryChunks->spaceAvailable();
        if (space < reqSize)
        {
            expandStorage(reqSize);
        }
        return listOfMemoryChunks->alloc(reqSize);
    }

    void free(void* doomed)
    {
        listOfMemoryChunks->free(doomed);
    }

private:
    void expandStorage(size_t reqSize)
    {
        listOfMemoryChunks = new MemoryChunk(listOfMemoryChunks, reqSize);
    }
    MemoryChunk* listOfMemoryChunks;
};

ByteMemoryPool::~ByteMemoryPool()
{
    MemoryChunk* memChunk = listOfMemoryChunks;
    while (memChunk)
    {
        listOfMemoryChunks = memChunk->nextMemChunk();
        delete memChunk;
        memChunk = listOfMemoryChunks;
    }
}

class Rational
{
public:
    Rational(int a = 0, int b = 1) : n(a), d(b) {}
    void* operator new(size_t size) {return memPool->alloc(size);}
    void operator delete(void* doomed, size_t size) {/*memPool->free(doomed);*/}
    static void newMemPool() {memPool = new ByteMemoryPool;}
    static void deleteMemPool() {delete memPool;}

private:
    int n;
    int d;
    static ByteMemoryPool* memPool;
};
ByteMemoryPool* Rational::memPool = NULL;

int main()
{
    const int ARRAY_SIZE = 1000;
    const int LOOP_TIMES = 5000;

    Rational* array[ARRAY_SIZE];
    clock_t beg = clock();
    Rational::newMemPool();
    for (int i = 0; i < LOOP_TIMES; ++i)
    {
        for (int j = 0; j < ARRAY_SIZE; ++j)
        {
            array[j] = new Rational(j);
        }
        for (int j = 0; j < ARRAY_SIZE; ++j)
        {
            delete array[j];
        }
    }
    clock_t end = clock();
    printf("use %f second(s).\n", 1.0 * (end - beg) / CLOCKS_PER_SEC);
    system("pause");
    Rational::deleteMemPool();

    return 0;
}

运行效果，
与上一篇文章里面的二个内存池实现的运行时间相比，没有多大差别。

你可以好好的阅读下代码，或者自己重新敲一遍，就会发现这个内存池的实现确实简单明了，没有一点冗余的代码，但是又非常高效。如果我们采用使用一段时间就重新初始化内存池的方式就不会耗光内存，不过恰当的使用该内存池也不是件容易的事情。其实，我主要还是觉得这个版本的内存池实现主要应该用在一次的业务处理时间不会太长，或者说内存申请量不会太多的场景中。

本文的思路和代码主要来自提高C++性能的编程技术一书。

单线程环境中对象大小固定的内存池

发表于 2012-11-15 分类于编程语言， C++ 阅读次数： Valine：
本文字数： 5.9k 阅读时长 ≈ 5 分钟

内存池并不是表面意义上存储大量可分配内存的池子，如果是这样的话，new和delete对应的就是一个理论上无限大的内存池。标题中的单线程指的是该内存池实现为了加快速度没有处理线程同步，因为很多应用你明显知道不需要线程同步。固定大小指的是该内存池每次只分配或者删除固定大小的对象。

这样的内存池怎么就加快了速度了。我觉得主要有以下几个方面。

1.不需要处理线程同步，去除掉线程同步的代码后，显然速度会加快。

2.总体来看，该内存池只会扩张不会收缩，也就是向系统释放堆内存的次数减少了。事实上，该内存池总是按需操作的。

3.该内存池的new和delete操作并没有去真正申请和释放堆内存，而是向自定义的对象空闲列表申请和释放。当对象空闲列表为空的时候，才一次性申请一大片空闲对象。大家都知道堆申请和释放比较耗时，最快的栈内存。所以，这也是一个显著的方面。

以下2段代码分别展示了原始的内存操作和使用内存池后的操作，

原始情况，

#include
#include
#include

class Rational
{
public:
    Rational(int a = 0, int b = 1) : n(a), d(b) {}

private:
    int n; // Numerator
    int d; // Denominator
};

int main()
{
    const int ARRAY_SIZE = 1000;
    const int LOOP_TIMES = 5000;
    Rational* array[ARRAY_SIZE];

    clock_t beg = clock();
    for (int i = 0; i < LOOP_TIMES; ++i)
    {
        for (int j = 0; j < ARRAY_SIZE; ++j)
        {
            array[j] = new Rational(j);
        }
        for (int j = 0; j < ARRAY_SIZE; ++j)
        {
            delete array[j];
        }
    }
    clock_t end = clock();
    printf("use %f second(s).\n", 1.0 * (end - beg) / CLOCKS_PER_SEC);
    system("pause");

    return 0;
}

该代码的运行结果，

内存池，

#include <stdio.h>
#include <time.h>
#include <stdlib.h>

struct NextOnFreeList
{
    NextOnFreeList* next;
};

class Rational
{
public:
    Rational(int a = 0, int b = 1) : n(a), d(b) {}

    void* operator new(size_t size)
    {
        if (freeList == 0)// if the list is empty, fill it up.
        {
            expandTheFreeList();
        }

        NextOnFreeList* head = freeList;
        freeList = head->next;
        return head;
    }

    void operator delete(void* doomed, size_t size)
    {
        NextOnFreeList* head = static_cast<NextOnFreeList*> (doomed);
        head->next = freeList;
        freeList = head;
    }
    static void newMemPool()
    {
        expandTheFreeList();
    }
    static void deleteMemPool();

private:
    static void expandTheFreeList();
    static NextOnFreeList* freeList;
    enum { EXPANSION_SIZE = 32 };
    int n; // Numerator
    int d; // Denominator
};

NextOnFreeList* Rational::freeList = NULL;

//当空闲列表里面没有对象时，该函数才会被调用
void Rational::expandTheFreeList()
{
    size_t size = sizeof(Rational) > sizeof(NextOnFreeList*) ?
                  sizeof(Rational) : sizeof(NextOnFreeList*);
    NextOnFreeList* runner = (NextOnFreeList*)new char[size];
    freeList = runner;
    for (int i = 0; i < EXPANSION_SIZE; ++i)
    {
        runner->next = (NextOnFreeList*)new char[size];
        runner = runner->next;
    }
    runner->next = 0;
}

void Rational::deleteMemPool()
{
    NextOnFreeList* nextPtr = freeList;
    while (nextPtr)
    {
        freeList = nextPtr->next;
        delete [] nextPtr;
        nextPtr = freeList;
    }
}

int main()
{
    const int ARRAY_SIZE = 1000;
    const int LOOP_TIMES = 5000;
    Rational* array[ARRAY_SIZE];

    clock_t beg = clock();
    Rational::newMemPool();
    for (int i = 0; i < LOOP_TIMES; ++i)
    {
        for (int j = 0; j < ARRAY_SIZE; ++j)
        {
            array[j] = new Rational(j);
        }
        for (int j = 0; j < ARRAY_SIZE; ++j)
        {
            delete array[j];
        }
    }
    clock_t end = clock();
    printf("use %f second(s).\n", 1.0 * (end - beg) / CLOCKS_PER_SEC);
    system("pause");
    Rational::deleteMemPool();

    return 0;
}

该代码运行结果，

通过以上结果的对比可以看到时间比例为921/78，直接就快了10多倍。而且我们的内存申请和删除操作还不够频繁，如果再更频繁的场合，效率上面的提示会更加大。

下面我们来分析一下内存池实现的代码。

说来也比较简单，因为原理都已经讲清楚了。首先去除了线程同步代码，然后把内存放在对象空闲列表里面，从里面释放和删除对象，当对象空闲列表为空的时候，一次性申请一片对象。作为一个有经验的c++程序员这些代码已经足够简单了。需要注意的是，在expandTheFreeList函数里面，申请新对象的时候，需要注意大小必须是Rational和NextOnFreeList*中大小大的一个。该内存池还用到了指针类型强转，语法上面还是比较巧妙的。

由于该内存池只是针对单个的类，应用场合未免有点限制。如果我们用泛型编程实现内存池，就可以把应用场合推广了。下面将内存池的功能独立出来，用模板重新实现了下，代码如下：

#include
#include
#include

template  class MemoryPool
{
public:
    MemoryPool(size_t size = EXPANSION_SIZE)
    {
        expandTheFreeList(size);
    }
    ~MemoryPool();
    //allocate a T element from the free list.
    void* alloc(size_t size)
    {
        if (next == NULL)
        {
            expandTheFreeList();
        }
        MemoryPool* head = next;
        next = head->next;
        return head;
    }
    //return a T element to the free list.
    void free(void* doomed)
    {
        MemoryPool* head = static_cast< MemoryPool* > (doomed);
        head->next = next;
        next = head;
    }

private:
    //next element on the free list.
    MemoryPool* next;
    //if the freelist is empty, expand it by this amount.
    enum {EXPANSION_SIZE = 32};
    //add free elements to the free list
    void expandTheFreeList(int howMany = EXPANSION_SIZE);
};

template  MemoryPool :: ~MemoryPool()
{
    MemoryPool* nextPtr = NULL;
    while (nextPtr)
    {
        nextPtr = next;
        next = next->next;
        delete [] nextPtr;
    }
}

template  void MemoryPool :: expandTheFreeList(int howMany)
{
    //we must allocate an object enough to contain the next pointer
    size_t size = sizeof(T) > sizeof(MemoryPool*) ? sizeof(T) :
                  sizeof(MemoryPool*);

    MemoryPool* runner = (MemoryPool*) new char[size];
    next = runner;
    for (int i = 0; i < howMany; ++i)     {         runner->next = (MemoryPool*) new char[size];
        runner = runner->next;
    }
    runner->next = NULL;
}

class Rational
{
public:
    Rational(int a = 0, int b = 1) : n(a), d(b) {}
    void* operator new(size_t size) {return memPool->alloc(size);}
    void operator delete(void* doomed, size_t size) {memPool->free(doomed);}
    static void newMemPool() {memPool = new MemoryPool;}
    static void deleteMemPool() {delete memPool;}

private:
    int n;
    int d;
    static MemoryPool* memPool;
};
MemoryPool* Rational::memPool = NULL;

int main()
{
    const int ARRAY_SIZE = 1000;
    const int LOOP_TIMES = 5000;
    Rational* array[ARRAY_SIZE];

    clock_t beg = clock();
    Rational::newMemPool();
    for (int i = 0; i < LOOP_TIMES; ++i)
    {
        for (int j = 0; j < ARRAY_SIZE; ++j)
        {
            array[j] = new Rational(j);
        }
        for (int j = 0; j < ARRAY_SIZE; ++j)
        {
            delete array[j];
        }
    }
    clock_t end = clock();
    printf("use %f second(s).\n", 1.0 * (end - beg) / CLOCKS_PER_SEC);
    system("pause");
    Rational::deleteMemPool();

    return 0;
}

运行效果如图：

可以看到用模板重新实现后，速度并没有下降多少，这个例子速度下降近一倍的原因估计是与原来的实现相比多了一些函数调用吧，但是还是比不使用内存池的情况下快一个数量级。

整个代码的思路是把内存池的实现部分用一个模板类包含了，用不同的类实例化模板类，就可以对不同的类使用内存池了，泛型编程在速度和灵活性上面的结合确实是非常优美的。而且你可以看到，例子二和例子三的主函数部分完全一致，也就是保持了外部接口的统一性，只需要修改类Rational的实现即可。现在将内存池应用到不同的类也只需要在类里面添加一个针对该类的泛型内存池成员而已。

虚函数所造成的性能损失

发表于 2012-11-13 分类于编程语言， C++ 阅读次数： Valine：
本文字数： 947 阅读时长 ≈ 1 分钟

假设在一个线程同步环境中，有类似下面所示的代码段：

//进入线程同步

nNum++;

//退出线程同步

以win32为例，如我们所知，线程同步工具有临界区，互斥体，信号量。我们可以任意选择一个，为了简单很可能我们就选择了临界区。假如我们需要同步的代码非常简单，我非常建议不需要使用c++的任何功能。但是，很可能没这么幸运，很可能你的代码会被很多人修改，很可能同步的时候需要异常退出，很可能同步的里面还有点逻辑处理，很可能你在退出的时候没有释放锁。那么你就悲剧了。

C++在这里一点上就体现出了与生俱来的优势，构造函数和析构函数。假如我们把获得锁写进构造函数里面，释放锁写进析构函数里面，就能保证任意情况的退出之前都能够释放锁，从而不会造成死锁。

还有个问题是我们应该如何实现这些不同的同步工具。如果，我们分别写三个类，CCriticalSection，CMutex，CSemaphore，这三个类不是继承自同一个基类的，而且这三个类里面也没有任何的虚函数，而且我们把操作都写成内联的。那么，在效率上与直接用C相比基本没有差别。因为，所有额外的调用开销都内联了。在不丧失效率的同时保持了灵活性，这确实是非常强大的地方。

万一你说为了灵活性，需要让这三个类继承同一个基类，CBaseLock，同时需要把析构函数定义成虚的，这样就会造成很多额外的性能损失。比如，可能需要构造和析构基类对象，需要初始化虚函数指针，执行阶段需要通过虚函数指针间接调用，还有一个最重要的损失，编译器无法内联虚函数，如果虚函数比较小，那么相对于原来的情况，这是一个巨大的性能损失。某种意义上，我们可以忽视，基类对象的构造和析构，以及虚函数指针的初始化和调用时刻的间接寻址，因为这些可以其它方面的因素来抵消。

但是，无法内联一个小的函数所造成的额外开销是很大的。想象一下，比如刚才几个类里面的析构函数只是释放锁这一个操作，肯定是可以内联的，但是现在写成虚函数了，就无法内联了，如果这个函数被调用很多次，比如几百万次，和原来消耗的时候相比，肯定是天壤之别了，因为原来没有函数调用开销，现在有，而且因为函数内部操作太少了，函数调用开销所占据的比例非常大，所以你的设计造成了巨大的性能损失。

本文的观点主要来自提高C++性能的编程技术一书，欢迎吐槽。

计算机图形学OpenGL版第五章代码汇总

发表于 2012-11-12 分类于图形学， OpenGL 阅读次数： Valine：
本文字数： 6.8k 阅读时长 ≈ 6 分钟

5.6.2 网格场景

#include <windows.h>
#include <gl/gl.h>
#include <gl/glu.h>
#include <gl/glut.h>
#pragma comment(linker, "/subsystem:\"windows\" /entry:\"mainCRTStartup\"")

const int WINDOW_WIDTH = 640;
const int WINDOW_HEIGHT = 480;
const int WINDOW_POS_X = 300;
const int WINDOW_POS_Y = 150;

void myInit()
{
    glClearColor(1.0f, 1.0f, 1.0f, 0.0f);
    glViewport(0, 0, WINDOW_WIDTH, WINDOW_HEIGHT);
}

//draw a z-axis, with cone at end
void axis(double length)
{
    glPushMatrix();
    glBegin(GL_LINES);
    glVertex3d(0, 0, 0);
    glVertex3d(0, 0, length);
    glEnd();
    glTranslated(0, 0, length - 0.2);//平移
    glutWireCone(0.04, 0.2, 12, 9);
    glPopMatrix();
}

void displayWire()
{
    glMatrixMode(GL_PROJECTION);//设置视景体
    glLoadIdentity();
    glOrtho(-2.0 * 64 / 48, 2.0 * 64 / 48, -2.0, 2.0, 0.1, 100);

    glMatrixMode(GL_MODELVIEW);
    glLoadIdentity();
    gluLookAt(1.0, 1.0, 2.0, 0.0, 0.0, 0.0, 0.0, 1.0, 0.0);

    glClear(GL_COLOR_BUFFER_BIT);
    glColor3d(0, 0, 0);

    axis(0.5);//z-axis
    glPushMatrix();
    glRotated(-90, 1.0, 0, 0);
    axis(0.5);//y-axis
    glRotated(90.0, 0, 1.0, 0);
    axis(0.5);//x-axis
    glPopMatrix();

    glPushMatrix();
    glTranslated(0.5, 0.5, 0.5);
    glutWireCube(1.0);//线框立方体
    glPopMatrix();

    glColor3d(1.0, 0, 0);
    glPushMatrix();
    glTranslated(1.0, 1.0, 0);
    glutWireSphere(0.25, 10, 8);//线框球体
    glPopMatrix();

    glColor3d(0, 1.0, 0);
    glPushMatrix();
    glTranslated(1.0, 0, 1.0);
    glutWireCone(0.2, 0.5, 10, 8);//线框圆锥体
    glPopMatrix();

    glColor3d(0, 0, 1.0);
    glPushMatrix();
    glTranslated(1.0, 1.0, 1.0);
    glutWireTeapot(0.2);//线框茶壶
    glPopMatrix();

    glColor3d(1.0, 0, 1.00);
    glPushMatrix();
    glTranslated(0, 1.0, 0);
    glutWireTorus(0.1, 0.3, 10, 10);//线框花环
    glPopMatrix();

    glColor3d(0, 1.0, 1.0);
    glPushMatrix();
    glTranslated(1.0, 0, 0);
    glScaled(0.15, 0.15, 0.15);
    glutWireDodecahedron();//线框12面体
    glPopMatrix();

    glColor3d(0.1, 0.5, 0.2);
    glPushMatrix();
    glTranslated(0, 1.0, 1.0);
    glutWireCube(0.25);
    glPopMatrix();

    glPushMatrix();
    glTranslated(0, 0, 1.0);
    GLUquadricObj* qobj = gluNewQuadric();//创建二次曲面对象
    gluQuadricDrawStyle(qobj, GLU_LINE);
    glColor3d(0.3, 0.5, 0.4);
    gluCylinder(qobj, 0.2, 0.2, 0.4, 8, 8);//圆柱体
    glPopMatrix();
    glFlush();
}

int main(int argc, char** argv)
{
    glutInit(argc, argv);
    glutInitDisplayMode(GLUT_SINGLE | GLUT_RGB);
    glutInitWindowSize(WINDOW_WIDTH, WINDOW_HEIGHT);
    glutInitWindowPosition(WINDOW_POS_X, WINDOW_POS_Y);
    glutCreateWindow("Transformation Test -Wireframes");
    glutDisplayFunc(displayWire);
    myInit();
    glutMainLoop();//进入消息循环

    return 0;
}

5.6.3 着色三维场景绘制

#include
#include <gl/gl.h>
#include <gl/glu.h>
#include <gl/glut.h>
#pragma comment(linker, "/subsystem:\"windows\" /entry:\"mainCRTStartup\"")

const int WINDOW_WIDTH = 640;
const int WINDOW_HEIGHT = 480;
const int WINDOW_POS_X = 300;
const int WINDOW_POS_Y = 150;

void myInit()
{
    glEnable(GL_LIGHTING);//enable the light source
    glEnable(GL_LIGHT0);
    glShadeModel(GL_SMOOTH);//光滑着色
    glEnable(GL_DEPTH_TEST);//启用深度测试,根据坐标的远近自动隐藏被遮住的图形
    glEnable(GL_NORMALIZE);//根据函数glNormal的设置条件，启用法向量
    glClearColor(1.0f, 1.0f, 1.0f, 0.0f);
    glViewport(0, 0, WINDOW_WIDTH, WINDOW_HEIGHT);
}

//draw thin wall with top = xz-plane, corner at origin
void wall(double thickness)
{
    glPushMatrix();
    glTranslated(0.5, 0.5 * thickness, 0.5);
    glScaled(1.0, thickness, 1.0);
    glutSolidCube(1.0);
    glPopMatrix();
}

//table leg
void tableLeg(double thick, double len)
{
    glPushMatrix();
    glTranslated(0, len / 2, 0);
    glScaled(thick, len, thick);
    glutSolidCube(1.0);
    glPopMatrix();
}

//draw one axis of the unit jack-a stretched sphere
void jackPart()
{
    glPushMatrix();
    glScaled(0.2, 0.2, 1.0);
    glutSolidSphere(1, 15, 15);
    glPopMatrix();

    glPushMatrix();
    glTranslated(0, 0, 1.2);//ball on one end
    glutSolidSphere(0.2, 15, 15);
    glTranslated(0, 0, -2.4);
    glutSolidSphere(0.2, 15, 15);//ball on the other end
    glPopMatrix();
}

//draw a unit jact out of spheroids
void jack()
{
    glPushMatrix();
    jackPart();
    glRotated(90.0, 0, 1, 0);
    jackPart();
    glRotated(90.0, 1.0, 0, 0);
    jackPart();
    glPopMatrix();
}

//draw the table - a top and four legs
//绘画桌子时候，外部调用已经使原点到达桌子中间了
void table(double topWid, double topThick, double legThick, double legLen)
{
    glPushMatrix();
    glTranslated(0, legLen, 0);
    glScaled(topWid, topThick, topWid);
    glutSolidCube(1.0);//桌面
    glPopMatrix();

    double dist = 0.95 * topWid / 2.0 - legThick / 2.0;
    glPushMatrix();
    //glTranslated(dist, 0, dist);
    glTranslated(dist, 0, dist);
    tableLeg(legThick, legLen);
    glTranslated(0, 0, -2 * dist);
    tableLeg(legThick, legLen);
    glTranslated(-2 * dist, 0, 2 * dist);
    tableLeg(legThick, legLen);
    glTranslated(0, 0, -2 * dist);
    tableLeg(legThick, legLen);
    glPopMatrix();
}

void displaySolid()
{
    //设置表面纹理属性
    GLfloat mat_ambient[] = {0.7, 0.7, 0.7, 1.0};
    GLfloat mat_diffuse[] = {0.6, 0.6, 0.6, 1.0};
    GLfloat mat_specular[] = {1.0, 1.0, 1.0, 1.0};//反射
    GLfloat mat_shininess[] = {50.0};//光

    glMaterialfv(GL_FRONT, GL_AMBIENT, mat_ambient);//环境光材质
    glMaterialfv(GL_FRONT, GL_DIFFUSE, mat_diffuse);//漫反射
    glMaterialfv(GL_FRONT, GL_SPECULAR, mat_specular);//镜面反射
    glMaterialfv(GL_FRONT, GL_SHININESS, mat_shininess);//光亮

    //设置光源属性
    GLfloat lightIntensity[] = {0.7, 0.7, 0.7, 1.0};
    GLfloat lightPosition[] = {2.0, 6.0, 3.0, 0.0};
    glLightfv(GL_LIGHT0, GL_POSITION, lightPosition);//设置光源0的位置
    glLightfv(GL_LIGHT0, GL_DIFFUSE, lightIntensity);//光源漫反射强度的RGBA值

    glMatrixMode(GL_PROJECTION);
    glLoadIdentity();
    double winHt = 1.0; // half - height of th window
    glOrtho(-winHt * 64 / 48.0, winHt * 64 / 48.0, -winHt, winHt, 0.1, 100.0);

    glMatrixMode(GL_MODELVIEW);//设置照相机
    glLoadIdentity();
    gluLookAt(2.3, 1.3, 2, 0, 0.25, 0, 0.0, 1.0, 0.0);

    //start draw
    glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT);

    glPushMatrix();
    glTranslated(0.4, 0.4, 0.6);
    glRotated(45, 0, 0, 1);
    glScaled(0.08, 0.08, 0.08);
    jack();//draw the jack
    glPopMatrix();

    glPushMatrix();
    glTranslated(0.6, 0.38, 0.5);
    glRotated(30, 0, 1, 0);
    glutSolidTeapot(0.08);//draw the teapot
    glPopMatrix();

    glPushMatrix();
    glTranslated(0.25, 0.42, 0.35);
    glutSolidSphere(0.1, 15, 15);//draw the sphere
    glPopMatrix();

    glPushMatrix();
    glTranslated(0.4, 0, 0.4);
    table(0.6, 0.02, 0.02, 0.3);//draw the table
    glPopMatrix();

    wall(0.02); //wall #1: in xz-plane
    glPushMatrix();
    glRotated(90.0, 0.0, 0.0, 1.0);
    wall(0.02);//wall #2: in xy-plane
    glRotated(90.0, 1.0, 0.0, 0.0);
    wall(0.02);
    glPopMatrix();//wall #3: in yz-plane

    glFlush();
}

int main(int argc, char** argv)
{
    glutInit(argc, argv);
    glutInitDisplayMode(GLUT_SINGLE | GLUT_RGB | GLUT_DEPTH);
    glutInitWindowSize(WINDOW_WIDTH, WINDOW_HEIGHT);
    glutInitWindowPosition(WINDOW_POS_X, WINDOW_POS_Y);
    glutCreateWindow("Shaded example-3D scene");
    glutDisplayFunc(displaySolid);
    myInit();
    glutMainLoop();//进入消息循环

    return 0;
}

5.6.4 使用SDL从文件中读取场景描述

SDLDraw