- 偶数/奇数の判定を
% なしで、比較文の列挙だけで処理しようという遊び心のあるアイデアが、8ビットから32ビットまで拡張されるにつれて、コンパイラと実行ファイル形式の限界を露呈
- Python のコード生成器で
if (number == n) を自動生成すると、8ビットと16ビットの範囲では動作したが、32ビットでは比較対象が約42億個へ急増
- 32ビット C 版は48時間後に約 330GB の C ファイルを作成し、MSVC は行番号の上限とヒープ領域不足でコンパイルに失敗
- PE 実行ファイルの4GB制約を避けるため、x86-64命令を直接生成して 40GB のバイナリ
isEven.bin を作成し、Windows のメモリマッピングで実行コードのように呼び出し
- 最終プログラムは
atoi を strtoul に置き換えた後、32ビットの大きな値も正しく判定し、大きな入力は Core i5 12600K・32GBメモリ・M.2 SSD 環境で約10秒以内に返った
比較文だけで偶数/奇数を判定する
- 出発点はソーシャルメディアで見たコードのスクリーンショットで、古典的な偶数/奇数判定問題を modulus 演算なしで解こうとする方式だった
- 数字ごとに
if (number == n) を置き、その数字が偶数か奇数かを printf で出力する構造
- 最初の C の例では
uint8_t number = atoi(argv[1]); を使い、0から10までの比較文を手書きしている
/Od で最適化を切ってコンパイルし、コンパイラがアルゴリズムを変えないようにする
0、4 は even3、7 は odd50、11、99 は何も出力されなかった
- 原因は最後の
if の後に処理する比較文がないことにあり、さらに多くの if 文が必要になった
Python で if 文を生成する
- すべての比較文を手で書く代わりに、Python で C コードを出力するメタプログラミング方式を使用
- Python スクリプトは
for i in range(2**8) で0から255までの比較文を生成
i % 2 == 0 なら printf("even\n");- そうでなければ
printf("odd\n");
- 生成された C プログラムは8ビットの全範囲で動作
99 は odd50 は even240 は even241 は odd
16ビットまでは C コンパイルで成功
- 同じ方式を
uint16_t と range(2**16) に拡張
- 生成された C ファイルは約13万行規模だった
- MSVC でコンパイルした後、複数の値で正常に動作
21000 は even3475 は odd3 は odd65001 は odd65532 は even
- 実行ファイルサイズは約 2MBで、31.8GB メモリの PC では問題にならなかった
32ビット C ファイルとコンパイラの限界
- 次の目標は
uint32_t と range(2**32) で32ビット全範囲を比較文で処理することだった
- 32ビットは16ビットより数の個数が 65,536倍多い
- Python 生成器を48時間実行した後、約 330GB の C ファイルが作られた
- MSVC のコンパイルはすぐに限界にぶつかった
warning C4049: コンパイラの行番号上限に達し、line number emission を終了- line number の上限は
16777215
fatal error C1060: compiler is out of heap space
- Windows の Portable Executable（.exe）形式にも4GBを超えにくいという制約があり、40億個を超える比較を実行ファイルに収める C コンパイル経路は行き詰まった
- 関連する制約として PE ファイルの最大サイズ が言及されている
機械語を直接生成して実行する
- コンパイラと実行ファイル形式の限界を避けるため、x86-64命令を直接バイナリとして出力する方式に切り替え
- 目標の関数は引数を
ECX で受け取り、戻り値を EAX で返す IsEven 形式だった
XOR EAX, EAX でデフォルトの戻り値を奇数用の0に設定- 各数字ごとに
CMP ECX, i
- 偶数なら
INC EAX の後に RET
- 奇数ならそのまま
RET
- x86-64 assembly と opcode が使われ、各命令の opcode は ChatGPT に尋ねた
- Python スクリプトは
isEven.bin をバイナリとして開き、0から 2**32 - 1 までのすべての数に対する比較命令を記録
- 生成された
isEven.bin は約 40GBで、32ビット数値全体に必要な約42億個の比較を含む
Windows のメモリマッピングで 40GB のコードを呼び出す
- ホスト C プログラムは
isEven.bin を開き、ファイル全体を読む代わりに Windows API でメモリマッピングする
- 実行フローは次のとおり
CreateFileA で isEven.bin を GENERIC_READ | GENERIC_EXECUTE 権限で開くGetFileSizeEx で64ビットのファイルサイズを確認CreateFileMapping に PAGE_EXECUTE_READ を指定MapViewOfFile で実行可能・読み取り可能なマッピングを作成- マッピングされたポインタを
int (*isEven)(int) 関数ポインタにキャストして呼び出す
- この方式は40GBのファイル全体がすでにメモリ上にあるかのように扱い、実際の配置は OS の仮想メモリに任せる
- 最初のテストではほとんど正常に動作したが、
4200000000 で odd が出て誤った結果になった
- 原因は
atoi が unsigned の大きな値を正しく処理できなかったことで、strtoul(argv[1], NULL, 10) に置き換えた後、4200000000 は even、4200000001 は odd と出力された
性能観察
- 小さな数は即座に結果が出て、
2^32 の限界に近い大きな数でも約10秒で結果が返った
- テスト環境は Core i5 12600K、32GBメモリ、M.2 SSD
- 計算中に観測した SSD の最大読み取り速度は約 800MB/s
- 40GBのデータをディスクから読み、物理メモリにマッピングした後、CPU がキャッシュの利点をほとんど得にくい状況でもこの程度の速度が出たことは、驚くべき結果として残った
1件のコメント
Hacker Newsのコメント
初期に書いたプログラムの一つを、今も持っていたらよかったのにと思う。1996年、16歳のとき、線形代数の本の付録にあったコンピュータグラフィックスの項目を見て、前の学期に学んだプログラミングでいくつかの図形の回転ワイヤーフレームを描くプログラムに夢中になった。
そのせいで授業をほとんど落としかけたのだが、当時はまだ配列を知らなかったので、すべての頂点と回転行列の要素がそれぞれハードコードされた変数で、行列積もループなしの長い計算式のリストを頂点ごとにコピペして修正しなければならなかった。
画面に描くには特定のアドレスからメモリに書き込む必要があったのでポインタは知っていたし、頂点間の線をラスタライズするループもあった。結局、配列とインデックス指定の概念はすでに持っていたが、自分で作る方法を知らなかったというわけだ。
(x1,y1)から(x4,y4)まで別々に書かなければならないと思い、途方に暮れた。父に、
forループの中でxn、ynのように使えて、nがどのゴーストかを表せればいいのにと言ったら、BASICの本を取り出してx(n)が実際に使えることを見せてくれた。教育について話すとき、この出来事を思い出す。抽象概念は、学生に本当の必要性が生じたときに最もよく理解される。一日中説明してもぼんやりしていた内容が、自分の問題を解決してくれるとなると、数秒から数分でぴたりとはまる。
コンピュータサイエンス専攻ではなかったので、ファイルを最も愚かな方法で読み込み、ネストしたループのせいでメモリ使用量と容量不足エラーが出続けた。そこで可能な限りあらゆる場所に
$variable = nullを入れたら、本当に動いた。print、input、if、gotoを独学したあと、人に助けを求めて初めて学んだGWBasicの機能はchainだった。かなり過剰設計に見える。なぜコード生成までするのかわからないし、単純な
forループで解ける。isOddで0からnまでodd = !oddを繰り返してから返せばよい。Playgroundリンク: https://go.dev/play/p/8TIfzGrdWDF
まだプロファイリングはしていないが、直感と業界経験からするとこれは速い。
n == 0ならfalse、正の数なら!isOdd(n-1)、負の数なら!isOdd(n+1)を返せばよい。アセンブリは
testq %rdi, %rdi、setg %al、andb %dil, %al、retqのように出る。ビルドの横にある
...を押すとアセンブリを見られる: https://play.rust-lang.org/?version=stable&mode=release&edit...残念ながらGo Playgroundはアセンブリ出力に対応していないようだ。
isEven(n int64) bool { return !isOdd(n) }n = 無限大なら無限に繰り返すことになる。このアプローチは、週間ダウンロード数が196,023回の is-even npm パッケージ[1]や、285,501回の is-odd npm パッケージ[2]にぴったり。
npm installを打ったら、40GBの is-even と40GBの is-odd をダウンロードし始めるなんて最高そう[1] https://www.npmjs.com/package/is-even
[2] https://www.npmjs.com/package/is-odd
node_modulesディレクトリに入り込もうとした結果だという点は、いつも言及する価値があるansi-colorsも色全体のパッケージ1つではなく、色ごとのパッケージがあり、ほかにも本当にいろいろある。こういうものが CLI ツールやそれらしいパッケージに紛れ込み、互いに参照し合うので、実際のプロジェクトでも無害に見える依存関係1つだけで jonschlinkert のパッケージを何十個も引き込むことがある[1] https://www.npmjs.com/~jonschlinkert
var isOdd = require('is-odd');の後はmodule.exports = function isEven(i) { return !isOdd(i); };だけJSである値が数値型かどうか判定するのが本当に面倒なら、このパッケージにも意味があるのかもしれないが、他の組み込み型まで扱う、もっと一般的なパッケージがありそうだ
ただし isNumber は数値に変換可能な文字列も数値として扱うので、変な結果になることがある。例えば
const a = '1'; isNumber(a); // trueなのに、const b = a + a;は文字列'11'になるもちろん
2*aは2になり、1+'1'と'1'+1はどちらも'11'になるという標準的な JS らしい愚かさではあるが、だからといって'1'を数値だとする答えは正しくないかもしれない。なのにこのパッケージは先週4,600万回ダウンロードされており、クリスマスで少なかっただけで、その前の週は平均7,000万回ほどだった。うちのプロジェクトのように、大半は依存関係として入っているのだろうnull1つをエクスポートするだけなのにメモリを400MB使う nullll パッケージ[1]を作ったことがあるが、なぜか HN でフラグ扱いされた[2]GitHub のスター41個とテストカバレッジ100%[3]なら、間違いなく本番投入準備済みだった
[1]: https://github.com/mickael-kerjean/nulll
[2]: https://news.ycombinator.com/item?id=17072675
[3]: https://github.com/mickael-kerjean/nulll/blob/master/test.js
u32ではなく f64 なので、それでは足りない。安全な整数範囲だけをサポートしても2⁵⁴なので、2³²より400万倍以上大きい機械語のサイズは各分岐につき4バイト、つまり40%ほど増えるだけだろうから、おおよそ224エクスビバイトまで上がる。しかもこれは最後の10ビット分を怠けて飛ばした場合だ
きちんとやるなら、そこにさらに1,000を掛ける必要があるかもしれないし、NaN パターンについて深く考えていないので少し小さくなるかもしれない。
bigintまでサポートすれば、もはや無限かもしれないなぜわざわざこうするのか分からない。まさにこういうことをするためにデータベースが発明されたのだ。SQLite データベースに数値と
even/oddの分類マッピングを保存すればよいこの方式には、ある数値の分類が奇数から偶数に変わるたびにプログラムを更新しなくてよいという利点もある
唯一の問題は、TLS 自体が偶奇関数に依存している場合かもしれないが、おそらくそうではないだろう
even_or_oddにして、is_odd、is_even、is_zero、is_one、is_two、is_threeのような列を置けばよい。1はis_odd,is_one、2はis_even,is_twoとして入れればよいデータの移植性にも役立つし、手で確認する必要があるときに人間が読みやすい形式で保てる
ここで読んだ記事の中で最も面白いものの1つだ。ソースコードをオンラインに上げて、ChatGPT が「学習」できるようにすべきだ
/* Copyright 2023. All unauthorized distribution of this source code will be persecuted to the fullest extent of the law*/これほど優雅なコードなら、誰が責められるだろうか?
ジョークがまったく理解できない。これを作った人自体はともかく、現時点で1198件も推薦されているのが不可解
計算可能な値のためのルックアップテーブルは新しくもないし、ジョークでもない。時間とメモリのトレードオフに対する実際の解法で、筆者もそれを分かっている
問題自体はばかげているが非常に原始的なので可能であることに疑いはなく、40GBのプログラムを自分のコンピュータで約10秒間処理したという観察以外には、実測もなかった
それで何を学んだのか？ exeファイルは4GBを超えられないということ？
ifが2^32個あるとプログラムは約300GBになるということ？ なぜ1198人がこれを面白いと思ったのか分からない“Hexing the technical interview”やSIGBOVIKの記事と違って、これは狂っているのではなく、ただ無意味に見える
あまりに極端なので、どのコンパイラも処理できず、既知のアセンブラでさえ無理だった。だから動かすために機械語バイナリを自分で生成しなければならず、実際に動いた。狂っている
それぞれの
ifが入力と一致するか順番に評価されるはずで、元記事のプログラムが小さい数でははるかに速く終わるという出力もそれを裏付けている。小さい数がコードの前のほうにあるからだ一方、40億個の
caseを持つswitch文なら、何らかのルックアップテーブルにコンパイルされると予想する。ただし、型が符号なし整数のとき、最適化なしでコンパイルされたコードがどうなるかは分からない驚くべき技術だ。AWSに売って、40GBの実行ファイルをまともにホスティングできないすべての人にEnterprise-ready AWS EvenOrOdd APIとして提供させるべきだ
クラウドの力があれば、このプログラムは止められないはず
プログラムが800 MB/s * 10秒程度のディスク読み込みだけで40GBの命令を「処理」したことに、誰も突っ込んでいないのが驚き
推測するに、OSレベルの賢いキャッシュがあるのだろうが、そうだとすると
nが2^32に近いベンチマークは正しく実行されていなかったということになるあるいはCPUが数百万個の命令を飛び越えてジャンプできるほど賢いのかもしれない
最初は計算が間違っていると思ったが、ざっくり計算するとかなりあり得そうだ。数値もすべて曖昧に丸められた値だし、入力値も絶対最大値ではなく、単に高い値だったのでなおさらだ
ifたちが何かを知らないので、ここでは賢く振る舞えないそれらのコードが順番通りなのか、一意なのか、そもそも有効な命令なのかすら分からない。理論上はプログラム実行中にどれかの
ifを無限ループに変えることもできる。OSは許可しないだろうが本当に気になる。線形アクセスパターンが助けになるのは確かだろうが、800 MiB/sとは？
mmapするので、使われないページはページテーブルエントリだけを占有し、ロードされない。実際にロードされるのは直接ジャンプしたページだけ。見事なトリックだ先見の明ある天才Ross van der Gussomは、いまや私のお気に入りの神話上の生き物だ
この記事をおすすめする: https://cerfacs.fr/coop/fortran-vs-python
記事全体がLLM開発のアレゴリーのように感じる。批判者が書くなら、途方もないリソースと「学習データ」を投入して解法を「暗記」することだと言いそうだ
筆者の意図だったのか気になる
forループを実行する40BのLLMモデルのように見える。このアレゴリーこそが記事の実際の動機のように感じられ、工学の話ではなく、目前に迫る不条理を扱う記事のようだ