From: Derrick Stolee Date: Fri, 23 Feb 2018 20:02:21 GMT Subject: Re: [PATCH v4 04/13] commit-graph: implement write_commit_graph() Message-ID: <8d29382b-e0a7-968f-b231-f27f89f275d3@gmail.com> In-Reply-To: On 2/23/2018 2:30 PM, Junio C Hamano wrote: > Derrick Stolee writes: > >> jt/binsearch-with-fanout introduces one when there is a 256-entry >> fanout table (not the case here). >> >> The bsearch() method in search.h (and used in >> pack-write.c:need_large_offset) does not return the _position_ of a >> found element. >> >> Neither of these suit my needs, but I could just be searching for the >> wrong strings. Also, I could divert my energies in this area to create >> a generic search in the style of jt/binsearch-with-fanout. > ... me goes and digs ... > > What I had in mind was the one in sha1-lookup.c, actually. Having > said that, hand-rolling another one is not too huge a deal; > eventually people will notice and consolidate code after the series > stabilizes anyway ;-) Ah, sha1_pos(). That definitely satisfies my use case. Thanks! My local branch has this replacement. > >>>> + num_large_edges++; >>>> + parent = parent->next; >>>> + } while (parent); >>> It feels somewhat wasteful to traverse the commit's parents list >>> only to count, without populating the octopus table (which I >>> understand is assumed to be minority case under this design). >> Since we are writing the commit graph file in-order, we cannot write >> the octopus table until after the chunk lengths are known. > Oh, my "minority case" comment was me wondering "since we expect > there are only a few, why not keep them in memory while we discover > them here, so that the writing phase that come later do not have to > go through all commits again counting their parents? would it be > more performant and a better trade-off?" We can certainly do such > an optimization later (iow, it is not all that crucial issue and > certainly I didn't mention the above as something that needs to be > "fixed"--there is nothing broken). > >> store the octopus table in memory and then dump it into the file >> later, but walking the parents is quite fast after all the commits are >> loaded. I'm not sure the time optimization merits the extra complexity >> here. (I'm happy to revisit this if we do see this performance >> lacking.) >> >> P.S. I really like the name "octopus table" and will use that for >> informal discussions of this format. > I actually do not mind that name used as the official term. I find > it far more descriptive and understandable than "long edge" / "large > edge" at least to a Git person. I will consider using this in the format and design documents. > >> You're right that int_id isn't great, and your more-specific >> "oid_table_pos" shows an extra reason why it isn't great: when we add >> the GRAPH_LAST_EDGE bit or set it to GRAPH_PARENT_MISSING, the value >> is NOT a table position. > Perhaps I am somewhat biased, but it is quite natural for our > codebase and internal API to say something like this: > > x_pos(table, key) function's return value is the non-negative > position for the key in the table when the key is there; when it > returns a negative value, it is (-1 - position) where the "position" > is the position in the table they key would have been found if > it was in there. > > and store the return value from such a function in a variable called > "pos". Surely, sometimes "pos" does not have _the_ position, but > that does not make it a bad name. > > Saying "MISSING is a special value that denotes 'nothing is here'" > and allowing it to be set to a variable that meant to hold the > position is not such a bad thing, though. After all, that is how > you use NULL as a special value for a pointer variable ;-). > > Same for using the high bit to mean something else. Taking these > together you would explain "low 31-bit of pos holds the position for > the item in the table. MISSING is a special value that you can use > to denote there is nothing. The LAST_EDGE bit denotes that one > group of positions ends there", or something like that. > >> I think the current name makes the following call very clear: > It is still a strange name nevertheless. > >>>> +char *write_commit_graph(const char *obj_dir) >>>> +{ >>>> + struct packed_oid_list oids; >>>> + struct packed_commit_list commits; >>>> + struct sha1file *f; >>>> + int i, count_distinct = 0; >>>> + DIR *info_dir; >>>> + struct strbuf tmp_file = STRBUF_INIT; >>>> + struct strbuf graph_file = STRBUF_INIT; >>>> + unsigned char final_hash[GIT_MAX_RAWSZ]; >>>> + char *graph_name; >>>> + int fd; >>>> + uint32_t chunk_ids[5]; >>>> + uint64_t chunk_offsets[5]; >>>> + int num_chunks; >>>> + int num_long_edges; >>>> + struct commit_list *parent; >>>> + >>>> + oids.nr = 0; >>>> + oids.alloc = (int)(0.15 * approximate_object_count()); >>> Heh, traditionalist would probably avoid unnecessary use of float >>> and use something like 1/4 or 1/8 ;-) After all, it is merely a >>> ballpark guestimate. >>> >>>> + num_long_edges = 0; >>> This again is about naming, but I find it a bit unnatural to call >>> the edge between a chind and its octopus parents "long". Individual >>> edges are not long--the only thing that is long is your "list of >>> edges". Some other codepaths in this patch seems to call the same >>> concept with s/long/large/, which I found somewhat puzzling. >> How about "num_extra_edges"... > Yes, "extra" in the name makes it very understandable. >