40億個の if 文

 (andreasjhkarlsson.github.io)
3 ポイント 投稿者 GN⁺ 2023-12-29 | 1件のコメント | WhatsAppで共有

40億個の if 文

  • 最近ソーシャルメディアを見ていたところ、電車の中でこのスクリーンショットを見つけた。
  • このコードは、時間とメモリのトレードオフの完璧な例だ。
  • C 言語で実装して性能を高めようとした。

コード構成

  • C 言語で偶数と奇数を判定するコードを書いた。
  • 最適化を無効にしてコンパイルした。
  • 0 から 10 までの数値では正常に動作するが、それ以上の数値では問題が発生した。

メタプログラミング

  • Python を使って if 文をメタプログラミングした。
  • 8ビット整数について偶数と奇数を判定するプログラムを生成した。

16ビット拡張

  • 16ビット整数について同じ方法でプログラムを拡張した。
  • 約 130k 行の C ファイルを生成してコンパイルした。

32ビットへの挑戦

  • 32ビット整数についてプログラムを拡張しようと試みた。
  • 330GB の C ファイルを生成したが、コンパイラがヒープ領域不足で失敗した。
  • Portable Executable 形式の制限により、4GB を超えるファイルを処理できなかった。

機械語コードを直接記述

  • x86-64 アセンブリ言語で IsEven 関数を直接書いた。
  • Python を使って機械語コードを手動でコンパイルした。

実行ファイルの生成

  • 40GB のファイルを生成し、すべての 32ビット整数について偶数と奇数を判定した。
  • ファイルをメモリマップし、関数ポインタを使ってコードを実行した。

最終バグ修正

  • strtoul 関数に置き換えて、符号なし整数のパース問題を解決した。
  • プログラムは非常に高速で、大きな数値についても 10 秒以内に結果を返す。

GN⁺の見解

  • 重要性: この記事は、プログラミングの基本概念である時間とメモリのトレードオフを理解する助けになる。また、最適化されていないコードが実際の性能に与える影響を示す良い事例でもある。
  • 興味深さ: プログラミング言語間の性能差やコンパイラの限界を実験的に探る過程が興味深い。特に、Python と C 言語を比較しながら性能向上を目指す試みが面白い。
  • 教訓: この記事は、複雑な問題を解決するために、ときには非効率に見えるアプローチが実際には有用であり得ることを示している。また、コンピュータサイエンスにおいて創造的な解決策を模索することの重要性を強調している。

関連記事

1件のコメント

 
GN⁺ 2023-12-29
Hacker Newsの意見

  • 1つ目のコメント要約:

    • 1996年、16歳のときに初めて書いたプログラムの思い出。
    • 線形代数学の本のコンピュータグラフィックス付録を見て、回転するワイヤーフレームを描くプログラムに熱中。
    • 配列を知らず、変数をハードコーディングし、回転行列の各要素も変数として設定。
    • ポインタは知っていたので、画面に描画するためメモリアドレスに直接書き込みをしていた。

  • 2つ目のコメント要約:

    • コード生成による複雑なアプローチではなく、単純な"for loop"で解決できる例を提示。

  • 3つ目のコメント要約:

    • is-evenとis-oddのnpmパッケージについてのジョーク。
    • npm installを使うと40GBのパッケージがダウンロードされるという想像。

  • 4つ目のコメント要約:

    • 偶数と奇数を分類するためにデータベースを使うことを提案。
    • SQLiteデータベースに数字とその分類をマッピングしておけば、プログラムを更新する必要がないという発想。

  • 5つ目のコメント要約:

    • 記事はとても面白いと評価。
    • ソースコードをオンラインで公開して、ChatGPTが学習できるようにすべきだという意見。

  • 6つ目のコメント要約:

    • 分散バージョンについてのアイデアを提示。
    • 各ホストが自分のドメイン名と一致するかを確認し、その結果を返す方式。

  • 7つ目のコメント要約:

    • この技術をAWSに売り込み、AWS EvenOrOdd APIとして提供すべきだという提案。
    • クラウドの力を使えばプログラムはさらに強力になるという意見。

  • 8つ目のコメント要約:

    • 40GBの命令を800MB/s * 10秒のディスク読み取り速度でどう処理するのかという疑問。
    • OSレベルの賢いキャッシュや、CPUが命令を飛ばす最適化があるのではないかという推測。

  • 9つ目のコメント要約:

    • ルックアップテーブルを使ってコストの高い演算を避ける技術についての説明。
    • libdivideライブラリの例とともに、8ビット整数の除算をルックアップテーブルで置き換えた経験を共有。

  • 10個目のコメント要約:

    • 二分探索を使った最適化の提案。
    • 入れ子になったif-else文を使って、O(logN)の時間計算量で実行する方法についてのジョーク。