Refactor hash search with fanout table
cover Refactor hash search with fanout table
After reviewing Derrick's Serialized Git Commit Graph patches [1], I noticed that "[PATCH v2 11/14] commit: integrate commit graph with commit parsing" contains (in bsearch_graph) a repeat of some packfile functionality. Here is a pack that refactors that functionality out.
Derrick, consider incorporating these patches in your next reroll.
[1] https://public-inbox.org/git/[email protected]/
Jonathan Tan (2):
packfile: remove GIT_DEBUG_LOOKUP log statements
packfile: refactor hash search with fanout table
packfile.c | 30 +++++------------------------- sha1-lookup.c | 24 ++++++++++++++++++++++++ sha1-lookup.h | 21 +++++++++++++++++++++ 3 files changed, 50 insertions(+), 25 deletions(-)
Signature · 1 line
2.16.0.rc1.238.g530d649a79-goog
PATCH 1/2 packfile: remove GIT_DEBUG_LOOKUP log statements
In commit 628522ec1439 ("sha1-lookup: more memory efficient search in sorted list of SHA-1", 2008-04-09), a different algorithm for searching a sorted list was introduced, together with a set of log statements guarded by GIT_DEBUG_LOOKUP that are invoked both when using that algorithm and when using the existing binary search. Those log statements was meant for experiments and debugging, but with the removal of the aforementioned different algorithm in commit f1068efefe6d ("sha1_file: drop experimental GIT_USE_LOOKUP search", 2017-08-09), those log statements are probably no longer necessary.
Remove those statements.
--- packfile.c | 11 ----------- 1 file changed, 11 deletions(-)
packfile.c +0 -11
@@ -1713,10 +1713,6 @@ off_t find_pack_entry_one(const unsigned char *sha1,const uint32_t *level1_ofs = p->index_data;const unsigned char *index = p->index_data;unsigned hi, lo, stride; -static int debug_lookup =-1 ; - -if (debug_lookup <0 ) - debug_lookup = !!getenv ("GIT_DEBUG_LOOKUP" );if (!index) {if (open_pack_index (p))
@@ -1738,17 +1734,10 @@ off_t find_pack_entry_one(const unsigned char *sha1, index +=4 ; } -if (debug_lookup) -printf ("%02x%02x%02x... lo %u hi %u nr %" PRIu32"\n" , - sha1[0 ], sha1[1 ], sha1[2 ], lo, hi, p->num_objects); -while (lo < hi) {unsigned mi = lo + (hi - lo) /2 ;int cmp =hashcmp (index + mi * stride, sha1); -if (debug_lookup) -printf ("lo %u hi %u rg %u mi %u\n" , - lo, hi, hi - lo, mi);if (!cmp)return nth_packed_object_offset (p, mi);if (cmp >0 )
Signature · 1 line
2.16.0.rc1.238.g530d649a79-goog
PATCH 2/2 packfile: refactor hash search with fanout table
In reply to Jonathan TanSubsequent patches will introduce file formats that make use of a fanout array and a sorted table containing hashes, just like packfiles. Refactor the hash search in packfile.c into its own function, so that those patches can make use of it as well.
--- packfile.c | 19 +++++-------------- sha1-lookup.c | 24 ++++++++++++++++++++++++ sha1-lookup.h | 21 +++++++++++++++++++++ 3 files changed, 50 insertions(+), 14 deletions(-)
packfile.c +5 -14
@@ -1712,7 +1712,8 @@ off_t find_pack_entry_one(const unsigned char *sha1, {const uint32_t *level1_ofs = p->index_data;const unsigned char *index = p->index_data; -unsigned hi, lo, stride; +unsigned stride; +int ret;if (!index) {if (open_pack_index (p))
@@ -1725,8 +1726,6 @@ off_t find_pack_entry_one(const unsigned char *sha1, index +=8 ; } index +=4 *256 ; - hi =ntohl (level1_ofs[*sha1]); - lo = ((*sha1 ==0x0 ) ?0 :ntohl (level1_ofs[*sha1 -1 ]));if (p->index_version >1 ) { stride =20 ; }else {
@@ -1734,17 +1733,9 @@ off_t find_pack_entry_one(const unsigned char *sha1, index +=4 ; } -while (lo < hi) { -unsigned mi = lo + (hi - lo) /2 ; -int cmp =hashcmp (index + mi * stride, sha1); - -if (!cmp) -return nth_packed_object_offset (p, mi); -if (cmp >0 ) - hi = mi; -else - lo = mi+1 ; - } + ret =bsearch_hash (sha1, level1_ofs, index, stride); +if (ret >=0 ) +return nth_packed_object_offset (p, ret);return 0 ; }
sha1-lookup.c +24 -0
@@ -99,3 +99,27 @@ int sha1_pos(const unsigned char *sha1, void *table, size_t nr, }while (lo < hi);return -lo-1 ; } + +int bsearch_hash (const unsigned char *sha1,const void *fanout_, +const void *table_,size_t stride) +{ +const uint32_t *fanout = fanout_; +const unsigned char *table = table_; +int hi, lo; + + hi =ntohl (fanout[*sha1]); + lo = ((*sha1 ==0x0 ) ?0 :ntohl (fanout[*sha1 -1 ])); + +while (lo < hi) { +unsigned mi = lo + (hi - lo) /2 ; +int cmp =hashcmp (table + mi * stride, sha1); + +if (!cmp) +return mi; +if (cmp >0 ) + hi = mi; +else + lo = mi +1 ; + } +return -lo -1 ; +}
sha1-lookup.h +21 -0
@@ -7,4 +7,25 @@ extern int sha1_pos(const unsigned char *sha1,void *table, size_t nr, sha1_access_fn fn); + +/* +* Searches for sha1 in table, using the given fanout table to determine the +* interval to search, then using binary search. Returns the element index of +* the position found if successful, -i-1 if not (where i is the index of the +* least element that is greater than sha1). +* +* Takes the following parameters: +* +* - sha1: the hash to search for +* - fanout: a 256-element array of NETWORK-order 32-bit integers; the integer +* at position i represents the number of elements in table whose first byte +* is less than or equal to i +* - table: a sorted list of hashes with optional extra information in between +* - stride: distance between two consecutive elements in table (should be +* GIT_MAX_RAWSZ or greater) +* +* This function does not verify the validity of the fanout table. +*/ +extern int bsearch_hash (const unsigned char *sha1,const void *fanout, +const void *table,size_t stride);#endif
Signature · 1 line
2.16.0.rc1.238.g530d649a79-goog
Quoted 4 lines · Jonathan Tan
After reviewing Derrick's Serialized Git Commit Graph patches [1], I noticed that "[PATCH v2 11/14] commit: integrate commit graph with commit parsing" contains (in
bsearch_graph) a repeat of some packfile functionality. Here is a pack that refactors that functionality out.
Yay. I had exactly the same reaction to that part of the series.
Thansk.
Derrick Stolee
Reviewed-byQuoted 9 lines · Junio C Hamano
Quoted 4 lines · Jonathan Tan
After reviewing Derrick's Serialized Git Commit Graph patches [1], I noticed that "[PATCH v2 11/14] commit: integrate commit graph with commit parsing" contains (in
bsearch_graph) a repeat of some packfile functionality. Here is a pack that refactors that functionality out.Yay. I had exactly the same reaction to that part of the series.
Thanks for doing this refactor. I'm a fan of reducing code clones, but also don't want to break well-worn code paths.
Jonathan: While you are doing this, I'm guessing you could use your new method to replace (and maybe speed up) the binary search in sha1_name.c:find_abbrev_len_for_pack(). Otherwise, I can take a stab at it next week.
Please add
Thanks,
-Stolee
Re: [PATCH 2/2] packfile: refactor hash search with fanout table
In reply to Jonathan TanAm 02.02.2018 um 23:36 schrieb Jonathan Tan:
Quoted 43 lines
Subsequent patches will introduce file formats that make use of a fanout array and a sorted table containing hashes, just like packfiles. Refactor the hash search in
packfile.cinto its own function, so that those patches can make use of it as well.Signed-off-by Jonathan Tan <[email protected]>--- packfile.c | 19 +++++-------------- sha1-lookup.c | 24 ++++++++++++++++++++++++ sha1-lookup.h | 21 +++++++++++++++++++++ 3 files changed, 50 insertions(+), 14 deletions(-)packfile.c +2
-7@@ -1712,7 +1712,8 @@ off_t find_pack_entry_one(const unsigned char *sha1, {const uint32_t *level1_ofs = p->index_data;const unsigned char *index = p->index_data; -unsigned hi, lo, stride; +unsigned stride; +int ret;if (!index) {if (open_pack_index (p))@@ -1725,8 +1726,6 @@ off_t find_pack_entry_one(const unsigned char *sha1, index +=8 ; } index +=4 *256 ; - hi =ntohl (level1_ofs[*sha1]); - lo = ((*sha1 ==0x0 ) ?0 :ntohl (level1_ofs[*sha1 -1 ]));if (p->index_version >1 ) { stride =20 ; }else {@@ -1734,17 +1733,9 @@ off_t find_pack_entry_one(const unsigned char *sha1, index +=4 ; } -while (lo < hi) { -unsigned mi = lo + (hi - lo) /2 ; -int cmp =hashcmp (index + mi * stride, sha1); -
packfile.c off_t find_pack_entry_one(const unsigned char *sha1, · line 1738
Quoted 10 lines
packfile.c +3
-7-if (!cmp) -return nth_packed_object_offset (p, mi); -if (cmp >0 ) - hi = mi; -else - lo = mi+1 ; - } + ret =bsearch_hash (sha1, level1_ofs, index, stride); +if (ret >=0 ) +return nth_packed_object_offset (p, ret);
Going from unsigned to signed int means the patch breaks support for more than 2G pack entries, which was put with 326bf39677 (Use uint32_t for all packed object counts.) in 2007.
Quoted 8 lines
packfile.c +0
-0return 0 ; }sha1-lookup.c +0
-0
sha1-lookup.c int sha1_pos(const unsigned char *sha1, void *table, size_t nr, · line 106
Quoted 8 lines
sha1-lookup.c +5
-0@@ -99,3 +99,27 @@ int sha1_pos(const unsigned char *sha1, void *table, size_t nr, }while (lo < hi);return -lo-1 ; } + +int bsearch_hash (const unsigned char *sha1,const void *fanout_, +const void *table_,size_t stride) +{ +const uint32_t *fanout = fanout_;
Why hide the type? It doesn't make the function more generic.
Quoted 40 lines
sha1-lookup.c +19
-0+const unsigned char *table = table_; +int hi, lo; + + hi =ntohl (fanout[*sha1]); + lo = ((*sha1 ==0x0 ) ?0 :ntohl (fanout[*sha1 -1 ])); + +while (lo < hi) { +unsigned mi = lo + (hi - lo) /2 ; +int cmp =hashcmp (table + mi * stride, sha1); + +if (!cmp) +return mi; +if (cmp >0 ) + hi = mi; +else + lo = mi +1 ; + } +return -lo -1 ; +}sha1-lookup.h +12
-0@@ -7,4 +7,25 @@ extern int sha1_pos(const unsigned char *sha1,void *table, size_t nr, sha1_access_fn fn); + +/* +* Searches for sha1 in table, using the given fanout table to determine the +* interval to search, then using binary search. Returns the element index of +* the position found if successful, -i-1 if not (where i is the index of the +* least element that is greater than sha1). +* +* Takes the following parameters: +* +* - sha1: the hash to search for +* - fanout: a 256-element array of NETWORK-order 32-bit integers; the integer +* at position i represents the number of elements in table whose first byte
sha1-lookup.h extern int sha1_pos(const unsigned char *sha1, · line 31
Quoted 10 lines
sha1-lookup.h +9
-0+* is less than or equal to i +* - table: a sorted list of hashes with optional extra information in between +* - stride: distance between two consecutive elements in table (should be +* GIT_MAX_RAWSZ or greater) +* +* This function does not verify the validity of the fanout table. +*/ +extern int bsearch_hash (const unsigned char *sha1,const void *fanout, +const void *table,size_t stride);#endif
Why not use sha1_pos()? I guess because it avoids the overhead of the accessor function, right? And I wonder how much of difference it makes.
A binary search function for embedded hashes just needs the key, a pointer to the first hash in the array, the stride and the number of elements. It can then be used with or without a fanout table, making it more versatile. Just a thought.
René
Re: [PATCH 2/2] packfile: refactor hash search with fanout table
Quoted 3 lines · On Fri, 9 Feb 2018 19:03:48 +0100 René Scharfe <[email protected]> wrote:
Going from unsigned to signed int means the patch breaks support for more than 2G pack entries, which was put with
326bf39677(Useuint32_tfor all packed object counts.) in 2007.
Ah, good catch. I'll wait to see if there are any more comments, then send out a new version.
Quoted 6 lines
sha1-lookup.c int sha1_pos(const unsigned char *sha1, void *table, size_t nr, · line 106
Quoted 4 lines
sha1-lookup.c +4
-0+int bsearch_hash (const unsigned char *sha1,const void *fanout_, +const void *table_,size_t stride) +{ +const uint32_t *fanout = fanout_;Why hide the type? It doesn't make the function more generic.
I thought that the fanout_ parameter could come from a variety of sources (e.g. direct mmap - void *, or mmap with some pointer arithmetic
- char *) so I just picked the generic one. But now I realize that that could lead to unaligned reads, which is probably not a good idea. I'll update it.
For consistency, I'll also update table_ to be unsigned char *. (Unsigned because it is primarily interpreted as hashes, which use "unsigned char *" in the Git code.)
Quoted 2 lines
Why not use
sha1_pos()? I guess because it avoids the overhead of the accessor function, right? And I wonder how much of difference it makes.
Yes, overhead of the accessor function. We would also need to modify sha1_pos to take in a function that we can pass userdata to (to contain the stride).
Quoted 4 lines
A binary search function for embedded hashes just needs the key, a pointer to the first hash in the array, the stride and the number of elements. It can then be used with or without a fanout table, making it more versatile. Just a thought.
I specifically want to include the fanout table in the calculation here, because it will be used by subsequent patches that also incorporate the fanout table.
v2 cover Refactor hash search with fanout table
In reply to Jonathan TanUpdates from v1:
- use uint32_t so that we can operate on packfiles of up to 4G objects (this also means that I had to change the signature of the function)
- don't hide types
Derrick: you'll need to slightly change your patch to use the new API. As for find_abbrev_len_for_pack(), that's a good idea - I didn't do it in this set but it definitely should be done.
Jonathan Tan (2):
packfile: remove GIT_DEBUG_LOOKUP log statements
packfile: refactor hash search with fanout table
packfile.c | 29 ++++------------------------- sha1-lookup.c | 28 ++++++++++++++++++++++++++++ sha1-lookup.h | 22 ++++++++++++++++++++++ 3 files changed, 54 insertions(+), 25 deletions(-)
Signature · 1 line
2.16.0.rc1.238.g530d649a79-goog
PATCH v2 2/2 packfile: refactor hash search with fanout table
Subsequent patches will introduce file formats that make use of a fanout array and a sorted table containing hashes, just like packfiles. Refactor the hash search in packfile.c into its own function, so that those patches can make use of it as well.
--- packfile.c | 18 ++++-------------- sha1-lookup.c | 28 ++++++++++++++++++++++++++++ sha1-lookup.h | 22 ++++++++++++++++++++++ 3 files changed, 54 insertions(+), 14 deletions(-)
packfile.c +4 -14
@@ -1712,7 +1712,8 @@ off_t find_pack_entry_one(const unsigned char *sha1, {const uint32_t *level1_ofs = p->index_data;const unsigned char *index = p->index_data; -unsigned hi, lo, stride; +unsigned stride; +uint32_t result;if (!index) {if (open_pack_index (p))
@@ -1725,8 +1726,6 @@ off_t find_pack_entry_one(const unsigned char *sha1, index +=8 ; } index +=4 *256 ; - hi =ntohl (level1_ofs[*sha1]); - lo = ((*sha1 ==0x0 ) ?0 :ntohl (level1_ofs[*sha1 -1 ]));if (p->index_version >1 ) { stride =20 ; }else {
@@ -1734,17 +1733,8 @@ off_t find_pack_entry_one(const unsigned char *sha1, index +=4 ; } -while (lo < hi) { -unsigned mi = lo + (hi - lo) /2 ; -int cmp =hashcmp (index + mi * stride, sha1); - -if (!cmp) -return nth_packed_object_offset (p, mi); -if (cmp >0 ) - hi = mi; -else - lo = mi+1 ; - } +if (bsearch_hash (sha1, level1_ofs, index, stride, &result)) +return nth_packed_object_offset (p, result);return 0 ; }
sha1-lookup.c +28 -0
@@ -99,3 +99,31 @@ int sha1_pos(const unsigned char *sha1, void *table, size_t nr, }while (lo < hi);return -lo-1 ; } + +int bsearch_hash (const unsigned char *sha1,const uint32_t *fanout_nbo, +const unsigned char *table,size_t stride,uint32_t *result) +{ +uint32_t hi, lo; + + hi =ntohl (fanout_nbo[*sha1]); + lo = ((*sha1 ==0x0 ) ?0 :ntohl (fanout_nbo[*sha1 -1 ])); + +while (lo < hi) { +unsigned mi = lo + (hi - lo) /2 ; +int cmp =hashcmp (table + mi * stride, sha1); + +if (!cmp) { +if (result) + *result = mi; +return 1 ; + } +if (cmp >0 ) + hi = mi; +else + lo = mi +1 ; + } + +if (result) + *result = lo; +return 0 ; +}
sha1-lookup.h +22 -0
@@ -7,4 +7,26 @@ extern int sha1_pos(const unsigned char *sha1,void *table, size_t nr, sha1_access_fn fn); + +/* +* Searches for sha1 in table, using the given fanout table to determine the +* interval to search, then using binary search. Returns 1 if found, 0 if not. +* +* Takes the following parameters: +* +* - sha1: the hash to search for +* - fanout_nbo: a 256-element array of NETWORK-order 32-bit integers; the +* integer at position i represents the number of elements in table whose +* first byte is less than or equal to i +* - table: a sorted list of hashes with optional extra information in between +* - stride: distance between two consecutive elements in table (should be +* GIT_MAX_RAWSZ or greater) +* - result: if not NULL, this function stores the element index of the +* position found (if the search is successful) or the index of the least +* element that is greater than sha1 (if the search is not successful) +* +* This function does not verify the validity of the fanout table. +*/ +int bsearch_hash (const unsigned char *sha1,const uint32_t *fanout_nbo, +const unsigned char *table,size_t stride,uint32_t *result);#endif
Signature · 1 line
2.16.0.rc1.238.g530d649a79-goog
PATCH v2 1/2 packfile: remove GIT_DEBUG_LOOKUP log statements
In reply to Jonathan TanIn commit 628522ec1439 ("sha1-lookup: more memory efficient search in sorted list of SHA-1", 2008-04-09), a different algorithm for searching a sorted list was introduced, together with a set of log statements guarded by GIT_DEBUG_LOOKUP that are invoked both when using that algorithm and when using the existing binary search. Those log statements was meant for experiments and debugging, but with the removal of the aforementioned different algorithm in commit f1068efefe6d ("sha1_file: drop experimental GIT_USE_LOOKUP search", 2017-08-09), those log statements are probably no longer necessary.
Remove those statements.
--- packfile.c | 11 ----------- 1 file changed, 11 deletions(-)
packfile.c +0 -11
@@ -1713,10 +1713,6 @@ off_t find_pack_entry_one(const unsigned char *sha1,const uint32_t *level1_ofs = p->index_data;const unsigned char *index = p->index_data;unsigned hi, lo, stride; -static int debug_lookup =-1 ; - -if (debug_lookup <0 ) - debug_lookup = !!getenv ("GIT_DEBUG_LOOKUP" );if (!index) {if (open_pack_index (p))
@@ -1738,17 +1734,10 @@ off_t find_pack_entry_one(const unsigned char *sha1, index +=4 ; } -if (debug_lookup) -printf ("%02x%02x%02x... lo %u hi %u nr %" PRIu32"\n" , - sha1[0 ], sha1[1 ], sha1[2 ], lo, hi, p->num_objects); -while (lo < hi) {unsigned mi = lo + (hi - lo) /2 ;int cmp =hashcmp (index + mi * stride, sha1); -if (debug_lookup) -printf ("lo %u hi %u rg %u mi %u\n" , - lo, hi, hi - lo, mi);if (!cmp)return nth_packed_object_offset (p, mi);if (cmp >0 )
Signature · 1 line
2.16.0.rc1.238.g530d649a79-goog
Quoted 3 lines · Jonathan Tan
Updates from v1:
- useuint32_tso that we can operate on packfiles of up to 4G objects (this also means that I had to change the signature of the function)
I take it "4G objects" means "4 billion objects". The distinction is only important that the limit is not a 4GB IDX file, but in fact a large enough object count that the IDX file can be 100+ GB.
Quoted 5 lines
- don't hide types
Derrick: you'll need to slightly change your patch to use the new API. As for
find_abbrev_len_for_pack(), that's a good idea - I didn't do it in this set but it definitely should be done.
Thanks. I'll try to remember to do that change when this lands in master. I'll bring the new prototype into my commit-graph patch.
Quoted 5 lines · Jonathan Tan
Updates from v1:
- useuint32_tso that we can operate on packfiles of up to 4G objects (this also means that I had to change the signature of the function)
- don't hide types
Quoted 7 lines
Derrick: you'll need to slightly change your patch to use the new API. As for
find_abbrev_len_for_pack(), that's a good idea - I didn't do it in this set but it definitely should be done.Jonathan Tan (2):
packfile: removeGIT_DEBUG_LOOKUPlog statements
packfile: refactor hash search with fanout table
Hmm, is this meant to replace the topic that was merged to 'next' last week?
Quoted 5 lines
packfile.c | 29 ++++------------------------- sha1-lookup.c | 28 ++++++++++++++++++++++++++++ sha1-lookup.h | 22 ++++++++++++++++++++++ 3 files changed, 54 insertions(+), 25 deletions(-)
Quoted 11 lines · On Tue, 13 Feb 2018 11:57:16 -0800 Junio C Hamano <[email protected]> wrote:
Quoted 9 lines · Jonathan Tan
Updates from v1:
- useuint32_tso that we can operate on packfiles of up to 4G objects (this also means that I had to change the signature of the function)
- don't hide typesDerrick: you'll need to slightly change your patch to use the new API. As for
find_abbrev_len_for_pack(), that's a good idea - I didn't do it in this set but it definitely should be done.
Quoted 6 lines
Quoted 3 lines
Jonathan Tan (2):
packfile: removeGIT_DEBUG_LOOKUPlog statements
packfile: refactor hash search with fanout tableHmm, is this meant to replace the topic that was merged to 'next' last week?
Yes - René pointed out [1] that V1 of my patch series (which you merged to 'next') does not handle packfiles of more than 2G pack entries, so I sent out a new version. Yes, this replaces jt/binsearch-with-fanout. Sorry for not being clearer.