mojavy.com

スレッドプールの実装方法について

March 03, 2014 at 08:58 PM | categories: unix, programming |

スレッドプール(thread pool)を実装するには、暇なときはthreadを寝かせておいて必要なときに起こす、というイベント通知の仕組みが必要になる。 UnixでC/C++で実装するときはpthreadの条件変数を使うのが普通だと思われるが、適当なファイルディスクリプタをopenしておいてread等でブロックさせる方法でも実装できそう。

どのようなやり方が一般的なのか、いくつか有名どころのOSSの実装を調べてみた。

libuvの場合

https://github.com/joyent/libuv

単純にpthread_cond_waitをつかっている 1 

static void worker(void* arg) {
  struct uv__work* w;
  QUEUE* q;

  (void) arg;

  for (;;) {
    uv_mutex_lock(&mutex);

    while (QUEUE_EMPTY(&wq))
      uv_cond_wait(&cond, &mutex);

    q = QUEUE_HEAD(&wq);

    if (q == &exit_message)
      uv_cond_signal(&cond);
    else {
      QUEUE_REMOVE(q);
      QUEUE_INIT(q);  /* Signal uv_cancel() that the work req is
                             executing. */
    }

    uv_mutex_unlock(&mutex);

    if (q == &exit_message)
      break;

    w = QUEUE_DATA(q, struct uv__work, wq);
    w->work(w);

    uv_mutex_lock(&w->loop->wq_mutex);
    w->work = NULL;  /* Signal uv_cancel() that the work req is done
                        executing. */
    QUEUE_INSERT_TAIL(&w->loop->wq, &w->wq);
    uv_async_send(&w->loop->wq_async);
    uv_mutex_unlock(&w->loop->wq_mutex);
  }
}

Boost.Asioの場合

http://www.boost.org/doc/libs/1_55_0/doc/html/boost_asio.html

Boost.Asioにスレッドプールそのものは提供されてないが以下のようにして簡単に実装することができる

#include <thread>
#include <functional>
#include <boost/asio.hpp>

int main ( int argc, char* argv[] ) {
    asio::io_service io_service;
    asio::io_service::work work(io_service);

    std::vector<std::thread> threadPool;

    for(size_t t = 0; t < std::thread::hardware_concurrency(); t++){
        threadPool.push_back(thread(std::bind(&asio::io_service::run, &io_service)));
    }

    io_service.post(std::bind(an_expensive_calculation, 42));
    io_service.post(std::bind(a_long_running_task, 123));

    //Do some things with the main thread

    io_service.stop();
    for(std::thread& t : threadPool) {
        t.join();
    }
}

http://stackoverflow.com/questions/14265676/using-boostasio-thread-pool-for-general-purpose-tasks

長くなるのでコードは省略するが、io_service::postするとunixの場合は最終的にはtask_io_service::wake_one_idle_thread_and_unlockからpthread_cond_signalが呼ばれる。

memcachedの場合

https://github.com/memcached/memcached

libeventのイベント通知機能を利用して実装している。それぞれのthread初期化の際にpipeをつくって、そのfdをlibeventに渡す。 2 libevent内部でそのfdをepollなりkqueueなりでブロックして待つ。

//
// memcached.c
//
typedef struct {
    pthread_t thread_id;        /* unique ID of this thread */
    struct event_base *base;    /* libevent handle this thread uses */
    struct event notify_event;  /* listen event for notify pipe */
    int notify_receive_fd;      /* receiving end of notify pipe */
    int notify_send_fd;         /* sending end of notify pipe */
    struct thread_stats stats;  /* Stats generated by this thread */
    struct conn_queue *new_conn_queue; /* queue of new connections to handle */
    cache_t *suffix_cache;      /* suffix cache */
    uint8_t item_lock_type;     /* use fine-grained or global item lock */
} LIBEVENT_THREAD;

//
// thread.c
//
void thread_init(int nthreads, struct event_base *main_base) {
//
// 中略
//
    threads = calloc(nthreads, sizeof(LIBEVENT_THREAD));
//
// さらに中略
//
    for (i = 0; i < nthreads; i++) {
        int fds[2];
        if (pipe(fds)) {
            perror("Can't create notify pipe");
            exit(1);
        }

        threads[i].notify_receive_fd = fds[0];
        threads[i].notify_send_fd = fds[1];

        setup_thread(&threads[i]);
        /* Reserve three fds for the libevent base, and two for the pipe */
        stats.reserved_fds += 5;
    }

    /* Create threads after we've done all the libevent setup. */
    for (i = 0; i < nthreads; i++) {
        create_worker(worker_libevent, &threads[i]);
    }

    /* Wait for all the threads to set themselves up before returning. */
    pthread_mutex_lock(&init_lock);
    wait_for_thread_registration(nthreads);
    pthread_mutex_unlock(&init_lock);
}

