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

[Andrew Suffield]

On Fri, Dec 19, 2003 at 03:08:02PM -0800, Tom Lord wrote:
>     A>>> Actually, that suggests a variation that makes more sense:
> 
>     A>>> When we're trying to modify or delete the file with id X, we
>     A>>> don't really want to know the path of every file in the tree
>     A>>> - just the one with id X. So, start by asking "Does the file
>     A>>> at path foo have id X?"
> 
>     A>>> and if it does, stop. If it doesn't, scan outwards until we
>     A>>> find it (simplified form: scan the whole tree).
> 
>     A>>> That'll require a bit of refactoring of the inventory
>     A>>> interface, I think, but shouldn't be too hard. It should work
>     A>>> for any changeset application.
> 
>     A>>> Adding a file is the exceptional case - we have to scan the
>     A>>> whole tree for that. But it doesn't happen very often in
>     A>>> general, so that's probably a reasonable cutoff point for the
>     A>>> optimisation.
> 
>     T>> My hunch is that you're proposing a fairly large amount of
>     T>> code work and resulting complexity for, after the
>     T>> inode-sig-implies-id hack being extended to handle explicit
>     T>> tags, a relatively small return.
> 
>     T>> I'd be much happier just to see a first cut at mason's
>     T>> optimization that only tries to handle the exact-patching
>     T>> case.
> 
>     A> I'd have thought that was actually harder to implement. What's
>     A> so difficult about just running the inventory scan on a single
>     A> named file?
> 
> mason's hack _does_ run inventory on single files (and short lists of
> single files).   What it _doesn't_ do is "search outward" for files.

Well, that part's fairly trivial to implement (in the simple form,
where you fall back to a full scan).

> Such optimizations require a fairly heavy proof before we can trust
> them: they must prove that the apply_changeset algorithm is invarient
> under them.  You haven't offered such a proof for your variation and,
> in fact, your proposal to specially consider only modified or deleted
> files is flat out wrong.

What's wrong with it?

-- 
  .''`.  ** Debian GNU/Linux ** | Andrew Suffield
 : :' :  http://www.debian.org/ |
 `. `'                          |
   `-             -><-          |

signature.asc
Description: Digital signature