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

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)             // 正規表現のコンパイルは実行回数に関係なく１回

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

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

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

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

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

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

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

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

/^\s*abc/   // 先頭に空白、続いてabc

■まとめ

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

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


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

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

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

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

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

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

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

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

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

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

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

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

JSX 速さの秘密 - 高速なJavaScriptを書く方法 from Kazuho Oku

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

遅いJavaScriptコードをマサカリでぶったぎる @kazuho #progpa pic.twitter.com/0QSVAF0nKV

— きしだﬗ (@kis) December 7, 2013

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

Benchmarking asm.js using real-world code (zlib.js)

In response to a chatter between Japanese developers on Twitter about how asm.js would perform on web browsers other than Firefox, @y_imaya has written a benchmark between zlib.js that he develops and maintains vs. zlib-asm written by @ukyo by inflating (e.g. decompressing) Canterbury Corpus (a well-known set of files used for benchmarking compressor/decompressors).

His blog post can be found here but I could not hesitate to take my own benchmark on mobile devices since I use zlib.js at work, and may want to switch to zlib-asm if it runs faster than that.

So here are the numbers (his benchmark is ready to run here). The numbers on the charts show the milliseconds that took for decompressing the whole corpus.

First of all, asm.js running on Firefox is clearly the performance winner among all, showing the technical advantage of the approach. On the other hand, the asm.js-version is roughly 2x slower on other web browsers compared to the hand-written JavaScript variant. So for the time being, it seems that using a well-written JavaScript library would be preferable on browsers other than Firefox.

Anyways qudos to @y_imaya and @ukyo for their great work. I hope to see more benchmarks based on code that is actually used, so that we could understand more about the benefits of asm.js.

EDIT: It would be great if someone could add a benchmark of PNaCl running on Chrome as well.

Do not allocate Typed Arrays too frequently, or your browser will die OOM

The following code causes the browsers' JavaScript runtime to crash (or allocate gigabytes of memory) when the array length is only around 1MB to 2MB (reproducible on Google Chrome 30.0.1599.101 / Safari 6.1 (8537.71) running on OS X 10.8.5; Mozilla Firefox 25.0.1 does not have the problem).

current length of Uint8Array is <input id="arrlen"> bytes.
<script>
var arr = new Uint8Array(12345);
function doit() {
  for (var i = 0; i < 100; ++i) {
    arr = new Uint8Array(arr.length + (Math.random() * 500 | 0));
  }
  document.getElementById("arrlen").value = arr.length;
}
setInterval(doit, 1);
</script>

test link

My understanding is that historically, this is due to the fact that Typed Arrays were defined outside of the ECMAScript specification and that it was implemented outside of the JavaScript VMs. Memory chunks that are used to store the elements of the arrays are allocated outside of the VM heap, and GC tracks only the reference to the array elements. Thus the pressure against GC is tiny per each allocation even though the pressure against malloc might be high. And the outcome is that malloc gives up well before GC starts to free the typed arrays that are no longer used.

I had thought that the problem had been fixed a while ago, but it still seems to exist. And although I believe that it will be fixed sooner or later I am writing this weblog so that, until then, others who fall into the pitfall can understand the problem.

PS. opened the issue on the Chromium issues tracker.

パスワードが漏洩しないウェブアプリの作り方 〜 ソルトつきハッシュで満足する前に考えるべきこと

■■序論

徳丸さんのスライド「いまさら聞けないパスワードの取り扱い方」に見られるように、昨今、ウェブアプリケーションの設計要件として、サーバ内に侵入された場合でもユーザーのパスワードをできるだけ保護すべきという論調が見受けられるようになってきました。

上掲のスライドでは、その手法としてソルトつきハッシュ化を勧めています。しかしながらスライドに書かれているとおり、ソルトつきハッシュには、複雑なパスワードの解読は困難になるものの、単純なパスワードを設定してしまっているユーザーのパスワードについては十分な保護を提供できないという問題があります。そして、多くのユーザーは適切なパスワード運用ができない、というのが悲しい現実です。

ソルトつきハッシュを使った手法でこのような問題が残るのは、ウェブアプリケーションサーバに侵入した攻撃者がユーザーの認証情報をダウンロードして、認証情報をオフライン攻撃することを防ぎようがない、という前提を置いているからです。

