スレッドの生成と破棄のオーバーヘッド

ID: 34

creation date: 2009/11/06 11:00

modification date: 2009/11/06 11:00

owner: mikio

Overhead of creating and destroying threads

複数のTTサーバ上に分散したテーブルDBに対してメタ検索（並列検索と結果のマージ）を行うメソッドとして tcrdbparasearch というメソッドを実装したが、これは内部でスレッドを立てて並列性を実現している。selectでI/Oの多重化を測るという手法も考えたし実際に実装もしてみたのだが、同じ接続に対して並列検索する場合は、非同期プロトコルでないのでI/O多重化が使えないということになって断念した（まあ、同じサーバに並列検索する意味があるかどうかは怪しいが、実装事情の制限をインターフェイスに反映するのはなるべく避けたいので）。

I did implement tcrdbparasearch which does parallel search against table dbs on multiple TokyoTytrant servers (and merge the resultset). To implement this, I used threads. I tried to implement using multiplexing io using "select" call, but had to give up, because I can not multiplex IO when connecting to a single server ( there is less use case to do parallel search against same server, but I did not want to reflect the implementation limitation to the interfaces).

スレッドを使わないようにしたかったのは、スレッドを生成（create）したり回収（join）したりする操作のオーバーヘッドが高いという事前知識があったからだ。でもそれって本当？ 多少のオーバーヘッドはあるにしても、そんなに高いのか？

大人は信用できない。自分の目で見て確かめるべきだ。実際に確かめるべくテストコードを書いてみた。並列性を1スレッドから256スレッドまで変化させつつ、スレッドの生成と回収の1セットあたりの時間を調べるのだ。「gcc -std=c99 -Wall -O2 -o mytest mytest.c」でビルドできる。結果は環境依存性が強いだろうから、ぜひ自分の環境で動かしてみてほしい。

Why did I try to avoid using threads in the beginning? Because I knew that it has high overhead to create and join threads. But is it really true?

To confirm the theory, I wrote a test code to change number of thread from 1 to 256 and capture the time to create and join the thread. You can build it with "gcc -std=c99 -Wall -O2 -o mytest mytest.c" command. The result may depend on OS/HW, so you may want to try it by yourself.

#include <stdio.h>

#include <stdlib.h>

#include <assert.h>

#include <pthread.h>

#include <sched.h>

#include <sys/time.h>

int main(int argc, char **argv);

static double mytime(void);

static void *worker(void *arg);

int main(int argc, char **argv){

  for(int tnum = 1; tnum <= 256; tnum *= 2){

    double stime = mytime();

    int max = 1000000 / tnum;

    for(int cnt = 0; cnt < max; cnt++){

      pthread_t threads[tnum];

      for(int i = 0; i < tnum; i++){

        if(pthread_create(threads + i, NULL, worker, NULL) != 0){

          perror("pthread_create");

          abort();

        }

      }

      for(int i = 0; i < tnum; i++){

        if(pthread_join(threads[i], NULL) != 0){

          perror("pthread_join");

          abort();

        }

      }

    }

    double etime = mytime();

    printf("%d\t%f\n", tnum, etime - stime);

  }

  return 0;

}

static double mytime(void){

  struct timeval tv;

  if(gettimeofday(&tv, NULL) == -1) return 0.0;

  return (double)tv.tv_sec + (double)tv.tv_usec / 1000000.0;

}

static void *worker(void *arg){

  sched_yield();

  return NULL;

}

俺の環境だと、以下のような結果になった。100万回の実行なので、total timeの秒数を1回のマイクロ秒数に読み替えられる。

Here is my result. The result set is total second per 1 million execution, so it is equivalent to total micro second per 1 execution.

考察の前に、このテストケースでは、ボススレッドは何もしていないし、ワーカスレッドはsched_yieldで自発的コンテキストスイッチを起こして1回以上のスケジューラ遅延を画策しているだけだ（なお、sched_yieldを省略した場合にはスループットが2%ほど向上するようだ）。なので、実際のユースケースではもっとオーバーヘッドは高いかもしれないが、傾向を見るにはこの実験も参考になるだろう。

In this test case, the boss thread does not do anything and the worker threads kicks off context switch using shed_yield to delay one scheduling. The throughput will increase by 2 % if I omit the shed_yield, but this will be enough for this experimentation purpose.

さて、1スレッドを生成して回収するだけなら16マイクロ秒しかかからないというのは意外であった。もっとかかるかと思っていたが、これならネットワークI/Oのオーバーヘッドに比べれば全然大したことないっぽい。4スレッドの時に最速になっているのはマシンのコア数が4つなのと関係あるような気がするが、定かではない。

ということで、並列性が10やそこらでよいのであれば、スレッドをガンガン使っても問題ないことがわかったので、tcrdbparasearchは現状のスレッドを利用するモデルのままで行くようにした。

Now, here is the analysis of the test result. It is surprising that it takes only 16 micro second when creating and joining only one thread, as I was expecting that it would take more. This overhead would be a way less than network IO overhead. The result also shows that it's the fastest when there are 4 threads. It's probably because this test was run on my 4 core machine, but not sure. To sums up, threading overhead is not a lot when there are 10 threads, so I decided to keep using threads inside tcrdbparasearch method.

なお、スレッドを立てられる数には処理系依存の限界があるので、何でもかんでもスレッドを立ててやれということではない。並列性が100とかになる場合はselectを使うべきだし、さらに1000や10000のオーダになる場合はepollなどを使うべきだろう。

One thing to note. You can not keep using threads for everything, as the limitation of the threads depends on OS. If you need more than 100 parallel operations, you should use "select". If you need 1000 or 10000, then you should use epoll .