pthread_cond_waitの実装

脱線するが、pthread_cond_waitがどのようにsleepにはいってるのか気になったので調べた。

https://sourceware.org/git/?p=glibc.git;a=tree;f=nptl;hb=HEAD

pthread_cond_waitのソースコードはglibcのnptl以下にある。 __pthread_cond_waitがlll_futex_waitを呼んでおり、これは以下のように実装されている。(以下はx86_64のもの) 

#define lll_futex_wait(futex, val, private) \
  lll_futex_timed_wait(futex, val, NULL, private)

#define lll_futex_timed_wait(futex, val, timeout, private) \
  ({                                         \
    register const struct timespec *__to __asm ("r10") = timeout;          \
    int __status;                                \
    register __typeof (val) _val __asm ("edx") = (val);                \
    __asm __volatile ("syscall"                            \
             : "=a" (__status)                         \
             : "0" (SYS_futex), "D" (futex),                 \
           "S" (__lll_private_flag (FUTEX_WAIT, private)),         \
           "d" (_val), "r" (__to)                    \
             : "memory", "cc", "r11", "cx");                 \
    __status;                                    \
  })

上記アセンブラは大体以下のような意味3 

futex(futex, FUTEX_WAIT, val, timeout, NULL, 0);  // 便宜上、上記コードの引数の変数名をそのままつかっているが、
                                                  // 1つめのfutexはシステムコールのfutexで、
                                                  // 2つめは引数のpthread_cond_tの__futexメンバ変数のアドレス

futex() システムコールは、 指定したアドレスの値が変更されるのをプログラムが待つ手段や 特定のアドレスに対して待機中のプロセスを wake (起床) させる手段を提供する

futex(2) http://linuxjm.sourceforge.jp/html/LDP_man-pages/man2/futex.2.html

とのこと。

まとめ

  • pthread_cond_waitをつかったもののほうが普通は高速なはず
  • memcachedのようなやりかただとユーザプロセス側でスレッドプール管理のための排他制御がほとんど不要になるので多少実装が簡単か

  1. pthread_cond_waitはunixの場合。windowsの場合はpSleepConditionVariableCS、これが使えない場合は疑似的に同様の動作をするようなラッパを定義している。 ↩

  2. memcachedでは使用してないが、libeventはシグナルを通知する際もfdをつかう。Boost.Asioもシグナル通知はpipeを経由する。 ↩

  3. 厳密には違う。 ↩

オーバーフローしにくい組み合わせの数の計算方法

October 17, 2013 at 09:13 PM | categories: algorithms, programming |

Cで組み合わせの数を計算するときに定義通り計算するとすぐにオーバーフローしてしまう。 例えば以下のような実装だと、 程度でも結果がおかしくなってしまう。

#include <iostream>

using namespace std;

uint64_t fac(uint64_t n) {
    if (n > 1)
        return n * fac(n-1);
    else
        return 1;
}

uint64_t combinations(uint64_t n, uint64_t k) {
    return fac(n) / (fac(k) * fac(n-k));
}

int main(int argc, char *argv[]) {
    cout << combinations(5, 3) << endl; // => 10
    cout << combinations(10, 5) << endl; // => 252
    cout << combinations(20, 10) << endl; // => 184756
    cout << combinations(30, 15) << endl; // => 0 !?
    return 0;
}

とりあえず素因数分解してやれば解決するのでいままでそうしてたのだけど、もっとかっこいい方法がないものかと思って探してみたらKnuth先生の本で以下のようなアルゴリズムが紹介されているらしい。1 これはかっこいい。

uint64_t combinations2(uint64_t n, uint64_t k) {
    uint64_t r = 1;
    for (uint64_t d = 1; d <= k; ++d) {
        r *= n--;
        r /= d;
    }
    return r;
}

int main(int argc, char *argv[]) {
    cout << combinations2(30, 15) << endl; // => 155117520
    cout << combinations2(60, 30) << endl; // => 118264581564861424

    cout << combinations2(64, 32) << endl; // これはオーバーフローする
    return 0;
}

結果の値が範囲内ならオーバーフローしないのか、というとそういうわけではないけどナイーブな実装に比べるとずっと計算できる範囲が広いので、値のレンジがあらかじめわかっているのであればこれで十分ですね。

  1. http://stackoverflow.com/questions/1838368/calculating-the-amount-of-combinations 残念ながらvol2は手元にはない ↩

C言語でtuple

July 10, 2013 at 09:02 PM | categories: C, programming |

Cをつかってるとtupleっぽいものがあれば便利なのに、と思うときが時々あります。

別にtupleなんてなくても