逆の言い方をすると、攻撃者がアプリケーションサーバに侵入したとしてもユーザーの認証情報にアクセスできなければ、認証情報を奪われる可能性はないわけです。そのようなシステムを構築するにはどのようにしたらいいでしょうか。

一般的なウェブアプリケーションにおける答えは、ストアドプロシージャの利用とデータベースサーバの保護にあります^注1。


■■ストアドプロシージャによるパスワード認証

多くのSQLデータベースサーバはストアドプロシージャとストアドファンクションをサポートしており、これはMySQLやPostgreSQLといったオープンソースRDBMSでも例外ではありません。ストアドプロシージャやストアドファンクションには二つの役割があり、ひとつは処理手順をまとめること、もうひとつは、テーブルへのアクセスパターンを限定することです。

たとえばMySQLの場合、以下のようなDDLを実行することで、一般ユーザー権限（webapp）からは読み書きできない認証情報カラムpasssalt（ソルト値を格納）とpasshash（ハッシュ値を格納）をもつuserテーブルを作ると同時に、パスワードの一致を確認するストアドファンクション（check_pw）を提供することができます。

-- テーブル定義
CREATE TABLE user (
  username varchar(255) NOT NULL,
  passsalt varbinary(255) NOT NULL,
  passhash varbinary(255) NOT NULL,
  PRIMARY KEY (username)
) DEFAULT CHARSET=utf8;

-- パスワードを検証するストアドファンクションを定義
DELIMITER |
CREATE FUNCTION check_pw(u TEXT, p TEXT) RETURNS INT
BEGIN
  RETURN (SELECT COUNT(*) FROM user WHERE username=u and passhash=SHA1(CONCAT(passsalt,SHA1(p))));
END;
|
DELIMETER ;

-- パスワードを更新するストアドプロシージャ定義
DELIMITER |
CREATE PROCEDURE update_pw(u TEXT, oldpass NEXT,newpasssalt TEXT,newpasshash TEXT)
BEGIN
  DECLARE r INT;
  SET r = check_pw(u, oldpass);
  IF r = 0 THEN
    SIGNAL SQLSTATE '45000'
      SET MESSAGE_TEXT 'incorrect old password'
  ELSE
    UPDATE user SET passsalt=newpasssalt,newpasshash=newpasshash WHERE username=u;
  END IF;
END;
|
DELIMETER ;

-- webappユーザーにusernameカラムのみSELECT権限付与
GRANT INSERT,DELETE ON db.user TO webapp@'webapp-host';
GRANT SELECT (username) ON db.user TO webapp@'webapp-host';

-- webappユーザーにストアドの実行権付与
GRANT EXECUTE ON FUNCTION check_pw TO webapp@'webapp-host';
GRANT EXECUTE ON PROCEDURE update_pw TO webapp@'webapp-host';

実際に、このデータベースに一般ユーザー権限で接続してみると、以下のように、ユーザーの作成はできるものの認証情報は読めない一方で、パスワードの検証は可能、となっていることがわかります。

% mysql -u webapp db

-- 新規ユーザー johndoe （パスワード: johnpass）を作成
mysql> insert into user (username,passsalt,passhash) values ('johndoe','abcdefg',sha1(concat('abcdefg',sha1('johnpass'))));
Query OK, 1 row affected (0.01 sec)

-- userテーブルの全カラムを読むことはできない
mysql> select * from user;
ERROR 1142 (42000): SELECT command denied to user 'webapp'@'webapp-host' for table 'user'

-- usernameカラムだけならば読むことができる
mysql> select username from user;
+----------+
| username |
+----------+
| johndoe  |
+----------+
1 row in set (0.00 sec)

-- パスワードの検証は可能
mysql> select check_pw('johndoe','johnpass');
+--------------------------------+
| check_pw('johndoe','johnpass') |
+--------------------------------+
|                              1 |
+--------------------------------+
1 row in set (0.00 sec)

-- 間違ったパスワードを指定すると検証に失敗
mysql> select check_pw('johndoe','badpass');
+-------------------------------+
| check_pw('johndoe','badpass') |
+-------------------------------+
|                             0 |
+-------------------------------+
1 row in set (0.00 sec)

