Hi Stefan, hi devs,
the revision graph as implemented on /trunk has a few
issues with mid- and large-sized repositories.
* analysis phase takes super-quadratic time
(i.e. worse than O(revNum^2))
* memory consumption becomes an issue with
large repositories (~1GB RAM per 100.000 revs)
* complex changes (e.g. renaming the project root
folder) result in graphs that are hard to read
For the repository at my office (37k revisions, >100
tags, >100 branches, most of them already closed),
the /trunk code takes 6 minutes to build the graph
while eating about 300 megs RAM.
Since I hear quite a few similar complaints from my
colleagues, I wondered if I could do better ;) This is
what I did on /branches/RevisionGraphRewrite:
* Use the log caching data structures to represent
the data (if l.c. is disabled, collect the data in a
temporary container). This will simplify and speed
up path operations while reducing memory consumption.
* Use a breadth search algorithm to scan the thistory
(i.e. follow all open branches simultaneously).
Organize the search paths in a tree, so unaffected
sub-trees (e.g. "tags" for most revisions) can be
skipped efficiently. This brings the runtime down
to an almost linear O (N log N).
* Use a simplified placing of the graph nodes.
At least for TSVN and for my office repository,
it results in "nice" graphs. However, there is
plenty of space for improvement without hurting
performance. As a result, no complex routing
for the graph's edges is necessary.
* Simplify the algorithm that draws connections.
Plain curved lines (Bezier splines) are in most
cases well to tell apart and if they should cross
a node box, the latter will still be readable.
If a denser node placement is defined in future,
we may of course add a more sophisticated
routing scheme.
For the office repository, the graph shows up in
less than a second, taking only 30 MB of RAM.
(even if showing all changes = 37k nodes).
Could you have a look at the result (and try the
options buttons)? I would love to merge that
into /trunk and then continue with the log caching /
merge tracking / documentation stuff.
-- Stefan^2.
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@tortoisesvn.tigris.org
For additional commands, e-mail: dev-help@tortoisesvn.tigris.org
Received on Sun Jul 8 00:46:36 2007