Re: [Gnu-arch-users] [PATCH] arch speedups on big trees

[Chris Mason]

On Wed, 2004-01-28 at 15:15, Aaron Bentley wrote:
> On Wed, 2004-01-28 at 14:20, Chris Mason wrote:
> 
> > > add-pristine can, indeed, take a --link option.
> > > 
> > Since libraries can be linked, and libraries would eventually kill
> > pristine trees, there's no need to add code to pristine trees that you
> > would just kill later on.
> 
> If doing after the fact is useful to you, tla changes --link will
> hardlink to a pristine just as well as it does to a revlib.
> 
Neat.
> 
> > I'm sure there are better ways to make it faster than my current code,
> > but I haven't seen a lot of other ideas discussed.
> 
> I think that hinting combined with with partial tree inventories can
> provide similar performance to reverse mapping.  Maybe I wasn't clear in
> that post, or maybe there are flaws I don't see:
> 
> If you've got hints and partial tree inventories (i.e. "search the tree
> for these ids, and start with these files"), performance should be
> similar to your original patch, but entirely safe.
> 
> For inexact patching:
> 
> To handle the case where a file is renamed, but remains in the same
> directory, you can hint all the files in the same directory as altered
> files.  You'd put them lower in the list than the entries for the actual
> altered files, so you'd only search them if the files *had* been
> renamed.
> 
> For a totally random file move, you'll do a half-tree inventory, on
> average.  But there are probably other forms of hinting that can reduce
> that too.  Like hinting directories/files with recent mtimes.
> 
> Does that make sense?

For renames it makes sense.  But it can't handle a new file without
doing a whole tree inventory, since arch makes sure the ids don't
conflict (my early patches didn't deal with this, Tom educated me ;-)

So, I do have code that falls back to a whole tree inventory for renames
and new files, but uses partial inventories in all other cases.  It
could be optimized with hints as you suggest.  I preferred the reverse
mapping idea because it covered all cases (and I merge lots of patches
that add files).  But I can forward along if you are interested.

-chris