枕を欹てて聴く

香炉峰の雪は簾を撥げて看る

How to carry native executables for (almost) all platforms

NOTE: If you find some bugs, please inform me :)

Abstract (in 10 seconds)

By investigating Ninja & Chromium depot_tools approach, I'll introduce the way to carry your C++ executable for (almost) all platforms.

Introduction

You sometimes would like to publish native executables. One day, you make a nice command written in C++, and using it on Linux x64. You may write a nice zsh script using this nice executable and it works as you want.

But you may control dotfiles on git repository and sometimes you need to sync your nice environment between your working machines. In the meantime, you may build your nice command on each environment. However, whenever you fix / enhance your native module, you need to rebuild it on all your machines. Some machines are the same architecture as your main machine. But some machines may be OSX. Another machines are Windows, etc...

Why don't you write it with Script languages?

You need to setup script languages environment on the each machines. And I sometimes would like to construct commands based on C++ libraries, such as LLVM.

NOTE: LLVM can be built as static library. So it is possible to bundle LLVM libraries to one executable file.

Why don't you write it with golang?

As the same as the above.

Windows

When adding a directory to PATH, cmd.exe will search a command through PATH directories. cmd.exe will find {name}.exe executable file. ".exe" extension! It is not (usually) considered in Linux & OSX. So placing {name}.exe and {name} command in the same directory, you can provide Windows and Unix binary at the same time.

So this stroy is very easy. The way is buidling command as name.exe and placing it on the appropriate directory. That's all.

OSX & Linux

You need to distinguish them. So the easiest way to start it is making {name} command sh script to execute an appropriate binary.

Switching binary with shell script

In the script, you can use uname command to distinguish the platform. This command works on FreeBSD, OSX and Linux. This is the definition of (almost) all platforms.

According to the uname man page, uname -s will answer the kernel name. For example,

    Linux,
    Darwin,
    FreeBSD

And you need to consider is that machine architecture (such as x64). You can get this by uname too. uname -m will return hardware architecture. For example,

    amd64  # On FreeBSD
    x86_64 # On Linux
    i386
    i686
    ...

You can see uname implementation of FreeBSD here. And actual code to gain a architecture name is here. And architecture candidates on FreeBSD seems the same to this.

amd64 arm i386 ia64 mips pc98 powerpc sparc64 x86

And on the Linux case. According to the Linux's Makefile (here), we can get subarchitecture by this script.

uname -m | sed -e s/i.86/x86/ -e s/x86_64/x86/ \
               -e s/sun4u/sparc64/ \
               -e s/arm.*/arm/ -e s/sa110/arm/ \
               -e s/s390x/s390/ -e s/parisc64/parisc/ \
               -e s/ppc.*/powerpc/ -e s/mips.*/mips/ \
               -e s/sh[234].*/sh/ -e s/aarch64.*/arm64/

So by adding amd64 case to it, we can get the command line to get sub architecture.

uname -m | sed -e s/i.86/x86/ -e s/x86_64/x86/ -e s/amd64/x86/ \
               -e s/sun4u/sparc64/ \
               -e s/arm.*/arm/ -e s/sa110/arm/ \
               -e s/s390x/s390/ -e s/parisc64/parisc/ \
               -e s/ppc.*/powerpc/ -e s/mips.*/mips/ \
               -e s/sh[234].*/sh/ -e s/aarch64.*/arm64/

And finally, you need to get if CPU is 64bit / 32bit. To get it on Linux, FreeBSD and Darwin, you can use getconf LONG_BIT according to the depot_tools source.

Then here's the complete switch script.

#!/bin/sh
OS="$(uname -s)"
ARCH="$(uname -m | sed -e s/i.86/x86/ -e s/x86_64/x86/ -e s/amd64/x86/ \
                       -e s/sun4u/sparc64/ \
                       -e s/arm.*/arm/ -e s/sa110/arm/ \
                       -e s/s390x/s390/ -e s/parisc64/parisc/ \
                       -e s/ppc.*/powerpc/ -e s/mips.*/mips/ \
                       -e s/sh[234].*/sh/ -e s/aarch64.*/arm64/)"
BIT="$(getconf LONG_BIT)"
COMMAND="${0}-${OS}-${ARCH}-${BIT}"

if [ -e "$COMMAND" ]; then
    exec "$COMMAND"
else
    echo "Command ${COMMAND} not found."
    echo "Unsupported architecture ${OS} ${ARCH} ${BIT}"
fi

So placing {name}-Linux-x86-64 in the same directory to this script, you can make command available on Linux x64 environment.

Building executables with -static option (Linux and FreeBSD)

Native executables (built by g++, clang or so) usually depends on libc, libgcc, libcompiler-rt, libsup++, libc++ and so on. But as you may know, you can build native executables not depending on them. You can use -static option.

g++ main.cc -static

Then g++ produces a executable not depending on the above libraries. You can ensure it by executing ldd {name}. So moving it to the other platform, it works correctly if OS, ARCH, BIT are the same.

NOTE: Without -static option, ldd a.out result may be the following.