このように、SQLデータベース内にパスワードの検証／更新ロジックを持たせることで、（データベースに一般ユーザー権限でアクセスするための情報が保存された）ウェブアプリケーションサーバに攻撃者の侵入を許した場合でも、パスワードの漏洩を防ぐことができます。

また、ストアドプロシージャで監査ログを出力することで、攻撃を検知したり被害範囲を特定したりといったことも可能になるでしょう。

(2013/11/27追記: このような手法を実践するにあたっては、@isidaiさんの指摘をあわせて参照の上、各自の責任において設計、実装くださいますようお願いいたします)

■■データベースサーバの保護

SQLデータベースの機能を利用してパスワードを保護する場合に考えなければならないこととして、ウェブアプリケーションサーバが攻撃者の手に落ちた場合に、そこを踏み台としてデータベースサーバに侵入されるリスクを下げるにはどうすれば良いか、という点があります。

答えは単純で、データベースサーバをウェブアプリケーションサーバとは別のネットワークセグメントに配置し、両者の間にファイアウォールを設置すれば良い^注2、ということになります。ファイアウォールの役割は、ウェブアプリケーションサーバからデータベースサーバへのアクセスを正規のTCPポートを指定するもの以外、全て遮断することです^注3。

このように設定することで、データベースサーバの権限管理機能にバグがない限り、ウェブアプリケーションサーバを踏み台として認証情報を奪われる可能性はなくなります。

なお、言うまでもありませんが、データベースサーバを配置するネットワークセグメントをインターネットと直接接続してはいけません。理想的には、アクセス手段を厳密に規定して管理系セグメントからのみ接続可能とすべきでしょう。


■■まとめ

ユーザーのパスワードを適切に暗号化することは重要ですが（そのまとめとして徳丸さんのスライドは優れていると思います）、サーバへの侵入を前提としてアーキテクチャを設計する際には、多層防御の手法が有効になります。

本稿では、RDBMSサーバのストアドプロシージャとファイアウォールの使用を通じて、ユーザーの認証情報を多層防御するウェブアプリケーションが簡単に構成できることを説明しました。


■■余談

実は、本稿で取り上げた問題とその解は、Unixにおいてシャドウパスワードが導入された経緯の変奏曲です。Unixのシャドウパスワードとは、誰もが閲覧可能なファイル（/etc/passwd）に一方向暗号化（ハッシュ化）されたパスワードを記載しておくのではなく、攻撃者（一般ユーザー）がアクセスし得ないファイル(/etc/shadow)に認証情報を配置し、認証が必要な場合はAPIを通してルート権限で動作するプロセスに問い合わせ、/etc/shadowの内容と比較した結果を回答してもらう、という仕組みです。

注1: 厳密に言うと、RDBMSでなくても別のサーバにAPIで問い合わせるのであればなんでもいいのですが
注2: ウェブアプリケーションとデータベースが１台のサーバに同居するケースでも、OSのユーザベースの権限分離を使って同様のことは不可能ではないと思います
注3: 大規模な構成かのように聞こえるかと思いますが、Amazon AWSのRDSを使うと必然的にこの構成になるなど、実は意外と身近なものです

もうひとつの知られざるオープンソース 〜 ウェブ企業のOSS戦略

「オープンソースソフトウェア(OSS)」と聞いて、あなたがイメージするものはなんですか？　多くの人は Linux や Apache、Firefox といった成功した大規模なソフトウェア製品を思い浮かべることでしょう。

実は、ウェブ上でサービスを提供する会社のエンジニアたちは、これらとは別の種類のOSSを使って仕事をしています。このブログエントリでは、そのようなOSSを紹介し、それらがなぜ開発され使われているかを説明したいと思います。


■ウェブ企業におけるOSS開発の実例と合理性

下の図は、Perl で記述される大規模ウェブアプリケーションの一般的な構成を示しています^注1。このうち、「自社ロジック」と書かれているところ以外は、全てオープンソースとして開発／公開されているモジュール（ソフトウェア部品）です。各社のエンジニアが密接に協力しながら、ミドルウェアをオープンソースとして整備していることがわかるかと思います^注2。

このような部品開発における会社を超えた協力体制は、Perl以外のプログラミング言語を使っているウェブ企業でも良く見られるものです。

いったいなぜ、そのような協力がなされるのでしょうか。

