Less is more

又到了这个时候，明天就要收拾东西回家过年了，只不过始发站从去年的苏州变成了北京。回想去年的这个时候还一边加紧的学习技术知识，一边担心来年能不能顺利找到合适的工作，不得不感叹时间确实过的挺快的。

2015年主要做了2件事。一是换了份工作，5月份从苏州辞职只身来到北京找工作，最终顺利的拿了到6个offer，这也要感谢Jordan、C哥在这个过程中给我的帮助。第二个就是迅速的融入了工作团队，顺利的完成了笑傲江湖新资料片的服务端开发任务，从中熟悉了不少大型端游服务端业务的特点以及处理实际线上问题的方法。

这一年工作上最大的感悟就是工作上需要professional。这里的professional不是指专业技术，而是指工作的时候不要受个人情绪影响，生活是生活，工作是工作，不能让个人情绪影响工作效率。

新的一年也希望自己能做好两件事吧，一是熟悉整个项目的代码结构及业务特点，二是学习编译原理和编程语言设计。至于其他的就顺其自然吧，不必强求。

在现代C++中，通过使用shared_ptr这样的智能指针能够很好的降低内存泄漏的可能性，但是在多线程中无保护的读写shared_ptr则有可能带来race condition的情况。

对此，boost官方文档是这样描述的：

shared_ptr 对象提供与内建类型一样的线程安全级别。一个 shared_ptr 实例可以同时被多个线程“读”（仅使用不变操作进行访问）。不同的 shared_ptr 实例可以同时被多个线程“写入”（使用类似operator= 或 reset 这样的可变操作进行访问）（即使这些实例是拷贝，而且共享下层的引用计数）。

从 Boost 版本 1.33.0 开始，shared_ptr 在以下平台上使用了 lock-free 实现：

• GNU GCC on x86 or x86-64;
• GNU GCC on IA64;
• Metrowerks CodeWarrior on PowerPC;
• GNU GCC on PowerPC;
• Windows.
  可以看到现在版本的shared_ptr本身的引用计数是安全并且无锁的，但是shard_ptr对象本身则不是，为什么呢？

简单来说，因为shared_ptr有不止引用计数一个数据成员，它有指向引用计数对象的指针和指向实际数据的指针这两个成员，虽然引用计数本身是原子化的，但是两个成员一起作为一个对象在多线程环境下读写时，就不能原子化了。

数据结构模型

shared_ptr是引用计数类型的智能指针，并且绝大多数实现都是存放在堆上的空间里。

具体来说，一个shared_ptr包含两个成员，一个是指向实际数据Foo的指针，一个是指向堆上的引用计数对象的指针ref_count。引用计数对象有多个数据成员，具体如上图所示，其中allocator和deleter是可选的。

partition算法是一种分类算法，简单来说就把一个序列分成前后两部分，前一部分都是满足某一条件的元素，后一部分都是不满足该条件的元素。关于partition算法最著名的应用就是quick sort（快速排序）了。

除了快速排序外，partition算法还经常用在下列场合：

• 在O(N)的时间内找出一个序列中第k大（小）的元素。
• 在O(N)的时间内找出一个序列中所有比k大（小）的元素。

但是这一类场景使用的partition算法和快速排序使用的partition算法有一些略微的差别，如果不小心错用的话，就会产生意料之外的错误了。

快速排序的partition算法

简单来说就是通过partition算法将待排序序列划分为以pivot（中间）值为分界点的两个子序列，一个子序列所有元素的值都小于pivot，另一个子序列所有元素的值都大于等于pivot，然后再对每个子序列递归进行这样的操作。

常见的时间复杂度为Nlog(N)的排序算法有快速排序、堆排序、归并排序。一般来说在有大量的待排序序列数据的时候，快速排序是三种算法中表现最好的。

相较于堆排序，快速排序有更好的缓存局部性。在待排序数据量很大时，堆排序每次从二叉堆取出最大值，再放入一个较小的值，然后二叉堆调整其中各个元素时，从整个序列来看数据地址跨越的范围较大，发生cache未命中的几率增加，导致数据局部性变差。而快速排序，由于每次进行partition的时候数据交换都集中在当前的这一小段序列中，因此数据的地址跨越范围小，cache未命中的几率较小，数据局部性就更好了。