$ ldd a.out
        linux-vdso.so.1 =>  (0x00007fff799fe000)
        libstdc++.so.6 => /usr/lib/x86_64-linux-gnu/libstdc++.so.6 (0x00007f67bd054000)
        libc.so.6 => /lib/x86_64-linux-gnu/libc.so.6 (0x00007f67bcc8c000)
        libm.so.6 => /lib/x86_64-linux-gnu/libm.so.6 (0x00007f67bc987000)
        /lib64/ld-linux-x86-64.so.2 (0x00007f67bd383000)
        libgcc_s.so.1 => /lib/x86_64-linux-gnu/libgcc_s.so.1 (0x00007f67bc771000)

Since linux-vdso.so.1 is contained in the linux kernel (Linux Virtual Dynamic Shared Objects), it isn't required as a shared library. And since libstdc++.so.6, libc.so.6, libm.so.6, libgcc_s.so.1 and /lib64/ld-linux-x86-64.so.2 are placed with the same name in a lot of Linux distributions. So if you don't worry about the edge cases, -static for system libraries is not necessary. Compiled binaries basically work on the other Linux systems. For example, ldd ninja-linux64 shows the same result. But of cource, the other libraries should be linked statically. This shows how to control linking with libraries. By following the way described in that article, we can control which libraries are linked statically. It's possible to link system libraries as dynamic and the others as static.

Building executables on OSX

However, -static option doesn't work on OSX. According to the man gcc.

This option will not work on Mac OS X unless all libraries (including libgcc.a) have also been compiled with -static.
Since neither a static version of libSystem.dylib nor crt0.o are provided, this option is not useful to most people.

So if you build with -static (e.g. clang++ portable.cc -static), you may get the following error.

ld: library not found for -lcrt0.o
clang: error: linker command failed with exit code 1 (use -v to see invocation)

This is also described on this article.

But don't worry about that. Since OSX environment layout is limited, basically dynamically linked system library is placed on appropriate sites. You can see dynamic linked libraries on the binary by otool -L executable. For example,

portable-Darwin-x86-64:
    /usr/lib/libc++.1.dylib (compatibility version 1.0.0, current version 120.0.0)
    /usr/lib/libSystem.B.dylib (compatibility version 1.0.0, current version 1197.1.1)

So in this time, we just build executables as name-Darwin-x86-64 and place it.

Cross compiling the 32 / 64 bit

Just googled and found the article and this. Especially, the latter article works correctly on my environment (Ubuntu 13.10, FreeBSD 10)

Result

So I've created the sample project portable to test it. It includes the above script and executables. (Windows 32bit, OSX 64bit, Linux 32bit, Linux 64bit. Their architecture is x86)

So just copying (or git clone) it and append this directory to the PATH, you can sync, execute, publish this command on the (almost) all platforms.

tumblr reblogging enviroment Advent Calendar 2013 - 17th day - Taberareloo Canary

f:id:Constellation:20131218025637j:plain特に関係のない UNIX 画像

This is posted for tumblr reblogging enviroment Advent Calendar 2013 17th day

予定地です, 現在進行形で作業しています... すみません...公開しました

3 秒でわかる版

f:id:Constellation:20131218023836p:plain

CI によって Taberareloo を commit ごとに自動 build し, Taberareloo Canary として提供します. ここ: https://drone.io/github.com/Constellation/taberareloo/files から taberareloo.crx を download して, Chrome 拡張機能のページ(上記のような)に向かって drag & drop で install することができます.

もしくは, ExtensionInstallSources を指定することで install 可能なサイトを増やすことができ, 例えば OSX の場合は, defaults コマンドで拡張可能です*1 ここで https://*drone.io/* を指定することで install が可能となります.

Introduction

一部で微妙な人気を博している Taberareloo はなんだかんだで公開から4年*2という時間を経つつも, YungSang さん*3, syoichi さん*4ら maintainer の方々によるメンテナンスによって維持され続けている. web scraping を基板とするシステムは多くの web service に対応することを可能にしたが service の変更に対して脆弱であり, 意図的に制限の弱い XPath を利用するなどの手法である程度の変化を吸収することはできるが, 大きな変化に対応するためには Taberareloo 自体の対応を必要とする. こういった変更の commit はすぐさま release されるわけではなく, release と commit の間には時間がかかる. また, release した後に問題が顕在化することがあり, release 直後に小規模の変更の release が相次ぐといった問題が存在した.

そこで Taberareloo では CI による commit ごとの build である Taberareloo Canary を提供する. CI によって commit ごとに build, 公開され, 自動的に updates.xml が更新され, release される. これにより Taberareloo Canary のユーザに対して commit ごとの build をすぐさま提供することができ, service 変更の早期対応や bug の早期発見に役立つ.

(ここまでで長い文章を書く気力が尽きました)

Architecture

drone.io は CI のサービスですが, artifact という, なんらかのファイルを生成し公開する機能を持っています. そこで artifact として crx / updates.xml を提供することで CI による自動的な build & release を提供しようというのが趣旨です. この時, grunt-crx を用いて crx file を作成しました, らくしたいーという思いが溢れました(しかし bugfix をするはめになりました...).

crx を作成するためには private key が必要ですが, 当たり前ですが CI サービスの repository に入れることはまずいです,

Security Notice

It is strongly recommended to store your privates keys outside the source folder of your extensions.

Otherwise we will laught at you.

grunt-crx README

