[RFC] Packing large repositories

[RFC] Packing large repositories

[Dana How]

Hi,

I just started experimenting with using git on
a large engineering project which has used p4 so far.
Part of a checkout is about 55GB;
after an initial commit and packing I have a 20GB+ packfile.
Of course this is unusable, since object_entry's in an .idx
file have only 32 bits in their offset fields.  I conclude that
for such large projects,  git-repack/git-pack-objects would need
new options to control maximum packfile size.

[ I don't think this affects git-{fetch,receive,send}-pack
since apparently only the pack is transferred and it only uses
the variable-length size and delta base offset encodings
(of course the accumulation of the 7 bit chunks in a 32b
 variable would need to be corrected, but at least the data
format doesn't change).]

So I am toying with adding a --limit <size> flag to git-repack/git-pack-objects.
This cannot be used with --stdout.  If specified, e.g.
  git-repack --limit 2g
then each packfile created could be at most 2^31-1 bytes in size.
It's possible that multiple packfiles would be created in one shot.
Thus git-pack-objects could write multiple names to stdout
and git-repack would need to be updated accordingly.

Finally, I wonder if having tree/commit/tag objects mixed into
such large packfiles would be a performance hit.
(Or maybe this will only appear once I have real history,
 not just a large initial commit.  But I can say that I now have 48K
 data blobs and 9K others.)
To find out, I may experiment with adding a --type=<types> option
to git-repack/git-pack-objects.  Thus typing
  git-repack --limit 2g --type=tree+commit+tag,blob
would cause git-pack-objects to make 2 passes over its internal
object list. On the first, it would pack tree, commit, and tag objects.
On the second, it would pack blobs. Each pass would write at
least one independent packfile (or more with --limit).  This would also
allow different incremental repacking strategies/schedules for different types.

Comments?

Thanks!
-- 
Dana L. How  danahow@gmail.com  +1 650 804 5991 cell

Re: [RFC] Packing large repositories

[Linus Torvalds]

On Wed, 28 Mar 2007, Dana How wrote:
> 
> I just started experimenting with using git on
> a large engineering project which has used p4 so far.
> Part of a checkout is about 55GB;
> after an initial commit and packing I have a 20GB+ packfile.

Oh wow. You don't do half measures, do you ;)

> Of course this is unusable, since object_entry's in an .idx
> file have only 32 bits in their offset fields.  I conclude that
> for such large projects,  git-repack/git-pack-objects would need
> new options to control maximum packfile size.

Either that, or update the index file format. I think that your approach 
of having a size limiter is actually the *better* one, though. 

> [ I don't think this affects git-{fetch,receive,send}-pack
> since apparently only the pack is transferred and it only uses
> the variable-length size and delta base offset encodings
> (of course the accumulation of the 7 bit chunks in a 32b
> variable would need to be corrected, but at least the data
> format doesn't change).]

Well, it does affect fetching, in that "git index-pack" obviously would 
also need to be taught how to split the resulting indexed packs up into 
multiple smaller ones from one large incoming one. But that shouldn't be 
fundamentally hard either, apart from the inconvenience of having to 
rewrite the object count in the pack headers..

To avoid that issue, it may be that it's actually better to split things 
up at pack-generation time *even* for the case of --stdout, exactly so 
that "git index-pack" wouldn't have to split things up (we potentially 
know a lot more about object sizes up-front at pack-generation time than 
we know at re-indexing).

> So I am toying with adding a --limit <size> flag to
> git-repack/git-pack-objects.

Sounds very sane.

> This cannot be used with --stdout.  If specified, e.g.
>  git-repack --limit 2g
> then each packfile created could be at most 2^31-1 bytes in size.

Sounds good, apart from the caveat above about "--stdout" that needs some 
thinking about.

> It's possible that multiple packfiles would be created in one shot.
> Thus git-pack-objects could write multiple names to stdout
> and git-repack would need to be updated accordingly.

Yes. That seems to be the least of all problems.

> Finally, I wonder if having tree/commit/tag objects mixed into
> such large packfiles would be a performance hit.

My initial reaction is that it's best to start off without worrying about 
that, and just do everything in the order that we do now (ie "sort by 
type first, recency second") and just split when we hit the size limit.

But if you actually want to experiment with different organizations, I 
don't think that's wrong. I would just personally start without it.

		Linus

Re: [RFC] Packing large repositories

[Shawn O. Pearce]

Linus Torvalds <torvalds@linux-foundation.org> wrote:
> On Wed, 28 Mar 2007, Dana How wrote:
> > Of course this is unusable, since object_entry's in an .idx
> > file have only 32 bits in their offset fields.  I conclude that
> > for such large projects,  git-repack/git-pack-objects would need
> > new options to control maximum packfile size.
> 
> Either that, or update the index file format. I think that your approach 
> of having a size limiter is actually the *better* one, though. 

Nico and I were hoping we could push the index file format change back
until pack v4 was also worthy of merging.  So I had also started work
on an index-pack splitter:

  URL:    git://repo.or.cz/git/fastimport.git
  Branch: sp/splitpack
 
Its far from complete.

> Well, it does affect fetching, in that "git index-pack" obviously would 
> also need to be taught how to split the resulting indexed packs up into 
> multiple smaller ones from one large incoming one. But that shouldn't be 
> fundamentally hard either, apart from the inconvenience of having to 
> rewrite the object count in the pack headers..

We already do this if its a thin-pack that is being made non-thin.
So its annoying, yea, but we already have one toe in that particular
pond...
 
> To avoid that issue, it may be that it's actually better to split things 
> up at pack-generation time *even* for the case of --stdout

This is actually a pretty good idea.  index-pack knows when the end
of its current packfile is; if there are 12 more bytes available in
the input stream and it looks like another pack header then it can
just restart itself over again with that next pack.  This is actually
a pretty small change in index-pack, certainly a lot less intrusive
than what I was trying to do in my sp/splitpack topic above.
 
-- 
Shawn.

Re: [RFC] Packing large repositories

[Nicolas Pitre]

On Fri, 30 Mar 2007, Shawn O. Pearce wrote:

> Linus Torvalds <torvalds@linux-foundation.org> wrote:
> > On Wed, 28 Mar 2007, Dana How wrote:
> > > Of course this is unusable, since object_entry's in an .idx
> > > file have only 32 bits in their offset fields.  I conclude that
> > > for such large projects,  git-repack/git-pack-objects would need
> > > new options to control maximum packfile size.
> > 
> > Either that, or update the index file format. I think that your approach 
> > of having a size limiter is actually the *better* one, though. 
> 
> Nico and I were hoping we could push the index file format change back
> until pack v4 was also worthy of merging.  So I had also started work
> on an index-pack splitter:
> 
>   URL:    git://repo.or.cz/git/fastimport.git
>   Branch: sp/splitpack
>  
> Its far from complete.

Well... actually I really think the best solution might simply be a new 
index format right now.  All the preparatory work has been done already 
anyway.

IMHO that's the solution that would require the least work at this 
point, with the least possibility of issues/bugs.

Pack v4 could just use an index v3 which would be almost the same as 
index v2.

Remains only to determine what this new index format should look like.  
I think that the SHA1 table and the offset table should be separate.  
For one it will require less mmap space to binary search through 
the SHA1 table, and it will make things much easier if pack v4 stores 
the SHA1 table itself.


Nicolas

Re: [RFC] Packing large repositories

[Geert Bosch]

On Mar 30, 2007, at 15:01, Nicolas Pitre wrote:

> Remains only to determine what this new index format should look like.
> I think that the SHA1 table and the offset table should be separate.
> For one it will require less mmap space to binary search through
> the SHA1 table, and it will make things much easier if pack v4 stores
> the SHA1 table itself.

I've been working on a design for a new index file format, and I'll
include my current draft at the end of this message. It is not finished,
and I've not written much code yet, but I'd like to prevent duplicated
work and give others the opportunity to borrow from the ideas so far.

My main focus is to minimize the amount of data accessed in a random
fashion, allow for multiple packs and virtually unlimited scaling.
This is achieved through a fan-out table that grows with the number
of items in the pack, keeping the fan-out table overhead under 2 bits
per object while encoding a growing prefix of the object ID. This
frees up bits for a pack number. The pack number is either used to
find the correct pack, or alternatively for the right chunk of a
very large pack file.

   -Geert

---
The primary purpose of the pack index is to quickly
find the location of a given SHA1 in any of the pack
files. It is also used for quick lookup of and expansion
of a unique prefix of a SHA1 object name.

Original Pack Index

The original pack index uses a separate index file
per pack file, with the same name as the pack file
but a .idx extension instead of .pack. After an
initial 256 entry fan-out table gives an approximate
range of the object, binary lookup is used to find
the exact object entry in the table of objects sorted
by SHA1. Each entry is 24 bytes: the 20 bytes of the
SHA1 and 4 bytes for the offset.

A problem with that approach is that doesn't scale well
for repositories with large numbers of objects and
pack files. In the following I'll assume a repository
with 1K packs containing about 1M objects of 1K bytes
each for a total repository size of 1TB. Such a scenario
could occur in a situation where many loosely connected
projects are combined in one large repository.

Performance with Large Repository

Now consider the working set needed to complete a job
involving the lookup of 1K random objects in the
repository described above. File access are counted
in 4K blocks.  The index for each pack is about 24M bytes,
and the total space for all indices is 24G bytes.

Each lookup in a pack file reads the entire fan-out table,
so the 1K * 4K = 4M of pack fan out tables is read.
A successful object lookup searches through about half
of the table entries, so each pack file will be used
approximately 500 times. Each of the 256 fan-out bins
has about 4K objects (totalling 96K bytes)
and will be accessed twice.

Of the expected 12 binary lookups, the first one will
be repeated twice, while the second level has a 50%
chance of hitting the same location, the third level
25% and so on. So, on average 11 unique lookups will
be done per object access for each pack. Since a total
of 22 random reads will be done in each 96K bin,
most if not all of the file blocks in the pack indices
needs to be read. As access is random, there is no
meaningful caching possible for the 24G working set
of indices.

The result is 500*11=5500 random disk reads accessing
each object, for a total of 5500K I/Os in the the 24G
of pack indices.

Multiple Pack Index

The linear search through packs is very inefficient
with large numbers of packs. Having packs much larger
than a GB is also problematic, due to this as repacking
and otherwise modifying packs gets very expensive.

Another issue is that binary search requires many
semi-random accesses spread over the index. Finally,
most of the information actually read consists of
SHA1's that are never needed.

This proposed pack index format does not focus on reducing
used disk space, but instead aims to reduce the number
of blocks that needs to be read to perform lookups.
This is done using three techniques:
   1) scale the number of fan-out bins with the number
      of objects in the index, keeping the expected
      number of objects in each bin constant
   2) take advantage of 1) by only storing a few bits
      following the common prefix in the main lookup table
      as a discriminant. Store the rest of the SHA1 and
      the pack offest in a separate, parallel, object table.
   3) Instead of repeating the variable-length common prefix
      and the discriminant, use the space for the prefix
      for a pack identifier and omit the discriminant altogether.

