15 / 24 · 実習

実習：1024のストールパターンを検査する

10サイクルのすべてのreadyパターンで、保持、置き換え、空にする動作を試します。

ストール下で値と順序を保つ

elastic-model.mjsを手動作成し、次のコードを保存してnode elastic-model.mjsを実行します。供給側は順序付きの4項目を提示し、受け入れられたときだけ進みます。パターンのビット0はエッジ0、ビット1はエッジ1、以降も同様に制御します。10ビットの全1024 readyパターンを試した後、受け取り側をreadyに保って未完了の項目を排出します。

置き換えを決める前に、更新前のスロットから引き渡します。空のスロットは受け取り側がストールしていても1項目受け入れます。満杯でストールしたスロットでは供給側を進められません。毎エッジnextを増やすと未受け入れの項目を捨て、バッファが正しくてもテスト供給側が誤りになります。

import assert from 'node:assert/strict';
const values = [0, 9, 255, 12];
let deliveries = 0;
for (let pattern = 0; pattern < 1024; pattern++) {
  let slot = null, next = 0;
  const seen = [];
  for (let edge = 0; edge < 20; edge++) {
    const ready = edge >= 10 || ((pattern >>> edge) & 1) === 1;
    const old = slot;
    const inReady = old === null || ready;
    if (old !== null && ready) seen.push(old);
    if (inReady) {
      slot = next < values.length ? { tag: next, y: values[next] } : null;
      if (slot !== null) next++;
    } else {
      assert.deepEqual(slot, old);
    }
    assert.equal(next - seen.length, Number(slot !== null));
  }
  assert.deepEqual(seen, values.map((y, tag) => ({ tag, y })));
  assert.equal(slot, null);
  deliveries += seen.length;
}
console.log(`ELASTIC PASS: 1024 patterns, ${deliveries} deliveries`);

パターン0では、受け取り側は最初の10エッジでストールします。tag0,y0はエッジ0で空のスロットに入り、エッジ9まで残ります。エッジ10で引き渡してtag1,y9を格納し、タグ1,2,3はエッジ11,12,13で転送されます。有効なゼロをnullと取り違えてはいけません。成功時は1024パターン、4096件の引き渡しを報告します。

各エッジ後、受け入れ数と引き渡し数の差は現在の占有数に等しくなります。この局所的な収支は最終出力比較より早く失敗箇所を絞れます。保持検査はペイロードの保存を対象としますが、実装との比較には、このモデルの変数が変わらないことだけでなく実際の出力を観測する必要があります。10サイクルの全パターンを試すのは範囲を限定したテストで、あらゆるストール長の証明ではありません。最終的な完了には受け取り側がいずれreadyになる仮定も必要です。永久のバックプレッシャーでは保持が必要であり、引き渡しは保証できません。

自分で考えてみましょう

パターン0では、エッジ0から9の間に供給側nextはどこまで進みますか。エッジ10後の占有数とnext-seen.lengthは何ですか。

解説を見る

エッジ0の項目だけを受け入れるためnext=1です。エッジ10でtag0を転送しtag1が入るので、next=2、seen.length=1となり、その差とスロット占有数はどちらも1です。

Lesson files

elastic-model.mjs ↓