Saturday, December 13, 2014

C言語で可変長引数をとる関数を、型安全に書く方法

C言語の可変長引数は、型安全でない(まちがった型の引数を渡してもコンパイルエラーにならない)とされています。これは言語仕様の理解としては正しいのですが、特定の型の引数を任意の個数とる関数に限っては、マクロを使うことで型安全性を確保することができます

任意の個数のdoubleを引数にとり、その和を返す関数「sumf」を例にあげて説明します。

C言語の可変長引数機構を使ってsumfを定義すると、以下のようになります。
#include <math.h>
#include <stdarg.h>
#include <stdio.h>

static double sumf(double nfirst, ...)
{
  double r = 0, n;
  va_list args;

  va_start(args, nfirst);
  for (n = nfirst; ! isnan(n); n = va_arg(args, double))
    r += n;
  va_end(args);

  return r;
}

int main(int argc, char **argv)
{
  printf("%f\n", sumf(NAN)); /* => 0 */
  printf("%f\n", sumf(1., NAN)); /* => 1 */
  printf("%f\n", sumf(1., 2.5, 3., NAN)); /* => 6.5 */
  return 0;
}
が、この定義には「NANを終端に使っているがために、NANを引数として渡すことができない(=終端を表す値が必要になる)」「型安全でない」という2点の問題があります。後者については、たとえば、sumf(1, 1, NAN)のように、うっかりdouble型以外の引数を渡してしまってもコンパイルエラーにならず、ただ結果がおかしくなったりコアダンプしたりすることになります注1

では、どのようにsumfを定義すれば良いのでしょう。答えを書いてしまうと、こんな感じです。
#include <stdio.h>

#define sumf(...)                                       \
  _sumf(                                                \
    (double[]){ __VA_ARGS__ },                          \
    sizeof((double[]){ __VA_ARGS__ }) / sizeof(double)  \
  )

static double _sumf(double *list, size_t count)
{
  double r = 0;
  size_t i;

  for (i = 0; i != count; ++i)
    r += list[i];

  return r;
}

int main(int argc, char **argv)
{
  printf("%f\n", sumf()); /* => 0 */注2
  printf("%f\n", sumf(1.)); /* => 1 */
  printf("%f\n", sumf(1., 2.5, 3)); /* => 6.5 */
  return 0;
}
この定義では、可変長の引数群をマクロを用いてインラインで配列として初期化し、かつ、その要素数をsizeof演算子を用いて計算しています。そのため、C言語標準の可変長引数機構を使った場合の問題はいずれも発生しません。要素数が_sumf関数に引数countとして渡されるため、終端を表す特殊な値は必要になりませんし、また、実引数はdouble型の配列として呼出側で構築されるため、誤った型の引数を渡してしまうとコンパイルエラーになります。あるいは、たとえばint型の値を渡してしまった場合は、コンパイラによってdouble型に昇格することになるからです。

私たちが開発しているHTTPサーバ「H2O」では、この手法を用いて、型安全な文字列結合関数h2o_concatを定義、使用しています。

以上、H2Oで使っているC言語の小ネタ紹介でした。

※この記事はH2O Advent Calendar 2014の一部です。

注1: 手元の環境だと、sumf(1, 1, NAN)の結果は1となります
注2: 可変長マクロに対して0個の引数を渡すのはC99の規格には違反しますが、GCCやClangは問題なく処理します

Monday, December 8, 2014

64bit時代のバッファ処理

プログラミングの「常識」は時代とともに変化します。そのひとつが、サーバプログラムにおけるバッファ処理です。

1990年代後半から2010年頃までは、メモリ空間の大きさ(32bitすなわち4GB注1)を超える大きさのファイルを扱う時代でした。このため、httpdなどのサーバプログラムにおいても、入出力データをいったんテンポラリファイルとしてバッファリングする必要がありました。ですが、ファイルI/Oはメモリアクセスと比べると低速です。このため、小さなサイズのデータについてはメモリアクセスする一方で、大きなサイズのデータについてはファイルI/Oを用いる、という煩雑なコードを書く必要がありました。

しかし、2014年も暮れとなる今 、サーバサイドにおいては64bit環境のみを考えれば良い時代に入りつつあります。