For a repository with N objects and highest PACK_NR P,
the total space used for the index is bounded by
24 * (N + P) bytes, if N is at least 512 and N >= 512 * P.

Limits:
    - Maximum number of packs: 2^27
    - Maximum number of objects: 2^40
    - Maximum repository size: 2^48 bytes

<PACK_INDEX>
    :   <IDX_PACK_LIST>
        <IDX_FANOUT_BITS>
        <IDX_FANOUT_TABLE>
        <IDX_LOOKUP_TABLE>
        <IDX_OBJECT_TABLE>
        <IDX_CHECKSUM>
    ;

<IDX_PACK_LIST>
    :   <IDX_PACK_LIST_ENTRIES>
        <ZERO_32> <IDX_PACK_LIST_CHECKSUM>
    ;
<IDX_PACK_LIST_ENTRIES>
    # List of packs sorted by ascending PACK_ID
    :  ( <IDX_PACK_NR> <PACK_ID> ) *
    ;

<PACK_ID>
    # 20-byte binary representation of the 40 hex-digit
    # value PACK_ID_HEX, such that pack-${PACK_ID_HEX}.pack
    # is the name of the pack file
    ;

<IDX_PACK_NR>
    # 32-bit unsigned integer in network order, with the same
    # value as the preceding <IDX_PACK_NR> (or zero for the
    # first entry), increased by the size of the pack file in
    # bytes, divided by 2^32 and rounded up.
    ;

<ZERO_32>
    # 32-bit zero
    ;

<IDX_PACK_LIST_CHECKSUM>
    # 20-byte SHA1 of <IDX_PACK_LIST_ENTRIES>
    ;

<IDX_FANOUT_BITS>
    # 1 byte with the smallest value N between 8 and 35,
    # such that 2^(N - 8) greater than or equal to the
    # largest IDX_PACK_NR in the IDX_PACK_LIST, and such that
    # 2^(N+5) is greater than or equal to the total number
    # of objects in all packs.
    ;

<IDX_FANOUT_TABLE>
    # Table of 2^${IDX_FANOUT_BITS} entries
    :   ( <IDX_PARTIAL_COUNT> ) *
    ;

<IDX_PARTIAL_COUNT>
    # 40 bit, network byte order, binary integer of the count of
    # objects in the pack file with the high IDX_FANOUT_BITS bits of
    # the object ID less than or equal to the index of the count,
    # starting from zero.
    ;

<IDX_LOOKUP_TABLE>
    # One 8-bit key per object indexed by the pack
    :   ( <IDX_LOOKUP_KEY> ) *
    ;

<IDX_LOOKUP_KEY>
    # Bits IDX_FANOUT_BITS through IDX_FANOUT_BITS + 7 of the
    # object ID.
    ;

<IDX_OBJECT_ENTRY>
    # The total width of each entry is 22 bytes
    :   ( <IDX_PACK_REF> <IDX_OBJECT_ID> <IDX_OFFSET> ) *
    ;

<IDX_PACK_REF>
    # A IDX_FANOUT_BITS - 8 bit wide integer value, equal to
    # PACK_NR of pack preceding the one containing the object
    # (or zero, if object is in first pack) increased with the
    # pack offset divided by 2^32.
    ;

<IDX_OBJECT_ID>
    # Bits IDX_FANOUT_BITS + 8 .. 159 of the object ID
    ;

<IDX_OFFSET>
    # 32-bits offset in network byte order
    ;

Re: [RFC] Packing large repositories

[Linus Torvalds]

On Sat, 31 Mar 2007, Geert Bosch wrote:
> 
> I've been working on a design for a new index file format, and I'll
> include my current draft at the end of this message. It is not finished,
> and I've not written much code yet, but I'd like to prevent duplicated
> work and give others the opportunity to borrow from the ideas so far.

Ok, here's one comment...

I think your basic assumption that the current index-pack is bad is 
broken ;)

The thing is, I think the index-pack could be improved, but I think we can 
get a bigger improvement from just being more intelligent about searching 
than from actually needing to re-organize the pack.

Here's a few clues:
 - binary search is certainly not the only way to do lookups on sorted 
   contents
 - one of the fundamental rules about cryptographic hashes is that they 
   are *evenly*distributed*
 - currently we do not take advantage of our inherent knowledge of the 
   distribution when we look things up, and we use a stupid binary lookup 
   that is guaranteed to basically always take O(log2(n)) random jumps 
   around the data area, with bad locality.

In other words, the 256-entry fan-out was meant to avoid the first eight 
levels of binary lookup. But the thing is, we should be able to generally 
do a *lot* better than any binary lookup by just doing a LINEAR SEARCH, 
which is also more cache-friendly, and prefetches much better when it's 
not in the cache.

The only thing we want for a linear search is a good starting point. Which 
gets us back to the simple: "SHA1 hashes are evenly distributed". In other 
words, getting a good starting point should be *trivial*.

So here's a suggestion:

 - start finding a range using the 256-entry fan-out, exactly the way we 
   did for the binary search. It's cheap. We could probably avoid EVEN 
   THIS, and just do one more newton-raphson iteration more. But since we 
   have the data, we migth as well use it. After all, it really *is* just 
   a first approximation of newton-raphson, and while it uses only 8 bits 
   (and we could do better), at least it's an *exact* one.

 - use newton-raphson to iterate closer. It should be a much faster way to 
   find the rough area for the entry we're searching for than binary 
   search. Two or three iterations should get us there, easily.

 - do a linear search once you're close enough.

Here's a stupid patch that does that. It's biggest weakness is that it 
only does a single iteration of newton-raphson. It should probably do at 
least one more iteration. I bet that you'd get so close that you find it 
really quickly if you did that. As it is, it doesn't seem to be any slower 
than the binary search..

