Interesting that it was actually slower than a custom format. Using the default format saves the cost of strbuf_expand(), but it was paying the price of strbuf_addf(), which the custom path no longer used. So the cost of strbuf_addf() is more than strbuf_expand(), which is not all that surprising.
Your patch seems obviously right, and everything below is idle speculation / nerd-sniping.
I have long wondered if we could do better with a separate initial parse step, which would let us walk the parse tree for each object. In theory that tree is more compact.
I think it would be a huge improvement for ref-filter, whose parser is complicated and slow (though its biggest sin is that it allocates a separate string for each atom before assembling the final output). But could it help even cat-file, which is using a pretty tight loop over strbuf_expand()? I sketched out a rough draft below.
It uses per-atom callback functions which is nice and clean, though we might be able to do even better with a big ugly switch() statement.
The timings I got are below (git.old is master with your patch here applied, and git.new is my patch on top). It looks like it does make a custom format ~3% faster. But it's still a shade slower than the default format. Not sure if it's the extra function calls, or if the static print_default_format() function gives the compiler more opportunities for optimization.
Benchmark 1: ./git.old cat-file --batch-all-objects --batch-check='%(objectname) %(objecttype) %(objectsize)'
Time (mean ± σ): 580.2 ms ± 5.0 ms [User: 558.7 ms, System: 21.5 ms]
Range (min … max): 569.9 ms … 585.6 ms 10 runs
Benchmark 2: ./git.new cat-file --batch-all-objects --batch-check='%(objectname) %(objecttype) %(objectsize)'
Time (mean ± σ): 580.4 ms ± 5.1 ms [User: 562.7 ms, System: 17.8 ms]
Range (min … max): 571.8 ms … 587.0 ms 10 runs
Benchmark 3: ./git.old cat-file --batch-all-objects --batch-check='%(objectname)-%(objecttype)-%(objectsize)'
Time (mean ± σ): 618.6 ms ± 5.0 ms [User: 598.9 ms, System: 19.7 ms]
Range (min … max): 613.6 ms … 628.3 ms 10 runs
Benchmark 4: ./git.new cat-file --batch-all-objects --batch-check='%(objectname)-%(objecttype)-%(objectsize)'
Time (mean ± σ): 600.2 ms ± 4.2 ms [User: 581.2 ms, System: 19.0 ms]
Range (min … max): 595.2 ms … 608.8 ms 10 runs
Summary
./git.old cat-file --batch-all-objects --batch-check='%(objectname) %(objecttype) %(objectsize)' ran
1.00 ± 0.01 times faster than ./git.new cat-file --batch-all-objects --batch-check='%(objectname) %(objecttype) %(objectsize)'
1.03 ± 0.01 times faster than ./git.new cat-file --batch-all-objects --batch-check='%(objectname)-%(objecttype)-%(objectsize)'
1.07 ± 0.01 times faster than ./git.old cat-file --batch-all-objects --batch-check='%(objectname)-%(objecttype)-%(objectsize)'Patch below, only lightly tested.
---
Show changes to builtin/cat-file.c +128 −52
diff --git a/builtin/cat-file.c b/builtin/cat-file.c
index d7f7895e30..9cc7ec7a6f 100644
--- a/builtin/cat-file.c
+++ b/builtin/cat-file.c
@@ -36,6 +36,8 @@ enum batch_mode {
BATCH_MODE_QUEUE_AND_DISPATCH,
};
+struct format_item;
+
struct batch_options {
struct list_objects_filter_options objects_filter;
int enabled;
@@ -48,6 +50,7 @@ struct batch_options {
char input_delim;
char output_delim;
const char *format;
+ struct format_item *parsed_format;
};
static const char *force_path;
@@ -294,12 +297,6 @@ struct expand_data {
const char *rest;
struct object_id delta_base_oid;
- /*
- * If mark_query is true, we do not expand anything, but rather
- * just mark the object_info with items we wish to query.
- */
- int mark_query;
-
/*
* Whether to split the input on whitespace before feeding it to
* get_sha1; this is decided during the mark_query phase based on
@@ -323,65 +320,152 @@ struct expand_data {
};
#define EXPAND_DATA_INIT { .mode = S_IFINVALID }
+struct format_item {
+ void (*add)(struct format_item *item, struct strbuf *sb, struct expand_data *data);
+ union {
+ struct {
+ const char *p;
+ size_t len;
+ } literal;
+ } u;
+ /*
+ * We could make a true tree here with child/next pointers, which would
+ * be necessary if we had recursive formats, like %(if). But for our
+ * simple formats for now it is enough to have a linear set of items,
+ * so we'll just allocate an array and terminate it with a NULL entry.
+ */
+};
+
+static void objectname_add(struct format_item *item UNUSED,
+ struct strbuf *sb, struct expand_data *data)
+{
+ strbuf_add_oid_hex(sb, &data->oid);
+}
+
+static void objecttype_add(struct format_item *item UNUSED,
+ struct strbuf *sb, struct expand_data *data)
+{
+ strbuf_addstr(sb, type_name(data->type));
+}
+
+static void objectsize_add(struct format_item *item UNUSED,
+ struct strbuf *sb, struct expand_data *data)
+{
+ strbuf_add_uint(sb, data->size);
+}
+
+static void objectsize_disk_add(struct format_item *item UNUSED,
+ struct strbuf *sb, struct expand_data *data)
+{
+ strbuf_add_uint(sb, data->disk_size);
+}
+
+static void rest_add(struct format_item *item UNUSED,
+ struct strbuf *sb, struct expand_data *data)
+{
+ strbuf_addstr(sb, data->rest);
+}
+
+static void deltabase_add(struct format_item *item UNUSED,
+ struct strbuf *sb, struct expand_data *data)
+{
+ strbuf_add_oid_hex(sb, &data->delta_base_oid);
+}
+
+static void objectmode_add(struct format_item *item UNUSED,
+ struct strbuf *sb, struct expand_data *data)
+{
+ if (data->mode != S_IFINVALID)
+ strbuf_addf(sb, "%06o", data->mode);
+}
+
+static void literal_add(struct format_item *item,
+ struct strbuf *sb, struct expand_data *data UNUSED)
+{
+ strbuf_add(sb, item->u.literal.p, item->u.literal.len);
+}
+
static int is_atom(const char *atom, const char *s, int slen)
{
int alen = strlen(atom);
return alen == slen && !memcmp(atom, s, alen);
}
-static int expand_atom(struct strbuf *sb, const char *atom, int len,
- struct expand_data *data)
+static int parse_atom(struct format_item *fmt, const char *atom, int len,
+ struct expand_data *data)
{
if (is_atom("objectname", atom, len)) {
- if (!data->mark_query)
- strbuf_add_oid_hex(sb, &data->oid);
+ fmt->add = objectname_add;
} else if (is_atom("objecttype", atom, len)) {
- if (data->mark_query)
- data->info.typep = &data->type;
- else
- strbuf_addstr(sb, type_name(data->type));
+ data->info.typep = &data->type;
+ fmt->add = objecttype_add;
} else if (is_atom("objectsize", atom, len)) {
- if (data->mark_query)
- data->info.sizep = &data->size;
- else
- strbuf_add_uint(sb, data->size);
+ data->info.sizep = &data->size;
+ fmt->add = objectsize_add;
} else if (is_atom("objectsize:disk", atom, len)) {
- if (data->mark_query)
- data->info.disk_sizep = &data->disk_size;
- else
- strbuf_add_uint(sb, data->disk_size);
+ data->info.disk_sizep = &data->disk_size;
+ fmt->add = objectsize_disk_add;
} else if (is_atom("rest", atom, len)) {
- if (data->mark_query)
- data->split_on_whitespace = 1;
- else if (data->rest)
- strbuf_addstr(sb, data->rest);
+ data->split_on_whitespace = 1;
+ fmt->add = rest_add;
} else if (is_atom("deltabase", atom, len)) {
- if (data->mark_query)
- data->info.delta_base_oid = &data->delta_base_oid;
- else
- strbuf_add_oid_hex(sb, &data->delta_base_oid);
+ data->info.delta_base_oid = &data->delta_base_oid;
+ fmt->add = deltabase_add;
} else if (is_atom("objectmode", atom, len)) {
- if (!data->mark_query && !(S_IFINVALID == data->mode))
- strbuf_addf(sb, "%06o", data->mode);
+ fmt->add = objectmode_add;
} else
return 0;
return 1;
}
-static void expand_format(struct strbuf *sb, const char *start,
- struct expand_data *data)
+static struct format_item *parse_format(const char *start,
+ struct expand_data *data)
{
- while (strbuf_expand_step(sb, &start)) {
+ struct format_item *ret = NULL;
+ size_t nr = 0, alloc = 0;
+
+ while (1) {
+ const char *percent = strchrnul(start, '%');
const char *end;
- if (skip_prefix(start, "%", &start) || *start != '(')
- strbuf_addch(sb, '%');
- else if ((end = strchr(start + 1, ')')) &&
- expand_atom(sb, start + 1, end - start - 1, data))
+ if (percent != start) {
+ ALLOC_GROW(ret, nr + 1, alloc);
+ ret[nr].add = literal_add;
+ ret[nr].u.literal.p = start;
+ ret[nr].u.literal.len = percent - start;
+ nr++;
+ }
+
+ if (!*percent)
+ break;
+
+ start = percent + 1;
+
+ ALLOC_GROW(ret, nr + 1, alloc);
+ if (skip_prefix(start, "%", &start) || *start != '(') {
+ ret[nr].add = literal_add;
+ ret[nr].u.literal.p = "%";
+ ret[nr].u.literal.len = 1;
+ } else if ((end = strchr(start + 1, ')')) &&
+ parse_atom(&ret[nr], start + 1, end - start - 1, data)) {
start = end + 1;
- else
+ } else {
strbuf_expand_bad_format(start, "cat-file");
+ }
+ nr++;
}
+
+ ALLOC_GROW(ret, nr + 1, alloc);
+ ret[nr].add = NULL;
+
+ return ret;
+}
+
+static void expand_format(struct strbuf *sb, struct format_item *fmt,
+ struct expand_data *data)
+{
+ for (; fmt->add; fmt++)
+ fmt->add(fmt, sb, data);
}
static void batch_write(struct batch_options *opt, const void *data, int len)
@@ -568,7 +652,7 @@ static void batch_object_write(const char *obj_name,
if (!opt->format) {
print_default_format(scratch, data, opt);
} else {
- expand_format(scratch, opt->format, data);
+ expand_format(scratch, opt->parsed_format, data);
strbuf_addch(scratch, opt->output_delim);
}
@@ -936,17 +1020,9 @@ static int batch_objects(struct batch_options *opt)
int save_warning;
int retval = 0;
- /*
- * Expand once with our special mark_query flag, which will prime the
- * object_info to be handed to odb_read_object_info_extended for each
- * object.
- */
- data.mark_query = 1;
- expand_format(&output,
- opt->format ? opt->format : DEFAULT_FORMAT,
- &data);
- data.mark_query = 0;
- strbuf_release(&output);
+ opt->parsed_format = parse_format(opt->format ?
+ opt->format : DEFAULT_FORMAT,
+ &data);
if (opt->transform_mode)
data.split_on_whitespace = 1;