プログラミング

ブールスキャンの対称性

Symmetries in Boolean Scan (ap29600.github.io)

8 pointsby g0xA52A2A2026年10月15日0 コメント

要約

この記事は、APL（配列プログラミング言語）におけるスキャン操作、特にブール演算に焦点を当てています。APLは多くの組み込み関数（プリミティブ）を持ち、それらの最適化に依存していますが、ブール演算のプリミティブが多数存在することは実装の複雑さやユーザーの混乱を招く可能性があります。著者は、スキャンの合成規則を分析し、特に否定のような単項関数を用いた前処理や後処理がスキャン操作に与える影響を調べることで、プリミティブの数を減らし、実装の労力を削減する可能性を探求しています。これにより、ブールプリミティブ間の対称性や関係性を明らかにし、パフォーマンスを維持しながらコードの簡潔化を目指します。

全文翻訳

ブールスキャンにおける対称性

APLのような配列言語は、多くの美しい記号（「プリミティブ」と呼ばれる）を組み込み関数として使用することで知られています。これらはユーザー定義関数とは異なり、インタプリタがそれらを認識し、特別な組み合わせを検出するなど高度な最適化を行うことができるため、区別されます。

APLプログラマーはこれらの最適化に依存するようになり、例えば +/（合計）のような一部の組み合わせのベクトル化が挙げられます。もし典型的なAPLインタプリタに、+/ と機能的に同等な関数 {⍺+⍵}/ を与えた場合、それは単に抽象化を実行するために要素あたり2つの関数呼び出し（dfn用とプリミティブ + 用）を行うだけでなく、それ自体が遅くなるため、はるかに遅く実行されます。

まともなAPLであれば、この特定組み合わせ専用のネイティブコードで実装されたタイトなループを備えており、APLが時にネイティブコードにコンパイルされる言語と競合できる理由がここにあります。

スキャンとフォールド

fold は、アキュムレータとコレクションの要素を入力として受け取り、新しいアキュムレータを返す二項関数を繰り返し呼び出して順序付けられたコレクションを反復処理する概念を一般化した高階関数です。
scan も同様ですが、アキュムレータの最終値を返す代わりに、反復中にアキュムレータが取ったすべての中間値のコレクションを返します。

どちらの場合も初期値が提供される場合とされない場合があり、後者の場合、最初の要素は初期値として扱われ、変更されずに返され、残りのコレクションのスキャンと連結されます。

APLではこれらの関数を演算子 / とで表します。

       10 = +/ 1 2 3 4
 1 3 6 10 = +
 1 2 3 4

この記事の残りの部分では、より扱いやすいフォールドとスキャンのセマンティクスを持つ、変更されたAPLのファンタジー方言を使用し、いくつかの関数方程式を記述します。APLを知らない場合は心配しないでください。Lisp、Haskell、Ocamlなどの伝統的な関数型言語のスキャンだと考えてください。主要な方程式はHaskellにも翻訳されます。

アルゴリズムの秘術

APLerがこれらに依存していると言うとき、私は本当にそれを意味します！スキャン、フォールド、逆スキャンは、min、max、plus、times演算子と共に、numpyに慣れている平均的なPythonプログラマーにとっては、非常に有用であるため、見慣れた、あるいは日常的な操作ですらあります。

減算での（右からの）フォールドは交互の合計になり、これは面白いです。

APLプログラムはそれを超えます。より小さい関数でのスキャンは何をしますか？等しくないでのスキャンは？モジュロでのフォールドは？

ここでの問題は、APLがアルゴリズムにおけるデータ依存性を処理するためのエスケープハッチを必要とすることです。APLでループを記述するのは構文的に扱いにくく、配列を明示的に反復処理するのは、プリミティブ関数が実行される速度と比較して気が遠くなるほど遅いためです。スキャンとフォールドは、情報を蓄積し、配列内で「移動」させるための非常に一般的な方法であり、それを行うためのAPLで最も慣用的な方法です。

ケーススタディ：引用符の解決

引用符文字を含むテキスト文字列があり、文字列のどの位置が引用符のペアの内側にあるか、または内側にないかを判断したいとします。Cで書くなら、次のようになります。

