こいつぁ、まったく馬鹿げた質問だけどな:
      Gitの
   パッキングヒューリスティックの
詳細はどこいきゃ確認できるんだい？

実に興味深い質問だね！

Gitのフォロワーは、Git IRCログを開いて、2006年2月10日を参照してください。

珍しいことに、King Git自身、Linus Torvalds（linus）が参加しています。 ナサニエル・スミス（njs`）は床を持っており、悟りを求めています。 他の人々は存在しますが、沈黙しています。

諸君聞き給え！

    <njs`> ええっと、本当にアホな質問するけど、
\tGitのパッキングヒューリスティックの詳細はどこで確認すりゃいいんだい？
        ググっても分からんし、
        ソースを読んでも役に立たんかったし、
        そしてメーリングリスト全体を探し歩くなんてやりたくもない。

大胆な語り口です！ 助けを乞う振りして探求者を三段構えで攻撃しています。グーグルが役に立たないという大げさな非難！ソースの自信たっぷりな悪用！ありがたーいメーリングリストのアーカイブを軽蔑する異端者！ 災いあれ

<pasky> ええ、パッキング関連のデルタとかは
    私にとってさえちょっぴり神秘的です ;)

ひたすら謙虚だぬ。

<linus> njs、ドキュメントは存在しないと思うわ。
     それは私以外の誰も実際に関与した事が無いと思う。
     Gitの他のほとんど（特にJunio）は活発で忙しいですが、
     私がそれを行った後、誰も触れませんでした。

不可解であいまいですが、これは確かにLinusスタイルです。賢人はこれを謝罪と解釈します。ごくわずかの人々は、それは単なる事実の陳述であると主張します。

<njs`> 次のステップは「ソースをもう一度読む」ことだと思うけどな。
    しかし、私は最初に、ある程度の強迫観念を惹起しなければなるまいて :-)

それはそう！ 両方の点で。

<linus> パッキングヒューリスティックは実際には本当に本当に単純なんだぜぃ。

誘います誘います！

<linus> でもオカシイ。

そして手のひら返し。それでこそLinus！

<linus> 思い出しな。Gitは実際にはファイルを追跡しねぇのよ。だからGitがすることは、
    - 全部のオブジェクトのリストを生成するじゃろ
    - そのリストを魔法のヒューリスティックに従ってソートするんじゃ
    - スライディングウィンドウを使用してリストを散歩し、
      ウィンドウ内の別のオブジェクトに対してオブジェクトを比較できるかどうかを確認するんじゃ
    - そんでもって最近の順序でリストを書き出す

伝統的でおとなしい表現:

<njs`> 私が見逃しているのは「魔法」という言葉の
    正確な定義だと思います

伝統的な洞察:

<pasky> そうだな

そして、バベルの塔のような混乱が起こりました。

<njs`> ああ、うーん、このスライディングウィンドウの意味も分からんわ
<pasky> iirc、コードを何気なく読んでいると、
    オブジェクトのsha1にすぎないように見えたけどね…

  1. which simply doesn’t sound as a very good heuristics, though ;)

<njs`> …..and recency order. okay, I think it’s clear I didn’t even realize how much I wasn’t realizing :-)

新しい跳躍の時です！そしてこうして悟りはまた新たに始まります。

<linus> 「魔法」は理論的には完全に恣意的です。
    どの順番でも作業パックが提供されますが、
    SHA-1順ではありません。
