| Message ID | e1aa89244ad3edb52aaeb28d6934cb2b0a0dc65a.1610576604.git.me@ttaylorr.com (mailing list archive) |
|---|---|
| State | Accepted |
| Commit | f33fb6e419ab9ca27403c8207e53f27411028420 |
| Headers | show |
| Series | pack-revindex: prepare for on-disk reverse index | expand |
Taylor Blau <me@ttaylorr.com> writes: > +/* > + * offset_to_pack_pos converts an object offset to a pack position. This > + * function returns zero on success, and a negative number otherwise. The > + * parameter 'pos' is usable only on success. > + * > + * If the reverse index has not yet been loaded, this function loads it lazily, > + * and returns an negative number if an error was encountered. It is somewhat strange to see a function that yields a non-negative "position" on success and a negative value to signal a failure to have a separate pointer to the location to receive the true return value. Do we truly care the upper half of "uint32_t" (in other words, do we seriously want to support more than 2G positions in a pack)? What I'm trying to get at is that int pos = offset_to_pack_pos(...); if (pos < 0) error(); else use(pos); is more natural than uint32_t pos; if (offset_to_pack_pos(..., &pos) < 0) error(); else use(pos); but now I wrote it down and laid it out in front of my eyes, the latter does not look too bad. ... later comes back after reading through the series ... The new callers all looked quite nice to eyes. Because we discourage assignment inside if() condition, the converted result does not make the code more verbose than the original. In fact, it makes it even clearer that we are checking for an error return from a function call. Quite nice. > + * This function runs in time O(log N) with the number of objects in the pack. Is it a good idea to commit to such performance characteristics as a promise to callers like this (the comment applies to all three functions)? It depends on how a developer is helped by this comment when deciding whether to use this function, or find other ways, to implement what s/he wants to do. > + */ > +int offset_to_pack_pos(struct packed_git *p, off_t ofs, uint32_t *pos); > +/* > + * pack_pos_to_index converts the given pack-relative position 'pos' by > + * returning an index-relative position. > + * > + * If the reverse index has not yet been loaded, or the position is out of > + * bounds, this function aborts. > + * > + * This function runs in constant time. > + */ > +uint32_t pack_pos_to_index(struct packed_git *p, uint32_t pos); > + > +/* > + * pack_pos_to_offset converts the given pack-relative position 'pos' into a > + * pack offset. For a pack with 'N' objects, asking for position 'N' will return > + * the total size (in bytes) of the pack. If we talk about "asking for 'N'" and want it to mean "one beyond the last position", it is better to clarify that we count from 0. But see below. > + * If the reverse index has not yet been loaded, or the position is out of > + * bounds, this function aborts. I think it is easier to read if the "unlike the above function, this allows pos that is one beyond the last object" is explained next to "if out of bounds, it is an error", not as a part of the previous paragraph. > + * This function runs in constant time. > + */ > +off_t pack_pos_to_offset(struct packed_git *p, uint32_t pos); > + > #endif
On 1/14/2021 1:46 AM, Junio C Hamano wrote: > Taylor Blau <me@ttaylorr.com> writes: > >> +/* >> + * offset_to_pack_pos converts an object offset to a pack position. This >> + * function returns zero on success, and a negative number otherwise. The >> + * parameter 'pos' is usable only on success. >> + * >> + * If the reverse index has not yet been loaded, this function loads it lazily, >> + * and returns an negative number if an error was encountered. > > It is somewhat strange to see a function that yields a non-negative > "position" on success and a negative value to signal a failure to > have a separate pointer to the location to receive the true return > value. Do we truly care the upper half of "uint32_t" (in other > words, do we seriously want to support more than 2G positions in a > pack)? > > What I'm trying to get at is that > > int pos = offset_to_pack_pos(...); > if (pos < 0) > error(); > else > use(pos); > > is more natural than I agree that this is used commonly, but usually in the case that we are finding a position in the list _or where such an item would be inserted_. For example: pos = index_name_pos(istate, dirname, len); if (pos < 0) pos = -pos-1; while (pos < istate->cache_nr) { ... But that does not apply in this case. Knowing that the requested offset lies between object 'i' and object 'i + 1' isn't helpful, since the offset still does not correspond to the start of an object. > uint32_t pos; > if (offset_to_pack_pos(..., &pos) < 0) > error(); > else > use(pos); > > but now I wrote it down and laid it out in front of my eyes, the > latter does not look too bad. > > ... later comes back after reading through the series ... > > The new callers all looked quite nice to eyes. Because we > discourage assignment inside if() condition, the converted > result does not make the code more verbose than the > original. In fact, it makes it even clearer that we are > checking for an error return from a function call. > > Quite nice. As someone who spends a decent amount of time working in C#, I also like this pattern. The APIs in C# work this way, too, such as: if (!set.TryGetValue(key, out value)) return false; // Use 'value', which is initialized now. Thanks, -Stolee
On Wed, Jan 13, 2021 at 10:46:57PM -0800, Junio C Hamano wrote: > Taylor Blau <me@ttaylorr.com> writes: > > > +/* > > + * offset_to_pack_pos converts an object offset to a pack position. This > > + * function returns zero on success, and a negative number otherwise. The > > + * parameter 'pos' is usable only on success. > > + * > > + * If the reverse index has not yet been loaded, this function loads it lazily, > > + * and returns an negative number if an error was encountered. > > It is somewhat strange to see a function that yields a non-negative > "position" on success and a negative value to signal a failure to > have a separate pointer to the location to receive the true return > value. Do we truly care the upper half of "uint32_t" (in other > words, do we seriously want to support more than 2G positions in a > pack)? I don't think that we care about that as much as we do about potential misuse of a signed return value. There are indeed a couple of spots where a potential negative return value is ignored, and then used to lookup an object in a pack, or some such. And that's part of the goal of this API: we have strict guidelines about when the output parameter is and isn't usable. That makes it more difficult to accidentally use an uninitialized value / negative number. > What I'm trying to get at is that [...] is more natural than [...] but > now I wrote it down and laid it out in front of my eyes, the latter > does not look too bad. OK, good :-). > ... later comes back after reading through the series ... > > The new callers all looked quite nice to eyes. Because we > discourage assignment inside if() condition, the converted > result does not make the code more verbose than the > original. In fact, it makes it even clearer that we are > checking for an error return from a function call. > > Quite nice. Thank you :-D. > > + * This function runs in time O(log N) with the number of objects in the pack. > > Is it a good idea to commit to such performance characteristics as a > promise to callers like this (the comment applies to all three > functions)? > > It depends on how a developer is helped by this comment when > deciding whether to use this function, or find other ways, to > implement what s/he wants to do. I don't mind it. If they all had the same performance characteristics, I wouldn't be for it, but since they don't, I think that it's good to know. Peff suggested this back in [1]. Thanks, Taylor [1]: https://lore.kernel.org/git/X%2F1guCOGWybOzIS7@coredump.intra.peff.net/
On Thu, Jan 14, 2021 at 12:06:20PM -0500, Taylor Blau wrote: > > > + * This function runs in time O(log N) with the number of objects in the pack. > > > > Is it a good idea to commit to such performance characteristics as a > > promise to callers like this (the comment applies to all three > > functions)? > > > > It depends on how a developer is helped by this comment when > > deciding whether to use this function, or find other ways, to > > implement what s/he wants to do. > > I don't mind it. If they all had the same performance characteristics, I > wouldn't be for it, but since they don't, I think that it's good to > know. Peff suggested this back in [1]. Yeah, I asked for this. As somebody who has frequently worked on the code which accesses the revindex (mostly bitmap stuff), I found it useful to understand how expensive the operations were. However, I also know what their runtimes are at this point, and it is not like somebody interested cannot look at the implementation. So it may not be that important. So I do still think it is useful, but if somebody feels strongly against it, I don't mind it being removed. -Peff
Jeff King <peff@peff.net> writes: > On Thu, Jan 14, 2021 at 12:06:20PM -0500, Taylor Blau wrote: > >> > > + * This function runs in time O(log N) with the number of objects in the pack. >> > >> > Is it a good idea to commit to such performance characteristics as a >> > promise to callers like this (the comment applies to all three >> > functions)? >> > >> > It depends on how a developer is helped by this comment when >> > deciding whether to use this function, or find other ways, to >> > implement what s/he wants to do. >> >> I don't mind it. If they all had the same performance characteristics, I >> wouldn't be for it, but since they don't, I think that it's good to >> know. Peff suggested this back in [1]. > > Yeah, I asked for this. As somebody who has frequently worked on the > code which accesses the revindex (mostly bitmap stuff), I found it > useful to understand how expensive the operations were. However, I also > know what their runtimes are at this point, and it is not like somebody > interested cannot look at the implementation. So it may not be that > important. > > So I do still think it is useful, but if somebody feels strongly against > it, I don't mind it being removed. That won't be me. It's not like you'd use pack_pos_to_index() combined with pack_pos_to_offset() instead of offset_to_pack_pos() because the latter is more expensive than using the other two functions; the comment does not help those who want to know relative performance of these functions for such a purpose. I was just curious who the comments were meant to help, that's all. Thanks.
diff --git a/pack-revindex.c b/pack-revindex.c index ecdde39cf4..0ca3b54b45 100644 --- a/pack-revindex.c +++ b/pack-revindex.c @@ -203,3 +203,35 @@ struct revindex_entry *find_pack_revindex(struct packed_git *p, off_t ofs) return p->revindex + pos; } + +int offset_to_pack_pos(struct packed_git *p, off_t ofs, uint32_t *pos) +{ + int ret; + + if (load_pack_revindex(p) < 0) + return -1; + + ret = find_revindex_position(p, ofs); + if (ret < 0) + return ret; + *pos = ret; + return 0; +} + +uint32_t pack_pos_to_index(struct packed_git *p, uint32_t pos) +{ + if (!p->revindex) + BUG("pack_pos_to_index: reverse index not yet loaded"); + if (p->num_objects <= pos) + BUG("pack_pos_to_index: out-of-bounds object at %"PRIu32, pos); + return p->revindex[pos].nr; +} + +off_t pack_pos_to_offset(struct packed_git *p, uint32_t pos) +{ + if (!p->revindex) + BUG("pack_pos_to_index: reverse index not yet loaded"); + if (p->num_objects < pos) + BUG("pack_pos_to_offset: out-of-bounds object at %"PRIu32, pos); + return p->revindex[pos].offset; +} diff --git a/pack-revindex.h b/pack-revindex.h index 848331d5d6..5a218aaa66 100644 --- a/pack-revindex.h +++ b/pack-revindex.h @@ -1,6 +1,21 @@ #ifndef PACK_REVINDEX_H #define PACK_REVINDEX_H +/** + * A revindex allows converting efficiently between three properties + * of an object within a pack: + * + * - index position: the numeric position within the list of sorted object ids + * found in the .idx file + * + * - pack position: the numeric position within the list of objects in their + * order within the actual .pack file (i.e., 0 is the first object in the + * .pack, 1 is the second, and so on) + * + * - offset: the byte offset within the .pack file at which the object contents + * can be found + */ + struct packed_git; struct revindex_entry { @@ -8,9 +23,48 @@ struct revindex_entry { unsigned int nr; }; +/* + * load_pack_revindex populates the revindex's internal data-structures for the + * given pack, returning zero on success and a negative value otherwise. + */ int load_pack_revindex(struct packed_git *p); int find_revindex_position(struct packed_git *p, off_t ofs); struct revindex_entry *find_pack_revindex(struct packed_git *p, off_t ofs); +/* + * offset_to_pack_pos converts an object offset to a pack position. This + * function returns zero on success, and a negative number otherwise. The + * parameter 'pos' is usable only on success. + * + * If the reverse index has not yet been loaded, this function loads it lazily, + * and returns an negative number if an error was encountered. + * + * This function runs in time O(log N) with the number of objects in the pack. + */ +int offset_to_pack_pos(struct packed_git *p, off_t ofs, uint32_t *pos); + +/* + * pack_pos_to_index converts the given pack-relative position 'pos' by + * returning an index-relative position. + * + * If the reverse index has not yet been loaded, or the position is out of + * bounds, this function aborts. + * + * This function runs in constant time. + */ +uint32_t pack_pos_to_index(struct packed_git *p, uint32_t pos); + +/* + * pack_pos_to_offset converts the given pack-relative position 'pos' into a + * pack offset. For a pack with 'N' objects, asking for position 'N' will return + * the total size (in bytes) of the pack. + * + * If the reverse index has not yet been loaded, or the position is out of + * bounds, this function aborts. + * + * This function runs in constant time. + */ +off_t pack_pos_to_offset(struct packed_git *p, uint32_t pos); + #endif
In the next several patches, we will prepare for loading a reverse index either in memory (mapping the inverse of the .idx's contents in-core), or directly from a yet-to-be-introduced on-disk format. To prepare for that, we'll introduce an API that avoids the caller explicitly indexing the revindex pointer in the packed_git structure. There are four ways to interact with the reverse index. Accordingly, four functions will be exported from 'pack-revindex.h' by the time that the existing API is removed. A caller may: 1. Load the pack's reverse index. This involves opening up the index, generating an array, and then sorting it. Since opening the index can fail, this function ('load_pack_revindex()') returns an int. Accordingly, it takes only a single argument: the 'struct packed_git' the caller wants to build a reverse index for. This function is well-suited for both the current and new API. Callers will have to continue to open the reverse index explicitly, but this function will eventually learn how to detect and load a reverse index from the on-disk format, if one exists. Otherwise, it will fallback to generating one in memory from scratch. 2. Convert a pack position into an offset. This operation is now called `pack_pos_to_offset()`. It takes a pack and a position, and returns the corresponding off_t. Any error simply calls BUG(), since the callers are not well-suited to handle a failure and keep going. 3. Convert a pack position into an index position. Same as above; this takes a pack and a position, and returns a uint32_t. This operation is known as `pack_pos_to_index()`. The same thinking about error conditions applies here as well. 4. Find the pack position for a given offset. This operation is now known as `offset_to_pack_pos()`. It takes a pack, an offset, and a pointer to a uint32_t where the position is written, if an object exists at that offset. Otherwise, -1 is returned to indicate failure. Unlike some of the callers that used to access '->offset' and '->nr' directly, the error checking around this call is somewhat more robust. This is important since callers should always pass an offset which points at the boundary of two objects. The API, unlike direct access, enforces that that is the case. This will become important in a subsequent patch where a caller which does not but could check the return value treats the signed `-1` from `find_revindex_position()` as an index into the 'revindex' array. Two design warts are carried over into the new API: - Asking for the index position of an out-of-bounds object will result in a BUG() (since no such object exists), but asking for the offset of the non-existent object at the end of the pack returns the total size of the pack. This makes it convenient for callers who always want to take the difference of two adjacent object's offsets (to compute the on-disk size) but don't want to worry about boundaries at the end of the pack. - offset_to_pack_pos() lazily loads the reverse index, but pack_pos_to_index() doesn't (callers of the former are well-suited to handle errors, but callers of the latter are not). Signed-off-by: Taylor Blau <me@ttaylorr.com> --- pack-revindex.c | 32 +++++++++++++++++++++++++++++ pack-revindex.h | 54 +++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 86 insertions(+)