brisbane:CHKMap.iteritems() tweaks

[John Arbash Meinel]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

I think I've gotten the fixes I wanted for CHKMap.iteritems(). It is
available at:

http://bzr.arbash-meinel.com/branches/bzr/brisbane/iter_changes_fixes

However, it doesn't end up improving things as much as I thought it
would. Under lsprof, the above branch shaves 9s out of 16s from the
LeafNode.iteritems() call. Which is what I wanted. Unfortunately, that
turns out to only be 5.0s => 4.4s without lsprof. I don't particularly
know *why* lsprof is penalizing the double iteration so heavily.

With and without my changes the time spent it InternalNode._iter_nodes()
stays relatively fixed at 4.4s, which happens to coincide with the
wall-clock time without lsprof. And that time breaks down into
"get_record_stream()" and "get_bytes_as()".

get_record_stream() time (1.45s) is evenly split between
get_build_details (0.8s paging in stuff from .cix), and _get_block (0.59s).

There are 397 calls to _get_block, which triggers 304 calls to
get_raw_records. (And 723 objects are actually returned by
get_record_stream.)

Of the time spent in 720 calls to get_bytes_as (2.37s), it all seems to
be zlib.decompress time (2.2s).

Now, I don't quite understand why we are reading 720 pages. I would have
though 512 would be the exact number. (1 root and 255 leaves for both
the maps). Though perhaps the parent_id,basename map is split out
differently. I know it has a depth of 4, which means we have at least
one extra split in there.

Anyway, it still looks like those 720 pages are spread across about 310
real groupcompress blocks, which seems pretty sub-optimal.

I have a couple thoughts, though:

1) Change 'bzr pack' so that it creates a separate set of groups for
items that are available in the newest XX (say 100) revisions. Or
possibly group everything into 100 rev chunks.

2) Split up the chk streams a bit more. Right now we create a new group
at every 'level', and order things by the prefix used to reach them.
Which clusters similar pages together, giving good compression.

I think what is happening is that the leaf node for "a" is expanded
right up at the beginning of the group, but then all the old revisions
for "a" follow it, pushing "b" to the middle of the group, and "c" just
at the very end. Which then overflows into the next group. So the "d"
page that you want doesn't even start at the beginning, etc.

As such, you need to decompress a good portion of all 300 pages that
everything lands on.

We can fit ~300 uncompressed chk pages per group. So if we ordered them
purely by revision, I would expect the first 255 records to be pure
insertion (as there is very little overlap), and then you'd get maybe
another 200 records that would compress very well. And then you'd start
a new group, and that cycle would repeat.

That would be you would get fairly poor compression, but only need to
read 1 block to get all the pages.

Alternatively, you could split the groups by exactly the prefix. Which
should end up giving you 720 groups that need to be read, but you would
only need to decompress the first few bytes of each group. You should
end up with approximately the same compression, since we are still
grouping the things that compress well together.

I know Robert didn't really like that I have the "get_record_stream()"
code creating multiple streams in order to signal the insert code how
things should be broken up. The issue I see is that the alternative is
having insert deserialise a second time, and possibly buffer to get
better insertion performance.

I suppose we might be able to try a couple different things. And
regardless, the attached patch does make things a little bit faster, and
will help even when we get pages faster to decode.

John
=:->
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.9 (Cygwin)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iEYEARECAAYFAknIMPYACgkQJdeBCYSNAAOU0wCeJu/AwJ2LdWSIlsLUxM0ns5TM
jz8An2nsPZ5H7G2QI7K83UIhMHWJzB4z
=Cwqe
-----END PGP SIGNATURE-----
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: iteritems.patch
Url: https://lists.ubuntu.com/archives/bazaar/attachments/20090323/431260d1/attachment-0001.diff