[darcs-users] Memory usage of Record

Jason Dagit dagit at codersbase.com
Sun Aug 30 03:14:26 UTC 2009


Recently I noticed that if you take a large code base and try to
import it into darcs that the performance is pretty dismal.  I was
thinking this was once optimized and perhaps it required a special
case like --all or something.  Regardless of whether it worked in the
past or not I thought I'd take a look.  I had some time to investigate
today and I'd like to share my findings.

I followed the profiling tips in chapter 25 of Real-World Haskell:

I mention it because the advice there lead me to observations I didn't
make in the past when profiling similar parts of darcs.

My setup worked like this:
0) build darcs for profiling as darcs-prof
1) Get a copy of the linux source tree (takes up 382MB of disk space)
2) darcs init; darcs add --recursive *
3) echo q | darcs-prof +RTS -p -hc -sstderr -RTS record -m "import" 2>
4) hp2ps -c darcs-prof.hp
5) examine the various artifacts created by the profiler

The main discovery I made today was that we're sucking the whole linux
tree into memory and holding it there.  This creates so much pressure
on the garbage collector that darcs spends only 30% of the time doing
real work.  In a way, this is a strictness issue so I played with the
strictness annotations used in the code.  In particular, the Prim data
type is defined like this:
data Prim C(x y) where
    Move :: !FileName -> !FileName -> Prim C(x y)
    DP :: !FileName -> !(DirPatchType C(x y)) -> Prim C(x y)
    FP :: !FileName -> !(FilePatchType C(x y)) -> Prim C(x y)
    Split :: FL Prim C(x y) -> Prim C(x y)
    Identity :: Prim C(x x)
    ChangePref :: !String -> !String -> !String -> Prim C(x y)

data FilePatchType C(x y) = RmFile | AddFile
                          | Hunk !Int [B.ByteString] [B.ByteString]
                          | TokReplace !String !String !String
                          | Binary B.ByteString B.ByteString
                            deriving (Eq,Ord)

By removing just the bangs, the profiler says that darcs is now doing
work 40% of the time.  That's a 10% increase.

Does anyone remember why the bangs are in the prim type?  I don't want
to remove them if it will bring back bugs.  David, perhaps you recall
why they are there?

I have a feeling that a better strategy would be to use
Control.Parallel.Strategies.rnf and create an instance of NFData for
Prim.  This would allow us finer granularity of control over when we
have a strict Prim and when we have a lazy Prim by applying rnf as

Next I started poking around in pending.  I noticed that in the
pending we don't store diffs, just the list of directories and files
to add.  So then I disabled the construction of diffs during record
that happens when an addfile is in pending.  This resulted in a darcs
needing less than 50 megs of ram (it needed about 500 megs to hold the
linux source in memory).  Of course that would be a buggy version of
darcs, but the test shows that the real space problem comes from
eagerly loading all the hunk patches into memory.

I'm not sure where to go next with this information.  One idea I had,
was to not calculate/create hunk patches until they are absolutely
needed.  For example, I don't think the hunk patches are needed until
we display them on the screen or write them to files.  Although, this
doesn't fix the case of what to do with the data once the user has
viewed it but before they have agreed to all the patches in the list.

Does anyone else have suggestions?  Does anyone know if Petr's work
will make a difference here?  I heard rumors of a darcs-hs that uses
hashed-storage more aggressively.  But, I doubt it impacts the reading
of pending?

I also noticed that we do some redundant string processing on file
paths.  readPrim reads "OldFashioned" paths out of pending which costs
us a non-trivial bit of processing when there are many files involved.


More information about the darcs-users mailing list