Friday, February 7, 2014

Why asm.js sometimes runs faster than hand-written JavaScript (and the changes in JSX 0.9.77)

I have released an update (version 0.9.77) of JSX - a statically-typed altJS programming language with an optimizing compiler to JavaScript, with the following changes:

  • the definition of int has been changed to strict 32-bit signed integer
  • introduce Promise class in conformance to the ECMAScript 6 draft

The second change should be obvious. Let me explain the reasoning behind the first one.

Background:

Until now, definition of int in JSX has been: a number that is at least possible to represent integers between -231 to 231-1, or may or may not become NaN or +-Infinity.

This was based on our understanding that enforcing integer arithmetic in JavaScript (i.e. using | 0) would lead to slower execution speed. We wanted the int type of JSX to represent some kind of integral numbers without sacrificing execution speed. And the type had been defined as such.

But the advent of asm.js has changed the game. Such enforced integer arithmetic is one of the most common patterns found in JavaScript generated by Emscripten (since it compiles C/C++ code), and it would be natural to expect that existing JavaScript runtimes would optimize against such patterns.

The Benchmark:

So I decided to take time to run a tiny benchmark that compares the execution speed of ordinary arithmetic vs. enforced integer arithmetic on fib-using-int - jsPerf, and the results are interesting.

The benchmark compares three functions calculating Fibonacci numbers using loops.

// original
function fib(n) {
  var value = 1, prev = 1;
  for (var i = 1; i < n; ++i) {
    var t = prev;
    prev = value;
    value += t;
  }
  return value;
}

// core operation is enforced integer arith.
function fib(n) {
  var value = 1, prev = 1;
  for (var i = 1; i < n; ++i) {
    var t = prev;
    prev = value;
    value = (value + t) | 0;                <--- HERE
  }
  return value;
}

// core operation and loop are integer arith.
function fib(n) {
  n = n | 0;                                <--- HERE
  var value = 1, prev = 1;
  for (var i = 1; i < n; i = (i + 1) | 0) { <--- HERE
    var t = prev;
    prev = value;
    value = (value + t) | 0;                <--- HERE
  }
  return value;
}

Looking at the results below (please refer to the benchmark page for the latest numbers) the fact is that code runs about 10% faster on Chrome and Firefox when explicitly specifying an extra operation (i.e. | 0).


This is not a surprise for people with the understanding of how the JIT (just-in-time-compile) engines of the runtimes work. The engines compile arithmetic operations in the original function of the benchmark into integer arithmetics with guards, so that the calculation can be changed to use floating-point operations once the numbers goes out of the 32-bit integer range. But if | 0 is added to the statement it becomes clear that the result of the arithmetic should be a module of 232 and thus that the guards become no longer necessary.

The Problem and the Solution:

The problem being left is how to write code that takes benefit from such optimizations. It is hard to add | 0 all over the source code, and there would be a negative performance impact unless you succeed in marking all of them correctly. It is once again clear that some kind of automated code generator is desirable for JavaScript, and this is the reason why we are happily applying the described change to JSX :-)

To summarize, JSX as of version 0.9.77 supports strict 32-bit integer arithmetic; and it is easy for the users to benefit from the described optimizations within the JavaScript runtimes. It's just a matter of marking some variables as : int. And the results of assignment to the variable as well as additions, subtractions, and multiplication between such variables would be int.


PS. I have also written the Fibonacci calculator in asm.js, but have excluded the numbers from the benchmark since it was too slow. It seems that there exists a non-marginal overhead when calling asm.js code from JavaScript.

Thursday, January 30, 2014

Q4M 0.9.12 has been released

Today I have released version 0.9.12 of Q4M - a message queue storage engine for MySQL.

As of the release, Q4M finally includes CMakeFiles.txt, file necessary for building Q4M together with MySQL 5.5 and above. The installation procedure is described in q4m.github.io/install.html.

Changelog is also available at the homepage. Have fun!

Tuesday, January 28, 2014

SSL/TLSライブラリの正しい使い方(もしくは、コモンネームの検証について)

スマホアプリの市場拡大に伴い、直接SSL/TLSライブラリを使用するプログラムを書く機会も増えてきている今日この頃かと思います。

SSL/TLSライブラリを使う際には、接続確立時にサーバの認証を正しく行う必要があります。具体的には、クライアントプログラムで以下の2種類の検証を行うことになります

  • SSL/TLSライブラリがサーバの証明書の検証に成功したこと
  • サーバの証明書に含まれるコモンネーム注1が接続しようとしたサーバと同一であること

