From: Junio C Hamano <hidden> Date: 2016-06-15 22:57:55
Vicent Martí [off-list ref] writes:
quoted
quoted
+ There is a bitmap for each Git object type, stored in the following
+ order:
+
+ - Commits
+ - Trees
+ - Blobs
+ - Tags
+
+ In each bitmap, the `n`th bit is set to true if the `n`th object
+ in the packfile index is of that type.
+
+ The obvious consequence is that the XOR of all 4 bitmaps will result
+ in a full set (all bits sets), and the AND of all 4 bitmaps will
+ result in an empty bitmap (no bits set).
Instead of XOR did you mean OR here?
Nope, I think XOR makes it more obvious: if the same bit is set on two
bitmaps, it would be cleared when XORed together, and hence all the
bits wouldn't be set. An OR would hide this case.
What case are you talking about?
The n-th object must be one of these four types and can never be of
more than one type at the same time, so a natural expectation from
the reader is "If you OR them together, you will get the same set".
If you say "If you XOR them", that forces the reader to wonder when
these bitmaps ever can overlap at the same bit position.
To sum it up: I'd like to see this format be strictly in Network Byte
Order,
Good.
I've been wondering what you meant by "cannot be mmap-ed" from the
very beginning. We mmapped the index for a long time, and it is
defined in terms of network byte order. Of course, pack .idx files
are in network byte order, too, and we mmap them without problems.
It seems that it primarily came from your fear that using network
byte order may be unnecessarily hard to perform well, and it would
be a good thing to do to try to do so first instead of punting from
the beginning.
and I'm going to try to make it run fast enough in that
encoding.
Hmph. Is it an option to start from what JGit does, so that people
can use both JGit and your code on the same repository? And then if
you do not succeed, after trying to optimize in-core processing
using that on-disk format to make it fast enough, start thinking
about tweaking the on-disk format?
Thanks.
On Tue, Jun 25, 2013 at 11:17 PM, Junio C Hamano [off-list ref] wrote:
What case are you talking about?
The n-th object must be one of these four types and can never be of
more than one type at the same time, so a natural expectation from
the reader is "If you OR them together, you will get the same set".
If you say "If you XOR them", that forces the reader to wonder when
these bitmaps ever can overlap at the same bit position.
I guess this is just wording. I don't particularly care about the
distinction, but I'll change it to OR.
quoted
To sum it up: I'd like to see this format be strictly in Network Byte
Order,
Good.
I've been wondering what you meant by "cannot be mmap-ed" from the
very beginning. We mmapped the index for a long time, and it is
defined in terms of network byte order. Of course, pack .idx files
are in network byte order, too, and we mmap them without problems.
It seems that it primarily came from your fear that using network
byte order may be unnecessarily hard to perform well, and it would
be a good thing to do to try to do so first instead of punting from
the beginning.
It cannot be mmapped not particularly because of endianness issues,
but because the original format is not indexed and requires a full
parse of the whole index before it can be accessed programatically.
The wrong endianness just increases the parse time.
quoted
and I'm going to try to make it run fast enough in that
encoding.
Hmph. Is it an option to start from what JGit does, so that people
can use both JGit and your code on the same repository? And then if
you do not succeed, after trying to optimize in-core processing
using that on-disk format to make it fast enough, start thinking
about tweaking the on-disk format?
I'm afraid this is not an option. I have an old patchset that
implements JGit v1 bitmap loading (and in fact that's how I initially
developed these series -- by loading the bitmaps from JGit for
debugging), but I discarded it because it simply doesn't pan out in
production. ~3 seconds time to spawn `upload-pack` is not an option
for us. I did not develop a tweaked on-disk format out of boredom.
I could dig up the patch if you're particularly interested in
backwards compatibility, but since it was several times slower than
the current iteration, I have no interest (time, actually) to maintain
it, brush it up, and so on. I have already offered myself to port the
v2 format to JGit as soon as it's settled. It sounds like a better
investment of all our times.
Following up on Shawn's comments, I removed the little-endian support
from the on-disk format and implemented lazy loading of the bitmaps to
make up for it. The result is decent (slowed down from 250ms to 300ms)
and it lets us keep the whole format as NWO on disk. I think it's a
good tradeback.
The relevant commits are available on my fork of Git (I'll be sending
v2 of the patchset once I finish tackling the other reviews):
https://github.com/vmg/git/commit/d6cdd4329a547580bbc0143764c726c48b887271https://github.com/vmg/git/commit/d8ec342fee87425e05c0db1e1630db8424612c71
As it stands right now, the only two changes from v1 of the on-disk format are:
- There is an index at the end. This is a good idea.
- The bitmaps are sorted in packfile-index order, not in packfile
order. This is a good idea.
As always, all your feedback is appreciated, but please keep in mind I
have strict performance concerns.
German kisses,
vmg
On Tue, Jun 25, 2013 at 4:08 PM, Vicent Martí [off-list ref] wrote:
On Tue, Jun 25, 2013 at 11:17 PM, Junio C Hamano [off-list ref] wrote:
quoted
What case are you talking about?
The n-th object must be one of these four types and can never be of
more than one type at the same time, so a natural expectation from
the reader is "If you OR them together, you will get the same set".
If you say "If you XOR them", that forces the reader to wonder when
these bitmaps ever can overlap at the same bit position.
I guess this is just wording. I don't particularly care about the
distinction, but I'll change it to OR.
Hmm, OK. If you think XOR and OR are the same operation, I also have a
bridge to sell you. Its in Brooklyn. Its a great value.
The correct operation is OR. Not XOR. OR. Drop the X.
It cannot be mmapped not particularly because of endianness issues,
but because the original format is not indexed and requires a full
parse of the whole index before it can be accessed programatically.
The wrong endianness just increases the parse time.
Wrong endianness has nothing to do with the parse time. Modern CPUs
can flip a word around very quickly. In JGit we chose to parse the
file at load time because its simpler than having an additional index
segment, and we do what you did which is to toss the object SHA-1s
into a hashtable for fast lookup. By the time we look for the SHA-1s
and toss them into a hashtable we can stride through the file and find
the bitmap regions. Simple.
In other words, the least complex solution possible that still
provides good performance. I'd say we have pretty good performance.
quoted
quoted
and I'm going to try to make it run fast enough in that
encoding.
Hmph. Is it an option to start from what JGit does, so that people
can use both JGit and your code on the same repository?
I'm afraid I agree here with Junio. The JGit format is already
shipping in JGit 3.0, Gerrit Code Review 2.6, and in heavy production
use for almost a year on android.googlesource.com, and Google's own
internal Git trees.
I would prefer to see a series adding bitmap support to C Git start
with the existing format, make it run, taking advantage of the
optimizations JGit uses (many of which you ignored and tried to "fix"
in other ways), and then look at improving the file format itself if
load time is still the largest low hanging fruit in upload-pack. I'm
guessing its not. You futzed around with the object table, but JGit
sped itself up considerably by simply not using the object table when
the bitmap is used. I think there are several such optimizations you
missed in your rush to redefine the file format.
quoted
And then if
you do not succeed, after trying to optimize in-core processing
using that on-disk format to make it fast enough, start thinking
about tweaking the on-disk format?
I'm afraid this is not an option. I have an old patchset that
implements JGit v1 bitmap loading (and in fact that's how I initially
developed these series -- by loading the bitmaps from JGit for
debugging), but I discarded it because it simply doesn't pan out in
production. ~3 seconds time to spawn `upload-pack` is not an option
for us. I did not develop a tweaked on-disk format out of boredom.
I think your code or experiments are bogus. Even on our systems with
JGit a cold start for the Linux kernel doesn't take 3s. And this is
JGit where Java is slow because "Jesus it has a lot of factories", and
without mmap'ing the file into the server's address space. Hell the
file has to come over the network from a remote disk array.
I could dig up the patch if you're particularly interested in
backwards compatibility, but since it was several times slower than
the current iteration, I have no interest (time, actually) to maintain
it, brush it up, and so on. I have already offered myself to port the
v2 format to JGit as soon as it's settled. It sounds like a better
investment of all our times.
Actually, I think the format you propose here is inferior to the JGit
format. In particular the idx-ordering means the EWAH code is useless.
You might as well not use the EWAH format and just store 2.6M bits per
commit. The idx-ordering also makes *much* harder to emit a pack file
a reasonable order for the client. Colby and I tried idx-ordering and
discarded it when it didn't perform as well as the pack-ordering that
JGit uses.
Following up on Shawn's comments, I removed the little-endian support
from the on-disk format and implemented lazy loading of the bitmaps to
make up for it. The result is decent (slowed down from 250ms to 300ms)
and it lets us keep the whole format as NWO on disk. I think it's a
good tradeback.
The maintenance burden of two endian formats in a single file is too
high to justify. I'm glad to see you saw that.
As it stands right now, the only two changes from v1 of the on-disk format are:
- There is an index at the end. This is a good idea.
I don't think the index is necessary if you plan to build a hashtable
at runtime anyway. If you mmap the file you can quickly skip over a
bitmap and find the next SHA-1 using this thing called "pointer
arithmetic". I am not sure if you are familiar with the term, perhaps
you could search the web for it.
- The bitmaps are sorted in packfile-index order, not in packfile
order. This is a good idea.
As Colby and I have repeatedly tried to explain, this is not a good idea.
German kisses,
Strawberry and now German kisses? What's next, Mango kisses?
That was a very rude reply. :(
Please refrain from interacting with me in the ML in the future. I'l
do accordingly.
Thanks!
vmg
On Thu, Jun 27, 2013 at 3:11 AM, Shawn Pearce [off-list ref] wrote:
On Tue, Jun 25, 2013 at 4:08 PM, Vicent Martí [off-list ref] wrote:
quoted
On Tue, Jun 25, 2013 at 11:17 PM, Junio C Hamano [off-list ref] wrote:
quoted
What case are you talking about?
The n-th object must be one of these four types and can never be of
more than one type at the same time, so a natural expectation from
the reader is "If you OR them together, you will get the same set".
If you say "If you XOR them", that forces the reader to wonder when
these bitmaps ever can overlap at the same bit position.
I guess this is just wording. I don't particularly care about the
distinction, but I'll change it to OR.
Hmm, OK. If you think XOR and OR are the same operation, I also have a
bridge to sell you. Its in Brooklyn. Its a great value.
The correct operation is OR. Not XOR. OR. Drop the X.
quoted
It cannot be mmapped not particularly because of endianness issues,
but because the original format is not indexed and requires a full
parse of the whole index before it can be accessed programatically.
The wrong endianness just increases the parse time.
Wrong endianness has nothing to do with the parse time. Modern CPUs
can flip a word around very quickly. In JGit we chose to parse the
file at load time because its simpler than having an additional index
segment, and we do what you did which is to toss the object SHA-1s
into a hashtable for fast lookup. By the time we look for the SHA-1s
and toss them into a hashtable we can stride through the file and find
the bitmap regions. Simple.
In other words, the least complex solution possible that still
provides good performance. I'd say we have pretty good performance.
quoted
quoted
quoted
and I'm going to try to make it run fast enough in that
encoding.
Hmph. Is it an option to start from what JGit does, so that people
can use both JGit and your code on the same repository?
I'm afraid I agree here with Junio. The JGit format is already
shipping in JGit 3.0, Gerrit Code Review 2.6, and in heavy production
use for almost a year on android.googlesource.com, and Google's own
internal Git trees.
I would prefer to see a series adding bitmap support to C Git start
with the existing format, make it run, taking advantage of the
optimizations JGit uses (many of which you ignored and tried to "fix"
in other ways), and then look at improving the file format itself if
load time is still the largest low hanging fruit in upload-pack. I'm
guessing its not. You futzed around with the object table, but JGit
sped itself up considerably by simply not using the object table when
the bitmap is used. I think there are several such optimizations you
missed in your rush to redefine the file format.
quoted
quoted
And then if
you do not succeed, after trying to optimize in-core processing
using that on-disk format to make it fast enough, start thinking
about tweaking the on-disk format?
I'm afraid this is not an option. I have an old patchset that
implements JGit v1 bitmap loading (and in fact that's how I initially
developed these series -- by loading the bitmaps from JGit for
debugging), but I discarded it because it simply doesn't pan out in
production. ~3 seconds time to spawn `upload-pack` is not an option
for us. I did not develop a tweaked on-disk format out of boredom.
I think your code or experiments are bogus. Even on our systems with
JGit a cold start for the Linux kernel doesn't take 3s. And this is
JGit where Java is slow because "Jesus it has a lot of factories", and
without mmap'ing the file into the server's address space. Hell the
file has to come over the network from a remote disk array.
quoted
I could dig up the patch if you're particularly interested in
backwards compatibility, but since it was several times slower than
the current iteration, I have no interest (time, actually) to maintain
it, brush it up, and so on. I have already offered myself to port the
v2 format to JGit as soon as it's settled. It sounds like a better
investment of all our times.
Actually, I think the format you propose here is inferior to the JGit
format. In particular the idx-ordering means the EWAH code is useless.
You might as well not use the EWAH format and just store 2.6M bits per
commit. The idx-ordering also makes *much* harder to emit a pack file
a reasonable order for the client. Colby and I tried idx-ordering and
discarded it when it didn't perform as well as the pack-ordering that
JGit uses.
quoted
Following up on Shawn's comments, I removed the little-endian support
from the on-disk format and implemented lazy loading of the bitmaps to
make up for it. The result is decent (slowed down from 250ms to 300ms)
and it lets us keep the whole format as NWO on disk. I think it's a
good tradeback.
The maintenance burden of two endian formats in a single file is too
high to justify. I'm glad to see you saw that.
quoted
As it stands right now, the only two changes from v1 of the on-disk format are:
- There is an index at the end. This is a good idea.
I don't think the index is necessary if you plan to build a hashtable
at runtime anyway. If you mmap the file you can quickly skip over a
bitmap and find the next SHA-1 using this thing called "pointer
arithmetic". I am not sure if you are familiar with the term, perhaps
you could search the web for it.
quoted
- The bitmaps are sorted in packfile-index order, not in packfile
order. This is a good idea.
As Colby and I have repeatedly tried to explain, this is not a good idea.
quoted
German kisses,
Strawberry and now German kisses? What's next, Mango kisses?
From: Jeff King <hidden> Date: 2016-06-15 22:57:56
On Thu, Jun 27, 2013 at 04:36:54AM +0200, Vicent Martí wrote:
That was a very rude reply. :(
Please refrain from interacting with me in the ML in the future. I'l
do accordingly.
I agree that the pointer arithmetic thing may have been a little much,
but I think there are some points we need to address in Shawn's email.
In particular, it seems like the slowness we saw with the v1 bitmap
format is not what Shawn and Colby have experienced. So it's possible
that our test setup is bad or different. Or maybe the C v1 reading
implementation had some problems that are fixable. It's hard to say
because we haven't shown any code that can be timed and compared.
And the pack-order versus idx-order for the bitmaps is still up in the
air. Do we have numbers on the on-disk sizes of the resulting EWAHs? The
pack-order ones should be more amenable to run-length encoding,
especially as you get further down into history (the tip ones would
mostly be 1's, no matter how you order them).
-Peff
On Wed, Jun 26, 2013 at 7:45 PM, Jeff King [off-list ref] wrote:
In particular, it seems like the slowness we saw with the v1 bitmap
format is not what Shawn and Colby have experienced. So it's possible
that our test setup is bad or different. Or maybe the C v1 reading
implementation had some problems that are fixable. It's hard to say
because we haven't shown any code that can be timed and compared.
Right, the format and implementation in JGit can do "Counting objects"
in 87ms for the Linux kernel history. But I think we are comparing
apples to steaks here, Vincent is (rightfully) concerned about process
startup performance, whereas our timings were assuming the process was
already running.
It would help everyone to understand the issues involved if we are at
least looking at the same file format.
And the pack-order versus idx-order for the bitmaps is still up in the
air. Do we have numbers on the on-disk sizes of the resulting EWAHs?
I did not see any presented in this thread, and I am very interested
in this aspect of the series. The path hash cache should be taking
about 9.9M of disk space, but I recall reading the bitmap file is 8M.
I don't understand.
Colby and I were very concerned about the size of the EWAH compressed
bitmaps because we wanted hundreds of them for a large history like
the kernel, and we wanted to minimize the amount of memory consumed by
the bitmap index when loaded into the process.
In the JGit implementation our copy of Linus' tree has 3.1M objects,
an 81.5 MiB idx file, and a 3.8 MiB bitmap file. We were trying to
keep the overhead below 10% of the idx file, and I think we have
succeeded on that. With 3.1M objects the v2 bitmap proposed in this
thread needs at least 11.8M, or 14+% overhead just for the path hash
cache.
The path hash cache may still be required, Colby and I have been
debating the merits of having the data available for delta compression
vs. the increase in memory required to hold it.
The
pack-order ones should be more amenable to run-length encoding,
especially as you get further down into history (the tip ones would
mostly be 1's, no matter how you order them).
This is also true for the type bitmaps, but especially so in the JGit
file ordering where we always write all trees before any blobs. The
type bitmaps are very compact and basically amount to defining a
single range in the file. This takes only a few words in the EWAH
compressed format.
From: Jeff King <hidden> Date: 2016-06-15 22:57:56
On Thu, Jun 27, 2013 at 09:07:38AM -0700, Shawn O. Pearce wrote:
quoted
And the pack-order versus idx-order for the bitmaps is still up in the
air. Do we have numbers on the on-disk sizes of the resulting EWAHs?
I did not see any presented in this thread, and I am very interested
in this aspect of the series. The path hash cache should be taking
about 9.9M of disk space, but I recall reading the bitmap file is 8M.
I don't understand.
I don't know there the 8M number came from, or if it was on the kernel
repo. My bitmap-enabled pack of linux-2.6 (about 3.2M objects) using
Vicent's patches looks like:
$ du -sh *
42M pack-9ea76831aec6c49c5ff42509a2a2ce97da13c5ad.bitmap
87M pack-9ea76831aec6c49c5ff42509a2a2ce97da13c5ad.idx
630M pack-9ea76831aec6c49c5ff42509a2a2ce97da13c5ad.pack
Packing the same repo with "jgit debug-gc" (jgit 3.0.0) yields:
$ du -sh *
3.0M pack-2478783825733a1f1012f0087a0b5a92aa7437d8.bitmap
82M pack-2478783825733a1f1012f0087a0b5a92aa7437d8.idx
585M pack-2478783825733a1f1012f0087a0b5a92aa7437d8.pack
4.8M pack-f61fb76112372288923be7a0464476892dfebe3e.idx
97M pack-f61fb76112372288923be7a0464476892dfebe3e.pack
If we assume that 12M of that is name-hash, that's still an order of
magnitude larger. For reference, jgit created 327 bitmaps (according to
its progress eye candy), and Vicent's patches generated 385. So that
explains some of the increase, but the per-bitmap size is still much
larger.
The path hash cache may still be required, Colby and I have been
debating the merits of having the data available for delta compression
vs. the increase in memory required to hold it.
I guess this is not an option for JGit, but for C git, an mmap-able
name-hash file means we can just fault in the pages mentioning objects
we actually need it for. And its use can be completely optional; in
fact, it doesn't even need to be inside the .bitmap file (though I
cannot think of a reason it would be useful outside of having bitmaps).
-Peff
Right, the format and implementation in JGit can do "Counting objects"
in 87ms for the Linux kernel history.
Actually, that was the timing when I first pushed the change. With the
improvements submitted throughout the year, we can do counting in
50ms, on my same machine.
But I think we are comparing
apples to steaks here, Vincent is (rightfully) concerned about process
startup performance, whereas our timings were assuming the process was
already running.
On Mon, Jul 1, 2013 at 11:47 AM, Colby Ranger [off-list ref] wrote:
quoted
But I think we are comparing
apples to steaks here, Vincent is (rightfully) concerned about process
startup performance, whereas our timings were assuming the process was
already running.
A reverse index that is hot in RAM would obviously load in about 0ms.
But a cold load of a reverse index that uses only 4 bytes per object
(as Colby did here) for 3.1M objects could take ~590ms to read from
disk, assuming spinning media moving 20 MiB/s. If 8 byte offsets were
also stored this could be more like 1700ms.
Numbers obviously get better if the spinning media can transfer at 40
MiB/s, now its more like 295ms for 4 bytes/object and 885ms for 12
bytes/object.
I think its still reasonable to compute the reverse index on the fly.
But JGit certainly does have the benefit of reusing it across requests
by relying on process memory based caches. C Git needs to rely on the
kernel buffer cache, which requires this data be written out to a file
to be shared.
From: Jeff King <hidden> Date: 2016-06-15 22:58:01
On Mon, Jul 01, 2013 at 11:47:32AM -0700, Colby Ranger wrote:
quoted
But I think we are comparing
apples to steaks here, Vincent is (rightfully) concerned about process
startup performance, whereas our timings were assuming the process was
already running.
I did some timing on loading the reverse index for the kernel and it
is pretty slow (~1200ms). I just submitted a fix to do a bucket sort
and reduced that to ~450ms, which is still slow but much better:
On my machine, loading the kernel revidx in C git is about ~830ms. I
switched the qsort() call to a radix/bucket sort, and have it down to
~200ms. So definitely much better, though that still leaves a bit to be
desired for quick commands. E.g., "git rev-list --count A..B" should
become fairly instantaneous with bitmaps, but in many cases the revindex
loading will take longer than it would have to simply do the actual
traversal.
-Peff
On Sun, Jul 7, 2013 at 2:46 AM, Jeff King [off-list ref] wrote:
On Mon, Jul 01, 2013 at 11:47:32AM -0700, Colby Ranger wrote:
quoted
quoted
But I think we are comparing
apples to steaks here, Vincent is (rightfully) concerned about process
startup performance, whereas our timings were assuming the process was
already running.
I did some timing on loading the reverse index for the kernel and it
is pretty slow (~1200ms). I just submitted a fix to do a bucket sort
and reduced that to ~450ms, which is still slow but much better:
On my machine, loading the kernel revidx in C git is about ~830ms. I
switched the qsort() call to a radix/bucket sort, and have it down to
~200ms. So definitely much better,
This is a very nice reduction. pack-objects would benefit from it even
without bitmaps. Since it doesn't require a data format change this is
a pretty harmless patch to include in Git. We may later conclude
caching the revidx is worthwhile, but until then a bucket sort doesn't
hurt. :-)
though that still leaves a bit to be
desired for quick commands. E.g., "git rev-list --count A..B" should
become fairly instantaneous with bitmaps, but in many cases the revindex
loading will take longer than it would have to simply do the actual
traversal.
Yea, we don't know of a way around this. In a few cases the bitmap
code in JGit is slower than the naive traversal, but these are only on
small segments of history. I wonder if you could guess which algorithm
to use by looking at the offsets of A and B using the idx file. If
they are near each other in the pack, run the naive algorithm without
bitmaps and revidx. If they are farther apart assume the bitmap would
help more than traversal and use bitmap+revidx.
Working out what the correct "distance" should be before switching
algorithms is hard. A and B could be megabytes apart in the pack but A
could be B's grandparent and traversed in milliseconds. I wonder how
often that is in practice, certainly if A and B are within a few
hundred kilobytes of each other the naive traversal should be almost
instant.