そこで今回は, drone.io の環境変数に key を入れることとし, また build 可能な branch を master に制限することによって, key の dump を防ぎました. なんか漏れがあったらまずい感じもしますが指摘してください.

また version 番号の 4 つめの部分を build 番号として用いました. build 番号を UNIX time にしようと試みたのですが, Chrome extension は仕様上, version のそれぞれの区切りは uint16_t でなければだめです. そこで, 前の updates.xml を取得し, その番号を increment したものを新たな番号として付与することにしました. この変更により, build 番号は連続します.

実装の途中で, npm の crx module について bug を発見したため, 一時的に自分の fork の module を利用していますが, 後に upstream する予定です. また grunt-crx についても private key をファイルでしか受け取ることができなかったため, 文字列で受け取ることができるように変更しました. これも後に upstream する予定です.

Conclusion

ゆゆ式は素晴らしいです. 最近はまんがタイムきららのドキドキ☆ビジュアルコミックスを読むことが生きるということなのだとひしひしと感じます. 来月からは桜Trickという最高の作品が始まるので見たほうが良いと思われます. またご注文はうさぎですか?という最高の作品についてもアニメ化するようなので原作を買っておくのを強く, 強くおすすめします.

Acknowledgment

というわけで, 明日も引き続き tumblr reblogging enviroment Advent Calendar 2013 とアニメをお楽しみください. 明日の担当は Tombloo に多くの緻密な patch を書かれている polygon_planet さんです. よろしくお願いします.

*1:http://superuser.com/questions/450893/how-to-install-a-private-user-script-in-chrome-21

*2:http://constellation.hatenablog.com/entry/20091129/1259514045

*3:https://github.com/YungSang

*4:https://github.com/syoichi

YieldExpression with delegate

In the latest ECMA262 6th draft (rev15), YieldExpression with delegate detailed algorithm is defined.

Reading the spec algortithm, I think this is very useful to put together iterators to make a complex iterator.

edit: I've reported issues in the spec about this section. https://bugs.ecmascript.org/show_bug.cgi?id=1486 https://bugs.ecmascript.org/show_bug.cgi?id=1487

For example,

function* gen() {
    for (let i = 0; i < 100; ++i) {
        yield i;
    }
}

function* main() {
     yield * gen();
}

for (let i of main()) {
    console.log(i);  // 0 -> 99
}
function* gen() {
    for (var i = 0; i < 100; ++i) {
        var receive = yield i;
        console.log(receive);    // 0, 1, 4, 9, ... , 9801
    }
}

function* main() {
    yield* gen();
}

let result = { done: false, value: undefined };
let iterator = main();
do {
    result = iterator.next(result.value * result.value);
    if (result.done) {
        break;
    }
    console.log(result.value);  // 0, 1, 2, 3, ..., 99
} while (true);
// the result of console is interleaved,
// 0, 0, 1, 1, 2, 4, 3, 9, ...

So we can easily create a new iterator for our data types.

function MapWithArray() {
    this.map = new Map();
    this.array = [];
}

function* MapWithArrayIterator(obj) {
    yield * obj.map;
    yield * obj.array;
}

let data = new MapWithArray;
let iterator = MapWithArrayIterator(data);

Polymorphic Inline Cache implementation of iv / lv5

This is a blog post for 12/22 VM advent calendar.

See http://qiita.com/advent-calendar/2012/vm for more nice blog posts :)

この記事は更新中です... 完成しました

Introduction

ECMA262 engine, iv / lv5 には, Polymorphic Inline Cache(以下PIC)が実装されています. ということで, ここではPIC, 特にLoadPropertyICの実装について記述したいと思います. PICのsystem本体についてはかなり多くの場所で記述されていると思うので, ここでは, かなり実践的な方向で記述したいと思います. そのため, 多くの前提知識を要求していますのでご容赦ください.

LoadOwnPropertyIC & PIC overview

iv / lv5におけるICの実装を紹介します. lv5/breaker/compiler.h

      asm_->mov(rdi, r14);
      LoadPropertyIC* ic(new LoadPropertyIC(native_code(), name));
      native_code()->BindIC(ic);
      asm_->mov(rdx, core::BitCast<uint64_t>(ic));
      const std::size_t offset = PolyIC::Generate64Mov(asm_);
      ic->BindOriginal(offset);
      asm_->call(rax);

raxに設定されているのは, 通常のLOAD_PROP関数です. このため, 一番最初の場合, LOAD_PROP関数が呼ばれます. そしてそこでは, 通常通りhashtableを引いてlookupします, 問題はここからです.

lv5/breaker/stub.h

  // cache phase
  // own property / proto property / chain lookup property
  if (slot.base() == obj) {
    // own property
    ic->LoadOwnProperty(ctx, obj->map(), slot.offset());
    return Extract(res);
  }

