From 4cea1ce0f69d079819f2a189febcea215045dabf Mon Sep 17 00:00:00 2001 From: =?utf8?q?Ren=C3=A9=20Scharfe?= Date: Sun, 6 Jan 2019 17:45:52 +0100 Subject: [PATCH] object-store: use one oid_array per subdirectory for loose cache MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit The loose objects cache is filled one subdirectory at a time as needed. It is stored in an oid_array, which has to be resorted after each add operation. So when querying a wide range of objects, the partially filled array needs to be resorted up to 255 times, which takes over 100 times longer than sorting once. Use one oid_array for each subdirectory. This ensures that entries have to only be sorted a single time. It also avoids eight binary search steps for each cache lookup as a small bonus. The cache is used for collision checks for the log placeholders %h, %t and %p, and we can see the change speeding them up in a repository with ca. 100 objects per subdirectory: $ git count-objects 26733 objects, 68808 kilobytes Test HEAD^ HEAD -------------------------------------------------------------------- 4205.1: log with %H 0.51(0.47+0.04) 0.51(0.49+0.02) +0.0% 4205.2: log with %h 0.84(0.82+0.02) 0.60(0.57+0.03) -28.6% 4205.3: log with %T 0.53(0.49+0.04) 0.52(0.48+0.03) -1.9% 4205.4: log with %t 0.84(0.80+0.04) 0.60(0.59+0.01) -28.6% 4205.5: log with %P 0.52(0.48+0.03) 0.51(0.50+0.01) -1.9% 4205.6: log with %p 0.85(0.78+0.06) 0.61(0.56+0.05) -28.2% 4205.7: log with %h-%h-%h 0.96(0.92+0.03) 0.69(0.64+0.04) -28.1% Reported-by: Ævar Arnfjörð Bjarmason Signed-off-by: Rene Scharfe Signed-off-by: Junio C Hamano --- object-store.h | 2 +- sha1-file.c | 9 ++++++--- 2 files changed, 7 insertions(+), 4 deletions(-) diff --git a/object-store.h b/object-store.h index 709bf856b6..2fb6c0e4db 100644 --- a/object-store.h +++ b/object-store.h @@ -20,7 +20,7 @@ struct object_directory { * Be sure to call odb_load_loose_cache() before using. */ char loose_objects_subdir_seen[256]; - struct oid_array loose_objects_cache; + struct oid_array loose_objects_cache[256]; /* * Path to the alternative object store. If this is a relative path, diff --git a/sha1-file.c b/sha1-file.c index 2f965b2688..c3c6e50704 100644 --- a/sha1-file.c +++ b/sha1-file.c @@ -2155,7 +2155,7 @@ struct oid_array *odb_loose_cache(struct object_directory *odb, { int subdir_nr = oid->hash[0]; odb_load_loose_cache(odb, subdir_nr); - return &odb->loose_objects_cache; + return &odb->loose_objects_cache[subdir_nr]; } void odb_load_loose_cache(struct object_directory *odb, int subdir_nr) @@ -2173,14 +2173,17 @@ void odb_load_loose_cache(struct object_directory *odb, int subdir_nr) for_each_file_in_obj_subdir(subdir_nr, &buf, append_loose_object, NULL, NULL, - &odb->loose_objects_cache); + &odb->loose_objects_cache[subdir_nr]); odb->loose_objects_subdir_seen[subdir_nr] = 1; strbuf_release(&buf); } void odb_clear_loose_cache(struct object_directory *odb) { - oid_array_clear(&odb->loose_objects_cache); + int i; + + for (i = 0; i < ARRAY_SIZE(odb->loose_objects_cache); i++) + oid_array_clear(&odb->loose_objects_cache[i]); memset(&odb->loose_objects_subdir_seen, 0, sizeof(odb->loose_objects_subdir_seen)); } -- 2.11.4.GIT