もちろん、64bit環境といったところで、64bit空間の全てをユーザプロセスが使えるわけではありません。現行のx86-64 CPUがサポートする論理アドレス空間は48bit(256TB相当)であり、多くのOSではその上位アドレス半分がカーネル空間に割り当てられ、残った128TBがユーザプロセスで使用可能な空間となっています注2

128TBものメモリ空間があれば、全てのテンポラリデータを「メモリ空間にマッピングして」使用することができます。

実際に、H2Oのバッファ処理では、64MBを超えるものについてはテンポラリファイルをftruncate/mmapすることで領域を確保注3し、これに対してメモリアクセスを行うようになっています。詳しくはh2o_buffer_reserve関数の定義をご覧ください。

バッファを利用する側のコードにおいては、サイズの大小に関係なく単なるメモリブロックとしてアクセスできるため、コードが単純かつ高速になるのです。

※本記事はH2O Advent Calendar 2014の一部です。

注1: 多くのOSにおいては、カーネルとメモリ空間を分け合う必要があるため、実際にユーザプロセスで使用できるメモリ空間は1GB〜3GB程度でした
注2: 参照: x86-64 - Wikipedia, the free encyclopedia - Operating system compatibility and characteristics
注3: malloc(3)で確保可能なメモリの総量である物理メモリ+スワップ領域の和は必ずしも十分に大きくないため、テンポラリファイルを生成してftruncateすることでディスク上に必要な領域を確保しています

Q. 条件分岐や算術演算を使わずに、max(a,b) を計算するプログラムを書けますか?

if文(条件分岐)を使わず、max(a, b) を計算 別解 | 津田の開発な日記」に関連した話です。リンク先のブログ記事では、条件分岐を使わずにmax(a,b)を実装する方法が議論されています。

では、更に条件を厳しくして、「条件分岐も算術演算も使わずに」max(a,b)を実装することはできるでしょうか?























なぜ、「もちろん」なのか。CPUは、ANDやOR、NOTのようなデジタルな論理回路から構成されています。であれば、当然、ビット演算(ビットシフトと&, |, ^)を使って、max(a, b)を実装することも可能なわけです。こんな感じ。

#include <stdio.h>

#define BIT(n, pos) (((n) >> (pos)) & 1)

static int mymax(int a, int b)
{
  int islt = BIT(a, 31) & (BIT(b, 31) ^ 1);
  int iseq = BIT(a, 31) ^ BIT(b, 31) ^ 1;

#define CHECK_BIT(pos) do { \
  islt |= iseq & (BIT(a, pos) ^ 1) & BIT(b, pos); \
  iseq &= BIT(a, pos) ^ BIT(b, pos) ^ 1; \
} while (0)

  CHECK_BIT(30); CHECK_BIT(29); CHECK_BIT(28);
  CHECK_BIT(27); CHECK_BIT(26); CHECK_BIT(25); CHECK_BIT(24);
  CHECK_BIT(23); CHECK_BIT(22); CHECK_BIT(21); CHECK_BIT(20);
  CHECK_BIT(19); CHECK_BIT(18); CHECK_BIT(17); CHECK_BIT(16);
  CHECK_BIT(15); CHECK_BIT(14); CHECK_BIT(13); CHECK_BIT(12);
  CHECK_BIT(11); CHECK_BIT(10); CHECK_BIT(9); CHECK_BIT(8);
  CHECK_BIT(7); CHECK_BIT(6); CHECK_BIT(5); CHECK_BIT(4);
  CHECK_BIT(3); CHECK_BIT(2); CHECK_BIT(1); CHECK_BIT(0);

#undef CHECK_BIT

  /* extend flag to 32-bit mask */
  islt <<= 31;
  islt >>= 31;

  return (a & (islt ^ 0xffffffff)) | (b & islt);
}

int main(int argc, char **argv)
{
  int a, b;

  if (argc != 3) {
    fprintf(stderr, "Usage: %s a b\n", argv[0]);
    return 1;
  }
  if (sscanf(argv[1], "%d", &a) != 1) {
    fprintf(stderr, "%s is not a number\n", argv[1]);
    return 1;
  }
  if (sscanf(argv[2], "%d", &b) != 1) {
    fprintf(stderr, "%s is not a number\n", argv[2]);
    return 0;
  }

  printf("max(%d,%d) is %d\n", a, b, mymax(a, b));

  return 0;
}


なぜHTTPSはHTTPより速いのか