And the nice thing is that I think that in large packs the "evenly 
distributed" should be *more*true* than in small packs, so this should 
scale up very nicely, and I'm hoping that it would get much better cache 
behaviour (because we wouldn't bounce around in the index file too much). 
I wouldn't be surprised if we basically hit it on the first try if we did 
two or three iterations of newton-raphson.

Comments? Does anybody want to take this and run with it?

(No guarantees that this really can ever beat binary search, but somebody 
might find this interesting. And I think the potential is there, but I 
think you do need to do at *least* two iterations).

		Linus
---
 sha1_file.c |   79 +++++++++++++++++++++++++++++++++++++++++++++++-----------
 1 files changed, 64 insertions(+), 15 deletions(-)

diff --git a/sha1_file.c b/sha1_file.c
index 9c26038..fc4dbc7 100644
--- a/sha1_file.c
+++ b/sha1_file.c
@@ -1543,29 +1543,78 @@ int nth_packed_object_sha1(const struct packed_git *p, uint32_t n,
 	return 0;
 }
 
-off_t find_pack_entry_one(const unsigned char *sha1,
-				  struct packed_git *p)
+struct index_entry {
+	uint32_t nb_offset;	/* pack-file offset in network byte order */
+	unsigned char sha1[20];	/* SHA1 of the object */
+};
+
+static off_t pack_search_backward(const struct index_entry *index, uint32_t guess, const unsigned char *sha1)
 {
-	const uint32_t *level1_ofs = p->index_data;
-	int hi = ntohl(level1_ofs[*sha1]);
-	int lo = ((*sha1 == 0x0) ? 0 : ntohl(level1_ofs[*sha1 - 1]));
-	const unsigned char *index = p->index_data;
+	int count = 1;
+	while (guess) {
+		int cmp;
 
-	index += 4 * 256;
+		guess--;
+		index--;
+		cmp = hashcmp(index->sha1, sha1);
+		if (!cmp)
+			return ntohl(index->nb_offset);
+		if (cmp < 0)
+			break;
+		count++;
+	}
+	return 0;
+}
 
-	do {
-		int mi = (lo + hi) / 2;
-		int cmp = hashcmp(index + 24 * mi + 4, sha1);
+static off_t pack_search_forward(const struct index_entry *index, uint32_t guess, uint32_t max, const unsigned char *sha1)
+{
+	int count = 1;
+	while (++guess < max) {
+		int cmp;
+
+		index++;
+		cmp = hashcmp(index->sha1, sha1);
 		if (!cmp)
-			return ntohl(*((uint32_t *)((char *)index + (24 * mi))));
+			return ntohl(index->nb_offset);
 		if (cmp > 0)
-			hi = mi;
-		else
-			lo = mi+1;
-	} while (lo < hi);
+			break;
+		count++;
+	}
 	return 0;
 }
 
+off_t find_pack_entry_one(const unsigned char *sha1,
+				  struct packed_git *p)
+{
+	const struct index_entry *index;
+	const uint32_t *level1_ofs = p->index_data;
+	uint32_t min, max, first;
+	uint32_t hash_val;
+	uint32_t guess;
+	int cmp;
+
+	first = *sha1;
+	min = first ? ntohl(level1_ofs[first - 1]) : 0;
+	max = ntohl(level1_ofs[first]);
+
+	hash_val = (sha1[1] << 24) |
+		   (sha1[2] << 16) |
+		   (sha1[3] << 8) |
+		   (sha1[4]);
+	guess = ((uint64_t)(max - min) * hash_val) >> 32;
+	guess += min;
+
+	index = (const struct index_entry *)((char *) p->index_data + 4 * 256);
+	index += guess;
+
+	cmp = hashcmp(index->sha1, sha1);
+	if (!cmp)
+		return ntohl(index->nb_offset);
+	if (cmp > 0)
+		return pack_search_backward(index, guess, sha1);
+	return pack_search_forward(index, guess, max, sha1);
+}
+
 static int matches_pack_name(struct packed_git *p, const char *ig)
 {
 	const char *last_c, *c;

Re: [RFC] Packing large repositories

[Nicolas Pitre]

On Sat, 31 Mar 2007, Geert Bosch wrote:

> I've been working on a design for a new index file format, and I'll
> include my current draft at the end of this message. It is not finished,
> and I've not written much code yet, but I'd like to prevent duplicated
> work and give others the opportunity to borrow from the ideas so far.

I'm glad you posted this as I intended to work on the index today.

> My main focus is to minimize the amount of data accessed in a random
> fashion, allow for multiple packs and virtually unlimited scaling.
> This is achieved through a fan-out table that grows with the number
> of items in the pack, keeping the fan-out table overhead under 2 bits
> per object while encoding a growing prefix of the object ID. This
> frees up bits for a pack number. The pack number is either used to
> find the correct pack, or alternatively for the right chunk of a
> very large pack file.

And how do you determine that pack number?

The index should be tied to the pack it is indexing and nothing else 
like the presence of other packs if possible.  When given a 20-byte SHA1 
you don't know what packnumber that corresponds to anyway.

> The linear search through packs is very inefficient
> with large numbers of packs. Having packs much larger
> than a GB is also problematic, due to this as repacking
> and otherwise modifying packs gets very expensive.

Repacking is not a frequent operation, and it can be done 
asynchronously.  So I don't consider that to be a big issue if it is 
expensive.  It is already extremely expensive compared to other GIT 
operations.  So it is better to have fewer and bigger packs to speed up 
runtime object searching than making repack less expensive with more 
smaller packs.

> Another issue is that binary search requires many
> semi-random accesses spread over the index. Finally,
> most of the information actually read consists of
> SHA1's that are never needed.

Of course the pack v4 design allow for bypassing all this altogether in 
most cases.  But it doesn't eliminate the need for an index in every 
cases.  So let's optimize the index first, especially since the pressing 
need now is to lift the 4G pack size limit. And pack v4 will come after 
that.

Just to say that the index doesn't need to be the ultimate thing as pack 
v4 will scale much better than any index format could ever do due to its 
direct object reference design.

However, a big detail that would greatly help pack v4 is to have the 
SHA1 table together in one block with no other fields inserted between 
entries.  Then the only difference between current packs and pack v4 
would be that the SHA1 table will be located in the pack itself instead 
of the index (pack v4 will carry the sorted SHA1 table already so the 
index won't have to store it).

> This proposed pack index format does not focus on reducing
> used disk space, but instead aims to reduce the number
> of blocks that needs to be read to perform lookups.
> This is done using three techniques:
>   1) scale the number of fan-out bins with the number
>      of objects in the index, keeping the expected
>      number of objects in each bin constant
>   2) take advantage of 1) by only storing a few bits
>      following the common prefix in the main lookup table
>      as a discriminant. Store the rest of the SHA1 and
>      the pack offest in a separate, parallel, object table.
>   3) Instead of repeating the variable-length common prefix
>      and the discriminant, use the space for the prefix
>      for a pack identifier and omit the discriminant altogether.

I think (2) conflicts with my goal of having the SHA1 table independent. 
It is really important for future compatibility with pack v4 that the 
SHA1 table remains a sorted list of contiguous 20-byte records.

I really like your adaptative fanout idea though.  So it could be 
possible to have something based on the largest common SHA1 prefix 
within a pack for example.  Or maybe it could be made multi level for an 
arbitrary portion of the largest common prefix.


Nicolas

Re: [RFC] Packing large repositories

[Nicolas Pitre]

On Sat, 31 Mar 2007, Linus Torvalds wrote:

> The thing is, I think the index-pack could be improved, but I think we can 
> get a bigger improvement from just being more intelligent about searching 
> than from actually needing to re-organize the pack.
> 
> Here's a few clues:
>  - one of the fundamental rules about cryptographic hashes is that they 
>    are *evenly*distributed*

I was thinking about that too.

> So here's a suggestion:
> 
>  - start finding a range using the 256-entry fan-out, exactly the way we 
>    did for the binary search. It's cheap. We could probably avoid EVEN 
>    THIS, and just do one more newton-raphson iteration more. But since we 
>    have the data, we migth as well use it. After all, it really *is* just 
>    a first approximation of newton-raphson, and while it uses only 8 bits 
>    (and we could do better), at least it's an *exact* one.
> 
>  - use newton-raphson to iterate closer. It should be a much faster way to 
>    find the rough area for the entry we're searching for than binary 
>    search. Two or three iterations should get us there, easily.
> 
>  - do a linear search once you're close enough.

I like that.


Nicolas

Re: [RFC] Packing large repositories

[Junio C Hamano]

Linus Torvalds <torvalds@linux-foundation.org> writes:

> In other words, the 256-entry fan-out was meant to avoid the first eight 
> levels of binary lookup. But the thing is, we should be able to generally 
> do a *lot* better than any binary lookup by just doing a LINEAR SEARCH, 
> which is also more cache-friendly, and prefetches much better when it's 
> not in the cache.
> ...
>  - use newton-raphson to iterate closer. It should be a much faster way to 
>    find the rough area for the entry we're searching for than binary 
>    search. Two or three iterations should get us there, easily.

