Think Distributed

Database and Distributed Systems

Erlang OTP 18 の Mailbox を理解する

プロセスのデータ構造

struct process(Process) にはフィールドが多すぎるため、message passing (とメモリ管理)に関係ないフィールドは除外している点に注意。メッセージパッシングで関係するのは、

  • ErlMessageQueue msg
    • プロセスが内部的に保持しているキュー。
    • erlang の資料に出てくる mailbox はこれを指す。
    • プロセスがメッセージを取得する時はこちらのキューから取る。
  • ErlMessageQueue msg_inq
    • sender がメッセージを置くためのキュー。
    • SMP が有効になっている時だけ使われる。
  • erts_proc_lock_t lock
    • プロセスのロック状態を保持する。
    • プロセス全体のロック、内部のキューだけのロックなど1つのフィールドで複数のロックを表現できる。
struct process {
    ErtsPTabElementCommon common; /* *Need* to be first in struct */
    ErlMessageQueue msg;    /* Message queue */  
    ErlHeapFragment* mbuf;  /* Pointer to message buffer list */
    Uint mbuf_sz;       /* Size of all message buffers */
    erts_smp_atomic32_t state;  /* Process state flags (see ERTS_PSFLG_*) */
    ErlMessageInQueue msg_inq;
    ErtsPendExit pending_exit;
    erts_proc_lock_t lock;
    erts_smp_atomic_t run_queue;
};

otp/erl_process.h at 1283ca3bc4bba3381f8fd1f59fb62780d3e17472 · erlang/otp · GitHub

メッセージ送信

VM がメッセージを送信するコードは以下のようになっている。erl_send がメッセージを送信するための関数。

 OpCase(send): {
     BeamInstr *next;
     Eterm result;

     PRE_BIF_SWAPOUT(c_p);
     c_p->fcalls = FCALLS - 1;
     reg[0] = r(0);
     result = erl_send(c_p, r(0), x(1));
     PreFetch(0, next);
     ERTS_VERIFY_UNUSED_TEMP_ALLOC(c_p);
     ERTS_SMP_REQ_PROC_MAIN_LOCK(c_p);
     PROCESS_MAIN_CHK_LOCKS(c_p);
     if (c_p->mbuf || MSO(c_p).overhead >= BIN_VHEAP_SZ(c_p)) {
     result = erts_gc_after_bif_call(c_p, result, reg, 2);
     r(0) = reg[0];
     E = c_p->stop;
     }
     HTOP = HEAP_TOP(c_p);
     FCALLS = c_p->fcalls;
     if (is_value(result)) {
     r(0) = result;
     CHECK_TERM(r(0));
     NextPF(0, next);
     } else if (c_p->freason == TRAP) {
     SET_CP(c_p, I+1);
     SET_I(c_p->i);
     SWAPIN;
     r(0) = reg[0];
     Dispatch();
     }
     goto find_func_info;
 }

メッセージをキューに積むコードは以下のようになっている。長い関数なので途中は相当端折っている。

#ifndef ERTS_SMP
    res = receiver->msg.len;
#else
    res = receiver->msg_inq.len;
    if (*receiver_locks & ERTS_PROC_LOCK_MAIN) {
    /*
     * We move 'in queue' to 'private queue' and place
     * message at the end of 'private queue' in order
     * to ensure that the 'in queue' doesn't contain
     * references into the heap. By ensuring this,
     * we don't need to include the 'in queue' in
     * the root set when garbage collecting.
     */
    res += receiver->msg.len;
    ERTS_SMP_MSGQ_MV_INQ2PRIVQ(receiver);
    LINK_MESSAGE_PRIVQ(receiver, mp);
    }
    else
#endif
    {
    LINK_MESSAGE(receiver, mp);
    }

otp/erl_message.c at 1283ca3bc4bba3381f8fd1f59fb62780d3e17472 · erlang/otp · GitHub

ERTS_PROC_LOCK_MAIN (プロセス全体のロック)が取れている時は直接 PRIVQ にメッセージを置いてしまう。ERTS_SMP_MSGQ_MV_INQ2PRIVQmsg_inqmsg のキューにすべて移動するマクロ。LINK_MESSAGE_PRIVQ はメッセージを PRIVQ の最後に追加するマクロ。

一方で、ERTS_PROC_LOCK_MSGQ (msg_inq に対するロック)しか取れていない時は msg_inq にメッセージを置く。LINK_MESSAGEmsg_inq の最後にメッセージをリンクするマクロ。

otp/erl_message.h at 1283ca3bc4bba3381f8fd1f59fb62780d3e17472 · erlang/otp · GitHub

Linux でメモリ帯域の利用状況を測定する

perf/x86/uncore: add support for SNB/IVB/HSW integrated memory controller PMU [LWN.net]

上記 URL で説明されていますが、Intel の IvyBridge などちょっと前のアーキテクチャでは perf でメモリ帯域の利用状況が確認できます。Hardware Performance Counter を使っているため、環境によっては取得できないので注意してください。perf list で自分の環境で使える event 一覧が見られるのでそれで確認してください。

perf を使って以下のコマンドを叩くと統計が取得できます。