先週、httpvshttps.com というウェブサイトが公開されました。このウェブサイトでは、HTTP と HTTPS を用いてアクセスした場合のウェブページのダウンロード完了までにかかる時間の比較ができるのですが、多くの環境で HTTPS の方が HTTP よりも高速なことに驚きの声が上がっていました。

HTTP が TCP 上で平文を送受信するのに対し、HTTPS は TCP 上で TLS (SSL) という暗号化技術を用いて通信を行います。ならば、TLS のオーバーヘッドのぶん HTTPS のほうが遅いはずだ、という予測に反する結果になったのですから、驚くのも無理はありません。

実は、この結果にはからくりがありました。

Google Chrome、Mozilla Firefox、最近のSafari注1は、Google が開発した通信プロトコル「SPDY」に対応しており、HTTPS の通信においてはHTTP/1.1 ではなく SPDY を TLS 上の通信プロトコルとして利用します。

HTTP/1.1 は20年近く前に標準化された技術であり、今日では様々な限界が指摘されるようになってきています。そのうち最大の問題が、ウェブブラウザ上において、現在ダウンロード中のファイルのダウンロードが完了するまで次のファイルのダウンロード要求を送信できないという問題です。クライアントとサーバ間を通信が往復するには、数十ミリ秒から数百ミリ秒という時間がかかります(この時間は、ラウンドトリップタイム (RTT) と呼ばれます)。

ウェブブラウザが、第一のファイルのダウンロードを完了した直後に第二のファイルのダウンロード要求をサーバに送信したとしても、その中身が届き始めるのは、このラウンドトリップタイムが経過した後になります。その間、サーバからクライアント方向の通信回路は無駄に遊んでいることになります。

httpvshttps.com のような、小さな画像ファイルを多数ダウンロードするウェブページでは(これは多くのウェブサイトに見られる一般的な特徴です)、この無駄が占める割合が大きくなるのです(ウェブブラウザの動作としては、リクエストを送信後、RTTが経過するまでじっと待ち、その後一瞬でファイル受信が完了、直後に次のリクエストを送信し、RTT が経過するまでじっと待つ…を繰り返す形になります)。

一方、SPDY はこれら HTTP/1.1 が抱える問題を改善しようとする Google の試みとして開発が進んできたプロトコルであり、多数のファイルを並行してダウンロードすることが可能となっています。HTTP/1.1 のように、ファイルの到着を待つだけの時間は発生しません。

この違いが、暗号化のオーバーヘッドがあるにも関わらず、HTTPS のウェブページの方が HTTP より速くダウンロードが完了することの原因なのです。


■この傾向は今後も続くのか

SPDY は Google が開発した実証実験的な性格の強いプロトコルでした。そこから得られた成果をもとに、現在、HTTP/2 という次世代の HTTP プロトコルの標準化が進められており、はやければあと数週間で標準化される見込みとなっています。

HTTP/2 プロトコルの標準化案自体は HTTP でのアクセスにおいても HTTPS でのアクセスにおいても利用可能なものとなっています。ですが、多くのウェブブラウザはHTTPS でのアクセスにおいてのみ、HTTP/2 を有効化する公算が高くなっています注2

このため、HTTPS の方が HTTP よりも高速である、という状況は今後とも続くと考えられます。

■HTTPS のサーバ負荷はどうなのか

HTTPS に対する事業者の不安としては、ダウンロード速度に加えてもう一点、サーバ負荷の問題をあげることができます。暗号化を導入することで、サーバの負荷が増大するのではないか。

筆者らが開発している、高速なHTTPサーバであるH2Oでは…(続く)

本記事は HTTP2 Advent Calendar 2014 および H2O Advent Calendar 2014 の一部です。筆者体調不良により遅延&書きかけの状態ですみませんすみません。