This is another egg of columbus moment that makes me feel it was
worth to have been in git community ;-).

I like it.

Re: [RFC] Packing large repositories

[Linus Torvalds]

On Sat, 31 Mar 2007, Linus Torvalds wrote:
> 
> Here's a stupid patch that does that. It's biggest weakness is that it 
> only does a single iteration of newton-raphson. It should probably do at 
> least one more iteration. I bet that you'd get so close that you find it 
> really quickly if you did that. As it is, it doesn't seem to be any slower 
> than the binary search..

Ok, here's a slightly updated patch that does a few more iterations..

It actually seems to outperform the old binary search for me, although 
quite frankly, my only test was the eclipse git thing, and doing a

	time git log > /dev/null

which isn't exactly scientific or necessarily even very interesting. For 
a run of five, I got:

Before:
	real    0m2.940s
	real    0m2.277s
	real    0m2.220s
	real    0m2.377s
	real    0m2.223s

After:
	real    0m2.903s
	real    0m2.217s
	real    0m2.269s
	real    0m2.148s
	real    0m2.215s

ie it's really pretty much in the noise, but the best-of-five actually 
comes with this Newton-Raphson + linear search thing rather than with the 
binary search.

Anyway, it's *so* much in the noise that I doubt that object lookup really 
is a very noticeable cost for this load (and perhaps it never is). But it 
was interesting to see that at least the theory seems sound.

The patch has some commented-out statistics code (ie "hit it in one" vs 
reporting how many steps forwards/backwards it needed to look.

Not really meant to be applied, but it was interesting to play with 
this. NOTE! I don't think the math is really strictly correct (ie the 
scaling inside the loop), but it's "close enough" to not matter, and this 
really was meant to be an request-for-discussion.

		Linus

---
diff --git a/sha1_file.c b/sha1_file.c
index 9c26038..b1643ea 100644
--- a/sha1_file.c
+++ b/sha1_file.c
@@ -1543,27 +1543,134 @@ int nth_packed_object_sha1(const struct packed_git *p, uint32_t n,
 	return 0;
 }
 
+struct index_entry {
+	uint32_t nb_offset;	/* pack-file offset in network byte order */
+	unsigned char sha1[20];	/* SHA1 of the object */
+};
+
+static off_t pack_search_backward(const struct index_entry *index, uint32_t guess, const unsigned char *sha1)
+{
+	int count = 1;
+	while (guess) {
+		int cmp;
+
+		guess--;
+		index--;
+		cmp = hashcmp(index->sha1, sha1);
+		if (!cmp) {
+//			error("  backward: %d", count);
+			return ntohl(index->nb_offset);
+		}
+		if (cmp < 0)
+			break;
+		count++;
+	}
+	return 0;
+}
+
+static off_t pack_search_forward(const struct index_entry *index, uint32_t guess, uint32_t max, const unsigned char *sha1)
+{
+	int count = 1;
+	while (++guess < max) {
+		int cmp;
+
+		index++;
+		cmp = hashcmp(index->sha1, sha1);
+		if (!cmp) {
+//			error("  forward: %d", count);
+			return ntohl(index->nb_offset);
+		}
+		if (cmp > 0)
+			break;
+		count++;
+	}
+	return 0;
+}
+
+/*
+ * The "fraction" thing is a 32-bit number that is seen as a
+ * fraction of 1<<32. Ie 0x80000000 means "half-way". We use
+ * this as a way to do simple comparisons of 32-bit partial
+ * SHA1 fragments, and to estimate how far off we are from
+ * the value we wish to see.
+ */
+static inline uint32_t get_fraction(const unsigned char *p)
+{
+	return (p[0] << 24) | (p[1] << 16) | (p[2] << 8) | p[3];
+}
+
+static inline int update_guess(unsigned int nr, uint32_t fraction)
+{
+	return (0x80000000 + nr * (uint64_t) fraction) >> 32;
+}
+
 off_t find_pack_entry_one(const unsigned char *sha1,
 				  struct packed_git *p)
 {
+	int i;
+	const struct index_entry *index;
 	const uint32_t *level1_ofs = p->index_data;
-	int hi = ntohl(level1_ofs[*sha1]);
-	int lo = ((*sha1 == 0x0) ? 0 : ntohl(level1_ofs[*sha1 - 1]));
-	const unsigned char *index = p->index_data;
+	uint32_t min, max, first;
+	uint32_t hash_val, guess;
+	int cmp;
 
-	index += 4 * 256;
+	/*
+	 * Get the initial range using the first 8 bits of
+	 * the SHA1 and the 8-bit fan-out in the index
+	 */
+	first = *sha1;
+	min = first ? ntohl(level1_ofs[first - 1]) : 0;
+	max = ntohl(level1_ofs[first]);
+	if (min == max)
+		return 0;
 
-	do {
-		int mi = (lo + hi) / 2;
-		int cmp = hashcmp(index + 24 * mi + 4, sha1);
-		if (!cmp)
-			return ntohl(*((uint32_t *)((char *)index + (24 * mi))));
-		if (cmp > 0)
-			hi = mi;
+	/*
+	 * Initial guess using the next 32 bits of the SHA1
+	 * (using "sha1+1" because the first byte of the SHA1
+	 * is now known to be irrelevant and will always match,
+	 * thanks to the index fan-out)
+	 */
+	hash_val = get_fraction(sha1+1);
+	guess = min + update_guess(max - min, hash_val);
+
+	/*
+	 * Look up that entry in the index file...
+	 */
+	index = (const struct index_entry *)((char *) p->index_data + 4 * 256);
+	index += guess;
+
+	/*
+	 * ..and update the guess with a correction based on how
+	 * close the guessed entry's hash value was.
+	 */
+	for (i = 0; i < 3; i++) {
+		uint32_t guess_hash_val = get_fraction(index->sha1+1);
+		int correction;
+
+		if (guess_hash_val == hash_val)
+			break;
+		if (guess_hash_val < hash_val)
+			correction = update_guess(max - guess, hash_val - guess_hash_val);
 		else
-			lo = mi+1;
-	} while (lo < hi);
-	return 0;
+			correction = -update_guess(guess - min, guess_hash_val - hash_val);
+		if (!correction)
+			break;
+		guess += correction;
+		index += correction;
+	}
+
+	/*
+	 * ..and we should now be close enough that now we'll just use a
+	 * linear search from the updated guess.
+	 */
+	cmp = hashcmp(index->sha1, sha1);
+	if (!cmp) {
+//		error("hit it in one!");
+		return ntohl(index->nb_offset);
+	}
+	if (cmp > 0)
+		return pack_search_backward(index, guess, sha1);
+	return pack_search_forward(index, guess, max, sha1);
 }
 
 static int matches_pack_name(struct packed_git *p, const char *ig)

Re: [RFC] Packing large repositories

[Linus Torvalds]

On Sat, 31 Mar 2007, Linus Torvalds wrote:
> 
> Ok, here's a slightly updated patch that does a few more iterations..

Don't use this. There's something wrong with it, and unlike the first 
patch, it doesn't even pass all tests.

I think it's because I decided to try to use rounding in the newton thing 
(which got things closer), but I suspect that rounding is broken - I think 
it can round to "outside" the valid range. I didn't notice that with the 
eclipse performance testing, probably because when you have enough objects 
you'll never see it, but with smaller packs, being off-by-one means that 
you can easily fall off the map ;)

So I'd like to re-iterate the note I had in that email:

> Not really meant to be applied, but it was interesting to play with 
> this. NOTE! I don't think the math is really strictly correct (ie the 
> scaling inside the loop), but it's "close enough" to not matter, and this 
> really was meant to be an request-for-discussion.

IOW, it's very much a RFD patch. I suspect it is trivial to fix, but I 
also suspect that unless somebody else decides that this is interesting, 
I'll just leave the patch behind. None of the loads I tested really seemed 
to be very sensitive to object lookup performance - the binary search 
simply seems ot be "good enough", and usually the costs are in generating 
patches ("git blame") or just diffing trees ("git log <pathspec>"), and 
the object lookup doesn't seem to be critical enough to worry about.

If somebody can point to a load where we spend a noticeable amount of time 
on doing index lookups, that would obviously change my opinion, but in the 
meantime, I think this is better considered a case of "we _could_ do 
something like this if it's ever an issue.."

		Linus

Re: [RFC] Packing large repositories

[Sam Vilain]