「そのようなエンジニア文化だから」というのもひとつの答えかと思います。ですが、彼らが業務の一環として開発したミドルウェアをオープンソースとして公開している以上、文化を裏打ちする経済的合理性を考えないわけにはいきません。

ウェブ業界は、主にコンテンツをユーザーに配信する企業群として成長してきました。これらの企業におけるコアコンピタンスとは、コンテンツ（あるいはコンテンツを提供してくれるユーザー）です。このため、ソフトウェア自身を金の卵だと考えるソフトウェア業と異なり、ウェブ業界では、ソフトウェアはコンテンツを配信するための手段だという位置づけをされることが多々あります。そして、ソフトウェアが売上をあげるための手段である以上、その開発／運用コストを削減することが重要になります^注3。

種々多様なコンテンツにあわせて迅速にソフトウェアインフラを整備し安価に運用するためには、カスタム開発を最小限に抑える必要があります。また、社外への発注や人材の流動、ビジネス規模の変化を考慮した場合、ソフトウェアスタック全体を内製し社内で維持改善を続けるよりも、業界全体のデファクトスタンダードとなる実装が自社の都合にあった形で存在することが望ましいと言うことができます。

図で示したソフトウェア構成は、この経済的な要求が反映された結果なのです。

たとえば、Furlを見てみましょう。2010年に開発が開始されたFurlは、LINEに勤務するエンジニアがメンテナンス権をもっている高速かつカスタマイズが容易なHTTPクライアントであり、サーバの必要台数がコストに響くような大規模サービスで好んで使われています。一方で、その開発には、当初からDeNAに所属するエンジニアが参加しており、同社の影響も大きいものがあります。その顕著な例が、DeNAの要件にあわせて追加された、DNSリゾルバの置換機能です。

一般的な使用形態において必要ない機能というのは、第三者が、たとえ必要なコードを書いて追加をお願いしたとしても、なかなか受け入れてもらえるものではありません。それは、機能の追加をいったん受け入れてしまうと、以後その機能をメンテナンスしていく責務が主開発者の肩にかかるからです。にもかかわらず、Furlに同機能が追加されたのは、両社のエンジニアが継続的に共同作業を行っており（Furlが、DeNAのエンジニアがメンテナンスしているHTTPパーサライブラリを使っていることを含みます）既に信頼関係が構築されていたという事情を勘案する必要があるでしょう。

このように、継続的にオープンソースのミドルウェア開発に参加することでコストを分担しつつ、自社にとって便利なものにしていく、という営みが実際に行われているのです。


■OSS共同開発のリスク評価

では、経済的な合理性はあったとして、部品を共同開発することによるリスクはないのでしょうか。よくある質問は「ある会社の社員が、ライバル社に害をなすような機能を組み込んだりしないのですか」というものです。ウェブ企業のエンジニアたちによるオープンソース開発では、この点についても抑止力が働く構造になっています。

本稿で例に挙げたOSSはいずれも、誰がどの機能を書いたか、コミットログを追うことで全て把握できるようになっています。そして、エンジニアのコミュニティにおけるコードの品質に対する最初の評価基準は、どの会社のエンジニアが書いたか、ではなく、誰が書いたか、という点です^注4。

この条件下において、悪意のあるコードをOSSに埋め込むことは、エンジニアにとってキャリアの終わりを意味します。そのような行為に手を染めたエンジニアは、以後就職先を見つけることはできないでしょう。終身雇用が期待できる業種なら、それでも悪行を働くインセンティブがあるかもしれませんが、ウェブ業界は転職を前提としたキャリアプランを立てざるをえないところです。このように、職業倫理のみならず経済的側面からも、共同開発によるリスクは抑えられていると言うことができます。実際には、コードが多くの目にさらされることによる品質向上効果の方が大きいと考えるべきでしょう。


■まとめ

以上、述べてきたように、ウェブ企業におけるオープンソース開発は、サポート収益を期待するソフトウェア企業のオープンソース^注5とは大きく異なる原理に基づいて活発な開発が行われている分野です。コンシューマには見えない小粒なソフトウェアが多いがゆえに見落とされがちな分野ですが、オープンソースソフトウェアに関する議論や検討を行う際には、これらの活動とその背景についても理解しておくことが望ましいかと思います。

