I obtained the following by running `darcs optimize enable-patch-index`
on a local mirror of http://darcs.net .

With darcs built with optimizations (ie normally):

https://dl.dropboxusercontent.com/u/6239815/patchindex_creation_optimized.pdf

Without optimizations (the command terminates with a stack overflow,
which made me discover the problem):

https://dl.dropboxusercontent.com/u/6239815/patchindex_creation_not_optimized.pdf

To generate these files, compile darcs with profiling enabled, then
delete _darcs/patch_index , then run `darcs optimize enable-patch-index
 +RTS -xt -hy`, then `hp2ps -c darcs.hp && ps2pdf darcs.ps && evince
darcs.pdf` .

It would be nice to see where the main memory consumption comes from,
and reduce it.

I used ghc 7.6.3 to obtain the above data and I've been told that 7.8
was nicer with regards to stack overflows. Anyway memory consumption
would remain high.

More data:

https://dl.dropboxusercontent.com/u/6239815/patchindex_creation_optimized_hm.pdf

The simplest way to check memory usage is to compile darcs with the flag
rts:   cabal install -frts

Then run with darcs optimize enable-patch-index +RTS -hT

And look into the generated memory report: hp2ps -c darcs.hp && ps2pdf
darcs.ps && evince darcs.pdf

Or generate runtime statistics with +RTS -s .

I've been playing around with this a bit, informed by some of the things Guillaume 
discovered.

Broadly it seems that the problem is that the entire list of [(PatchId, [PatchMod 
FileName])] is being constructed and then used to build the PatchIndex, rather than 
being produced and consumed incrementally.

I think that the list of patches from the repository is itself parsed lazily (otherwise 
all darcs commands that operate on PatchSet would read the entire set into memory), so 
the problem must be coming from the patch index code itself.

I can see a few potential reasons:
 - the set of FileNames that patches2PatchMods passes around and the related use of 
mapAccumL, which may be introducing an unintentional dependency on calculating the 
entire output list before producing any results
 - the two uses of pmods in createPatchIndexFrom (pids and mods) which may mean it's 
kept in memory for the second use until the first one is done
 - the nubSeq in applyPatchMods and the way the state monad is used - these *should* be 
incremental in themselves, but it makes it a bit hard to untangle the logic

Logically, it should always be possible to build the patch index up one patch at a time 
- otherwise updatePatchIndex wouldn't work properly. However the code isn't quite 
structured that way, so I'd like to simplify it to bring us closer to that point.

Another way of improving memory usage substantially might be to make sure that the 
strings and bytestrings in the list are all shared with each other via hash-
consing/interning. For example lots of filenames must be repeated a lot. However this 
seems like a bit fiddly to implement (you need to manage a cache) and might interfere 
with laziness.

I'm going to accept a series of patches by Ganesh and me that solve the
memory leak, so this issue will be fixed.

This does not guarantee that it will be activated by default in 2.10
since it uses up time to build anyway, but I'll open another ticket for
that topic.