Dana How wrote:
> Hi,
>
> I just started experimenting with using git on
> a large engineering project which has used p4 so far.
> Part of a checkout is about 55GB;
> after an initial commit and packing I have a 20GB+ packfile.
> Of course this is unusable, since object_entry's in an .idx

Another idea to consider is that if you are storing changes of files
which have a compressed file format, you will almost certainly save a
huge amount by storing the uncompressed version in the git repository -
as then delta compression stands a chance of working.

Sam.

Re: [RFC] Packing large repositories

[Geert Bosch]

On Mar 31, 2007, at 20:36, Linus Torvalds wrote:

> So here's a suggestion:
>
>  - start finding a range using the 256-entry fan-out, exactly the  
> way we
>    did for the binary search. It's cheap. We could probably avoid EVEN
>    THIS, and just do one more newton-raphson iteration more. But  
> since we
>    have the data, we migth as well use it. After all, it really  
> *is* just
>    a first approximation of newton-raphson, and while it uses only  
> 8 bits
>    (and we could do better), at least it's an *exact* one.
>
>  - use newton-raphson to iterate closer. It should be a much faster  
> way to
>    find the rough area for the entry we're searching for than binary
>    search. Two or three iterations should get us there, easily.
>
>  - do a linear search once you're close enough.

Actually, I had implemented this first, using two newton-raphson
iterations and then binary search. With just one iteration is
too little, and one iteration+binary search often is no win.
Two iterations followed by binary search cuts the nr of steps in
half for the Linux kernel. Two iterations followed by linear search
is often worse, because of "unlucky" cases that end up doing many
probes. Still, during the 5-8 probes in moderately large repositories
(1M objects), each probe pretty much requires its own cache line:
very cache unfriendly.

By using a fan-out table with an average nr of entries per bin
of 32 or so, you get a total cache footprint of between 1 and 2 bits
per entry for the random lookup. So, a complete lookup only hits
about 3 cache lines.  After a few lookups, almost all of the
fan-out table will be in cache, while currently, the cache is
filled with useless 24 byte SHA1+offset of unrelated objects.

   -Geert

PS. I'm travelling now, so can't participate in the discussion
     or send code as much as I'd like and mail may be late or
     out of sequence.

Re: [RFC] Packing large repositories

[Dana How]

