Issue 1106 make darcs record, etc. O(1) in time (is now O(n) wrt num patches)

Title make darcs record, etc. O(1) in time (is now O(n) wrt num patches)
Priority feature Status resolved
Milestone Resolved in
Superseder Nosy List darcs-devel, dmitry.kurochkin, kowey, mornfall, simonmar, thorkilnaur
Assigned To mornfall
Topics Hashed, Performance

Created on 2008-09-27.12:28:51 by droundy, last changed 2010-05-08.15:45:11 by mornfall.

msg6146 (view) Author: droundy Date: 2008-09-27.12:28:47
It would be nice to make darcs record (and pull, and apply) take O(1) time,
rather than being O(N) in the number of patches in the repository.  The problem
is that when we write out the new the hashed inventory,  we have to hash all the
 older inventories, even though we haven't modified them.  If we simply cache
the hash of each inventory as we read it (in the PatchSet), and remove the hash
if we modify it, then we can make writing out  the new hashed inventory O(1)...
well, actually, O(number of patches since last tag).

On my fast computers, this doesn't seem like a big issue, but when running darcs
on the darcs repository, it takes a few seconds to write the inventories, so
it's well worth fixing--it'll only be worse on a repository with a long history.

This  is unfortunately quite an invasive change, since it has to change the type
of PatchSet p, which is currently just RL (RL PatchInfoAnd p).  As an example,
you could look at PatchInfoAnd, which caches the hash of each patch in the same
way that we'd like to cache the hash of each tag inventory.

I imagine something like

data PatchSet p C(z) where
   PatchSet :: Maybe String -> RL (PatchInfoAnd p) C(y z)
            -> PatchSet p C(y) -> PatchSet p C(z)

The tricky part will be writing a safe  interface, so that we can't accidentally
modify a PatchSet without setting its hash value to Nothing, but that is
sufficiently expressive that it will be practical to convert the entire code to
use it.  For read-only purposes, of course, and as a transition, we can easily
write converters to and from RL (RL (PatchInfoAnd p)), which perhaps will allow
a gradual conversion, with unfixed code just running more slowly (at its current

msg9818 (view) Author: kowey Date: 2010-01-14.09:55:08
Is this what David's NewSet work is all about?
msg10038 (view) Author: kowey Date: 2010-02-19.16:46:14
I think Petr has claimed this one for the 2010-03 sprint
Date User Action Args
2008-09-27 12:28:51droundycreate
2008-09-27 13:08:45dmitry.kurochkinsetnosy: + dmitry.kurochkin
2008-11-03 22:10:47koweysettopic: + Performance
nosy: + thorkilnaur
2009-08-06 18:00:38adminsetnosy: + markstos, jast, Serware, darcs-devel, zooko, mornfall, tommy, beschmi, - droundy
2009-08-06 21:12:59adminsetnosy: - beschmi
2009-08-10 21:49:16adminsetnosy: - tommy, markstos, darcs-devel, zooko, jast, Serware, mornfall
2009-08-10 23:46:45adminsetnosy: - dagit
2009-08-12 14:54:23koweysetstatus: needs-reproduction -> needs-implementation
nosy: kowey, simon, thorkilnaur, dmitry.kurochkin
2009-08-25 17:25:49adminsetnosy: + darcs-devel, - simon
2009-08-26 13:21:43koweysettopic: - Confirmed
nosy: kowey, darcs-devel, thorkilnaur, dmitry.kurochkin
2009-08-27 14:32:54adminsetnosy: kowey, darcs-devel, thorkilnaur, dmitry.kurochkin
2010-01-14 09:55:10koweysetnosy: + mornfall
messages: + msg9818
2010-01-14 09:58:34koweylinkissue1729 superseder
2010-01-14 09:59:02koweysettopic: + Hashed
nosy: + simonmar
title: make darcs record, etc. O(1) in time -> make darcs record, etc. O(1) in time (is now O(n) wrt num patches)
2010-02-19 16:46:16koweysetassignedto: mornfall
messages: + msg10038
2010-02-19 16:47:39koweylinkissue1589 superseder
2010-03-21 11:29:30koweylinkpatch196 issues
2010-05-08 15:45:11mornfallsetstatus: needs-implementation -> resolved