Re: [PATCH][libsvn_wc] Issue 2607: Post-commit working copy processing exhibits O(n^2) behaviour

On 9/20/06, Malcolm Rowe <malcolm-svn-dev@farside.org.uk> wrote:
> On Tue, Sep 19, 2006 at 10:29:11PM +0200, Erik Huelsmann wrote:
> > >Are there any situations in which the fact that we're processing commit
> > >items out of order would make a difference?
> >
> > Well, I sent the patch to zhakov and included a list of failing tests.
> > I thought that they were caused by out-of-order processing, but I've
> > added code to sort the adm's back into queue order before running
> > their logs.
> >
>
> Oh, I didn't realise we were getting failures. Okay. (We should probably
> ditch the sorting code if it turns out not to make a difference.)

Well, the failures should be gone with the attached patch. I also
ditched the sorting code, because the failures weren't caused by
out-of-order-processing.

In another mail in this thread you said:

"Are there any situations in which the fact that we're processing commit
items out of order would make a difference? The only ones I can think
of would involve overlapping items (i.e. a parent with RECURSE set as
one item, a child entry as another item). I'm not sure whether this is
even a valid scenario, and if it is, I'm not sure that it matters."

Yup. That's why this version explicitly checks and eliminates
overlapping items in case of recursive processing.

> I reduced the failing svnlook test case to the attached reproduction
> recipe. Unfortunately, I got lost in the maze of log files (which I'm
> not very familiar with), so I don't think I'm going to get very far
> debugging this.

Well, we talked on IRC already, the log files were a big help!

Here's the new log message:

[[[
Resolve issue 2607: post-commit processing exhibits O(n^2) behavior.

* subversion/include/svn_wc.h
* subversion/libsvn_wc/adm_ops.c
  (svn_wc_committed_queue_t): New type for commit item queues.
  (svn_wc_queue_committed): New. Adds a new item to the committed items
   queue. Optionally does required initialization.
  (svn_wc_process_committed_queue): New. Processes (with O(n) behavior)
   the queue of committed items, running all log files (which causes
   the entries file to be rewritten) as a last step.

* subversion/libsvn_wc/adm_ops.c
  (process_committed_internal): New. Abstracted out of
   svn_wc_process_committed4 to serve as a base for
   svn_wc_process_committed_queue too. Changed to account for the fact
   that the base log number may not start at 0 anymore.
  (committed_queue_item_t): New. Structure to store parameters for each
   committed item.
  (affected_adm_t): New. Structure to do some book-keeping
   for the affected adm areas.
  (have_recursive_parent): New. Used to determine whether a path
   will already have been processed, because one of its parents
   was processed recursively.
  (svn_wc_process_committed4): Rewrite in terms of
   process_committed_internal.

* subversion/libsvn_client/commit.c
  (have_processed_parent): Remove. Now obsolete.
  (svn_client_commit4): Adapted to use the new queued post-commit
   processing functions. Because we process all logs after queueing
   the items, there are fewer cases of SVN_ERR_WC_NOT_LOCKED to
   catch. Same thing for deleted items: the entry-existance check
   is no longer relevant: when we check for existance it'll still exist.
]]]

And the patch is attached. More comments?

Thanks in advance!

bye,

Erik.

---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org