[-- Attachment #1: Type: text/plain, Size: 6615 bytes --]

On 3/28/07, Linus Torvalds <torvalds@linux-foundation.org> wrote:
> > I just started experimenting with using git ...
> > Part of a checkout is about 55GB;
> > after an initial commit and packing I have a 20GB+ packfile.
> > Of course this is unusable, ... . I conclude that
> > for such large projects,  git-repack/git-pack-objects would need
> > new options to control maximum packfile size.
>
> Either that, or update the index file format. I think that your approach
> of having a size limiter is actually the *better* one, though.
>
> > [ I don't think this affects git-{fetch,receive,send}-pack
> > since apparently only the pack is transferred and it only uses
> > the variable-length size and delta base offset encodings
> > (of course the accumulation of the 7 bit chunks in a 32b
> > variable would need to be corrected, but at least the data
> > format doesn't change).]
>
> Well, it does affect fetching, in that "git index-pack" obviously would
> also need to be taught how to split the resulting indexed packs up into
> multiple smaller ones from one large incoming one. But that shouldn't be
> fundamentally hard either, apart from the inconvenience of having to
> rewrite the object count in the pack headers..
>
> To avoid that issue, it may be that it's actually better to split things
> up at pack-generation time *even* for the case of --stdout, exactly so
> that "git index-pack" wouldn't have to split things up (we potentially
> know a lot more about object sizes up-front at pack-generation time than
> we know at re-indexing).

The attached patch adds a --pack-limit[=N] option
to git-repack/git-pack-objects.  N defaults to 1<<31,
and the result with --pack-limit is that no packfile
can be equal to or larger than N.  A --blob-limit=N
option is also added (see below).

My original plan was simply to ensure that no
object started at a file offset not representable in 31 bits.
However,  I became concerned about the arithmetic involved
when mmap'ing a pack,  so I decided to make sure *all*
bytes lived at offsets representable in 31 bits.

Consequently after an object is written out,
the new offset is checked.  If the limit has been exceeded,
the write is rolled back (see sha1mark/sha1undo).
This is awkward and inefficient,  but yields packs closer
to the limit and happens too infrequently to be of much impact.

However, there are really two modes when packing:
packing to disk, and packing to stdout.
Since you can't rollback a write on stdout,  the initial
file-offset-limit technique is used when --stdout is specified.
[Note:  I did not *test* the --pack-limit && --stdout combination.]

To fully guarantee that a pack file doesn't exceed a certain size,
objects above that size must not be packed into it.
But I think this makes sense -- I don't see a lot of advantage
to packing a 100MB+ object into a pack,  except for fetch/send
which is a serial stream without index anyway.  Thus
this patch automatically excludes any object whose uncompressed
size is 1/4 or more of the packfile size limit when --stdout
is not specified.  This behavior can be altered with an explicit
--blob-limit=N option.

Two interesting twists presented themselves.
First,  the packfile contains the number of objects in
the header at the beginning,  and this header is included
in the final SHA1.  But I don't know the final count until
the limit is reached.  Consequently the header must be
rewritten and the entire file rescanned to make the correct
checksum.  This already happens in two other places in git.

Secondly,  when using --pack-limit with --stdout,  the header
can't be rewritten.  Instead the object count in the header
is left at 0 to flag that it's wrong.  The end of an individual
pack inside a multi-pack stream COULD be detected by checking,
after each object,  if the next 20 bytes are equal to the SHA1
of what's come before.  I've made no additional effort beyond
this minimal solution because it's not clear that splitting
a pack up at the transmitter is better than at the receiver.
An alternative method is to add,  before the final SHA1,  a last
object of type OBJ_NONE and length 0 (thus a single zero byte).
This would function as an EOF marker.  I've indicated where this
would go in write_pack_file but didn't put it in since the current
code doesn't tolerate a 0 object count in the header anyway (yet?).
[Note: I have *not* started in on teaching git-index-pack etc.
 how to read such concatenated split packs since (a) I'd like
 to see which way people will prefer and (b) I don't plan on
 using the feature anyway and I'm wondering if I'm alone
 in that reaction.]

Some code has been added but
very few function relationships have been changed,
with the exception that write_pack_file now calls write_index_file
directly since write_pack_file decides when to split packs
and thus must call write_index_file before moving on to the next pack.

In response to my original post,  I've seen some emails about
changing the pack file/index file format.  This is exactly what I
*didn't* want to do,  since (1) it would delay a feature I'd like to
use now,  (2) the current format is better than people seem to realize,
and (3) it would create yet another flag in the config file
to help phase in a new feature over a year or two.

If,  however,  there are other pent-up reasons for changing the format
which might make it happen sometime soon,  I can see some small tweaks
that could be useful.

* [For stdout/serial access:] Tolerate "0" for object count in a .pack
file;  it would mean look for the pack end by either matching a SHA1 or
looking for an OBJ_NONE/0 record,  all as explained above.
(The point is to avoid any need to rescan a file to rebuild checksums.)

* [For disk/random access:] Don't change the current .pack/.idx files,
but do add a third file type which would be a "super index" with a format
similar to .idx.  It would map sorted SHA1s to (pack#,offset) pairs,
either in one table of triples or two parallel tables, one of SHA1s and
the other of pairs.  It probably would only be used if mentioned in
objects/info/packs (and it would be automatically ignored if older than
objects/info/packs?).  It could be searched by taking advantage of the
uniform SHA1 distribution recently discussed.  There would be at most
one such file in a repository;  perhaps the .idx files from which it was
generated could be removed.  For safety the "super index" could contain
a small table of all the SHA1s for the packs it indexes.

Thanks,
-- 
Dana L. How  danahow@gmail.com  +1 650 804 5991 cell

cat GIT-VERSION-FILE
GIT_VERSION = 1.5.1.rc2.18.g9c88-dirty

[-- Attachment #2: large.patch --]
[-- Type: application/octet-stream, Size: 20042 bytes --]

diff --git a/builtin-pack-objects.c b/builtin-pack-objects.c
index b5f9648..0a11113 100644
--- a/builtin-pack-objects.c
+++ b/builtin-pack-objects.c
@@ -14,8 +14,8 @@
 #include "list-objects.h"
 
 static const char pack_usage[] = "\
-git-pack-objects [{ -q | --progress | --all-progress }] \n\
-	[--local] [--incremental] [--window=N] [--depth=N] \n\
+git-pack-objects [{ -q | --progress | --all-progress }] [--pack-limit[=N]]\n\
+	[--blob-limit=N] [--local] [--incremental] [--window=N] [--depth=N]\n\
 	[--no-reuse-delta] [--delta-base-offset] [--non-empty] \n\
 	[--revs [--unpacked | --all]*] [--reflog] [--stdout | base-name] \n\
 	[<ref-list | <object-list]";
@@ -29,6 +29,7 @@ struct object_entry {
 	unsigned int depth;	/* delta depth */
 	unsigned int delta_limit;	/* base adjustment for in-pack delta */
 	unsigned int hash;	/* name hint hash */
+	char no_write;		/* flag: written to previous pack OR too big */
 	enum object_type type;
 	enum object_type in_pack_type;	/* could be delta */
 	unsigned long delta_size;	/* delta data size (uncompressed) */
@@ -68,7 +69,10 @@ static int allow_ofs_delta;
 
 static struct object_entry **sorted_by_sha, **sorted_by_type;
 static struct object_entry *objects;
-static uint32_t nr_objects, nr_alloc, nr_result;
+static struct object_entry **written_list;
+static uint32_t nr_objects, nr_alloc, nr_result, nr_written, nr_skipped = 0;
+static uint32_t offset_limit = 0;
+static uint32_t blob_limit = 0;
 static const char *base_name;
 static unsigned char pack_file_sha1[20];
 static int progress = 1;
@@ -415,13 +419,17 @@ static off_t write_object(struct sha1file *f,
 	}
 
 	if (!to_reuse) {
+		int usable_delta =	!entry->delta ? 0 :
+					!offset_limit ? 1 :
+					entry->delta->no_write ? 0 :
+					entry->delta->offset ? 1 : 0;
 		buf = read_sha1_file(entry->sha1, &type, &size);
 		if (!buf)
 			die("unable to read %s", sha1_to_hex(entry->sha1));
 		if (size != entry->size)
 			die("object %s size inconsistency (%lu vs %lu)",
 			    sha1_to_hex(entry->sha1), size, entry->size);
-		if (entry->delta) {
+		if (usable_delta) {
 			buf = delta_against(buf, size, entry);
 			size = entry->delta_size;
 			obj_type = (allow_ofs_delta && entry->delta->offset) ?
@@ -503,62 +511,212 @@ static off_t write_one(struct sha1file *f,
 			       struct object_entry *e,
 			       off_t offset)
 {
-	if (e->offset || e->preferred_base)
+	struct sha1posn posn;
+	uint32_t save_written = 0, save_written_delta = 0;
+	uint32_t save_reused = 0, save_reused_delta = 0;
+	if (e->offset || e->preferred_base || e->no_write)
 		/* offset starts from header size and cannot be zero
 		 * if it is written already.
 		 */
 		return offset;
 	/* if we are deltified, write out its base object first. */
-	if (e->delta)
+	if (e->delta) {
 		offset = write_one(f, e->delta, offset);
+		if (!offset)
+			return offset;
+	}
+	if (offset_limit) {
+		if ( !pack_to_stdout ) {
+			/* save state before write for possible later seekback */
+			save_written = written, save_written_delta = written_delta;
+			save_reused = reused, save_reused_delta = reused_delta;
+			sha1mark(f, &posn);
+		} else if ( (unsigned long)offset >= (unsigned long)offset_limit )
+			/*
+			 * This ensures that no object's offset in the pack
+			 * exceeds or is equal to the offset_limit.  It is
+			 * a looser way of limiting packsize w/o seeking and
+			 * is used in --stdout mode.
+			 */
+			return 0;
+	}
 	e->offset = offset;
-	return offset + write_object(f, e);
+	offset += write_object(f, e);
+	/*
+	 * This ensures that the packfile size never exceeds or matches
+	 * the offset_limit if supplied.  The "20" is for the final SHA1.
+	 * This limit isn't used with --stdout since it requires seeking.
+	 */
+	if (offset_limit && !pack_to_stdout &&
+	    (unsigned long)offset >= (unsigned long)(offset_limit - 20)) {
+		written = save_written, written_delta = save_written_delta;
+		reused = save_reused, reused_delta = save_reused_delta;
+		sha1undo(f, &posn, offset, e->offset);
+		e->offset = 0;
+		return 0;
+	}
+	*written_list++ = e;
+	return offset;
+}
+
+/*
+ * Move this, the version in fast-import.c,
+ * and index_pack.c:readjust_pack_header_and_sha1 into sha1_file.c ?
+ */
+static void fixup_header_footer(int pack_fd, unsigned char *pack_file_sha1,
+				char *pack_name, uint32_t object_count)
+{
+	static const int buf_sz = 128 * 1024;
+	SHA_CTX c;
+	struct pack_header hdr;
+	char *buf;
+
+	if (lseek(pack_fd, 0, SEEK_SET) != 0)
+		die("Failed seeking to start: %s", strerror(errno));
+	if (read_in_full(pack_fd, &hdr, sizeof(hdr)) != sizeof(hdr))
+		die("Unable to reread header of %s", pack_name);
+	if (lseek(pack_fd, 0, SEEK_SET) != 0)
+		die("Failed seeking to start: %s", strerror(errno));
+	hdr.hdr_entries = htonl(object_count);
+	write_or_die(pack_fd, &hdr, sizeof(hdr));
+
+	SHA1_Init(&c);
+	SHA1_Update(&c, &hdr, sizeof(hdr));
+
+	buf = xmalloc(buf_sz);
+	for (;;) {
+		size_t n = xread(pack_fd, buf, buf_sz);
+		if (!n)
+			break;
+		if (n < 0)
+			die("Failed to checksum %s", pack_name);
+		SHA1_Update(&c, buf, n);
+	}
+	free(buf);
+
+	SHA1_Final(pack_file_sha1, &c);
+	write_or_die(pack_fd, pack_file_sha1, 20);
+	close(pack_fd);
 }
 
+typedef int (*entry_sort_t)(const struct object_entry *, const struct object_entry *);
+
+static entry_sort_t current_sort;
+
+/* forward declarations for write_pack_file */
+/* (probably should move sorting stuff up here) */
+static int sort_comparator(const void *_a, const void *_b);
+static int sha1_sort(const struct object_entry *a, const struct object_entry *b);
+static void write_index_file(void);
+
 static void write_pack_file(void)
 {
-	uint32_t i;
+	uint32_t i, j;
 	struct sha1file *f;
 	off_t offset;
 	struct pack_header hdr;
 	unsigned last_percent = 999;
-	int do_progress = progress;
+	int do_progress = progress >> !base_name;
+	char oldname[PATH_MAX];
+	int pack_fd;
+	struct object_entry **list;
+	SHA_CTX ctx;
+	uint32_t nr_actual = nr_result - nr_skipped;
 
-	if (!base_name) {
-		f = sha1fd(1, "<stdout>");
-		do_progress >>= 1;
-	}
-	else
-		f = sha1create("%s-%s.%s", base_name,
-			       sha1_to_hex(object_list_sha1), "pack");
 	if (do_progress)
-		fprintf(stderr, "Writing %u objects.\n", nr_result);
-
-	hdr.hdr_signature = htonl(PACK_SIGNATURE);
-	hdr.hdr_version = htonl(PACK_VERSION);
-	hdr.hdr_entries = htonl(nr_result);
-	sha1write(f, &hdr, sizeof(hdr));
-	offset = sizeof(hdr);
-	if (!nr_result)
-		goto done;
-	for (i = 0; i < nr_objects; i++) {
-		offset = write_one(f, objects + i, offset);
-		if (do_progress) {
-			unsigned percent = written * 100 / nr_result;
-			if (progress_update || percent != last_percent) {
-				fprintf(stderr, "%4u%% (%u/%u) done\r",
-					percent, written, nr_result);
-				progress_update = 0;
-				last_percent = percent;
+		fprintf(stderr, "Writing %u objects.\n", nr_actual);
+	written_list = list = xmalloc(nr_objects * sizeof(struct object_entry *));
+
+	for (i = 0; i < nr_objects;) {
+		if (!base_name) {
+			f = sha1fd(pack_fd = 1, "<stdout>");
+		}
+		else {
+			int len = snprintf(oldname, sizeof oldname, "%s-XXXXXX", base_name);
+			if (len >= PATH_MAX)
+				die("excessive pathname length for initial packfile name");
+			pack_fd = mkstemp(oldname);
+			if (pack_fd < 0)
+				die("can't create %s: %s", oldname, strerror(errno));
+			f = sha1fd(pack_fd, oldname);
+		}
+
+		hdr.hdr_signature = htonl(PACK_SIGNATURE);
+		hdr.hdr_version = htonl(PACK_VERSION);
+		hdr.hdr_entries = htonl(!base_name && offset_limit ? 0 : nr_actual);
+		sha1write(f, &hdr, sizeof(hdr));
+		offset = sizeof(hdr);
+		for (; i < nr_objects; i++) {
+			off_t offset_one = write_one(f, objects + i, offset);
+			if (!offset_one)
+				break;
+			offset = offset_one;
+			if (do_progress) {
+				unsigned percent = written * 100 / nr_actual;
+				if (progress_update || percent != last_percent) {
+					fprintf(stderr, "%4u%% (%u/%u) done\r",
+						percent, written, nr_actual);
+					progress_update = 0;
+					last_percent = percent;
+				}
 			}
 		}
+		nr_written = written_list - list;
+		written_list = list;
+
+		/*
+		 * Write terminator record here if desired:
+		 * type=OBJ_NONE, len=0;  this is a zero byte.
+		 */
+
+		/*
+		 * Did we write the wrong # entries in the header?
+		 * If so, rewrite it like in fast-import (gackk).
+		 */
+		if ( !base_name || nr_written == nr_actual ) {
+			sha1close(f, pack_file_sha1, 1);
+		} else {
+			sha1close(f, pack_file_sha1, -1);
+			fixup_header_footer(pack_fd, pack_file_sha1, oldname, nr_written);
+		}
+
+		/*
+		 * compute object_list_sha1 of sorted sha's we just wrote out;
+		 * we also mark these objects as written
+		 */
+		current_sort = sha1_sort;
+		qsort(list, nr_written, sizeof(struct object_entry *), sort_comparator);
+		SHA1_Init(&ctx);
+		for (j = 0; j < nr_written; j++) {
+			struct object_entry *entry = *list++;
+			entry->no_write = 1;
+			SHA1_Update(&ctx, entry->sha1, 20);
+		}
+		SHA1_Final(object_list_sha1, &ctx);
+		list = written_list;
+		/*
+		 * now we can rename the pack correctly and write the index file
+		 */
+		if (base_name) {
+			char newname[PATH_MAX];
+			int len = snprintf(newname, sizeof newname, "%s-%s.%s",
+						base_name, sha1_to_hex(object_list_sha1), "pack");
+			if (len >= PATH_MAX)
+				die("excessive pathname length for final packfile name");
+			if (rename(oldname, newname) < 0)
+				die("could not rename the pack file");
+		}
+		if (!pack_to_stdout) {
+			write_index_file();
+			puts(sha1_to_hex(object_list_sha1));
+		}
 	}
-	if (do_progress)
+
+	free(written_list);
+	if (nr_actual && do_progress)
 		fputc('\n', stderr);
- done:
-	if (written != nr_result)
-		die("wrote %u objects while expecting %u", written, nr_result);
-	sha1close(f, pack_file_sha1, 1);
+	if (written != nr_actual)
+		die("wrote %u objects while expecting %u", written, nr_actual);
 }
 
 static void write_index_file(void)
@@ -566,8 +724,8 @@ static void write_index_file(void)
 	uint32_t i;
 	struct sha1file *f = sha1create("%s-%s.%s", base_name,
 					sha1_to_hex(object_list_sha1), "idx");
-	struct object_entry **list = sorted_by_sha;
-	struct object_entry **last = list + nr_result;
+	struct object_entry **list = written_list;
+	struct object_entry **last = list + nr_written;
 	uint32_t array[256];
 
 	/*
@@ -583,7 +741,7 @@ static void write_index_file(void)
 				break;
 			next++;
 		}
-		array[i] = htonl(next - sorted_by_sha);
+		array[i] = htonl(next - written_list);
 		list = next;
 	}
 	sha1write(f, array, 256 * 4);
@@ -591,8 +749,8 @@ static void write_index_file(void)
 	/*
 	 * Write the actual SHA1 entries..
 	 */
-	list = sorted_by_sha;
-	for (i = 0; i < nr_result; i++) {
+	list = written_list;
+	for (i = 0; i < nr_written; i++) {
 		struct object_entry *entry = *list++;
 		uint32_t offset = htonl(entry->offset);
 		sha1write(f, &offset, 4);
@@ -1014,7 +1172,7 @@ static void check_object(struct object_entry *entry)
 				ofs = c & 127;
 				while (c & 128) {
 					ofs += 1;
-					if (!ofs || ofs & ~(~0UL >> 7))
+					if (!ofs || ofs & ~(~0UL >> 1))
 						die("delta base offset overflow in pack for %s",
 						    sha1_to_hex(entry->sha1));
 					c = buf[used_0++];
@@ -1058,6 +1216,7 @@ static void check_object(struct object_entry *entry)
 	}
 
 	entry->type = sha1_object_info(entry->sha1, &entry->size);
+	nr_skipped += entry->no_write = blob_limit && (unsigned long)entry->size >= blob_limit;
 	if (entry->type < 0)
 		die("unable to get type of object %s",
 		    sha1_to_hex(entry->sha1));
@@ -1103,10 +1262,6 @@ static void get_object_details(void)
 	}
 }
 
-typedef int (*entry_sort_t)(const struct object_entry *, const struct object_entry *);
-
-static entry_sort_t current_sort;
-
 static int sort_comparator(const void *_a, const void *_b)
 {
 	struct object_entry *a = *(struct object_entry **)_a;
@@ -1197,6 +1352,12 @@ static int try_delta(struct unpacked *trg, struct unpacked *src,
 	if (trg_entry->type != src_entry->type)
 		return -1;
 
+	/* Don't try deltas involving excessively large objects when
+	 * pack size is limited
+	 */
+	if (trg_entry->no_write || src_entry->no_write)
+		return -1;
+
 	/* We do not compute delta to *create* objects we are not
 	 * going to pack.
 	 */
@@ -1538,6 +1699,7 @@ int cmd_pack_objects(int argc, const char **argv, const char *prefix)
 	const char **rp_av;
 	int rp_ac_alloc = 64;
 	int rp_ac;
+	int added = 0;
 
 	rp_av = xcalloc(rp_ac_alloc, sizeof(*rp_av));
 
@@ -1566,6 +1728,24 @@ int cmd_pack_objects(int argc, const char **argv, const char *prefix)
 			incremental = 1;
 			continue;
 		}
+		if (!strcmp("--pack-limit", arg)) {
+			offset_limit = 1UL << 31;
+			continue;
+		}
+		if (!prefixcmp(arg, "--pack-limit=")) {
+			char *end;
+			offset_limit = strtoul(arg+13, &end, 0);
+			if (!arg[13] || *end)
+				usage(pack_usage);
+			continue;
+		}
+		if (!prefixcmp(arg, "--blob-limit=")) {
+			char *end;
+			blob_limit = strtoul(arg+13, &end, 0);
+			if (!arg[13] || *end)
+				usage(pack_usage);
+			continue;
+		}
 		if (!prefixcmp(arg, "--window=")) {
 			char *end;
 			window = strtoul(arg+9, &end, 0);
@@ -1629,6 +1809,24 @@ int cmd_pack_objects(int argc, const char **argv, const char *prefix)
 		}
 		usage(pack_usage);
 	}
+	if ( offset_limit && !blob_limit && !pack_to_stdout ) {
+		/* need to limit blob size when creating bounded packs on disk */
+		blob_limit = offset_limit >> 2;
+		added |= 2;
+	}
+	if ( offset_limit && !no_reuse_delta ) {
+		/* didn't audit this case yet */
+		no_reuse_delta = 1;
+		added |= 1;
+	}
+	if ( added ) {
+		fprintf(stderr, "Added to command line:");
+		if ( added & 1 )
+			fprintf(stderr, " --no-reuse-delta");
+		if ( added & 2 )
+			fprintf(stderr, " --blob-limit=%u", blob_limit);
+		fprintf(stderr, "\n");
+	}
 
 	/* Traditionally "pack-objects [options] base extra" failed;
 	 * we would however want to take refs parameter that would
@@ -1695,10 +1893,6 @@ int cmd_pack_objects(int argc, const char **argv, const char *prefix)
 			progress_update = 0;
 		}
 		write_pack_file();
-		if (!pack_to_stdout) {
-			write_index_file();
-			puts(sha1_to_hex(object_list_sha1));
-		}
 	}
 	if (progress)
 		fprintf(stderr, "Total %u (delta %u), reused %u (delta %u)\n",
diff --git a/builtin-unpack-objects.c b/builtin-unpack-objects.c
index 3956c56..84a6c5c 100644
--- a/builtin-unpack-objects.c
+++ b/builtin-unpack-objects.c
@@ -209,7 +209,7 @@ static void unpack_delta_entry(enum object_type type, unsigned long delta_size,
 		base_offset = c & 127;
 		while (c & 128) {
 			base_offset += 1;
-			if (!base_offset || base_offset & ~(~0UL >> 7))
+			if (!base_offset || base_offset & ~(~0UL >> 1))
 				die("offset value overflow for delta base object");
 			pack = fill(1);
 			c = *pack;
diff --git a/csum-file.c b/csum-file.c
index b7174c6..e2bef75 100644
--- a/csum-file.c
+++ b/csum-file.c
@@ -35,7 +35,10 @@ int sha1close(struct sha1file *f, unsigned char *result, int update)
 	if (offset) {
 		SHA1_Update(&f->ctx, f->buffer, offset);
 		sha1flush(f, offset);
+		f->offset = 0;
 	}
+	if (update < 0)
+		return 0;	/* only want to flush (no checksum write, no close) */
 	SHA1_Final(f->buffer, &f->ctx);
 	if (result)
 		hashcpy(result, f->buffer);
@@ -69,6 +72,44 @@ int sha1write(struct sha1file *f, void *buf, unsigned int count)
 	return 0;
 }
 
+/*
+ * Save current position/state in output file
+ * (needs to be fast -- no system calls!)
+ */
+void sha1mark(struct sha1file *f, struct sha1posn *p)
+{
+	p->offset = f->offset;
+	p->ctx = f->ctx;	/* larger than I'd like */
+}
+
+/*
+ * Restore previous position/state in output file
+ * (can be slow)
+ */
+void sha1undo(struct sha1file *f, struct sha1posn *p, long new, long old)
+{
+	if (new - old == (long)f->offset - (long)p->offset) {
+		f->ctx = p->ctx;
+		f->offset = p->offset;
+		return;
+	}
+	if (lseek(f->fd, (off_t)old - (off_t)p->offset, SEEK_SET) == (off_t)-1)
+		die("sha1 file '%s' undo seekback error (%s)", f->name, strerror(errno));
+	f->ctx = p->ctx;
+	while (p->offset) {
+		int ret = xread(f->fd, f->buffer, p->offset);
+		if (!ret)
+			die("sha1 file '%s' undo readback error. No data", f->name);
+		if (ret < 0)
+			die("sha1 file '%s' undo readback error (%s)", f->name, strerror(errno));
+		SHA1_Update(&f->ctx, f->buffer, ret);
+		p->offset -= ret;
+	}
+	if (ftruncate(f->fd, (off_t)old))
+		die("sha1 file '%s' undo truncate error (%s)", f->name, strerror(errno));
+	f->offset = 0;
+}
+
 struct sha1file *sha1create(const char *fmt, ...)
 {
 	struct sha1file *f;
diff --git a/csum-file.h b/csum-file.h
index 3ad1a99..780df17 100644
--- a/csum-file.h
+++ b/csum-file.h
@@ -9,11 +9,17 @@ struct sha1file {
 	char name[PATH_MAX];
 	unsigned char buffer[8192];
 };
+struct sha1posn {
+	unsigned int offset;
+	SHA_CTX ctx;
+};
 
 extern struct sha1file *sha1fd(int fd, const char *name);
 extern struct sha1file *sha1create(const char *fmt, ...) __attribute__((format (printf, 1, 2)));
 extern int sha1close(struct sha1file *, unsigned char *, int);
 extern int sha1write(struct sha1file *, void *, unsigned int);
 extern int sha1write_compressed(struct sha1file *, void *, unsigned int);
+extern void sha1mark(struct sha1file *, struct sha1posn *);
+extern void sha1undo(struct sha1file *, struct sha1posn *, long, long);
 
 #endif
diff --git a/git-repack.sh b/git-repack.sh
index ddfa8b4..0299ff1 100755
--- a/git-repack.sh
+++ b/git-repack.sh
@@ -18,6 +18,9 @@ do
 	-q)	quiet=-q ;;
 	-f)	no_reuse_delta=--no-reuse-delta ;;
 	-l)	local=--local ;;
+	--pack-limit) extra="$extra $1" ;;
+	--pack-limit=*) extra="$extra $1" ;;
+	--blob-limit=*) extra="$extra $1" ;;
 	--window=*) extra="$extra $1" ;;
 	--depth=*) extra="$extra $1" ;;
 	*)	usage ;;
@@ -62,11 +65,12 @@ case ",$all_into_one," in
 esac
 
 args="$args $local $quiet $no_reuse_delta$extra"
-name=$(git-pack-objects --non-empty --all --reflog $args </dev/null "$PACKTMP") ||
+names=$(git-pack-objects --non-empty --all --reflog $args </dev/null "$PACKTMP") ||
 	exit 1
-if [ -z "$name" ]; then
+if [ -z "$names" ]; then
 	echo Nothing new to pack.
-else
+fi
+for name in $names ; do
 	chmod a-w "$PACKTMP-$name.pack"
 	chmod a-w "$PACKTMP-$name.idx"
 	if test "$quiet" != '-q'; then
@@ -92,7 +96,7 @@ else
 		exit 1
 	}
 	rm -f "$PACKDIR/old-pack-$name.pack" "$PACKDIR/old-pack-$name.idx"
-fi
+done
 
 if test "$remove_redundant" = t
 then
diff --git a/http-fetch.c b/http-fetch.c
index 557b403..09baedc 100644
--- a/http-fetch.c
+++ b/http-fetch.c
@@ -198,7 +198,7 @@ static void start_object_request(struct object_request *obj_req)
 		SHA1_Init(&obj_req->c);
 		if (prev_posn>0) {
 			prev_posn = 0;
-			lseek(obj_req->local, SEEK_SET, 0);
+			lseek(obj_req->local, 0, SEEK_SET);
 			ftruncate(obj_req->local, 0);
 		}
 	}