cacheableでown propertyであることが発覚すると, offsetを使って, ICを構築し始めます. lv5/breaker/poly_ic.h

    as.inLocalLabel();
    gen(this, &as, ".EXIT");  // ここでmain codeが作成される
    // fail path
    as.L(".EXIT");  // TestMapContentsなどで失敗するとここへjmpする
    // ここでIC末尾のjmpを生成, fallback pathへjmp
    const std::size_t pos = GenerateTail(&as);
    ic->set_tail(const_cast<uint8_t*>(as.getCode()) + pos);
    as.outLocalLabel();
      // main code

      // map一致を検査
      IC::TestMapConstant(as, map_, r8, r10, fail);
      // load
      LoadPropertyIC::GenerateFastLoad(as, r8, offset_);
    // GenerateFastLoad
    const std::ptrdiff_t data_offset =
        JSObject::SlotsOffset() +
        JSObject::Slots::DataOffset();

    // dataのpointerを取得し
    as->mov(rax, qword[reg + data_offset]);

    // offset access. 結果はraxに入れる
    // これはx64 calling convension参照
    as->mov(rax, qword[rax + kJSValSize * offset]);

    // retはICがpassした時に行われる
    as->ret();

r8にobjectが入っているので, cache対象のmapと一致するかどうかをtestします. そして一致した場合にGenerateFastLoadでoffset accessを行います. ここでretが最後に入っているところに注目です.

そして, ICの末尾をLOAD_PROP関数へのjmpにして, また, 一番初めのcallのraxをICのcallに書き換えます

  void ChainingObjectLoad(Unit* ic, uintptr_t code) {
    // このICが呼ばれるようにする
    if (empty()) {  // ICが初めて生成された時
      // rewrite original
      // LOAD_PROP呼び出しのcallを書き換え
      native_code()->assembler()->rewrite(from_original_, code, k64Size);
    } else {
      if (!object_chain()) {
        // rewrite object guard
        Rewrite(from_object_guard_, code, k64Size);
      } else {
        // 一つ前のICの最後のjmpを自分に書き換え
        object_chain()->Redirect(code);
      }
    }

    // このICの最後のjmpを設定する
    if ((size() + 1) == kMaxPolyICSize) {
      // last one
      // kMaxPolyICSizeより多くのICがぶら下がっている時
      // ICを生成しないLOAD_PROPにjmpするようにする
      ic->Redirect(core::BitCast<uintptr_t>(&stub::LOAD_PROP_GENERIC));
    } else {
      // それ以外の場合は, LOAD_PROPへjmpする
      ic->Redirect(core::BitCast<uintptr_t>(&stub::LOAD_PROP));
    }
  }

iv / lv5のICにおいては, 次々とtestをしながら条件が合うかどうかをcheckしていきます, そして, passすると, propertyをloadしてretするのです. これによって, ICが成功次第, もとのprogramのpathに戻ることができます.

ICが徐々に構築されていくさまを図で表します. 初回. 通常のLOAD_PROP stub function callになっています.

first

ICが構築されると, 最初のcallの対象がICになり, ICのtestで失敗するとLOAD_PROPへfallbackします.

second

また, LOAD_PROPは, 新たにICを構築し, 前に構築したICの最後のjmpを書き換え, 自分をchainにつなぎます. これによって, 一つのcallsiteで幾つものmapをhandleすることができます, これこそ, Polymorphicであるということです.

third

LoadProto/ChainPropertyIC & Map transition system

LoadOwnPropertyICにおいては, objectのmapが期待値かどうかをtestします, このtestにpassすれば, 対象のobjectのshapeはcacheをとった時のobjectのshapeと同じということであり, offset lookupによってpropertyを引っ張りだすことができます. では, prototypeにある場合, あるいはもっと上にある場合はどうでしょうか?

もっと上にあった場合, ICはその道中たどったobjectのshape全てが期待値を維持していることをtestしなければいけません. それは, 途中のobjectのshapeが変わることで, lookup先が変わる場合があるからです. ECMAScriptで例を示します.

function getToString(instance) {
  return instance.toString;
}
function Test() { }
var instance = new Test;
getToString(instance);    // lookup Object.prototype.toString
Test.prototype.toString = function() { };
getToString(instance);    // lookup Test.prototype.toString

一度目のtoString lookupでは,

  1. instance object
  2. Test.prototype
  3. Object.prototype

とたどってlookupしました. その後Test.prototype.toStringへの代入によってTest.prototypeのshapeが変わった事によって, Object.prototypeに至らずにlookupが終了するようになっています. ここでTest.prototypeのmap testをしなければ, この変更を検知できません.

では, 実際にLoadChainPropertyICのcodeを紹介します.

lv5/breaker/poly_ic.h

    void operator()(LoadPropertyIC* site, Xbyak::CodeGenerator* as, const char* fail) const {
      JSObject* prototype = NULL;
      as->mov(r11, r8);  // r11に対象のobject
      for (Chain::const_iterator it = chain_->begin(),
           last = chain_->end(); it != last; ++it) {
        // mapの数だけtestを出力
        Map* map = *it;
        IC::TestMapConstant(as, map, r11, r10, fail, Xbyak::CodeGenerator::T_NEAR);
        prototype = map->prototype();
        as->mov(r11, core::BitCast<uintptr_t>(prototype));
      }
      // last check
      IC::TestMapConstant(as, map_, r11, r10, fail, Xbyak::CodeGenerator::T_NEAR);
      // load
      LoadPropertyIC::GenerateFastLoad(as, r11, offset_);
    }

objectがlookupされた時, own objectからtarget objectに至るまでのmapをchainとして取得し, それに合わせてtestを出力しています. chainにはmapが詰まっており, このguardのcheckしているのは道中のobjectが全てあるときのmapと同じmapを持っているか?を確認しているのです.

