CPUキャッシュ– tag –
-
コンピュータ科学 深掘り
計算量とO記法 — データが10倍で100倍遅くなる
テストデータ100件では一瞬だった処理が、本番の10万件で固まりました。原因は「遅いコード」ではなく「データが増えると時間が何倍になるか」を見ていなかったことでした。この記事ではVMの中に小さな計測台を作り、O(1)・O(log n)・O(n)・O(n log n)・O(n²)・O(2ⁿ) の6つを実際に走らせて、nを10倍にしたとき時間が何倍になるかを表にします。定数を無視する理由も、nとn²/100が逆転する交差点を実測して確かめます。最後に、同じO(n)でもメモリのアクセス順で数倍変わることを測り、なぜ最後は必ず測るのかまで見ます。 -
コンピュータ科学 深掘り
配列と連結リスト — 先頭への追加が数百倍遅い
配列の末尾に1万件足すのは一瞬なのに、先頭に1万件足したら固まりました。原因は「データの置き方」で、この記事ではそれをVMの中のNode.jsで実測して確かめます。push と unshift を10万回ずつ回して差を測り、動的配列の「2倍に取り直して全部コピー」を自分で実装してコピー回数を数え、単方向・双方向の連結リストを自分の手で書きます。そのうえで、同じ O(n) の全走査を配列と連結リストで比べると教科書どおりにならないことを実測で確認し、CPUキャッシュという理由まで降りていきます。最後に「どの操作にどちらが向くか」を、計算量と実測の両方が入った1枚の表にまとめます。 -
コンピュータ科学 深掘り
CPUの仕組みを自作する — 足し算しかしていない
CPUを「魔法の箱」で終わらせないために、手元で全部作って動かします。2の補数をJavaScriptで組んで引き算を足し算に置き換え、AND・OR・XOR・NOTの4関数だけから8ビット加算器を作って0〜255の全組み合わせでJavaScriptの + と一致することを確認します。命令が10個だけの極小CPUシミュレータを書いてフェッチ・デコード・実行を1サイクルずつ表示させ、レジスタ版とメモリ版でアクセス回数を数えます。最後に本物のCPUを lscpu と gcc -S で覗き、キャッシュの効き方を実測して、割り込みの回数が増える瞬間を vmstat で見ます。
1