- 2010年に投稿されたJavaの
humanReadableByteCount回答は、2018年の研究で最もコピーされたStack Overflowコード片と確認されたが、バイトサイズのフォーマットにおける境界値で誤った結果を出していた
- このコードは、
kB、MB、GBのような接頭辞が1000または1024の累乗であることを利用し、ループの代わりに対数計算で単位を選ぶ方式だった
- 中核的なバグは、SIモードで
999,999 bytesが"1000.0 kB"と出力される丸め境界値の問題で、仕様上、数値範囲が1から999.9なら"1.0 MB"が正しい
- より大きな値では、
doubleの浮動小数点精度の限界も重なり、999,949,999,999,999,999という入力が1000.0 PBになっていた。補正にはしきい値計算とスケール縮小、ビットパターン補正、strictfpが必要だった
- 最終コードは負数と
Long.MIN_VALUEまで処理するが、元の簡潔さは失われた。Stack Overflowのコードをコピーする際には、エッジケースのテストと出典表示もあわせて必要になる
2010年の回答が狙った単純化
- 問題は、バイト数を人間が読みやすい文字列にフォーマットすることだった
- 例:
123,456,789 bytesを"123.5 MB"のように出力する
- 暗黙の仕様は、結果文字列の数値部分が1から999.9の間で、適切なサイズ接尾辞が付く形式だった
- 既存の回答は、
EB、PB、TB、GB、MB、kB、Bを大きい単位から順にたどり、バイト数より小さい最初の単位を選ぶループベースのアプローチだった
- 新しい回答は、ループと分岐を減らすために
Math.logとMath.powを使っていた
- SIモードでは単位が
1000
- バイナリ表記では単位が
1024
exp = log(bytes) / log(unit)の値を整数に変換し、接頭辞インデックスとして使用- 接頭辞はSIでは
"kMGTPE"、バイナリでは"KMGTPE"を使い、バイナリには"i"を付け加える
コピーの実態とOpenJDKでのエピソード
- Sebastian Baltesの論文Usage and Attribution of Stack Overflow Code Snippets in GitHub Projectsは、Stack Overflowのコード片がGitHubプロジェクトでどのように使われ、出典表示されているかを分析した
- 分析方法は、Stack Overflowのデータダンプからコード片を抽出し、公開GitHubリポジトリのコードと照合するものだった
- 中心的な問いは、Stack OverflowのCC BY-SA 3.0ライセンスに沿った出典表示が守られているかだった
- 結果として、ほとんどの利用者は適切な出典表示を含めていなかった
- 回答ID 3758880は論文の表で最上位にあり、当時は数十万回の閲覧と1,000件以上のアップボートを得ていた
- GitHubで
humanReadableByteCountを検索すると数千件の使用例が見つかり、ローカルリポジトリでは次のコマンドで確認できる
git grep humanReadableByteCount
- OpenJDKリポジトリでも一致例が見つかった
- そのコードには出典表示がなく、OpenJDKのライセンスはCC BY-SA 3.0と互換性がなかった
- Sebastian BaltesはOpenJDK開発メーリングリストで、そのコードがStack OverflowからOpenJDKへコピーされたのか、逆だったのかを質問した
- 回答の投稿者は、そのコミットがマージされる前にはOracleに入社しておらず、そのパッチにも貢献していなかった
- その後、課題が登録され、コードは削除された
1つ目のバグ: 9が続く境界値
- 一見疑わしい問題は、実際の原因ではなかった
longの最大値は2^63 - 1、約9.2 × 10^18なので、EBより上の単位には進まないbytes < unitの場合は最初のifが処理するため、expが0になってcharAt(exp - 1)が失敗することもない
- 実際の問題は丸め境界値だった
- 入力
999,999 bytesはSIモードで"1000.0 kB"になる
- 数値部分が1から999.9の間でなければならないという仕様に従えば、正しい結果は
"1.0 MB"である
- 執筆時点で投稿されていた22件の回答すべてが、Apache CommonsやAndroidライブラリを使う回答も含め、このバグまたはその変種を抱えていた
- 解決の要点は、指数
expをいつ次の単位に上げるかを決めるしきい値である
kからMに変わる時点は、値が999.9 kより1 MBに近くなる999,950MからGに変わる時点は999,950,000- バイナリモードではしきい値が整数ではないため、
ceilが必要になる
if (bytes >= Math.ceil(Math.pow(unit, exp) * (unit - 0.05)))
exp++;
2つ目のバグ: double精度の限界
- 上の補正を適用しても、
999,949,999,999,999,999という入力は1000.0 PBと出力され、正しい結果は999.9 PBだった
- 原因は数式そのものではなく、double精度の限界だった
- IEEE 754表現では、0に近い浮動小数点値は密だが、大きな値は非常に疎になる
- 非常に大きな
doubleでは、Long.MAX_VALUEを引いても値が変わらないことがある
double a = Double.MAX_VALUE;
double b = a - Long.MAX_VALUE;
System.err.println(a == b); // prints true
- 問題となる計算は2か所で発生する
String.formatの引数で行う除算expを上げるかどうかを決めるしきい値計算
- 1つ目の問題は、中間の
bytes値を精度がより良い範囲に下げ、expを調整する方式で処理する
- 最終結果はいずれ丸められるため、下位桁を捨ててもよいという前提である
if (exp > 4) {
bytes /= unit;
exp--;
}
- 2つ目の問題では下位ビットが重要だった
999,949,99…9と999,950,00…0は異なる指数に分類されなければならない- 可能なしきい値はSIとバイナリを合わせて12個あり、そのうち1つだけが誤った結果を出していた
- 誤った結果は
D00で終わるビットパターンで識別して補正する
- 特定の浮動小数点結果のビットパターンに依存するため、
strictfpを付けた
負数入力と最終コード
- Javaにはunsigned
longがないため、負のバイト数の処理も追加された
- 従来は
-10,000という入力が-10000 Bと出力されていた
absBytesを導入し、exp関連の計算は絶対値基準で行う
Long.MIN_VALUEには特別な処理が必要だった
-Long.MIN_VALUE == Long.MIN_VALUEだからである- そのため、
bytes == Long.MIN_VALUEならLong.MAX_VALUEを使い、それ以外ではMath.abs(bytes)を使う
- 最終版には、
strictfp、しきい値補正、Long.MIN_VALUE処理、大きな指数でのスケール縮小が含まれる
- ループと過剰な分岐を避けようとしたコードは、すべてのコーナーケースを整えた後、元のバージョンより読みにくいコードになった
- プロダクション品質の最新コードは、別記事Formatting byte size to human readable formatを参照できる
実務で残る教訓
- Stack Overflowのコード片は、数千件のアップボートがあってもバグを含む可能性がある
- コピーしたコードには、とくにエッジケースのテストが必要である
- 浮動小数点演算は、境界値と大きな数で扱いが難しい
- コードをコピーするときは適切な出典表示が必要であり、そうしないと実際に問題になり得る
1件のコメント
Hacker News の意見
ハードコードされた値と
if文（またはwhile）を使う回答が、どれも最大 5回の比較を行うのは興味深い単位が B、KiB、MiB、GiB、TiB、EiB までだけなら、最大3つの
if文でも解決できる。GiB 以上かを確認すれば B/KiB/MiB ではないと分かるので、二分探索が勝つZiB と YiB まで増やしても最大3回の比較で十分で、ハードコード方式は最大7回まで行く。自分で書くなら
log/pow/浮動小数点はミスの可能性が大きすぎるので使わず、if文をハードコードしつつ二分探索にすると思うこのようなコードは、より遅く、より複雑で、テストやレビューもより難しいコードを書くために多くのことをしているようなものだ
（2019）過去の議論:
https://news.ycombinator.com/item?id=21693431
https://news.ycombinator.com/item?id=21698619
https://news.ycombinator.com/item?id=27533684
The most copied StackOverflow snippet of all time is flawed (2019) - https://news.ycombinator.com/item?id=27533684 - 2021年6月、コメント334件
The most copied StackOverflow snippet of all time is flawed - https://news.ycombinator.com/item?id=21698619 - 2019年12月、コメント88件
The most copied StackOverflow snippet of all time is flawed - https://news.ycombinator.com/item?id=21693431 - 2019年12月、コメント3件
理解できない。接尾辞が7つなら二分探索で正しいものを選べばよく、比較は3回で済む。あるいは単純にやっても比較は6回だ
log()を2回、pow()を1回、ceil()を使うのが、単純な方式よりなぜ良いというのか分からない。ここで説明されているバグ自体が、賢くやりすぎようとして生まれた完璧な例だそれでも丸めのバグを考慮しているので、原文の最初のコード例よりは少しましだ
また比較6回は最大値の場合だけで、実際の使用ではそうなる可能性は低そうだ。ほとんどの値が B や KB の範囲なら、線形方式の方がよい場合もある
厚かましい宣伝だが、S/O からコピーする代わりに、人間が読みやすい形式でサイズを高速かつ正確にフォーマットしたいなら、私たちのオープンソース PrettySize ライブラリも使える。Rust 用 [0] と .NET 用 [1] があり、ファイルサイズに対する型安全な論理演算も安全かつ簡単にしてくれる
S/O のスニペットは4行だが、これらのライブラリははるかに包括的で、テスト、出力フォーマットオプション、サイズ変換などを含む
[0]: https://github.com/neosmart/prettysize-rs
[1]: https://github.com/neosmart/PrettySize.net
純粋な疑問なのだが、Stack Overflow の信用できないコードをそのままコピーしてアプリケーションに貼り付ける開発者はかなり多いのだろうか？
人々が Stack Overflow からそのままコピーするという推測は有名だが、実際に誰かがやっているのを見るまでは冗談に近いと思っていた。自分もなじみのない領域で問題を解くときの出発点として Stack Overflow を使うが、コードをそのままコピーしたことはない。
たいてい断片的なコードは、自分が必要としていることだけを正確にやってくれるわけではないので、API を調べ、説明されているアプローチをもとに自分の解法を作る必要がある。特に Python では、Stack Overflow が有用なニッチな APIの方向を示してくれたことが多い。
文字どおり Google → 最初に見える Stack Overflow のリンクをクリック → 最初に見えるコードブロックをコピー＆ペースト、という流れで、時には言語すら違っていた。ペアプログラミング中には、入力デバイスを物理的に奪い取る必要があった。間違っていると言うと、こちらが言い終える前にページ上の 2 つ目のコード片を貼り付けていて、妙に速かった。
極端な例ではあるが、「コードが必要だ。Stack Overflow にコードがある。解決！」という考え方で、それが適切な解法かどうかをまったく考えない開発者は多い。
いずれにせよ私たちは、あまり気にしていない配管作業の部分について、見知らぬ人が作ったライブラリコードを常に取り込んでいる。掘り下げて理解したければ自分で書く可能性が高いが、この部分は「とにかく動く」状態にしてプロジェクトを進めたいなら、コンパイラエラー駆動開発になる。
変数名も変える。
foo、bar、bazが多すぎて、人間には読みづらいことが多いからだ。同じ問題に再び出会ったときも、盲目的にコピーした場合より、自分が何をしたのか思い出しやすい。log 2が必要なのに、なぜ浮動小数点のログを使うのか分からない。私が何か見落としていなければ、以下の式は 2^63 バイト未満の正の数について
floor(log2(value))を正確に返し、しかもずっと速い。Long.bitCount( (Long.highestOneBit(value) << 1) - 1) - 1コード片を見た瞬間に、浮動小数点の
log演算と整数に対する除算が目に入り、賢く書きすぎたせいで本質的にバグを生みやすいコードだと判断して、頭の中ですぐに捨てた。知識の連鎖はどこまでも続く。ごく小さな知識でさえ、一度取り出すと元に戻すのがどれほど難しいかを示している。
Stack Exchange が活発な貢献者を急速に失っている状況で、後になって誤りだったと判明した早撃ち回答を正すには何が必要なのか気になる。そして、こうした「少し間違った」回答が検索履歴に、さらに LLM の歴史の中にますます固定化されていくと、私たちの集合知にとって何を意味するのかも気になる。
基礎軍事訓練のときを思い出す。教官たちは新兵に、誰もやり方を知らない課題をわざと指示なしで与えて立ち去ることがあった。
すると必ず誰かが間違った方法で始め、残り全員がその人に従った。
公開される経済見通しでも似たようなことが起こる。他の人は当てたのに一人だけ外した人は、全員が一緒に外した人よりはるかに厳しく扱われる。
こうしたアルゴリズムにおける浮動小数点誤差を、必ずしも「欠陥」とは見なさない。コードが論理的かつ数学的に正しい解法を定義しているなら、それ自体は「正しい」と考える。
浮動小数点誤差を解決するのはそれより一段上の作業であり、実際に重要なときにだけ行うものだ。浮動小数点誤差が存在せず、考慮する必要もない完璧な未来のプログラミング言語を想像できるが、私のアルゴリズムの 99% はそういう言語を対象にしているようなものだ。