[darcs-users] more naive thoughts of improving conflict resolution performance

[Mark Stosberg]

I hope these comments add value, considering my lack of understanding of
the conflict resolution code.

It's my understanding that conflicts are slow because there are an
exponential number of cases to review to confirm that there does in fact
have to be a conflict.

I assume this number of cases to review can be computed or approximated
fairly easy in advance. 

However, what the conflict will look like if it does happen can be known
in advance: It's the overlapping parts of a particular patch and the
repo it's attempting to be applied against. 

My central idea is: What if we removed criteria that we had to
absolutely confirm that a conflict couldn't be avoided, and settled for
a high probability that it couldn't be avoided? 

My reasoning is that I'd rather spend a few minutes resolving 'fake'
conflicts by hand once a while, than face hours of waiting for an
obvious conclusion: There's going to be a conflict. 

If I'm not totally off base, it seems we could take a cue from spam
fighting software like SpamAssassian. 

It includes the notion that "this message has a 55% probability of
of being spam. That's over our threshold, so it gets marked as spam'

Likewise with darcs, I think we ought to be able to say 'I've tried 55%
of the possible conflict resolution cases, and I'm going to give up and
call it a conflict'. 

Again, I think a couple other bits of the spam fighting software could
make sense here: 

 - darcs can collect stats about how many cases need to be reviewed, on
   average, to determine if there is a conflict. 

 - The threshold for what is a conflict can be tunable per repository,
   and can possibly be self-adjusting based on the stats collected. 

This could enable logic like: "On average this repo has to look at less
than 10% of possibilities to determine there is a conflict. So we're
going to give up now after looking at 35%". 

    Mark

-- 
http://mark.stosberg.com/