注意して欲しいのは, 一番初めは, 実行時に与えられるobject, r11のmapを検査していますが, その後r11のprototypeを取るのではなく, chainからprototypeを取得しています. つまり, 実はこのguardではprototypeの探索をやっておらず, IC作成時に取得されたchainに属するobjectのmapが変わっていないかを確認しているだけなのです

chain

なぜr11のprototypeを動的にたどる必要がないのでしょうか?

それは, Mapの中にprototypeが含まれているからです. iv / lv5ではobjectのprototypeが変更されるとMap transitionが起こるようになっており, MapのIDの表す同じShapeの中には同じPrototypeであるという保証も含まれているからです. これによってmapが一致することを検査すると, 一つ上のprototype objectも変わっていないことも同時に検査できるのです.

Storing ALL information into Map ID

ICにおいてはMapのtestが重要となります. このため, Mapが何の一意性を表しているのかが非常に重要になります. 例えば, prototypeをMapに持たせてprototypeの変更によってMap transitionを起こすことにより, MapのIDのtestはprototypeが変わっていないことを保証することができるのです.

このため, 一般にECMAScript engineでは, Objectを以下のように設計します.

map

Mapがhashtableを持っており, hashtableにはkeyに対してattributesとoffsetが格納されています. そしてoffsetがObjectのslotを表しているというふうな実装です. 注目して欲しいのは, hashtableのvalueがoffsetだけではなく, attributesも含んでいるところです. slotの方には, property descriptorでいうところのvalueしか存在しません. なぜslotの方でattributesとvalueを持たないのでしょうか?

それはこのようにすることで, attributesをMapの管理下に置くことができるからです. そしてiv / lv5ではこのattributesが変わるだけでもMap transitionが起きます. writable:truewritable:falseにするとMap transitionが起こるのです. その結果, MapのIDはattributesが変わっていないことをも保証することができるのです

例えば, propertyをstoreするとします.

var obj = {};
for (var i = 0; i < 100; ++i) {
  obj.test = i;
}

この時, StorePropertyICを構築するとして, StoreOwnPropertyICが構築された時, ICは何をcheckすれば良いのでしょうか?

答えはなんと, Map checkをするだけで良いのです. もしもMapにattributesの情報が入っていなければ, lv5はstoreするたびにwritableがtrueであるかどうかを検査する必要があります. しかし, attributesの情報がMapに入っており, ICが構築されたとすれば, そのIC構築対象のMapのslotは当然writableであり, このMap checkをするだけで, writableなattributesかどうかのtestをも行なっていることになるのです.

Conclusion

iv / lv5におけるLoadPropertyPICの具体的なcodeを用いて, Map transitionの設計, PICの設計について説明しました.

ホワイトクリスマスイブになるそうですが, あずにゃんと一緒に楽しく過ごす予定です. iv / lv5はまだまだ高速化を予定しております, Context Threading JITが終了すると, 自作GC, SSA based optimizing JIT compilerへと進もうと考えております. また, ES6本格対応も検討しており, Meta Object Protocol(MOP, ECMAScripterにとって今熱い言葉の一つ)によるrewrite, cleanupも考えております. 来年度もiv / lv5にご期待ください><

Introducing ibrik - code coverage tool for CoffeeScript by using istanbul

ibrikImage: © lorises 2010

Istanbul made by Krishnan Anantheswaran from the Yahoo! Cocktail team is great code coverage tool for JavaScript. (see usage by Ariya Hidayat)

Internally it uses Esprima to parse JavaScript code and Escodegen to generate instrumented JavaScript code.

istanbul architecture

These modules use Mozilla JavaScript AST as Internal Representation. Therefore, if we prepare Mozilla JavaScript AST, istanbul can generate instrumented code and coverage result.

I've created ibrik, the code coverage tool for CoffeeScript by using istanbul and CoffeeScriptRedux compiler.

We can install it by

npm install -g ibrik

write test.coffee

call = ->
  console.log 'this is function'

a = 200

if no
  call()

if yes
  do -> console.log('hello')
  if no
    console.log 'out'

and use it by

ibrik cover test.coffee

We gets summary.

Statements   : 72.73% ( 8/11 )
Branches     : 50% ( 3/6 )
Functions    : 50% ( 1/2 )
Lines        : 66.67% ( 6/9 )

And by using istanbul, we can see coverage result on browser.

istanbul report html && open coverage/index.html

brower result

Internal

CoffeeScriptRedux made by Michael Ficarra generates Mozilla JS AST and generate JavaScript code by using Escodegen as its backend.

CoffeeScriptRedux architecture

So ibrik generates Mozilla JS AST by using CoffeeScriptRedux compiler and passes it to istanbul instrumenter.

ibrik archirecture

istanbul instrumenter refers line & column information attached to AST, so by attaching line & column information to original (CoffeeScript) code, we can get instrumented JavaScript code and trace CoffeeScript execution. This is the same logic to how CoffeeScriptRedux compiler generates SourceMap.

Future

ibrik implementation is still at very experimental stage. Check the ibrik project on GitHub.

Contributions are welcome.

JSC Array optimization for adding new property

This is a blog post for 12/6 VM advent calendar.

