kakts-log

programming について調べたことを整理していきます

v8 ver6.0まとめ

v8 ver6.0がリリースされました。
ざっくりと新機能や改善点を整理します。
v8project.blogspot.jp

Main features

SharedArrayBuffer

ver6.0から、SharedArrayBufferがのサポートが開始されました。

developer.mozilla.org

SharedArrayBufferは、javascriptワーカーと、ワーカー間の同期制御時にメモリを共有するローレベルメカニズムです。

Object rest/spread properties

ES.nextの仕様において、現在stage3 である Object rest/spread propertiesが採用されました。

変数宣言時に、Object内の特定のプロパティを指定でき、さらに …restと記述すれば、指定されていない残りのプロパティをまとめて取得できます。

// Rest properties for object destructuring assignment:
const person = {
  firstName: 'Sebastian',
  lastName: 'Markbåge',
  country: 'USA',
  state: 'CA',
};
const { firstName, lastName, ...rest } = person;
console.log(firstName); // Sebastian
console.log(lastName); // Markbåge

// firstName, lastName以外のプロパティをまとめて取得できる
console.log(rest); // { country: 'USA', state: 'CA' }

// Spread properties for object literals:
// オブジェクトリテラルを用いて変数を宣言する際にも同様に記述して使うことができる
const personCopy = { firstName, lastName, ...rest };
console.log(personCopy);
// { firstName: 'Sebastian', lastName: 'Markbåge', country: 'USA', state: 'CA' }

ES6 Performance

v8 ver6.0において、ES2015の機能のパフォーマンス改善もされています。 javascriptのパフォーマンスベンチマークツールである Ares-6において、10%の改善がみられたようです。

http://browserbench.org/ARES-6/

v8 API

v8 APIに関してもいくつかの変更が加えられています。
変更点詳細は下記ページにまとまっています。
docs.google.com

npm5から導入された package-lock.jsonについて

先日npm5がリリースされました。同時期にリリースされたNode.js v8.0.0にもバンドルされており、
複数ある新機能のうち、package-lock.jsonについて気になったので本家のドキュメントの内容を読んでまとめました。

docs.npmjs.com

package-lock.jsonについて

package-lock.json はnode_modules配下やpackage.jsonに変更があった際に自動で作成・変更されるファイルです。
具体的には、 npm install npm update npm uninstallなど、パッケージに変更が加えられるタイミングで作成・変更されます。

このファイルはpackage.jsonなどのように、リポジトリのソースの一部として組み込まれるように設計され、様々な目的のために利用されます。

package-lock.jsonを導入する目的は以下のとおりです。

  • リポジトリの依存関係を表現する単一の方法を提供する。
    チームメンバーそれぞれの環境での開発時や、CIによるデプロイ時など、環境に限らず同じ依存関係をもってサブモジュールをインストールできることを保障します。

  • 対象のサブモジュールに対して、過去のバージョンに容易に戻れるような手段を提供する。

  • 可読性のあるソースコードにより、モジュール改装の変更の可視化を容易にする。

  • npmパッケージのインストールプロセスの最適化
    すでにインストール済みのパッケージのメタデータ解析をスキップする事により、インストールプロセスの最適化を実現します。
    yarnと比べるとまだまだ遅いですが、npm4と比べるとかなり速度が改善しています。
    docs.google.com

package-lock.jsonの重要な点は、ファイルが公開できることと、もしトップレベルモジュールにpackage-lock.jsonファイルがある場合、下位モジュールでのpackage-lock.jsonは無視されるということです。
npm4で存在していた、npm-shrinkwrap.jsonとフォーマットを共有しているため、本質的には中身は同じものですが、package-lock.jsonはファイルを公開できることが異なります。
しかしpackage-lock.jsonを公開することは、CIツールを使ったデプロイを行うか、本番環境への公開プロセスを使用しない限り、おすすめできません。

もしpackage-lock.jsonとnpm-shrinkwrap.jsonがパッケージのルートディレクトリに両方存在していた場合、
package-lock.jsonは完全に無視されます。

参考

