Re: Calculating tree nodes

On 9/4/07, Jon Smirl [off-list ref] wrote:

On 9/4/07, David Tweed [off-list ref] wrote:

quoted

On 9/4/07, Jon Smirl [off-list ref] wrote:

quoted

Git has picked up the hierarchical storage scheme since it was built
on a hierarchical file system.

FWIW my memory is that initial git used path-to-blob lists (as you're
describing but without delta-ing) and tree nodes were added after a
couple of weeks, the motivation _at the time_ being they were a
natural way to dramatically reduce the size of repos.

One of the nice things about tree nodes is that for doing a diff
between versions you can, to overwhelming probability, decide
equality/inequality of two arbitrarily deep and complicated subtrees
by comparing 40 characters, regardless of how remote and convoluted
their common ancestry. With delta chains don't you end up having to
trace back to a common "entry" in the history? (Of course, I don't
know how packs affect this - presumably there's some delta chasing to
get to the bare objects as well.)

While it is a 40 character compare, how many disk accesses were needed
to get those two SHAs into memory?

That's a difficult question. Clearly if you're starting on a machine
without anything cached, you're probably a bit worse off. If not and
you've got a "wide, shallow tree where changes occur clustered within
directories rather than spread uniformly throughout the tree" then
it's likely already there.

But it's all I suspect it should be looked at in relative terms: with
the respect to the delta-d list of SHA's, do you need to do more or
less disk reads to be able to compare stuff? Dunno: I'd imagine this
depends on precisely what's delta'd against what and how many of those
you need to read in order to put two entries into a comparable form.
The key point I was making was not so much the 40 characters as that
(at least with loose objects) if you can are given the top-level
SHA's, you can efficiently decide equality (a key to efficient
diffing) _without having to care how those two are related in the
history or read any extra history_.

-- 
cheers, dave tweed__________________________
david.tweed@gmail.com
Rm 124, School of Systems Engineering, University of Reading.
"we had no idea that when we added templates we were adding a Turing-
complete compile-time language." -- C++ standardisation committee