See http://qiita.com/advent-calendar/2012/vm for more nice blog posts :)

Introduction

ECMA262にとってArrayは最も重要なObjectの1つであり, loop内で高い頻度でアクセスされる性質上, Arrayの最適化はengineの実行速度に多大な影響を及ぼします.

ここではJavaScriptCoreの行なっているArrayに対して新しいpropertyを追加する処理の最適化を紹介します.

Background

ECMA262において, Arrayはliteral形式ならばown propertyを最初から定義できますが,

var array = [0, 1, 2, 3, 4];
console.log(array.hasOwnProperty('0'));  // true

それ以外の場合, lengthをconstructorに与えようと, lengthを増やそうと, 最初はemptyな状態で定義されます.

var array = Array(10);
console.log(array.length);  // 10
console.log(array.hasOwnProperty('0'));  // false
var array = [];
array.length = 10;
console.log(array.length);  // 10
console.log(array.hasOwnProperty('0'));  // false

また, ECMA262において, 代入は, [[Put]] internal method callとして表現されます. その[[Put]] step 1では [[CanPut]]によって, 実行可能かどうかを判断する項目があります.

  1. If the result of calling the [[CanPut]] internal method of O with argument P is false, then

[[CanPut]] は何のためにあるのか? これは, writableがfalseな書き込みのreject, getterだけ定義されていてsetterの無いpropertyへの代入の阻止, unextensibleなobjectのpropertyを増やす行為の阻止, といった判断をするためのpredicateです.

var obj = {};
Object.defineProperty(obj, 'a', { value: 1, writable: false });
obj.a = 2;
console.log(obj.a);  // 1

var obj = {};
Object.defineProperty(obj, 'a', { get: function() { } });
obj.a = 2;
console.log(obj.a);  // undefined

Problem

[[CanPut]] is very very slow

しかし, [[CanPut]], own propertyが見つからないときは, [[Prototype]]をたどる必要があります. というのも, setterやwritableをhandleしなければいけないからです. 簡単に説明すると以下のような形になります.

  1. If own propertyがある
    1. If data propertyならwritableをreturn
    2. Else accessorなのでsetterがあるかどうかをreturn
  2. Else If own propertyが無いなら, [[Prototype]]をたどって見つけてくる
    1. If data propertyなら, own propertyを新たに増やすので, own extensible && writableをreturn
    2. Else accessorならsetterがあるかどうかをreturn
  3. Else 見つからないのであれば, own propertyを新たに増やすので, own extensibleをreturn

これは, 以下のようなcaseに対応する必要があるからです.

writable: false

Object.defineProperty(Array.prototype, '0', { value: 100, writable: false });
var array = [];
array[0] = 200;
console.log(array[0]);  // 100

setter

Object.defineProperty(Array.prototype, '0', { get: function() { return 42; }, set: function() { } });
var array = [];
array[0] = 200;  // setter called
console.log(array[0]);  // 42

このため[[CanPut]]はもしも対象のpropertyがemptyであると[[Prototype]]ひとつひとつさかのぼって見ていかないといけません. もちろん一度対象indexにown propertyが作成されれば次回からはown propertyを見るだけで良いです.

しかしこれはつまり, 新しいpropertyを追加する際にはprototype chainを登って検証する必要があるということです. 新たなpropertyの追加はprogramにとって非常に多く実行される処理の1つであり, ここでchainをいちいち登るようなことがあってはperformance上大きな問題を抱えてしまいます またこのような複雑な行動ではICを構築することが難しくなります.

Adding new indexed property is executed frequently

一般にECMA262 engineではobjectのindexed propertyとnamed propertyを別々に管理します. これはindexed propertyとnamed propertyではその扱われ方の特徴が異なるからです. named propertyがmemberとして扱われその形状が暗黙的classを表す一方, indexed propertyは配列などのデータのindexとして扱われる傾向があります.

さて, propertyの代入が非常に多く行われるのはindexed propertyです. というのもindexed propertyではloop内で挿入/削除されることが考えられるからです. このようなArray的扱われ方をするobjectにおいて, new propertyを追加するたびに[[Prototype]]のchainを通るのは非常に高いコストとなります.

このため, indexed propertyを新たに追加する際に[[Prototype]]探索を省くことが出来れば, 大幅な高速化が見込まれます. これが今回の主題です.

JSC Array optimization

これを実現するためJSCはindexed property全般に対して前提条件を定め, これを満たすobjectについて最適化を行なっています. この前提は,

[[Prototype]]に設定されるobjectのindexed propertyには, writable:falseやaccessorは存在しない

です. これが成立すると, 新たなindexed propertyを追加するときに, [[Prototype]]をたどる必要がなくなり, 全てobject単体で判断できます.

[[Prototype]]たどってないけどindexed propertyにaccessorがないなら問題ないよねっ

この最適化は, JSCのruntime/JSObject.cpp, JSObject::putByIndex, JSObject::putByIndexBeyondVectorLength の処理にあらわれます.

NonArrayWithSlowPutArrayStorage, ArrayWithSlowPutArrayStorage 以外の場合は, [[Prototype]]を見ずに処理しています.

