ジッパーは実際にどの程度の性能を発揮しますか?いつ使用する必要がありますか?

Question

私は、 ジッパー 素晴らしいアイデアです。これは、リストまたはツリーをたどり、機能的な方法でローカル更新のように見えるものを作成する方法をエレガントに提供します。

漸近的には、コストは妥当であるように見えます。ただし、データ構造を走査するには、反復ごとにメモリ割り当てが必要です。通常のリストまたはツリーの走査は単なるポインタの追跡です。これは高価なようです（間違っていたら修正してください）。

法外な費用がかかりますか?また、どのような状況でジッパーを使用するのが合理的でしょうか?

Answer 1

確実なデータ ポイントを 1 つ提供できます。ジョン・ディアスと私は 2005 年の ML ワークショップでの論文 ここでは、制御フロー グラフを表すためにジッパーを使用するコストと、Objective Caml で可変レコード フィールドを使用するコストを比較しました。ジッパーベースの制御フロー グラフを使用したコンパイラーのパフォーマンスが、ポインターでリンクされた変更可能なレコードを含む従来のデータ構造を使用したパフォーマンスよりも実際にわずかに優れていることがわかり、非常に嬉しい驚きを感じました。正確に情報を提供できる本格的な分析ツールが見つかりませんでした なぜ ジッパーは高速でしたが、その理由は、維持する不変式が少なく、ポインタの割り当てが比較的少なかったためではないかと思います。また、オプティマイザが賢く、ジッパーによって発生した割り当てコストの一部を償却できた可能性もあります。いかなる場合でも、 ジッパーは最適化コンパイラで使用でき、実際にはわずかなパフォーマンスが得られます。 利点.