object-store: use one oid_array per subdirectory for loose cache

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 <avarab@gmail.com>
Signed-off-by: Rene Scharfe <l.s.r@web.de>
Signed-off-by: Junio C Hamano <gitster@pobox.com>

diff --git a/object-store.h b/object-store.h
index 709bf856b678bbd9ccd10714283277524df6b394..2fb6c0e4db132bcbd0957ddb8796d75ee402d974 100644 (file)
--- 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 2f965b26880d850e78b1611669b56bd503f8a230..c3c6e50704a8c7e1ff26676a6fe706175ead30f4 100644 (file)
--- 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));
 }