[MERGE] Simple fix for "bzr log file"
John Arbash Meinel
john at arbash-meinel.com
Thu Sep 18 22:56:56 BST 2008
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
There are better fixes possible, but this is my first go at cleaning up the
memory consumption for "bzr log file".
Basically, we create the per-file graph, and the whole-tree graph. And then
for each node in the whole-tree, we track what per-file ancestry we have.
That way we can determine which nodes have merged a given file change. We can
ultimately do it in a better way, but this change is incrementally better than
what we have.
Basically, the old code would *always* create a new set() whenever you have a
revision with more than 1 parent. The new code only creates a new set() if the
parents are actually different for that file.
This drops memory consumption for the mysql file from
large-enough-that-it-swaps-and-I-have-to-kill it, to only 400MB.
There is a very simple change, which can drop the memory consumption down to
about 277MB, by caching tuples instead of frozensets. But it means we have to
recompute the sets later on.
Analysis of memory consumption as it stands:
Basically, if a file has N revisions, we end up with ~N sets. And for these
sets, they are of size 1, 2, 3, ... N. So with N revisions we use memory on
the order of N(N+1)/2, aka N^2. set() objects make this worse because to avoid
hash collisions, they try to keep their objects either 1/2 empty, or 1/4 empty
(I don't remember off-hand).
So we can use tuples() which at least efficiently pack their memory. We still
scale very poorly when N is large.
The best thing I can think of to fix it, is to use information from
'merge_sort'. Basically, when "merge_depth" decreases we know that we need to
include that node.
I chose to go with the "fast" frozenset() logic over the "memory-efficient"
tuple logic, but we can change our minds in the future.
John
=:->
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.6 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org
iD8DBQFI0s6oJdeBCYSNAAMRAiFoAKCT0tItBKIdBHgJtgL4XewRxgIYTwCgx7nw
NHBVyH1oIBhNB2KOi7gJXcU=
=FKSn
-----END PGP SIGNATURE-----
-------------- next part --------------
A non-text attachment was scrubbed...
Name: lighter_file_log.patch
Type: text/x-diff
Size: 20500 bytes
Desc: not available
Url : https://lists.ubuntu.com/archives/bazaar/attachments/20080918/b4d04f81/attachment-0001.bin
More information about the bazaar
mailing list