performance - ジッパーは実際にどの程度機能しますか? また、いつ使用する必要がありますか?

Question

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

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

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

Answer 1

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