bool in_quotes = false;
for (size_t i = 0; i < n; ++i) {
    if (string[i] == '"') {
        in_quotes = !in_quotes;
    }
}

一方、APLでは、結果が前の例の in_quotes の値を含む配列になる、次のようになります。文字列の各文字と " 文字との比較から得られるブール値に対してスキャンを実行するという考え方です。

in_quotes ← ≠\string='"'

これがなぜ機能するのかを見るために、Cバージョンを算術にエンコードして分岐なしにしましょう。類似性をより明確にするために、値 0 と 1 では同じことを行うため、通常 ^ がより自然な場所で != と書くことができます。

bool in_quotes = false;
for (size_t i = 0; i < n; ++i) {
    in_quotes = in_quotes != (string[i] == '"');
}

ブールスキャン：実際にいくつ必要か？

APLには多くのプリミティブがあります。私が知る限り、すべての非自明な二項ブール関数を組み込んでいる唯一の言語です。それらを真理値表と共に示します。

	一般名	00	01	10	11
`∧`	and	0	0	0	1
`>`	より大きい	0	0	1	0
`<`	より小さい	0	1	0	0
`≠`	等しくない (xor)	0	1	1	0
`∨`	or	0	1	1	1
`⍱`	nor	1	0	0	0
`=`	等しい	1	0	0	1
`≥`	以上	1	0	1	1
`≤`	以下 (含意)	1	1	0	1
`⍲`	nand	1	1	1	0

これは実装者の側での問題です。多くのプリミティブは多くの組み合わせを意味し、それぞれについてまともなコードを書くことは、労働力と実行可能サイズ（したがって命令キャッシュ）の両方でコストがかかります。さらに、ブールスキャンに対してまともなコードが何であるかを判断することは、私が示したスニペットよりもはるかに高い基準です。APLはパックされたビットベクトルをブール配列の表現に使用するため、これらの操作はCPUサイクルあたり数十要素を消費する可能性がありますが、簡単なベンチマークによると、単純な実装ではサイクルあたり約0.6要素しか処理できません。

真理値表を見ただけで、これらのうちどれが本当に有用かを判断するのは簡単ではなく、問題に正確に答える操作がぞんざいに実装されていることをユーザーが知るのは本当に残念です。

パフォーマンスを完全に犠牲にすることなく、実装作業を削減する方法はありますか？

スキャン合成規則

スキャン ⍺ f\ ⍵ の構造は次のとおりです。

［画像: scan base］

g という関数で何らかの前処理を行いたい場合、スキャンの動作を変更するには、次のようなデータフローになります。

［画像: scan pre］

これを調べる動機は、ブール配列を単項スカラー関数で前処理することは、私たちができる最も安価なことの1つだからです。実際、非自明なブール単項スカラー関数はブール否定だけです。この観察を一時的に脇に置いておき、この操作はまだスキャンでしょうか？もしそうなら、この結果を生成するためにスキャンはどの関数オペランドを取るべきでしょうか？

各ステップで ⍵ が g を介して渡されていることが明らかです。したがって、答えは {⍺ f (g ⍵)} であり、単純な方程式に至ります。

⍺ f\ g¨ ⍵ ←→ ⍺ (f∘g)\ ⍵

同等のHaskell

scanl f x (map g ys) = scanl (\x y -> f x (g y)) x ys

g が任意の関数であり、∘ はAPLの合成演算子「ジョット」で、次を満たす場合

⍺ f∘g ⍵ ←→ ⍺ f (g ⍵)

後処理 g がどのような影響を与えるかを理解するのは少しトリッキーです。

［画像: scan post］

見た目は前と同じですが、各 f の呼び出しへの入力が、出力配列に送られる値と同じではないことに注意してください。したがって、これはスキャンではありません！これを修正するために、g が左逆関数 g-1 を持ち、各呼び出しペアの間に挿入すると仮定します。

［画像: scan conj］

これは関数 {g ((g⍣¯1) ⍺) f ⍵} を使用したスキャン図ですが、初期値 x は g で前処理されています。これにより、次の方程式が得られます。

