[svn.haxx.se] · SVN Dev · SVN Users · SVN Org · TSVN Dev · TSVN Users · Subclipse Dev · Subclipse Users · this month's index

Re: [PATCH] Skip-deltas, for review

From: William Uther <will+_at_cs.cmu.edu>
Date: 2002-07-27 05:13:58 CEST

On 26/7/02 10:23 PM, "Glenn A. Thompson" <gthompson@cdr.net> wrote:

>> I don't think this is about extra time for analysis, it's about _less_
>> time for commits. That's pretty important, IMHO.
>> What I'd suggest: Instead of doing this redeltification synchronously as
>> part of the commit, why not add support for this in svnadmin, and call
>> that asynchronously from a post-commit hook? We really don't care when
>> the redeltification takes place, as long as it happens before the change
>> is 5000 revisions old.
>> -
> Thats kind of what I was thinking. Why do this every commit. Why not do it
> when "the repos seems to be getting slow don't you think?" statements start
> popping up.

I prefer the concept of having the repos be self-maintaining. I don't want
to have to run svnadmin on my repos when it gets large, I want it to just

Of course if commits becomes really slow then it could be made an option,
but I'd trade the small slowdown for the easier maintenance. Remember that
the average slowdown in commit speed is O(log(log(N)) - we do log N
re-deltifications every log N steps. That's REALLY small.

One strange thing: I though skip-lists would cost more in terms of space. I
was thinking about a factor of 2 (hmm - or should that be N logN?). Any
thoughts on why you aren't seeing this?

For those looking for a diagram, see

BTW: One code strangeness. When I read the code, in txn_deltify(), I was
expecting something like:

  /* Redeltify the desired number of predecessors. */
  count = 0;
  fs = svn_fs__dag_get_fs (node);
  for (lev = 0; lev < nlevels; lev++)
      prevnode = node;
      while (count < (1 << lev))
          const svn_fs_id_t *pred_id;

          SVN_ERR (svn_fs__dag_get_predecessor_id (&pred_id, prednode,
          if (pred_id == NULL)
            return svn_error_create (SVN_ERR_FS_CORRUPT, 0, 0, trail->pool,
                                     "faulty predecessor count");
          SVN_ERR (svn_fs__dag_get_node (&prednode, fs, pred_id, trail));
      SVN_ERR (svn_fs__dag_deltify (prednode, node, props_only, trail));

Note that I've moved the "prevnode = node" inside the outer loop. This
means you re-deltify every 2^Nth revision rather than every 2^(N+1)-1th
revision. The difference is small. I was just wondering if it was

2^N: 1 2 4 8 16 32
2^(N+1)-1: 1 3 7 15 31 63

\x/ill :-}

To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org
Received on Sat Jul 27 05:14:59 2002

This is an archived mail posted to the Subversion Dev mailing list.

This site is subject to the Apache Privacy Policy and the Apache Public Forum Archive Policy.