mambaやripのinstallが何故早いのか調べたメモ
mamba-org
- フランスにjupyterやConda-forgeの開発者が集まるQuantStackという会社があり、そこに所属していた開発者 @wuoulf が主軸になったOSSプロジェクト
- condaは大部分がPythonで書かれたツールであるのに対し、Mambaプロジェクトではcondaの互換性を保った形で多くをC++で再実装したツール「mamba」を開発している
- mambaはcondaに比べ、依存解決やパッケージのbuild方法の変更、並列化を行う事でも高速化されている
mambaでの速度改善
- conda installの実装
- 関連するrepodata.jsonファイルを全てダウンロードしてメモリ上に乗せる
- すべての依存関係の中から環境で使用される可能性のあるパッケージを絞り込む
- SATとしてSATソルバを再帰的に実行する
- SATソルバの結果得られたパッケージをinstallする
- conda実装はSATソルバと他ロジックを複数回行き来しており、依存解決はC++、優先度決定やCachingの戦略はPythonという形になっている
- Pythonとのやり取りがボトルネックになるため、mambaではrepodata.jsonを取得後、2の段階からC++に情報を渡す実装となっており「複数回のSATソルバ呼び出し」が無くなった
- C++実装のため「優先度決定等のためのPythonとC++間のオブジェクトの行き来」も大幅に無くなった
ripに応用されたこと
- ‣
- ここまでで得られたテクニックを利用し、Rustでまるっと書き直したのがripにあたる
- Rustで書くことで高速に依存解決とinstallができるようにな実装になっている
- 依存解決はlibsolv(CDCL)のRust実装「resolvo」を利用
- ロジック面のポイントとしてresolvoに入っているIncremental solvingという考え方が高速化に繋がっている
- Pythonパッケージにおいては正確なメタデータがPyPI APIから返ってこないため、METADATAファイルに何らかの形でアクセスする必要がありこれが高コスト
- 優先度付きキューにメタデータ取得処理を詰め込んで、Solverは非同期的にPackageの情報を取得、追加しながら探索を行う