g¨ ⍺ f\ ⍵ ←→ (g ⍺) (g⍤(g⍣¯1⍛f))\ ⍵

同等のHaskell

map g (scanl f x ys) = scanl (\x y -> g (f (ig x) y)) (g x) ys

ここでもいくつかの合成演算子が使用されています。

(g⍣¯1) g ⍵ ←→ ⍵ ⍝ APLは時々自分で逆関数を見つけることができます！
⍺ (g⍤f) ⍵ ←→ g (⍺ f ⍵)
⍺ (g⍛f) ⍵ ←→ (g ⍺) f ⍵

そして最後に、これら2つの関係を組み合わせて3番目の関係を見つけることができます。

g ⍺ f\ g ⍵ ←→ (g ⍺) g⍤(g⍣¯1⍛f∘g)\ ⍵

同等のHaskell

map g (scanl f x (map g ys)) = scanl (\x y -> g (f (ig x) (g y))) (g x) ys

真理値表のシャッフル

特に、g が否定関数 ~ である場合に、これらの3つの関係のいずれかによって関連付けられているプリミティブのペアを見つけることに興味があります。真理値表から始め、上記で説明した変換の下でそれらがどのように変化するかを分析します。

すべての真理値表を配列 a として一度に表現します。形状は 10 2 2 です。

    a
┌┌→──┐
↓↓0 0│
││0 1│
││   │
││0 0│
││1 0│
││   │
││0 1│
││0 0│
││   │
││0 1│
││1 0│
││   │
││0 1│
││1 1│
││   │
││1 0│
││0 0│
││   │
││1 0│
││0 1│
││   │
││1 0│
││1 1│
││   │
││1 1│
││0 1│
││   │
││1 1│
││1 0│
└└~──┘

右引数に ~ を合成することは、⌽ 関数を使用して最後の軸を反転することと同じです。

    pre ← ⌽[2] a

出力を否定することは、各エントリを否定するだけです。これを行う場合、左引数も否定する必要があります。これは、各真理値表の最初の軸（ここでは中央の軸）を反転することによって行います。

    post ← ~ ⌽[1] a

そしてもちろん、両方の変換を同時に行うことができます。

    both ← ~ ⌽[1] ⌽[2] a

これで、元の配列で得られた真理値表を検索することによって、誰が誰と関連しているかを見つけることができます。

    index ← ↑(⊂a)⍳¨a pre post both

┌→──────────────────┐
↓0 1 2 3 4 5 6 7 8 9│
│1 0 5 6 7 2 3 4 9 8│
│7 4 9 3 1 8 6 0 5 2│
│4 7 8 6 0 9 3 1 2 5│
└~──────────────────┘

これで、真理値表が参照していたシンボルのリストをインデックスで参照できます。

    '∧><∨⍱=≥≤⍲'[index]

┌→─────────┐
↓∧><≠∨⍱=≥≤⍲│
│>∧⍱=≥<≠∨⍲≤│
│≥∨⍲≠>≤=∧⍱<│
│∨≥≤=∧⍲≠><⍱│
└──────────┘

これをどう解釈するか？一番上の行は元のシンボルです。2番目の行は、上記の最初のスキャン方程式、つまり ⍺ p\ ~⍵ ←→ ⍺ q\ ⍵ によって、一番上の行に関連付けられているシンボルです。同様に、3番目と4番目の行は、~ (~⍺) p\ ⍵ ←→ ⍺ q\ ⍵ および ~ (~⍺) p\ ~⍵ ←→ ⍺ q\ ⍵ を介して最初の行に関連付けられています。

結論

∧、<、≠ のセットが少なくとも1回はすべての列をカバーしていることがわかります。したがって、これらのそれぞれについて高速な実装を提供すれば、これらの対称性を適用するだけで、他の実装からまともな実装を導き出すことができます。これにより、パフォーマンスを完全に犠牲にすることなく、実装時間と実行可能サイズが削減されます。

