abcdefGets

ゲッツ!

WebWorker & SharedArrayBuffer & Atomics (2)

二回目です。
前回の記事はWebWorkerとSharedArrayBufferとAtomics(1)です。

Memory Model

ES2017のドラフトからMemoryModelという項目が追加された。
これはSharedArrayBufferのDataBlockに適用されるモデルで、プログラムがとりうるメモリの順序を示したものである。

ES2017ではSequential Consistency(SeqCst)かUnorderedが定義される。

Unordered

Unorderedとはメモリの順序に対して、各種スレッドが何の制約も持たいない状態である。

// main.js
sharedArrayBuffer[0] = 0;
sharedArrayBuffer[1] = 0;

// thread1.js

sharedArrayBuffer[0] = 1;
sharedArrayBuffer[1] = 1;

// thread2.js

const v1 = sharedArrayBuffer[0];
const v2 = sharedArrayBuffer[1];

console.log(v1, v2); // 1, 0

// thread3.js

const v1 = sharedArrayBuffer[0];
const v2 = sharedArrayBuffer[1];

console.log(v1, v2); // 0, 1

このように各スレッドによって値の見え方と順序は異なる。

Sequential Consistency(SeqCst)

Sequential Consistencyはアクセスの原子性に加えて、各スレッドから見たメモリアクセスも決まった順序が保証される制約である。

// main.js
sharedArrayBuffer[0] = 0;
sharedArrayBuffer[1] = 0;

// thread1.js

Atomics.store(sharedArrayBuffer, 0, 1);
Atomics.store(sharedArrayBuffer, 1, 1);

// thread2.js

const v1 = Atomics.load(sharedArrayBuffer, 0);
const v2 = Atomics.load(sharedArrayBuffer, 1);

console.log(v1, v2); // 1, 0 or 0, 1

// thread3.js

const v1 = Atomics.load(sharedArrayBuffer[0]);
const v2 = Atomics.load(sharedArrayBuffer[1]);

console.log(v1, v2); // 1, 0 or 0, 1

Sequential Consistencyが保証されている場合、thread2.jsとthread3.jsで値の見え方に差が出ることはありえない。
何故ならば、Sequential Consistencyは全てのスレッドに対して順序通りの実行結果が観測される事を保証しているからである。

RacesとDataRaces

ES2017にはRacesとData Racesという状態が記述されている。

happens-before

DataRacesの前にhappens-before状態を理解せねばならない。
happens-beforeとは以下の制約を満たす状態である。

  • EventsSet(execution)に含まれるような全てのE,Dに対して
  • E agent-order before Dならば
  • あるいは E synchronizes-with Dならば、
  • あるいは EとDがSharedDataBlockEventSet(execution)に含まれ、E.[[Order]]がInitで、EとDの領域が重なっており
    • D.[[Order]]がInitではない
    • E happens-before Dである
  • あるいは E happens-before Fを満たすようなFがあり、F happens-before Dが満たされるとき、E happens-before Dである。

これだけの説明だと非常に理解しづらいが、単純に E happens-before DとはイベントEがイベントDの前に発生する関係性である。

var x = 0;
var y = x;

ただし、一見このプログラムではx happens-before yが成り立ちそうに見えるが、コンパイラによる最適化、CPUによる実行順序の入れ替えにより、
x happens-before yを確実に成り立たせることはできない。
特にjavascriptには他の言語にある、volatile修飾子のような仕組みが無いため、よりコントロール不可能である。

Races

Racesとはプログラムが以下の状態であることである。

  • E, D2つのイベントがあったとき
  • E happens-before D、D happens-before Eを満たせず
  • EとDがメモリへの書き込みを伴うイベントで
  • EとDのメモリアドレスが重なり合うとき あるいは E reads-from D か D reads-from Eを満たすとき

これは以下のような状態である。

// thread1
sharedArrayBuffer[0] = 1; // E

// thread2
console.log(sharedArrayBuffer[0]); // D

ここではE・DともにE happens-before Dを完全に満たしていない為、Racesである。

// thread1
Atomics.store(sharedArrayBuffer, 0, 1); // E

// thread2
console.log(Atomics.load(sharedArrayBuffer, 0)); // D

この場合はAtomicsを用いてE happens-before Dを満たしているのでOK

Data Races

Data Raceは以下の状態である。

  • Races状態のE、Dが
  • [[Order]] SeqCstを持っていないか、EとDのアドレスが重なっているとき

このRaces、Data Races状態になければ Data Race Free Programe SC-DRFと呼ばれる状態である。

全体的に、Specificationからのセマンティックな処理についての話になってしまったので、少々理解しづらいが、

基本的には

  • EcmascriptにはSeqCstかUnorderedの2つの実行順があり、
  • 全ての変数アクセス・書き込み順がSeqCstであれば、DataRaceFreeである。
  • つまりSharedArrayBufferには常にAtomicsでアクセスしましょう

ってことを覚えておけばいいんじゃなかろうか。

おまけ(V8実装)

現在のV8のAtomicsの実装はruntime-atomics.ccにある。
なかの実装を見るとわかるけど、実際の処理はGCC__atomic_xxx系かVSのInterlockedXXXで簡易に実装してある。
また、isLockFreeの実装は以下のようになっていて、

inline bool AtomicIsLockFree(uint32_t size) {
  return size == 1 || size == 2 || size == 4;
}

32ビットまでの配列に対応しているようだ。