{"thread":{"id":"8320","subject":"[PATCH 1/3] Lazily open pack index files on demand","startedAt":"2007-05-26T05:24:19Z","lastAt":"2007-05-28T18:31:40Z","messageCount":22,"participants":["Shawn O. Pearce","Junio C Hamano","Dana How","Nicolas Pitre","A Large Angry SCM","Linus Torvalds","Karl Hasselström"],"isPatch":true,"patchVersion":1,"patchTotal":3},"messages":[{"id":"43324","messageId":"20070526052419.GA11957@spearce.org","threadId":"8320","inReplyTo":null,"subject":"[PATCH 1/3] Lazily open pack index files on demand","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2007-05-26T05:24:19Z","receivedAt":"2007-05-26T05:24:19Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"In some repository configurations the user may have many packfiles,\nbut all of the recent commits/trees/tags/blobs are likely to\nbe in the most recent packfile (the one with the newest mtime).\nIt is therefore common to be able to complete an entire operation\nby accessing only one packfile, even if there are 25 packfiles\navailable to the repository.\n\nRather than opening and mmaping the corresponding .idx file for\nevery pack found, we now only open and map the .idx when we suspect\nthere might be an object of interest in there.\n\nOf course we cannot known in advance which packfile contains an\nobject, so we still need to scan the entire packed_git list to\nlocate anything. But odds are users want to access objects in the\nmost recently created packfiles first, and that may be all they\never need for the current operation.\n\nJunio observed in b867092f that placing recent packfiles before\nolder ones can slightly improve access times for recent objects,\nwithout degrading it for historical object access.\n\nThis change improves upon Junio's observations by trying even harder\nto avoid the .idx files that we won't need.\n\nSigned-off-by: Shawn O. Pearce \n---\n\n This conflicts (in a subtle way) with Dana How's\n \"sha1_file.c:rearrange_packed_git() should consider packs' object\n sizes\" patch as we now have num_objects = 0 for any indexes we\n have not opened. In the case of Dana's patch this would cause\n those packfiles to have very high ranks, possibly sorting much\n later than they should have.\n\n builtin-count-objects.c | 2 ++\n cache.h | 3 ++-\n pack-check.c | 9 +++++++--\n pack-redundant.c | 3 +++\n sha1_file.c | 38 +++++++++++++++++++++++++++++++++++---\n 5 files changed, 49 insertions(+), 6 deletions(-)\n\ndiff --git a/builtin-count-objects.c b/builtin-count-objects.c\nindex ff90ebd..ac65e03 100644\n--- a/builtin-count-objects.c\n+++ b/builtin-count-objects.c\n@@ -111,6 +111,8 @@ int cmd_count_objects(int ac, const char **av, const char *prefix)\n \t\tfor (p = packed_git; p; p = p->next) {\n \t\t\tif (!p->pack_local)\n \t\t\t\tcontinue;\n+\t\t\tif (!p->index_data && open_pack_index(p))\n+\t\t\t\tcontinue;\n \t\t\tpacked += p->num_objects;\n \t\t\tnum_pack++;\n \t\t}\ndiff --git a/cache.h b/cache.h\nindex cd875bc..0f4a05b 100644\n--- a/cache.h\n+++ b/cache.h\n@@ -485,10 +485,11 @@ extern struct packed_git *find_sha1_pack(const unsigned char *sha1,\n \t\t\t\t\t struct packed_git *packs);\n \n extern void pack_report(void);\n+extern int open_pack_index(struct packed_git *);\n extern unsigned char* use_pack(struct packed_git *, struct pack_window **, off_t, unsigned int *);\n extern void unuse_pack(struct pack_window **);\n extern struct packed_git *add_packed_git(const char *, int, int);\n-extern const unsigned char *nth_packed_object_sha1(const struct packed_git *, uint32_t);\n+extern const unsigned char *nth_packed_object_sha1(struct packed_git *, uint32_t);\n extern off_t find_pack_entry_one(const unsigned char *, struct packed_git *);\n extern void *unpack_entry(struct packed_git *, off_t, enum object_type *, unsigned long *);\n extern unsigned long unpack_object_header_gently(const unsigned char *buf, unsigned long len, enum object_type *type, unsigned long *sizep);\ndiff --git a/pack-check.c b/pack-check.c\nindex d04536b..7475348 100644\n--- a/pack-check.c\n+++ b/pack-check.c\n@@ -129,12 +129,17 @@ static void show_pack_info(struct packed_git *p)\n \n int verify_pack(struct packed_git *p, int verbose)\n {\n-\toff_t index_size = p->index_size;\n-\tconst unsigned char *index_base = p->index_data;\n+\toff_t index_size;\n+\tconst unsigned char *index_base;\n \tSHA_CTX ctx;\n \tunsigned char sha1[20];\n \tint ret;\n \n+\tif (open_pack_index(p))\n+\t\treturn error(\"packfile %s index not opened\", p->pack_name);\n+\tindex_size = p->index_size;\n+\tindex_base = p->index_data;\n+\n \tret = 0;\n \t/* Verify SHA1 sum of the index file */\n \tSHA1_Init(&ctx);\ndiff --git a/pack-redundant.c b/pack-redundant.c\nindex 87077e1..0617320 100644\n--- a/pack-redundant.c\n+++ b/pack-redundant.c\n@@ -550,6 +550,9 @@ static struct pack_list * add_pack(struct packed_git *p)\n \tl.pack = p;\n \tllist_init(&l.all_objects);\n \n+\tif (!p->index_data && open_pack_index(p))\n+\t\treturn NULL;\n+\n \tbase = p->index_data;\n \tbase += 256 * 4 + ((p->index_version < 2) ? 4 : 8);\n \tstep = (p->index_version < 2) ? 24 : 20;\ndiff --git a/sha1_file.c b/sha1_file.c\nindex 12d2ef2..6a5ba63 100644\n--- a/sha1_file.c\n+++ b/sha1_file.c\n@@ -530,6 +530,21 @@ static int check_packed_git_idx(const char *path, struct packed_git *p)\n \treturn 0;\n }\n \n+int open_pack_index (struct packed_git *p)\n+{\n+\tchar *idx_name;\n+\tint ret;\n+\n+\tif (p->index_data)\n+\t\treturn 0;\n+\n+\tidx_name = xstrdup(p->pack_name);\n+\tstrcpy(idx_name + strlen(idx_name) - strlen(\".pack\"), \".idx\");\n+\tret = check_packed_git_idx(idx_name, p);\n+\tfree(idx_name);\n+\treturn ret;\n+}\n+\n static void scan_windows(struct packed_git *p,\n \tstruct packed_git **lru_p,\n \tstruct pack_window **lru_w,\n@@ -605,6 +620,9 @@ static int open_packed_git_1(struct packed_git *p)\n \tunsigned char *idx_sha1;\n \tlong fd_flag;\n \n+\tif (!p->index_data && open_pack_index(p))\n+\t\treturn error(\"packfile %s index unavailable\", p->pack_name);\n+\n \tp->pack_fd = open(p->pack_name, O_RDONLY);\n \tif (p->pack_fd < 0 || fstat(p->pack_fd, &st))\n \t\treturn -1;\n@@ -757,8 +775,7 @@ struct packed_git *add_packed_git(const char *path, int path_len, int local)\n \t\treturn NULL;\n \tmemcpy(p->pack_name, path, path_len);\n \tstrcpy(p->pack_name + path_len, \".pack\");\n-\tif (stat(p->pack_name, &st) || !S_ISREG(st.st_mode) ||\n-\t check_packed_git_idx(path, p)) {\n+\tif (stat(p->pack_name, &st) || !S_ISREG(st.st_mode)) {\n \t\tfree(p);\n \t\treturn NULL;\n \t}\n@@ -766,6 +783,10 @@ struct packed_git *add_packed_git(const char *path, int path_len, int local)\n \t/* ok, it looks sane as far as we can check without\n \t * actually mapping the pack file.\n \t */\n+\tp->index_version = 0;\n+\tp->index_data = NULL;\n+\tp->index_size = 0;\n+\tp->num_objects = 0;\n \tp->pack_size = st.st_size;\n \tp->next = NULL;\n \tp->windows = NULL;\n@@ -1572,10 +1593,15 @@ void *unpack_entry(struct packed_git *p, off_t obj_offset,\n \treturn data;\n }\n \n-const unsigned char *nth_packed_object_sha1(const struct packed_git *p,\n+const unsigned char *nth_packed_object_sha1(struct packed_git *p,\n \t\t\t\t\t uint32_t n)\n {\n \tconst unsigned char *index = p->index_data;\n+\tif (!index) {\n+\t\tif (open_pack_index(p))\n+\t\t\treturn NULL;\n+\t\tindex = p->index_data;\n+\t}\n \tif (n >= p->num_objects)\n \t\treturn NULL;\n \tindex += 4 * 256;\n@@ -1612,6 +1638,12 @@ off_t find_pack_entry_one(const unsigned char *sha1,\n \tconst unsigned char *index = p->index_data;\n \tunsigned hi, lo;\n \n+\tif (!index) {\n+\t\tif (open_pack_index(p))\n+\t\t\treturn 0;\n+\t\tlevel1_ofs = p->index_data;\n+\t\tindex = p->index_data;\n+\t}\n \tif (p->index_version > 1) {\n \t\tlevel1_ofs += 2;\n \t\tindex += 8;\n-- \n1.5.2.789.g8ee1\n"},{"id":"43336","messageId":"7vabvsm1h8.fsf@assigned-by-dhcp.cox.net","threadId":"8320","inReplyTo":"20070526052419.GA11957@spearce.org","subject":"Re: [PATCH 1/3] Lazily open pack index files on demand","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2007-05-26T08:29:55Z","receivedAt":"2007-05-26T08:29:55Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Shawn O. Pearce\" writes:\n\n> This conflicts (in a subtle way) with Dana How's\n> \"sha1_file.c:rearrange_packed_git() should consider packs' object\n> sizes\" patch as we now have num_objects = 0 for any indexes we\n> have not opened. In the case of Dana's patch this would cause\n> those packfiles to have very high ranks, possibly sorting much\n> later than they should have.\n\nI am keeping that rearrange stuff on hold, partly because I am\nmoderately hesitant to do the fp, which feels overkill at that\nlow level of code.\n\nAlso, I am hoping that we can discard that the object density\ncriteria altogether by making the default repack behaviour\nfriendlier to the pathological cases, e.g. by emitting huge\nblobs at the end of the packstream, potentially pushing it out\nto later parts of split packs by themselves and automatically\nmarking them with the .keep flag. Until that kind of\nimprovements materialize, people with pathological cases could\n(1) handcraft a pack that contains only megablob, (2) place that\non central alternate, (3) touch it with artificially old\ntimestamp, which hopefully is a good enough workaround.\n"},{"id":"43356","messageId":"20070526173046.GW28023@spearce.org","threadId":"8320","inReplyTo":"7vabvsm1h8.fsf@assigned-by-dhcp.cox.net","subject":"Re: [PATCH 1/3] Lazily open pack index files on demand","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2007-05-26T17:30:46Z","receivedAt":"2007-05-26T17:30:46Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Junio C Hamano wrote:\n> \"Shawn O. Pearce\" writes:\n> \n> > This conflicts (in a subtle way) with Dana How's\n> > \"sha1_file.c:rearrange_packed_git() should consider packs' object\n> > sizes\" patch as we now have num_objects = 0 for any indexes we\n> > have not opened. In the case of Dana's patch this would cause\n> > those packfiles to have very high ranks, possibly sorting much\n> > later than they should have.\n> \n> I am keeping that rearrange stuff on hold, partly because I am\n> moderately hesitant to do the fp, which feels overkill at that\n> low level of code.\n\nYea, I've actually been having similiar thoughts.\n \n> Also, I am hoping that we can discard that the object density\n> criteria altogether by making the default repack behaviour\n> friendlier to the pathological cases, e.g. by emitting huge\n> blobs at the end of the packstream, potentially pushing it out\n> to later parts of split packs by themselves and automatically\n> marking them with the .keep flag. Until that kind of\n> improvements materialize, people with pathological cases could\n> (1) handcraft a pack that contains only megablob, (2) place that\n> on central alternate, (3) touch it with artificially old\n> timestamp, which hopefully is a good enough workaround.\n\nRight, I was having the same idea. If we have pack-objects just\nshuffle the really big stuff to the end of its object list they\nwill naturally fall into the end of the packfile, and the split\nout packfiles. Then if we do the mtime flipping you suggested\nearlier right before we exit pack-objects the larger blob packs\nwill automatically sort behind the smaller commit/tree packs.\nNo fp needed.\n\nMy patch was exactly because I did what you say above; I handcrafted\na pack that contains only large-ish blobs, placed them into a\ncentral repo, and connected it by alternates. Because of the\nlocal flag logic it is automatically behind my commit/tree pack.\nBut I also rarely (if ever) have to access that megablob packfile.\nYet the .idx was still being opened. On Cygwin/Windows that penalty\nis high enough to have almost doubled the running time of a simple\n\"git show\".\n\n-- \nShawn.\n"},{"id":"43366","messageId":"56b7f5510705261031o311b89bapd730374cbc063931@mail.gmail.com","threadId":"8320","inReplyTo":"7vabvsm1h8.fsf@assigned-by-dhcp.cox.net","subject":"Re: [PATCH 1/3] Lazily open pack index files on demand","fromName":"Dana How","fromEmail":"danahow@gmail.com","sentAt":"2007-05-26T17:31:00Z","receivedAt":"2007-05-26T17:31:00Z","isPatch":true,"sender":{"key":"danahow@gmail.com","avatar":null},"body":"On 5/26/07, Junio C Hamano wrote:\n> \"Shawn O. Pearce\" writes:\n> > This conflicts (in a subtle way) with Dana How's\n> > \"sha1_file.c:rearrange_packed_git() should consider packs' object\n> > sizes\" patch as we now have num_objects = 0 for any indexes we\n> > have not opened. In the case of Dana's patch this would cause\n> > those packfiles to have very high ranks, possibly sorting much\n> > later than they should have.\n> I am keeping that rearrange stuff on hold, partly because I am\n> moderately hesitant to do the fp, which feels overkill at that\n> low level of code.\nOh, I thought the fp might cause a gag reflex -- I had to add -lm.\nUnfortunately, when trying to automatically detect and grade outliers,\nwhich is what I was trying to do, (datum - mean) / std_dev is hard to beat,\nand I needed sqrt for std_dev -- all other fp could be easily written out.\n\n> Also, I am hoping that we can discard that the object density\n> criteria altogether by making the default repack behaviour\n> friendlier to the pathological cases, e.g. by emitting huge\n> blobs at the end of the packstream, potentially pushing it out\n> to later parts of split packs by themselves and automatically\n> marking them with the .keep flag. Until that kind of\n> improvements materialize, people with pathological cases could\n> (1) handcraft a pack that contains only megablob, (2) place that\n> on central alternate, (3) touch it with artificially old\n> timestamp, which hopefully is a good enough workaround.\nI think we should do what we can to make the timestamp as\nmeaningful as possible, which is why I submitted that stamping patch.\n\nI think there are two interesting strategies compatible\nwith maximally-informative timestamps:\n\n(1) git-repack -a -d repacks everything on each call. You would need:\n(1a) Rewrite builtin-pack-objects.c so only the object_ix hash\n accesses the \"objects\" array directly, everything else\n goes through a pointer table.\n(1b) Sort the new pointer table by object type, in order\n tag -> commit -> tree -> nice blob -> naughty blob.\n The sort is stable so the order within each group is unchanged.\n(1c) Do not deltify naughty blobs. Naughty blobs are those\n blobs marked \"nodelta\" or very large blobs.\n(1d) Write out objects in new pointer table order. Splitting\n will cause metadata to be in first pack, naughty blobs\n tend to be in the last pack.\n(1e) When done writing all packs, swap their timestamps\n so current timestamp sorting will look at naughty blobs last.\n\n(2) git-repack -a -d runs in two passes and maintains .keep files:\n(2a) Add a new flag --types=[gctb]+ to pack-objects to be supplied\n by git-repack. This means only taGs/Commits/Trees/Blobs\n are to be passed, all others dropped.\n(2b) Put a new loop around the core of git-repack. In the first iteration,\n pack with --types=b, then with --types=gct in the second.\n Thus metadata will have more recent timestamp.\n(2c) If packs are split, also swap timestamps like in (1e),\n within each iteration.\n(2d) If an iteration produces split packs, mark all but the last\n in the sequence with a .keep file automatically. The\n .keep files contain the string \"repack\".\n(2e) Add new option to repack: -A. If specified, the first\n thing repack does is remove any keep file containing \"repack\".\n(2f) The existing response of repack to keep files -- do not repack them --\n is retained to ensure on each -a/not -A repack, we only\n repack the tail of each set of packs: metadata, data.\n The metadata set will probably only ever contain one pack\n and will always be repacked.\n\nI've (badly) implemented (1b) and confirmed it had no impact\non linux-2.6 repo. I've also implemented (2a), (2b), (2d), and (2f),\nbut not fully measured them. I'd like to finish this work, but\n\"megapacks\" are very time-consuming to manipulate, and\nwith the loose megablob approach they are not as useful for me.\n\nFinally, some people might want more esoteric repacking\nstrategies than what I've listed above. We could add a\n--packed flag to pack-objects to help them. This means that\ngit pack-objects --packed --unpacked= --unpacked=\nwould only repack pack1 and pack2 and would not absorb\nany loose blobs. This would allow you to maintain any number\nof packfile classes you want and maintain them yourself.\nEach would be indicated by something different in a .keep file.\n(To newly absorb loose blobs in a class, you would do\n cat object-list | git-pack-objects --incremental\nfrom some object-list you built following your rules).\nThese strategies would be too special-purpose to be in git,\nbut adding --packed is a small and useful change.\n\nShawn: When I first saw the index-loading code, my first\nthought was that all the index tables should be\nmerged (easy since sorted) so callers only need to do one search.\nWith indices loaded lazily, either you can't merge, or you\nmerge sequentially, raising merge cost from (total entries) to\nalmost (index files) * (total entries). What do you think about\nmerging the SHA-1 tables, and how would/should it interact with\nlazy index file loading?\n\nBTW, if it's not apparent, I think my object density patch\nshould be dropped. It has served its purpose as a thought experiment.\n\nThanks,\n-- \nDana L. How danahow@gmail.com +1 650 804 5991 cell\n"},{"id":"43386","messageId":"alpine.LFD.0.99.0705262223540.3366@xanadu.home","threadId":"8320","inReplyTo":"56b7f5510705261031o311b89bapd730374cbc063931@mail.gmail.com","subject":"Re: [PATCH 1/3] Lazily open pack index files on demand","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2007-05-27T02:43:36Z","receivedAt":"2007-05-27T02:43:36Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Sat, 26 May 2007, Dana How wrote:\n\n> I think there are two interesting strategies compatible\n> with maximally-informative timestamps:\n> \n> (1) git-repack -a -d repacks everything on each call. You would need:\n> (1a) Rewrite builtin-pack-objects.c so only the object_ix hash\n> accesses the \"objects\" array directly, everything else\n> goes through a pointer table.\n> (1b) Sort the new pointer table by object type, in order\n> tag -> commit -> tree -> nice blob -> naughty blob.\n> The sort is stable so the order within each group is unchanged.\n\nThis is not a good idea in general for runtime access to the pack. If \nyou consider a checkout, the commit object \nis looked up, then the root tree object, then each tree entry is \nrecursively looked up. Right now the way the objects are laid out, the \nmost recent commit will have all its objects contiguously found in the \npack and in the right order (that means tree and blobs mixed up). This \ngets less and less true as you go back into history, but at least the \nrecent stuff has a really nice access pattern.\n\nBecause commit objects are so fundamental to many graph operations they \nare already all packed together. But tree and blob objects are \nintermixed for the reason stated above.\n\nThe naughty blob is a really special category and I think they should be \ntreated as such. Therefore I don't think the common/normal case should \nbe impacted with a generic change for something that is still a special \ncase.\n\nIn other words, I think the naughty blob could simply be recognized as \nsuch and be referenced in a special list instead of being written out \ninitially. Then when everything is believed to be written, the special \nlist can be walked to force write those naughty blob at last. No need \nto modify the current object order.\n\n\nNicolas\n"},{"id":"43390","messageId":"20070527033429.GY28023@spearce.org","threadId":"8320","inReplyTo":"56b7f5510705261031o311b89bapd730374cbc063931@mail.gmail.com","subject":"Re: [PATCH 1/3] Lazily open pack index files on demand","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2007-05-27T03:34:29Z","receivedAt":"2007-05-27T03:34:29Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Dana How wrote:\n> Shawn: When I first saw the index-loading code, my first\n> thought was that all the index tables should be\n> merged (easy since sorted) so callers only need to do one search.\n\nYes; in fact this has been raised on the list before. The general\nidea was to create some sort of \"super index\" that had a list of\nall objects and which packfile they could be found in. This way the\nrunning process doesn't have to search multiple indexes, and the\nprocess doesn't have to be responsible for the merging itself.\n\nSee the thing is, if you read all of every .idx file on a simple\n`git-log` operation you've already lost. The number of trees and\nblobs tends to far outweigh the number of commits and they really\noutweigh the number of commits the average user looks at in a\n`git-log` session before they abort their pager. So sorting all\nof the available .idx files before we produce even the first commit\nis a horrible thing to do.\n\nBut the problem with a super index is repacking. Every time the user\nrepacks their recent loose objects (or recently fetched packs) we are\nfolding some packfiles together, but may be leaving others alone.\nThe super index would need to account for the packfiles we aren't\nlooking at or repacking. It gets complicated fast.\n\nThere's also the problem of alternate ODBs; do we fold the indexes\nof our alternates into our own super index? Or does each ODB get\nits own super index and we still have to load multiple super index\nfiles?\n\nIn pack v4 we're likely to move the SHA-1 table from the .idx file\ninto the front of the .pack file. This makes the .idx file hold\nonly the offsets and the CRC checkums of each object. If we start\nmaking a super index, we have to duplicate the SHA-1 table twice\n(once in the .pack, again in the super index).\n\n-- \nShawn.\n"},{"id":"43391","messageId":"56b7f5510705262131g2d4186a0q605abbcea624d42d@mail.gmail.com","threadId":"8320","inReplyTo":"alpine.LFD.0.99.0705262223540.3366@xanadu.home","subject":"Re: [PATCH 1/3] Lazily open pack index files on demand","fromName":"Dana How","fromEmail":"danahow@gmail.com","sentAt":"2007-05-27T04:31:18Z","receivedAt":"2007-05-27T04:31:18Z","isPatch":true,"sender":{"key":"danahow@gmail.com","avatar":null},"body":"On 5/26/07, Nicolas Pitre wrote:\n> On Sat, 26 May 2007, Dana How wrote:\n> > (1) git-repack -a -d repacks everything on each call. You would need:\n> > (1a) Rewrite builtin-pack-objects.c so only the object_ix hash\n> > accesses the \"objects\" array directly, everything else\n> > goes through a pointer table.\n> > (1b) Sort the new pointer table by object type, in order\n> > tag -> commit -> tree -> nice blob -> naughty blob.\n> > The sort is stable so the order within each group is unchanged.\n>\n> Because commit objects are so fundamental to many graph operations they\n> are already all packed together. But tree and blob objects are\n> intermixed for the reason stated above.\nI noticed that all the commits were together and\nwondered if that was deliberate.\n\n> The naughty blob is a really special category and I think they should be\n> treated as such. Therefore I don't think the common/normal case should\n> be impacted with a generic change for something that is still a special\n> case.\nThis argument makes sense.\n\n> In other words, I think the naughty blob could simply be recognized as\n> such and be referenced in a special list instead of being written out\n> initially. Then when everything is believed to be written, the special\n> list can be walked to force write those naughty blob at last. No need\n> to modify the current object order.\nThis works as long as a naughty blob can't be a delta base for a nice blob\n(causing it to be pushed out early by the recursion in write_one()).\nI think that's a reasonable and understandable restriction.\n\nThanks,\n-- \nDana L. How danahow@gmail.com +1 650 804 5991 cell\n"},{"id":"43392","messageId":"56b7f5510705262140rea5e1e5r49bdd5e99c466daa@mail.gmail.com","threadId":"8320","inReplyTo":"20070527033429.GY28023@spearce.org","subject":"Re: [PATCH 1/3] Lazily open pack index files on demand","fromName":"Dana How","fromEmail":"danahow@gmail.com","sentAt":"2007-05-27T04:40:42Z","receivedAt":"2007-05-27T04:40:42Z","isPatch":true,"sender":{"key":"danahow@gmail.com","avatar":null},"body":"On 5/26/07, Shawn O. Pearce wrote:\n> Dana How wrote:\n> > Shawn: When I first saw the index-loading code, my first\n> > thought was that all the index tables should be\n> > merged (easy since sorted) so callers only need to do one search.\n>\n> Yes; in fact this has been raised on the list before. The general\n> idea was to create some sort of \"super index\" that had a list of\n> all objects and which packfile they could be found in. This way the\n> running process doesn't have to search multiple indexes, and the\n> process doesn't have to be responsible for the merging itself.\n>\n> See the thing is, if you read all of every .idx file on a simple\n> `git-log` operation you've already lost. The number of trees and\n> blobs tends to far outweigh the number of commits and they really\n> outweigh the number of commits the average user looks at in a\n> `git-log` session before they abort their pager. So sorting all\n> of the available .idx files before we produce even the first commit\n> is a horrible thing to do.\n>\n> But the problem with a super index is repacking. Every time the user\n> repacks their recent loose objects (or recently fetched packs) we are\n> folding some packfiles together, but may be leaving others alone.\n> The super index would need to account for the packfiles we aren't\n> looking at or repacking. It gets complicated fast.\n>\n> There's also the problem of alternate ODBs; do we fold the indexes\n> of our alternates into our own super index? Or does each ODB get\n> its own super index and we still have to load multiple super index\n> files?\nYes, the problem is that even an on-demand, \"lazy\" merge\nis likely to require far more work than the expected number of index probes.\n\n> In pack v4 we're likely to move the SHA-1 table from the .idx file\n> into the front of the .pack file. This makes the .idx file hold\n> only the offsets and the CRC checkums of each object. If we start\n> making a super index, we have to duplicate the SHA-1 table twice\n> (once in the .pack, again in the super index).\nHmm, hopefully the SHA-1 table can go at the _end_\nsince with split packs that's the only time we know the number\nof objects in the pack... ;-)\n\nThanks,\n-- \nDana L. How danahow@gmail.com +1 650 804 5991 cell\n"},{"id":"43432","messageId":"alpine.LFD.0.99.0705271039170.3366@xanadu.home","threadId":"8320","inReplyTo":"56b7f5510705262131g2d4186a0q605abbcea624d42d@mail.gmail.com","subject":"Re: [PATCH 1/3] Lazily open pack index files on demand","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2007-05-27T14:41:38Z","receivedAt":"2007-05-27T14:41:38Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Sat, 26 May 2007, Dana How wrote:\n\n> On 5/26/07, Nicolas Pitre wrote:\n> > In other words, I think the naughty blob could simply be recognized as\n> > such and be referenced in a special list instead of being written out\n> > initially. Then when everything is believed to be written, the special\n> > list can be walked to force write those naughty blob at last. No need\n> > to modify the current object order.\n> This works as long as a naughty blob can't be a delta base for a nice blob\n> (causing it to be pushed out early by the recursion in write_one()).\n> I think that's a reasonable and understandable restriction.\n\nSure. Or the delta can inherit the naughty property if its base is also \nnaughty, which solves the problem nicely.\n\n\nNicolas\n"},{"id":"43435","messageId":"alpine.LFD.0.99.0705271110550.3366@xanadu.home","threadId":"8320","inReplyTo":"20070527033429.GY28023@spearce.org","subject":"Re: [PATCH 1/3] Lazily open pack index files on demand","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2007-05-27T15:26:06Z","receivedAt":"2007-05-27T15:26:06Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Sat, 26 May 2007, Shawn O. Pearce wrote:\n\n> Dana How wrote:\n> > Shawn: When I first saw the index-loading code, my first\n> > thought was that all the index tables should be\n> > merged (easy since sorted) so callers only need to do one search.\n> \n> Yes; in fact this has been raised on the list before. The general\n> idea was to create some sort of \"super index\" that had a list of\n> all objects and which packfile they could be found in. This way the\n> running process doesn't have to search multiple indexes, and the\n> process doesn't have to be responsible for the merging itself.\n> \n> See the thing is, if you read all of every .idx file on a simple\n> `git-log` operation you've already lost. The number of trees and\n> blobs tends to far outweigh the number of commits and they really\n> outweigh the number of commits the average user looks at in a\n> `git-log` session before they abort their pager. So sorting all\n> of the available .idx files before we produce even the first commit\n> is a horrible thing to do.\n\nThere is also the question of memory footprint. If you have a global \nindex, then for each object you need to have a tupple containing SHA1 + \npack offset + reference to corresponding pack. Right now we only need \nSHA1 + pack offset.\n\nBTW I think the Newton-Raphson based index lookup approach should be \nrevived at some point.\n\n\nNicolas\n"},{"id":"43436","messageId":"alpine.LFD.0.99.0705271127110.3366@xanadu.home","threadId":"8320","inReplyTo":"56b7f5510705262140rea5e1e5r49bdd5e99c466daa@mail.gmail.com","subject":"Re: [PATCH 1/3] Lazily open pack index files on demand","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2007-05-27T15:29:17Z","receivedAt":"2007-05-27T15:29:17Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Sat, 26 May 2007, Dana How wrote:\n\n> On 5/26/07, Shawn O. Pearce wrote:\n> > In pack v4 we're likely to move the SHA-1 table from the .idx file\n> > into the front of the .pack file. This makes the .idx file hold\n> > only the offsets and the CRC checkums of each object. If we start\n> > making a super index, we have to duplicate the SHA-1 table twice\n> > (once in the .pack, again in the super index).\n> Hmm, hopefully the SHA-1 table can go at the _end_\n> since with split packs that's the only time we know the number\n> of objects in the pack... ;-)\n\nHmmm good point to consider.\n\n\nNicolas\n"},{"id":"43440","messageId":"56b7f5510705270906u54792b40g621313d197880fc0@mail.gmail.com","threadId":"8320","inReplyTo":"alpine.LFD.0.99.0705271110550.3366@xanadu.home","subject":"Re: [PATCH 1/3] Lazily open pack index files on demand","fromName":"Dana How","fromEmail":"danahow@gmail.com","sentAt":"2007-05-27T16:06:22Z","receivedAt":"2007-05-27T16:06:22Z","isPatch":true,"sender":{"key":"danahow@gmail.com","avatar":null},"body":"On 5/27/07, Nicolas Pitre wrote:\n> BTW I think the Newton-Raphson based index lookup approach should be\n> revived at some point.\nYes.\n\n I think if we figure out the statistics we could win big.\nI thought about it a bit when it was first discussed\nbut need to return to it.\n\nThanks,\n-- \nDana L. How danahow@gmail.com +1 650 804 5991 cell\n"},{"id":"43458","messageId":"20070527213525.GC28023@spearce.org","threadId":"8320","inReplyTo":"alpine.LFD.0.99.0705271127110.3366@xanadu.home","subject":"Re: [PATCH 1/3] Lazily open pack index files on demand","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2007-05-27T21:35:25Z","receivedAt":"2007-05-27T21:35:25Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Nicolas Pitre wrote:\n> On Sat, 26 May 2007, Dana How wrote:\n> \n> > On 5/26/07, Shawn O. Pearce wrote:\n> > > In pack v4 we're likely to move the SHA-1 table from the .idx file\n> > > into the front of the .pack file. This makes the .idx file hold\n> > > only the offsets and the CRC checkums of each object. If we start\n> > > making a super index, we have to duplicate the SHA-1 table twice\n> > > (once in the .pack, again in the super index).\n> > \n> > Hmm, hopefully the SHA-1 table can go at the _end_\n> > since with split packs that's the only time we know the number\n> > of objects in the pack... ;-)\n> \n> Hmmm good point to consider.\n\nThe problem with putting the SHA-1 table at the end of the pack is\nit ruins the streaming for both unpack-objects and index-pack if\nwe were to ever use pack v4 as a transport format. Or just try\nto run a pack v4 packfile through unpack-objects, just locally,\nsay to extract megablobs. ;-)\n\n-- \nShawn.\n"},{"id":"43460","messageId":"20070527215245.GD28023@spearce.org","threadId":"8320","inReplyTo":"alpine.LFD.0.99.0705271110550.3366@xanadu.home","subject":"Re: [PATCH 1/3] Lazily open pack index files on demand","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2007-05-27T21:52:45Z","receivedAt":"2007-05-27T21:52:45Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Nicolas Pitre wrote:\n> On Sat, 26 May 2007, Shawn O. Pearce wrote:\n> \n> > Dana How wrote:\n> > > Shawn: When I first saw the index-loading code, my first\n> > > thought was that all the index tables should be\n> > > merged (easy since sorted) so callers only need to do one search.\n> \n> There is also the question of memory footprint. If you have a global \n> index, then for each object you need to have a tupple containing SHA1 + \n> pack offset + reference to corresponding pack. Right now we only need \n> SHA1 + pack offset.\n\nI'm about half-way through a super-index implementation. Right now\nthe super-index is defined to be just one index file per repository\n(objects/pack/super.index) with a format that looks like the\nfollowing:\n\n header:\n uint32_t sdx_signature ('PSDX')\n uint32_t sdx_version (1)\n uint16_t sdx_packs\n uint8_t sdx_prefix_len;\n uint8_t __reserved;\n\n pack table:\n /* SHA-1 of each pack's sorted SHA-1 object list */\n unsigned char pack_sha1[20][sdx_packs];\n\n fan-out table:\n /* This is the standard fan-out also used in a tOc/.idx */\n uint32_t fan_out[256];\n\n records:\n unsigned char prefix[hdr.sdx_prefix_len - 1];\n int8_t splits[hdr.sdx_packs];\n\n trailer:\n unsigned char sha1_of_the_above[20];\n\nI build the super-index by merging the .idx of all available\npackfiles; since they are already sorted the merge is obviously\nquite trivial.\n\nThe sdx_prefix_len field is initialized to something that gives a\nreasonably unique object name; e.g. in git.git an sdx_prefix_len\nof 3 or 4 gets pretty good at narrowing the set of objects down\nvery small. The idea here is that the sdx_prefix_len should be\nalmost the unique abbreviation length for this repository.\n\nWe store 1 less byte of the prefix in the record because of the\nfan-out table already accounting for the first byte of the prefix.\n\nThe splits array contains a single signed integer for each packfile;\nif the integer is 0 then that packfile does not contain any object\nthat starts with that corresponding prefix. In such a case we\ncan completely avoid looking at that corresponding packfile.\nWith my lazy index loading change, I may not even need to open\nthat index. ;-)\n\nIf the splits array entry is non-zero and is negative, its the number\nof times we need to halve down (towards 'lo') to get to entries\nthat start with this prefix and that are in that packfile's fan-out\ntable entry range. If its positive its the number of times we have\nto halve up (towards 'hi'). This way we can jump more directly to\nthe relevant index records and avoid redoing binary search work we\nhave already accomplished in the super index.\n\nSo we can generally build super index records at a cost of 3 or\n4 bytes + sdx_packs. We can also determine which packfile(s) we\nneed to scan quite quickly, and we can jump further into the part\nof the index avoiding a number of expensive hashcmp() calls. It\nmay actually be a good savings at runtime, well worth the slightly\nhigher memory footprint.\n\nMy testing is not yet complete, so I cannot offer any hard numbers\nagainst any interesting/common data sets...\n \n> BTW I think the Newton-Raphson based index lookup approach should be \n> revived at some point.\n\nThat doesn't help with 10 packfiles though, does it?\n\n-- \nShawn.\n"},{"id":"43473","messageId":"alpine.LFD.0.99.0705271929480.3366@xanadu.home","threadId":"8320","inReplyTo":"20070527215245.GD28023@spearce.org","subject":"Re: [PATCH 1/3] Lazily open pack index files on demand","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2007-05-27T23:35:16Z","receivedAt":"2007-05-27T23:35:16Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Sun, 27 May 2007, Shawn O. Pearce wrote:\n\n> Nicolas Pitre wrote:\n> > BTW I think the Newton-Raphson based index lookup approach should be \n> > revived at some point.\n> \n> That doesn't help with 10 packfiles though, does it?\n\nIt helps irrespective of the number of pack files. With the current \nbinary search the lookup cost is O(log n). With a Newton method this \ncost is almost O(1). If you have 10 pack files then you may have to do \n5 separate lookups on average, but those lookups are still faster with a \nNewton method.\n\n\nNicolas\n"},{"id":"43480","messageId":"56b7f5510705271835m5a375324p3a908fe766fdf902@mail.gmail.com","threadId":"8320","inReplyTo":"20070527213525.GC28023@spearce.org","subject":"Re: [PATCH 1/3] Lazily open pack index files on demand","fromName":"Dana How","fromEmail":"danahow@gmail.com","sentAt":"2007-05-28T01:35:47Z","receivedAt":"2007-05-28T01:35:47Z","isPatch":true,"sender":{"key":"danahow@gmail.com","avatar":null},"body":"On 5/27/07, Shawn O. Pearce wrote:\n> Nicolas Pitre wrote:\n> > On Sat, 26 May 2007, Dana How wrote:\n> > > On 5/26/07, Shawn O. Pearce wrote:\n> > > > In pack v4 we're likely to move the SHA-1 table from the .idx file\n> > > > into the front of the .pack file. This makes the .idx file hold\n> > > > only the offsets and the CRC checkums of each object. If we start\n> > > > making a super index, we have to duplicate the SHA-1 table twice\n> > > > (once in the .pack, again in the super index).\n> > > Hmm, hopefully the SHA-1 table can go at the _end_\n> > > since with split packs that's the only time we know the number\n> > > of objects in the pack... ;-)\n> > Hmmm good point to consider.\n> The problem with putting the SHA-1 table at the end of the pack is\n> it ruins the streaming for both unpack-objects and index-pack if\n> we were to ever use pack v4 as a transport format. Or just try\n> to run a pack v4 packfile through unpack-objects, just locally,\n> say to extract megablobs. ;-)\n\nPerhaps I have stumbled on another issue related to\nincluding SHA-1s in packfiles. This is completely independent\nof the handling of megablobs (my current focus), but the presence\nof large blobs do make this issue more apparent.\n\nSome history of what I've been doing with git:\nFirst I simply had to import the repo,\nwhich led to split packs (this was before index v2).\nThen maintaining the repo led to the unfinished maxblobsize stuff.\nDistributing the repo included users pulling (usually) from the central repo,\nwhich would be trivial since it was also an alternate.\nLocal repacking would avoid heavy load on it.\n\nNow I've started looking into how to push back into the\ncentral repo from a user's repo (not everything will be central;\nsome pulling between users will occur\notherwise I wouldn't be as interested).\n\nIt looks like the entire sequence is:\nA. git add file [compute SHA-1 & compress file into objects/xx]\nB. git commit [write some small objects locally]\nC. git push {using PROTO_LOCAL}:\n 1. read & uncompress objects\n 2. recompress objects into a pack and send through a pipe\n 3. read pack on other end of pipe and uncompress each object\n 4. compute SHA-1 for each object and compress file into objects/xx\n\nSo, after creating an object in the local working tree,\nto get it into the central repo, we must:\ncompress -> uncompress -> compress -> uncompress -> compress.\nIn responsiveness this won't compare very well to Perforce,\nwhich has only one compress step.\n\nThe sequence above could be somewhat different currently in git.\nThe user might have repacked their repo before pushing,\nbut this just moves C1 and C2 back earlier in time,\nit doesn't remove the need for them. Besides, the blobs in\na push are more likely to be recent and hence unpacked.\n\nAlso, C3 and C4 might not happen if more than 100 blobs get pushed.\nBut this seems very unusual; only 0.3% of commits in the history\nhad 100+ new files/file contents. If the 100 level is reduced,\nthen the central repo fills up with packfiles and their index files,\nreducing performance for everybody (using the central repo as an alternate).\n\nThus there really is 5X more compression activity going on\ncompared to Perforce. How can this be reduced?\n\nOne way is to restore the ability to write the \"new\" loose object format.\nThen C1, C2, and C4 disappear. C3 must remain because we need\nto uncompress the object to compute its SHA-1; we don't need\nto recompress since we were already given the compressed form.\n\nAnd that final sentence is why I sent this email: if the packfile\ncontained the SHA-1s, either at the beginning or before each object,\nthen they wouldn't need to be recomputed at the receiving end\nand the extra decompression could be skipped as well. This would\nmake the total zlib effort the same as Perforce.\n\nThe fact that a loose object is never overwritten would still be retained.\nIs that sufficient security? Or does the SHA-1 always need to be\nrecomputed on the receiving end? Could that be skipped just for\nspecific connections and/or protocols (presumably \"trusted\" ones)?\n\nNote that none of this depends on how megablobs are handled,\nbut large blobs certainly do make the 5X more zlib activity more apparent.\n\nShawn: I think you mentioned something related to this a few days ago.\nAlso, you didn't like split packs putting SHA-1s at the end because\nthat messed up streaming for transport, but packs are not split for transport.\n\nThanks,\n-- \nDana L. How danahow@gmail.com +1 650 804 5991 cell\n"},{"id":"43482","messageId":"alpine.LFD.0.99.0705272207280.3366@xanadu.home","threadId":"8320","inReplyTo":"20070527213525.GC28023@spearce.org","subject":"Re: [PATCH 1/3] Lazily open pack index files on demand","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2007-05-28T02:18:26Z","receivedAt":"2007-05-28T02:18:26Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Sun, 27 May 2007, Shawn O. Pearce wrote:\n\n> Nicolas Pitre wrote:\n> > On Sat, 26 May 2007, Dana How wrote:\n> > \n> > > On 5/26/07, Shawn O. Pearce wrote:\n> > > > In pack v4 we're likely to move the SHA-1 table from the .idx file\n> > > > into the front of the .pack file. This makes the .idx file hold\n> > > > only the offsets and the CRC checkums of each object. If we start\n> > > > making a super index, we have to duplicate the SHA-1 table twice\n> > > > (once in the .pack, again in the super index).\n> > > \n> > > Hmm, hopefully the SHA-1 table can go at the _end_\n> > > since with split packs that's the only time we know the number\n> > > of objects in the pack... ;-)\n> > \n> > Hmmm good point to consider.\n> \n> The problem with putting the SHA-1 table at the end of the pack is\n> it ruins the streaming for both unpack-objects and index-pack if\n> we were to ever use pack v4 as a transport format. Or just try\n> to run a pack v4 packfile through unpack-objects, just locally,\n> say to extract megablobs. ;-)\n\nRight. In fact I think the SHA1 table could still remain at the \nbeginning even if we don't know yet that the pack will be split. It \nwould just happen to contain redundent entries.\n\nIn fact it would be impossible to store it at the end in the hope of \ntrimming it down according to the written objects because the idea is to \nhave commit and tree objects index into that table. So if you cull \nentries from the table then indices in already written out objects won't \nmatch.\n\n\nNicolas\n"},{"id":"43483","messageId":"465A3EB9.7090403@gmail.com","threadId":"8320","inReplyTo":"56b7f5510705271835m5a375324p3a908fe766fdf902@mail.gmail.com","subject":"Re: [PATCH 1/3] Lazily open pack index files on demand","fromName":"A Large Angry SCM","fromEmail":"gitzilla@gmail.com","sentAt":"2007-05-28T02:30:17Z","receivedAt":"2007-05-28T02:30:17Z","isPatch":true,"sender":{"key":"gitzilla@gmail.com","avatar":"https://gravatar.com/avatar/354625c442439908ff3dd99757dee330e29e9df7847472384faf7a00add247fb?d=mp&s=160"},"body":"Dana How wrote:\n[...]\n> \n> Some history of what I've been doing with git:\n> First I simply had to import the repo,\n> which led to split packs (this was before index v2).\n> Then maintaining the repo led to the unfinished maxblobsize stuff.\n> Distributing the repo included users pulling (usually) from the central \n> repo,\n> which would be trivial since it was also an alternate.\n> Local repacking would avoid heavy load on it.\n> \n> Now I've started looking into how to push back into the\n> central repo from a user's repo (not everything will be central;\n> some pulling between users will occur\n> otherwise I wouldn't be as interested).\n> \n> It looks like the entire sequence is:\n> A. git add file [compute SHA-1 & compress file into objects/xx]\n> B. git commit [write some small objects locally]\n> C. git push {using PROTO_LOCAL}:\n> 1. read & uncompress objects\n> 2. recompress objects into a pack and send through a pipe\n> 3. read pack on other end of pipe and uncompress each object\n> 4. compute SHA-1 for each object and compress file into objects/xx\n> \n> So, after creating an object in the local working tree,\n> to get it into the central repo, we must:\n> compress -> uncompress -> compress -> uncompress -> compress.\n> In responsiveness this won't compare very well to Perforce,\n> which has only one compress step.\n> \n> The sequence above could be somewhat different currently in git.\n> The user might have repacked their repo before pushing,\n> but this just moves C1 and C2 back earlier in time,\n> it doesn't remove the need for them. Besides, the blobs in\n> a push are more likely to be recent and hence unpacked.\n> \n> Also, C3 and C4 might not happen if more than 100 blobs get pushed.\n> But this seems very unusual; only 0.3% of commits in the history\n> had 100+ new files/file contents. If the 100 level is reduced,\n> then the central repo fills up with packfiles and their index files,\n> reducing performance for everybody (using the central repo as an \n> alternate).\n> \n> Thus there really is 5X more compression activity going on\n> compared to Perforce. How can this be reduced?\n> \n> One way is to restore the ability to write the \"new\" loose object format.\n> Then C1, C2, and C4 disappear. C3 must remain because we need\n> to uncompress the object to compute its SHA-1; we don't need\n> to recompress since we were already given the compressed form.\n> \n> And that final sentence is why I sent this email: if the packfile\n> contained the SHA-1s, either at the beginning or before each object,\n> then they wouldn't need to be recomputed at the receiving end\n> and the extra decompression could be skipped as well. This would\n> make the total zlib effort the same as Perforce.\n> \n> The fact that a loose object is never overwritten would still be retained.\n> Is that sufficient security? Or does the SHA-1 always need to be\n> recomputed on the receiving end? Could that be skipped just for\n> specific connections and/or protocols (presumably \"trusted\" ones)?\n[...]\n\nSo how do you want to decide when to trust the sender and when to \nvalidate that the objects received have the SHA-1's claimed? A _central_ \nrepository, being authoritative, would need to _always_ validate _all_ \nobjects it receives. An since, with a central repository setup, the \ncentral repository is where the CPU resources are the most in demand, \nvalidating the object IDs when received at the developers repositories \nshould not be a problem. And just to be fair, how does Perforce \nguarantee that the retrieved version of a file matches what was checked in?\n"},{"id":"43495","messageId":"alpine.LFD.0.98.0705280907290.26602@woody.linux-foundation.org","threadId":"8320","inReplyTo":"alpine.LFD.0.99.0705271929480.3366@xanadu.home","subject":"Re: [PATCH 1/3] Lazily open pack index files on demand","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-05-28T16:22:02Z","receivedAt":"2007-05-28T16:22:02Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Sun, 27 May 2007, Nicolas Pitre wrote:\n> \n> It helps irrespective of the number of pack files. With the current \n> binary search the lookup cost is O(log n). With a Newton method this \n> cost is almost O(1).\n\nThis is not true.\n\nFirst off, when comparing O(logn) to O(1), with \"n\" being less than a \nbillion, they are pretty much exactly the same. Think of it this way: \nO(logn) == O(9) == O(1), if you know that n < 10**9.\n\nSecondly, the cost of Newton isn't \"almost O(1)\". I don't know _what_ it \nis (the rule of thumb with Newton-Raphson should be that the number of \nsignificant correct digits in the answer doubles with each iteration: I \nthink that probably means that it should approximate O(loglog(n)), but I \nhaven't thought deeply about it.\n\nBut regardless, we end up testing \"a few\" values. Both for the binary \nsearch and for Newton-Raphson.\n\nSo every time you talk about O-notation, you should also consider the \nconstant costs, especially if the function in question is a slow-changing \none (ie when we start talking O(N**3) we can start ignoring the constants. \nWith O(logn), you sure as hell cannot!)\n\nAnd the thing is, Newton-Raphson didn't actually speed anything up in my \ntests. Sometimes it was better, sometimes it was worse, most of the time \nit was in the noise.\n\nNow, I'm sure the thing could be tweaked. Maybe I didn't do a very good \njob at my initial implementation. It was a quick hack. But before somebody \nmakes a better one and actually shows better performance, I'd say that the \njury is still out.\n\n\t\tLinus\n"},{"id":"43502","messageId":"alpine.LFD.0.99.0705281242210.11491@xanadu.home","threadId":"8320","inReplyTo":"alpine.LFD.0.98.0705280907290.26602@woody.linux-foundation.org","subject":"Re: [PATCH 1/3] Lazily open pack index files on demand","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2007-05-28T17:13:19Z","receivedAt":"2007-05-28T17:13:19Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Mon, 28 May 2007, Linus Torvalds wrote:\n\n> On Sun, 27 May 2007, Nicolas Pitre wrote:\n> > \n> > It helps irrespective of the number of pack files. With the current \n> > binary search the lookup cost is O(log n). With a Newton method this \n> > cost is almost O(1).\n> \n> This is not true.\n> \n> First off, when comparing O(logn) to O(1), with \"n\" being less than a \n> billion, they are pretty much exactly the same. Think of it this way: \n> O(logn) == O(9) == O(1), if you know that n < 10**9.\n\nAgreed.\n\n> Secondly, the cost of Newton isn't \"almost O(1)\". I don't know _what_ it \n> is (the rule of thumb with Newton-Raphson should be that the number of \n> significant correct digits in the answer doubles with each iteration: I \n> think that probably means that it should approximate O(loglog(n)), but I \n> haven't thought deeply about it.\n\nSure. But given the reasoning you gave above for O(log N) being about \nthe same as O(1) for a small enough N, I think that O(log log N) is even \ncloser to O(1) in that regard.\n\n> And the thing is, Newton-Raphson didn't actually speed anything up in my \n> tests. Sometimes it was better, sometimes it was worse, most of the time \n> it was in the noise.\n\nOK I didn't remember the difference was so unconclusive.\nThe constant cost is certainly a big factor in the equation.\n\nMaybe we didn't test with a big enough repo yet (big in the sense of \nnumber of objects) to see the variable cost actually dominate.\n\nDid you try with the KDE repo at the time? It has over 4M objects.\nThe binary search would require 14 itterations while the Newton search \nshould take around 3 or 4 itterations if the log O(log N) esttimate is \nright. Of course the evaluation of the next mid point is more costly \nwith the Newton method.\n\n\nNicolas\n"},{"id":"43500","messageId":"20070528174037.GA1118@diana.vm.bytemark.co.uk","threadId":"8320","inReplyTo":"alpine.LFD.0.98.0705280907290.26602@woody.linux-foundation.org","subject":"Re: [PATCH 1/3] Lazily open pack index files on demand","fromName":"Karl Hasselström","fromEmail":"kha@treskal.com","sentAt":"2007-05-28T17:40:37Z","receivedAt":"2007-05-28T17:40:37Z","isPatch":true,"sender":{"key":"kha@treskal.com","avatar":"https://gravatar.com/avatar/f0120c734b5279b345075a28521e1ac66acb20c9913ffe9bf6ae97e53f7f3f13?d=mp&s=160"},"body":"On 2007-05-28 09:22:02 -0700, Linus Torvalds wrote:\n\n> Secondly, the cost of Newton isn't \"almost O(1)\". I don't know\n> _what_ it is (the rule of thumb with Newton-Raphson should be that\n> the number of significant correct digits in the answer doubles with\n> each iteration: I think that probably means that it should\n> approximate O(loglog(n)), but I haven't thought deeply about it.\n\nWith binary search, the number of correct bits in the index increases\nby 1 for each iteration. With Newton iteration, the number of correct\nbits doubles for each iteration. So the number of Newton iteration\nshould be the log of the number of binary search iterations, i.e. log\nlog n like you say.\n\nBut for non-astronomical values of n, I agree that this kind of big-O\nanalysis is much inferior to benchmarking.\n\n-- \nKarl Hasselström, kha@treskal.com\n www.treskal.com/kalle\n"},{"id":"43509","messageId":"alpine.LFD.0.99.0705281314440.11491@xanadu.home","threadId":"8320","inReplyTo":"56b7f5510705271835m5a375324p3a908fe766fdf902@mail.gmail.com","subject":"Re: [PATCH 1/3] Lazily open pack index files on demand","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2007-05-28T18:31:40Z","receivedAt":"2007-05-28T18:31:40Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Sun, 27 May 2007, Dana How wrote:\n\n> Perhaps I have stumbled on another issue related to\n> including SHA-1s in packfiles. This is completely independent\n> of the handling of megablobs (my current focus), but the presence\n> of large blobs do make this issue more apparent.\n> \n> Some history of what I've been doing with git:\n> First I simply had to import the repo,\n> which led to split packs (this was before index v2).\n> Then maintaining the repo led to the unfinished maxblobsize stuff.\n> Distributing the repo included users pulling (usually) from the central repo,\n> which would be trivial since it was also an alternate.\n> Local repacking would avoid heavy load on it.\n> \n> Now I've started looking into how to push back into the\n> central repo from a user's repo (not everything will be central;\n> some pulling between users will occur\n> otherwise I wouldn't be as interested).\n> \n> It looks like the entire sequence is:\n> A. git add file [compute SHA-1 & compress file into objects/xx]\n> B. git commit [write some small objects locally]\n> C. git push {using PROTO_LOCAL}:\n> 1. read & uncompress objects\n> 2. recompress objects into a pack and send through a pipe\n> 3. read pack on other end of pipe and uncompress each object\n> 4. compute SHA-1 for each object and compress file into objects/xx\n> \n> So, after creating an object in the local working tree,\n> to get it into the central repo, we must:\n> compress -> uncompress -> compress -> uncompress -> compress.\n> In responsiveness this won't compare very well to Perforce,\n> which has only one compress step.\n> \n> The sequence above could be somewhat different currently in git.\n> The user might have repacked their repo before pushing,\n> but this just moves C1 and C2 back earlier in time,\n> it doesn't remove the need for them. Besides, the blobs in\n> a push are more likely to be recent and hence unpacked.\n> \n> Also, C3 and C4 might not happen if more than 100 blobs get pushed.\n> But this seems very unusual; only 0.3% of commits in the history\n> had 100+ new files/file contents. If the 100 level is reduced,\n> then the central repo fills up with packfiles and their index files,\n> reducing performance for everybody (using the central repo as an alternate).\n\nBut it makes repacking on the central repo much easier, easily regaining \nperformance for everybody, even more so than if objects were left loose. \nYou could even use one of GIT's many hooks to asynchronously launch a \nrepack whenever a push has been completed to keep the number of server \nside packs low.\n\nAlso, the treshold of 100 is for all objects, not only files. So if you \ndo multiple commits before pushing (a workflow that GIT strongly \nencourage) then you need only 12 commits modifying only 3 file each \nwith those files located in a subdirectory of their own to create 96 \nobjects already. It grows even faster if the modified files are more \ndeeply nested.\n\nThe 100 object treshold was arbitrarily determined and no performance \ntests were ever done to confirm if this is the best value.\n\n> Thus there really is 5X more compression activity going on\n> compared to Perforce. How can this be reduced?\n> \n> One way is to restore the ability to write the \"new\" loose object format.\n> Then C1, C2, and C4 disappear. C3 must remain because we need\n> to uncompress the object to compute its SHA-1; we don't need\n> to recompress since we were already given the compressed form.\n\nC4 isn't mandatory if you keep object packed on the remote end like I \nsuggest above.\n\nNote that C1 is unavoidable when locally repacking. It is the only way \nto make sure the new pack won't blindly reuse data that might have been \ncorrupted on disk (think random bit flip), and wrap it with a valid SHA1 \nthat includes the corrupted data which is even worse. And yes it \nhappened at least once with a report on this list. This is why we are a \nbit paranoid about data integrity. And even if the server currently \nrecompute object SHA1 upon reception of a pack, I think C1 during a push \nis a good thing too just so you don't bother the server if your own repo \nis locally corrupted.\n\nAnd yet you need C1 anyway for deltification in most normal cases.\n\nAs for C2, you should see it as helping the server repack objects. If \nC2 is distributed amongst all client (including C1 and deltification) it \nis then much less visible and the server doesn't need to do that part \nwhen repacking.\n\n> And that final sentence is why I sent this email: if the packfile\n> contained the SHA-1s, either at the beginning or before each object,\n> then they wouldn't need to be recomputed at the receiving end\n> and the extra decompression could be skipped as well. This would\n> make the total zlib effort the same as Perforce.\n\nThis cannot be done. GIT, being distributed, means that you should not \ntrust the remote end. The notion of validation and trust comes from the \nfact that GIT actively validate the SHA1 of what it is fed so a rogue \nserver (or even client) cannot just substitute an object for another \n(with or without malice) and pretend everything is fine.\n\n> The fact that a loose object is never overwritten would still be retained.\n> Is that sufficient security? Or does the SHA-1 always need to be\n> recomputed on the receiving end? Could that be skipped just for\n> specific connections and/or protocols (presumably \"trusted\" ones)?\n\nEven trusted connections can sometimes transmit bad bits. Corruption \n_will_ happen someday to someone. It already happened to people on this \nlist. Hardware is not immune to faults, and the bigger is your repo, \nthe more likely you're susceptible to such things. If SHA1 is validated \non each hop then any corruption won't be able to propagate.\n\n> Shawn: I think you mentioned something related to this a few days ago.\n> Also, you didn't like split packs putting SHA-1s at the end because\n> that messed up streaming for transport, but packs are not split for transport.\n\nLike I stated elsewhere the SHA1 table has no advantage being at the end \nanyway since it cannot be trimmed down even for split packs.\n\n\nNicolas\n"}]}