typedef struct {
   char *s;
   int *i;
} tuple;

のようにして構造体をつかえばいいのですが、必要になるたびにこれをするのはちょっとめんどくさいですよね。

というわけで色々試行錯誤してみたところ、以下のようにしてunionの配列にするというのがそこそこ便利だったので紹介します。

以下は使用例です。

#include <stdio.h>

typedef union {
    void *p;
    char *s;
    int i;
    char c;
} tuple_u;
typedef tuple_u tuple[2];

int main(int argc, char *argv[]) {
    tuple t = { { .s = "hoge" }, { .i = 123 } };

    printf("%s, %d\n", t[0].s, t[1].i);
    return 0;
}

C99のdesignated initializerをつかえば初期化もまあそこそこ書きやすいし、型の組み合わせもある程度柔軟にできます。

C++ではなくあえてCをつかうような人の多くは独自のコンテナライブラリのようなものをもってると思いますが、上記のようなtupleがあれば便利な場面は結構あるのではないかと思います。

The P Convention

February 24, 2013 at 02:42 PM | categories: lisp, programming |

lisp

Lispには'p'という接尾辞がつく名前の関数があるが、この'p'はpredicateのこと。

The -P Convention

ところが、HaskellやOCamlにも'p'という接尾辞がつく関数があって、そちらはprimeの意味で使うらしい。 シングルクオート(ダッシュ)記号は英語だとprimeというので、例えばfoo'という名前の関数はfooという名前のヘルパー関数的なもの、ということになる。

“foop”: a naming convention? It's a helper recursive function for “foo”; what does the suffix “p” mean?

ちなみに、OCamlだとシングルクオートが識別子につかえるのでfoo'という名前の関数も結構あるらしい。

まぎらわしい、かと思ったけど使う文脈が違うし意外とそうでもないか。

人気プログラミング言語ランキング(stackoverflow調べ)

February 05, 2013 at 11:00 PM | categories: programming |

stack

なんとなく気になったのでstackoverflowのでの人気プログラミング言語ランキングをつくってみました。(2013-02-05現在)

1.   c#              411382pt
2.   java            361120pt
3.   php             337941pt
4.   javascript      321791pt
5.   c++             175790pt
6.   python          160796pt
7.   html            145373pt
8.   objective-c     119891pt
9.   sql             115147pt
10.  css             113039pt
11.  c               83501pt
12.  ruby            64350pt
13.  xml             56444pt
14.  regex           51670pt
15.  vb.net          41260pt
16.  html5           27217pt
17.  linq            26200pt
18.  actionscript-3  24286pt
19.  perl            24092pt
20.  r               23256pt
21.  delphi          18866pt
22.  tsql            18119pt
23.  matlab          15289pt
24.  xaml            14115pt
25.  scala           13444pt
26.  vba             12300pt
27.  css3            11564pt
28.  xslt            11032pt
29.  haskell         9827pt
30.  assembly        7580pt
31.  razor           7385pt
32.  actionscript    6440pt
33.  excel-vba       6309pt
34.  groovy          5551pt
35.  vbscript        4926pt
36.  c++11           4894pt
37.  vb6             4886pt
38.  xhtml           4675pt
39.  plsql           4548pt
40.  svg             4540pt
41.  f#              4341pt
42.  python-3.x      4229pt
43.  awk             3481pt
44.  wsdl            3249pt
45.  lua             3183pt
46.  erlang          3077pt
47.  coffeescript    2754pt
48.  c#-3.0          2615pt
49.  latex           2570pt
50.  lisp            2395pt
51.  mathematica     2395pt
52.  prolog          2317pt
53.  scheme          2199pt
54.  uml             2093pt
55.  applescript     2092pt

-- 次点

go         1648pt
ocaml      1329pt
d          877pt

補足

  • stackoverflow APIを利用して調べました。stackoverflow公式のものではありません。
  • ランキングは質問につけられたタグの件数順です。
  • プログラミング言語のタグは、tag infoのエントリに/language/i がマッチするかどうかで抽出し、明らかにプログラミング言語じゃないものは手動で適当に除外しました。
  • マークアップ言語とかバージョン違いで複数ある言語とか微妙なのはそのまま残しました。
  • 次点以下の言語は、apiをしばらくクロールしてもでてこなかった言語のうち思いついたものを手動でしらべました。

所感

C#が1位なのはちょっと意外でしたがそれ以外は大体イメージ通りでした。 質問が多い順でもあるので、下位にある言語は質問が少なくて逆にイケてると言えなくもないですね。

D言語すばらしい。

ともあれ、stackoverflowのAPIは結構充実してるので色々遊べそうです。

About Me

pic
mojavy

Recent posts



Categories

Badges