diff --git a/http-push.c b/http-push.c
index 724720c..e3f7675 100644
--- a/http-push.c
+++ b/http-push.c
@@ -312,7 +312,7 @@ static void start_fetch_loose(struct transfer_request *request)
 		SHA1_Init(&request->c);
 		if (prev_posn>0) {
 			prev_posn = 0;
-			lseek(request->local_fileno, SEEK_SET, 0);
+			lseek(request->local_fileno, 0, SEEK_SET);
 			ftruncate(request->local_fileno, 0);
 		}
 	}
diff --git a/index-pack.c b/index-pack.c
index 6284fe3..d35c4c4 100644
--- a/index-pack.c
+++ b/index-pack.c
@@ -249,7 +249,7 @@ static void *unpack_raw_entry(struct object_entry *obj, union delta_base *delta_
 		base_offset = c & 127;
 		while (c & 128) {
 			base_offset += 1;
-			if (!base_offset || base_offset & ~(~0UL >> 7))
+			if (!base_offset || base_offset & ~(~0UL >> 1))
 				bad_object(obj->offset, "offset value overflow for delta base object");
 			p = fill(1);
 			c = *p;
diff --git a/sha1_file.c b/sha1_file.c
index 9c26038..7082d3e 100644
--- a/sha1_file.c
+++ b/sha1_file.c
@@ -1149,7 +1149,7 @@ static off_t get_delta_base(struct packed_git *p,
 		base_offset = c & 127;
 		while (c & 128) {
 			base_offset += 1;
-			if (!base_offset || base_offset & ~(~0UL >> 7))
+			if (!base_offset || base_offset & ~(~0UL >> 1))
 				die("offset value overflow for delta base object");
 			c = base_info[used++];
 			base_offset = (base_offset << 7) + (c & 127);

Re: [RFC] Packing large repositories

[Shawn O. Pearce]

Geert Bosch <bosch@adacore.com> wrote:
> Actually, I had implemented this first, using two newton-raphson
> iterations and then binary search. With just one iteration is
> too little, and one iteration+binary search often is no win.
> Two iterations followed by binary search cuts the nr of steps in
> half for the Linux kernel. Two iterations followed by linear search
> is often worse, because of "unlucky" cases that end up doing many
> probes. Still, during the 5-8 probes in moderately large repositories
> (1M objects), each probe pretty much requires its own cache line:
> very cache unfriendly.

If Nico and I can ever find the time to get our ideas for pack v4
coded into something executable, I think you will find this is less
of an issue than you think.

We're hoping to change enough of the commit and tree traversal
code that the "tight" loops around chasing tree, parent, and blob
pointers can be done using strictly pack offsets and completely
avoid these SHA-1 lookups.  Thus the only time we'd fall into the
above-mentioned SHA-1 lookup path is on initial entry to a revision
walk, or when spanning to another packfile.  This would mean most
workloads should only hit that code once per command line argument.

-- 
Shawn.