而对于归并排序，由于归并排序的空间复杂度是O(N)，每一层归并的时候都会发生数据从原始空间到辅助空间的拷贝或者从辅助空间到原始空间的拷贝，而原始空间是调用者申请的，辅助空间是被调用者自己申请的，所以从进程的虚拟地址空间上来讲两段空间的地址一般相差较大，这样每次拷贝的时候出现cache未命中的次数会升高，所以堆排序的局部性也不如快速排序。

Substitution Failure Is Not An Error

SFINAE，即匹配失败不是错误。它是C++中一种很有用的规则。在决议重载的模板函数或者特化/偏特化类的时候，如果对一个较为「特化」版的候选者的模板形参推断（匹配）失败，将转而对其他次「特化」的候选者进行模板参数推断（匹配），而不是返回一个错误。

先看一个简单的例子：

struct Test
{
    typedef int foo;
};

template<typename T>
void bar(typename T::foo) // #1
{
}

template<typename T>
void bar(T) // #2
{
}

int main(int argc, char* argv[])
{
    bar<Test>(0); // call #1
    bar<int>(0);  // call #2, not error.
}

第一个函数调用，显示实例化形参为Test类型，而Test有一个类型foo，所以匹配#1版本成功。

第二个函数调用，因为编译器总是最先尝试推断（匹配）「最特化」的候选函数，所以先对#1版本进行匹配，而int是一个内置类型，并没有子类型foo，所以#1版本匹配失败，然后转而对#2版本的候选函数进行匹配，即T实例化为int类型，匹配成功。

利用SFINAE这种特性，就可以在编译期做很多事情了。

套接字的默认状态是阻塞的。如果一个套接字不能立即完成相应的调用，那么该线程就会被投入睡眠，等待相应的操作完成。阻塞一个套接字的操作可能是输入操作、输出操作、接受外来连接、发起外出连接这四种操作中的一种。如果把套接字改为非阻塞的话，这些操作就会变的不一样了。

• 输入操作，包括read、readv、recv、recvfrom和recvmsg这五个函数（aio系列函数除外，其为异步IO）。对于非阻塞的套接字，如果输入操作不能被满足（TCP套接字默认是至少有一个字节的数据可读，UDP套接字默认是有一个完整的数据报可读），相应的输入调用将立即返回EWOULDBLOCK错误（在Linux上EWOULDBLOCK与EAGAIN等价）
• 输出操作，包括write、writev、send、sendto和sendmsg这5个函数（aio系列函数除外，其为异步IO）。对于非阻塞的TCP套接字，如果其发送缓冲区根本没有空间，相关函数调用将立即返回EWOULDBLOCK错误。如果其发送缓冲区中有一些空间单不足以装下所有用户数据，返回值将是内核能够从用户缓冲区复制到内核发送缓冲区的字节数，也称「不足计数」。
• 接受外来连接，即accept函数。对于非阻塞的TCP套接字，如果调用accept函数但无连接到达，则立即返回一个EWOULDBLOCK错误。
• 发起外出连接，即connect函数。对于非阻塞的TCP套接字，如果调用connect并且连接不能立即建立，那么连接的建立可以照样发起，不过会返回一个EINPROGRESS错误。但此时并不能确定是连接发生错误还是已成功建立连接，具体内容后文再讨论。

connect

在非阻塞TCP套接字上调用connect函数，将立即返回一个EINPROGRESS错误，不过已经发起的TCP三路握手继续进行（即调用connect使套接字发送SYN分节后立即返回EINPROGRESS）。然后就可以用epoll/poll/select检测该连接的成功或者失败。

相对于阻塞connect，非阻塞connect有下面几个用途：

1. 可以在TCP三次握手的时候进行其他操作。因为客户发生一个SYN分节，然后等到收到服务端的ACK分节后，客户端的连接才建立起来，这其中经过了一个RTT时间。但是RTT的实际波动范围较大，从局域网的几毫秒到广域网的几秒，非阻塞connect可以把这段时间利用起来处理其他事物。
2. 可以同时建立多个连接。
3. 可以通过epoll/poll/select设置超时时间。默认的阻塞connect的超时一般为75秒，如果想要设置更短的超时时间就可以通过非阻塞connect配合IO复用来完成。
   阅读全文 »