ラブグラフのエンジニア、横江 (@yokoe24) です。
みなさんは git コマンドで merge をしたことがありますか？
ありますね！！
（※ git を g でエイリアス振っていますが、 git merge develop です）
merge をしたときの出力をよく見ると、地味に気になる一文があります。
Merge made by the 'ort' strategy.
なんでしょう、これ・・・？
sort じゃなくて ort ・・・？
気になったので調べてみました。
すぐに出てくるのがこの記事。
2021/08/17 にリリースされた Git 2.33.0 についての記事です。
Gitの新しいマージ戦略「merge-ort」は、再帰的戦略をスクラッチで書き直したもので、正確性やパフォーマンスの問題に対処しています。GitHubによると、名前の変更が多い大規模なマージの場合、merge-ort は500 倍ものスピードアップを達成し、rebase操作におけるマージではmerge-ortは9000 倍以上スピードアップする模様。新しいmerge-ortは既存のマージコードよりも一貫して高速に動作する事が期待されています。
なんかすごそう！！
他にはこういう記事がありました。
既存の ort strategy と recursive strategy についての対比を書いてくれています。
ただし、この記事内では ort を Ostensibly Recursive Three-way の略だと紹介しているのですが、
実際にコード内を読んでみると、
/*
* "Ostensibly Recursive's Twin" merge strategy, or "ort" for short. Meant
* as a drop-in replacement for the "recursive" merge strategy, allowing one
* to replace
とあるように、 Ostensibly Recursive's Twin が正しい略なようですので、
記事の正確性には不安が残ります。
いろいろ調べた結果、
一番情報が多く正確性も高そうなのが GitHub のブログでした。さすが GitHub！
ここでは、マージ手法として使われていた resolve が2005年には merge-recursive となり、
そして2021年の Git 2.33 で merge-recursive になったこと、
および、アルゴリズム手法の変更によってどういう問題が解決していったのかを説明しています。
詳しいところは理解しきれていませんが、
複数のコミットがあるときに再帰的にマージしていたものを、先に全体感を見てからマージ手順を見ていくことで、
多数のコミットがある場合のマージ速度が高速になっています。
結果として、多数のファイルの名前変更を含み変更ファイル数も多いような、元の merge-recursive が苦手としていた変更において、
マージの速度は 500倍 、 rebaseの速度は 9000倍 となったそうです！ すごい！！
また、 メモリ使用量の低減 や、 コンフリクトが起こりにくくなる といった改良にもつながっています。
すごい！
カンタンにですが、 merge-ort の説明でした。
Merge made by the 'ort' strategy.
を見るたびに、素晴らしいアルゴリズムを作った方々への感謝をしようと思います😌
Discussion