JSObject::putByIndex より抜粋

     // JSObject::putByIndexより抜粋. 殆どの場合, このpathに入る
     case NonArrayWithArrayStorage:
     case ArrayWithArrayStorage: {
         ArrayStorage* storage = thisObject->m_butterfly->arrayStorage();

         // 超えていたら, breakしてputByIndexBeyondVectorLengthへ
         if (propertyName >= storage->vectorLength())
             break;

         WriteBarrier<Unknown>& valueSlot = storage->m_vector[propertyName];
         unsigned length = storage->length();

         // Update length & m_numValuesInVector as necessary.
         if (propertyName >= length) {
             length = propertyName + 1;
             storage->setLength(length);
             ++storage->m_numValuesInVector;
         } else if (!valueSlot)
             ++storage->m_numValuesInVector;

         // それ以外の場合は単純にsetするだけ
         valueSlot.set(exec->globalData(), thisObject, value);
         return;
     }

これと同じようなことをJIT codeでも行なっています. さあめくるめくMacroAssemblerによる機械語生成codeへ!

jit/JITPropertyAccess.cpp, JIT::emitArrayStoragePutByVal

JIT::JumpList JIT::emitArrayStoragePutByVal(Instruction* currentInstruction, PatchableJump& badType)
{
    unsigned value = currentInstruction[3].u.operand;
    ArrayProfile* profile = currentInstruction[4].u.arrayProfile;

    JumpList slowCases;

    // ArrayStorageShapeかどうかのguard
    // ここで上記前提が成り立っているかどうかがcheckされる
    badType = patchableBranch32(NotEqual, regT2, TrustedImm32(ArrayStorageShape));
    loadPtr(Address(regT0, JSObject::butterflyOffset()), regT2);

    // storageの長さ以内に収まっているかguard
    // 収まっていなかったら, allocateしないといけない
    slowCases.append(branch32(AboveOrEqual, regT1, Address(regT2, ArrayStorage::vectorLengthOffset())));

    // indexでvalueを直接引っ張って, その値がemptyかどうかを検査
    // emptyならば, array hole
    Jump empty = branchTest64(Zero, BaseIndex(regT2, regT1, TimesEight, OBJECT_OFFSETOF(ArrayStorage, m_vector[0])));

    // valueをstore
    Label storeResult(this);
    // 値を持ってきて,
    emitGetVirtualRegister(value, regT3);
    // indexの場所にstore
    store64(regT3, BaseIndex(regT2, regT1, TimesEight, OBJECT_OFFSETOF(ArrayStorage, m_vector[0])));
    // endまでjump
    Jump end = jump();

    // emptyの時は
    empty.link(this);
    // array holeがあるよとarrayに記録しつつ (for further optimization)
    emitArrayProfileStoreToHoleSpecialCase(profile);
    // valueの数を更新して (+1)
    add32(TrustedImm32(1), Address(regT2, ArrayStorage::numValuesInVectorOffset()));
    // もしもlength以下だったら, lengthを増やす必要はないので, 上のstoreResultの位置にjump
    branch32(Below, regT1, Address(regT2, ArrayStorage::lengthOffset())).linkTo(storeResult, this);

    // lengthをindex + 1の値に変更して...
    add32(TrustedImm32(1), regT1);
    store32(regT1, Address(regT2, ArrayStorage::lengthOffset()));
    sub32(TrustedImm32(1), regT1);
    // storeResultの位置にjump
    jump().linkTo(storeResult, this);

    // end
    end.link(this);

    return slowCases;
}

このように非常に高速な機械語に展開されます.

見事, [[Prototype]]を一切たどらずに, 高速なnew property creationを達成しました.

End of Eden

上の最適化は, 当然前提が成り立っていることを前提としているわけで, 崩れてしまえば全く成り立たなくなります. JSCは, この前提が成り立っているobjectを注意深くmarkingして, 前提が成立しているobjectに対して最適化を行なっています.

では, この前提が守られているobjectかどうか, 以下にして追跡するのでしょうか?

[[Prototype]] and array storage state

[[Prototype]]にsetされるobjectというのは非常に限られています. 入り口としては, __proto__と, cunstroctor.prototype, またObject.createの引数といったものがあります.

ここで条件を注意深く絞ります. 例えば以下のようにされた場合,

var array = [];
var proto = {};
Object.defineProperty(proto, '0', { value: 0, writable: false });
var obj = Object.create(proto);

arrayには影響がありません. この場合前提が崩れるのはobjだけです. objは前提の崩れたobjectとして最初から作成されます.

このようにobject作成後に前提が変更されなければ良いのですが, 残念ながら作成後のobjectの前提を崩すことができます. [[Prototype]]に設定されているobjectが変更された時です. 例えば以下のような場合です.

var array = [];
var obj = Object.create({});
var proto = Object.getPrototypeOf(obj);
Object.defineProperty(proto, '0', { value: 0, writable: false });
var array = [];
Object.defineProperty(Array.prototype, '0', { value: 0, writable: false });

これはheap中にある全てのobject(array含む)に影響があります. なぜなら, protoArray.prototype[[Prototype]]に設定されたことのあるobjectという情報はあっても, どのobjectの[[Prototype]]なのかという情報は持っていないからです(それを持っていては, 巨大な辞書が必要になります). そのため, 現在heapにある全てのobjectの前提が崩れたとみなさざるを得なくなります.

