[darcs-devel] announcing darcs 2.0.0pre1, the first prerelease for darcs 2

Petr Rockai me at mornfall.net
Sat Dec 15 16:38:43 UTC 2007


David Roundy <droundy at darcs.net> writes:
> Okay, I've found a couple of really stupid bits of code, and this goes a
> lot faster now.  The "17" pull took under three seconds, and that's with
> profiling running.  Fortunately (and perhaps unsurprisingly) the issue was
> largely with the "easy" parts of the algorithm.  Well, one change (that
> gave a 50% drop in time used) was a patch sequence comparison where we
> didn't check first for the quick case in which the two sequences had
> different lengths.  The other change, which made a much bigger difference
> was being smarter when working out the possible sequences of
> non-conflicting patches that led to a conflict.  In my defense, this code
> was written just a few weeks before the prerelease darcs 2, while I was
> working on a grant proposal...
Yes, it is a good thing to first get it correct (i.e. premature
optimisation... we all know it).

> Anyhow, it'll be a couple of hours before tests are passed and changes are
> pushed, but then I'd appreciate it if you'd take another look at this! (I
> could do it myself but right now I think I need a break... and it's far
> easier to motivate myself to fix a problem pointed out by someone else than
> to look for said problem myself.)
Okey, I have pulled in your changes and re-ran the test:
35: 6.8s
36: 7.6s
37: 8.5s
38: 9.4s
39: 10.3s
40: 11.4s
41: 12.6s
42: 14.2s
...
55: 44s
56: 55s
57: 53s

(Okey, towards the end, this probably got a little skewed by other
stuff running on the box.)

I will have to think a little to see what kind of function this is,
asymptotically. It grows faster than both n^2 and n^3 and apparently
slower than 2^n. I may have made a mistake somewhere.

So with the changes, it is again a *lot* better, with the 10s depth
going from 15 to 38 or so. Thanks for the improvement!

(I have been thinking about the "ultimate" solution since I got up
today; if I ever reach a state where I no more see "why it won't
work", I will mail the list...)

-- 
Peter Rockai | me()mornfall!net | prockai()redhat!com
 http://blog.mornfall.net | http://web.mornfall.net

"In My Egotistical Opinion, most people's C programs should be
 indented six feet downward and covered with dirt."
     -- Blair P. Houghton on the subject of C program indentation


More information about the darcs-devel mailing list