npm5の他の機能も解説されており、勉強になります。
yosuke-furukawa.hatenablog.com

npm-shrinkwrap.jsonとpackage-lock.jsonとの違いについて stackoverflow.com

docker run時にホスト上のランダムなポートにコンテナを割り当てる

docker run時にコンテナ内の特定のポートに、host上のランダムなポートをbindさせる方法をまとめます。

簡単なwebサーバの実装とDockerコンテナ用のDockerfileの記述

今回、下記のような構成で簡単なwebサーバを作るとする。

$ tree
.
├── Dockerfile            # webサーバ用コンテナのDockerfile
└── app
    └── identidock.py  # Flask webサーバの実装

今回は本筋でないので説明しませんが、pythonのwebフレームワークであるFlaskを使って、localhost の/に対してhttpリクエストしたときに Hello Worldを返す簡単なサーバを作ります。
./app/identidock.py に下記のように実装します。

from flask import Flask
app = Flask(__name__)

@app.route('/')
def hello_world():
    return 'Hello World\n'

if __name__ == '__main__':
    app.run(debug = True, host = '0.0.0.0')

続いて肝心なDockerfileの説明をします。
uwsgiというユーザ・グループを作成した上で、 コンテナ内の9090番ポートにwebサーバ、9191番にサーバパフォーマンス統計用のサーバを立ち上げる設定を記述します

FROM python:3.4


# uswgiというグループ・ユーザを作成
RUN groupadd -r uwsgi && useradd -r -g uwsgi uwsgi

# Flask uWSGI pip install
RUN pip install Flask==0.10.1 uWSGI==2.0.8

# コマンド実行時の作業ディレクトリ指定
WORKDIR /app

# ./appをコンテナ内にあるファイルシステムの/appにコピーする
COPY app /app

# 解放するポートを明示的に指定
EXPOSE 9090 9191
# これ以降のすべての行の実行ユーザをuwsgiに設定する
USER uwsgi

# uWSGIを実行する新たなコマンドを生成する
# uWSGIに対して、9090ポートで待ち受けるhttpサーバを起動させる。 /app/identidock.pyからappというアプリを実行させる
# 9191でstatsサーバも起動する
CMD ["uwsgi", "--http", "0.0.0.0:9090", "--wsgi-file", "/app/identidock.py", "--callable", "app", "--stats", "0.0.0.0:9191"]

これで、ひとまずwebサーバ用のDockerコンテナの準備ができたので、buildしていきます。

webappという名前でDockerコンテナのbuildを行います。

$ docker build -t webapp .

Dockerコンテナを指定したホスト上のポートにbindさせる

まずは、Dockerコンテナ内の 9090, 9191番ポートをホスト上の指定したポートにbindさせます。
方法としては、docker runコマンド実行時に、オプションで設定させるだけです。

コンテナ内の9090,9191を下記のポートにbindさせることとします。

  • 9090番ポート → host上の9090番ポート 9090:9090
  • 9191番ポート → host上の9191番ポート 9191:9191
    上記のように、 ${host上のポート}:${コンテナ内のポート}という形式で、docker run時に -pオプションで追加してあげればbindすることができます。
    同時に、コンテナ名を webapp-testとします
$ docker run -d -p 9090:9090 -p 9191:9191 --name webapp-test

docker runが完了したら、実際にポートがbind されているか、 docker portで確認します。

# docker port確認
$ docker port webapp-test
9191/tcp -> 0.0.0.0:9191
9090/tcp -> 0.0.0.0:9090

#  疎通確認
$ curl localhost:9090 
Hello World

これで、指定したホスト上のポートにDockerコンテナをbindさせることができました。

Dockerコンテナにホスト上のポートをランダムにbindさせる。

今度は、Dockerコンテナの9090, 9191に対して、ホスト上の大きな番号のポートを自動的に割り当てます。
この方法は非常に簡単で、 docker run 時に -P を引数として使うことで、実現できます。

docker run –helpでは、-Pオプションは以下のように説明されています。

-P, --publish-all    Publish all exposed ports to random ports

やることはこれだけです。

