{"thread":{"id":"60827","subject":"[PATCH 0/7] reftable: improve ref iteration performance","startedAt":"2024-02-01T10:24:59Z","lastAt":"2024-02-13T06:57:27Z","messageCount":23,"participants":["Patrick Steinhardt","Eric Sunshine","John Cai","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":7},"messages":[{"id":"487724","messageId":"cover.1706782841.git.ps@pks.im","threadId":"60827","inReplyTo":null,"subject":"[PATCH 0/7] reftable: improve ref iteration performance","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-02-01T10:24:54Z","receivedAt":"2024-02-01T10:24:59Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"Hi,\n\nthis patch series aims to improve performance when iterating over many\nrefs with the reftable backend. It mostly does so by trying to reduce\nthe number of allocations and avoiding useless copying of memory where\npossible.\n\nI've been careful to avoid conflicts with any in-flight topics, so it\nshould be fine for all of the topics to go in indepentently of each\nother. The benchmarks have all been done with ps/reftable-backend at\n066dced0b1 (ci: add jobs to test with the reftable backend, 2024-01-30).\n\nPatrick\n\nPatrick Steinhardt (7):\n  reftable/record: introduce function to compare records by key\n  reftable/merged: allocation-less dropping of shadowed records\n  reftable/merged: skip comparison for records of the same subiter\n  reftable/pq: allocation-less comparison of entry keys\n  reftable/block: swap buffers instead of copying\n  reftable/record: don't try to reallocate ref record name\n  reftable/reader: add comments to `table_iter_next()`\n\n reftable/block.c  |  3 +--\n reftable/merged.c | 19 +++++++-------\n reftable/merged.h |  2 --\n reftable/pq.c     | 13 +--------\n reftable/reader.c | 26 +++++++++++-------\n reftable/record.c | 67 ++++++++++++++++++++++++++++++++++++++++++++---\n reftable/record.h |  7 +++++\n 7 files changed, 100 insertions(+), 37 deletions(-)\n\n-- \n2.43.GIT\n\n"},{"id":"487725","messageId":"fadabec696f75ae0fa25bcbf87012fcc4768acaa.1706782841.git.ps@pks.im","threadId":"60827","inReplyTo":"cover.1706782841.git.ps@pks.im","subject":"[PATCH 1/7] reftable/record: introduce function to compare records by key","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-02-01T10:24:58Z","receivedAt":"2024-02-01T10:25:02Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"In some places we need to sort reftable records by their keys to\ndetermine their ordering. This is done by first formatting the keys into\na `struct strbuf` and then using `strbuf_cmp()` to compare them. This\nlogic is needlessly roundabout and can end up costing quite a bit fo CPU\ncycles, both due to the allocation and formatting logic.\n\nIntroduce a new `reftable_record_cmp()` function that knows to compare\ntwo records with each other without requiring allocations.\n\nSigned-off-by: Patrick Steinhardt <ps@pks.im>\n---\n reftable/record.c | 62 ++++++++++++++++++++++++++++++++++++++++++++++-\n reftable/record.h |  7 ++++++\n 2 files changed, 68 insertions(+), 1 deletion(-)\n\ndiff --git a/reftable/record.c b/reftable/record.c\nindex 5c3fbb7b2a..f1b6a5eac9 100644\n--- a/reftable/record.c\n+++ b/reftable/record.c\n@@ -430,7 +430,6 @@ static int reftable_ref_record_is_deletion_void(const void *p)\n \t\t(const struct reftable_ref_record *)p);\n }\n \n-\n static int reftable_ref_record_equal_void(const void *a,\n \t\t\t\t\t  const void *b, int hash_size)\n {\n@@ -439,6 +438,13 @@ static int reftable_ref_record_equal_void(const void *a,\n \treturn reftable_ref_record_equal(ra, rb, hash_size);\n }\n \n+static int reftable_ref_record_cmp_void(const void *_a, const void *_b)\n+{\n+\tconst struct reftable_ref_record *a = _a;\n+\tconst struct reftable_ref_record *b = _b;\n+\treturn strcmp(a->refname, b->refname);\n+}\n+\n static void reftable_ref_record_print_void(const void *rec,\n \t\t\t\t\t   int hash_size)\n {\n@@ -455,6 +461,7 @@ static struct reftable_record_vtable reftable_ref_record_vtable = {\n \t.release = &reftable_ref_record_release_void,\n \t.is_deletion = &reftable_ref_record_is_deletion_void,\n \t.equal = &reftable_ref_record_equal_void,\n+\t.cmp = &reftable_ref_record_cmp_void,\n \t.print = &reftable_ref_record_print_void,\n };\n \n@@ -625,6 +632,25 @@ static int reftable_obj_record_equal_void(const void *a, const void *b, int hash\n \treturn 1;\n }\n \n+static int reftable_obj_record_cmp_void(const void *_a, const void *_b)\n+{\n+\tconst struct reftable_obj_record *a = _a;\n+\tconst struct reftable_obj_record *b = _b;\n+\tint cmp;\n+\n+\tcmp = memcmp(a->hash_prefix, b->hash_prefix,\n+\t\t     a->hash_prefix_len > b->hash_prefix_len ?\n+\t\t     a->hash_prefix_len : b->hash_prefix_len);\n+\tif (cmp)\n+\t\treturn cmp;\n+\n+\t/*\n+\t * When the prefix is the same then the object record that is longer is\n+\t * considered to be bigger.\n+\t */\n+\treturn a->hash_prefix_len - b->hash_prefix_len;\n+}\n+\n static struct reftable_record_vtable reftable_obj_record_vtable = {\n \t.key = &reftable_obj_record_key,\n \t.type = BLOCK_TYPE_OBJ,\n@@ -635,6 +661,7 @@ static struct reftable_record_vtable reftable_obj_record_vtable = {\n \t.release = &reftable_obj_record_release,\n \t.is_deletion = &not_a_deletion,\n \t.equal = &reftable_obj_record_equal_void,\n+\t.cmp = &reftable_obj_record_cmp_void,\n \t.print = &reftable_obj_record_print,\n };\n \n@@ -953,6 +980,22 @@ static int reftable_log_record_equal_void(const void *a,\n \t\t\t\t\t hash_size);\n }\n \n+static int reftable_log_record_cmp_void(const void *_a, const void *_b)\n+{\n+\tconst struct reftable_log_record *a = _a;\n+\tconst struct reftable_log_record *b = _b;\n+\tint cmp = strcmp(a->refname, b->refname);\n+\tif (cmp)\n+\t\treturn cmp;\n+\n+\t/*\n+\t * Note that the comparison here is reversed. This is because the\n+\t * update index is reversed when comparing keys. For reference, see how\n+\t * we handle this in reftable_log_record_key()`.\n+\t */\n+\treturn b->update_index - a->update_index;\n+}\n+\n int reftable_log_record_equal(const struct reftable_log_record *a,\n \t\t\t      const struct reftable_log_record *b, int hash_size)\n {\n@@ -1002,6 +1045,7 @@ static struct reftable_record_vtable reftable_log_record_vtable = {\n \t.release = &reftable_log_record_release_void,\n \t.is_deletion = &reftable_log_record_is_deletion_void,\n \t.equal = &reftable_log_record_equal_void,\n+\t.cmp = &reftable_log_record_cmp_void,\n \t.print = &reftable_log_record_print_void,\n };\n \n@@ -1077,6 +1121,13 @@ static int reftable_index_record_equal(const void *a, const void *b, int hash_si\n \treturn ia->offset == ib->offset && !strbuf_cmp(&ia->last_key, &ib->last_key);\n }\n \n+static int reftable_index_record_cmp(const void *_a, const void *_b)\n+{\n+\tconst struct reftable_index_record *a = _a;\n+\tconst struct reftable_index_record *b = _b;\n+\treturn strbuf_cmp(&a->last_key, &b->last_key);\n+}\n+\n static void reftable_index_record_print(const void *rec, int hash_size)\n {\n \tconst struct reftable_index_record *idx = rec;\n@@ -1094,6 +1145,7 @@ static struct reftable_record_vtable reftable_index_record_vtable = {\n \t.release = &reftable_index_record_release,\n \t.is_deletion = &not_a_deletion,\n \t.equal = &reftable_index_record_equal,\n+\t.cmp = &reftable_index_record_cmp,\n \t.print = &reftable_index_record_print,\n };\n \n@@ -1147,6 +1199,14 @@ int reftable_record_is_deletion(struct reftable_record *rec)\n \t\treftable_record_data(rec));\n }\n \n+int reftable_record_cmp(struct reftable_record *a, struct reftable_record *b)\n+{\n+\tif (a->type != b->type)\n+\t\tBUG(\"cannot compare reftable records of different type\");\n+\treturn reftable_record_vtable(a)->cmp(\n+\t\treftable_record_data(a), reftable_record_data(b));\n+}\n+\n int reftable_record_equal(struct reftable_record *a, struct reftable_record *b, int hash_size)\n {\n \tif (a->type != b->type)\ndiff --git a/reftable/record.h b/reftable/record.h\nindex fd80cd451d..0d96fbfd1b 100644\n--- a/reftable/record.h\n+++ b/reftable/record.h\n@@ -62,6 +62,12 @@ struct reftable_record_vtable {\n \t/* Are two records equal? This assumes they have the same type. Returns 0 for non-equal. */\n \tint (*equal)(const void *a, const void *b, int hash_size);\n \n+\t/*\n+\t * Compare keys of two records with each other. The records must have\n+\t * the same type.\n+\t */\n+\tint (*cmp)(const void *a, const void *b);\n+\n \t/* Print on stdout, for debugging. */\n \tvoid (*print)(const void *rec, int hash_size);\n };\n@@ -114,6 +120,7 @@ struct reftable_record {\n };\n \n /* see struct record_vtable */\n+int reftable_record_cmp(struct reftable_record *a, struct reftable_record *b);\n int reftable_record_equal(struct reftable_record *a, struct reftable_record *b, int hash_size);\n void reftable_record_print(struct reftable_record *rec, int hash_size);\n void reftable_record_key(struct reftable_record *rec, struct strbuf *dest);\n-- \n2.43.GIT\n\n"},{"id":"487726","messageId":"576a96f2e5cf462d2f5793a0c8244f4966789654.1706782841.git.ps@pks.im","threadId":"60827","inReplyTo":"cover.1706782841.git.ps@pks.im","subject":"[PATCH 2/7] reftable/merged: allocation-less dropping of shadowed records","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-02-01T10:25:02Z","receivedAt":"2024-02-01T10:25:06Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"The purpose of the merged reftable iterator is to iterate through all\nentries of a set of tables in the correct order. This is implemented by\nusing a sub-iterator for each table, where the next entry of each of\nthese iterators gets put into a priority queue. For each iteration, we\ndo roughly the following steps:\n\n  1. Retrieve the top record of the priority queue. This is the entry we\n     want to return to the caller.\n\n  2. Retrieve the next record of the sub-iterator that this record came\n     from. If any, add it to the priority queue at the correct position.\n     The position is determined by comparing the record keys, which e.g.\n     corresponds to the refname for ref records.\n\n  3. Keep removing the top record of the priority queue until we hit the\n     first entry whose key is larger than the returned record's key.\n     This is required to drop \"shadowed\" records.\n\nThe last step will lead to at least one comparison to the next entry,\nbut may lead to many comparisons in case the reftable stack consists of\nmany tables with shadowed records. It is thus part of the hot code path\nwhen iterating through records.\n\nThe code to compare the entries with each other is quite inefficient\nthough. Instead of comparing record keys with each other directly, we\nfirst format them into `struct strbuf`s and only then compare them with\neach other. While we already optimized this code path to reuse buffers\nin 829231dc20 (reftable/merged: reuse buffer to compute record keys,\n2023-12-11), the cost to format the keys into the buffers still adds up\nquite significantly.\n\nRefactor the code to use `reftable_record_cmp()` instead, which has been\nintroduced in the preceding commit. This function compares records with\neach other directly without requiring any memory allocations or copying\nand is thus way more efficient.\n\nThe following benchmark uses git-show-ref(1) to print a single ref\nmatching a pattern out of 1 million refs. This is the most direct way to\nexercise ref iteration speed as we remove all overhead of having to show\nthe refs, too.\n\n    Benchmark 1: show-ref: single matching ref (revision = HEAD~)\n      Time (mean ± σ):     180.7 ms ±   4.7 ms    [User: 177.1 ms, System: 3.4 ms]\n      Range (min … max):   174.9 ms … 211.7 ms    1000 runs\n\n    Benchmark 2: show-ref: single matching ref (revision = HEAD)\n      Time (mean ± σ):     162.1 ms ±   4.4 ms    [User: 158.5 ms, System: 3.4 ms]\n      Range (min … max):   155.4 ms … 189.3 ms    1000 runs\n\n    Summary\n      show-ref: single matching ref (revision = HEAD) ran\n        1.11 ± 0.04 times faster than show-ref: single matching ref (revision = HEAD~)\n\nSigned-off-by: Patrick Steinhardt <ps@pks.im>\n---\n reftable/merged.c | 11 ++---------\n reftable/merged.h |  2 --\n 2 files changed, 2 insertions(+), 11 deletions(-)\n\ndiff --git a/reftable/merged.c b/reftable/merged.c\nindex c258ce953e..fb9978d798 100644\n--- a/reftable/merged.c\n+++ b/reftable/merged.c\n@@ -51,8 +51,6 @@ static void merged_iter_close(void *p)\n \t\treftable_iterator_destroy(&mi->stack[i]);\n \t}\n \treftable_free(mi->stack);\n-\tstrbuf_release(&mi->key);\n-\tstrbuf_release(&mi->entry_key);\n }\n \n static int merged_iter_advance_nonnull_subiter(struct merged_iter *mi,\n@@ -105,14 +103,11 @@ static int merged_iter_next_entry(struct merged_iter *mi,\n \t  such a deployment, the loop below must be changed to collect all\n \t  entries for the same key, and return new the newest one.\n \t*/\n-\treftable_record_key(&entry.rec, &mi->entry_key);\n \twhile (!merged_iter_pqueue_is_empty(mi->pq)) {\n \t\tstruct pq_entry top = merged_iter_pqueue_top(mi->pq);\n-\t\tint cmp = 0;\n+\t\tint cmp;\n \n-\t\treftable_record_key(&top.rec, &mi->key);\n-\n-\t\tcmp = strbuf_cmp(&mi->key, &mi->entry_key);\n+\t\tcmp = reftable_record_cmp(&top.rec, &entry.rec);\n \t\tif (cmp > 0)\n \t\t\tbreak;\n \n@@ -246,8 +241,6 @@ static int merged_table_seek_record(struct reftable_merged_table *mt,\n \t\t.typ = reftable_record_type(rec),\n \t\t.hash_id = mt->hash_id,\n \t\t.suppress_deletions = mt->suppress_deletions,\n-\t\t.key = STRBUF_INIT,\n-\t\t.entry_key = STRBUF_INIT,\n \t};\n \tint n = 0;\n \tint err = 0;\ndiff --git a/reftable/merged.h b/reftable/merged.h\nindex d5b39dfe7f..7d9f95d27e 100644\n--- a/reftable/merged.h\n+++ b/reftable/merged.h\n@@ -31,8 +31,6 @@ struct merged_iter {\n \tuint8_t typ;\n \tint suppress_deletions;\n \tstruct merged_iter_pqueue pq;\n-\tstruct strbuf key;\n-\tstruct strbuf entry_key;\n };\n \n void merged_table_release(struct reftable_merged_table *mt);\n-- \n2.43.GIT\n\n"},{"id":"487727","messageId":"0ca86eba710895f0e22fc15fe5221f5487031f64.1706782841.git.ps@pks.im","threadId":"60827","inReplyTo":"cover.1706782841.git.ps@pks.im","subject":"[PATCH 3/7] reftable/merged: skip comparison for records of the same subiter","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-02-01T10:25:06Z","receivedAt":"2024-02-01T10:25:09Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"When retrieving the next entry of a merged iterator we need to drop all\nrecords of other sub-iterators that would be shadowed by the record that\nwe are about to return. We do this by comparing record keys, dropping\nall keys that are smaller or equal to the key of the record we are about\nto return.\n\nThere is an edge case here where we can skip that comparison: when the\nrecord in the priority queue comes from the same subiterator than the\nrecord we are about to return then we know that its key must be larger\nthan the key of the record we are about to return. This property is\nguaranteed by the sub-iterators, and if it didn't hold then the whole\nmerged iterator would return records in the wrong order, too.\n\nWhile this may seem like a very specific edge case it's in fact quite\nlikely to happen. For most repositories out there you can assume that we\nwill end up with one large table and several smaller ones on top of it.\nThus, it is very likely that the next entry will sort towards the top of\nthe priority queue.\n\nSpecial case this and break out of the loop in that case. The following\nbenchmark uses git-show-ref(1) to print a single ref matching a pattern\nout of 1 million refs:\n\n  Benchmark 1: show-ref: single matching ref (revision = HEAD~)\n    Time (mean ± σ):     162.6 ms ±   4.5 ms    [User: 159.0 ms, System: 3.5 ms]\n    Range (min … max):   156.6 ms … 188.5 ms    1000 runs\n\n  Benchmark 2: show-ref: single matching ref (revision = HEAD)\n    Time (mean ± σ):     156.8 ms ±   4.7 ms    [User: 153.0 ms, System: 3.6 ms]\n    Range (min … max):   151.4 ms … 188.4 ms    1000 runs\n\n  Summary\n    show-ref: single matching ref (revision = HEAD) ran\n      1.04 ± 0.04 times faster than show-ref: single matching ref (revision = HEAD~)\n\nSigned-off-by: Patrick Steinhardt <ps@pks.im>\n---\n reftable/merged.c | 8 ++++++++\n 1 file changed, 8 insertions(+)\n\ndiff --git a/reftable/merged.c b/reftable/merged.c\nindex fb9978d798..0f74a14a77 100644\n--- a/reftable/merged.c\n+++ b/reftable/merged.c\n@@ -107,6 +107,14 @@ static int merged_iter_next_entry(struct merged_iter *mi,\n \t\tstruct pq_entry top = merged_iter_pqueue_top(mi->pq);\n \t\tint cmp;\n \n+\t\t/*\n+\t\t * When the next entry comes from the same queue as the current\n+\t\t * entry then it must by definition be larger. This avoids a\n+\t\t * comparison in the most common case.\n+\t\t */\n+\t\tif (top.index == entry.index)\n+\t\t\tbreak;\n+\n \t\tcmp = reftable_record_cmp(&top.rec, &entry.rec);\n \t\tif (cmp > 0)\n \t\t\tbreak;\n-- \n2.43.GIT\n\n"},{"id":"487728","messageId":"1c9c19a3b3daf9690fda0423c52da33e337c8b54.1706782841.git.ps@pks.im","threadId":"60827","inReplyTo":"cover.1706782841.git.ps@pks.im","subject":"[PATCH 4/7] reftable/pq: allocation-less comparison of entry keys","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-02-01T10:25:10Z","receivedAt":"2024-02-01T10:25:14Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"The priority queue is used by the merged iterator to iterate over\nreftable records from multiple tables in the correct order. The queue\nends up having one record for each table that is being iterated over,\nwith the record that is supposed to be shown next at the top. For\nexample, the key of a ref record is equal to its name so that we end up\nsorting the priority queue lexicographically by ref name.\n\nTo figure out the order we need to compare the reftable record keys with\neach other. This comparison is done by formatting them into a `struct\nstrbuf` and then doing `strbuf_strcmp()` on the result. We then discard\nthe buffers immediately after the comparison.\n\nThis ends up being very expensive. Because the priority queue usually\ncontains as many records as we have tables, we call the comparison\nfunction `O(log($tablecount))` many times for every record we insert.\nFurthermore, when iterating over many refs, we will insert at least one\nrecord for every ref we are iterating over. So ultimately, this ends up\nbeing called `O($refcount * log($tablecount))` many times.\n\nRefactor the code to use the new `refatble_record_cmp()` function that\nhas been implemented in a preceding commit. This function does not need\nto allocate memory and is thus significantly more efficient.\n\nThe following benchmark prints a single ref matching a specific pattern\nout of 1 million refs via git-show-ref(1), where the reftable stack\nconsists of three tables:\n\n  Benchmark 1: show-ref: single matching ref (revision = HEAD~)\n    Time (mean ± σ):     224.4 ms ±   6.5 ms    [User: 220.6 ms, System: 3.6 ms]\n    Range (min … max):   216.5 ms … 261.1 ms    1000 runs\n\n  Benchmark 2: show-ref: single matching ref (revision = HEAD)\n    Time (mean ± σ):     172.9 ms ±   4.4 ms    [User: 169.2 ms, System: 3.6 ms]\n    Range (min … max):   166.5 ms … 204.6 ms    1000 runs\n\n  Summary\n    show-ref: single matching ref (revision = HEAD) ran\n      1.30 ± 0.05 times faster than show-ref: single matching ref (revision = HEAD~)\n\nSigned-off-by: Patrick Steinhardt <ps@pks.im>\n---\n reftable/pq.c | 13 +------------\n 1 file changed, 1 insertion(+), 12 deletions(-)\n\ndiff --git a/reftable/pq.c b/reftable/pq.c\nindex dcefeb793a..7220efc39a 100644\n--- a/reftable/pq.c\n+++ b/reftable/pq.c\n@@ -14,20 +14,9 @@ license that can be found in the LICENSE file or at\n \n int pq_less(struct pq_entry *a, struct pq_entry *b)\n {\n-\tstruct strbuf ak = STRBUF_INIT;\n-\tstruct strbuf bk = STRBUF_INIT;\n-\tint cmp = 0;\n-\treftable_record_key(&a->rec, &ak);\n-\treftable_record_key(&b->rec, &bk);\n-\n-\tcmp = strbuf_cmp(&ak, &bk);\n-\n-\tstrbuf_release(&ak);\n-\tstrbuf_release(&bk);\n-\n+\tint cmp = reftable_record_cmp(&a->rec, &b->rec);\n \tif (cmp == 0)\n \t\treturn a->index > b->index;\n-\n \treturn cmp < 0;\n }\n \n-- \n2.43.GIT\n\n"},{"id":"487729","messageId":"ac3d43c001ba0db34b8caa1435b91f27a01fd5c9.1706782841.git.ps@pks.im","threadId":"60827","inReplyTo":"cover.1706782841.git.ps@pks.im","subject":"[PATCH 5/7] reftable/block: swap buffers instead of copying","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-02-01T10:25:14Z","receivedAt":"2024-02-01T10:25:18Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"When iterating towards the next record in a reftable block we need to\nkeep track of the key that the last record had. This is required because\nreftable records use prefix compression, where subsequent records may\nreuse parts of their preceding record's key.\n\nThis key is stored in the `block_iter::last_key`, which we update after\nevery call to `block_iter_next()`: we simply reset the buffer and then\nadd the current key to it.\n\nThis is a bit inefficient though because it requires us to copy over the\nkey on every iteration, which adds up when iterating over many records.\nInstead, we can make use of the fact that the `block_iter::key` buffer\nis basically only a scratch buffer. So instead of copying over contents,\nwe can just swap both buffers.\n\nThe following benchmark prints a single ref matching a specific pattern\nout of 1 million refs via git-show-ref(1):\n\n  Benchmark 1: show-ref: single matching ref (revision = HEAD~)\n    Time (mean ± σ):     155.7 ms ±   5.0 ms    [User: 152.1 ms, System: 3.4 ms]\n    Range (min … max):   150.8 ms … 185.7 ms    1000 runs\n\n  Benchmark 2: show-ref: single matching ref (revision = HEAD)\n    Time (mean ± σ):     150.8 ms ±   4.2 ms    [User: 147.1 ms, System: 3.5 ms]\n    Range (min … max):   145.1 ms … 180.7 ms    1000 runs\n\n  Summary\n    show-ref: single matching ref (revision = HEAD) ran\n      1.03 ± 0.04 times faster than show-ref: single matching ref (revision = HEAD~)\n\nSigned-off-by: Patrick Steinhardt <ps@pks.im>\n---\n reftable/block.c | 3 +--\n 1 file changed, 1 insertion(+), 2 deletions(-)\n\ndiff --git a/reftable/block.c b/reftable/block.c\nindex 1df3d8a0f0..44381ea6a3 100644\n--- a/reftable/block.c\n+++ b/reftable/block.c\n@@ -342,8 +342,7 @@ int block_iter_next(struct block_iter *it, struct reftable_record *rec)\n \t\treturn -1;\n \tstring_view_consume(&in, n);\n \n-\tstrbuf_reset(&it->last_key);\n-\tstrbuf_addbuf(&it->last_key, &it->key);\n+\tstrbuf_swap(&it->last_key, &it->key);\n \tit->next_off += start.len - in.len;\n \treturn 0;\n }\n-- \n2.43.GIT\n\n"},{"id":"487730","messageId":"41dff8731c308c6d72ebd0066be8963bda725ea2.1706782841.git.ps@pks.im","threadId":"60827","inReplyTo":"cover.1706782841.git.ps@pks.im","subject":"[PATCH 6/7] reftable/record: don't try to reallocate ref record name","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-02-01T10:25:18Z","receivedAt":"2024-02-01T10:25:21Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"When decoding reftable ref records we first release the pointer to the\nrecord passed to us and then use realloc(3P) to allocate the refname\narray. This is a bit misleading though as we know at that point that the\nrefname will always be `NULL`, so we would always end up allocating a\nnew char array anyway.\n\nRefactor the code to use `REFTABLE_ALLOC_ARRAY()` instead. As the\nfollowing benchmark demonstrates this is a tiny bit more efficient. But\nthe bigger selling point really is the gained clarity.\n\n  Benchmark 1: show-ref: single matching ref (revision = HEAD~)\n    Time (mean ± σ):     150.1 ms ±   4.1 ms    [User: 146.6 ms, System: 3.3 ms]\n    Range (min … max):   144.5 ms … 180.5 ms    1000 runs\n\n  Benchmark 2: show-ref: single matching ref (revision = HEAD)\n    Time (mean ± σ):     148.9 ms ±   4.5 ms    [User: 145.2 ms, System: 3.4 ms]\n    Range (min … max):   143.0 ms … 185.4 ms    1000 runs\n\n  Summary\n    show-ref: single matching ref (revision = HEAD) ran\n      1.01 ± 0.04 times faster than show-ref: single matching ref (revision = HEAD~)\n\nIdeally, we should try and reuse the memory of the old record instead of\nfirst freeing and then immediately reallocating it. This requires some\nmore surgery though and is thus left for a future iteration.\n\nSigned-off-by: Patrick Steinhardt <ps@pks.im>\n---\n reftable/record.c | 5 +++--\n 1 file changed, 3 insertions(+), 2 deletions(-)\n\ndiff --git a/reftable/record.c b/reftable/record.c\nindex f1b6a5eac9..6465a7b8f4 100644\n--- a/reftable/record.c\n+++ b/reftable/record.c\n@@ -377,10 +377,11 @@ static int reftable_ref_record_decode(void *rec, struct strbuf key,\n \n \tassert(hash_size > 0);\n \n-\tr->refname = reftable_realloc(r->refname, key.len + 1);\n+\tr->refname = reftable_malloc(key.len + 1);\n \tmemcpy(r->refname, key.buf, key.len);\n-\tr->update_index = update_index;\n \tr->refname[key.len] = 0;\n+\n+\tr->update_index = update_index;\n \tr->value_type = val_type;\n \tswitch (val_type) {\n \tcase REFTABLE_REF_VAL1:\n-- \n2.43.GIT\n\n"},{"id":"487731","messageId":"2f1f1dd95e1cc360bde3547bd18e227a9c326e13.1706782841.git.ps@pks.im","threadId":"60827","inReplyTo":"cover.1706782841.git.ps@pks.im","subject":"[PATCH 7/7] reftable/reader: add comments to `table_iter_next()`","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-02-01T10:25:22Z","receivedAt":"2024-02-01T10:25:25Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"While working on the optimizations in the preceding patches I stumbled\nupon `table_iter_next()` multiple times. It is quite easy to miss the\nfact that we don't call `table_iter_next_in_block()` twice, but that the\nsecond call is in fact `table_iter_next_block()`.\n\nAdd comments to explain what exactly is going on here to make things\nmore obvious. While at it, touch up the code to conform to our code\nstyle better.\n\nSigned-off-by: Patrick Steinhardt <ps@pks.im>\n---\n reftable/reader.c | 26 +++++++++++++++++---------\n 1 file changed, 17 insertions(+), 9 deletions(-)\n\ndiff --git a/reftable/reader.c b/reftable/reader.c\nindex 64dc366fb1..add7d57f0b 100644\n--- a/reftable/reader.c\n+++ b/reftable/reader.c\n@@ -357,24 +357,32 @@ static int table_iter_next(struct table_iter *ti, struct reftable_record *rec)\n \n \twhile (1) {\n \t\tstruct table_iter next = TABLE_ITER_INIT;\n-\t\tint err = 0;\n-\t\tif (ti->is_finished) {\n+\t\tint err;\n+\n+\t\tif (ti->is_finished)\n \t\t\treturn 1;\n-\t\t}\n \n+\t\t/*\n+\t\t * Check whether the current block still has more records. If\n+\t\t * so, return it. If the iterator returns positive then the\n+\t\t * current block has been exhausted.\n+\t\t */\n \t\terr = table_iter_next_in_block(ti, rec);\n-\t\tif (err <= 0) {\n+\t\tif (err <= 0)\n \t\t\treturn err;\n-\t\t}\n \n+\t\t/*\n+\t\t * Otherwise, we need to continue to the next block in the\n+\t\t * table and retry. If there are no more blocks then the\n+\t\t * iterator is drained.\n+\t\t */\n \t\terr = table_iter_next_block(&next, ti);\n-\t\tif (err != 0) {\n-\t\t\tti->is_finished = 1;\n-\t\t}\n \t\ttable_iter_block_done(ti);\n-\t\tif (err != 0) {\n+\t\tif (err) {\n+\t\t\tti->is_finished = 1;\n \t\t\treturn err;\n \t\t}\n+\n \t\ttable_iter_copy_from(ti, &next);\n \t\tblock_iter_close(&next.bi);\n \t}\n-- \n2.43.GIT\n\n"},{"id":"487745","messageId":"CAPig+cR0iMPQWeTjC3RVnJFydGL6ZNdV3O63uC84VJ+TJhv_Ew@mail.gmail.com","threadId":"60827","inReplyTo":"fadabec696f75ae0fa25bcbf87012fcc4768acaa.1706782841.git.ps@pks.im","subject":"Re: [PATCH 1/7] reftable/record: introduce function to compare records by key","fromName":"Eric Sunshine","fromEmail":"sunshine@sunshineco.com","sentAt":"2024-02-01T15:00:41Z","receivedAt":"2024-02-01T15:00:55Z","isPatch":true,"sender":{"key":"sunshine@sunshineco.com","avatar":"https://avatars.githubusercontent.com/u/163641?v=4"},"body":"On Thu, Feb 1, 2024 at 8:31 AM Patrick Steinhardt <ps@pks.im> wrote:\n> In some places we need to sort reftable records by their keys to\n> determine their ordering. This is done by first formatting the keys into\n> a `struct strbuf` and then using `strbuf_cmp()` to compare them. This\n> logic is needlessly roundabout and can end up costing quite a bit fo CPU\n> cycles, both due to the allocation and formatting logic.\n\ns/fo/of/\n\n> Introduce a new `reftable_record_cmp()` function that knows to compare\n> two records with each other without requiring allocations.\n\nperhaps: s/knows to compare/knows how to compare/\n\n> Signed-off-by: Patrick Steinhardt <ps@pks.im>\n"},{"id":"487756","messageId":"CAPig+cQwgYdKCHnu1TUj2JYyQkRF6Ey4hw1MvAVpfhqcwjV04w@mail.gmail.com","threadId":"60827","inReplyTo":"0ca86eba710895f0e22fc15fe5221f5487031f64.1706782841.git.ps@pks.im","subject":"Re: [PATCH 3/7] reftable/merged: skip comparison for records of the same subiter","fromName":"Eric Sunshine","fromEmail":"sunshine@sunshineco.com","sentAt":"2024-02-01T17:29:16Z","receivedAt":"2024-02-01T17:29:29Z","isPatch":true,"sender":{"key":"sunshine@sunshineco.com","avatar":"https://avatars.githubusercontent.com/u/163641?v=4"},"body":"On Thu, Feb 1, 2024 at 8:17 AM Patrick Steinhardt <ps@pks.im> wrote:\n> When retrieving the next entry of a merged iterator we need to drop all\n> records of other sub-iterators that would be shadowed by the record that\n> we are about to return. We do this by comparing record keys, dropping\n> all keys that are smaller or equal to the key of the record we are about\n> to return.\n>\n> There is an edge case here where we can skip that comparison: when the\n> record in the priority queue comes from the same subiterator than the\n\ns/than/as/\n\n> record we are about to return then we know that its key must be larger\n> than the key of the record we are about to return. This property is\n> guaranteed by the sub-iterators, and if it didn't hold then the whole\n> merged iterator would return records in the wrong order, too.\n>\n> While this may seem like a very specific edge case it's in fact quite\n> likely to happen. For most repositories out there you can assume that we\n> will end up with one large table and several smaller ones on top of it.\n> Thus, it is very likely that the next entry will sort towards the top of\n> the priority queue.\n>\n> Special case this and break out of the loop in that case. The following\n> benchmark uses git-show-ref(1) to print a single ref matching a pattern\n> out of 1 million refs:\n>\n>   Benchmark 1: show-ref: single matching ref (revision = HEAD~)\n>     Time (mean ± σ):     162.6 ms ±   4.5 ms    [User: 159.0 ms, System: 3.5 ms]\n>     Range (min … max):   156.6 ms … 188.5 ms    1000 runs\n>\n>   Benchmark 2: show-ref: single matching ref (revision = HEAD)\n>     Time (mean ± σ):     156.8 ms ±   4.7 ms    [User: 153.0 ms, System: 3.6 ms]\n>     Range (min … max):   151.4 ms … 188.4 ms    1000 runs\n>\n>   Summary\n>     show-ref: single matching ref (revision = HEAD) ran\n>       1.04 ± 0.04 times faster than show-ref: single matching ref (revision = HEAD~)\n>\n> Signed-off-by: Patrick Steinhardt <ps@pks.im>\n"},{"id":"487789","messageId":"Zbx6aDzXpYy4Is2t@tanuki","threadId":"60827","inReplyTo":"CAPig+cQwgYdKCHnu1TUj2JYyQkRF6Ey4hw1MvAVpfhqcwjV04w@mail.gmail.com","subject":"Re: [PATCH 3/7] reftable/merged: skip comparison for records of the same subiter","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-02-02T05:15:20Z","receivedAt":"2024-02-02T05:15:25Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"On Thu, Feb 01, 2024 at 12:29:16PM -0500, Eric Sunshine wrote:\n> On Thu, Feb 1, 2024 at 8:17 AM Patrick Steinhardt <ps@pks.im> wrote:\n> > When retrieving the next entry of a merged iterator we need to drop all\n> > records of other sub-iterators that would be shadowed by the record that\n> > we are about to return. We do this by comparing record keys, dropping\n> > all keys that are smaller or equal to the key of the record we are about\n> > to return.\n> >\n> > There is an edge case here where we can skip that comparison: when the\n> > record in the priority queue comes from the same subiterator than the\n> \n> s/than/as/\n\nThanks for your corrections, as usual :) I'll refrain from sending a v2\nfor now, but have squashed the fixes in while I wait for more feedback\non this series.\n\nPatrick\n"},{"id":"488294","messageId":"5335108F-4A21-4429-9BDF-3923D96884C0@gmail.com","threadId":"60827","inReplyTo":"2f1f1dd95e1cc360bde3547bd18e227a9c326e13.1706782841.git.ps@pks.im","subject":"Re: [PATCH 7/7] reftable/reader: add comments to `table_iter_next()`","fromName":"John Cai","fromEmail":"johncai86@gmail.com","sentAt":"2024-02-09T16:01:13Z","receivedAt":"2024-02-09T16:01:15Z","isPatch":true,"sender":{"key":"johncai86@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2354211?v=4"},"body":"\nHi Patrick,\n\nOn 1 Feb 2024, at 5:25, Patrick Steinhardt wrote:\n\n> While working on the optimizations in the preceding patches I stumbled\n> upon `table_iter_next()` multiple times. It is quite easy to miss the\n> fact that we don't call `table_iter_next_in_block()` twice, but that the\n> second call is in fact `table_iter_next_block()`.\n>\n> Add comments to explain what exactly is going on here to make things\n> more obvious. While at it, touch up the code to conform to our code\n> style better.\n>\n> Signed-off-by: Patrick Steinhardt <ps@pks.im>\n> ---\n>  reftable/reader.c | 26 +++++++++++++++++---------\n>  1 file changed, 17 insertions(+), 9 deletions(-)\n>\n> diff --git a/reftable/reader.c b/reftable/reader.c\n> index 64dc366fb1..add7d57f0b 100644\n> --- a/reftable/reader.c\n> +++ b/reftable/reader.c\n> @@ -357,24 +357,32 @@ static int table_iter_next(struct table_iter *ti, struct reftable_record *rec)\n>\n>  \twhile (1) {\n>  \t\tstruct table_iter next = TABLE_ITER_INIT;\n> -\t\tint err = 0;\n> -\t\tif (ti->is_finished) {\n> +\t\tint err;\n> +\n> +\t\tif (ti->is_finished)\n>  \t\t\treturn 1;\n> -\t\t}\n>\n> +\t\t/*\n> +\t\t * Check whether the current block still has more records. If\n> +\t\t * so, return it. If the iterator returns positive then the\n> +\t\t * current block has been exhausted.\n> +\t\t */\n>  \t\terr = table_iter_next_in_block(ti, rec);\n> -\t\tif (err <= 0) {\n> +\t\tif (err <= 0)\n>  \t\t\treturn err;\n> -\t\t}\n>\n> +\t\t/*\n> +\t\t * Otherwise, we need to continue to the next block in the\n> +\t\t * table and retry. If there are no more blocks then the\n> +\t\t * iterator is drained.\n> +\t\t */\n>  \t\terr = table_iter_next_block(&next, ti);\n> -\t\tif (err != 0) {\n> -\t\t\tti->is_finished = 1;\n> -\t\t}\n>  \t\ttable_iter_block_done(ti);\n> -\t\tif (err != 0) {\n> +\t\tif (err) {\n\nwhat's the reason for moving the if statement that handles err down after\ntable_iter_block_done?\n\n> +\t\t\tti->is_finished = 1;\n>  \t\t\treturn err;\n>  \t\t}\n> +\n>  \t\ttable_iter_copy_from(ti, &next);\n>  \t\tblock_iter_close(&next.bi);\n>  \t}\n> -- \n> 2.43.GIT\n\nThanks\nJohn\n"},{"id":"488431","messageId":"ZcnV1ULJaurT99tJ@tanuki","threadId":"60827","inReplyTo":"5335108F-4A21-4429-9BDF-3923D96884C0@gmail.com","subject":"Re: [PATCH 7/7] reftable/reader: add comments to `table_iter_next()`","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-02-12T08:24:53Z","receivedAt":"2024-02-12T08:24:58Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"On Fri, Feb 09, 2024 at 11:01:13AM -0500, John Cai wrote:\n> \n> Hi Patrick,\n> \n> On 1 Feb 2024, at 5:25, Patrick Steinhardt wrote:\n> \n> > While working on the optimizations in the preceding patches I stumbled\n> > upon `table_iter_next()` multiple times. It is quite easy to miss the\n> > fact that we don't call `table_iter_next_in_block()` twice, but that the\n> > second call is in fact `table_iter_next_block()`.\n> >\n> > Add comments to explain what exactly is going on here to make things\n> > more obvious. While at it, touch up the code to conform to our code\n> > style better.\n> >\n> > Signed-off-by: Patrick Steinhardt <ps@pks.im>\n> > ---\n> >  reftable/reader.c | 26 +++++++++++++++++---------\n> >  1 file changed, 17 insertions(+), 9 deletions(-)\n> >\n> > diff --git a/reftable/reader.c b/reftable/reader.c\n> > index 64dc366fb1..add7d57f0b 100644\n> > --- a/reftable/reader.c\n> > +++ b/reftable/reader.c\n> > @@ -357,24 +357,32 @@ static int table_iter_next(struct table_iter *ti, struct reftable_record *rec)\n> >\n> >  \twhile (1) {\n> >  \t\tstruct table_iter next = TABLE_ITER_INIT;\n> > -\t\tint err = 0;\n> > -\t\tif (ti->is_finished) {\n> > +\t\tint err;\n> > +\n> > +\t\tif (ti->is_finished)\n> >  \t\t\treturn 1;\n> > -\t\t}\n> >\n> > +\t\t/*\n> > +\t\t * Check whether the current block still has more records. If\n> > +\t\t * so, return it. If the iterator returns positive then the\n> > +\t\t * current block has been exhausted.\n> > +\t\t */\n> >  \t\terr = table_iter_next_in_block(ti, rec);\n> > -\t\tif (err <= 0) {\n> > +\t\tif (err <= 0)\n> >  \t\t\treturn err;\n> > -\t\t}\n> >\n> > +\t\t/*\n> > +\t\t * Otherwise, we need to continue to the next block in the\n> > +\t\t * table and retry. If there are no more blocks then the\n> > +\t\t * iterator is drained.\n> > +\t\t */\n> >  \t\terr = table_iter_next_block(&next, ti);\n> > -\t\tif (err != 0) {\n> > -\t\t\tti->is_finished = 1;\n> > -\t\t}\n> >  \t\ttable_iter_block_done(ti);\n> > -\t\tif (err != 0) {\n> > +\t\tif (err) {\n> \n> what's the reason for moving the if statement that handles err down after\n> table_iter_block_done?\n\nGood question. Ultimately, it's a simplification because I just merge\nthe two blocks which checked for `err != 0` into a single block. There\nis no need to mark the iterator as finished before calling\n`table_iter_block_done()`.\n\nSo becaiuse `table_iter_block_done()` doesn't inspect `is_finished`,\nthese two implementations are in the end equivalent. Before:\n\n```\nif (err)\n    ti->is_finished = 1;\ntable_iter_block_done(ti);\nif (err)\n    return err;\n```\n\nAfter:\n\n```\ntable_iter_block_done(ti);\nif (err) {\n    ti->is_finished = 1;\n    return err;\n}\n```\n\nThe latter is much easier to reason about I think. It's also more\nefficient because there's one branch less.\n\nPatrick\n"},{"id":"488432","messageId":"cover.1707726654.git.ps@pks.im","threadId":"60827","inReplyTo":"cover.1706782841.git.ps@pks.im","subject":"[PATCH v2 0/7] reftable: improve ref iteration performance","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-02-12T08:32:21Z","receivedAt":"2024-02-12T08:32:26Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"Hi,\n\nthis is the second version of my patch series that improves ref\niteration performance. There are no code changes compared to v1, but a\nfew improvements to the commit messages.\n\nThanks!\n\nPatrick\n\nPatrick Steinhardt (7):\n  reftable/record: introduce function to compare records by key\n  reftable/merged: allocation-less dropping of shadowed records\n  reftable/merged: skip comparison for records of the same subiter\n  reftable/pq: allocation-less comparison of entry keys\n  reftable/block: swap buffers instead of copying\n  reftable/record: don't try to reallocate ref record name\n  reftable/reader: add comments to `table_iter_next()`\n\n reftable/block.c  |  3 +--\n reftable/merged.c | 19 +++++++-------\n reftable/merged.h |  2 --\n reftable/pq.c     | 13 +--------\n reftable/reader.c | 26 +++++++++++-------\n reftable/record.c | 67 ++++++++++++++++++++++++++++++++++++++++++++---\n reftable/record.h |  7 +++++\n 7 files changed, 100 insertions(+), 37 deletions(-)\n\nRange-diff against v1:\n1:  fadabec696 ! 1:  bcdb5a2bf0 reftable/record: introduce function to compare records by key\n    @@ Commit message\n         In some places we need to sort reftable records by their keys to\n         determine their ordering. This is done by first formatting the keys into\n         a `struct strbuf` and then using `strbuf_cmp()` to compare them. This\n    -    logic is needlessly roundabout and can end up costing quite a bit fo CPU\n    +    logic is needlessly roundabout and can end up costing quite a bit of CPU\n         cycles, both due to the allocation and formatting logic.\n     \n    -    Introduce a new `reftable_record_cmp()` function that knows to compare\n    -    two records with each other without requiring allocations.\n    +    Introduce a new `reftable_record_cmp()` function that knows how to\n    +    compare two records with each other without requiring allocations.\n     \n         Signed-off-by: Patrick Steinhardt <ps@pks.im>\n     \n2:  576a96f2e5 = 2:  2364a0fa33 reftable/merged: allocation-less dropping of shadowed records\n3:  0ca86eba71 ! 3:  205e6b488b reftable/merged: skip comparison for records of the same subiter\n    @@ Commit message\n         to return.\n     \n         There is an edge case here where we can skip that comparison: when the\n    -    record in the priority queue comes from the same subiterator than the\n    +    record in the priority queue comes from the same subiterator as the\n         record we are about to return then we know that its key must be larger\n         than the key of the record we are about to return. This property is\n         guaranteed by the sub-iterators, and if it didn't hold then the whole\n4:  1c9c19a3b3 = 4:  fd09ba70fe reftable/pq: allocation-less comparison of entry keys\n5:  ac3d43c001 = 5:  2317aa43b9 reftable/block: swap buffers instead of copying\n6:  41dff8731c = 6:  8c67491504 reftable/record: don't try to reallocate ref record name\n7:  2f1f1dd95e ! 7:  167f67fad8 reftable/reader: add comments to `table_iter_next()`\n    @@ Commit message\n         more obvious. While at it, touch up the code to conform to our code\n         style better.\n     \n    +    Note that one of the refactorings merges two conditional blocks into\n    +    one. Before, we had the following code:\n    +\n    +    ```\n    +    err = table_iter_next_block(&next, ti\n    +    if (err != 0) {\n    +            ti->is_finished = 1;\n    +    }\n    +    table_iter_block_done(ti);\n    +    if (err != 0) {\n    +            return err;\n    +    }\n    +    ```\n    +\n    +    As `table_iter_block_done()` does not care about `is_finished`, the\n    +    conditional blocks can be merged into one block:\n    +\n    +    ```\n    +    err = table_iter_next_block(&next, ti\n    +    table_iter_block_done(ti);\n    +    if (err != 0) {\n    +            ti->is_finished = 1;\n    +            return err;\n    +    }\n    +    ```\n    +\n    +    This is both easier to reason about and more performant because we have\n    +    one branch less.\n    +\n         Signed-off-by: Patrick Steinhardt <ps@pks.im>\n     \n      ## reftable/reader.c ##\n\nbase-commit: c875e0b8e036c12cfbf6531962108a063c7a821c\n-- \n2.43.GIT\n\n"},{"id":"488433","messageId":"bcdb5a2bf0acb5cc25756df10845a60197868db8.1707726654.git.ps@pks.im","threadId":"60827","inReplyTo":"cover.1707726654.git.ps@pks.im","subject":"[PATCH v2 1/7] reftable/record: introduce function to compare records by key","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-02-12T08:32:25Z","receivedAt":"2024-02-12T08:32:29Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"In some places we need to sort reftable records by their keys to\ndetermine their ordering. This is done by first formatting the keys into\na `struct strbuf` and then using `strbuf_cmp()` to compare them. This\nlogic is needlessly roundabout and can end up costing quite a bit of CPU\ncycles, both due to the allocation and formatting logic.\n\nIntroduce a new `reftable_record_cmp()` function that knows how to\ncompare two records with each other without requiring allocations.\n\nSigned-off-by: Patrick Steinhardt <ps@pks.im>\n---\n reftable/record.c | 62 ++++++++++++++++++++++++++++++++++++++++++++++-\n reftable/record.h |  7 ++++++\n 2 files changed, 68 insertions(+), 1 deletion(-)\n\ndiff --git a/reftable/record.c b/reftable/record.c\nindex 5c3fbb7b2a..f1b6a5eac9 100644\n--- a/reftable/record.c\n+++ b/reftable/record.c\n@@ -430,7 +430,6 @@ static int reftable_ref_record_is_deletion_void(const void *p)\n \t\t(const struct reftable_ref_record *)p);\n }\n \n-\n static int reftable_ref_record_equal_void(const void *a,\n \t\t\t\t\t  const void *b, int hash_size)\n {\n@@ -439,6 +438,13 @@ static int reftable_ref_record_equal_void(const void *a,\n \treturn reftable_ref_record_equal(ra, rb, hash_size);\n }\n \n+static int reftable_ref_record_cmp_void(const void *_a, const void *_b)\n+{\n+\tconst struct reftable_ref_record *a = _a;\n+\tconst struct reftable_ref_record *b = _b;\n+\treturn strcmp(a->refname, b->refname);\n+}\n+\n static void reftable_ref_record_print_void(const void *rec,\n \t\t\t\t\t   int hash_size)\n {\n@@ -455,6 +461,7 @@ static struct reftable_record_vtable reftable_ref_record_vtable = {\n \t.release = &reftable_ref_record_release_void,\n \t.is_deletion = &reftable_ref_record_is_deletion_void,\n \t.equal = &reftable_ref_record_equal_void,\n+\t.cmp = &reftable_ref_record_cmp_void,\n \t.print = &reftable_ref_record_print_void,\n };\n \n@@ -625,6 +632,25 @@ static int reftable_obj_record_equal_void(const void *a, const void *b, int hash\n \treturn 1;\n }\n \n+static int reftable_obj_record_cmp_void(const void *_a, const void *_b)\n+{\n+\tconst struct reftable_obj_record *a = _a;\n+\tconst struct reftable_obj_record *b = _b;\n+\tint cmp;\n+\n+\tcmp = memcmp(a->hash_prefix, b->hash_prefix,\n+\t\t     a->hash_prefix_len > b->hash_prefix_len ?\n+\t\t     a->hash_prefix_len : b->hash_prefix_len);\n+\tif (cmp)\n+\t\treturn cmp;\n+\n+\t/*\n+\t * When the prefix is the same then the object record that is longer is\n+\t * considered to be bigger.\n+\t */\n+\treturn a->hash_prefix_len - b->hash_prefix_len;\n+}\n+\n static struct reftable_record_vtable reftable_obj_record_vtable = {\n \t.key = &reftable_obj_record_key,\n \t.type = BLOCK_TYPE_OBJ,\n@@ -635,6 +661,7 @@ static struct reftable_record_vtable reftable_obj_record_vtable = {\n \t.release = &reftable_obj_record_release,\n \t.is_deletion = &not_a_deletion,\n \t.equal = &reftable_obj_record_equal_void,\n+\t.cmp = &reftable_obj_record_cmp_void,\n \t.print = &reftable_obj_record_print,\n };\n \n@@ -953,6 +980,22 @@ static int reftable_log_record_equal_void(const void *a,\n \t\t\t\t\t hash_size);\n }\n \n+static int reftable_log_record_cmp_void(const void *_a, const void *_b)\n+{\n+\tconst struct reftable_log_record *a = _a;\n+\tconst struct reftable_log_record *b = _b;\n+\tint cmp = strcmp(a->refname, b->refname);\n+\tif (cmp)\n+\t\treturn cmp;\n+\n+\t/*\n+\t * Note that the comparison here is reversed. This is because the\n+\t * update index is reversed when comparing keys. For reference, see how\n+\t * we handle this in reftable_log_record_key()`.\n+\t */\n+\treturn b->update_index - a->update_index;\n+}\n+\n int reftable_log_record_equal(const struct reftable_log_record *a,\n \t\t\t      const struct reftable_log_record *b, int hash_size)\n {\n@@ -1002,6 +1045,7 @@ static struct reftable_record_vtable reftable_log_record_vtable = {\n \t.release = &reftable_log_record_release_void,\n \t.is_deletion = &reftable_log_record_is_deletion_void,\n \t.equal = &reftable_log_record_equal_void,\n+\t.cmp = &reftable_log_record_cmp_void,\n \t.print = &reftable_log_record_print_void,\n };\n \n@@ -1077,6 +1121,13 @@ static int reftable_index_record_equal(const void *a, const void *b, int hash_si\n \treturn ia->offset == ib->offset && !strbuf_cmp(&ia->last_key, &ib->last_key);\n }\n \n+static int reftable_index_record_cmp(const void *_a, const void *_b)\n+{\n+\tconst struct reftable_index_record *a = _a;\n+\tconst struct reftable_index_record *b = _b;\n+\treturn strbuf_cmp(&a->last_key, &b->last_key);\n+}\n+\n static void reftable_index_record_print(const void *rec, int hash_size)\n {\n \tconst struct reftable_index_record *idx = rec;\n@@ -1094,6 +1145,7 @@ static struct reftable_record_vtable reftable_index_record_vtable = {\n \t.release = &reftable_index_record_release,\n \t.is_deletion = &not_a_deletion,\n \t.equal = &reftable_index_record_equal,\n+\t.cmp = &reftable_index_record_cmp,\n \t.print = &reftable_index_record_print,\n };\n \n@@ -1147,6 +1199,14 @@ int reftable_record_is_deletion(struct reftable_record *rec)\n \t\treftable_record_data(rec));\n }\n \n+int reftable_record_cmp(struct reftable_record *a, struct reftable_record *b)\n+{\n+\tif (a->type != b->type)\n+\t\tBUG(\"cannot compare reftable records of different type\");\n+\treturn reftable_record_vtable(a)->cmp(\n+\t\treftable_record_data(a), reftable_record_data(b));\n+}\n+\n int reftable_record_equal(struct reftable_record *a, struct reftable_record *b, int hash_size)\n {\n \tif (a->type != b->type)\ndiff --git a/reftable/record.h b/reftable/record.h\nindex fd80cd451d..0d96fbfd1b 100644\n--- a/reftable/record.h\n+++ b/reftable/record.h\n@@ -62,6 +62,12 @@ struct reftable_record_vtable {\n \t/* Are two records equal? This assumes they have the same type. Returns 0 for non-equal. */\n \tint (*equal)(const void *a, const void *b, int hash_size);\n \n+\t/*\n+\t * Compare keys of two records with each other. The records must have\n+\t * the same type.\n+\t */\n+\tint (*cmp)(const void *a, const void *b);\n+\n \t/* Print on stdout, for debugging. */\n \tvoid (*print)(const void *rec, int hash_size);\n };\n@@ -114,6 +120,7 @@ struct reftable_record {\n };\n \n /* see struct record_vtable */\n+int reftable_record_cmp(struct reftable_record *a, struct reftable_record *b);\n int reftable_record_equal(struct reftable_record *a, struct reftable_record *b, int hash_size);\n void reftable_record_print(struct reftable_record *rec, int hash_size);\n void reftable_record_key(struct reftable_record *rec, struct strbuf *dest);\n-- \n2.43.GIT\n\n"},{"id":"488434","messageId":"2364a0fa3369063355bed966267a19fb9af3a6b6.1707726654.git.ps@pks.im","threadId":"60827","inReplyTo":"cover.1707726654.git.ps@pks.im","subject":"[PATCH v2 2/7] reftable/merged: allocation-less dropping of shadowed records","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-02-12T08:32:29Z","receivedAt":"2024-02-12T08:32:33Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"The purpose of the merged reftable iterator is to iterate through all\nentries of a set of tables in the correct order. This is implemented by\nusing a sub-iterator for each table, where the next entry of each of\nthese iterators gets put into a priority queue. For each iteration, we\ndo roughly the following steps:\n\n  1. Retrieve the top record of the priority queue. This is the entry we\n     want to return to the caller.\n\n  2. Retrieve the next record of the sub-iterator that this record came\n     from. If any, add it to the priority queue at the correct position.\n     The position is determined by comparing the record keys, which e.g.\n     corresponds to the refname for ref records.\n\n  3. Keep removing the top record of the priority queue until we hit the\n     first entry whose key is larger than the returned record's key.\n     This is required to drop \"shadowed\" records.\n\nThe last step will lead to at least one comparison to the next entry,\nbut may lead to many comparisons in case the reftable stack consists of\nmany tables with shadowed records. It is thus part of the hot code path\nwhen iterating through records.\n\nThe code to compare the entries with each other is quite inefficient\nthough. Instead of comparing record keys with each other directly, we\nfirst format them into `struct strbuf`s and only then compare them with\neach other. While we already optimized this code path to reuse buffers\nin 829231dc20 (reftable/merged: reuse buffer to compute record keys,\n2023-12-11), the cost to format the keys into the buffers still adds up\nquite significantly.\n\nRefactor the code to use `reftable_record_cmp()` instead, which has been\nintroduced in the preceding commit. This function compares records with\neach other directly without requiring any memory allocations or copying\nand is thus way more efficient.\n\nThe following benchmark uses git-show-ref(1) to print a single ref\nmatching a pattern out of 1 million refs. This is the most direct way to\nexercise ref iteration speed as we remove all overhead of having to show\nthe refs, too.\n\n    Benchmark 1: show-ref: single matching ref (revision = HEAD~)\n      Time (mean ± σ):     180.7 ms ±   4.7 ms    [User: 177.1 ms, System: 3.4 ms]\n      Range (min … max):   174.9 ms … 211.7 ms    1000 runs\n\n    Benchmark 2: show-ref: single matching ref (revision = HEAD)\n      Time (mean ± σ):     162.1 ms ±   4.4 ms    [User: 158.5 ms, System: 3.4 ms]\n      Range (min … max):   155.4 ms … 189.3 ms    1000 runs\n\n    Summary\n      show-ref: single matching ref (revision = HEAD) ran\n        1.11 ± 0.04 times faster than show-ref: single matching ref (revision = HEAD~)\n\nSigned-off-by: Patrick Steinhardt <ps@pks.im>\n---\n reftable/merged.c | 11 ++---------\n reftable/merged.h |  2 --\n 2 files changed, 2 insertions(+), 11 deletions(-)\n\ndiff --git a/reftable/merged.c b/reftable/merged.c\nindex c258ce953e..fb9978d798 100644\n--- a/reftable/merged.c\n+++ b/reftable/merged.c\n@@ -51,8 +51,6 @@ static void merged_iter_close(void *p)\n \t\treftable_iterator_destroy(&mi->stack[i]);\n \t}\n \treftable_free(mi->stack);\n-\tstrbuf_release(&mi->key);\n-\tstrbuf_release(&mi->entry_key);\n }\n \n static int merged_iter_advance_nonnull_subiter(struct merged_iter *mi,\n@@ -105,14 +103,11 @@ static int merged_iter_next_entry(struct merged_iter *mi,\n \t  such a deployment, the loop below must be changed to collect all\n \t  entries for the same key, and return new the newest one.\n \t*/\n-\treftable_record_key(&entry.rec, &mi->entry_key);\n \twhile (!merged_iter_pqueue_is_empty(mi->pq)) {\n \t\tstruct pq_entry top = merged_iter_pqueue_top(mi->pq);\n-\t\tint cmp = 0;\n+\t\tint cmp;\n \n-\t\treftable_record_key(&top.rec, &mi->key);\n-\n-\t\tcmp = strbuf_cmp(&mi->key, &mi->entry_key);\n+\t\tcmp = reftable_record_cmp(&top.rec, &entry.rec);\n \t\tif (cmp > 0)\n \t\t\tbreak;\n \n@@ -246,8 +241,6 @@ static int merged_table_seek_record(struct reftable_merged_table *mt,\n \t\t.typ = reftable_record_type(rec),\n \t\t.hash_id = mt->hash_id,\n \t\t.suppress_deletions = mt->suppress_deletions,\n-\t\t.key = STRBUF_INIT,\n-\t\t.entry_key = STRBUF_INIT,\n \t};\n \tint n = 0;\n \tint err = 0;\ndiff --git a/reftable/merged.h b/reftable/merged.h\nindex d5b39dfe7f..7d9f95d27e 100644\n--- a/reftable/merged.h\n+++ b/reftable/merged.h\n@@ -31,8 +31,6 @@ struct merged_iter {\n \tuint8_t typ;\n \tint suppress_deletions;\n \tstruct merged_iter_pqueue pq;\n-\tstruct strbuf key;\n-\tstruct strbuf entry_key;\n };\n \n void merged_table_release(struct reftable_merged_table *mt);\n-- \n2.43.GIT\n\n"},{"id":"488435","messageId":"205e6b488be9165d08e0fecb6197ebfc6747ba1c.1707726654.git.ps@pks.im","threadId":"60827","inReplyTo":"cover.1707726654.git.ps@pks.im","subject":"[PATCH v2 3/7] reftable/merged: skip comparison for records of the same subiter","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-02-12T08:32:37Z","receivedAt":"2024-02-12T08:32:41Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"When retrieving the next entry of a merged iterator we need to drop all\nrecords of other sub-iterators that would be shadowed by the record that\nwe are about to return. We do this by comparing record keys, dropping\nall keys that are smaller or equal to the key of the record we are about\nto return.\n\nThere is an edge case here where we can skip that comparison: when the\nrecord in the priority queue comes from the same subiterator as the\nrecord we are about to return then we know that its key must be larger\nthan the key of the record we are about to return. This property is\nguaranteed by the sub-iterators, and if it didn't hold then the whole\nmerged iterator would return records in the wrong order, too.\n\nWhile this may seem like a very specific edge case it's in fact quite\nlikely to happen. For most repositories out there you can assume that we\nwill end up with one large table and several smaller ones on top of it.\nThus, it is very likely that the next entry will sort towards the top of\nthe priority queue.\n\nSpecial case this and break out of the loop in that case. The following\nbenchmark uses git-show-ref(1) to print a single ref matching a pattern\nout of 1 million refs:\n\n  Benchmark 1: show-ref: single matching ref (revision = HEAD~)\n    Time (mean ± σ):     162.6 ms ±   4.5 ms    [User: 159.0 ms, System: 3.5 ms]\n    Range (min … max):   156.6 ms … 188.5 ms    1000 runs\n\n  Benchmark 2: show-ref: single matching ref (revision = HEAD)\n    Time (mean ± σ):     156.8 ms ±   4.7 ms    [User: 153.0 ms, System: 3.6 ms]\n    Range (min … max):   151.4 ms … 188.4 ms    1000 runs\n\n  Summary\n    show-ref: single matching ref (revision = HEAD) ran\n      1.04 ± 0.04 times faster than show-ref: single matching ref (revision = HEAD~)\n\nSigned-off-by: Patrick Steinhardt <ps@pks.im>\n---\n reftable/merged.c | 8 ++++++++\n 1 file changed, 8 insertions(+)\n\ndiff --git a/reftable/merged.c b/reftable/merged.c\nindex fb9978d798..0f74a14a77 100644\n--- a/reftable/merged.c\n+++ b/reftable/merged.c\n@@ -107,6 +107,14 @@ static int merged_iter_next_entry(struct merged_iter *mi,\n \t\tstruct pq_entry top = merged_iter_pqueue_top(mi->pq);\n \t\tint cmp;\n \n+\t\t/*\n+\t\t * When the next entry comes from the same queue as the current\n+\t\t * entry then it must by definition be larger. This avoids a\n+\t\t * comparison in the most common case.\n+\t\t */\n+\t\tif (top.index == entry.index)\n+\t\t\tbreak;\n+\n \t\tcmp = reftable_record_cmp(&top.rec, &entry.rec);\n \t\tif (cmp > 0)\n \t\t\tbreak;\n-- \n2.43.GIT\n\n"},{"id":"488436","messageId":"fd09ba70fe16216114781dba9dd4d197bd0c4258.1707726654.git.ps@pks.im","threadId":"60827","inReplyTo":"cover.1707726654.git.ps@pks.im","subject":"[PATCH v2 4/7] reftable/pq: allocation-less comparison of entry keys","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-02-12T08:32:43Z","receivedAt":"2024-02-12T08:32:47Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"The priority queue is used by the merged iterator to iterate over\nreftable records from multiple tables in the correct order. The queue\nends up having one record for each table that is being iterated over,\nwith the record that is supposed to be shown next at the top. For\nexample, the key of a ref record is equal to its name so that we end up\nsorting the priority queue lexicographically by ref name.\n\nTo figure out the order we need to compare the reftable record keys with\neach other. This comparison is done by formatting them into a `struct\nstrbuf` and then doing `strbuf_strcmp()` on the result. We then discard\nthe buffers immediately after the comparison.\n\nThis ends up being very expensive. Because the priority queue usually\ncontains as many records as we have tables, we call the comparison\nfunction `O(log($tablecount))` many times for every record we insert.\nFurthermore, when iterating over many refs, we will insert at least one\nrecord for every ref we are iterating over. So ultimately, this ends up\nbeing called `O($refcount * log($tablecount))` many times.\n\nRefactor the code to use the new `refatble_record_cmp()` function that\nhas been implemented in a preceding commit. This function does not need\nto allocate memory and is thus significantly more efficient.\n\nThe following benchmark prints a single ref matching a specific pattern\nout of 1 million refs via git-show-ref(1), where the reftable stack\nconsists of three tables:\n\n  Benchmark 1: show-ref: single matching ref (revision = HEAD~)\n    Time (mean ± σ):     224.4 ms ±   6.5 ms    [User: 220.6 ms, System: 3.6 ms]\n    Range (min … max):   216.5 ms … 261.1 ms    1000 runs\n\n  Benchmark 2: show-ref: single matching ref (revision = HEAD)\n    Time (mean ± σ):     172.9 ms ±   4.4 ms    [User: 169.2 ms, System: 3.6 ms]\n    Range (min … max):   166.5 ms … 204.6 ms    1000 runs\n\n  Summary\n    show-ref: single matching ref (revision = HEAD) ran\n      1.30 ± 0.05 times faster than show-ref: single matching ref (revision = HEAD~)\n\nSigned-off-by: Patrick Steinhardt <ps@pks.im>\n---\n reftable/pq.c | 13 +------------\n 1 file changed, 1 insertion(+), 12 deletions(-)\n\ndiff --git a/reftable/pq.c b/reftable/pq.c\nindex dcefeb793a..7220efc39a 100644\n--- a/reftable/pq.c\n+++ b/reftable/pq.c\n@@ -14,20 +14,9 @@ license that can be found in the LICENSE file or at\n \n int pq_less(struct pq_entry *a, struct pq_entry *b)\n {\n-\tstruct strbuf ak = STRBUF_INIT;\n-\tstruct strbuf bk = STRBUF_INIT;\n-\tint cmp = 0;\n-\treftable_record_key(&a->rec, &ak);\n-\treftable_record_key(&b->rec, &bk);\n-\n-\tcmp = strbuf_cmp(&ak, &bk);\n-\n-\tstrbuf_release(&ak);\n-\tstrbuf_release(&bk);\n-\n+\tint cmp = reftable_record_cmp(&a->rec, &b->rec);\n \tif (cmp == 0)\n \t\treturn a->index > b->index;\n-\n \treturn cmp < 0;\n }\n \n-- \n2.43.GIT\n\n"},{"id":"488437","messageId":"2317aa43b95fc5f418504e9cf24b01048c3dbf8f.1707726654.git.ps@pks.im","threadId":"60827","inReplyTo":"cover.1707726654.git.ps@pks.im","subject":"[PATCH v2 5/7] reftable/block: swap buffers instead of copying","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-02-12T08:32:48Z","receivedAt":"2024-02-12T08:32:52Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"When iterating towards the next record in a reftable block we need to\nkeep track of the key that the last record had. This is required because\nreftable records use prefix compression, where subsequent records may\nreuse parts of their preceding record's key.\n\nThis key is stored in the `block_iter::last_key`, which we update after\nevery call to `block_iter_next()`: we simply reset the buffer and then\nadd the current key to it.\n\nThis is a bit inefficient though because it requires us to copy over the\nkey on every iteration, which adds up when iterating over many records.\nInstead, we can make use of the fact that the `block_iter::key` buffer\nis basically only a scratch buffer. So instead of copying over contents,\nwe can just swap both buffers.\n\nThe following benchmark prints a single ref matching a specific pattern\nout of 1 million refs via git-show-ref(1):\n\n  Benchmark 1: show-ref: single matching ref (revision = HEAD~)\n    Time (mean ± σ):     155.7 ms ±   5.0 ms    [User: 152.1 ms, System: 3.4 ms]\n    Range (min … max):   150.8 ms … 185.7 ms    1000 runs\n\n  Benchmark 2: show-ref: single matching ref (revision = HEAD)\n    Time (mean ± σ):     150.8 ms ±   4.2 ms    [User: 147.1 ms, System: 3.5 ms]\n    Range (min … max):   145.1 ms … 180.7 ms    1000 runs\n\n  Summary\n    show-ref: single matching ref (revision = HEAD) ran\n      1.03 ± 0.04 times faster than show-ref: single matching ref (revision = HEAD~)\n\nSigned-off-by: Patrick Steinhardt <ps@pks.im>\n---\n reftable/block.c | 3 +--\n 1 file changed, 1 insertion(+), 2 deletions(-)\n\ndiff --git a/reftable/block.c b/reftable/block.c\nindex 1df3d8a0f0..44381ea6a3 100644\n--- a/reftable/block.c\n+++ b/reftable/block.c\n@@ -342,8 +342,7 @@ int block_iter_next(struct block_iter *it, struct reftable_record *rec)\n \t\treturn -1;\n \tstring_view_consume(&in, n);\n \n-\tstrbuf_reset(&it->last_key);\n-\tstrbuf_addbuf(&it->last_key, &it->key);\n+\tstrbuf_swap(&it->last_key, &it->key);\n \tit->next_off += start.len - in.len;\n \treturn 0;\n }\n-- \n2.43.GIT\n\n"},{"id":"488438","messageId":"8c674915044c47c46c8e4efcb4d914fdd26e5c55.1707726654.git.ps@pks.im","threadId":"60827","inReplyTo":"cover.1707726654.git.ps@pks.im","subject":"[PATCH v2 6/7] reftable/record: don't try to reallocate ref record name","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-02-12T08:32:53Z","receivedAt":"2024-02-12T08:32:56Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"When decoding reftable ref records we first release the pointer to the\nrecord passed to us and then use realloc(3P) to allocate the refname\narray. This is a bit misleading though as we know at that point that the\nrefname will always be `NULL`, so we would always end up allocating a\nnew char array anyway.\n\nRefactor the code to use `REFTABLE_ALLOC_ARRAY()` instead. As the\nfollowing benchmark demonstrates this is a tiny bit more efficient. But\nthe bigger selling point really is the gained clarity.\n\n  Benchmark 1: show-ref: single matching ref (revision = HEAD~)\n    Time (mean ± σ):     150.1 ms ±   4.1 ms    [User: 146.6 ms, System: 3.3 ms]\n    Range (min … max):   144.5 ms … 180.5 ms    1000 runs\n\n  Benchmark 2: show-ref: single matching ref (revision = HEAD)\n    Time (mean ± σ):     148.9 ms ±   4.5 ms    [User: 145.2 ms, System: 3.4 ms]\n    Range (min … max):   143.0 ms … 185.4 ms    1000 runs\n\n  Summary\n    show-ref: single matching ref (revision = HEAD) ran\n      1.01 ± 0.04 times faster than show-ref: single matching ref (revision = HEAD~)\n\nIdeally, we should try and reuse the memory of the old record instead of\nfirst freeing and then immediately reallocating it. This requires some\nmore surgery though and is thus left for a future iteration.\n\nSigned-off-by: Patrick Steinhardt <ps@pks.im>\n---\n reftable/record.c | 5 +++--\n 1 file changed, 3 insertions(+), 2 deletions(-)\n\ndiff --git a/reftable/record.c b/reftable/record.c\nindex f1b6a5eac9..6465a7b8f4 100644\n--- a/reftable/record.c\n+++ b/reftable/record.c\n@@ -377,10 +377,11 @@ static int reftable_ref_record_decode(void *rec, struct strbuf key,\n \n \tassert(hash_size > 0);\n \n-\tr->refname = reftable_realloc(r->refname, key.len + 1);\n+\tr->refname = reftable_malloc(key.len + 1);\n \tmemcpy(r->refname, key.buf, key.len);\n-\tr->update_index = update_index;\n \tr->refname[key.len] = 0;\n+\n+\tr->update_index = update_index;\n \tr->value_type = val_type;\n \tswitch (val_type) {\n \tcase REFTABLE_REF_VAL1:\n-- \n2.43.GIT\n\n"},{"id":"488439","messageId":"167f67fad841ad06535a5532088fa6c9125fb1cd.1707726654.git.ps@pks.im","threadId":"60827","inReplyTo":"cover.1707726654.git.ps@pks.im","subject":"[PATCH v2 7/7] reftable/reader: add comments to `table_iter_next()`","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-02-12T08:32:57Z","receivedAt":"2024-02-12T08:33:00Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"While working on the optimizations in the preceding patches I stumbled\nupon `table_iter_next()` multiple times. It is quite easy to miss the\nfact that we don't call `table_iter_next_in_block()` twice, but that the\nsecond call is in fact `table_iter_next_block()`.\n\nAdd comments to explain what exactly is going on here to make things\nmore obvious. While at it, touch up the code to conform to our code\nstyle better.\n\nNote that one of the refactorings merges two conditional blocks into\none. Before, we had the following code:\n\n```\nerr = table_iter_next_block(&next, ti\nif (err != 0) {\n\tti->is_finished = 1;\n}\ntable_iter_block_done(ti);\nif (err != 0) {\n\treturn err;\n}\n```\n\nAs `table_iter_block_done()` does not care about `is_finished`, the\nconditional blocks can be merged into one block:\n\n```\nerr = table_iter_next_block(&next, ti\ntable_iter_block_done(ti);\nif (err != 0) {\n\tti->is_finished = 1;\n\treturn err;\n}\n```\n\nThis is both easier to reason about and more performant because we have\none branch less.\n\nSigned-off-by: Patrick Steinhardt <ps@pks.im>\n---\n reftable/reader.c | 26 +++++++++++++++++---------\n 1 file changed, 17 insertions(+), 9 deletions(-)\n\ndiff --git a/reftable/reader.c b/reftable/reader.c\nindex 64dc366fb1..add7d57f0b 100644\n--- a/reftable/reader.c\n+++ b/reftable/reader.c\n@@ -357,24 +357,32 @@ static int table_iter_next(struct table_iter *ti, struct reftable_record *rec)\n \n \twhile (1) {\n \t\tstruct table_iter next = TABLE_ITER_INIT;\n-\t\tint err = 0;\n-\t\tif (ti->is_finished) {\n+\t\tint err;\n+\n+\t\tif (ti->is_finished)\n \t\t\treturn 1;\n-\t\t}\n \n+\t\t/*\n+\t\t * Check whether the current block still has more records. If\n+\t\t * so, return it. If the iterator returns positive then the\n+\t\t * current block has been exhausted.\n+\t\t */\n \t\terr = table_iter_next_in_block(ti, rec);\n-\t\tif (err <= 0) {\n+\t\tif (err <= 0)\n \t\t\treturn err;\n-\t\t}\n \n+\t\t/*\n+\t\t * Otherwise, we need to continue to the next block in the\n+\t\t * table and retry. If there are no more blocks then the\n+\t\t * iterator is drained.\n+\t\t */\n \t\terr = table_iter_next_block(&next, ti);\n-\t\tif (err != 0) {\n-\t\t\tti->is_finished = 1;\n-\t\t}\n \t\ttable_iter_block_done(ti);\n-\t\tif (err != 0) {\n+\t\tif (err) {\n+\t\t\tti->is_finished = 1;\n \t\t\treturn err;\n \t\t}\n+\n \t\ttable_iter_copy_from(ti, &next);\n \t\tblock_iter_close(&next.bi);\n \t}\n-- \n2.43.GIT\n\n"},{"id":"488458","messageId":"xmqq4jed7g87.fsf@gitster.g","threadId":"60827","inReplyTo":"167f67fad841ad06535a5532088fa6c9125fb1cd.1707726654.git.ps@pks.im","subject":"Re: [PATCH v2 7/7] reftable/reader: add comments to `table_iter_next()`","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2024-02-12T17:19:20Z","receivedAt":"2024-02-12T17:19:25Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Patrick Steinhardt <ps@pks.im> writes:\n\n> While working on the optimizations in the preceding patches I stumbled\n> upon `table_iter_next()` multiple times. It is quite easy to miss the\n> fact that we don't call `table_iter_next_in_block()` twice, but that the\n> second call is in fact `table_iter_next_block()`.\n>\n> Add comments to explain what exactly is going on here to make things\n> more obvious. While at it, touch up the code to conform to our code\n> style better.\n>\n> Note that one of the refactorings merges two conditional blocks into\n> one. Before, we had the following code:\n>\n> ```\n> err = table_iter_next_block(&next, ti\n\n\");\"???\n\n> if (err != 0) {\n> \tti->is_finished = 1;\n> }\n> table_iter_block_done(ti);\n> if (err != 0) {\n> \treturn err;\n> }\n> ```\n>\n> As `table_iter_block_done()` does not care about `is_finished`, the\n> conditional blocks can be merged into one block:\n>\n> ```\n> err = table_iter_next_block(&next, ti\n> table_iter_block_done(ti);\n> if (err != 0) {\n> \tti->is_finished = 1;\n> \treturn err;\n> }\n> ```\n>\n> This is both easier to reason about and more performant because we have\n> one branch less.\n>\n> Signed-off-by: Patrick Steinhardt <ps@pks.im>\n> ---\n>  reftable/reader.c | 26 +++++++++++++++++---------\n>  1 file changed, 17 insertions(+), 9 deletions(-)\n>\n> diff --git a/reftable/reader.c b/reftable/reader.c\n> index 64dc366fb1..add7d57f0b 100644\n> --- a/reftable/reader.c\n> +++ b/reftable/reader.c\n> @@ -357,24 +357,32 @@ static int table_iter_next(struct table_iter *ti, struct reftable_record *rec)\n>  \n>  \twhile (1) {\n>  \t\tstruct table_iter next = TABLE_ITER_INIT;\n> -\t\tint err = 0;\n> -\t\tif (ti->is_finished) {\n> +\t\tint err;\n> +\n> +\t\tif (ti->is_finished)\n>  \t\t\treturn 1;\n> -\t\t}\n>  \n> +\t\t/*\n> +\t\t * Check whether the current block still has more records. If\n> +\t\t * so, return it. If the iterator returns positive then the\n> +\t\t * current block has been exhausted.\n> +\t\t */\n>  \t\terr = table_iter_next_in_block(ti, rec);\n> -\t\tif (err <= 0) {\n> +\t\tif (err <= 0)\n>  \t\t\treturn err;\n> -\t\t}\n>  \n> +\t\t/*\n> +\t\t * Otherwise, we need to continue to the next block in the\n> +\t\t * table and retry. If there are no more blocks then the\n> +\t\t * iterator is drained.\n> +\t\t */\n>  \t\terr = table_iter_next_block(&next, ti);\n> -\t\tif (err != 0) {\n> -\t\t\tti->is_finished = 1;\n> -\t\t}\n>  \t\ttable_iter_block_done(ti);\n> -\t\tif (err != 0) {\n> +\t\tif (err) {\n> +\t\t\tti->is_finished = 1;\n>  \t\t\treturn err;\n>  \t\t}\n> +\n>  \t\ttable_iter_copy_from(ti, &next);\n>  \t\tblock_iter_close(&next.bi);\n>  \t}\n"},{"id":"488503","messageId":"ZcsSz3rJIsK_HFzj@tanuki","threadId":"60827","inReplyTo":"xmqq4jed7g87.fsf@gitster.g","subject":"Re: [PATCH v2 7/7] reftable/reader: add comments to `table_iter_next()`","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-02-13T06:57:19Z","receivedAt":"2024-02-13T06:57:27Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"On Mon, Feb 12, 2024 at 09:19:20AM -0800, Junio C Hamano wrote:\n> Patrick Steinhardt <ps@pks.im> writes:\n> \n> > While working on the optimizations in the preceding patches I stumbled\n> > upon `table_iter_next()` multiple times. It is quite easy to miss the\n> > fact that we don't call `table_iter_next_in_block()` twice, but that the\n> > second call is in fact `table_iter_next_block()`.\n> >\n> > Add comments to explain what exactly is going on here to make things\n> > more obvious. While at it, touch up the code to conform to our code\n> > style better.\n> >\n> > Note that one of the refactorings merges two conditional blocks into\n> > one. Before, we had the following code:\n> >\n> > ```\n> > err = table_iter_next_block(&next, ti\n> \n> \");\"???\n\nOh, right, seems to be a copy-paste error. I see you already fixed it in\nps/reftable-iteration-perf and merged the branch to next. Thanks!\n\nPatrick\n"}]}