とはいってもarrayはもう作成してしまいました. これをたどる術がないのにどうやってarrayに「前提が崩れたobjectである」とmarkingするのでしょう?

実はたどる術はあります, だってGCはたどってますよね?

Switch heap objects storage to slow kind

runtime/JSObject.cpp, JSObject::notifyPresenceOfIndexedAccessorsはその名の通り, indexed propertyにreadonly OR accessorが定義された時に呼ばれます.

void JSObject::notifyPresenceOfIndexedAccessors(JSGlobalData& globalData)
{
    // もうこのobjectの[[Prototype]]より上でindexed propertyにaccessorがあるから,
    // もうすでに前提が崩れたことはheapに反映されていますよというcheck
    if (mayInterceptIndexedAccesses())
        return;

    // structure (HiddenClass / Map / Shapeお好きなように) をtransitさせる
    setStructure(globalData, Structure::nonPropertyTransition(globalData, structure(), AddIndexedAccessors));

    // [[Prototype]]に設定されたことがなければ無害
    if (!mayBeUsedAsPrototype(globalData))
        return;

    // 残念...
    globalObject()->haveABadTime(globalData);
}

そして, runtime/JSGlobalObject.cpp, JSGlobalObject::haveABadTimeが呼ばれます. 前提が崩れたことが反映されます. 大技.

void JSGlobalObject::haveABadTime(JSGlobalData& globalData)
{
    ASSERT(&globalData == &this->globalData());

    if (isHavingABadTime())
        return;

    // Make sure that all allocations or indexed storage transitions that are inlining
    // the assumption that it's safe to transition to a non-SlowPut array storage don't
    // do so anymore.
    m_havingABadTimeWatchpoint->notifyWrite();
    ASSERT(isHavingABadTime()); // The watchpoint is what tells us that we're having a bad time.

    // Make sure that all JSArray allocations that load the appropriate structure from
    // this object now load a structure that uses SlowPut.
    for (unsigned i = 0; i < NumberOfIndexingShapes; ++i)
        m_arrayStructureForIndexingShapeDuringAllocation[i].set(globalData, this, originalArrayStructureForIndexin    gType(ArrayWithSlowPutArrayStorage));

    // Heapにあるobjectを全部探してきて, 片っ端から最適化flagをoffにして回る!!
    //
    // Make sure that all objects that have indexed storage switch to the slow kind of
    // indexed storage.
    MarkedArgumentBuffer foundObjects; // Use MarkedArgumentBuffer because switchToSlowPutArrayStorage() may GC.
    ObjectsWithBrokenIndexingFinder finder(foundObjects, this);
    globalData.heap.objectSpace().forEachLiveCell(finder);
    while (!foundObjects.isEmpty()) {
        JSObject* object = asObject(foundObjects.last());
        foundObjects.removeLast();
        ASSERT(hasBrokenIndexing(object));
        object->switchToSlowPutArrayStorage(globalData);
    }
}

GCと同じくheap上のobjectをすべて探してきて, 片っ端から前提が崩れたことを反映させます. これによりすでに作られてしまったJIT codeもすべてArrayShape guardの時点でfailさせることによってinvalidateし, putByIndexなどもslow patternに変わり, で一件落着ですね.

Conclusion

というわけで, JSCは前提を定めてそれに対する最適化を行い, この前提が崩れた際にはHeapを無理やり修正するという手段でもって最適化を行なっているのでした.

くれぐれも, indexed propertyにaccessorを指定しないようにしましょう.

LL Decadeに参加してきました

LL Decadeに参加してきましたー!
プログラミング言語処理系を自作してわかったこと | LL Decade

このメンツ, サンドバックになる気配を敏感に感じ取り, 「やばいっ!」と思っていたのですが, 皆さん優しい方ばかりで, 意外にサンドバックになりませんでした. よかったですです...

資料は以下のものになります.

x86 / x64最適化勉強会の際よりも, engine全体を俯瞰する形で, また, ES.next方面の話を入れる等の構成にしました.

shibuya: the ES.next engineの話

shibuya

概要としては, esprima harmony branchを用いてES.next engineを作り, 最適化可能ポイントを探りlv5での実装のための知識の蓄積を行い, 同時にES.nextの仕様のbugを発見, また非効率的, パフォーマンス上問題になり得る場所を特定し, 仕様へ貢献していこうという趣旨のprojectです.
yieldなどどうしても無理なところ以外は, 完全に仕様のAbstract Operationと実装が一致することを目指しており, この点lv5とまた少し毛色の違う, より原理主義的な仕様準拠を掲げています.

まだ, あまり実装が出来上がっていませんが, どんどん実装していこうと思います.

また, もちろん, 主に自分が楽しいというのが入っているのも当然あります...

感想

mruby が非常に気になっていて, 是非お聞きしてみたいと思っていたことを聞くことができ, とてもためになりました. ありがとうございます. IC (いもうとコンプレックス, a.k.a. Inline Caching), かわいいですね... LowLevelに落としてすみません...

うさみみがインパクトすごかったです, Functional City Nagoya怖い...
LLの文化を感じ取ることのできる, 非常に刺激的なイベントでした. 参加者, 運営の皆様, 本当にありがとうございました. とても楽しかったです!

補足

鈍器購入しました.

f:id:Constellation:20120805010041p:image