"Matthew D. Fuller" <fullermd@over-yonder.net> writes:

quoted text
>> For example, how long does it take to do an arbitrary "undo" (ie
>> forcing a branch to an earlier state) [...]
>
> I don't understand the thrust of this, either.  As I understand the
> operation you're talking about, it doesn't have anything to do with a
> branch; you'd just be whipping the working tree around to different
> versions.  That should be O(diff) on any modern VCS.

There are two things to do:

* Mark the tree as corresponding to a different revision in the past.
  This is roughly "echo 'revision@id-123' > .bzr/checkout/last-revision"
  in bzr. Obviously, writting the file is O(1), but computing the
  revision identifier if you say "bzr switch -r 42" (I'm not sure
  switch accepts this BTW), you have to load the revision history.
  Indeed, bzr would load it anyway to make sure that the revision you
  switch to is in the revision history.

  In bzr, you have .bzr/branch/revision-history for each branch, which
  is a newline-separated list of revision-identifiers. In the case of
  bzr.dev, for example, this file is 112KB as of now. This is
  O(history), with "history" being the length of the path from HEAD to
  the initial commit, following the leftmost ancestor (i.e. number of
  revisions in a centralized workflow, and less than this otherwise).
  That said, the constant factor is very small. For example, on
  bzr.dev, I did "grep -n some-rev-id" (which does revid-to-revno), it
  takes 0.004 seconds (Vs 0.003 seconds to grep in /dev/null
  instead ;-) ), so you'd need many orders of magnitude before this
  becomes a limitation.

  Linus's point AIUI is that this will _never_ be a limitation of git.

* Then, do the "merge" to make your tree up to date. You can hardly do
  faster than git and its unpacked format, but this is at the cost of
  disk space. But as you say, in almost any modern VCS, that's
  O(diff). In a space-efficient format, that's just the tradeoff you
  make between full copies of a file and delta-compression.

-- 
Matthieu
-
To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html