# ホスト上のランダムなポートにコンテナを割り当てる
$ docker run -d -P --name webapp-test webapp

# ポート確認
$ docker port webapp-test
9090/tcp -> 0.0.0.0:32769
9191/tcp -> 0.0.0.0:32768

Dockerコンテナへのランダムなポートbindの利点

このランダムなポートbindの利点としては、ある1台のホスト上に複数のコンテナを実行する際に、使われていないポートを自分で管理して明示的にしていするよりも、ポートのbindを全部Docker側に任せる事ができるので、管理が楽になります。

docker exitedなコンテナをまとめて削除する

dockerでの開発中に、docker runしてエラーが発生し、exitedになっているコンテナが残った状態になる場合があります。

$ docker ps -a
CONTAINER ID        IMAGE                    COMMAND                  CREATED             STATUS                     PORTS                    NAMES
0efc271c4b9e        testapp               "python identidock.py"   6 seconds ago       Exited (1) 4 seconds ago                            gifted_nobel
cf94c6f94ae3        testapp               "bin/bash"               10 seconds ago      Created                                             stoic_murdock
65ebe4051e20        testapp               "bin/bash"               5 minutes ago       Created                    0.0.0.0:5000->5000/tcp   infallible_ritchie

コンテナ名やIDを指定して下記のように1つずつコンテナを削除するのもできます

$ docker rm ${CONTAINER_NAME}
$ docker rm ${CONTAINER_ID}

これでは複数exitedになっている場合大変なので、docker rmの引数に、exitedなコンテナのIDをまとめて渡すようにします。

exitedなコンテナのIDのみ取得する

まず、docker ps -aを実行したときに表示されるコンテナの一覧から、 statusがexitedなもののコンテナIDのみ出力させるようにします。 –filterで条件を指定することでコレが可能になります。

status exitedなコンテナのIDのみ表示させる
$ docker ps -a --filter 'status=exited' -q
0efc271c4b9e
cf94c6f94ae3
65ebe4051e20

これをdocker psの引数として渡すことで、exitedなコンテナをまとめて削除できます。

# exitedなコンテナをまとめて削除する
$ docker rm $(docker ps -a --filter 'status=exited' -q)

Hash-Based サーチアルゴリズム まとめ

今回、多くの要素を持ち、必ずしもソートされていないコレクションに対して特定の値を探す際に効果的なHash-Basedサーチアルゴリズムについてまとめます。
日本語ではハッシュ法による探索アルゴリズムと呼ばれることもあります。

Hash-Basedサーチアルゴリズム

一般的によく知られたアプローチの一つは、hash関数をつかって、検索対象のコレクションの要素内の特徴を使ってハッシュテーブルのインデックスに変換することです。
ハッシュ法によるサーチは、シーケンシャルサーチやバイナリサーチよりも、average-caseでのパフォーマンスがより良いものとなっています。

Hash-Basedサーチにおいて、n個の要素を持つ集合Cは最初にHと呼ばれるハッシュテーブルと、配列構造を持つb個のビンにロードされる。
この前処理はO(n)のパフォーマンスを持つが、 しかし後の検索においてパフォーマンスが向上する。 ハッシュ関数のコンセプトはこのパフォーマンス向上を可能にする。

ハッシュ関数は各要素Ciを整数値hiに変換する決定関数です。
まず、hiを 0<= hi < bと仮定する。 要素をハッシュテーブルに読み込む時、 Ciは H[hi]のビンに格納される。 すべての要素が格納された後、アイテムtを探索する場合は H[hash(t)]のビンの中から要素を探索する

ハッシュ関数は、もし要素CiとCjが同値の場合 hash(Ci) == hash(Cj)となることを保証します。
これは、集合Cの中の要素のうち、ハッシュ値が同じ場合がありうることを意味します。
これはハッシュ衝突として知られ、ハッシュテーブルはこの状況に対応する方法が要求されます。