注1: 主要なモジュールと本稿に登場するものを中心に抜粋して図示しています。実際には、他にも多くの人が開発した様々なOSSモジュールが使用されています
注2: 会社の枠を超えた恊働の実態とOSSを使うに際してコミッターの所属を気にする必要がないということを説明するためにあえて社名を出しているだけなので、その点、ご理解とご配慮をいただけると幸いです
注3: 主目的がサポート収益の最大化ではなくコードの共有によるコストの削減であるため、ウェブ企業が公開するOSSについては緩やかなOSSライセンスが選択される傾向にあります（Perlモジュールの場合はPerl License（Artistic LicenseとGPLのデュアルライセンス）が通常）
注4: 品質の高い貢献が従来から多い人のコードは信頼される一方、新規参入者のコードは注意深く検査されるという意味です
注5: ソフトウェア企業の（OSSを含む）競争戦略については、やや古いですが「ソフトウエア企業の競争戦略」（マイケル・A.クスマノ）が良書だと思います

渋谷から見える山々

西方面。

Q4M now supports MySQL 5.5 / 5.6, an advisory to 0.9.7, 0.9.8 users

Q4M is a message queue implemented as a pluggable storage engine of MySQL.

Thanks to the helps from @laysakura; and @kamipo I have finally added to Q4M support for MySQL 5.5 / 5.6 in 0.9.8.

After releasing 0.9.8 I have noticed that a bug was introduced in 0.9.7 that may cause crashes and/or data losses when accessing tables created under previous versions of Q4M.

If you are using either 0.9.7 or 0.9.8 (that were upgraded from any previous version of Q4M), I recommend you to run the queue_compact(tbl_name) function against all existing Q4M tables to avoid the issue.  Sorry for the inconvenience.

If you are an existing user of 0.9.6 or an earlier version, please upgrade directly to 0.9.9.


--- Japanese Translation (in brief) ---

Q4M 0.9.7 と 0.9.8 には、それら以前のバージョンで作成されたテーブルデータにアクセスが発生した場合に、クラッシュあるいはデータロスが発生する可能性をもつバグが存在します。

このバグは、queue_compact(tbl_name) 関数を全ての Q4M テーブルに対し適用することで回避できますので、いずれかのバージョンをアップグレードとしてインストールした場合は、そうされることを推奨します。

また、0.9.6 以前をお使いの方がアップグレードされる際には、0.9.9 以降へ一気にアップグレードすることをお勧めします。

ご不便をおかけし申し訳ありません。

デブサミ2013基調講演「ウェブブラウザの時代は終わるのか 〜スマホアプリとHTML5の未来〜」スライド

ウェブブラウザの時代は終わるのか 〜スマホアプリとHTML5の未来〜 from Kazuho Oku

Writing fast, processor-independent code using C++ and LLVM bitcode

Using inline assembly along with C/C++ code has long been the best choice for developers writing optimized code. However the approach had its shortcomings:

- the need to write assembly for each architecture
- the use of inline assembly hinders certain compiler optimizations (such as register allocation)

But thanks to LLVM it is now possible to write processor-independent assembly functions using its bitcode, and use its link-time optimizer to get the function expanded in-line into C/C++ code.

I have created an example that shows how to implement fast integer arithmetics (with overflow detection) in C++, which is available at github.com/kazuho/add_with_overflow.

It uses a bitcode-level intrinsic called "llvm.sadd.with.overflow.i32" (that gets inlined) to implement integer addition with overflow check.

With the example, the source code

if (! add_with_overflow(&ret, x, y))

gets compiled into

addl    8(%rsp), %esi
jno     LBB1_4

As can be seen, the generated code is highly optimized. Not only does it use the JNO instruction, the source operand of ADDL is placed on stack (which would be faster than on register since the value is never again being referred to). Such kind of an optimization has been impossible with inline assembly of GCC (that requires the arguments to be loaded on registers).

Since the output (after inline expansion) is a .s file (processor dependent assembly), it is possible to link the optimized code using other linkers as well.

Note: the work is based on Fast integer overflow detection - Xi Wang, and I would like to thank the author for his excellent work.

Note 2: Since the bitcode instructions might change in the future, it might be a good idea to limit the length of the functions written in bitcode as short as possible.