$ sudo perf stat -a -e 'uncore_imc/data_reads/,uncore_imc/data_writes/' -I 1000 sleep 5
#           time             counts unit events
     1.000095560         262,143.41 MiB  uncore_imc/data_reads/
     1.000095560              12.06 MiB  uncore_imc/data_writes/
     2.000314132               0.00 MiB  uncore_imc/data_reads/
     2.000314132               8.25 MiB  uncore_imc/data_writes/
     3.000480806               0.00 MiB  uncore_imc/data_reads/
     3.000480806               7.49 MiB  uncore_imc/data_writes/
     4.000651614               0.00 MiB  uncore_imc/data_reads/
     4.000651614              19.56 MiB  uncore_imc/data_writes/
     5.000839460               0.00 MiB  uncore_imc/data_reads/
     5.000839460               9.58 MiB  uncore_imc/data_writes/
     5.001142524           1,024.05 MiB  uncore_imc/data_reads/
     5.001142524               0.17 MiB  uncore_imc/data_writes/

たまに uncore_imc/data_reads/ がものすごく大きな値になるのが何が要因なのか分からず…。

ちなみに、uncore_imc/data_reads/, uncore_imc/data_writes/Intel のドキュメントは以下の URL にあります。

Monitoring Integrated Memory Controller Requests in the 2nd, 3rd, 4th, 5th, 6th generation Intel® Core™ processors | Intel® Software

Erlang OTP 18 の binary メモリアロケーション

OTP 18 ではメモリアロケーターとして以下の実装がサポートされている。

  • GOODFIT
    • 空き領域をサイズ範囲でいくつかに分割し、要求されたサイズに近いブロックから空きブロックを探す。
    • 見つからなかったら次に大きなサイズ範囲の領域を探す。
    • 探索する時の探索の深さに制限が付いているという意味で GOODFIT。
  • BESTFIT
    • サイズ順にソートされた空き領域から指定したサイズと最も近いブロックを探してそれを返す。
    • オプションでアドレス順序にソートするか、ブロックサイズでソートするかが選べる。
  • AFIT
    • テンポラリなアロケーションをする時に使う。
    • 空き領域の先頭だけ見て、それが使えるならそれを返し、使えなければ新しいキャリアを作って返す。
  • AOFIT
    • BESTFIT と同じような作りで、空き領域のソート順がアドレス順になっている点が違う。
    • サイズに合う最初に見つかった空きブロックを返す。
    • デフォルト無効
    • test_allocator というのでしか使われていない。test_allocator はドキュメントにも出てこない(?)

OTP 18 で binary のメモリアローケータとしてはベストフィットアロケーターが使われている。

Erlang OTP 18 の crc32

OTP 18 の CRC 実装は zlib の crc32 を利用した実装となっている。

otp/erl_bif_chksum.c at 1283ca3bc4bba3381f8fd1f59fb62780d3e17472 · erlang/otp · GitHub

zlib の crc32 は lookup table を使ったよくある実装になっている。SSE で定義されている _mm_crc32_u32 などの CPU 命令は使われていない。

otp/crc32.c at 1283ca3bc4bba3381f8fd1f59fb62780d3e17472 · erlang/otp · GitHub

ちなみに、ffmpegCRC はどうなっているかというと、以下のブログの ffmpeg contributor の人の実装になっている。

Lair Of The Multimedia Guru » Fast CRC

FFmpeg/crc.c at a0ac49e38ee1d1011c394d7be67d0f08b2281526 · FFmpeg/FFmpeg · GitHub

Erlang OTP 18 の maps の内部実装

Erlang の maps は hashmap なのかと思っていたけどもう少し複雑な実装になっていた。maps の内部実装には

  1. flatmap: キー一覧と値一覧を別々に配列として持つ
  2. hashmap: いわゆるハッシュマップ

の 2 つがあり、エントリの数によって実装が切り替わる仕組みとなっている。エントリ数が 32 を越えるまでは flatmap で、それ以上になると hashmap が使われるようになる。

切り替えのしきい値は以下のコードを参照。

otp/erl_map.h at 1283ca3bc4bba3381f8fd1f59fb62780d3e17472 · erlang/otp · GitHub

よって、小規模な maps に対する maps:get は単純な linear search になるため平均計算量は O(N)、最悪計算量 は O(N) となる。最悪計算量は hashmap を使っても変わらない。

エントリの数が小規模な場合に hash 計算してしまうのと flatmap で検索するのだとどちらが効率的なのかよく分からないけども、

otp/utils.c at 1283ca3bc4bba3381f8fd1f59fb62780d3e17472 · erlang/otp · GitHub

を見るに、 box 化されていない erlang term(e.g.: tuple などの複雑なデータ)に対する hash 計算はコストが高そうに見える。

文字列に対するハッシュ関数

UNIX プログラミングテクニックという本を10年ぶりぐらいに読み返していたら、文字列に対するハッシュ関数として以下の関数が紹介されていた。Wikipedia によるとどうもこれは ELF で使われているハッシュ関数でもあるらしい。

#include <stdio.h>

unsigned long hashpjw(char *s) {
  char *p;
  unsigned long h = 0;
  for (p = s; *p; p++) {
    h = (h << 4) + (*p);
    unsigned long g = 0;
    if ((g = h) & 0xF0000000) {
      h ^= g >> 24;
      h ^= g;
    }
  }
  return h;
}

int main() {
  printf("%zd\n", hashpjw("abcd"));
  printf("%zd\n", hashpjw("abcdef"));
  printf("%zd\n", hashpjw("abcdefg"));
  printf("%zd\n", hashpjw("abcdefgh"));
  return 0;
}