最もよく知られた解決策として、各ハッシュインデックスにlinked listを保持し、すべてのハッシュ衝突したデータをハッシュテーブルに格納する手法があります。
各ハッシュインデックスが保持するlinked listは線形的にサーチされる必要がありますが、各linked listの要素数は非常に少ないため、探索時間は短くすみます。

下記の疑似コードはハッシュインデックスが衝突した際の linked-listの振る舞いを書いている

  • Uを取りうるハッシュ値の集合とする。 各要素e は Cに属していて、 ハッシュ値 h は Uに属する
  • ハッシュテーブルHはb個のビンを持っている。各ビンは集合Cの中からn個の要素を持つ。
  • ハッシュ関数hashは、集合Cのすべての要素eに対して 0<= h <bとなるハッシュ値hを出力する
Best, Average O(1)
Worst O(n)

// ハッシュテーブルをロードする
loadTable (size, C)
    H = new array of given size
    foreach e in C do
        h = hash(e)
            if H[h] is empty then
            H[h] = new Linked List
            add e to H[h]
    return A
end

// サーチ
search (H, t)
    h = hash(t)
    list = H[h]
    if list is empty then
        return false
    if list contains t then
        return true
    return false
end

Hash-Basedサーチの2つの問題

Hash-Basedサーチを実装するにあたって、主要な問題は2つあります。
- ハッシュ関数のデザイン
- ハッシュ値衝突のハンドリング

綿密に設計されていないハッシュ関数は、ハッシュキーをハッシュテーブルに分配するロジックが良くないため、ハッシュテーブルへの値の格納において、偏りがでてしまいます。
そして、特定のビンに多くの値が格納されるので、ハッシュ衝突が起きる割合が多くなります。
これはhash-basedサーチにおけるパフォーマンスの低下を招きます

input/output

イナリサーチと異なり、Hash-Based searchにおいては、サーチ対象のコレクションCは必ずしもソートされる必要がない。 もしCがソートされていた場合、Cの各要素をハッシュテーブルHに格納するハッシュ関数は、H内部で元のソート情報を保持することがないので意味がない

Hash-Based-Searchにおける入力は、既に作成済みのハッシュテーブルHと、サーチ対象の要素tです。 アルゴリズムは、要素tが、ハッシュ関数を適用した出力値 h = hash(t)として、H[h]のビンに含まれている場合trueを返す。

もし213,557個の英単語の配列があるとして、ある単語を探す場合 バイナリサーチの場合は最大で18回(log(213557) = 17.70)の探索が必要です。 Hash-Based Searchの場合比較回数は、コレクションのサイズというよりも、ハッシュテーブルの各ビンが保持するlinked-listの長さに依存します。

ハッシュ関数について

hash関数を定義するに当たって、ゴールは多くの異なる値を正の数に変換し、各要素を必ずしもユニークにする必要はない ハッシュ化は何十年にも渡って研究されてきているが、その多くの手法はサーチ以外の目的に対しても使うことができる。

例えば、特別なハッシュ関数は暗号化に使われたりする。 サーチにおいては、ハッシュ関数はハッシュテーブルへの値のばらつきが均一であることと、計算時間が短いものが良いです。 → ハッシュ関数の実装については後日まとめます。。。

v8 "Launching ignition and Turbofan" 和訳

先日リリースされたv8 5.9において、新たなコード実行パイプラインが導入され、大きくパフォーマンスが向上したとのことです。
今後リリースされるNode.js ver8においてもv8 5.9が使われるため、概要を整理するためにv8本家のブログを和訳してまとめてみました。
v8project.blogspot.jp

Launching ignition and Turbofan

v8 5.9から新しいjavascript実行パイプラインが導入されました。 Chromeでは、バージョン59からこれが導入されます。
新しい実行パイプラインでは、従来と比べてパフォーマンスが大きく向上し、javascript アプリケーションにおいてメモリの使用量に関してもかなり改善されます。

新しいパイプラインは、Ignitionというv8のインタプリタによって動作し、さらにTurboFanとよばれるv8の新しいコンパイラによって最適化されます。

v8 5.9において初めて、IgnitionとTurboFanが導入されました。
これは、2010年からv8によって使われていたFull-codegenとCrankshaftが最新のjavascriptの機能と最適化にキャッチアップできなくなってきたことによります。
v8チームは、Full-codegenとCrankShaftを近々完全に除外する予定で、これはv8が今後シンプルでさらにメンテナブルなアーキテクチャを採用することを意味します。

A Long Journey

IgnitionとTurboFanを組み合わせたパイプラインは3年半ほど開発が続いていました。
この開発により、v8チームは実際に稼働しているjavascriptのパフォーマンス計測の知見を集め、Full-codegenとCrankshaftによるパイプラインの欠点を注意深く考慮しました。
これによりv8チームはjavascript全体の最適化を続けるための基礎を固めることができました。

TurboFanについて

TurboFan プロジェクトは、Crankshaftによる欠点に対処するために2013年後半にスタートしました。
Crankshaftはjavascriptのサブセットのみ最適化することができます。
例えば、Crankshaftは、try-catch-finallyキーワードを利用した例外ハンドリングを行うjavascriptコードを最適化するようには設計されていませんでした。
Crankshaftにおいては、javascriptの新たな機能に対応することが難しく、これらの新機能はほぼ常に9つものプラットフォームのためにアーキテクチャに依存したコードを書く必要がありました。
さらに、Crankshaftのアーキテクチャは、最適化されたマシンコードを生成することのみに制限されています。
これにより、チップアーキテクチャ毎に1万行を超えるコードをメンテナンスするv8チームの要求にも関わらず、パフォーマンスを最大限に発揮できませんでした。

TurboFanはES5当時のすべてのjavascriptの機能に対して最適化するだけでなく、ES2015やそれ以降の新たな機能に対しても最適化を行えるように設計されました。
TurboFanは高レベル・低レベルの間をうまく分割することができるようなレイヤー構造のコンパイラデザインを導入し、アーキテクチャ依存のコードを変更することなく新たな機能を追加することが容易です。
さらに、暗黙的な命令コンパイルのフェーズを導入し、各プラットフォームに対するアーキテクチャ依存のコードを極力減らすことが可能です。
この新たなフェーズの導入により、アーキテクチャ依存のコードは1度きりだけ書いて、後に変更する必要がほとんどありません。
このフェーズや他の機能に対する決定によって、v8がサポートするすべてのアーキテクチャにおいて、メンテナンス性が向上し、コンパイルの最適化コードにかかるコストが軽減しました。

Ignitionについて

v8のIgnitionインタプリタにおける開発当初の動機としては、モバイル端末におけるメモリ消費の削減が挙げられます。
Ignition導入前は、v8のFull-codegenによって生成されたコードは、Chromejavascriptヒープメモリの1/3ものメモリを占めていました。
これにより、実際のwebアプリケーションのデータのための容量が小さくなってしまっていました。

Chrome M53でIgnitionが導入された当時、制限されたRAM容量をもつAndroidバイスにおいて、最適化されていないjavascriptコードのためのメモリ領域が減少していることが ARM64ベースのモバイル端末において確認されました。

後に、v8チームはIgnitionのバイトコードが、Crankshaftがソースコードからリコンパイルするよりも、最適化されたマシンコードを生み出すために活用できるという利点を活かしました。
Ignitionのバイトコードはよりクリーンで、よりエラーを起こしにくいベースライン実行モデルをv8にもたらし、v8のAdaptive Optimization*1の重要な特徴である、Deoptimizationメカニズムをシンプルな構造にしました。
最終的に、バイトコードの生成がFull-codegenコンパイルコードの生成よりも早くなり、Ignitionの実行によってスクリプトの高速化をできるようになりました。

IgnitionとTurboFanのデザインを密接に組み合わせることで、アーキテクチャ全体の利点があります。
例えば、v8チームは、Ignitionのハイパフォーマンスなバイトコードハンドラを手で書いて組み合わせるよりも、
TurboFanの中間表現をバイトコードハンドラの機能を表現するために用い、TurboFanに最適化と多くのプラットフォームのためのコンパイル済みコードを生成させる方針をとりました。
これにより、Igtionプラットフォームがすべてのチップアーキテクチャにおいて改善され、メンテナンスの負荷がなくなりました。

Running the Numbers

ここでは新しいパイプラインによるパフォーマンスとメモリ消費を見ていきましょう。

v8チームは定期的にTelemetry-Catapultフレームワークを使って、javascriptのアプリのパフォーマンスを調査してきました。
以前にブログ記事*2に書いたように、実際のアプリケーションにおけるパフォーマンスのテストを行うことが、いかに我々の最適化の仕事をすすめるかといったことを議論してきました。
Ignition-TurboFanパイプラインへの変更によって、実際のアプリケーションにおいて改善が見られました。
特に、幾つかの有名なウェブサイトにおいて、ユーザインタラクションテストの実行スピードの向上が見られました。
f:id:kakts:20170517001921p:plain

f:id:kakts:20170517001930p:plain

Speedometerは統合的なベンチマークツールであるが、我々は、他の統合的なベンチマークよりもSpeedometerがより実際のアプリケーションの負荷を近似していることをあきらかにしました。
Ignition-TurboFanパイプラインへの変更によって、v8のSpeedometerベンチマークが5-10%向上しました。

サーバサイドjavascriptにおいても同様に速度向上がみられ、AcmeAirとよばれるnode.jsのベンチマークにおいても10%以上の向上がみられました。

f:id:kakts:20170517002624p:plain

IgnitionとTurboFanはv8全体のメモリ使用量を減らします。 Chrome M59において、このパイプラインはデスクトップやハイエンドなモバイル端末のメモリ使用量を5-10%減らします。
このメモリ使用量削減は、以前のブログ記事*3で取り上げたIgnitionのメモリ 管理をv8にもたらしたことに起因します。

これらの改善はあくまでも序章で、IgnitionとTurboFanのパイプラインは、今後のjavascriptのパフォーマンス向上のための最適化と、ChromeとNode.jsにおけるv8のメモリ使用量の削減を容易にします。

How browserify works

browserifyの仕組みに関して調べてみたのでメモ

How browserify works

browserifyはコマンドで指定したソースコードからAbstract syntax treeAbstract syntax tree - Wikipedia による静的解析を行い、コードの中に書かれているrequire()を探す。
ソースコード中にrequire()が存在した場合、ファイル中の module 文字列を元にファイルパスを特定し、更に再帰的にrequire()があるかたどっていく。

各ファイルは、静的に解析され、1つのマップにまとめられた1つのrequire()関数にマッピングされ、1つのjsファイルに結合される。
これは、browserifyによって吐き出されたjsファイルは、完全にself-containedであり、アプリケーションが必要とするすべてのものをオーバーヘッド無しで保持できることを意味する。

why concatenate

browserify はサーバ上で動作するビルドステップです。 アプリケーションのすべての依存関係を含んだ単一のbundle fileを生成します。
ここでは、ブラウザ用のモジュールシステムの実装方法を紹介し、各手法のメリット・デメリットについてまとめます。

window glocals

module システムを使う代わりに、各jsファイルがwindow グローバルオブジェクトにプロパティを定義するか、内部の名前空間を利用した実装を行います。 このアプローチは、結論から言うとうまくスケールしません。なぜならば、扱うファイルが増えるたびに、すべてのhtmlページに scriptタグを使って各ファイルを読み込む必要があります。
さらに、あるファイル内で、他のファイルで定義されるモジュールを使っている場合、order-sensitiveであり、読み込む順序を意識する必要があります。
これは非常にリファクタリングとメンテナンスがしづらいのがデメリットですが、すべてのブラウザでこのアプローチを取れることと、サーバサイドのツールが必要ないことがメリットになります。

concatenate

window globalsにプロパティを定義する代わりに、サーバサイドであらかじめすべてのスクリプトを結合する手法があります。
この手法ではいまだにorder-sensitiveで、順番に依存しますが、script タグ1つですむため、ローディングが早くなります。

source mapが無い場合、スローされた例外からは簡単に元のファイルのコードを辿れません。

参考

github.com