ちなみに、これらはまったく新しいものではありません。トリック ⍺ ≠\ ⍵ ←→ ⍺ = ~⍵ は、Kには組み込みの等しくない演算子がないため、Kプログラマーの間ではよく知られています。同様に、これらのショートカットの多くは、BQNのあまり一般的でない組み合わせのCBQNインタプリタで使用されています。

付録A. ブレインストーミングと観察

元々、APLファームのDiscordサーバーでこれを議論しましたが、そこでユーザーの何人かが興味深いコメントをしました。

有限状態機械としての真理値表

K言語では、x f\ y の形式は、f の非負整数のペアに対する値を含む行列 a を持つ x a\ y の形式と同等です。この形式は、y のシーケンス上で a で定義された遷移を持つ状態機械を進めます。

(  x a\ ~y) =   x  (  |'a)\ y
(~ x a\  y) = (~x) (~|  a)\ y
(~ x a\ ~y) = (~x) (~||'a)\ y

同等のHaskell

runFsm a x ys = scan (\x y -> (a !! x) !! y) x ys

            runFsm a x $ map (1 -) ys = runFsm      x  (                  map reverse           a) ys
map (1 -) $ runFsm a x             ys = runFsm (1 - x) (map (map (1 -))               $ reverse a) ys
map (1 -) $ runFsm a x $ map (1 -) ys = runFsm (1 - x) (map (map (1 -)) $ map reverse $ reverse a) ys

与えられた変換の下での不変量

与えられた変換は、テーブルの行または列を置換したり、エントリを否定したりします。これは、テーブル内の1の数が2のままであるか、1と3の間で切り替わることを意味します。さらに、変換は可換であり、自己逆であるため、私たちの関係は同値関係です。= と ≠ はそれ自身のクラスに属し、1つの変換が両方の操作を固定し、他の変換は少なくともさらに2つを埋めると推測できます。

これらのうち、~⌽[0]a という変換を適用して3つの0を作成し、次に ⌽[1]a を適用して、単一の1エントリが2番目の列に配置されるようにすることができます。区別される唯一の2つの可能性は、1の値が a[1;1]（∧ を与える）にあるか、a[0;1]（< を与える）にあるかです。

付録B. ブールスキャンの効率的な実装

Xor

マシンワードでのxorスキャンは、Bit Twiddling Hacks で説明されているようなプレフィックスダブリング技術を使用して、数命令で効率的に実装できます。

uint64_t xorscan_word (uint64_t word) {
    word ^= word << 1;
    word ^= word << 2;
    word ^= word << 4;
    word ^= word << 8;
    word ^= word << 16;
    word ^= word << 32;
    return word;
}

前のワードからのキャリーを処理するだけで済みます。典型的な方法は、それを word の最初のビットとxorすることですが、これは実際には最適ではありません。carry は各イテレーションの開始時に必要とされ、終了時にのみ更新されるため、すべてのイテレーションが非常に長い依存チェーンに結びついていることに注意してください。

void xorscan_bad (bool initial, uint64_t *words, size_t n) {
    uint64_t carry = (uint64_t)initial;
    for (size_t i = 0; i < n; ++i) {
        uint64_t word = xorscan_word(words[i] ^ carry);
        carry = word >> 63;
        words[i] = word;
    }
}

これは次のコアループにコンパイルされ、約3〜4ビット/サイクルで実行されます。（私が提供するすべてのタイミングは、キャッシュがホットなメモリを対象としており、それ以外の場合はメモリレイテンシが実行時間を支配します）。

アセンブリ出力

.loop:
    xor    (%rdx),%rdi
    add    $0x8,%rdx
    lea    (%rdi,%rdi,1),%rax
    xor    %rdi,%rax
    lea    0x0(,%rax,4),%rcx
    xor    %rcx,%rax
    mov    %rax,%rcx
    shl    $0x4,%rcx
    xor    %rcx,%rax
    mov    %rax,%rcx
    shl    $0x8,%rcx
    xor    %rcx,%rax
    mov    %rax,%rcx
    shl    $0x10,%rcx
    xor    %rcx,%rax
    mov    %rax,%rcx
    shl    $0x20,%rcx
    xor    %rcx,%rax
    mov    %rax,%rdi
    mov    %rax,-0x8(%rdx)
    shr    $0x3f,%rdi
    cmp    %rdx,%rsi
    jne    .loop

スーパースカラー実行を備えたCPUでは、前の結果の使用を可能な限り遅延させることができれば便利です。幸いなことに、xorは結合法則を満たすため、キャリービットを最終結果のすべての位置にブロードキャストするだけで済みます。これにより、CPUは前のイテレーションの結果が準備できる前に、次のイテレーションの xorscan_word の実行を開始できます。

void xorscan_good (bool initial, uint64_t *words, size_t n) {
    uint64_t carry = - (uint64_t)initial;
    for (size_t i = 0; i < n; ++i) {
        uint64_t word = carry ^ xorscan_word(words[i]);
        carry = - (word >> 63);
        words[i] = word;
    }
}

これははるかに高速で、サイクルあたり最大10.5ビットを処理します。

アセンブリ出力

.loop:
    mov    (%rcx),%rdx
    add    $0x8,%rcx
    lea    (%rdx,%rdx,1),%rax
    xor    %rdx,%rax
    lea    0x0(,%rax,4),%rdx
    xor    %rdx,%rax
    mov    %rax,%rdx
    shl    $0x4,%rdx
    xor    %rdx,%rax
    mov    %rax,%rdx
    shl    $0x8,%rdx
    xor    %rdx,%rax
    mov    %rax,%rdx
    shl    $0x10,%rdx
    xor    %rdx,%rax
    mov    %rax,%rdx
    shl    $0x20,%rdx
    xor    %rdx,%rax
    xor    %rsi,%rax
    mov    %rax,%rsi
    mov    %rax,-0x8(%rcx)
    sar    $0x3f,%rsi
    cmp    %rcx,%rdi
    jne    .loop

CPUがキャリーレス乗算命令（多くの最新CPUがサポートしています！）をサポートしている場合、xorscan_word はワード 0xffffffffffffffff（すべて1）とのキャリーレス乗算として実装できます。

And

上記のすべて（キャリーレス乗算を除く）は、^ を & に置き換えることでそのまま適用できます。ただし、より高速な方法があります。

まず、単一ワードのandスキャンは、xorよりもはるかに簡単に実装できます。

uint64_t andscan_word (uint64_t word) {
    return word & ~(word + 1);
}

これは、1を加算すると最初の1の連続が0の連続に変わり、次に否定すると最初の0の連続が1の連続に戻り、他のすべてを否定するため機能します。最後のビットごとのandは、2つの一致する1の連続、一致する0ビットのペア、およびそれ以外のすべての不一致ビットを確認します。

例を挙げます。ビットは最下位から最上位の順序です。


`word`	`11100011010101011`
`word+1`	`00010011010101011`
`~(word + 1)`	`11101100101010100`
`word & ~(word + 1)`	`11100000000000000`

これをワードの配列に拡張するために、それより前のすべてがすでに1であることがわかっており、それ以降はすべて無条件に0に設定できるため、実際にスキャンが必要なワードは最大で1つであることを観察します。

完全な実装は次のようになります。

void andscan (bool initial, uint64_t *words, size_t n) {
    size_t i = 0;
    if (initial) {
        for (; i < n; ++i) {
            uint64_t word = words[i];
            if (~word) {
                words[i] = andscan_word(word);
                ++i;
                break;
            }
        }
    }
    for (; i < n; ++i) {
        words[i] = 0;
    }
}

これにより2つの別々のループが生成されます。最初の最も集中的なループはサイクルあたり62ビットを処理でき、もう1つはmemsetへの呼び出しにコンパイルされます。

アセンブリ出力

.loop:
    add    $0x8,%rcx
    cmp    %rax,%rdx
    je     .found
    mov    (%rcx),%rsi
    inc    %rax
    cmp    $0xffffffffffffffff,%rsi
    je     .loop

より小さい

これは最も複雑なケースであり、私が提示するソリューションは simdjson ライブラリからのもので、エスケープされた文字を見つけるために使用しています。実際、< が何をするかの直感は、1の連続するシーケンスで奇数オフセットにあるすべての 1 ビットをオフにすることであり、これは文字列内のどのバックスラッシュがエスケープとして機能し、どれがエスケープされているかを判断するために必要なものです。

uint64_t ltscan_word (uint64_t word) {
    uint64_t guard = word << 1 | 0xaaaaaaaaaaaaaaaa;
    uint64_t parity = guard - word;
    return (parity ^ 0xaaaaaaaaaaaaaaaa) & word;
}

ここでもリトルエンディアンのビット順で例を示します。


`word`	`1110000111100111`
`word << 1`	`0111000011110011`
`guard`	`0111010111110111`
`parity`	`1110010000010000`
`parity ^ odd`	`1011000101000101`
`result`	`1010000101000101`

シフトと奇数ビットの設定は、減算で借用チェーンが開始されるかどうかを制御します。1の連続の開始は、偶数位置にある場合は0に設定され、それ以外の場合は1のままです。連続の最後の要素も借用チェーンを停止するために末尾を越えて移動されます。次に元のビットマスクを減算すると、最初のケースではすべてのビットが設定され、2番目のケースではすべてのビットが設定解除された借用チェーンが作成されます。ここで奇数ビットをすべて反転すると、偶数位置で始まる連続の偶数ビットが設定され、奇数位置で始まる連続の奇数ビットが設定され、これらの連続の外側にいくつかのゴミが残ります。これをビットごとのandでクリーンアップします。

Xorの場合と同様に、これらを連鎖させる単純な方法は、前の結果の最後のビットが設定されている場合に最初のビットをクリアすることですが、Marshallのノートでは、クリティカルパスの長さを短縮するよりスマートな方法についても言及しています。

void ltscan (bool init, uint64_t *words, size_t n) {
    uint64_t carry = (uint64_t)init;
    for (size_t i = 0; i < n; ++i) {
        uint64_t word = ltscan_word(words[i] &~ carry);
        carry = word >> 63;
        words[i] = word;
    }
}

この特定のバージョンは、サイクルあたり8.8ビットを処理できます。

アセンブリ出力

.loop:
    andn   (%rsi),%rdi,%rdi
    add    $0x8,%rsi
    lea    (%rdi,%rdi,1),%rax
    or     %rdx,%rax
    sub    %rdi,%rax
    xor    %rdx,%rax
    and    %rdi,%rax
    mov    %rax,%rdi
    mov    %rax,-0x8(%rsi)
    shr    $0x3f,%rdi
    cmp    %rsi,%rcx
    jne    .loop

1。はい、十分にスマートな（™）コンパイラはユーザー定義コードでもこれを行うことができますが、それは高価であり、APLはインタプリタが非常にシンプルである必要があった時代に存在しました。

2。空でないリストに呼び出された場合

3。「直接関数」、APLでのラムダの名称。⍺ は暗黙的に定義された最初の引数、⍵ は2番目の引数です。

4。すでにAPLを知っている方のために、APLのスキャンは、関数引数が結合法則を満たす場合にのみ、私が書いたものと同等です。なぜなら、伝統的にAPLは非常に風変わりなスキャン演算子を持っているからです。私は、スキャンが左から右に操作され、明示的に与えられた初期値を持つように定義されたAPLの想像上のバリアントを検討します。dzaima/APL、BQN、Kはすべてこのバージョンのスキャンを持っていますが、この記事の残りのコードとは互換性がありません。KAPはほぼ適していますが、スキャンに初期値を与えることをサポートしていないため、方程式に醜いエッジケースが生じます。

5。最近、古いIBMドキュメントで報告されたイディオムを見つけました。これは、リストの最後の要素が1かどうかをチェックするためにモジュロを使用したフォールドを使用していました。私はその操作がインタプリタによって認識されたと仮定しますが、それがイディオムでなかった場合、そのコードをイディオムと呼ぶのは信じられないほど悪い考えだったでしょう。

6。データ全体に線形の依存チェーンがあるため、スカラーループができる絶対的な最大値はサイクルあたり1要素です。

7。DiscoDougによって提案されました。

8。Marshallによって提案されました。