注1: YosemiteまたはiOS 8上で動作するものに限る
注2: 参照: (HTTP/2標準化ワークグループ座長のブログ記事, https://wiki.mozilla.org/Networking/http2

Monday, December 1, 2014

Improving Parser Performance using SSE Instructions (in case of PicoHTTPParser)

PicoHTTPParser is a tiny but very fast HTTP parser library known for its use by many Perl applications. In the slides I used last month, I suggested it could be even faster if SIMD instructions were used. Now the feature is available thanks to @herumi.

The library now uses the PCMPESTRI instruction which is part of SSE 4.2, running 68% to 90% faster.

Benchmarkclang -O3clang -O3 -msse4.2Improvement
bench.c2,181,0254,140,787+90%
fukamachi.c3,213,4405,400,064+68%

PCMPxSTRx is a SIMD instruction that can be used for parsing text. In _SIDD_CMP_RANGES mode, it checks at most 16 bytes at once, if each byte is within given set of ranges. Herumi and I have created a wrapper function for the instruction named findchar_fast that iterates though every 16 bytes of a given buffer to find the first occurrence of a byte within a set of given ranges.

And the function is merged neatly into the parser; the code below at first uses the SIMD function to look for a control character (the match condition is defined as ranges1), then falls back to the non-SIMD code to handling up to 15 remaining characters (that cannot be processed by the SIMD function due to out-of-bounds access).
#ifdef __SSE4_2__
  static const char ranges1[] =
    "\0\010"
    /* allow HT */
    "\012\037"
    /* allow SP and up to but not including DEL */
    "\177\177"
    /* allow chars w. MSB set */
    ;
  int found;
  buf = findchar_fast(buf, buf_end,
                      ranges1, sizeof(ranges1) - 1,
                      &found);
  if (found)
    goto FOUND_CTL;
#endif
  /* code that handles the input byte-by-byte */
To summarize, PCMPxSTRx is an excellent instruction for performance that can be cleanly integrated into existing parsers (tokenizers). Hopefully we will see performance improvements in various parsers in the future through the use of the instruction.

This blog post has been written as part of the H2O Advent Calendar.

Wednesday, November 5, 2014

[memo] Installing nghttp2 onto OSX

Following the steps below should install nghttp2 with all of its useful apps for testing into /usr/local/http2-15 of your OS X machine.

-- openssl
% wget --no-check-certificate https://www.openssl.org/source/openssl-1.0.2-beta3.tar.gz
% tar xzf openssl-1.0.2-beta3.tar.gz
% cd openssl-1.0.2-beta3
% KERNEL_BITS=64 ./config shared enable-ec_nistp_64_gcc_128 --prefix=/usr/local/http2-15
% make
% make install

-- libevent
% wget https://github.com/downloads/libevent/libevent/libevent-2.0.21-stable.tar.gz
% CFLAGS=-I/usr/local/http2-15/include CXXFLAGS=-I/usr/local/http2-15/include LDFLAGS=-L/usr/local/http2-15/lib ./configure --prefix=/usr/local/http2-15
% make
% make install

-- zlib-1.2.8
% wget http://zlib.net/zlib-1.2.8.tar.gz
% tar xzf zlib-1.2.8.tar.gz
% cd zlib-1.2.8
% ./configure --prefix=/usr/local/http2-15
% make
% make install

--  spdylay
% git clone https://github.com/tatsuhiro-t/spdylay.git
% cd spdylay
% (cd m4 && wget http://keithr.org/eric/src/whoisserver-nightly/m4/am_path_xml2.m4)
% autoreconf -i
% PKG_CONFIG_PATH=/usr/local/http2-15/lib/pkgconfig ./configure --prefix=/usr/local/http-15
% make
% make install

-- nghttp2
% git clone https://github.com/tatsuhiro-t/nghttp2.git
% cd nghttp2
% (cd m4 && wget http://keithr.org/eric/src/whoisserver-nightly/m4/am_path_xml2.m4)
% autoreconf -i
% PKG_CONFIG_PATH=/usr/local/http2-15/lib/pkgconfig ./configure --prefix=/usr/local/http2-15 --enable-app --disable-threads
% make
% make install

note: I have gathered this from my command history. Please forgive me if any of them are wrong.
EDIT: added libevent as pointed out by @tatsuhiro-t.

Tuesday, November 4, 2014

The internals H2O (or how to write a fast server)

Yesterday, I had the opportunity to speak at the HTTP2Conference held in Tokyo.

Until now, I have rather been silent about H2O since I think it is still premature for wild use. But you do not need to worry about such thing in a technology conference, so I happily talked about the motives behind H2O, and its implementation.

IMO the talk should be interesting not only to people working with HTTP server implementations but also to those interested in programming in general, since it covers the common performance pitfalls (or misconceptions as I see) in many server implementations.

Below are the slides and the recorded video of my presentation.

Enjoy!

PS. Please forgive me for the provocative attitude in the questions raised in the last part of the slides. They were intentionally written as such in order to spark discussion at the hall.



my talk starts a 3h15m (in Japanese)

Related links: