ワズムかどうかワズム？

Linkuriousは、LinkuriousEnterpriseに取り組んでいます。これは、グラフとその視覚化ツールの力を活用して、世界中の企業や政府が金融犯罪と戦うのを支援するWebベースのプラットフォームです。



Linkurious Enterpriseの主な機能の1つは、素人向けに設計された、習得と使用が簡単なグラフ視覚化インターフェイスです。 2015年、グラフを視覚化するための既存のJavaScriptライブラリの機能に不満を感じ、独自のライブラリであるOgmaの開発を開始しました。











Ogmaは、ネットワーク構造のレンダリングを目的としたレンダリングおよび計算パフォーマンスのJSライブラリです。D3.jsやSigma.jsなどの他のJavaScriptツールを使用してネットワーク構造がどのようにレンダリングされるかを見たことがあるかもしれません。これらのツールの機能が不足していました。私たちが使用していたソリューションには、特定のパフォーマンス要件を満たすために、いくつかの特定の機能があることが重要でした。サードパーティのライブラリでどちらも見つかりませんでした。そのため、独自のライブラリをゼロから開発することにしました。

仕事

ネットワーク構造の視覚化



Ogmaライブラリは、最先端のアルゴリズムを使用するように設計されています。高度なWebGLベースのレンダリングエンジンからその深部で使用されるWebワーカーまで、そのすべてのコンポーネントは、利用可能な最高のネットワークレンダリングパフォーマンスを提供することを目的としています。私たちの目標は、長期的なタスクを実行するときにライブラリを非常にインタラクティブにし、ライブラリに実装されている主要なグラフ視覚化アルゴリズムが迅速かつ安定して機能するようにすることでした。



WebAssembly（Wasm）テクノロジーは、最初に報告された瞬間から、Web開発者に以前に利用可能だったものと比べて遜色のないレベルのパフォーマンスを約束してきました。同時に、開発者自身が新しいテクノロジーを使用するために過度の努力をする必要はありませんでした。彼らは、コンパイル後にブラウザで実行できる、知っている高性能言語でコードを書く必要がありました。



Wasmテクノロジーが少し開発された後、実装する前に試してみて、いくつかのパフォーマンステストを実施することにしました。一般的に、振り返らずに高速のWasmトレインに飛び込む前に、安全にプレイすることにしました。



Wasmに私たちを惹きつけたのは、このテクノロジーがJavaScriptよりも効率的にメモリとプロセッサリソースを使用して、問題をうまく解決できることでした。

私たちの研究

私たちの研究は、同様のデータ構造を使用してさまざまな言語に簡単に移植できるグラフを操作することを目的としたアルゴリズムの検索から始まりました。



n-bodyアルゴリズムを選択しました。これは、フォースグラフの視覚化アルゴリズムを比較するためのベースラインとしてよく使用されます。このアルゴリズムに従って実行される計算は、視覚化システムの中で最もリソースを消費する部分です。このようなシステムの作業のこの部分を以前よりも効率的に実行できれば、これはOgmaに実装されているすべてのフォースグラフ視覚化アルゴリズムに非常に良い影響を及ぼします。

基準

嘘、ひどい嘘、そしてベンチマークがあります。



Max DeMarzi



「正直な」ベンチマークを開発することはしばしば不可能な作業です。事実、人工的に作成された環境では、現実の世界に典型的なシナリオを再現することは困難です。複雑なシステムに適した環境を作成することは、常に非常に困難です。実際、実験室環境では外部要因を制御するのは簡単ですが、実際には、ソリューションの「パフォーマンス」がどのように見えるかは、多くの予期しないものの影響を受けます。



私たちの場合、ベンチマークは、n-bodyアルゴリズムの実装のパフォーマンスを調べることで、明確に定義された単一の問題を解決することを目的としていました。



これは、信頼できる組織がパフォーマンスを測定するために使用する、明確で十分に文書化されたアルゴリズムです。プログラミング言語。



他の公正なテストと同様に、私たちは研究するさまざまな言語のためにいくつかのルールを事前に定義しています：

• アルゴリズムのさまざまな実装では、同様のコード構造を使用する必要があります。
• 複数のプロセスまたは複数のスレッドを使用することは禁止されています。
• SIMDの使用は禁止されています。
• 安定したバージョンのコンパイラのみがテストされます。ナイトリー、ベータ、アルファ、プレアルファなどのリリースを使用することは禁止されています。
• 各言語には、最新のコンパイラバージョンのみが使用されます。

ルールを決定した後、すでにアルゴリズムの実装に進むことができました。ただし、これを行う前に、パフォーマンスを調査する言語を選択する必要もありました。

JSの競合他社

Wasmは、ブラウザで実行される命令のバイナリ形式です。さまざまなプログラミング言語で書かれたコードは、この形式にコンパイルされます。彼らはWasmコードを人間が読めるコードとして言っていますが、Wasmで直接プログラムを書くことは、正気の人が下すことができる決定ではありません。その結果、ベンチマーク調査を実施し、以下の候補を選択しました。

• C
• さび
• AssemblyScript

n-bodyアルゴリズムは、これら3つの言語で実装されました。さまざまな実装のパフォーマンスを、基本のJavaScript実装のパフォーマンスと比較しました。



各アルゴリズムの実装では、1000ポイントを使用し、異なる反復回数でアルゴリズムを実行しました。各プログラムセッションを完了するのにかかる時間を測定しました。



テストは、次のソフトウェアとハ​​ードウェアを使用して実行されました。

• NodeJS 12.9.1
• Chrome 79.0.3945.130（公式ビルド）（64ビット）
• clang10.0.0-C言語で実装されたアルゴリズムのバージョン
• emcc 1.39.6-コマンドラインからEmscriptenコンパイラを呼び出すためのフロントエンド、gcc / clangの代替、およびリンカー
• 貨物1.40.0
• wasm-pack 0.8.1
• AssemblyScript 0.9.0
• MacOS 10.15.2
• Macbook Pro 2017 Retina
• Intel Dual Core i5 2,3 GHz、8GB DDR3、256GB SSD

ご覧のとおり、テストでは最速のコンピューターではなく、Wasm、つまりブラウザーのコンテキストで実行されるコードをテストしています。そして、とにかく、ブラウザは通常、システムで利用可能なすべてのプロセッサコアとすべてのRAMにアクセスできるわけではありません。



さらに面白くするために、各アルゴリズム実装のいくつかのバージョンを作成しました。 n体システムのある時点では、座標の64ビットの数値表現があり、他の時点では32ビットでした。



Rustでアルゴリズムの「二重」実装を使用したことも注目に値します。まず、Wasmツールを使用せずに、「ネイティブ」で「安全でない」Rust実装が作成されました。その後、wasm-packを使用して、追加の「安全な」Rust実装が作成されました。このアルゴリズムの実装はJSとの統合が容易であり、Wasmのメモリをより適切に管理できることが期待されていました。

テスト

2つの主要な環境で実験を実行しました。これはNode.jsとブラウザ（Chrome）です。



どちらの場合も、ベンチマークはウォームスクリプトを使用して実行されました。つまり、テストを実行する前にガベージコレクションが開始されていませんでした。各テストの実行後にガベージコレクションを実行したところ、結果に大きな影響はなかったようです。



AssemblyScriptで記述されたソースコードに基づいて、以下が生成されました。

• アルゴリズムの基本的なJS実装。
• Wasmモジュール。
• Asm.jsモジュール。

asm.jsモジュールがasm.jsと完全に互換性がなかったことに注意するのは興味深いことです。モジュールの先頭に「useasm」ディレクティブを追加しようとしましたが、ブラウザーはこの最適化を受け入れませんでした。後で、使用したbinaryenコンパイラが、コードをasm.jsと完全に互換性のあるものにしようとしていないことを発見しました。代わりに、Wasmのある種の効率的なJSバージョンの形成に焦点を合わせました。



最初にNode.jsでテストを実行しました。





Node.js環境でコードを実行する次



に、ブラウザーで同じコードのパフォーマンスを測定しました。





ブラウザでのコードの実行



asm.jsバージョンのコードの動作が他のオプションよりも遅いことにすぐに気付きました。ただし、これらのグラフでは、さまざまなコードバリアントの結果をアルゴリズムの基本的なJS実装と明確に比較することはできません。したがって、すべてをよりよく理解するために、さらにいくつかの図を作成しました。





アルゴリズムの他の実装とJS実装の違い（64ビットのポイント座標を持つベンチマークバージョン）





アルゴリズムの他の実装とJS実装（32ビットのポイント座標を



持つベンチマークバージョン）の違い64ビットと32ビットのポイント座標を持つベンチマークバージョンは著しく異なります。これにより、JavaScriptでは数値は両方になり得ると考えるようになるかもしれません。事実、アルゴリズムの実装では、比較ベースとして使用されるJSの数値は常に64ビットですが、他の言語からWasmにコードを変換するコンパイラは、さまざまな方法でそのような数値を処理します。



特に、これはasm.jsバージョンのテストに大きな影響を与えます。ポイントの座標が32ビットのバージョンは、基本的なJS実装と64ビットの数値を使用するasm.jsバージョンの両方よりもパフォーマンスが大幅に劣ります。



前の図では、他のコードバリアントのパフォーマンスがJSバリアントとどのように比較されるかを理解するのは困難です。これは、AssemblyScriptのメトリックが他のメトリックとあまりにも異なるためです。これを理解するために、asm.jsの結果を削除して別の図を作成しました。





JS実装からのアルゴリズムの他の実装間の違い（asm.jsなしの64ビットのポイント座標を持つベンチマークバージョン）





アルゴリズムの他の実装とJS実装の違い（asm.jsを使用しない32ビットのポイント座標を持つベンチマークバージョン）



数値の表現の違いが、他のバージョンのテストに影響を与えているようです。しかし、彼らはさまざまな方法で影響を与えました。たとえば、32ビットの数値（フロート）を使用したCバリアントは、64ビットの数値（ダブル）を使用したCバリアントよりも遅くなりました。32ビット番号（f32）を使用したテストの両方のRustバージョンは、64ビット番号（f64）を使用したバージョンよりも高速になりました。

アルゴリズムの実装が不十分ですか？

上記のデータの分析は、次の考えを示唆している可能性があります。テストされたすべてのWasmアセンブリのパフォーマンスはJavaScript実装に非常に近いため、Wasm実装がアルゴリズムのネイティブ実装のパフォーマンス機能のみを反映している可能性はありますか？





アルゴリズムのネイティブ実装とJavaScript実装の比較アルゴリズム実装の



ネイティブバージョンは、JavaScript実装よりも常に高速です。



また、Wasmアセンブリは、そのようなアセンブリの作成に使用されるコードのネイティブバージョンよりも遅いことに気付きました。パフォーマンスの違いは20〜50％です。これは、1000回の反復を伴うベンチマークの短縮バージョンで見つかりました。





C実装と対応するWasmアセンブリ





Rustの実装と対応するWasmビルド





wasm-packを使用して作成されたRust実装、および対応するWasmアセンブリ



ネイティブコードの実行時間を測定するときに、プログラムのロードに必要な時間も考慮され、Wasmバリアントの場合、この時間は考慮されませんでした。

結果

基本的なJS実装と比較して、アルゴリズムの2つのRust実装のパフォーマンスの向上は平均して20％でした。これはおそらくRustイメージには適していますが、取得にかかった労力に比べるとパフォーマンスの向上は少なすぎます。



これらのテストからどのような結論を導き出すことができますか？そして、ここにいくつかあります。JSコードを慎重に作成することで、かなり高いパフォーマンスを得ることができ、他のプログラミング言語に切り替える必要がありません。



新しいプログラミング言語を学ぶことは常に良いことです。しかし、新しい言語を学ぶのには十分な理由があるに違いありません。高レベルの設計アーキテクチャは、コンパイラやマイクロ最適化よりもパフォーマンスにとって重要であるため、パフォーマンスが「間違った」理由であることがよくあります。



実験として、JavaScriptをTypeScriptに変更して、フォースグラフ視覚化アルゴリズムの実装を記述しました。その結果、コードベースの品質は向上しましたが、パフォーマンスは向上しませんでした。具体的にパフォーマンスを測定したところ、移行後、わずかに5％増加したことがわかりました。おそらくその理由はコードのリファクタリングです。



JavaScriptの開発とパフォーマンスの問題に興味がある場合は、この講演をご覧になることをお勧めします。これは、私たちが得たものと同様の結果に聞こえました。



Webプロジェクトの「重い」部分の開発にどのようにアプローチしますか？