software transaction memory

所谓的 STM 就是将内存当做类似数据库一样来访问,这种基于“ACID”机制的 transaction 对数据库来说一般是 fail 掉出现冲突的 transaction,类似对内存来说这个概念也是出现在访问冲突的情况下,只是因为是内存,不可能完成 durability 的需求。

一个常见的例子是 RB tree,通常为了保证这个树在多线程访问的正确性,我们必须为整棵树上锁,读取或者写入都必须获得 lock,这个策略很明显不会是最优的,比如两个插入同时发生,如果两者值相差很远,即便调整树的形状也有很高的概率两者产生变换的子树完全没有交集,那更不用说一些读取和写入同时发生的 case。STM 就为这种 concurrency 控制提供了非常细粒度的选择余地。

一个常见的问题是,那么怎么写 code 呢?GCC 在 4.7 就开始提供了 STM 的基本支持(相关 wiki),下面是一个简单的例子(来自这里

#include <iostream>
#include <thread>

static const int THR_NUM = 4;
static const int ITER_NUM = 1024 * 1024;

static int a = 0, b = 0, c = 0;

static void thr_func() {
  for (int i = 0; i < ITER_NUM; ++i) {
    __transaction_atomic {
      ++a;
      b += 2;
      c = a + b;
    }
  }
}

int
main(int argc, char *argv[]) {
  std::thread thr[THR_NUM];

  for (auto &t : thr)
    t = std::thread(thr_func);

  for (auto &t : thr)
    t.join();

  std::cout << "a=" << a << " b=" << b
            << " c=" << c << std::endl;

  return 0;
}

编译执行后的结果如下:

$ opt/local/bin/g++-mp-4.8 -std=c++11 -fgnu-tm test.cpp   -o test
$ time ./test
=4000000 b=8000000 c=12000000

real	0m1.672s
user	0m6.196s
sys	0m0.140s
$ time ./test # without STM
a=1509777 b=3048416 c=4558193

real	0m0.046s
user	0m0.155s
sys	0m0.002s

可以看出,第一使用 STM 现在还是很慢的,第二似乎结果是我们需要的。我们也能很简单的 reason,这就是 STM 的功能,提供一个 optimistic locking 机制,而 mutex 之类的因为是 pessimistic 的,某种意义上 concurrency 会较差,当然从巨大的效率差异上来看,这个功能还是太鸡肋,毕竟为了 tracking 冲突代价不小。STM 体现在各个语言里面呈现的技术也不大一样,functional programming language 比较喜欢 monads。值得注意的是跟 STM 有关的 code 因为可能被 rollback 理论上是不能有 side effect 的,比如 IO,这也会给很多别的事情造成麻烦,比如 debugging。据说这几年这玩意会火,倒是看到不少语言都开始提供这方面的 library 了,不知道 C++ 里面什么时候能看见。

更多的信息可以看看 linuxcon 上这位同志的介绍。

——————
So went the present over before him: and himself lodged that night in the company.

Advertisements
software transaction memory

发表评论

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s