JSON、CSVへのデータシリアライズやログ記録の際に、数値を文字列に変換します。浮動小数点数はバイナリ形式で保存されますが、10進数の文字列が必要です。最初に正式に発表されたアルゴリズムはSteeleとWhiteのDragonスキーム（特にDragin2）で、1990年のことです。それ以来、より高速な手法としてGrisu3、Ryū、Schubfach、Grisu-Exact、Dragonboxが登場しました。C++17では、この目的のための標準関数std::to_charsが用意されています。一般的な目標は、元の数値を一意に識別できる最短の文字列を生成することです。

私たちは最近、Converting Binary Floating-Point Numbers to Shortest Decimal Stringsを発表しました。浮動小数点数から文字列への完全な変換を検証します。実際の変換は2つのステップからなります。数値を受け取り、有効数字と10のべき乗を計算するステップ（ステップ1）と、文字列を生成するステップ（ステップ2）です。例えば、数値piの場合、文字列3.1415927を生成する前に31415927と-7を計算する必要があります（ステップ1）。文字列生成では、ドットを適切な位置に配置し、必要に応じて指数表記に切り替えます。文字列生成は比較的安価で、古い方式では無視できるコストでしたが、ソフトウェアの高速化に伴い、今ではより重要な要素（時間の20%〜35%を占める）となっています。

結果は変換する数値によってかなり異なりますが、Jeon氏によるDragonboxとGiulietti氏によるSchubfachの2つの実装が最も優れている傾向にあることがわかりました。Adams氏によるRyūの実装もそれに迫るか、同等の速度です。これらの手法はすべて、1990年のオリジナルのDragon 4より約10倍高速です。3十年で10倍の性能向上は、年間約8%の向上に相当し、これはすべてより良い実装とアルゴリズムによるものです。

効率的なアルゴリズムは、生成される文字列1つあたり200〜350命令を使用します。Linuxでの標準関数std::to_charsは、必要以上に少し多くの命令を使用している（最大で約2倍）ことがわかりました。したがって、一般的な実装を改善する余地があります。人気のC++ライブラリfmtの使用は、少し効率が劣ります。

面白い事実として、利用可能などの関数も最短の文字列を生成していないことがわかりました。std::to_chars C++関数は数値0.00011を0.00011（7文字）としてレンダリングしますが、より短い科学的表記1.1e-4の方が適切です。ただし、慣習により、科学的表記に切り替える場合は指数を2桁にパディングする必要があります（したがって1.1e-04）。この技術的な問題を超えて、どの実装も常に最短の文字列を生成するわけではないことがわかりました。

私たちのコード、データセット、生の結果はすべてオープンソースです。ベンチマークスイートはhttps://github.com/fastfloat/float_serialization_benchmark、テストデータはhttps://github.com/fastfloat/float-dataにあります。

Reference: Converting Binary Floating-Point Numbers to Shortest
Decimal Strings: An Experimental Review, Software: Practice and Experience (to appear)

Published by

Post navigation