スライディングデルタウィンドウの順序について説明する前に、
最新の順序について説明しましょう。
それはある意味でより重要です。
<njs`> しかり。物をパックする作業方法だけが必要な場合は、
    catを使用するだけで、
    問題を回避できます…

しばーしお待ち下さい…

<linus> 最新の順序付け(recency ordering)
    (基本的には、オブジェクトを、ヘッドから「到達可能」な順序で、「物理的に」パックに入れる)
    が重要です。
<njs`> そりゃ分かるよ
<linus> それがパックに良い局所性を与えるものなので、それは重要です。
    パックの先頭でオブジェクトをヘッドの近く
    (古いものでも新しいものでも、ヘッドから「到達可能」です）に保ちます。
    そうすることで、パックには実際に絶対に
    「素晴らしい」IOパターンがあります。

ここ重要。もう一度じっくり読め

<linus> ただし、最新の順序付けは、
    実際にデルタを生成する方法を決定するのにまったく役に立たないため、
    デルタの順序付けは別のものです。
解説しよう！デルタ順位付け(delta ordering)とは！:
- オブジェクトリストを生成するときに、
  「最初に」到達した名前で定義される、
  オブジェクトの「ベース名」で最初に並べ替えます
- 同じベース名内で、オブジェクトのサイズで並べ替えます
- ただし、常に異なるタイプを個別に並べ替えます(コミットが最初です)。
正確には違いますが、ほぼこんな感じです。

<njs`> The "first reached" thing is not too important, just you need some way to break ties since the same objects may be reachable many ways, yes?

そこをkwsk:

<linus> 重要なのは、
    それはすべて実際にはランダムなヒューリスティックであり、
    順序付けは正確さにとってまったく重要ではないということですが、
    ヒューリスティックが互いにうまく差分化する可能性のあるものに
    「凝集」(clumping)を与える場合、それは大いに役立ちます。

重要なポイントなので、こっそり自分で調べて、その結果を以下にまとめました。 公平を期すために言うと、それは時間とともにいくらか変化しました。そして、リビジョン履歴魔法を使って、私の父の誕生日である3月1日のGit IRCLogsからの以下のエントリを呼び寄せました:

<gitster> 上記のlinusからの引用は、
    少し書き直す必要があります:
    - 最初にタイプでソートします。
      異なるオブジェクトが互いに差分化(delta)することはありません。<
    - 次に、ファイル名/ディレクトリ名で並べ替えます。
      ベース名のハッシュは先頭からBITS_PER_INT〜DIR_BITSビットを占め、
      末尾のDIR_BITSは先頭のパス要素のハッシュ用です。
    - 次に、「薄い」パッキングを実行している場合、
      パックしないオブジェクトは、
      他のオブジェクトよりも早くソートされます。
    - そして最後に、サイズで大きいものから小さいものへと並べ替えます。

1つのうねりで、明確化と不明瞭化！ それにもかかわらず、権威があります。 不可解でありながら簡潔。 ソースコードからの引用の概念さえも求めます。 明らかに、さらなる研究が必要です。

<gitster> これがソート順です。これが意味することは:
    - 異なるオブジェクトタイプを差分化(delta)することはありません。
    - 同じフルパスのオブジェクトを差分化(delta)することを好みますが、
      異なるディレクトリからの同じ名前のファイルを許可します。
    - 送信しないオブジェクトがある場合は、
      それに対して差分化(delta)することを常に好みます。
    - 大きなオブジェクトに対して差分化(delta)することを好むので、
      多くの削除があります。
最後から2番目のルールは「薄い」パッキング用です。他の側にそのようなオブジェクトがあることがわかっている場合に使用されます。

再び登場しました「薄い」パック(Thin packs)。 「薄いパックとは？」と思いました。 だから私は尋ねます:

<jdl> 薄いパックって何？
<gitster> pack-objectsの上流として、 `--objects-edge` を伴って rev-listを実行します。
    パック転送プロトコルはそれをネゴシエートします。

わぉ！一瞬でクリアしちゃいましたよ！

<gitster> 2つの方向があります。プッシュとフェッチです。

まぁ奥様みました？ プッシュとプルじゃございませんことよ！ ここで混乱が始まることがいかに多いことか。 さりげに、こんなことにも言及しています！

<gitster> プッシュのために、git-send-packは相手側でgit-receive-packを呼び出します。
    receive-packには、「I have up to these commits」(これらのコミットまであります)と書かれています。
    send-packはそれらを調べ、相手側から欠落しているものを計算します。
    したがって、「薄い」がデフォルトになる可能性があります。
他の向きでは、fetchとgit-fetch-packとgit-clone-packが、
相手側でgit-upload-packを呼び出します
(sshを介して、またはデーモンと通信します)。
2つのケースがあります: `-k` を伴ったfetch-pack と clone-pack がひとつ、 `-k` なしの fetch-pack でもうひとつです。
`-k` を伴ったfetch-pack と clone-pack は、
ダウンロードされたパックファイルを展開せずに保持するため、
薄いパック転送(thin pack transfer)は使用しません。
それ以外の場合、生成されたパックには、
同じパック内にベースオブジェクトのないデルタ(差分)が含まれます。
ただし、 `-k` を伴わないfetch-packは、受信したパックを個々のオブジェクトに分解するため、
upload-packがサポートしている場合は、
upload-packに薄いパック(thin pack)を提供するように自動的に問合せます。

然り。

それからどうした

閑話休題。

<njs`> そして「basename」は、「basename(3)に従って、
    ファイルオブジェクトとdirオブジェクトのパスの終わりの末尾であり、
    すべてのcommitオブジェクトとtagオブジェクトが同じbasenameを持つように宣言する」
    などの意味です。

幸いなことに、それもgitsterが私たちに明らかにしたポイントです！

付け加えると、そのトリックは、ファイル名に基づいて、類似している可能性のあるファイルをハッシュバケット内で互いに近くに配置することです。以前は、「foo/Makefile」と「bar/baz/quux/Makefile」と「Makefile」は、共通のベース名「Makefile」のすべて同じバケットに配置されていました。しかし、今では「近い」バケツに着地します。

このアルゴリズムでは、「同じバケット」だけでなく、「近いバケット」も差分化候補と見なすことができます。理論的根拠として、Makefilesのようなファイルは、どのディレクトリにあるかに関係なく、非常によく似たコンテンツを持っていることが多いということです。

<linus> さまざまなデルタ化アルゴリズムを試し、
    「デルタウィンドウ」を大きくしましたが、スライディングウィンドウが大きすぎると、
    パックの生成に非常にコストがかかります。
    すべてのオブジェクトを他の大量のオブジェクトと比較する必要があります。
他にも多くの些細なヒューリスティックがありますが、
デルタに価値がないことを事前に知ることができれば
(サイズの違いにより、以前のデルタ結果を考慮に入れて、
「わかりました。それを試してみても意味がありません。
悪化する」と判断できます)、
基本的に「このペアをデルタにするのは割に合わない」に要約されます。
最終結果: パッキングは実際には非常にサイズ効率が良いです。
CPUパワーをいくらか浪費する一方で、
実際には月に1回しか実行しないことになっているため(夜間に実行できます)、
誰も気にしません。

素敵な技術者的手際です。それが問題ではない時間を見つけて、それを問題ではないと宣言します。まったく良いやり方です！

<njs`> それじゃあ、繰り返しになるけど、私がついていけてるか確認するために、
    パックするオブジェクトのリストを取得することから始め、
    このヒューリスティックでソートします
    (基本的にタプル(タイプ, ベース名, サイズ)で辞書式順序)。
次に、このリストを調べて、
(調整可能なパラメーターである)最後のn個のオブジェクトに対する各オブジェクトのデルタを計算し、
これらのデルタの最小のものを選択します。

大幅に簡素化されていますが、本質はコレです！

<linus> その通りだ。
<njs`> 次に、各オブジェクトを表すデルタまたはフルテキスト(fulltext)を選択したら、
    最新性で再並替え(re-sort by recency)して、
    その順序で書き出します。
<linus> <linus>うん。それで、その他の細々を言うと:

そしてもちろん、linusならダメ押し言うよね。

<linus> - デルタ深度を別のマジック値に制限します
    (現在、ウィンドウとデルタ深度のマジック値はどちらも「10」です)
<njs`> うーん、私の直感では、必要なものが近くにあるため、
    マヂで悪いIOパターンになってしまう気がします。
    実際にそれらを再構築するには、
    ランダムな方法でジャンプする必要があるかもしれません。
<linus> - デルタを書き出すにあたって、
    デルタであるオブジェクトをまだ書き出していない場合、最初にベースオブジェクトを書き出します。
    しかし、それらを再構築すると、実際には優れたIOパターンが得られます。
    理由は以下のとおりです:
    - 大きなオブジェクトは「より最近」になる傾向があります(リーナスの法則:ファイル達は成長します)
    - 大きなオブジェクトから小さなオブジェクトへのデルタの生成を
      積極的に試みます
    - これは、ツリーの最上位にデルタがほとんどないことを意味します
      (つまり、実際のデルタは「後方デルタ」(backwards deltas)です）

繰り返しますが、我々はこの段落全体を読み直す必要があります。Linusの法則を私たちにぬるりと滑り込ませたからだけでなく、それは重要だからです。ここでいくつかのポイントを明確にしましょう:

<njs`> つまり、実際には、
    デルタの順序と最近の順序は非常によく一致しているということです。
<linus> ええそうです。これには別の良い面があります
    (そして、それは以下のように設計されました):
    - 大きなオブジェクトに対してデルタを生成する理由は、
      実際には大きなスペース節約にもなります。

<njs`> Hmm, but your last comment (if "we haven’t yet written out the object it is a delta against, we write out the base object first"), seems like it would make these facts mostly irrelevant because even if in practice you would not have to wander around much, in fact you just brute-force say that in the cases where you might have to wander, don’t do that :-)

<linus> Yes and no. Notice the rule: we only write out the base object first if the delta against it was more recent. That means that you can actually have deltas that refer to a base object that is not close to the delta object, but that only happens when the delta is needed to generate an old object.

<linus> お分かり？

ごめん。私は最初の2、3回読み込んだ時は見逃してました。

<linus> これにより、パックの前側が密になります。
    パックの前側には、「最近の」オブジェクトに関連しないデータが含まれることはありません。
    サイズの最適化は、xdeltaの使用に由来します
    (ただし、他の多くのデルタアルゴリズムにも当てはまります)。
    データの削除は、データの追加よりも(サイズ的に)安価です。
データを削除するときは、「バイトn--mをコピー」と言うだけで済みます。
対照的に、データを追加するデルタでは、
「これらのバイトを追加します： '実際のデータはここにあります'」と言わなければなりません。

  • njs` が退出しました: Read error: 104 (Connection reset by peer) 

    <linus> うーん。 njsが逝ったのは私のせいじゃないよね？

  • njs` が channel #git に入室しました。 

    <pasky> :)

もちろん皆そう思ってるよ。

そして、まるで njs が全知であると期待されたかのように:

<linus> njs、何か見逃しましたか？

OK、詳しく説明します。それはオタクのユーモアです。 njs が実際に少しの間接続されていなかった場合、切断中に何かを逃したかどうかをどうやって知ることができますか？彼はユーモアのセンスのある慈悲深い独裁者です！よくいうよｗｗｗ

<njs`> クソルーターめ、グレムリンめ

これはCiscoの安っぽいショットです。 そんなもん捨てちまえ

<njs`> イエスもありノーでもある。ルールに注意してください。
最初にベースオブジェクトを書き出すのは、それに対するデルタがより最近のものである場合のみです。
私はこれらすべての順番で迷子になっています、再読させてください:-)
それで、書き込みの順番は新しいものから順にということですよね？
(おそらく逆の方法かもしれませんが、私たちが言ったかどうかはわかりません）
自宅に戻ったら私の接続はログに記録されているので、
そこであなたが言ったことを読むことができるでしょう :-)

そして、気にしている人のために、全知全能トリックが詳細に説明されました！

<linus> そうだよ。常に最新のものを最初に書きます
<njs`> そして、ええっと、歴史の深いものはIOの特性が悪くなる、
という部分は理解できましたが、ある種、気にならないものです。
<linus> 「最新の」オブジェクトがデルタ化するために
    古いオブジェクトを必要とする場合(しばしば縮小が起こる)、
    我々はデルタを伴って古いオブジェクトを書き出します。
<njs`> (それがもっともっと起こったら…)
<linus> とにかく、パックファイルはさらに簡単に高密度になる可能性がありますが、
    ストリーミング(Gitプロトコル)とディスク上の操作での両方に使用されるため、
    ちょいとばかり冗長でパフォーマンスが良くありません(it has a few pessimizations)。

実は、これは造語なんです。しかしこれは後の最適化のための設定として使われる造語で、現実の言葉なのです:

<linus> 特に、pack-fileは圧縮されますが、
    一度に1つのオブジェクトだけが圧縮されるため、実際の圧縮率は理論上の圧縮率よりも低くなります。
    しかし、それは、「オブジェクト名→パックファイル内の場所」の変換を行うための、
    単純なインデックスを使用した、
    すべてにおいて優れたランダムアクセスであることを意味します。
<njs`> 大→小 をデルタ化することの本当の勝利は、
    gzipが実行されるより均一な統計であると思いませんか？
(あなたはバイトをどこかに配置する必要がありますが、
より大きなブロブに配置すると、圧縮が優先されます)
実際、圧縮戦略とは何でしょうか -- 各デルタは個別にgzipで圧縮され、
ファイル全体がgzipで圧縮され、
その間のどこかでは圧縮はまったく行われませんが…？
正しい。

現実のIRCが始まります。例:

<pasky> 残りは朝に読みます、私は本当に眠らなければなりません、
    さもなければ今日の試験で私には何の希望もありません…
    皆さんお休みなさい。

ありゃりゃ。

<linus> pasky: おやすみ
<njs`> pasky: グッドラック
<linus> 正しい: 圧縮動作のために、大きい→小さい ことが問題になります。
    圧縮されていない場合は、
    おそらく違いはありません。
<njs`> うんうん。
<linus> とにかく：パックファイルが完璧だと主張するつもりはありませんが、
    それは密度と使いやすさのバランスが
    うまく取れている傾向があります。

うほっ！保存しますた。これは、エンジニアリングの公正なトレードオフです。 危機一髪！ 実際、Linusは、いくつかの基本的なエンジニアリングの基礎、設計オプションなどを反映しています。

<linus> さらに重要なことは、Gitが概念的にデルタをまったく処理せず、
    「オブジェクト全体」のストアになることを可能にすることです。
これにはいくつかの問題があります
(先日、Gitメーリングリストで
巨大ファイルの良くない振る舞いについて説明しました)が、
基本的なGitの概念が本当に単純で素直であることを意味します。
それはすべて非常に安定しています。
これは非常に単純な基本的な考え方の結果であると私は思います。
そのため、
何が起こっているのかについて混乱することはありません。
バグは発生しますが、それらは「単純な」バグです。
また、オブジェクトストアの詳細を実際に間違えるバグは、
ほとんどの場合非常に明白であるため、見間違えようがありません。
<njs`> ああ。

それはもうおなかいっぱいだよ

<linus> とにかく。 私は寝る。まだ午前6時ではありませんが、
      私には3人の子供がいて、子供らを送り出すために早朝に起きなければなりません。
      私には素晴らしい睡眠が必要です。
<njs`> :-)
<njs`> <njs`> infodumpに感謝します、
    私は本当にGitパックの詳細を見つけることができませんでした :-)

そして今や、あなたは物語の顛末を知ったのです。