On Tue, Aug 26, 2025 at 12:26:07AM -0400, Jeff King wrote:
> This particular case may not be representative, either. I picked it
> because it was easy to convert. But I wonder how bad it would be to put
> the object flags for a traversal into a hash. Right now those are in the
> original struct, not even in a commit-slab. So I'd guess it's an even
> bigger slowdown.
Just for fun, and because I hadn't tortured myself with coccinelle
syntax in a while, I tried removing object.flags entirely. Apply the
patch below, then:
make SPATCH_USE_O_DEPENDENCIES= contrib/coccinelle/flags.cocci.patch
git apply contrib/coccinelle/flags.cocci.patch
That misses a few stragglers, which I'll include fixes for below.
Anyway, the result is a system that does hash lookups for every access
of the "flags" field. I added a few helpers to do |= and &= without
doing two lookups. Probably this could go a little further with some
kind of test-and-set (e.g., you want to know if SEEN is set and if not,
set it and do some other stuff). But it gives a general idea.
I tried timing merge-base which I know will need to paint flags, using
an old commit (so that we have to walk almost down to the root). Here
are the results:
Benchmark 1: ./git.orig merge-base HEAD 19b2860cba574
Time (mean ± σ): 31.7 ms ± 0.7 ms [User: 26.1 ms, System: 5.5 ms]
Range (min … max): 30.5 ms … 34.0 ms 89 runs
Benchmark 2: ./git.hash merge-base HEAD 19b2860cba574
Time (mean ± σ): 39.7 ms ± 0.7 ms [User: 33.9 ms, System: 5.8 ms]
Range (min … max): 38.5 ms … 42.6 ms 75 runs
Summary
./git.orig merge-base HEAD 19b2860cba574 ran
1.25 ± 0.03 times faster than ./git.hash merge-base HEAD 19b2860cba574
And here's a rev-list which needs to set SEEN on a lot of objects (but
also has to actually inflate a lot of trees, too):
$ hyperfine -L v orig,hash './git.{v} rev-list --objects --all'
Benchmark 1: ./git.orig rev-list --objects --all
Time (mean ± σ): 2.875 s ± 0.050 s [User: 2.799 s, System: 0.075 s]
Range (min … max): 2.803 s … 2.973 s 10 runs
Benchmark 2: ./git.hash rev-list --objects --all
Time (mean ± σ): 5.547 s ± 0.069 s [User: 5.477 s, System: 0.070 s]
Range (min … max): 5.396 s … 5.671 s 10 runs
Summary
./git.orig rev-list --objects --all ran
1.93 ± 0.04 times faster than ./git.hash rev-list --objects --all
I expected the merge-base to fare much worse, since it's otherwise
mostly just pulling commit data from the commit-graph file and walking
the pointers. But I guess we check a lot of SEEN flags for rev-list.
Anyway, I think the numbers there demonstrate that it's probably not
that interesting a direction. I'm a little curious how a slab would
fare. It shouldn't be _too_ hard to slot it in with a similar API (the
real work was adjusting all the callers via cocci). But I'm not sure I
have the stomach to waste more time on this. ;)
Patches below for reference. This is the one that rips out the flags
field:
---
contrib/coccinelle/flags.cocci | 59 ++++++++++++++++++++++++++++++++++
object.c | 5 ++-
object.h | 29 ++++++++++++++++-
3 files changed, 91 insertions(+), 2 deletions(-)
create mode 100644 contrib/coccinelle/flags.cocci
diff --git a/contrib/coccinelle/flags.cocci b/contrib/coccinelle/flags.cocci
new file mode 100644
index 0000000000..5dae0054d6
--- /dev/null
+++ b/contrib/coccinelle/flags.cocci
@@ -0,0 +1,59 @@
+@@
+struct object *OBJPTR;
+expression FLAGS;
+@@
+- OBJPTR->flags |= FLAGS
++ objflags_set(OBJPTR, FLAGS)
+
+@@
+struct object *OBJPTR;
+expression FLAGS;
+@@
+- OBJPTR->flags &= FLAGS
++ objflags_clear(OBJPTR, FLAGS)
+
+@@
+struct object *OBJPTR;
+@@
+- OBJPTR->flags
++ objflags_get(OBJPTR)
+
+@@
+expression TYPEDOBJ;
+expression FLAGS;
+@@
+- TYPEDOBJ->object.flags |= FLAGS
++ objflags_set(&TYPEDOBJ->object, FLAGS)
+
+@@
+expression TYPEDOBJ;
+expression FLAGS;
+@@
+- TYPEDOBJ->object.flags &= FLAGS
++ objflags_clear(&TYPEDOBJ->object, FLAGS)
+
+@@
+expression TYPEDOBJ;
+@@
+- TYPEDOBJ->object.flags
++ objflags_get(&TYPEDOBJ->object)
+
+@@
+struct object_array_entry *ENTRY;
+expression FLAGS;
+@@
+- ENTRY->item->flags |= FLAGS
++ objflags_set(ENTRY->item, FLAGS)
+
+@@
+struct object_array_entry *ENTRY;
+expression FLAGS;
+@@
+- ENTRY->item->flags &= FLAGS
++ objflags_clear(ENTRY->item, FLAGS)
+
+@@
+struct object_array_entry *ENTRY;
+@@
+- ENTRY->item->flags
++ objflags_get(ENTRY->item)
diff --git a/object.c b/object.c
index c1553ee433..679aadbd7b 100644
--- a/object.c
+++ b/object.c
@@ -14,6 +14,9 @@
#include "alloc.h"
#include "commit-graph.h"
+static kh_obj_flags_t objflags_data;
+kh_obj_flags_t *objflags = &objflags_data;
+
unsigned int get_max_object_index(const struct repository *repo)
{
return repo->parsed_objects->obj_hash_size;
@@ -149,7 +152,7 @@ void *create_object(struct repository *r, const struct object_id *oid, void *o)
struct object *obj = o;
obj->parsed = 0;
- obj->flags = 0;
+ /* flags default to 0 via flags hash */
oidcpy(&obj->oid, oid);
if (r->parsed_objects->obj_hash_size - 1 <= r->parsed_objects->nr_objs * 2)
diff --git a/object.h b/object.h
index 14718051f2..50d1d0e65f 100644
--- a/object.h
+++ b/object.h
@@ -159,7 +159,6 @@ static inline unsigned int canon_mode(unsigned int mode)
struct object {
unsigned parsed : 1;
unsigned type : TYPE_BITS;
- unsigned flags : FLAG_BITS;
struct object_id oid;
};
@@ -369,5 +368,33 @@ static inline value_type name##_get(kh_##name##_t *map, const struct object *obj
}
OBJHASH_INIT(obj_timestamp, timestamp_t, 0);
+OBJHASH_INIT(obj_flags, unsigned, 0);
+
+extern kh_obj_flags_t *objflags;
+
+static inline unsigned objflags_get(const struct object *obj)
+{
+ return obj_flags_get(objflags, obj);
+}
+
+static inline void objflags_set(const struct object *obj, unsigned flags)
+{
+ int hash_ret;
+ khiter_t pos = kh_put_obj_flags(objflags, obj, &hash_ret);
+ if (!hash_ret)
+ kh_value(objflags, pos) |= flags;
+ else
+ kh_value(objflags, pos) = flags;
+}
+
+static inline void objflags_clear(const struct object *obj, unsigned flags)
+{
+ int hash_ret;
+ khiter_t pos = kh_put_obj_flags(objflags, obj, &hash_ret);
+ if (!hash_ret)
+ kh_value(objflags, pos) &= flags;
+ else
+ kh_value(objflags, pos) = 0;
+}
#endif /* OBJECT_H */
And then this one gives you the fixups on top of applying the cocci
patch:
---
builtin/describe.c | 5 +++--
builtin/fsck.c | 2 +-
builtin/log.c | 10 +++++-----
commit-graph.c | 2 +-
commit-reach.c | 2 +-
http-push.c | 2 +-
range-diff.c | 2 +-
reflog.c | 6 +++---
revision.c | 4 ++--
9 files changed, 18 insertions(+), 17 deletions(-)
diff --git a/builtin/describe.c b/builtin/describe.c
index b9ebdb9a3d..aeb3b3344f 100644
--- a/builtin/describe.c
+++ b/builtin/describe.c
@@ -290,7 +290,7 @@ static bool all_have_flag(const struct lazy_queue *queue, unsigned flag)
{
for (size_t i = queue->get_pending ? 1 : 0; i < queue->queue.nr; i++) {
struct commit *commit = queue->queue.array[i].data;
- if (!(commit->object.flags & flag))
+ if (!(objflags_get(&commit->object) & flag))
return false;
}
return true;
@@ -398,7 +398,8 @@ static void describe_commit(struct object_id *oid, struct strbuf *dst)
have_util = 1;
}
- objflags_get(&cmit->object) = SEEN;
+ /* weird, this assigns SEEN instead of OR-ing it? */
+ obj_flags_put(objflags, &cmit->object, SEEN);
lazy_queue_put(&queue, cmit);
while (!lazy_queue_empty(&queue)) {
struct commit *c = lazy_queue_get(&queue);
diff --git a/builtin/fsck.c b/builtin/fsck.c
index c2a3df8c1d..c5d5a4ea75 100644
--- a/builtin/fsck.c
+++ b/builtin/fsck.c
@@ -214,7 +214,7 @@ static int mark_used(struct object *obj, enum object_type type UNUSED,
{
if (!obj)
return 1;
- obj->flags |= USED;
+ objflags_set(obj, USED);
return 0;
}
diff --git a/builtin/log.c b/builtin/log.c
index 9ceeace9c3..34ba1ff782 100644
--- a/builtin/log.c
+++ b/builtin/log.c
@@ -1164,8 +1164,8 @@ static void get_patch_ids(struct rev_info *rev, struct patch_ids *ids)
/* given a range a..b get all patch ids for b..a */
repo_init_revisions(the_repository, &check_rev, rev->prefix);
check_rev.max_parents = 1;
- objflags_get(o1) ^= UNINTERESTING;
- objflags_get(o2) ^= UNINTERESTING;
+ obj_flags_put(objflags, o1, objflags_get(o1) ^ UNINTERESTING);
+ obj_flags_put(objflags, o2, objflags_get(o2) ^ UNINTERESTING);
add_pending_object(&check_rev, o1, "o1");
add_pending_object(&check_rev, o2, "o2");
if (prepare_revision_walk(&check_rev))
@@ -1178,8 +1178,8 @@ static void get_patch_ids(struct rev_info *rev, struct patch_ids *ids)
/* reset for next revision walk */
clear_commit_marks(c1, SEEN | UNINTERESTING | SHOWN | ADDED);
clear_commit_marks(c2, SEEN | UNINTERESTING | SHOWN | ADDED);
- objflags_get(o1) = flags1;
- objflags_get(o2) = flags2;
+ obj_flags_put(objflags, o1, flags1);
+ obj_flags_put(objflags, o2, flags2);
}
static void gen_message_id(struct rev_info *info, const char *base)
@@ -2224,7 +2224,7 @@ int cmd_format_patch(int argc,
* origin" that prepares what the origin side still
* does not have.
*/
- rev.pending.objects[0].item->flags |= UNINTERESTING;
+ objflags_set(rev.pending.objects[0].item, UNINTERESTING);
add_head_to_pending(&rev);
check_head = 1;
}
diff --git a/commit-graph.c b/commit-graph.c
index 89a48171e4..a29f716523 100644
--- a/commit-graph.c
+++ b/commit-graph.c
@@ -1568,7 +1568,7 @@ static void close_reachable(struct write_commit_graph_context *ctx)
commit = lookup_commit(ctx->r, &ctx->oids.oid[i]);
if (commit)
- commit->object.flags &= ~REACHABLE;
+ objflags_clear(&commit->object, ~REACHABLE);
}
stop_progress(&ctx->progress);
}
diff --git a/commit-reach.c b/commit-reach.c
index 329c61d559..3189aee0db 100644
--- a/commit-reach.c
+++ b/commit-reach.c
@@ -812,7 +812,7 @@ int can_all_from_reach_with_flag(struct object_array *from,
* leave a note to ourselves not to worry about
* this object anymore.
*/
- from->objects[i].item->flags |= assign_flag;
+ objflags_set(from->objects[i].item, assign_flag);
continue;
}
diff --git a/http-push.c b/http-push.c
index 0706929cac..5d7635988e 100644
--- a/http-push.c
+++ b/http-push.c
@@ -1377,7 +1377,7 @@ static int get_delta(struct rev_info *revs, struct remote_lock *lock)
while (objects) {
struct object_list *next = objects->next;
- if (!(objects->item->flags & UNINTERESTING))
+ if (!(objflags_get(objects->item) & UNINTERESTING))
count += add_send_request(objects->item, lock);
free(objects);
diff --git a/range-diff.c b/range-diff.c
index 8a2dcbee32..2774720615 100644
--- a/range-diff.c
+++ b/range-diff.c
@@ -611,7 +611,7 @@ int is_range_diff_range(const char *arg)
repo_init_revisions(the_repository, &revs, NULL);
if (setup_revisions(3, argv, &revs, NULL) == 1) {
for (i = 0; i < revs.pending.nr; i++)
- if (revs.pending.objects[i].item->flags & UNINTERESTING)
+ if (objflags_get(revs.pending.objects[i].item) & UNINTERESTING)
negative++;
else
positive++;
diff --git a/reflog.c b/reflog.c
index 879e802228..ff99a8353c 100644
--- a/reflog.c
+++ b/reflog.c
@@ -244,12 +244,12 @@ static int commit_is_complete(struct commit *commit)
if (!is_incomplete) {
/* mark all found commits as complete, iow SEEN */
for (i = 0; i < found.nr; i++)
- found.objects[i].item->flags |= SEEN;
+ objflags_set(found.objects[i].item, SEEN);
}
}
/* clear flags from the objects we traversed */
for (i = 0; i < found.nr; i++)
- found.objects[i].item->flags &= ~STUDYING;
+ objflags_clear(found.objects[i].item, ~STUDYING);
if (is_incomplete)
objflags_set(&commit->object, INCOMPLETE);
else {
@@ -262,7 +262,7 @@ static int commit_is_complete(struct commit *commit)
* we have seen during this process are complete.
*/
for (i = 0; i < found.nr; i++)
- found.objects[i].item->flags |= SEEN;
+ objflags_set(found.objects[i].item, SEEN);
}
/* free object arrays */
object_array_clear(&study);
diff --git a/revision.c b/revision.c
index 90e3ee30d5..4fd4b96eb1 100644
--- a/revision.c
+++ b/revision.c
@@ -3656,10 +3656,10 @@ static void trace2_topo_walk_statistics_atexit(void)
static inline void test_flag_and_insert(struct prio_queue *q, struct commit *c, int flag)
{
- if (c->object.flags & flag)
+ if (objflags_get(&c->object) & flag)
return;
- c->object.flags |= flag;
+ objflags_set(&c->object, flag);
prio_queue_put(q, c);
}
--
2.51.0.382.g68ff637df6