前者については、OpenSSLの場合はSSL_CTX_set_verifyの引数にSSL_VERIFY_PEERを指定するなどして、ライブラリ側で処理を行わせることが可能です(証明書の検証に失敗した場合はSSL_connectがエラーを返します)。

一方、後者についてはSSL/TLSライブラリによって差があり、検証機能を有効にするために特別な呼出が必要だったり、あるいは検証機能を提供していないライブラリもあるため注意が必要です(これは、SSL/TLSが任意のストリームで安全な通信手段を確立するためのものであるのに対し、コモンネームの検証はTCP/IP+DNS上でSSL/TLSを使用する場合に必要となる作業である、という要件のズレによるものです)。

たとえば、OpenSSLはコモンネームの検証機能を提供していないので、アプリケーションプログラマが独自に同機能を実装する必要があります。具体的な方法はいくつかあるのですが、最も単純な形で以下のようになるかと思います注2

// returns non-zero value if the verification succeeds
static int verify_common_name_of_ssl(SSL* ssl, const char* hostname)
{
    X509* peer;
    X509_NAME* subject_name;
    char peer_name[256];

    peer = X509_get_peer_certificate(ssl);
    if (peer == NULL)
        return 0; // fail
    subject_name = X509_get_subject_name(X509_get_peer_certificate(ssl);
    if (subject_name == NULL)
        return 0; // fail
    if (X509_NAME_get_text_by_NID(subject_name, NID_commonName, peer_name, sizeof(peer_name)) == -1)
        return 0; // fail
    return strcasecmp(peer_name, hostname) == 0;
}

Android SDKを使っている場合は、公式ドキュメントに注意喚起と対応方法の説明があるので、そちらを参考にすれば良いかと思います(参照: Warnings About Using SSLSocket Directly - Security with HTTPS and SSL | Android Developers)。

iOSでSecure Transportを使っている場合は、SSLSetPeerDomainNameを呼び出して、ライブラリに検証を依頼することが推奨されています(参照: Secure Transport Reference)。

詳しくは、お使いのSSL/TLSライブラリのドキュメントを参照することをお勧めします注3

また、SSL/TLSを使用するアプリケーションのコードレビューや検証にあたっては、コモンネームの確認を行っているかを検証項目に含めることが望ましいと言えるでしょう。

注1: コモンネームとは、証明書に含まれる「www.google.com」等のホスト名のことです(参照: コモンネームとは何ですか - knowledge.verisign.co.jp
注2: ワイルドカード証明書への対応など、任意の証明書に対応する実装をするとなると泥沼が待っているかと思います(参照: WildcardCertificates - CAcert Wiki
注3: より高レベルな、ホスト名解決とTCP上でのSSL/TLS接続機能を一体として提供している類のライブラリにおいては、コモンネームの確認機能が組み込まれている場合が多いかと思います

Monday, January 27, 2014

JSX - experimental support for NPM

Based on @shibukawa-sans work, I have added experimental support for NPM-based packages in JSX 0.9.75. It is now possible to publish libraries for JSX using NPM (or use such packages from JSX).

A tiny example would be the following:

package.json:
{
  "dependencies": {
    "nodejs.jsx": "~ 0.1.1"
  }
}

hello-npm.jsx:
import "nodejs.jsx/*.jsx";

class _Main {
  static function main(args : string[]) : void {
    fs.appendFileSync("/dev/fd/1", "hello npm!\n");
  }
}

Running npm install would install nodejs.jsx (JSX binding for node.js) which is specified as a dependency in package.json. And when the compiler is executed (e.g. jsx hello-npm.jsx) it would automatically search for the imported files and use them in the node_modules directory.

For the time being, file specified in the main section of package.json is used if the name of a module is an argument to the import statement (e.g. import "npm-module-name"). Or the directory designated by the dependencies/lib section is searched if a file within an npm module is specified (e.g. import "npm-module-name/filename").

If you have any comments / suggestions please file a issue at the GitHub issues page.

Tuesday, January 21, 2014

Deflate (gzip) のアルゴリズムを視覚化してみた

DeflateとそのバリエーションであるZIPやgzipは、HTTPにおけるデータ転送やファイル圧縮など、様々な場面で使われる圧縮アルゴリズムです。

そのアルゴリズムの解説としてはslideshare.net/7shi/deflateを始め優れたものがいろいろあるかと思いますが、実際のデータをエンコードして視覚化できるものがないのが不満でした

というわけで、作った注1

ソースコードは、github.com/kazuho/visiflateにあります。

こいつをダウンロードして動かすと、記事の末尾の出力結果のようにダラダラと、どのようにエンコードされているかが表示されます。

この出力を見ることで、例えば、不思議の国のアリスのテキストをgzipすると

テキスト圧縮長
(ビット)
複製位置
"Alice was beginning to get very tired of sitt"224なし
"ing "1329バイト前
"by her"32なし
" si"1115バイト前
"st"9なし
"er "117バイト前
"on the bank, an"72なし
"d of "1342バイト前

のような感じにエンコードされることが分かります。

自分の好きなデータで試すことができて便利!という話でした。


PS. 以下は実行結果です。

% make
% gzip < alice.txt > alice.txt.gz
% ./puff -10 alice.txt.gz
puff() succeeded uncompressing 1328 bytes
8 compressed bytes unused
inpos=406,inbits=224,outpos=0,outbytes=45
    41 6c 69 63 65 20 77 61 73 20 62 65 67 69 6e 6e 69 6e 67 20 74 6f 20 67 65 74 20 76 65 72 79 20 74 69 72 65 64 20 6f 66 20 73 69 74 74
    A  l  i  c  e     w  a  s     b  e  g  i  n  n  i  n  g     t  o     g  e  t     v  e  r  y     t  i  r  e  d     o  f     s  i  t  t 

inpos=630,inbits=13,outpos=45,outbytes=4,distance=-29
    69 6e 67 20
    i  n  g    

inpos=643,inbits=32,outpos=49,outbytes=6
    62 79 20 68 65 72
    b  y     h  e  r 

inpos=675,inbits=11,outpos=55,outbytes=3,distance=-15
    20 73 69
       s  i 

inpos=686,inbits=9,outpos=58,outbytes=2
    73 74
    s  t 

inpos=695,inbits=11,outpos=60,outbytes=3,distance=-7
    65 72 20
    e  r    

inpos=706,inbits=72,outpos=63,outbytes=15
    6f 6e 20 74 68 65 20 62 61 6e 6b 2c 20 61 6e
    o  n     t  h  e     b  a  n  k  ,     a  n 

inpos=778,inbits=13,outpos=78,outbytes=5,distance=-42
    64 20 6f 66 20
    d     o  f    

注1: 元にしたのは、zlibに付属する参照実装であるPuff

Wednesday, December 18, 2013

プログラミング言語における正規表現リテラルの必要性について

Twitterに書いたことのまとめです。

プログラミング言語の仕様の一部として正規表現リテラルを提供することの得失について、JavaScriptを例に説明します。

■より簡潔なコード

言うまでもありませんが、正規表現リテラルを使った方が簡潔なコードになります。
(new RegExp("abc")).exec(s)  // リテラルを使わない場合
/abc/.exec(s)                // リテラルを使った場合
また、正規表現リテラルがない場合は、文字列リテラルとしてのエスケープと正規表現としてのエスケープが二重に必要になる結果、コードの保守性が低下します注1
new RegExp("\\\\n");  // リテラルを使わない場合
/\\n/                 // リテラルを使った場合

■エラー検出タイミング

正規表現リテラルがない場合、実際にその正規表現が評価されるまで記述エラーを検出することができません。正規表現リテラルがあれば、コンパイル時注2にエラーを検出できるので、開発効率と品質が向上します。
new RegExp("(abc")  // 実行時例外
/(abc/              // コンパイル(起動)時にエラー検出

■実行速度

正規表現リテラルがないと、正規表現を適用する度ごとに、毎回正規表現をコンパイルするコードを書きがちです。これは、実行速度を大幅に悪化させます。正規表現リテラルがあれば、正規表現を言語処理系側でコンパイルして使い回すことができるので、実行速度が向上します。
new RegExp("abc").exec(s) // 実行する度に正規表現がコンパイルされる
/abc/.exec(s)             // 正規表現のコンパイルは実行回数に関係なく1回

また、正規表現に対しては「単純な文字列処理関数より遅そう」という意見を目にすることもありますが、そのような一般化は誤りです注3。例えば、JavaScript処理系における速度比較についてはregexp-indexof・jsPerfをご覧ください。ウェブブラウザによっては、正規表現を使ったほうがString#indexOfよりも高速なのがご確認いただけると思います。

■より単純で強力な文字列API

上記3点より、正規表現の使用を前提とするのであれば、正規表現リテラルを採用した方が言語処理系の利用者の開発効率が向上することは明らかだと思います。

残る問題は、正規表現リテラルを採用することで、そのプログラミング言語はより煩雑で、利用者にとって使いづらいものになってしまわないかという点です。

この点については、以下のトレードオフが存在します。

PythonやPHPのような正規表現の使用を積極的にアフォードしていないプログラミング言語では、多くの文字列処理関数が存在します。利用者は、これらの関数の仕様を記憶するか、あるいは都度ドキュメントを参照することを求められます。

これに対し、JavaScriptやPerlのような正規表現リテラルを提供しているプログラミング言語では、文字列処理関数の数は比較的少なくなっています。必要な処理は、プログラマが正規表現を使って簡単に書くことができるからです。

また、正規表現を使うことで、例えば以下のような、複数の評価手法を合成した処理を簡単に記述することができます。文字列処理関数を使うアプローチの場合、このような処理をするためには複数の関数を組み合わせざるを得ません。
/^\s*abc/   // 先頭に空白、続いてabc

■まとめ

以上のように、正規表現リテラルを言語仕様に導入すれば、プログラマに正規表現の学習を強いることと引き換えに、より単純で強力な処理系を提供することができます注4

言語処理系の開発時に正規表現リテラルを採用すべきか否かについて検討すべき論点は、だいたい以上のとおりだと思います。あとは、言語処理系がどのような目的で、どのような開発者に使われるのか、処理系開発者のバランス感覚によって決まる問題ではないでしょうか。


■補遺 (2013/12/19追記):

正規表現リテラル導入の是非は上のとおりですが、文字列処理に正規表現を推奨すべき否か、という論点について、私の考えを補足します。

プログラミング言語仕様の設計という視座にたった場合、文字列処理の手法として、文字列処理関数を推奨するアプローチと正規表現を推奨するアプローチのいずれがより優れているか、という問いに対して一般化できる答えは存在しません

たとえば、PHP等に存在するtrim関数(文字列の前後の空白を削除)は、同等の正規表現(s.replace(/^\s*(.*)\s*$/, "$1"))よりも簡潔です。文字列処理のうち、頻出するパターンについて、適切な名前をもつ関数を提供することで可読性を向上させるというアプローチは理に適っています。

逆のケースとしては、次のようなものがあります。

文字列処理を実装していると、文字列の末尾から改行文字を1つ(のみ)削除したいこともあれば、末尾の改行文字を全て削除したいこともあります。正規表現を使えば、この種の需要に対応することは簡単です(/\n$/ あるいは /\n*$/)が、これらの需要に対応する文字列処理関数をいちいち言語処理系で提供することは現実的ではありません。

あるいは、電話番号を入力するフォームにおいて適切な文字のみが使われているかチェックするのに適しているのは、文字列関数ではなく正規表現(/^[0-9\-]+$/)でしょう。

このように、正規表現を使うアプローチには、文字列処理関数と比較して、単純な処理においては可読性が劣りがちな一方で、様々なバリエーションがある処理を統一的な手法で記述できるという点では優れているという特徴があります。

注1: この問題は、エスケープシーケンスの衝突を回避できる言語(例: Perl)、raw文字列リテラルが存在する言語(例: Python)では問題になりません
注2: 多くのインタプリタ型処理系の場合は起動時
注3: プログラムのソースコードであれ正規表現であれ、コンパイル後にVMで(場合によっては機械語にコンパイルして)実行される以上、速度差はその変換処理の優劣の問題だと理解すべきです
注4: 正規表現は使い方に制約がなさすぎて嫌、という考え方もあるかと思います

Saturday, December 7, 2013

JavaScriptで高速なコードを書く際の注意点。または私は如何にして心配するのを止めてJSXを作ることにしたか

本日、福岡で開催されたプログラミング言語のパフォーマンスを考えるイベント「ぷろぐぱ」で、「JSX 速さの秘密 - 高速なJavaScriptを書く方法」という演題で講演しました。

JavaScriptで速いコードを書こうとする際に陥りがちな罠を紹介し、それらの問題にJSXではどうやって対処しているか、プログラミング言語設計と最適化機能の実装を説明しました。プログラミング言語設計に興味がある方にとっても、JavaScriptを使ったプログラミングに興味がある方にとっても面白い内容になっているかと思います。


講演中の写真とあわせてご笑覧いただければ。



※本記事はJSX Advent Calendar 2013の一部です。