Yebangyu's Blog

Fond of Concurrency Programming and Machine Learning

虚函数和变长参数模板的妙用

假如我们需要设计和实现自己的容器,比如说vector,list,queue等。

同一类容器,我们可能有不同的实现和用途,因此我们抽象出了一个Base Class,比如说(以Vector为例):

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
#include<iostream>
using namespace std;
template<typename T>
class BaseVector
{
public:
  virtual void pre_allocate(int capacity) = 0;
};

template<typename T>
class SmallVector: public BaseVector<T> //一种特定的实现
{
public:
  virtual void pre_allocate(int capacity)
  {
    p_ = (T*)malloc(sizeof(T) * capacity); //实际里可能不是malloc,而是自己实现的allocator
   //错误处理等等不在本文考虑范围之内
    for (int i = 0; i < capacity; ++i) {
      new(&p_[i]) T(); //预先构造好。注意,这里需要参数个数为0的默认构造函数
    }
  }
private:
  T *p_;
};
class NoParameters
{
  //do something
};
int main()
{
  SmallVector<NoParameters> vec0;
  vec0.pre_allocate(1000);
  return 0;
}

没问题。一切完美。不过你试图这样使用vector类,就不行了:

Singleton与多线程

如果您和我一样,都只有C++背景,之前对设计模式也一窍不通,那么也没有关系,因为本文不需要您对设计模式有多么了解。

Singleton模式

所谓的单例模式,single instance模式,简单实现如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Singleton
{
  public:
    static Singleton* instance();
  private:
    static Singleton* pInstance;
};

Singleton* Singleton::pInstance = NULL;

Singleton* Singleton::instance()
{
  if (pInstance == NULL) {
    pInstance = new Singleton();
  }
  return pInstance;
}

Lock Free中的Hazard Pointer(下)

在前面几篇文章里,我们介绍了Hazard Pointer,一种用于lock free data structure设计中内存管理的利器,这个利器不仅思想简单,还可以用来防止ABA问题,读者诸君务必掌握。

本文作为第三部分,给出工业级代码中,实现Hazard Pointer的一些策略和需要注意的点。

Hazard Pointer管理

我们知道Hazard Pointer封装了原始指针,那么Hazard Pointer的内存和生命周期本身如何管理呢?以下是常见的策略:

性能优化的那些传说和迷思

相信你在很多书籍中见到很多代码调优(tuning code)的建议和方法。这些书籍可能包括《编程珠玑》、《深入理解计算机系统》、《程序设计实践》、《Optimized C++》等等。坦白说,这些书我都看过,它们确实提供了不少有意思的性能调优的方法,那么我们的问题是,这些建议和方法有效吗?所谓有效,一种衡量途径是,假如我们不那么做,是否编译器已经会自动优化了呢?

本文我们举几个例子,然后开启编译器优化选项后,看看发生了什么。

本文环境为:Ubuntu 14.04 32bit + Intel I7 CPU + GCC 4.8

生成汇编代码的语句是:g++ -S -O2 code.cpp

循环展开

对于下面的函数

1
2
3
4
5
6
void f1(int *a)
{
  for (int i = 0; i < 3;i++) {
    a[i] = a[i] + 2;
  }
}

它们建议可以将循环展开,变成这样:

1
2
3
4
5
6
void f2(int *a)
{
  a[0] = a[0] + 2;
  a[1] = a[1] + 2;
  a[2] = a[2] + 2;
}

一个轻量的lock free程序调试工具

lock free 程序时序混乱,逻辑复杂,反直觉的地方很多,心智负担很重,因此调试起来也非常困难。

下面用C++编写了一个用于调试lock free代码的程序,非常轻量,代码如下,只适用于linux环境。

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
//xx.h
#include <pthread.h>
class LockFreeLogger
{
public:
  struct Event
  {
    char *message;
    pthread_t thread_id;
    int info;
  };
  LockFreeLogger()
  {
    pos_ = 0;
    buffer_ = new Event[SIZE];
  }
  void log(char *message, int info)
  {
    int pos = __sync_fetch_and_add(&pos_, 1);
    buffer_[pos].message = message;
    buffer_[pos].info = info;
    buffer_[pos].thread_id = pthread_self();
  }
  void report()
  {
    //single thread code
    for (int i = 0; i < pos_; i++) {
      //cout or fwrite buffer_[i];
    }
  }
private:
  int pos_;
  Event *buffer_;
  static const int SIZE = 1234567;
};

extern LockFreeLogger logger;

#define LOG(message, info) logger.log(message, info)

Lock Free中的Epoch Based Reclamation

楔子

一般认为,用C/C++编写Lock Free代码非常困难,主要原因无非是两个:

  • 内存模型
  • 内存回收

C++11引入了标准的内存模型,在此之前,C++程序员依赖于具体的体系结构特点和编译器提供的feature来保证正确的内存访问语义。C++11出来后,程序员编写健壮的、可移植的lock free代码成为可能。

但是内存回收问题依旧存在。我们知道,和Java这种提供自动gc的语言相比,C++程序员刀耕火种,得自己管理内存。当一个线程正在访问某块内存,而另外一个线程将它释放将是一个灾难行为。解决内存回收问题在lock free里显得更加困难。

目前用于lock free代码的内存回收的经典方法有:Lock Free Reference Counting、Hazard Pointer、Epoch Based Reclamation、Quiescent State Based Reclamation等。上回我们简单介绍了Hazard Pointer,本文我们介绍Epoch Based Reclamation方法。据我所知,这是第一篇介绍这个方法的中文资料。

MCS Lock

回顾

上回 我们介绍了Ticket Lock算法,和传统的简单的CAS操作来实现spin lock相比,它提供了不少很好的性质:比如FIFO、没有饥饿等等。

但是根据论文,ticket lock的scalability很差。我们不妨简单回顾一下(代码片段也摘自该论文):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
struct spinlock_t
{
  int current_ticket ;
  int next_ticket ;
}
void spin_lock (spinlock_t *lock)
{
  int t = atomic_fetch_and_inc(&lock -> next_ticket );
  while (t != lock->current_ticket )
  ; /* spin */
}
void spin_unlock (spinlock_t *lock)
{
  lock->current_ticket++;
}

实现可重入锁

基本概念

可重入锁(Reentrant Lock),是指允许同一个线程多次对该锁进行acquire动作。对于不可重入的锁,当一个线程多次调用acquire后将造成死锁。可重入锁具有广泛的应用,例如:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
struct Routine
{
  void f()
  {
    lock_.lock();
    h();
    g();
    lock_.unlock();
  }
  void g()
  {
    lock_.lock();
    cout<<"abc"<<endl;
    lock_.unlock();
  }
  void h()
  {
    lock_.lock();
    cout<<"def"<<endl;
    lock_.unlock();
  }
  Lock lock_;
};

Sequence Lock

在读多写少(Read Mostly)的场景里,我们可能会使用的同步设施包括:

  • Mutex / Spin Lock
  • Reader Writer Lock
  • Sequence Lock
  • Read Copy Update

前面两种一般人都很清楚了,如雷贯耳、妇孺皆知。如果您对Spin Lock的实现细节有兴趣,建议您阅读我的这几篇博客:

Peterson Lock

Ticket Lock

MCS Queue Lock

从今天起,我们介绍后面两种同步设施。今天我们先介绍Sequence Lock。

String与Copy On Write

什么是Copy On Write

Copy On Write(COW)作为一种优化技术被广泛使用,在string的实现中也不例外。考虑如下的代码:

1
2
3
string s("1234");
string t = s;
cout<<t[1]<<endl;

第二行,通过调用copy constructor(注意,这里调用的是copy constructor,而不是copy assignment,因为它是从无到有构造对象,而不是设置已有对象)构造对象t,第三行对t中的某个元素进行只读操作。

如果让你实现copy constructor,你会怎么做呢?教科书里的、简单的实现大概是这样: