{"thread":{"id":"60913","subject":"[PATCH 00/12] reftable: improve ref iteration performance (pt.2)","startedAt":"2024-02-14T07:45:43Z","lastAt":"2024-03-04T10:49:43Z","messageCount":51,"participants":["Patrick Steinhardt","Justin Tobler","James Liu"],"isPatch":true,"patchVersion":1,"patchTotal":12},"messages":[{"id":"488615","messageId":"cover.1707895758.git.ps@pks.im","threadId":"60913","inReplyTo":null,"subject":"[PATCH 00/12] reftable: improve ref iteration performance (pt.2)","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-02-14T07:45:37Z","receivedAt":"2024-02-14T07:45:43Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"Hi,\n\nthis is the second part of my patch series that aim to improve raw ref\niteration performance with the reftable backend. The target of this\nseries was to get the reftable backend performant enough to match the\nfiles backend. This was achieved via two angles:\n\n  - Refactorings of the merged iterators that allow us to skip copying\n    and allocating records from the sub-iterators to the caller. This is\n    implemented by the first 8 patches.\n\n  - Refactorings of how we decode reftable records so that we reuse\n    allocated memory. Like this the number of allocations don't scale\n    with the number of iterated records anymore, but instead with the\n    number of blocks which we're iterating over.\n\nCombined, these refactorings lead to a sizeable speedup when iterating\nover 1 million refs:\n\n```\nBenchmark 1: show-ref: single matching ref (revision = HEAD~)\n  Time (mean ± σ):     146.1 ms ±   4.2 ms    [User: 143.2 ms, System: 2.8 ms]\n  Range (min … max):   140.7 ms … 180.2 ms    1000 runs\n\nBenchmark 2: show-ref: single matching ref (revision = HEAD)\n  Time (mean ± σ):      97.6 ms ±   3.2 ms    [User: 94.8 ms, System: 2.7 ms]\n  Range (min … max):    94.6 ms … 122.1 ms    1000 runs\n\nSummary\n  show-ref: single matching ref (revision = HEAD) ran\n    1.50 ± 0.07 times faster than show-ref: single matching ref (revision = HEAD~)\n```\n\nWith this, the reftable backend is now on par with the files backend:\n\n```\nBenchmark 1: show-ref: single matching ref (refformat = files)\n  Time (mean ± σ):      97.8 ms ±   3.4 ms    [User: 87.6 ms, System: 10.0 ms]\n  Range (min … max):    95.0 ms … 121.3 ms    1000 runs\n\nBenchmark 2: show-ref: single matching ref (refformat = reftable)\n  Time (mean ± σ):      97.4 ms ±   3.2 ms    [User: 94.5 ms, System: 2.7 ms]\n  Range (min … max):    94.1 ms … 126.3 ms    1000 runs\n\nSummary\n  show-ref: single matching ref (refformat = reftable) ran\n    1.00 ± 0.05 times faster than show-ref: single matching ref (refformat = files)\n```\n\nThere are still optimization opportunities left, but given that the\noriginal target has been fulfilled I decided to stop so that the patch\nseries remains somewhat reasonably sized.\n\nThe patch series is based on `master` at 2996f11c1d (Sync with 'maint',\n2024-02-12) and depends on ps/reftable-iteration-perf at c68ca7abd3\n(reftable/reader: add comments to `table_iter_next()`, 2024-02-12).\n\nPatrick\n\nPatrick Steinhardt (12):\n  reftable/pq: use `size_t` to track iterator index\n  reftable/merged: make `merged_iter` structure private\n  reftable/merged: advance subiter on subsequent iteration\n  reftable/merged: make subiters own their records\n  reftable/merged: remove unnecessary null check for subiters\n  reftable/merged: handle subiter cleanup on close only\n  reftable/merged: circumvent pqueue with single subiter\n  reftable/merged: avoid duplicate pqueue emptiness check\n  reftable/record: reuse refname when decoding\n  reftable/record: reuse refname when copying\n  reftable/record: decode keys in place\n  reftable: allow inlining of a few functions\n\n reftable/block.c           |  25 +++----\n reftable/block.h           |   2 -\n reftable/iter.c            |   5 --\n reftable/iter.h            |   4 --\n reftable/merged.c          | 139 +++++++++++++++++++------------------\n reftable/merged.h          |   9 ---\n reftable/pq.c              |  18 +----\n reftable/pq.h              |  16 +++--\n reftable/pq_test.c         |  41 +++++------\n reftable/record.c          |  64 +++++++++--------\n reftable/record.h          |  21 ++++--\n reftable/record_test.c     |   3 +-\n reftable/reftable-record.h |   1 +\n 13 files changed, 170 insertions(+), 178 deletions(-)\n\n\nbase-commit: 2996f11c1d11ab68823f0939b6469dedc2b9ab90\n-- \n2.43.GIT\n\n"},{"id":"488616","messageId":"eeaaac9e07c830f1c1ccd9d238fe6f725374d16b.1707895758.git.ps@pks.im","threadId":"60913","inReplyTo":"cover.1707895758.git.ps@pks.im","subject":"[PATCH 01/12] reftable/pq: use `size_t` to track iterator index","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-02-14T07:45:41Z","receivedAt":"2024-02-14T07:45:45Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"The reftable priority queue is used by the merged iterator to yield\nrecords from its sub-iterators in the expected order. Each entry has a\nrecord corresponding to such a sub-iterator as well as an index that\nindicates which sub-iterator the record belongs to. But while the\nsub-iterators are tracked with a `size_t`, we store the index as an\n`int` in the entry.\n\nFix this and use `size_t` consistently.\n\nSigned-off-by: Patrick Steinhardt <ps@pks.im>\n---\n reftable/pq.h | 2 +-\n 1 file changed, 1 insertion(+), 1 deletion(-)\n\ndiff --git a/reftable/pq.h b/reftable/pq.h\nindex e85bac9b52..9e25a43a36 100644\n--- a/reftable/pq.h\n+++ b/reftable/pq.h\n@@ -12,7 +12,7 @@ license that can be found in the LICENSE file or at\n #include \"record.h\"\n \n struct pq_entry {\n-\tint index;\n+\tsize_t index;\n \tstruct reftable_record rec;\n };\n \n-- \n2.43.GIT\n\n"},{"id":"488617","messageId":"be807e7650e2b11e5d6f7dd84ca1c549408f678a.1707895758.git.ps@pks.im","threadId":"60913","inReplyTo":"cover.1707895758.git.ps@pks.im","subject":"[PATCH 02/12] reftable/merged: make `merged_iter` structure private","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-02-14T07:45:45Z","receivedAt":"2024-02-14T07:45:49Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"The `merged_iter` structure is not used anywhere outside of \"merged.c\",\nbut is declared in its header. Move it into the code file so that it is\nclear that its implementation details are never exposed to anything.\n\nSigned-off-by: Patrick Steinhardt <ps@pks.im>\n---\n reftable/merged.c | 9 +++++++++\n reftable/merged.h | 9 ---------\n 2 files changed, 9 insertions(+), 9 deletions(-)\n\ndiff --git a/reftable/merged.c b/reftable/merged.c\nindex 1aa6cd31b7..12ebd732e8 100644\n--- a/reftable/merged.c\n+++ b/reftable/merged.c\n@@ -17,6 +17,15 @@ license that can be found in the LICENSE file or at\n #include \"reftable-error.h\"\n #include \"system.h\"\n \n+struct merged_iter {\n+\tstruct reftable_iterator *stack;\n+\tuint32_t hash_id;\n+\tsize_t stack_len;\n+\tuint8_t typ;\n+\tint suppress_deletions;\n+\tstruct merged_iter_pqueue pq;\n+};\n+\n static int merged_iter_init(struct merged_iter *mi)\n {\n \tfor (size_t i = 0; i < mi->stack_len; i++) {\ndiff --git a/reftable/merged.h b/reftable/merged.h\nindex 7d9f95d27e..288ad66656 100644\n--- a/reftable/merged.h\n+++ b/reftable/merged.h\n@@ -24,15 +24,6 @@ struct reftable_merged_table {\n \tuint64_t max;\n };\n \n-struct merged_iter {\n-\tstruct reftable_iterator *stack;\n-\tuint32_t hash_id;\n-\tsize_t stack_len;\n-\tuint8_t typ;\n-\tint suppress_deletions;\n-\tstruct merged_iter_pqueue pq;\n-};\n-\n void merged_table_release(struct reftable_merged_table *mt);\n \n #endif\n-- \n2.43.GIT\n\n"},{"id":"488618","messageId":"38d45995662ba92f4b985b82deac298446274511.1707895758.git.ps@pks.im","threadId":"60913","inReplyTo":"cover.1707895758.git.ps@pks.im","subject":"[PATCH 03/12] reftable/merged: advance subiter on subsequent iteration","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-02-14T07:45:50Z","receivedAt":"2024-02-14T07:45:54Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"When advancing the merged iterator, we pop the top-most entry from its\npriority queue and then advance the sub-iterator that the entry belongs\nto, adding the result as a new entry. This is quite sensible in the case\nwhere the merged iterator is used to actual iterate through records. But\nthe merged iterator is also used when we look up a single record, only,\nso advancing the sub-iterator is wasted effort because we would never\neven look at the result.\n\nInstead of immediately advancing the sub-iterator, we can also defer\nthis to the next iteration of the merged iterator by storing the\nintent-to-advance. This results in a small speedup when reading many\nrecords. The following benchmark creates 10000 refs, which will also end\nup with many ref lookups:\n\n    Benchmark 1: update-ref: create many refs (revision = HEAD~)\n      Time (mean ± σ):     337.2 ms ±   7.3 ms    [User: 200.1 ms, System: 136.9 ms]\n      Range (min … max):   329.3 ms … 373.2 ms    100 runs\n\n    Benchmark 2: update-ref: create many refs (revision = HEAD)\n      Time (mean ± σ):     332.5 ms ±   5.9 ms    [User: 197.2 ms, System: 135.1 ms]\n      Range (min … max):   327.6 ms … 359.8 ms    100 runs\n\n    Summary\n      update-ref: create many refs (revision = HEAD) ran\n        1.01 ± 0.03 times faster than update-ref: create many refs (revision = HEAD~)\n\nWhile this speedup alone isn't really worth it, this refactoring will\nalso allow two additional optimizations in subsequent patches. First, it\nwill allow us to special-case when there is only a single sub-iter left\nto circumvent the priority queue altogether. And second, it makes it\neasier to avoid copying records to the caller.\n\nSigned-off-by: Patrick Steinhardt <ps@pks.im>\n---\n reftable/merged.c | 26 ++++++++++++--------------\n 1 file changed, 12 insertions(+), 14 deletions(-)\n\ndiff --git a/reftable/merged.c b/reftable/merged.c\nindex 12ebd732e8..9b1ccfff00 100644\n--- a/reftable/merged.c\n+++ b/reftable/merged.c\n@@ -19,11 +19,12 @@ license that can be found in the LICENSE file or at\n \n struct merged_iter {\n \tstruct reftable_iterator *stack;\n+\tstruct merged_iter_pqueue pq;\n \tuint32_t hash_id;\n \tsize_t stack_len;\n \tuint8_t typ;\n \tint suppress_deletions;\n-\tstruct merged_iter_pqueue pq;\n+\tssize_t advance_index;\n };\n \n static int merged_iter_init(struct merged_iter *mi)\n@@ -96,13 +97,17 @@ static int merged_iter_next_entry(struct merged_iter *mi,\n \tstruct pq_entry entry = { 0 };\n \tint err = 0;\n \n+\tif (mi->advance_index >= 0) {\n+\t\terr = merged_iter_advance_subiter(mi, mi->advance_index);\n+\t\tif (err < 0)\n+\t\t\treturn err;\n+\t\tmi->advance_index = -1;\n+\t}\n+\n \tif (merged_iter_pqueue_is_empty(mi->pq))\n \t\treturn 1;\n \n \tentry = merged_iter_pqueue_remove(&mi->pq);\n-\terr = merged_iter_advance_subiter(mi, entry.index);\n-\tif (err < 0)\n-\t\treturn err;\n \n \t/*\n \t  One can also use reftable as datacenter-local storage, where the ref\n@@ -116,14 +121,6 @@ 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@@ -137,6 +134,7 @@ static int merged_iter_next_entry(struct merged_iter *mi,\n \n \treftable_record_release(rec);\n \t*rec = entry.rec;\n+\tmi->advance_index = entry.index;\n \n done:\n \tif (err)\n@@ -160,9 +158,8 @@ static int merged_iter_next(struct merged_iter *mi, struct reftable_record *rec)\n static int merged_iter_next_void(void *p, struct reftable_record *rec)\n {\n \tstruct merged_iter *mi = p;\n-\tif (merged_iter_pqueue_is_empty(mi->pq))\n+\tif (merged_iter_pqueue_is_empty(mi->pq) && mi->advance_index < 0)\n \t\treturn 1;\n-\n \treturn merged_iter_next(mi, rec);\n }\n \n@@ -255,6 +252,7 @@ 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.advance_index = -1,\n \t};\n \tstruct merged_iter *p;\n \tint err;\n-- \n2.43.GIT\n\n"},{"id":"488619","messageId":"2c51c60d165f5bb4e998c8b5dbb33be72e54d8a8.1707895758.git.ps@pks.im","threadId":"60913","inReplyTo":"cover.1707895758.git.ps@pks.im","subject":"[PATCH 04/12] reftable/merged: make subiters own their records","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-02-14T07:45:54Z","receivedAt":"2024-02-14T07:45:57Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"For each subiterator, the merged table needs to track their current\nrecord. This record is owned by the priority queue though instead of by\nthe merged iterator. This is not optimal performance-wise.\n\nFor one, we need to move around records whenever we add or remove a\nrecord from the priority queue. Thus, the bigger the entries the more\nbytes we need to copy around. And compared to pointers, a reftable\nrecord is rather on the bigger side. The other issue is that this makes\nit harder to reuse the records.\n\nRefactor the code so that the merged iterator tracks ownership of the\nrecords per-subiter. Instead of having records in the priority queue, we\ncan now use mere pointers to the per-subiter records. This also allows\nus to swap records between the caller and the per-subiter record instead\nof doing an actual copy via `reftable_record_copy_from()`, which removes\nthe need to release the caller-provided record.\n\nThis results in a noticeable speedup when iterating through many refs.\nThe following benchmark iterates through 1 million refs:\n\n  Benchmark 1: show-ref: single matching ref (revision = HEAD~)\n    Time (mean ± σ):     145.5 ms ±   4.5 ms    [User: 142.5 ms, System: 2.8 ms]\n    Range (min … max):   141.3 ms … 177.0 ms    1000 runs\n\n  Benchmark 2: show-ref: single matching ref (revision = HEAD)\n    Time (mean ± σ):     139.0 ms ±   4.7 ms    [User: 136.1 ms, System: 2.8 ms]\n    Range (min … max):   134.2 ms … 182.2 ms    1000 runs\n\n  Summary\n    show-ref: single matching ref (revision = HEAD) ran\n      1.05 ± 0.05 times faster than show-ref: single matching ref (revision = HEAD~)\n\nThis refactoring also allows a subsequent refactoring where we start\nreusing memory allocated by the reftable records because we do not need\nto release the caller-provided record anymore.\n\nSigned-off-by: Patrick Steinhardt <ps@pks.im>\n---\n reftable/merged.c  | 54 ++++++++++++++++++++++++----------------------\n reftable/pq.c      |  8 ++-----\n reftable/pq.h      |  2 +-\n reftable/pq_test.c | 41 ++++++++++++++++-------------------\n 4 files changed, 49 insertions(+), 56 deletions(-)\n\ndiff --git a/reftable/merged.c b/reftable/merged.c\nindex 9b1ccfff00..ae74234472 100644\n--- a/reftable/merged.c\n+++ b/reftable/merged.c\n@@ -17,8 +17,13 @@ license that can be found in the LICENSE file or at\n #include \"reftable-error.h\"\n #include \"system.h\"\n \n+struct merged_subiter {\n+\tstruct reftable_iterator iter;\n+\tstruct reftable_record rec;\n+};\n+\n struct merged_iter {\n-\tstruct reftable_iterator *stack;\n+\tstruct merged_subiter *subiters;\n \tstruct merged_iter_pqueue pq;\n \tuint32_t hash_id;\n \tsize_t stack_len;\n@@ -32,16 +37,18 @@ static int merged_iter_init(struct merged_iter *mi)\n \tfor (size_t i = 0; i < mi->stack_len; i++) {\n \t\tstruct pq_entry e = {\n \t\t\t.index = i,\n+\t\t\t.rec = &mi->subiters[i].rec,\n \t\t};\n \t\tint err;\n \n-\t\treftable_record_init(&e.rec, mi->typ);\n-\t\terr = iterator_next(&mi->stack[i], &e.rec);\n+\t\treftable_record_init(&mi->subiters[i].rec, mi->typ);\n+\t\terr = iterator_next(&mi->subiters[i].iter,\n+\t\t\t\t    &mi->subiters[i].rec);\n \t\tif (err < 0)\n \t\t\treturn err;\n \t\tif (err > 0) {\n-\t\t\treftable_iterator_destroy(&mi->stack[i]);\n-\t\t\treftable_record_release(&e.rec);\n+\t\t\treftable_iterator_destroy(&mi->subiters[i].iter);\n+\t\t\treftable_record_release(&mi->subiters[i].rec);\n \t\t\tcontinue;\n \t\t}\n \n@@ -56,9 +63,11 @@ static void merged_iter_close(void *p)\n \tstruct merged_iter *mi = p;\n \n \tmerged_iter_pqueue_release(&mi->pq);\n-\tfor (size_t i = 0; i < mi->stack_len; i++)\n-\t\treftable_iterator_destroy(&mi->stack[i]);\n-\treftable_free(mi->stack);\n+\tfor (size_t i = 0; i < mi->stack_len; i++) {\n+\t\treftable_iterator_destroy(&mi->subiters[i].iter);\n+\t\treftable_record_release(&mi->subiters[i].rec);\n+\t}\n+\treftable_free(mi->subiters);\n }\n \n static int merged_iter_advance_nonnull_subiter(struct merged_iter *mi,\n@@ -66,17 +75,16 @@ static int merged_iter_advance_nonnull_subiter(struct merged_iter *mi,\n {\n \tstruct pq_entry e = {\n \t\t.index = idx,\n+\t\t.rec = &mi->subiters[idx].rec,\n \t};\n \tint err;\n \n-\treftable_record_init(&e.rec, mi->typ);\n-\terr = iterator_next(&mi->stack[idx], &e.rec);\n+\terr = iterator_next(&mi->subiters[idx].iter, &mi->subiters[idx].rec);\n \tif (err < 0)\n \t\treturn err;\n-\n \tif (err > 0) {\n-\t\treftable_iterator_destroy(&mi->stack[idx]);\n-\t\treftable_record_release(&e.rec);\n+\t\treftable_iterator_destroy(&mi->subiters[idx].iter);\n+\t\treftable_record_release(&mi->subiters[idx].rec);\n \t\treturn 0;\n \t}\n \n@@ -86,7 +94,7 @@ static int merged_iter_advance_nonnull_subiter(struct merged_iter *mi,\n \n static int merged_iter_advance_subiter(struct merged_iter *mi, size_t idx)\n {\n-\tif (iterator_is_null(&mi->stack[idx]))\n+\tif (iterator_is_null(&mi->subiters[idx].iter))\n \t\treturn 0;\n \treturn merged_iter_advance_nonnull_subiter(mi, idx);\n }\n@@ -121,25 +129,19 @@ 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\tcmp = reftable_record_cmp(&top.rec, &entry.rec);\n+\t\tcmp = reftable_record_cmp(top.rec, entry.rec);\n \t\tif (cmp > 0)\n \t\t\tbreak;\n \n \t\tmerged_iter_pqueue_remove(&mi->pq);\n \t\terr = merged_iter_advance_subiter(mi, top.index);\n \t\tif (err < 0)\n-\t\t\tgoto done;\n-\t\treftable_record_release(&top.rec);\n+\t\t\treturn err;\n \t}\n \n-\treftable_record_release(rec);\n-\t*rec = entry.rec;\n \tmi->advance_index = entry.index;\n-\n-done:\n-\tif (err)\n-\t\treftable_record_release(&entry.rec);\n-\treturn err;\n+\tSWAP(*rec, *entry.rec);\n+\treturn 0;\n }\n \n static int merged_iter_next(struct merged_iter *mi, struct reftable_record *rec)\n@@ -257,10 +259,10 @@ static int merged_table_seek_record(struct reftable_merged_table *mt,\n \tstruct merged_iter *p;\n \tint err;\n \n-\tREFTABLE_CALLOC_ARRAY(merged.stack, mt->stack_len);\n+\tREFTABLE_CALLOC_ARRAY(merged.subiters, mt->stack_len);\n \tfor (size_t i = 0; i < mt->stack_len; i++) {\n \t\terr = reftable_table_seek_record(&mt->stack[i],\n-\t\t\t\t\t\t &merged.stack[merged.stack_len], rec);\n+\t\t\t\t\t\t &merged.subiters[merged.stack_len].iter, rec);\n \t\tif (err < 0)\n \t\t\tgoto out;\n \t\tif (!err)\ndiff --git a/reftable/pq.c b/reftable/pq.c\nindex e0ccce2b97..0074d6bc43 100644\n--- a/reftable/pq.c\n+++ b/reftable/pq.c\n@@ -14,7 +14,7 @@ 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-\tint cmp = reftable_record_cmp(&a->rec, &b->rec);\n+\tint cmp = reftable_record_cmp(a->rec, b->rec);\n \tif (cmp == 0)\n \t\treturn a->index > b->index;\n \treturn cmp < 0;\n@@ -82,10 +82,6 @@ void merged_iter_pqueue_add(struct merged_iter_pqueue *pq, const struct pq_entry\n \n void merged_iter_pqueue_release(struct merged_iter_pqueue *pq)\n {\n-\tint i = 0;\n-\tfor (i = 0; i < pq->len; i++) {\n-\t\treftable_record_release(&pq->heap[i].rec);\n-\t}\n \tFREE_AND_NULL(pq->heap);\n-\tpq->len = pq->cap = 0;\n+\tmemset(pq, 0, sizeof(*pq));\n }\ndiff --git a/reftable/pq.h b/reftable/pq.h\nindex 9e25a43a36..ce23972c16 100644\n--- a/reftable/pq.h\n+++ b/reftable/pq.h\n@@ -13,7 +13,7 @@ license that can be found in the LICENSE file or at\n \n struct pq_entry {\n \tsize_t index;\n-\tstruct reftable_record rec;\n+\tstruct reftable_record *rec;\n };\n \n struct merged_iter_pqueue {\ndiff --git a/reftable/pq_test.c b/reftable/pq_test.c\nindex c202eff848..b7d3c80cc7 100644\n--- a/reftable/pq_test.c\n+++ b/reftable/pq_test.c\n@@ -27,48 +27,43 @@ void merged_iter_pqueue_check(struct merged_iter_pqueue pq)\n \n static void test_pq(void)\n {\n-\tchar *names[54] = { NULL };\n-\tint N = ARRAY_SIZE(names) - 1;\n-\n \tstruct merged_iter_pqueue pq = { NULL };\n+\tstruct reftable_record recs[54];\n+\tint N = ARRAY_SIZE(recs) - 1, i;\n \tchar *last = NULL;\n \n-\tint i = 0;\n \tfor (i = 0; i < N; i++) {\n-\t\tchar name[100];\n-\t\tsnprintf(name, sizeof(name), \"%02d\", i);\n-\t\tnames[i] = xstrdup(name);\n+\t\tstruct strbuf refname = STRBUF_INIT;\n+\t\tstrbuf_addf(&refname, \"%02d\", i);\n+\n+\t\treftable_record_init(&recs[i], BLOCK_TYPE_REF);\n+\t\trecs[i].u.ref.refname = strbuf_detach(&refname, NULL);\n \t}\n \n \ti = 1;\n \tdo {\n-\t\tstruct pq_entry e = { .rec = { .type = BLOCK_TYPE_REF,\n-\t\t\t\t\t       .u.ref = {\n-\t\t\t\t\t\t       .refname = names[i],\n-\t\t\t\t\t       } } };\n+\t\tstruct pq_entry e = {\n+\t\t\t.rec = &recs[i],\n+\t\t};\n+\n \t\tmerged_iter_pqueue_add(&pq, &e);\n \t\tmerged_iter_pqueue_check(pq);\n+\n \t\ti = (i * 7) % N;\n \t} while (i != 1);\n \n \twhile (!merged_iter_pqueue_is_empty(pq)) {\n \t\tstruct pq_entry e = merged_iter_pqueue_remove(&pq);\n-\t\tstruct reftable_record *rec = &e.rec;\n \t\tmerged_iter_pqueue_check(pq);\n \n-\t\tEXPECT(reftable_record_type(rec) == BLOCK_TYPE_REF);\n-\t\tif (last) {\n-\t\t\tEXPECT(strcmp(last, rec->u.ref.refname) < 0);\n-\t\t}\n-\t\t/* this is names[i], so don't dealloc. */\n-\t\tlast = rec->u.ref.refname;\n-\t\trec->u.ref.refname = NULL;\n-\t\treftable_record_release(rec);\n-\t}\n-\tfor (i = 0; i < N; i++) {\n-\t\treftable_free(names[i]);\n+\t\tEXPECT(reftable_record_type(e.rec) == BLOCK_TYPE_REF);\n+\t\tif (last)\n+\t\t\tEXPECT(strcmp(last, e.rec->u.ref.refname) < 0);\n+\t\tlast = e.rec->u.ref.refname;\n \t}\n \n+\tfor (i = 0; i < N; i++)\n+\t\treftable_record_release(&recs[i]);\n \tmerged_iter_pqueue_release(&pq);\n }\n \n-- \n2.43.GIT\n\n"},{"id":"488620","messageId":"f1156dbf51c50ba2f63aff09e71f996d937c82a1.1707895758.git.ps@pks.im","threadId":"60913","inReplyTo":"cover.1707895758.git.ps@pks.im","subject":"[PATCH 05/12] reftable/merged: remove unnecessary null check for subiters","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-02-14T07:45:59Z","receivedAt":"2024-02-14T07:46:02Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"Whenever we advance a subiter we first call `iterator_is_null()`. This\nis not needed though because we only ever advance subiters which have\nentries in the priority queue, and we do not end entries to the priority\nqueue when the subiter has been exhausted.\n\nDrop the check as well as the now-unused function. This results in a\nsurprisingly big speedup:\n\n    Benchmark 1: show-ref: single matching ref (revision = HEAD~)\n      Time (mean ± σ):     138.1 ms ±   4.4 ms    [User: 135.1 ms, System: 2.8 ms]\n      Range (min … max):   133.4 ms … 167.3 ms    1000 runs\n\n    Benchmark 2: show-ref: single matching ref (revision = HEAD)\n      Time (mean ± σ):     134.4 ms ±   4.2 ms    [User: 131.5 ms, System: 2.8 ms]\n      Range (min … max):   130.0 ms … 164.0 ms    1000 runs\n\n    Summary\n      show-ref: single matching ref (revision = HEAD) ran\n        1.03 ± 0.05 times faster than show-ref: single matching ref (revision = HEAD~)\n\nSigned-off-by: Patrick Steinhardt <ps@pks.im>\n---\n reftable/iter.c   |  5 -----\n reftable/iter.h   |  4 ----\n reftable/merged.c | 10 +---------\n 3 files changed, 1 insertion(+), 18 deletions(-)\n\ndiff --git a/reftable/iter.c b/reftable/iter.c\nindex 8b5ebf6183..7aa30c4a51 100644\n--- a/reftable/iter.c\n+++ b/reftable/iter.c\n@@ -16,11 +16,6 @@ license that can be found in the LICENSE file or at\n #include \"reader.h\"\n #include \"reftable-error.h\"\n \n-int iterator_is_null(struct reftable_iterator *it)\n-{\n-\treturn !it->ops;\n-}\n-\n static void filtering_ref_iterator_close(void *iter_arg)\n {\n \tstruct filtering_ref_iterator *fri = iter_arg;\ndiff --git a/reftable/iter.h b/reftable/iter.h\nindex 47d67d84df..537431baba 100644\n--- a/reftable/iter.h\n+++ b/reftable/iter.h\n@@ -16,10 +16,6 @@ license that can be found in the LICENSE file or at\n #include \"reftable-iterator.h\"\n #include \"reftable-generic.h\"\n \n-/* Returns true for a zeroed out iterator, such as the one returned from\n- * iterator_destroy. */\n-int iterator_is_null(struct reftable_iterator *it);\n-\n /* iterator that produces only ref records that point to `oid` */\n struct filtering_ref_iterator {\n \tint double_check;\ndiff --git a/reftable/merged.c b/reftable/merged.c\nindex ae74234472..29ad09f3d8 100644\n--- a/reftable/merged.c\n+++ b/reftable/merged.c\n@@ -70,8 +70,7 @@ static void merged_iter_close(void *p)\n \treftable_free(mi->subiters);\n }\n \n-static int merged_iter_advance_nonnull_subiter(struct merged_iter *mi,\n-\t\t\t\t\t       size_t idx)\n+static int merged_iter_advance_subiter(struct merged_iter *mi, size_t idx)\n {\n \tstruct pq_entry e = {\n \t\t.index = idx,\n@@ -92,13 +91,6 @@ static int merged_iter_advance_nonnull_subiter(struct merged_iter *mi,\n \treturn 0;\n }\n \n-static int merged_iter_advance_subiter(struct merged_iter *mi, size_t idx)\n-{\n-\tif (iterator_is_null(&mi->subiters[idx].iter))\n-\t\treturn 0;\n-\treturn merged_iter_advance_nonnull_subiter(mi, idx);\n-}\n-\n static int merged_iter_next_entry(struct merged_iter *mi,\n \t\t\t\t  struct reftable_record *rec)\n {\n-- \n2.43.GIT\n\n"},{"id":"488621","messageId":"4e50ac655064481691b71f70a9265185976ccbeb.1707895758.git.ps@pks.im","threadId":"60913","inReplyTo":"cover.1707895758.git.ps@pks.im","subject":"[PATCH 06/12] reftable/merged: handle subiter cleanup on close only","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-02-14T07:46:03Z","receivedAt":"2024-02-14T07:46:07Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"When advancing one of the subiters fails we immediately release\nresources associated with that subiter. This is not necessary though as\nwe will release these resources when closing the merged iterator anyway.\n\nDrop the logic and only release resources when the merged iterator is\ndone. This is a mere cleanup that should help reduce the cognitive load\nwhen reading through the code.\n\nSigned-off-by: Patrick Steinhardt <ps@pks.im>\n---\n reftable/merged.c | 12 ++----------\n 1 file changed, 2 insertions(+), 10 deletions(-)\n\ndiff --git a/reftable/merged.c b/reftable/merged.c\nindex 29ad09f3d8..d9ed4a19dd 100644\n--- a/reftable/merged.c\n+++ b/reftable/merged.c\n@@ -46,11 +46,8 @@ static int merged_iter_init(struct merged_iter *mi)\n \t\t\t\t    &mi->subiters[i].rec);\n \t\tif (err < 0)\n \t\t\treturn err;\n-\t\tif (err > 0) {\n-\t\t\treftable_iterator_destroy(&mi->subiters[i].iter);\n-\t\t\treftable_record_release(&mi->subiters[i].rec);\n+\t\tif (err > 0)\n \t\t\tcontinue;\n-\t\t}\n \n \t\tmerged_iter_pqueue_add(&mi->pq, &e);\n \t}\n@@ -79,13 +76,8 @@ static int merged_iter_advance_subiter(struct merged_iter *mi, size_t idx)\n \tint err;\n \n \terr = iterator_next(&mi->subiters[idx].iter, &mi->subiters[idx].rec);\n-\tif (err < 0)\n+\tif (err)\n \t\treturn err;\n-\tif (err > 0) {\n-\t\treftable_iterator_destroy(&mi->subiters[idx].iter);\n-\t\treftable_record_release(&mi->subiters[idx].rec);\n-\t\treturn 0;\n-\t}\n \n \tmerged_iter_pqueue_add(&mi->pq, &e);\n \treturn 0;\n-- \n2.43.GIT\n\n"},{"id":"488622","messageId":"cd65d849a4372636a9827de64b6b35237fd4801b.1707895758.git.ps@pks.im","threadId":"60913","inReplyTo":"cover.1707895758.git.ps@pks.im","subject":"[PATCH 07/12] reftable/merged: circumvent pqueue with single subiter","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-02-14T07:46:08Z","receivedAt":"2024-02-14T07:46:11Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"The merged iterator uses a priority queue to order records so that we\ncan yielid them in the expected order. This priority queue of course\ncomes with some overhead as we need to add, compare and remove entries\nin that priority queue.\n\nIn the general case, that overhead cannot really be avoided. But when we\nhave a single subiter left then there is no need to use the priority\nqueue anymore because the order is exactly the same as what that subiter\nwould return.\n\nWhile having a single subiter may sound like an edge case, it happens\nmore frequently than one might think. In the most common scenario, you\ncan expect a repository to have a single large table that contains most\nof the records and then a set of smaller tables which contain later\nadditions to the reftable stack. In this case it is quite likely that we\nexhaust subiters of those smaller stacks before exhausting the large\ntable.\n\nSpecial-case this and return records directly from the remaining\nsubiter. This results in a sizeable speedup when iterating over 1m refs\nin a repository with a single table:\n\n  Benchmark 1: show-ref: single matching ref (revision = HEAD~)\n    Time (mean ± σ):     135.4 ms ±   4.4 ms    [User: 132.5 ms, System: 2.8 ms]\n    Range (min … max):   131.0 ms … 166.3 ms    1000 runs\n\n  Benchmark 2: show-ref: single matching ref (revision = HEAD)\n    Time (mean ± σ):     126.3 ms ±   3.9 ms    [User: 123.3 ms, System: 2.8 ms]\n    Range (min … max):   122.7 ms … 157.0 ms    1000 runs\n\n  Summary\n    show-ref: single matching ref (revision = HEAD) ran\n      1.07 ± 0.05 times faster than show-ref: single matching ref (revision = HEAD~)\n\nSigned-off-by: Patrick Steinhardt <ps@pks.im>\n---\n reftable/merged.c | 24 ++++++++++++++++++++++--\n 1 file changed, 22 insertions(+), 2 deletions(-)\n\ndiff --git a/reftable/merged.c b/reftable/merged.c\nindex d9ed4a19dd..29161a32cf 100644\n--- a/reftable/merged.c\n+++ b/reftable/merged.c\n@@ -87,16 +87,36 @@ static int merged_iter_next_entry(struct merged_iter *mi,\n \t\t\t\t  struct reftable_record *rec)\n {\n \tstruct pq_entry entry = { 0 };\n-\tint err = 0;\n+\tint err = 0, empty;\n+\n+\tempty = merged_iter_pqueue_is_empty(mi->pq);\n \n \tif (mi->advance_index >= 0) {\n+\t\t/*\n+\t\t * When there are no pqueue entries then we only have a single\n+\t\t * subiter left. There is no need to use the pqueue in that\n+\t\t * case anymore as we know that the subiter will return entries\n+\t\t * in the correct order already.\n+\t\t *\n+\t\t * While this may sound like a very specific edge case, it may\n+\t\t * happen more frequently than you think. Most repositories\n+\t\t * will end up having a single large base table that contains\n+\t\t * most of the refs. It's thus likely that we exhaust all\n+\t\t * subiters but the one from that base ref.\n+\t\t */\n+\t\tif (empty)\n+\t\t\treturn iterator_next(&mi->subiters[mi->advance_index].iter,\n+\t\t\t\t\t     rec);\n+\n \t\terr = merged_iter_advance_subiter(mi, mi->advance_index);\n \t\tif (err < 0)\n \t\t\treturn err;\n+\t\tif (!err)\n+\t\t\tempty = 0;\n \t\tmi->advance_index = -1;\n \t}\n \n-\tif (merged_iter_pqueue_is_empty(mi->pq))\n+\tif (empty)\n \t\treturn 1;\n \n \tentry = merged_iter_pqueue_remove(&mi->pq);\n-- \n2.43.GIT\n\n"},{"id":"488623","messageId":"68bd6871132bac3ff8d67e908dd31647feab6bc3.1707895758.git.ps@pks.im","threadId":"60913","inReplyTo":"cover.1707895758.git.ps@pks.im","subject":"[PATCH 08/12] reftable/merged: avoid duplicate pqueue emptiness check","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-02-14T07:46:13Z","receivedAt":"2024-02-14T07:46:17Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"When calling `merged_iter_next_void()` we first check whether the iter\nhas been exhausted already. We already perform this check two levels\ndown the stack in `merged_iter_next_entry()` though, which makes this\ncheck redundant.\n\nNow if this check was there to accellerate the common case it might have\nmade sense to keep it. But the iterator being exhausted is rather the\nuncommon case because you can expect most reftable stacks to contain\nmore than two refs.\n\nSimplify the code by removing the check. As `merged_iter_next_void()` is\nbasically empty except for calling `merged_iter_next()` now, merge these\ntwo functions. This also results in a tiny speedup when iterating over\nmany refs:\n\n    Benchmark 1: show-ref: single matching ref (revision = HEAD~)\n      Time (mean ± σ):     125.6 ms ±   3.8 ms    [User: 122.7 ms, System: 2.8 ms]\n      Range (min … max):   122.4 ms … 153.4 ms    1000 runs\n\n    Benchmark 2: show-ref: single matching ref (revision = HEAD)\n      Time (mean ± σ):     124.0 ms ±   3.9 ms    [User: 121.1 ms, System: 2.8 ms]\n      Range (min … max):   120.1 ms … 156.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\nSigned-off-by: Patrick Steinhardt <ps@pks.im>\n---\n reftable/merged.c | 20 ++++++--------------\n 1 file changed, 6 insertions(+), 14 deletions(-)\n\ndiff --git a/reftable/merged.c b/reftable/merged.c\nindex 29161a32cf..f85a24c678 100644\n--- a/reftable/merged.c\n+++ b/reftable/merged.c\n@@ -148,27 +148,19 @@ static int merged_iter_next_entry(struct merged_iter *mi,\n \treturn 0;\n }\n \n-static int merged_iter_next(struct merged_iter *mi, struct reftable_record *rec)\n+static int merged_iter_next_void(void *p, struct reftable_record *rec)\n {\n+\tstruct merged_iter *mi = p;\n \twhile (1) {\n \t\tint err = merged_iter_next_entry(mi, rec);\n-\t\tif (err == 0 && mi->suppress_deletions &&\n-\t\t    reftable_record_is_deletion(rec)) {\n+\t\tif (err)\n+\t\t\treturn err;\n+\t\tif (mi->suppress_deletions && reftable_record_is_deletion(rec))\n \t\t\tcontinue;\n-\t\t}\n-\n-\t\treturn err;\n+\t\treturn 0;\n \t}\n }\n \n-static int merged_iter_next_void(void *p, struct reftable_record *rec)\n-{\n-\tstruct merged_iter *mi = p;\n-\tif (merged_iter_pqueue_is_empty(mi->pq) && mi->advance_index < 0)\n-\t\treturn 1;\n-\treturn merged_iter_next(mi, rec);\n-}\n-\n static struct reftable_iterator_vtable merged_iter_vtable = {\n \t.next = &merged_iter_next_void,\n \t.close = &merged_iter_close,\n-- \n2.43.GIT\n\n"},{"id":"488624","messageId":"3ba697036c1db3837f46775823a7bd55602b4bac.1707895758.git.ps@pks.im","threadId":"60913","inReplyTo":"cover.1707895758.git.ps@pks.im","subject":"[PATCH 09/12] reftable/record: reuse refname when decoding","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-02-14T07:46:19Z","receivedAt":"2024-02-14T07:46:22Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"When decoding a reftable record we will first release the user-provided\nrecord and then decode the new record into it. This is quite inefficient\nas we basically need to reallocate at least the refname every time.\n\nRefactor the function to start tracking the refname capacity. Like this,\nwe can stow away the refname, release, restore and then grow the refname\nto the required number of bytes via `REFTABLE_ALLOC_GROW()`.\n\nThis refactoring is safe to do because all functions that assigning to\nthe refname will first call `release_reftable_record()`, which will zero\nout the complete record after releasing memory.\n\nThis change results in a nice speedup when iterating over 1 million\nrefs:\n\n  Benchmark 1: show-ref: single matching ref (revision = HEAD~)\n\n    Time (mean ± σ):     124.0 ms ±   3.9 ms    [User: 121.1 ms, System: 2.7 ms]\n    Range (min … max):   120.4 ms … 152.7 ms    1000 runs\n\n  Benchmark 2: show-ref: single matching ref (revision = HEAD)\n    Time (mean ± σ):     114.4 ms ±   3.7 ms    [User: 111.5 ms, System: 2.7 ms]\n    Range (min … max):   111.0 ms … 152.1 ms    1000 runs\n\n  Summary\n    show-ref: single matching ref (revision = HEAD) ran\n      1.08 ± 0.05 times faster than show-ref: single matching ref (revision = HEAD~)\n\nFurthermore, with this change we now perform a mostly constant number of\nallocations when iterating. Before this change:\n\n  HEAP SUMMARY:\n      in use at exit: 13,603 bytes in 125 blocks\n    total heap usage: 1,006,620 allocs, 1,006,495 frees, 25,398,363 bytes allocated\n\nAfter this change:\n\n  HEAP SUMMARY:\n      in use at exit: 13,603 bytes in 125 blocks\n    total heap usage: 6,623 allocs, 6,498 frees, 509,592 bytes allocated\n\nSigned-off-by: Patrick Steinhardt <ps@pks.im>\n---\n reftable/record.c          | 16 ++++++++++++----\n reftable/reftable-record.h |  1 +\n 2 files changed, 13 insertions(+), 4 deletions(-)\n\ndiff --git a/reftable/record.c b/reftable/record.c\nindex d6bb42e887..e800cfef00 100644\n--- a/reftable/record.c\n+++ b/reftable/record.c\n@@ -368,16 +368,24 @@ static int reftable_ref_record_decode(void *rec, struct strbuf key,\n \tstruct reftable_ref_record *r = rec;\n \tstruct string_view start = in;\n \tuint64_t update_index = 0;\n-\tint n = get_var_int(&update_index, &in);\n+\tconst char *refname = NULL;\n+\tsize_t refname_cap = 0;\n+\tint n;\n+\n+\tassert(hash_size > 0);\n+\n+\tn = get_var_int(&update_index, &in);\n \tif (n < 0)\n \t\treturn n;\n \tstring_view_consume(&in, n);\n \n+\tSWAP(refname, r->refname);\n+\tSWAP(refname_cap, r->refname_cap);\n \treftable_ref_record_release(r);\n+\tSWAP(refname, r->refname);\n+\tSWAP(refname_cap, r->refname_cap);\n \n-\tassert(hash_size > 0);\n-\n-\tr->refname = reftable_malloc(key.len + 1);\n+\tREFTABLE_ALLOC_GROW(r->refname, key.len + 1, r->refname_cap);\n \tmemcpy(r->refname, key.buf, key.len);\n \tr->refname[key.len] = 0;\n \ndiff --git a/reftable/reftable-record.h b/reftable/reftable-record.h\nindex bb6e99acd3..e657001d42 100644\n--- a/reftable/reftable-record.h\n+++ b/reftable/reftable-record.h\n@@ -22,6 +22,7 @@ license that can be found in the LICENSE file or at\n /* reftable_ref_record holds a ref database entry target_value */\n struct reftable_ref_record {\n \tchar *refname; /* Name of the ref, malloced. */\n+\tsize_t refname_cap;\n \tuint64_t update_index; /* Logical timestamp at which this value is\n \t\t\t\t* written */\n \n-- \n2.43.GIT\n\n"},{"id":"488625","messageId":"d7311598c0f81ad3fa41560b54b0974d41485a23.1707895758.git.ps@pks.im","threadId":"60913","inReplyTo":"cover.1707895758.git.ps@pks.im","subject":"[PATCH 10/12] reftable/record: reuse refname when copying","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-02-14T07:46:24Z","receivedAt":"2024-02-14T07:46:27Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"Do the same optimization as in the preceding commit, but this time for\n`reftable_record_copy()`. While not as noticeable, it still results in a\nsmall speedup when iterating over 1 million refs:\n\n  Benchmark 1: show-ref: single matching ref (revision = HEAD~)\n    Time (mean ± σ):     114.0 ms ±   3.8 ms    [User: 111.1 ms, System: 2.7 ms]\n    Range (min … max):   110.9 ms … 144.3 ms    1000 runs\n\n  Benchmark 2: show-ref: single matching ref (revision = HEAD)\n    Time (mean ± σ):     112.5 ms ±   3.7 ms    [User: 109.5 ms, System: 2.8 ms]\n    Range (min … max):   109.2 ms … 140.7 ms    1000 runs\n\n  Summary\n    show-ref: single matching ref (revision = HEAD) ran\n      1.01 ± 0.05 times faster than show-ref: single matching ref (revision = HEAD~)\n\nSigned-off-by: Patrick Steinhardt <ps@pks.im>\n---\n reftable/record.c | 18 +++++++++++++++---\n 1 file changed, 15 insertions(+), 3 deletions(-)\n\ndiff --git a/reftable/record.c b/reftable/record.c\nindex e800cfef00..3f2a639036 100644\n--- a/reftable/record.c\n+++ b/reftable/record.c\n@@ -205,14 +205,26 @@ static void reftable_ref_record_copy_from(void *rec, const void *src_rec,\n {\n \tstruct reftable_ref_record *ref = rec;\n \tconst struct reftable_ref_record *src = src_rec;\n+\tchar *refname = NULL;\n+\tsize_t refname_cap = 0;\n+\n \tassert(hash_size > 0);\n \n-\t/* This is simple and correct, but we could probably reuse the hash\n-\t * fields. */\n+\tSWAP(refname, ref->refname);\n+\tSWAP(refname_cap, ref->refname_cap);\n \treftable_ref_record_release(ref);\n+\tSWAP(refname, ref->refname);\n+\tSWAP(refname_cap, ref->refname_cap);\n+\n \tif (src->refname) {\n-\t\tref->refname = xstrdup(src->refname);\n+\t\tsize_t refname_len = strlen(src->refname);\n+\n+\t\tREFTABLE_ALLOC_GROW(ref->refname, refname_len + 1,\n+\t\t\t\t    ref->refname_cap);\n+\t\tmemcpy(ref->refname, src->refname, refname_len);\n+\t\tref->refname[refname_len] = 0;\n \t}\n+\n \tref->update_index = src->update_index;\n \tref->value_type = src->value_type;\n \tswitch (src->value_type) {\n-- \n2.43.GIT\n\n"},{"id":"488626","messageId":"f0663c1d62d13d01afb1fa6c3760a38741bdfc8e.1707895758.git.ps@pks.im","threadId":"60913","inReplyTo":"cover.1707895758.git.ps@pks.im","subject":"[PATCH 11/12] reftable/record: decode keys in place","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-02-14T07:46:28Z","receivedAt":"2024-02-14T07:46:31Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"When reading a record from a block, we need to decode the record's key.\nAs reftable keys are prefix-compressed, meaning they reuse a prefix from\nthe preceding record's key, this is a bit more involved than just having\nto copy the relevant bytes: we need to figure out the prefix and suffix\nlengths, copy the prefix from the preceding record and finally copy the\nsuffix from the current record.\n\nThis is done by passing three buffers to `reftable_decode_key()`: one\nbuffer that holds the result, one buffer that holds the last key, and\none buffer that points to the current record. The final key is then\nassembled by calling `strbuf_add()` twice to copy over the prefix and\nsuffix.\n\nPerforming two memory copies is inefficient though. And we can indeed do\nbetter by decoding keys in place. Instead of providing two buffers, the\ncaller may only call a single buffer that is already pre-populated with\nthe last key. Like this, we only have to call `strbuf_setlen()` to trim\nthe record to its prefix and then `strbuf_add()` to add the suffix.\n\nThis refactoring leads to a noticeable performance bump when iterating\nover 1 million refs:\n\n  Benchmark 1: show-ref: single matching ref (revision = HEAD~)\n    Time (mean ± σ):     112.2 ms ±   3.9 ms    [User: 109.3 ms, System: 2.8 ms]\n    Range (min … max):   109.2 ms … 149.6 ms    1000 runs\n\n  Benchmark 2: show-ref: single matching ref (revision = HEAD)\n    Time (mean ± σ):     106.0 ms ±   3.5 ms    [User: 103.2 ms, System: 2.7 ms]\n    Range (min … max):   103.2 ms … 133.7 ms    1000 runs\n\n  Summary\n    show-ref: single matching ref (revision = HEAD) ran\n      1.06 ± 0.05 times faster than show-ref: single matching ref (revision = HEAD~)\n\nSigned-off-by: Patrick Steinhardt <ps@pks.im>\n---\n reftable/block.c       | 25 +++++++++++--------------\n reftable/block.h       |  2 --\n reftable/record.c      | 19 +++++++++----------\n reftable/record.h      |  9 ++++++---\n reftable/record_test.c |  3 ++-\n 5 files changed, 28 insertions(+), 30 deletions(-)\n\ndiff --git a/reftable/block.c b/reftable/block.c\nindex 72eb73b380..ad9074dba6 100644\n--- a/reftable/block.c\n+++ b/reftable/block.c\n@@ -291,9 +291,8 @@ static int restart_key_less(size_t idx, void *args)\n \t/* the restart key is verbatim in the block, so this could avoid the\n \t   alloc for decoding the key */\n \tstruct strbuf rkey = STRBUF_INIT;\n-\tstruct strbuf last_key = STRBUF_INIT;\n \tuint8_t unused_extra;\n-\tint n = reftable_decode_key(&rkey, &unused_extra, last_key, in);\n+\tint n = reftable_decode_key(&rkey, &unused_extra, in);\n \tint result;\n \tif (n < 0) {\n \t\ta->error = 1;\n@@ -326,35 +325,34 @@ int block_iter_next(struct block_iter *it, struct reftable_record *rec)\n \tif (it->next_off >= it->br->block_len)\n \t\treturn 1;\n \n-\tn = reftable_decode_key(&it->key, &extra, it->last_key, in);\n+\tn = reftable_decode_key(&it->last_key, &extra, in);\n \tif (n < 0)\n \t\treturn -1;\n-\n-\tif (!it->key.len)\n+\tif (!it->last_key.len)\n \t\treturn REFTABLE_FORMAT_ERROR;\n \n \tstring_view_consume(&in, n);\n-\tn = reftable_record_decode(rec, it->key, extra, in, it->br->hash_size);\n+\tn = reftable_record_decode(rec, it->last_key, extra, in, it->br->hash_size);\n \tif (n < 0)\n \t\treturn -1;\n \tstring_view_consume(&in, n);\n \n-\tstrbuf_swap(&it->last_key, &it->key);\n \tit->next_off += start.len - in.len;\n \treturn 0;\n }\n \n int block_reader_first_key(struct block_reader *br, struct strbuf *key)\n {\n-\tstruct strbuf empty = STRBUF_INIT;\n-\tint off = br->header_off + 4;\n+\tint off = br->header_off + 4, n;\n \tstruct string_view in = {\n \t\t.buf = br->block.data + off,\n \t\t.len = br->block_len - off,\n \t};\n-\n \tuint8_t extra = 0;\n-\tint n = reftable_decode_key(key, &extra, empty, in);\n+\n+\tstrbuf_reset(key);\n+\n+\tn = reftable_decode_key(key, &extra, in);\n \tif (n < 0)\n \t\treturn n;\n \tif (!key->len)\n@@ -371,7 +369,6 @@ int block_iter_seek(struct block_iter *it, struct strbuf *want)\n void block_iter_close(struct block_iter *it)\n {\n \tstrbuf_release(&it->last_key);\n-\tstrbuf_release(&it->key);\n }\n \n int block_reader_seek(struct block_reader *br, struct block_iter *it,\n@@ -408,8 +405,8 @@ int block_reader_seek(struct block_reader *br, struct block_iter *it,\n \t\tif (err < 0)\n \t\t\tgoto done;\n \n-\t\treftable_record_key(&rec, &it->key);\n-\t\tif (err > 0 || strbuf_cmp(&it->key, want) >= 0) {\n+\t\treftable_record_key(&rec, &it->last_key);\n+\t\tif (err > 0 || strbuf_cmp(&it->last_key, want) >= 0) {\n \t\t\terr = 0;\n \t\t\tgoto done;\n \t\t}\ndiff --git a/reftable/block.h b/reftable/block.h\nindex 17481e6331..51699af233 100644\n--- a/reftable/block.h\n+++ b/reftable/block.h\n@@ -84,12 +84,10 @@ struct block_iter {\n \n \t/* key for last entry we read. */\n \tstruct strbuf last_key;\n-\tstruct strbuf key;\n };\n \n #define BLOCK_ITER_INIT { \\\n \t.last_key = STRBUF_INIT, \\\n-\t.key = STRBUF_INIT, \\\n }\n \n /* initializes a block reader. */\ndiff --git a/reftable/record.c b/reftable/record.c\nindex 3f2a639036..37682cc7d0 100644\n--- a/reftable/record.c\n+++ b/reftable/record.c\n@@ -159,20 +159,19 @@ int reftable_encode_key(int *restart, struct string_view dest,\n \treturn start.len - dest.len;\n }\n \n-int reftable_decode_key(struct strbuf *key, uint8_t *extra,\n-\t\t\tstruct strbuf last_key, struct string_view in)\n+int reftable_decode_key(struct strbuf *last_key, uint8_t *extra,\n+\t\t\tstruct string_view in)\n {\n \tint start_len = in.len;\n \tuint64_t prefix_len = 0;\n \tuint64_t suffix_len = 0;\n-\tint n = get_var_int(&prefix_len, &in);\n+\tint n;\n+\n+\tn = get_var_int(&prefix_len, &in);\n \tif (n < 0)\n \t\treturn -1;\n \tstring_view_consume(&in, n);\n \n-\tif (prefix_len > last_key.len)\n-\t\treturn -1;\n-\n \tn = get_var_int(&suffix_len, &in);\n \tif (n <= 0)\n \t\treturn -1;\n@@ -181,12 +180,12 @@ int reftable_decode_key(struct strbuf *key, uint8_t *extra,\n \t*extra = (uint8_t)(suffix_len & 0x7);\n \tsuffix_len >>= 3;\n \n-\tif (in.len < suffix_len)\n+\tif (in.len < suffix_len ||\n+\t    prefix_len > last_key->len)\n \t\treturn -1;\n \n-\tstrbuf_reset(key);\n-\tstrbuf_add(key, last_key.buf, prefix_len);\n-\tstrbuf_add(key, in.buf, suffix_len);\n+\tstrbuf_setlen(last_key, prefix_len);\n+\tstrbuf_add(last_key, in.buf, suffix_len);\n \tstring_view_consume(&in, suffix_len);\n \n \treturn start_len - in.len;\ndiff --git a/reftable/record.h b/reftable/record.h\nindex a05e2be179..91c9c6ebfd 100644\n--- a/reftable/record.h\n+++ b/reftable/record.h\n@@ -81,9 +81,12 @@ int reftable_encode_key(int *is_restart, struct string_view dest,\n \t\t\tstruct strbuf prev_key, struct strbuf key,\n \t\t\tuint8_t extra);\n \n-/* Decode into `key` and `extra` from `in` */\n-int reftable_decode_key(struct strbuf *key, uint8_t *extra,\n-\t\t\tstruct strbuf last_key, struct string_view in);\n+/*\n+ * Decode into `last_key` and `extra` from `in`. `last_key` is expected to\n+ * contain the decoded key of the preceding record, if any.\n+ */\n+int reftable_decode_key(struct strbuf *last_key, uint8_t *extra,\n+\t\t\tstruct string_view in);\n \n /* reftable_index_record are used internally to speed up lookups. */\n struct reftable_index_record {\ndiff --git a/reftable/record_test.c b/reftable/record_test.c\nindex a86cff5526..89209894d8 100644\n--- a/reftable/record_test.c\n+++ b/reftable/record_test.c\n@@ -295,7 +295,8 @@ static void test_key_roundtrip(void)\n \tEXPECT(!restart);\n \tEXPECT(n > 0);\n \n-\tm = reftable_decode_key(&roundtrip, &rt_extra, last_key, dest);\n+\tstrbuf_addstr(&roundtrip, \"refs/heads/master\");\n+\tm = reftable_decode_key(&roundtrip, &rt_extra, dest);\n \tEXPECT(n == m);\n \tEXPECT(0 == strbuf_cmp(&key, &roundtrip));\n \tEXPECT(rt_extra == extra);\n-- \n2.43.GIT\n\n"},{"id":"488627","messageId":"56ec6549326e52d88e6d063ce1a9f26b2a805d09.1707895758.git.ps@pks.im","threadId":"60913","inReplyTo":"cover.1707895758.git.ps@pks.im","subject":"[PATCH 12/12] reftable: allow inlining of a few functions","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-02-14T07:46:35Z","receivedAt":"2024-02-14T07:46:38Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"We have a few functions which are basically just accessors to\nstructures. As those functions are executed inside the hot loop when\niterating through many refs, the fact that they cannot be inlined is\ncosting us some performance.\n\nMove the function definitions into their respective headers so that they\ncan be inlined. This results in a performance improvement when iterating\nover 1 million refs:\n\n  Benchmark 1: show-ref: single matching ref (revision = HEAD~)\n    Time (mean ± σ):     102.4 ms ±   3.7 ms    [User: 99.6 ms, System: 2.7 ms]\n    Range (min … max):    99.1 ms … 129.1 ms    1000 runs\n\n  Benchmark 2: show-ref: single matching ref (revision = HEAD)\n    Time (mean ± σ):      98.3 ms ±   3.7 ms    [User: 95.4 ms, System: 2.7 ms]\n    Range (min … max):    94.9 ms … 126.2 ms    1000 runs\n\n  Summary\n    show-ref: single matching ref (revision = HEAD) ran\n      1.04 ± 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     | 10 ----------\n reftable/pq.h     | 12 ++++++++++--\n reftable/record.c | 11 -----------\n reftable/record.h | 12 ++++++++++--\n 4 files changed, 20 insertions(+), 25 deletions(-)\n\ndiff --git a/reftable/pq.c b/reftable/pq.c\nindex 0074d6bc43..7fb45d8c60 100644\n--- a/reftable/pq.c\n+++ b/reftable/pq.c\n@@ -20,16 +20,6 @@ int pq_less(struct pq_entry *a, struct pq_entry *b)\n \treturn cmp < 0;\n }\n \n-struct pq_entry merged_iter_pqueue_top(struct merged_iter_pqueue pq)\n-{\n-\treturn pq.heap[0];\n-}\n-\n-int merged_iter_pqueue_is_empty(struct merged_iter_pqueue pq)\n-{\n-\treturn pq.len == 0;\n-}\n-\n struct pq_entry merged_iter_pqueue_remove(struct merged_iter_pqueue *pq)\n {\n \tint i = 0;\ndiff --git a/reftable/pq.h b/reftable/pq.h\nindex ce23972c16..f796c23179 100644\n--- a/reftable/pq.h\n+++ b/reftable/pq.h\n@@ -22,12 +22,20 @@ struct merged_iter_pqueue {\n \tsize_t cap;\n };\n \n-struct pq_entry merged_iter_pqueue_top(struct merged_iter_pqueue pq);\n-int merged_iter_pqueue_is_empty(struct merged_iter_pqueue pq);\n void merged_iter_pqueue_check(struct merged_iter_pqueue pq);\n struct pq_entry merged_iter_pqueue_remove(struct merged_iter_pqueue *pq);\n void merged_iter_pqueue_add(struct merged_iter_pqueue *pq, const struct pq_entry *e);\n void merged_iter_pqueue_release(struct merged_iter_pqueue *pq);\n int pq_less(struct pq_entry *a, struct pq_entry *b);\n \n+static inline struct pq_entry merged_iter_pqueue_top(struct merged_iter_pqueue pq)\n+{\n+\treturn pq.heap[0];\n+}\n+\n+static inline int merged_iter_pqueue_is_empty(struct merged_iter_pqueue pq)\n+{\n+\treturn pq.len == 0;\n+}\n+\n #endif\ndiff --git a/reftable/record.c b/reftable/record.c\nindex 37682cc7d0..fdda28645c 100644\n--- a/reftable/record.c\n+++ b/reftable/record.c\n@@ -1176,11 +1176,6 @@ void reftable_record_key(struct reftable_record *rec, struct strbuf *dest)\n \treftable_record_vtable(rec)->key(reftable_record_data(rec), dest);\n }\n \n-uint8_t reftable_record_type(struct reftable_record *rec)\n-{\n-\treturn rec->type;\n-}\n-\n int reftable_record_encode(struct reftable_record *rec, struct string_view dest,\n \t\t\t   int hash_size)\n {\n@@ -1302,12 +1297,6 @@ int reftable_log_record_is_deletion(const struct reftable_log_record *log)\n \treturn (log->value_type == REFTABLE_LOG_DELETION);\n }\n \n-void string_view_consume(struct string_view *s, int n)\n-{\n-\ts->buf += n;\n-\ts->len -= n;\n-}\n-\n static void *reftable_record_data(struct reftable_record *rec)\n {\n \tswitch (rec->type) {\ndiff --git a/reftable/record.h b/reftable/record.h\nindex 91c9c6ebfd..5e8304e052 100644\n--- a/reftable/record.h\n+++ b/reftable/record.h\n@@ -25,7 +25,11 @@ struct string_view {\n };\n \n /* Advance `s.buf` by `n`, and decrease length. */\n-void string_view_consume(struct string_view *s, int n);\n+static inline void string_view_consume(struct string_view *s, int n)\n+{\n+\ts->buf += n;\n+\ts->len -= n;\n+}\n \n /* utilities for de/encoding varints */\n \n@@ -127,7 +131,6 @@ 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-uint8_t reftable_record_type(struct reftable_record *rec);\n void reftable_record_copy_from(struct reftable_record *rec,\n \t\t\t       struct reftable_record *src, int hash_size);\n uint8_t reftable_record_val_type(struct reftable_record *rec);\n@@ -138,6 +141,11 @@ int reftable_record_decode(struct reftable_record *rec, struct strbuf key,\n \t\t\t   int hash_size);\n int reftable_record_is_deletion(struct reftable_record *rec);\n \n+static inline uint8_t reftable_record_type(struct reftable_record *rec)\n+{\n+\treturn rec->type;\n+}\n+\n /* frees and zeroes out the embedded record */\n void reftable_record_release(struct reftable_record *rec);\n \n-- \n2.43.GIT\n\n"},{"id":"489004","messageId":"qprofop624nevbicid4rplfqlanfrujyxiilfqwchrppnmw7u4@3dvw5udjtrah","threadId":"60913","inReplyTo":"be807e7650e2b11e5d6f7dd84ca1c549408f678a.1707895758.git.ps@pks.im","subject":"Re: [PATCH 02/12] reftable/merged: make `merged_iter` structure private","fromName":"Justin Tobler","fromEmail":"jltobler@gmail.com","sentAt":"2024-02-20T18:15:23Z","receivedAt":"2024-02-20T18:16:03Z","isPatch":true,"sender":{"key":"jltobler@gmail.com","avatar":"https://avatars.githubusercontent.com/u/53454972?v=4"},"body":"On 24/02/14 08:45AM, Patrick Steinhardt wrote:\n> The `merged_iter` structure is not used anywhere outside of \"merged.c\",\n> but is declared in its header. Move it into the code file so that it is\n> clear that its implementation details are never exposed to anything.\n> \n> Signed-off-by: Patrick Steinhardt <ps@pks.im>\n> ---\n>  reftable/merged.c | 9 +++++++++\n>  reftable/merged.h | 9 ---------\n>  2 files changed, 9 insertions(+), 9 deletions(-)\n> \n> diff --git a/reftable/merged.c b/reftable/merged.c\n> index 1aa6cd31b7..12ebd732e8 100644\n> --- a/reftable/merged.c\n> +++ b/reftable/merged.c\n> @@ -17,6 +17,15 @@ license that can be found in the LICENSE file or at\n>  #include \"reftable-error.h\"\n>  #include \"system.h\"\n>  \n\nsuggestion: I think it would be nice to document a little about the\nmerge iterator here at a high-level. Maybe just to explain that this\nallows iteration over multiple tables as if it were a single table.\n\n> +struct merged_iter {\n> +\tstruct reftable_iterator *stack;\n> +\tuint32_t hash_id;\n> +\tsize_t stack_len;\n> +\tuint8_t typ;\n> +\tint suppress_deletions;\n> +\tstruct merged_iter_pqueue pq;\n> +};\n> +\n>  static int merged_iter_init(struct merged_iter *mi)\n>  {\n>  \tfor (size_t i = 0; i < mi->stack_len; i++) {\n> diff --git a/reftable/merged.h b/reftable/merged.h\n> index 7d9f95d27e..288ad66656 100644\n> --- a/reftable/merged.h\n> +++ b/reftable/merged.h\n> @@ -24,15 +24,6 @@ struct reftable_merged_table {\n>  \tuint64_t max;\n>  };\n>  \n\nSince we are removing `merge_iter` from the header here, I think we can\nalso remove the `#include \"pg.h\"`.\n\n> -struct merged_iter {\n> -\tstruct reftable_iterator *stack;\n> -\tuint32_t hash_id;\n> -\tsize_t stack_len;\n> -\tuint8_t typ;\n> -\tint suppress_deletions;\n> -\tstruct merged_iter_pqueue pq;\n> -};\n> -\n>  void merged_table_release(struct reftable_merged_table *mt);\n>  \n>  #endif\n> -- \n> 2.43.GIT\n> \n\n\n"},{"id":"489006","messageId":"ns2yw3icnl3udejbgsv4ojwgzbe7eg57bvsm53kciuemlvmgbr@mpjtogpzdavi","threadId":"60913","inReplyTo":"38d45995662ba92f4b985b82deac298446274511.1707895758.git.ps@pks.im","subject":"Re: [PATCH 03/12] reftable/merged: advance subiter on subsequent iteration","fromName":"Justin Tobler","fromEmail":"jltobler@gmail.com","sentAt":"2024-02-20T18:25:10Z","receivedAt":"2024-02-20T18:25:50Z","isPatch":true,"sender":{"key":"jltobler@gmail.com","avatar":"https://avatars.githubusercontent.com/u/53454972?v=4"},"body":"On 24/02/14 08:45AM, Patrick Steinhardt wrote:\n> When advancing the merged iterator, we pop the top-most entry from its\n\ns/top-most/topmost\n\n> priority queue and then advance the sub-iterator that the entry belongs\n> to, adding the result as a new entry. This is quite sensible in the case\n> where the merged iterator is used to actual iterate through records. But\n\ns/actual/actually\n\n> the merged iterator is also used when we look up a single record, only,\n> so advancing the sub-iterator is wasted effort because we would never\n> even look at the result.\n> \n> Instead of immediately advancing the sub-iterator, we can also defer\n> this to the next iteration of the merged iterator by storing the\n> intent-to-advance. This results in a small speedup when reading many\n> records. The following benchmark creates 10000 refs, which will also end\n> up with many ref lookups:\n> \n>     Benchmark 1: update-ref: create many refs (revision = HEAD~)\n>       Time (mean ± σ):     337.2 ms ±   7.3 ms    [User: 200.1 ms, System: 136.9 ms]\n>       Range (min … max):   329.3 ms … 373.2 ms    100 runs\n> \n>     Benchmark 2: update-ref: create many refs (revision = HEAD)\n>       Time (mean ± σ):     332.5 ms ±   5.9 ms    [User: 197.2 ms, System: 135.1 ms]\n>       Range (min … max):   327.6 ms … 359.8 ms    100 runs\n> \n>     Summary\n>       update-ref: create many refs (revision = HEAD) ran\n>         1.01 ± 0.03 times faster than update-ref: create many refs (revision = HEAD~)\n> \n> While this speedup alone isn't really worth it, this refactoring will\n> also allow two additional optimizations in subsequent patches. First, it\n> will allow us to special-case when there is only a single sub-iter left\n> to circumvent the priority queue altogether. And second, it makes it\n> easier to avoid copying records to the caller.\n> \n> Signed-off-by: Patrick Steinhardt <ps@pks.im>\n> ---\n>  reftable/merged.c | 26 ++++++++++++--------------\n>  1 file changed, 12 insertions(+), 14 deletions(-)\n> \n> diff --git a/reftable/merged.c b/reftable/merged.c\n> index 12ebd732e8..9b1ccfff00 100644\n> --- a/reftable/merged.c\n> +++ b/reftable/merged.c\n> @@ -19,11 +19,12 @@ license that can be found in the LICENSE file or at\n>  \n>  struct merged_iter {\n>  \tstruct reftable_iterator *stack;\n> +\tstruct merged_iter_pqueue pq;\n>  \tuint32_t hash_id;\n>  \tsize_t stack_len;\n>  \tuint8_t typ;\n>  \tint suppress_deletions;\n> -\tstruct merged_iter_pqueue pq;\n> +\tssize_t advance_index;\n>  };\n>  \n>  static int merged_iter_init(struct merged_iter *mi)\n> @@ -96,13 +97,17 @@ static int merged_iter_next_entry(struct merged_iter *mi,\n>  \tstruct pq_entry entry = { 0 };\n>  \tint err = 0;\n>  \n> +\tif (mi->advance_index >= 0) {\n> +\t\terr = merged_iter_advance_subiter(mi, mi->advance_index);\n> +\t\tif (err < 0)\n> +\t\t\treturn err;\n> +\t\tmi->advance_index = -1;\n> +\t}\n> +\n\nWithout additional context, it isn't immediately clear to me why the\nsub-iterator is condionally advanced at the beginning. Maybe a comment\ncould be added to explain as done in the commit message to help with\nclarity?\n\n>  \tif (merged_iter_pqueue_is_empty(mi->pq))\n>  \t\treturn 1;\n>  \n>  \tentry = merged_iter_pqueue_remove(&mi->pq);\n> -\terr = merged_iter_advance_subiter(mi, entry.index);\n> -\tif (err < 0)\n> -\t\treturn err;\n>  \n>  \t/*\n>  \t  One can also use reftable as datacenter-local storage, where the ref\n> @@ -116,14 +121,6 @@ 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\nI'm not quite sure I follow by the above check is removed as part of\nthis change. Would you mind clarifying?\n\n-Justin\n"},{"id":"489519","messageId":"cover.1709045927.git.ps@pks.im","threadId":"60913","inReplyTo":"cover.1707895758.git.ps@pks.im","subject":"[PATCH v2 00/13] reftable: improve ref iteration performance (pt.2)","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-02-27T15:06:13Z","receivedAt":"2024-02-27T15:06:19Z","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 raw ref\niteration performance with the reftable backend.\n\nChanges compared to v1 are sparse:\n\n  - Adapted an include because we don't need \"pq.h\" anymore.\n\n  - Some commit message improvements.\n\n  - I re-did the performance benchmarks in patch 12 as I noticed they\n    were stale.\n\n  - I also included one more patch to avoid re-computing the prefix\n    length on every iteration.\n\nThis patch series is now based on \"master\" directly at a2082dbdd3 (Start\nthe 2.45 cycle, 2024-02-26).\n\nThanks!\n\nPatrick\n\nPatrick Steinhardt (13):\n  reftable/pq: use `size_t` to track iterator index\n  reftable/merged: make `merged_iter` structure private\n  reftable/merged: advance subiter on subsequent iteration\n  reftable/merged: make subiters own their records\n  reftable/merged: remove unnecessary null check for subiters\n  reftable/merged: handle subiter cleanup on close only\n  reftable/merged: circumvent pqueue with single subiter\n  reftable/merged: avoid duplicate pqueue emptiness check\n  reftable/record: reuse refname when decoding\n  reftable/record: reuse refname when copying\n  reftable/record: decode keys in place\n  reftable: allow inlining of a few functions\n  refs/reftable: precompute prefix length\n\n refs/reftable-backend.c    |   6 +-\n reftable/block.c           |  25 +++----\n reftable/block.h           |   2 -\n reftable/iter.c            |   5 --\n reftable/iter.h            |   4 --\n reftable/merged.c          | 139 +++++++++++++++++++------------------\n reftable/merged.h          |  11 +--\n reftable/pq.c              |  18 +----\n reftable/pq.h              |  16 +++--\n reftable/pq_test.c         |  41 +++++------\n reftable/record.c          |  64 +++++++++--------\n reftable/record.h          |  21 ++++--\n reftable/record_test.c     |   3 +-\n reftable/reftable-record.h |   1 +\n 14 files changed, 175 insertions(+), 181 deletions(-)\n\nRange-diff against v1:\n 1:  eeaaac9e07 =  1:  292e5f8888 reftable/pq: use `size_t` to track iterator index\n 2:  be807e7650 !  2:  95e1ccafc4 reftable/merged: make `merged_iter` structure private\n    @@ reftable/merged.c: license that can be found in the LICENSE file or at\n      \tfor (size_t i = 0; i < mi->stack_len; i++) {\n     \n      ## reftable/merged.h ##\n    +@@ reftable/merged.h: license that can be found in the LICENSE file or at\n    + #ifndef MERGED_H\n    + #define MERGED_H\n    + \n    +-#include \"pq.h\"\n    ++#include \"system.h\"\n    + \n    + struct reftable_merged_table {\n    + \tstruct reftable_table *stack;\n     @@ reftable/merged.h: struct reftable_merged_table {\n      \tuint64_t max;\n      };\n 3:  38d4599566 !  3:  0e327e5fe3 reftable/merged: advance subiter on subsequent iteration\n    @@ Metadata\n      ## Commit message ##\n         reftable/merged: advance subiter on subsequent iteration\n     \n    -    When advancing the merged iterator, we pop the top-most entry from its\n    +    When advancing the merged iterator, we pop the topmost entry from its\n         priority queue and then advance the sub-iterator that the entry belongs\n         to, adding the result as a new entry. This is quite sensible in the case\n    -    where the merged iterator is used to actual iterate through records. But\n    -    the merged iterator is also used when we look up a single record, only,\n    -    so advancing the sub-iterator is wasted effort because we would never\n    -    even look at the result.\n    +    where the merged iterator is used to actually iterate through records.\n    +    But the merged iterator is also used when we look up a single record,\n    +    only, so advancing the sub-iterator is wasted effort because we would\n    +    never even look at the result.\n     \n         Instead of immediately advancing the sub-iterator, we can also defer\n         this to the next iteration of the merged iterator by storing the\n 4:  2c51c60d16 =  4:  494d74deff reftable/merged: make subiters own their records\n 5:  f1156dbf51 =  5:  0adf34d08b reftable/merged: remove unnecessary null check for subiters\n 6:  4e50ac6550 =  6:  01152ce130 reftable/merged: handle subiter cleanup on close only\n 7:  cd65d849a4 =  7:  370b6cfc6c reftable/merged: circumvent pqueue with single subiter\n 8:  68bd687113 =  8:  1e279f21e6 reftable/merged: avoid duplicate pqueue emptiness check\n 9:  3ba697036c =  9:  15a8cbf678 reftable/record: reuse refname when decoding\n10:  d7311598c0 = 10:  35b1af2f06 reftable/record: reuse refname when copying\n11:  f0663c1d62 = 11:  d7151ef361 reftable/record: decode keys in place\n12:  56ec654932 ! 12:  99b238a40d reftable: allow inlining of a few functions\n    @@ Commit message\n         can be inlined. This results in a performance improvement when iterating\n         over 1 million refs:\n     \n    -      Benchmark 1: show-ref: single matching ref (revision = HEAD~)\n    -        Time (mean ± σ):     102.4 ms ±   3.7 ms    [User: 99.6 ms, System: 2.7 ms]\n    -        Range (min … max):    99.1 ms … 129.1 ms    1000 runs\n    +        Benchmark 1: show-ref: single matching ref (revision = HEAD~)\n    +          Time (mean ± σ):     105.9 ms ±   3.6 ms    [User: 103.0 ms, System: 2.8 ms]\n    +          Range (min … max):   103.1 ms … 133.4 ms    1000 runs\n     \n    -      Benchmark 2: show-ref: single matching ref (revision = HEAD)\n    -        Time (mean ± σ):      98.3 ms ±   3.7 ms    [User: 95.4 ms, System: 2.7 ms]\n    -        Range (min … max):    94.9 ms … 126.2 ms    1000 runs\n    +        Benchmark 2: show-ref: single matching ref (revision = HEAD)\n    +          Time (mean ± σ):     100.7 ms ±   3.4 ms    [User: 97.8 ms, System: 2.8 ms]\n    +          Range (min … max):    97.8 ms … 124.0 ms    1000 runs\n     \n    -      Summary\n    -        show-ref: single matching ref (revision = HEAD) ran\n    -          1.04 ± 0.05 times faster than show-ref: single matching ref (revision = HEAD~)\n    +        Summary\n    +          show-ref: single matching ref (revision = HEAD) ran\n    +            1.05 ± 0.05 times faster than show-ref: single matching ref (revision = HEAD~)\n     \n         Signed-off-by: Patrick Steinhardt <ps@pks.im>\n     \n -:  ---------- > 13:  627bd1f5f7 refs/reftable: precompute prefix length\n-- \n2.44.0\n\n"},{"id":"489520","messageId":"292e5f88889142eb29ced96010b02025b134e3ae.1709045927.git.ps@pks.im","threadId":"60913","inReplyTo":"cover.1709045927.git.ps@pks.im","subject":"[PATCH v2 01/13] reftable/pq: use `size_t` to track iterator index","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-02-27T15:06:17Z","receivedAt":"2024-02-27T15:06:21Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"The reftable priority queue is used by the merged iterator to yield\nrecords from its sub-iterators in the expected order. Each entry has a\nrecord corresponding to such a sub-iterator as well as an index that\nindicates which sub-iterator the record belongs to. But while the\nsub-iterators are tracked with a `size_t`, we store the index as an\n`int` in the entry.\n\nFix this and use `size_t` consistently.\n\nSigned-off-by: Patrick Steinhardt <ps@pks.im>\n---\n reftable/pq.h | 2 +-\n 1 file changed, 1 insertion(+), 1 deletion(-)\n\ndiff --git a/reftable/pq.h b/reftable/pq.h\nindex e85bac9b52..9e25a43a36 100644\n--- a/reftable/pq.h\n+++ b/reftable/pq.h\n@@ -12,7 +12,7 @@ license that can be found in the LICENSE file or at\n #include \"record.h\"\n \n struct pq_entry {\n-\tint index;\n+\tsize_t index;\n \tstruct reftable_record rec;\n };\n \n-- \n2.44.0\n\n"},{"id":"489521","messageId":"95e1ccafc42aef324b5d44580d16d9463d18d371.1709045927.git.ps@pks.im","threadId":"60913","inReplyTo":"cover.1709045927.git.ps@pks.im","subject":"[PATCH v2 02/13] reftable/merged: make `merged_iter` structure private","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-02-27T15:06:22Z","receivedAt":"2024-02-27T15:06:26Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"The `merged_iter` structure is not used anywhere outside of \"merged.c\",\nbut is declared in its header. Move it into the code file so that it is\nclear that its implementation details are never exposed to anything.\n\nSigned-off-by: Patrick Steinhardt <ps@pks.im>\n---\n reftable/merged.c |  9 +++++++++\n reftable/merged.h | 11 +----------\n 2 files changed, 10 insertions(+), 10 deletions(-)\n\ndiff --git a/reftable/merged.c b/reftable/merged.c\nindex 1aa6cd31b7..12ebd732e8 100644\n--- a/reftable/merged.c\n+++ b/reftable/merged.c\n@@ -17,6 +17,15 @@ license that can be found in the LICENSE file or at\n #include \"reftable-error.h\"\n #include \"system.h\"\n \n+struct merged_iter {\n+\tstruct reftable_iterator *stack;\n+\tuint32_t hash_id;\n+\tsize_t stack_len;\n+\tuint8_t typ;\n+\tint suppress_deletions;\n+\tstruct merged_iter_pqueue pq;\n+};\n+\n static int merged_iter_init(struct merged_iter *mi)\n {\n \tfor (size_t i = 0; i < mi->stack_len; i++) {\ndiff --git a/reftable/merged.h b/reftable/merged.h\nindex 7d9f95d27e..a2571dbc99 100644\n--- a/reftable/merged.h\n+++ b/reftable/merged.h\n@@ -9,7 +9,7 @@ license that can be found in the LICENSE file or at\n #ifndef MERGED_H\n #define MERGED_H\n \n-#include \"pq.h\"\n+#include \"system.h\"\n \n struct reftable_merged_table {\n \tstruct reftable_table *stack;\n@@ -24,15 +24,6 @@ struct reftable_merged_table {\n \tuint64_t max;\n };\n \n-struct merged_iter {\n-\tstruct reftable_iterator *stack;\n-\tuint32_t hash_id;\n-\tsize_t stack_len;\n-\tuint8_t typ;\n-\tint suppress_deletions;\n-\tstruct merged_iter_pqueue pq;\n-};\n-\n void merged_table_release(struct reftable_merged_table *mt);\n \n #endif\n-- \n2.44.0\n\n"},{"id":"489522","messageId":"0e327e5fe360560b4de8c5098879581bbde2baa9.1709045927.git.ps@pks.im","threadId":"60913","inReplyTo":"cover.1709045927.git.ps@pks.im","subject":"[PATCH v2 03/13] reftable/merged: advance subiter on subsequent iteration","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-02-27T15:06:26Z","receivedAt":"2024-02-27T15:06:30Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"When advancing the merged iterator, we pop the topmost entry from its\npriority queue and then advance the sub-iterator that the entry belongs\nto, adding the result as a new entry. This is quite sensible in the case\nwhere the merged iterator is used to actually iterate through records.\nBut the merged iterator is also used when we look up a single record,\nonly, so advancing the sub-iterator is wasted effort because we would\nnever even look at the result.\n\nInstead of immediately advancing the sub-iterator, we can also defer\nthis to the next iteration of the merged iterator by storing the\nintent-to-advance. This results in a small speedup when reading many\nrecords. The following benchmark creates 10000 refs, which will also end\nup with many ref lookups:\n\n    Benchmark 1: update-ref: create many refs (revision = HEAD~)\n      Time (mean ± σ):     337.2 ms ±   7.3 ms    [User: 200.1 ms, System: 136.9 ms]\n      Range (min … max):   329.3 ms … 373.2 ms    100 runs\n\n    Benchmark 2: update-ref: create many refs (revision = HEAD)\n      Time (mean ± σ):     332.5 ms ±   5.9 ms    [User: 197.2 ms, System: 135.1 ms]\n      Range (min … max):   327.6 ms … 359.8 ms    100 runs\n\n    Summary\n      update-ref: create many refs (revision = HEAD) ran\n        1.01 ± 0.03 times faster than update-ref: create many refs (revision = HEAD~)\n\nWhile this speedup alone isn't really worth it, this refactoring will\nalso allow two additional optimizations in subsequent patches. First, it\nwill allow us to special-case when there is only a single sub-iter left\nto circumvent the priority queue altogether. And second, it makes it\neasier to avoid copying records to the caller.\n\nSigned-off-by: Patrick Steinhardt <ps@pks.im>\n---\n reftable/merged.c | 26 ++++++++++++--------------\n 1 file changed, 12 insertions(+), 14 deletions(-)\n\ndiff --git a/reftable/merged.c b/reftable/merged.c\nindex 12ebd732e8..9b1ccfff00 100644\n--- a/reftable/merged.c\n+++ b/reftable/merged.c\n@@ -19,11 +19,12 @@ license that can be found in the LICENSE file or at\n \n struct merged_iter {\n \tstruct reftable_iterator *stack;\n+\tstruct merged_iter_pqueue pq;\n \tuint32_t hash_id;\n \tsize_t stack_len;\n \tuint8_t typ;\n \tint suppress_deletions;\n-\tstruct merged_iter_pqueue pq;\n+\tssize_t advance_index;\n };\n \n static int merged_iter_init(struct merged_iter *mi)\n@@ -96,13 +97,17 @@ static int merged_iter_next_entry(struct merged_iter *mi,\n \tstruct pq_entry entry = { 0 };\n \tint err = 0;\n \n+\tif (mi->advance_index >= 0) {\n+\t\terr = merged_iter_advance_subiter(mi, mi->advance_index);\n+\t\tif (err < 0)\n+\t\t\treturn err;\n+\t\tmi->advance_index = -1;\n+\t}\n+\n \tif (merged_iter_pqueue_is_empty(mi->pq))\n \t\treturn 1;\n \n \tentry = merged_iter_pqueue_remove(&mi->pq);\n-\terr = merged_iter_advance_subiter(mi, entry.index);\n-\tif (err < 0)\n-\t\treturn err;\n \n \t/*\n \t  One can also use reftable as datacenter-local storage, where the ref\n@@ -116,14 +121,6 @@ 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@@ -137,6 +134,7 @@ static int merged_iter_next_entry(struct merged_iter *mi,\n \n \treftable_record_release(rec);\n \t*rec = entry.rec;\n+\tmi->advance_index = entry.index;\n \n done:\n \tif (err)\n@@ -160,9 +158,8 @@ static int merged_iter_next(struct merged_iter *mi, struct reftable_record *rec)\n static int merged_iter_next_void(void *p, struct reftable_record *rec)\n {\n \tstruct merged_iter *mi = p;\n-\tif (merged_iter_pqueue_is_empty(mi->pq))\n+\tif (merged_iter_pqueue_is_empty(mi->pq) && mi->advance_index < 0)\n \t\treturn 1;\n-\n \treturn merged_iter_next(mi, rec);\n }\n \n@@ -255,6 +252,7 @@ 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.advance_index = -1,\n \t};\n \tstruct merged_iter *p;\n \tint err;\n-- \n2.44.0\n\n"},{"id":"489523","messageId":"494d74deffcc9d473431c238b713d65015305fa4.1709045927.git.ps@pks.im","threadId":"60913","inReplyTo":"cover.1709045927.git.ps@pks.im","subject":"[PATCH v2 04/13] reftable/merged: make subiters own their records","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-02-27T15:06:30Z","receivedAt":"2024-02-27T15:06:34Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"For each subiterator, the merged table needs to track their current\nrecord. This record is owned by the priority queue though instead of by\nthe merged iterator. This is not optimal performance-wise.\n\nFor one, we need to move around records whenever we add or remove a\nrecord from the priority queue. Thus, the bigger the entries the more\nbytes we need to copy around. And compared to pointers, a reftable\nrecord is rather on the bigger side. The other issue is that this makes\nit harder to reuse the records.\n\nRefactor the code so that the merged iterator tracks ownership of the\nrecords per-subiter. Instead of having records in the priority queue, we\ncan now use mere pointers to the per-subiter records. This also allows\nus to swap records between the caller and the per-subiter record instead\nof doing an actual copy via `reftable_record_copy_from()`, which removes\nthe need to release the caller-provided record.\n\nThis results in a noticeable speedup when iterating through many refs.\nThe following benchmark iterates through 1 million refs:\n\n  Benchmark 1: show-ref: single matching ref (revision = HEAD~)\n    Time (mean ± σ):     145.5 ms ±   4.5 ms    [User: 142.5 ms, System: 2.8 ms]\n    Range (min … max):   141.3 ms … 177.0 ms    1000 runs\n\n  Benchmark 2: show-ref: single matching ref (revision = HEAD)\n    Time (mean ± σ):     139.0 ms ±   4.7 ms    [User: 136.1 ms, System: 2.8 ms]\n    Range (min … max):   134.2 ms … 182.2 ms    1000 runs\n\n  Summary\n    show-ref: single matching ref (revision = HEAD) ran\n      1.05 ± 0.05 times faster than show-ref: single matching ref (revision = HEAD~)\n\nThis refactoring also allows a subsequent refactoring where we start\nreusing memory allocated by the reftable records because we do not need\nto release the caller-provided record anymore.\n\nSigned-off-by: Patrick Steinhardt <ps@pks.im>\n---\n reftable/merged.c  | 54 ++++++++++++++++++++++++----------------------\n reftable/pq.c      |  8 ++-----\n reftable/pq.h      |  2 +-\n reftable/pq_test.c | 41 ++++++++++++++++-------------------\n 4 files changed, 49 insertions(+), 56 deletions(-)\n\ndiff --git a/reftable/merged.c b/reftable/merged.c\nindex 9b1ccfff00..ae74234472 100644\n--- a/reftable/merged.c\n+++ b/reftable/merged.c\n@@ -17,8 +17,13 @@ license that can be found in the LICENSE file or at\n #include \"reftable-error.h\"\n #include \"system.h\"\n \n+struct merged_subiter {\n+\tstruct reftable_iterator iter;\n+\tstruct reftable_record rec;\n+};\n+\n struct merged_iter {\n-\tstruct reftable_iterator *stack;\n+\tstruct merged_subiter *subiters;\n \tstruct merged_iter_pqueue pq;\n \tuint32_t hash_id;\n \tsize_t stack_len;\n@@ -32,16 +37,18 @@ static int merged_iter_init(struct merged_iter *mi)\n \tfor (size_t i = 0; i < mi->stack_len; i++) {\n \t\tstruct pq_entry e = {\n \t\t\t.index = i,\n+\t\t\t.rec = &mi->subiters[i].rec,\n \t\t};\n \t\tint err;\n \n-\t\treftable_record_init(&e.rec, mi->typ);\n-\t\terr = iterator_next(&mi->stack[i], &e.rec);\n+\t\treftable_record_init(&mi->subiters[i].rec, mi->typ);\n+\t\terr = iterator_next(&mi->subiters[i].iter,\n+\t\t\t\t    &mi->subiters[i].rec);\n \t\tif (err < 0)\n \t\t\treturn err;\n \t\tif (err > 0) {\n-\t\t\treftable_iterator_destroy(&mi->stack[i]);\n-\t\t\treftable_record_release(&e.rec);\n+\t\t\treftable_iterator_destroy(&mi->subiters[i].iter);\n+\t\t\treftable_record_release(&mi->subiters[i].rec);\n \t\t\tcontinue;\n \t\t}\n \n@@ -56,9 +63,11 @@ static void merged_iter_close(void *p)\n \tstruct merged_iter *mi = p;\n \n \tmerged_iter_pqueue_release(&mi->pq);\n-\tfor (size_t i = 0; i < mi->stack_len; i++)\n-\t\treftable_iterator_destroy(&mi->stack[i]);\n-\treftable_free(mi->stack);\n+\tfor (size_t i = 0; i < mi->stack_len; i++) {\n+\t\treftable_iterator_destroy(&mi->subiters[i].iter);\n+\t\treftable_record_release(&mi->subiters[i].rec);\n+\t}\n+\treftable_free(mi->subiters);\n }\n \n static int merged_iter_advance_nonnull_subiter(struct merged_iter *mi,\n@@ -66,17 +75,16 @@ static int merged_iter_advance_nonnull_subiter(struct merged_iter *mi,\n {\n \tstruct pq_entry e = {\n \t\t.index = idx,\n+\t\t.rec = &mi->subiters[idx].rec,\n \t};\n \tint err;\n \n-\treftable_record_init(&e.rec, mi->typ);\n-\terr = iterator_next(&mi->stack[idx], &e.rec);\n+\terr = iterator_next(&mi->subiters[idx].iter, &mi->subiters[idx].rec);\n \tif (err < 0)\n \t\treturn err;\n-\n \tif (err > 0) {\n-\t\treftable_iterator_destroy(&mi->stack[idx]);\n-\t\treftable_record_release(&e.rec);\n+\t\treftable_iterator_destroy(&mi->subiters[idx].iter);\n+\t\treftable_record_release(&mi->subiters[idx].rec);\n \t\treturn 0;\n \t}\n \n@@ -86,7 +94,7 @@ static int merged_iter_advance_nonnull_subiter(struct merged_iter *mi,\n \n static int merged_iter_advance_subiter(struct merged_iter *mi, size_t idx)\n {\n-\tif (iterator_is_null(&mi->stack[idx]))\n+\tif (iterator_is_null(&mi->subiters[idx].iter))\n \t\treturn 0;\n \treturn merged_iter_advance_nonnull_subiter(mi, idx);\n }\n@@ -121,25 +129,19 @@ 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\tcmp = reftable_record_cmp(&top.rec, &entry.rec);\n+\t\tcmp = reftable_record_cmp(top.rec, entry.rec);\n \t\tif (cmp > 0)\n \t\t\tbreak;\n \n \t\tmerged_iter_pqueue_remove(&mi->pq);\n \t\terr = merged_iter_advance_subiter(mi, top.index);\n \t\tif (err < 0)\n-\t\t\tgoto done;\n-\t\treftable_record_release(&top.rec);\n+\t\t\treturn err;\n \t}\n \n-\treftable_record_release(rec);\n-\t*rec = entry.rec;\n \tmi->advance_index = entry.index;\n-\n-done:\n-\tif (err)\n-\t\treftable_record_release(&entry.rec);\n-\treturn err;\n+\tSWAP(*rec, *entry.rec);\n+\treturn 0;\n }\n \n static int merged_iter_next(struct merged_iter *mi, struct reftable_record *rec)\n@@ -257,10 +259,10 @@ static int merged_table_seek_record(struct reftable_merged_table *mt,\n \tstruct merged_iter *p;\n \tint err;\n \n-\tREFTABLE_CALLOC_ARRAY(merged.stack, mt->stack_len);\n+\tREFTABLE_CALLOC_ARRAY(merged.subiters, mt->stack_len);\n \tfor (size_t i = 0; i < mt->stack_len; i++) {\n \t\terr = reftable_table_seek_record(&mt->stack[i],\n-\t\t\t\t\t\t &merged.stack[merged.stack_len], rec);\n+\t\t\t\t\t\t &merged.subiters[merged.stack_len].iter, rec);\n \t\tif (err < 0)\n \t\t\tgoto out;\n \t\tif (!err)\ndiff --git a/reftable/pq.c b/reftable/pq.c\nindex e0ccce2b97..0074d6bc43 100644\n--- a/reftable/pq.c\n+++ b/reftable/pq.c\n@@ -14,7 +14,7 @@ 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-\tint cmp = reftable_record_cmp(&a->rec, &b->rec);\n+\tint cmp = reftable_record_cmp(a->rec, b->rec);\n \tif (cmp == 0)\n \t\treturn a->index > b->index;\n \treturn cmp < 0;\n@@ -82,10 +82,6 @@ void merged_iter_pqueue_add(struct merged_iter_pqueue *pq, const struct pq_entry\n \n void merged_iter_pqueue_release(struct merged_iter_pqueue *pq)\n {\n-\tint i = 0;\n-\tfor (i = 0; i < pq->len; i++) {\n-\t\treftable_record_release(&pq->heap[i].rec);\n-\t}\n \tFREE_AND_NULL(pq->heap);\n-\tpq->len = pq->cap = 0;\n+\tmemset(pq, 0, sizeof(*pq));\n }\ndiff --git a/reftable/pq.h b/reftable/pq.h\nindex 9e25a43a36..ce23972c16 100644\n--- a/reftable/pq.h\n+++ b/reftable/pq.h\n@@ -13,7 +13,7 @@ license that can be found in the LICENSE file or at\n \n struct pq_entry {\n \tsize_t index;\n-\tstruct reftable_record rec;\n+\tstruct reftable_record *rec;\n };\n \n struct merged_iter_pqueue {\ndiff --git a/reftable/pq_test.c b/reftable/pq_test.c\nindex c202eff848..b7d3c80cc7 100644\n--- a/reftable/pq_test.c\n+++ b/reftable/pq_test.c\n@@ -27,48 +27,43 @@ void merged_iter_pqueue_check(struct merged_iter_pqueue pq)\n \n static void test_pq(void)\n {\n-\tchar *names[54] = { NULL };\n-\tint N = ARRAY_SIZE(names) - 1;\n-\n \tstruct merged_iter_pqueue pq = { NULL };\n+\tstruct reftable_record recs[54];\n+\tint N = ARRAY_SIZE(recs) - 1, i;\n \tchar *last = NULL;\n \n-\tint i = 0;\n \tfor (i = 0; i < N; i++) {\n-\t\tchar name[100];\n-\t\tsnprintf(name, sizeof(name), \"%02d\", i);\n-\t\tnames[i] = xstrdup(name);\n+\t\tstruct strbuf refname = STRBUF_INIT;\n+\t\tstrbuf_addf(&refname, \"%02d\", i);\n+\n+\t\treftable_record_init(&recs[i], BLOCK_TYPE_REF);\n+\t\trecs[i].u.ref.refname = strbuf_detach(&refname, NULL);\n \t}\n \n \ti = 1;\n \tdo {\n-\t\tstruct pq_entry e = { .rec = { .type = BLOCK_TYPE_REF,\n-\t\t\t\t\t       .u.ref = {\n-\t\t\t\t\t\t       .refname = names[i],\n-\t\t\t\t\t       } } };\n+\t\tstruct pq_entry e = {\n+\t\t\t.rec = &recs[i],\n+\t\t};\n+\n \t\tmerged_iter_pqueue_add(&pq, &e);\n \t\tmerged_iter_pqueue_check(pq);\n+\n \t\ti = (i * 7) % N;\n \t} while (i != 1);\n \n \twhile (!merged_iter_pqueue_is_empty(pq)) {\n \t\tstruct pq_entry e = merged_iter_pqueue_remove(&pq);\n-\t\tstruct reftable_record *rec = &e.rec;\n \t\tmerged_iter_pqueue_check(pq);\n \n-\t\tEXPECT(reftable_record_type(rec) == BLOCK_TYPE_REF);\n-\t\tif (last) {\n-\t\t\tEXPECT(strcmp(last, rec->u.ref.refname) < 0);\n-\t\t}\n-\t\t/* this is names[i], so don't dealloc. */\n-\t\tlast = rec->u.ref.refname;\n-\t\trec->u.ref.refname = NULL;\n-\t\treftable_record_release(rec);\n-\t}\n-\tfor (i = 0; i < N; i++) {\n-\t\treftable_free(names[i]);\n+\t\tEXPECT(reftable_record_type(e.rec) == BLOCK_TYPE_REF);\n+\t\tif (last)\n+\t\t\tEXPECT(strcmp(last, e.rec->u.ref.refname) < 0);\n+\t\tlast = e.rec->u.ref.refname;\n \t}\n \n+\tfor (i = 0; i < N; i++)\n+\t\treftable_record_release(&recs[i]);\n \tmerged_iter_pqueue_release(&pq);\n }\n \n-- \n2.44.0\n\n"},{"id":"489524","messageId":"0adf34d08b781c384d878d7d5f651efcefa7d7ab.1709045927.git.ps@pks.im","threadId":"60913","inReplyTo":"cover.1709045927.git.ps@pks.im","subject":"[PATCH v2 05/13] reftable/merged: remove unnecessary null check for subiters","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-02-27T15:06:34Z","receivedAt":"2024-02-27T15:06:38Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"Whenever we advance a subiter we first call `iterator_is_null()`. This\nis not needed though because we only ever advance subiters which have\nentries in the priority queue, and we do not end entries to the priority\nqueue when the subiter has been exhausted.\n\nDrop the check as well as the now-unused function. This results in a\nsurprisingly big speedup:\n\n    Benchmark 1: show-ref: single matching ref (revision = HEAD~)\n      Time (mean ± σ):     138.1 ms ±   4.4 ms    [User: 135.1 ms, System: 2.8 ms]\n      Range (min … max):   133.4 ms … 167.3 ms    1000 runs\n\n    Benchmark 2: show-ref: single matching ref (revision = HEAD)\n      Time (mean ± σ):     134.4 ms ±   4.2 ms    [User: 131.5 ms, System: 2.8 ms]\n      Range (min … max):   130.0 ms … 164.0 ms    1000 runs\n\n    Summary\n      show-ref: single matching ref (revision = HEAD) ran\n        1.03 ± 0.05 times faster than show-ref: single matching ref (revision = HEAD~)\n\nSigned-off-by: Patrick Steinhardt <ps@pks.im>\n---\n reftable/iter.c   |  5 -----\n reftable/iter.h   |  4 ----\n reftable/merged.c | 10 +---------\n 3 files changed, 1 insertion(+), 18 deletions(-)\n\ndiff --git a/reftable/iter.c b/reftable/iter.c\nindex 8b5ebf6183..7aa30c4a51 100644\n--- a/reftable/iter.c\n+++ b/reftable/iter.c\n@@ -16,11 +16,6 @@ license that can be found in the LICENSE file or at\n #include \"reader.h\"\n #include \"reftable-error.h\"\n \n-int iterator_is_null(struct reftable_iterator *it)\n-{\n-\treturn !it->ops;\n-}\n-\n static void filtering_ref_iterator_close(void *iter_arg)\n {\n \tstruct filtering_ref_iterator *fri = iter_arg;\ndiff --git a/reftable/iter.h b/reftable/iter.h\nindex 47d67d84df..537431baba 100644\n--- a/reftable/iter.h\n+++ b/reftable/iter.h\n@@ -16,10 +16,6 @@ license that can be found in the LICENSE file or at\n #include \"reftable-iterator.h\"\n #include \"reftable-generic.h\"\n \n-/* Returns true for a zeroed out iterator, such as the one returned from\n- * iterator_destroy. */\n-int iterator_is_null(struct reftable_iterator *it);\n-\n /* iterator that produces only ref records that point to `oid` */\n struct filtering_ref_iterator {\n \tint double_check;\ndiff --git a/reftable/merged.c b/reftable/merged.c\nindex ae74234472..29ad09f3d8 100644\n--- a/reftable/merged.c\n+++ b/reftable/merged.c\n@@ -70,8 +70,7 @@ static void merged_iter_close(void *p)\n \treftable_free(mi->subiters);\n }\n \n-static int merged_iter_advance_nonnull_subiter(struct merged_iter *mi,\n-\t\t\t\t\t       size_t idx)\n+static int merged_iter_advance_subiter(struct merged_iter *mi, size_t idx)\n {\n \tstruct pq_entry e = {\n \t\t.index = idx,\n@@ -92,13 +91,6 @@ static int merged_iter_advance_nonnull_subiter(struct merged_iter *mi,\n \treturn 0;\n }\n \n-static int merged_iter_advance_subiter(struct merged_iter *mi, size_t idx)\n-{\n-\tif (iterator_is_null(&mi->subiters[idx].iter))\n-\t\treturn 0;\n-\treturn merged_iter_advance_nonnull_subiter(mi, idx);\n-}\n-\n static int merged_iter_next_entry(struct merged_iter *mi,\n \t\t\t\t  struct reftable_record *rec)\n {\n-- \n2.44.0\n\n"},{"id":"489525","messageId":"01152ce13072429f2047cc874b182c2938ab49fd.1709045927.git.ps@pks.im","threadId":"60913","inReplyTo":"cover.1709045927.git.ps@pks.im","subject":"[PATCH v2 06/13] reftable/merged: handle subiter cleanup on close only","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-02-27T15:06:38Z","receivedAt":"2024-02-27T15:06:42Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"When advancing one of the subiters fails we immediately release\nresources associated with that subiter. This is not necessary though as\nwe will release these resources when closing the merged iterator anyway.\n\nDrop the logic and only release resources when the merged iterator is\ndone. This is a mere cleanup that should help reduce the cognitive load\nwhen reading through the code.\n\nSigned-off-by: Patrick Steinhardt <ps@pks.im>\n---\n reftable/merged.c | 12 ++----------\n 1 file changed, 2 insertions(+), 10 deletions(-)\n\ndiff --git a/reftable/merged.c b/reftable/merged.c\nindex 29ad09f3d8..d9ed4a19dd 100644\n--- a/reftable/merged.c\n+++ b/reftable/merged.c\n@@ -46,11 +46,8 @@ static int merged_iter_init(struct merged_iter *mi)\n \t\t\t\t    &mi->subiters[i].rec);\n \t\tif (err < 0)\n \t\t\treturn err;\n-\t\tif (err > 0) {\n-\t\t\treftable_iterator_destroy(&mi->subiters[i].iter);\n-\t\t\treftable_record_release(&mi->subiters[i].rec);\n+\t\tif (err > 0)\n \t\t\tcontinue;\n-\t\t}\n \n \t\tmerged_iter_pqueue_add(&mi->pq, &e);\n \t}\n@@ -79,13 +76,8 @@ static int merged_iter_advance_subiter(struct merged_iter *mi, size_t idx)\n \tint err;\n \n \terr = iterator_next(&mi->subiters[idx].iter, &mi->subiters[idx].rec);\n-\tif (err < 0)\n+\tif (err)\n \t\treturn err;\n-\tif (err > 0) {\n-\t\treftable_iterator_destroy(&mi->subiters[idx].iter);\n-\t\treftable_record_release(&mi->subiters[idx].rec);\n-\t\treturn 0;\n-\t}\n \n \tmerged_iter_pqueue_add(&mi->pq, &e);\n \treturn 0;\n-- \n2.44.0\n\n"},{"id":"489526","messageId":"370b6cfc6cfe8a81684fe4d9c72138cb467fa268.1709045927.git.ps@pks.im","threadId":"60913","inReplyTo":"cover.1709045927.git.ps@pks.im","subject":"[PATCH v2 07/13] reftable/merged: circumvent pqueue with single subiter","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-02-27T15:06:42Z","receivedAt":"2024-02-27T15:06:46Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"The merged iterator uses a priority queue to order records so that we\ncan yielid them in the expected order. This priority queue of course\ncomes with some overhead as we need to add, compare and remove entries\nin that priority queue.\n\nIn the general case, that overhead cannot really be avoided. But when we\nhave a single subiter left then there is no need to use the priority\nqueue anymore because the order is exactly the same as what that subiter\nwould return.\n\nWhile having a single subiter may sound like an edge case, it happens\nmore frequently than one might think. In the most common scenario, you\ncan expect a repository to have a single large table that contains most\nof the records and then a set of smaller tables which contain later\nadditions to the reftable stack. In this case it is quite likely that we\nexhaust subiters of those smaller stacks before exhausting the large\ntable.\n\nSpecial-case this and return records directly from the remaining\nsubiter. This results in a sizeable speedup when iterating over 1m refs\nin a repository with a single table:\n\n  Benchmark 1: show-ref: single matching ref (revision = HEAD~)\n    Time (mean ± σ):     135.4 ms ±   4.4 ms    [User: 132.5 ms, System: 2.8 ms]\n    Range (min … max):   131.0 ms … 166.3 ms    1000 runs\n\n  Benchmark 2: show-ref: single matching ref (revision = HEAD)\n    Time (mean ± σ):     126.3 ms ±   3.9 ms    [User: 123.3 ms, System: 2.8 ms]\n    Range (min … max):   122.7 ms … 157.0 ms    1000 runs\n\n  Summary\n    show-ref: single matching ref (revision = HEAD) ran\n      1.07 ± 0.05 times faster than show-ref: single matching ref (revision = HEAD~)\n\nSigned-off-by: Patrick Steinhardt <ps@pks.im>\n---\n reftable/merged.c | 24 ++++++++++++++++++++++--\n 1 file changed, 22 insertions(+), 2 deletions(-)\n\ndiff --git a/reftable/merged.c b/reftable/merged.c\nindex d9ed4a19dd..29161a32cf 100644\n--- a/reftable/merged.c\n+++ b/reftable/merged.c\n@@ -87,16 +87,36 @@ static int merged_iter_next_entry(struct merged_iter *mi,\n \t\t\t\t  struct reftable_record *rec)\n {\n \tstruct pq_entry entry = { 0 };\n-\tint err = 0;\n+\tint err = 0, empty;\n+\n+\tempty = merged_iter_pqueue_is_empty(mi->pq);\n \n \tif (mi->advance_index >= 0) {\n+\t\t/*\n+\t\t * When there are no pqueue entries then we only have a single\n+\t\t * subiter left. There is no need to use the pqueue in that\n+\t\t * case anymore as we know that the subiter will return entries\n+\t\t * in the correct order already.\n+\t\t *\n+\t\t * While this may sound like a very specific edge case, it may\n+\t\t * happen more frequently than you think. Most repositories\n+\t\t * will end up having a single large base table that contains\n+\t\t * most of the refs. It's thus likely that we exhaust all\n+\t\t * subiters but the one from that base ref.\n+\t\t */\n+\t\tif (empty)\n+\t\t\treturn iterator_next(&mi->subiters[mi->advance_index].iter,\n+\t\t\t\t\t     rec);\n+\n \t\terr = merged_iter_advance_subiter(mi, mi->advance_index);\n \t\tif (err < 0)\n \t\t\treturn err;\n+\t\tif (!err)\n+\t\t\tempty = 0;\n \t\tmi->advance_index = -1;\n \t}\n \n-\tif (merged_iter_pqueue_is_empty(mi->pq))\n+\tif (empty)\n \t\treturn 1;\n \n \tentry = merged_iter_pqueue_remove(&mi->pq);\n-- \n2.44.0\n\n"},{"id":"489527","messageId":"1e279f21e6b79d8628d5407881cee0d5032d7297.1709045927.git.ps@pks.im","threadId":"60913","inReplyTo":"cover.1709045927.git.ps@pks.im","subject":"[PATCH v2 08/13] reftable/merged: avoid duplicate pqueue emptiness check","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-02-27T15:06:46Z","receivedAt":"2024-02-27T15:06:50Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"When calling `merged_iter_next_void()` we first check whether the iter\nhas been exhausted already. We already perform this check two levels\ndown the stack in `merged_iter_next_entry()` though, which makes this\ncheck redundant.\n\nNow if this check was there to accellerate the common case it might have\nmade sense to keep it. But the iterator being exhausted is rather the\nuncommon case because you can expect most reftable stacks to contain\nmore than two refs.\n\nSimplify the code by removing the check. As `merged_iter_next_void()` is\nbasically empty except for calling `merged_iter_next()` now, merge these\ntwo functions. This also results in a tiny speedup when iterating over\nmany refs:\n\n    Benchmark 1: show-ref: single matching ref (revision = HEAD~)\n      Time (mean ± σ):     125.6 ms ±   3.8 ms    [User: 122.7 ms, System: 2.8 ms]\n      Range (min … max):   122.4 ms … 153.4 ms    1000 runs\n\n    Benchmark 2: show-ref: single matching ref (revision = HEAD)\n      Time (mean ± σ):     124.0 ms ±   3.9 ms    [User: 121.1 ms, System: 2.8 ms]\n      Range (min … max):   120.1 ms … 156.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\nSigned-off-by: Patrick Steinhardt <ps@pks.im>\n---\n reftable/merged.c | 20 ++++++--------------\n 1 file changed, 6 insertions(+), 14 deletions(-)\n\ndiff --git a/reftable/merged.c b/reftable/merged.c\nindex 29161a32cf..f85a24c678 100644\n--- a/reftable/merged.c\n+++ b/reftable/merged.c\n@@ -148,27 +148,19 @@ static int merged_iter_next_entry(struct merged_iter *mi,\n \treturn 0;\n }\n \n-static int merged_iter_next(struct merged_iter *mi, struct reftable_record *rec)\n+static int merged_iter_next_void(void *p, struct reftable_record *rec)\n {\n+\tstruct merged_iter *mi = p;\n \twhile (1) {\n \t\tint err = merged_iter_next_entry(mi, rec);\n-\t\tif (err == 0 && mi->suppress_deletions &&\n-\t\t    reftable_record_is_deletion(rec)) {\n+\t\tif (err)\n+\t\t\treturn err;\n+\t\tif (mi->suppress_deletions && reftable_record_is_deletion(rec))\n \t\t\tcontinue;\n-\t\t}\n-\n-\t\treturn err;\n+\t\treturn 0;\n \t}\n }\n \n-static int merged_iter_next_void(void *p, struct reftable_record *rec)\n-{\n-\tstruct merged_iter *mi = p;\n-\tif (merged_iter_pqueue_is_empty(mi->pq) && mi->advance_index < 0)\n-\t\treturn 1;\n-\treturn merged_iter_next(mi, rec);\n-}\n-\n static struct reftable_iterator_vtable merged_iter_vtable = {\n \t.next = &merged_iter_next_void,\n \t.close = &merged_iter_close,\n-- \n2.44.0\n\n"},{"id":"489528","messageId":"15a8cbf6782653f4d57ef351e2d7894835813d88.1709045927.git.ps@pks.im","threadId":"60913","inReplyTo":"cover.1709045927.git.ps@pks.im","subject":"[PATCH v2 09/13] reftable/record: reuse refname when decoding","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-02-27T15:06:50Z","receivedAt":"2024-02-27T15:06:54Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"When decoding a reftable record we will first release the user-provided\nrecord and then decode the new record into it. This is quite inefficient\nas we basically need to reallocate at least the refname every time.\n\nRefactor the function to start tracking the refname capacity. Like this,\nwe can stow away the refname, release, restore and then grow the refname\nto the required number of bytes via `REFTABLE_ALLOC_GROW()`.\n\nThis refactoring is safe to do because all functions that assigning to\nthe refname will first call `release_reftable_record()`, which will zero\nout the complete record after releasing memory.\n\nThis change results in a nice speedup when iterating over 1 million\nrefs:\n\n  Benchmark 1: show-ref: single matching ref (revision = HEAD~)\n\n    Time (mean ± σ):     124.0 ms ±   3.9 ms    [User: 121.1 ms, System: 2.7 ms]\n    Range (min … max):   120.4 ms … 152.7 ms    1000 runs\n\n  Benchmark 2: show-ref: single matching ref (revision = HEAD)\n    Time (mean ± σ):     114.4 ms ±   3.7 ms    [User: 111.5 ms, System: 2.7 ms]\n    Range (min … max):   111.0 ms … 152.1 ms    1000 runs\n\n  Summary\n    show-ref: single matching ref (revision = HEAD) ran\n      1.08 ± 0.05 times faster than show-ref: single matching ref (revision = HEAD~)\n\nFurthermore, with this change we now perform a mostly constant number of\nallocations when iterating. Before this change:\n\n  HEAP SUMMARY:\n      in use at exit: 13,603 bytes in 125 blocks\n    total heap usage: 1,006,620 allocs, 1,006,495 frees, 25,398,363 bytes allocated\n\nAfter this change:\n\n  HEAP SUMMARY:\n      in use at exit: 13,603 bytes in 125 blocks\n    total heap usage: 6,623 allocs, 6,498 frees, 509,592 bytes allocated\n\nSigned-off-by: Patrick Steinhardt <ps@pks.im>\n---\n reftable/record.c          | 16 ++++++++++++----\n reftable/reftable-record.h |  1 +\n 2 files changed, 13 insertions(+), 4 deletions(-)\n\ndiff --git a/reftable/record.c b/reftable/record.c\nindex d6bb42e887..e800cfef00 100644\n--- a/reftable/record.c\n+++ b/reftable/record.c\n@@ -368,16 +368,24 @@ static int reftable_ref_record_decode(void *rec, struct strbuf key,\n \tstruct reftable_ref_record *r = rec;\n \tstruct string_view start = in;\n \tuint64_t update_index = 0;\n-\tint n = get_var_int(&update_index, &in);\n+\tconst char *refname = NULL;\n+\tsize_t refname_cap = 0;\n+\tint n;\n+\n+\tassert(hash_size > 0);\n+\n+\tn = get_var_int(&update_index, &in);\n \tif (n < 0)\n \t\treturn n;\n \tstring_view_consume(&in, n);\n \n+\tSWAP(refname, r->refname);\n+\tSWAP(refname_cap, r->refname_cap);\n \treftable_ref_record_release(r);\n+\tSWAP(refname, r->refname);\n+\tSWAP(refname_cap, r->refname_cap);\n \n-\tassert(hash_size > 0);\n-\n-\tr->refname = reftable_malloc(key.len + 1);\n+\tREFTABLE_ALLOC_GROW(r->refname, key.len + 1, r->refname_cap);\n \tmemcpy(r->refname, key.buf, key.len);\n \tr->refname[key.len] = 0;\n \ndiff --git a/reftable/reftable-record.h b/reftable/reftable-record.h\nindex bb6e99acd3..e657001d42 100644\n--- a/reftable/reftable-record.h\n+++ b/reftable/reftable-record.h\n@@ -22,6 +22,7 @@ license that can be found in the LICENSE file or at\n /* reftable_ref_record holds a ref database entry target_value */\n struct reftable_ref_record {\n \tchar *refname; /* Name of the ref, malloced. */\n+\tsize_t refname_cap;\n \tuint64_t update_index; /* Logical timestamp at which this value is\n \t\t\t\t* written */\n \n-- \n2.44.0\n\n"},{"id":"489529","messageId":"35b1af2f0612e51bc0cf87afe9c44197b2b8ccaf.1709045927.git.ps@pks.im","threadId":"60913","inReplyTo":"cover.1709045927.git.ps@pks.im","subject":"[PATCH v2 10/13] reftable/record: reuse refname when copying","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-02-27T15:06:55Z","receivedAt":"2024-02-27T15:06:58Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"Do the same optimization as in the preceding commit, but this time for\n`reftable_record_copy()`. While not as noticeable, it still results in a\nsmall speedup when iterating over 1 million refs:\n\n  Benchmark 1: show-ref: single matching ref (revision = HEAD~)\n    Time (mean ± σ):     114.0 ms ±   3.8 ms    [User: 111.1 ms, System: 2.7 ms]\n    Range (min … max):   110.9 ms … 144.3 ms    1000 runs\n\n  Benchmark 2: show-ref: single matching ref (revision = HEAD)\n    Time (mean ± σ):     112.5 ms ±   3.7 ms    [User: 109.5 ms, System: 2.8 ms]\n    Range (min … max):   109.2 ms … 140.7 ms    1000 runs\n\n  Summary\n    show-ref: single matching ref (revision = HEAD) ran\n      1.01 ± 0.05 times faster than show-ref: single matching ref (revision = HEAD~)\n\nSigned-off-by: Patrick Steinhardt <ps@pks.im>\n---\n reftable/record.c | 18 +++++++++++++++---\n 1 file changed, 15 insertions(+), 3 deletions(-)\n\ndiff --git a/reftable/record.c b/reftable/record.c\nindex e800cfef00..3f2a639036 100644\n--- a/reftable/record.c\n+++ b/reftable/record.c\n@@ -205,14 +205,26 @@ static void reftable_ref_record_copy_from(void *rec, const void *src_rec,\n {\n \tstruct reftable_ref_record *ref = rec;\n \tconst struct reftable_ref_record *src = src_rec;\n+\tchar *refname = NULL;\n+\tsize_t refname_cap = 0;\n+\n \tassert(hash_size > 0);\n \n-\t/* This is simple and correct, but we could probably reuse the hash\n-\t * fields. */\n+\tSWAP(refname, ref->refname);\n+\tSWAP(refname_cap, ref->refname_cap);\n \treftable_ref_record_release(ref);\n+\tSWAP(refname, ref->refname);\n+\tSWAP(refname_cap, ref->refname_cap);\n+\n \tif (src->refname) {\n-\t\tref->refname = xstrdup(src->refname);\n+\t\tsize_t refname_len = strlen(src->refname);\n+\n+\t\tREFTABLE_ALLOC_GROW(ref->refname, refname_len + 1,\n+\t\t\t\t    ref->refname_cap);\n+\t\tmemcpy(ref->refname, src->refname, refname_len);\n+\t\tref->refname[refname_len] = 0;\n \t}\n+\n \tref->update_index = src->update_index;\n \tref->value_type = src->value_type;\n \tswitch (src->value_type) {\n-- \n2.44.0\n\n"},{"id":"489530","messageId":"d7151ef361c8433aff8c1d6e0729efeb487e3878.1709045927.git.ps@pks.im","threadId":"60913","inReplyTo":"cover.1709045927.git.ps@pks.im","subject":"[PATCH v2 11/13] reftable/record: decode keys in place","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-02-27T15:06:59Z","receivedAt":"2024-02-27T15:07:02Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"When reading a record from a block, we need to decode the record's key.\nAs reftable keys are prefix-compressed, meaning they reuse a prefix from\nthe preceding record's key, this is a bit more involved than just having\nto copy the relevant bytes: we need to figure out the prefix and suffix\nlengths, copy the prefix from the preceding record and finally copy the\nsuffix from the current record.\n\nThis is done by passing three buffers to `reftable_decode_key()`: one\nbuffer that holds the result, one buffer that holds the last key, and\none buffer that points to the current record. The final key is then\nassembled by calling `strbuf_add()` twice to copy over the prefix and\nsuffix.\n\nPerforming two memory copies is inefficient though. And we can indeed do\nbetter by decoding keys in place. Instead of providing two buffers, the\ncaller may only call a single buffer that is already pre-populated with\nthe last key. Like this, we only have to call `strbuf_setlen()` to trim\nthe record to its prefix and then `strbuf_add()` to add the suffix.\n\nThis refactoring leads to a noticeable performance bump when iterating\nover 1 million refs:\n\n  Benchmark 1: show-ref: single matching ref (revision = HEAD~)\n    Time (mean ± σ):     112.2 ms ±   3.9 ms    [User: 109.3 ms, System: 2.8 ms]\n    Range (min … max):   109.2 ms … 149.6 ms    1000 runs\n\n  Benchmark 2: show-ref: single matching ref (revision = HEAD)\n    Time (mean ± σ):     106.0 ms ±   3.5 ms    [User: 103.2 ms, System: 2.7 ms]\n    Range (min … max):   103.2 ms … 133.7 ms    1000 runs\n\n  Summary\n    show-ref: single matching ref (revision = HEAD) ran\n      1.06 ± 0.05 times faster than show-ref: single matching ref (revision = HEAD~)\n\nSigned-off-by: Patrick Steinhardt <ps@pks.im>\n---\n reftable/block.c       | 25 +++++++++++--------------\n reftable/block.h       |  2 --\n reftable/record.c      | 19 +++++++++----------\n reftable/record.h      |  9 ++++++---\n reftable/record_test.c |  3 ++-\n 5 files changed, 28 insertions(+), 30 deletions(-)\n\ndiff --git a/reftable/block.c b/reftable/block.c\nindex 72eb73b380..ad9074dba6 100644\n--- a/reftable/block.c\n+++ b/reftable/block.c\n@@ -291,9 +291,8 @@ static int restart_key_less(size_t idx, void *args)\n \t/* the restart key is verbatim in the block, so this could avoid the\n \t   alloc for decoding the key */\n \tstruct strbuf rkey = STRBUF_INIT;\n-\tstruct strbuf last_key = STRBUF_INIT;\n \tuint8_t unused_extra;\n-\tint n = reftable_decode_key(&rkey, &unused_extra, last_key, in);\n+\tint n = reftable_decode_key(&rkey, &unused_extra, in);\n \tint result;\n \tif (n < 0) {\n \t\ta->error = 1;\n@@ -326,35 +325,34 @@ int block_iter_next(struct block_iter *it, struct reftable_record *rec)\n \tif (it->next_off >= it->br->block_len)\n \t\treturn 1;\n \n-\tn = reftable_decode_key(&it->key, &extra, it->last_key, in);\n+\tn = reftable_decode_key(&it->last_key, &extra, in);\n \tif (n < 0)\n \t\treturn -1;\n-\n-\tif (!it->key.len)\n+\tif (!it->last_key.len)\n \t\treturn REFTABLE_FORMAT_ERROR;\n \n \tstring_view_consume(&in, n);\n-\tn = reftable_record_decode(rec, it->key, extra, in, it->br->hash_size);\n+\tn = reftable_record_decode(rec, it->last_key, extra, in, it->br->hash_size);\n \tif (n < 0)\n \t\treturn -1;\n \tstring_view_consume(&in, n);\n \n-\tstrbuf_swap(&it->last_key, &it->key);\n \tit->next_off += start.len - in.len;\n \treturn 0;\n }\n \n int block_reader_first_key(struct block_reader *br, struct strbuf *key)\n {\n-\tstruct strbuf empty = STRBUF_INIT;\n-\tint off = br->header_off + 4;\n+\tint off = br->header_off + 4, n;\n \tstruct string_view in = {\n \t\t.buf = br->block.data + off,\n \t\t.len = br->block_len - off,\n \t};\n-\n \tuint8_t extra = 0;\n-\tint n = reftable_decode_key(key, &extra, empty, in);\n+\n+\tstrbuf_reset(key);\n+\n+\tn = reftable_decode_key(key, &extra, in);\n \tif (n < 0)\n \t\treturn n;\n \tif (!key->len)\n@@ -371,7 +369,6 @@ int block_iter_seek(struct block_iter *it, struct strbuf *want)\n void block_iter_close(struct block_iter *it)\n {\n \tstrbuf_release(&it->last_key);\n-\tstrbuf_release(&it->key);\n }\n \n int block_reader_seek(struct block_reader *br, struct block_iter *it,\n@@ -408,8 +405,8 @@ int block_reader_seek(struct block_reader *br, struct block_iter *it,\n \t\tif (err < 0)\n \t\t\tgoto done;\n \n-\t\treftable_record_key(&rec, &it->key);\n-\t\tif (err > 0 || strbuf_cmp(&it->key, want) >= 0) {\n+\t\treftable_record_key(&rec, &it->last_key);\n+\t\tif (err > 0 || strbuf_cmp(&it->last_key, want) >= 0) {\n \t\t\terr = 0;\n \t\t\tgoto done;\n \t\t}\ndiff --git a/reftable/block.h b/reftable/block.h\nindex 17481e6331..51699af233 100644\n--- a/reftable/block.h\n+++ b/reftable/block.h\n@@ -84,12 +84,10 @@ struct block_iter {\n \n \t/* key for last entry we read. */\n \tstruct strbuf last_key;\n-\tstruct strbuf key;\n };\n \n #define BLOCK_ITER_INIT { \\\n \t.last_key = STRBUF_INIT, \\\n-\t.key = STRBUF_INIT, \\\n }\n \n /* initializes a block reader. */\ndiff --git a/reftable/record.c b/reftable/record.c\nindex 3f2a639036..37682cc7d0 100644\n--- a/reftable/record.c\n+++ b/reftable/record.c\n@@ -159,20 +159,19 @@ int reftable_encode_key(int *restart, struct string_view dest,\n \treturn start.len - dest.len;\n }\n \n-int reftable_decode_key(struct strbuf *key, uint8_t *extra,\n-\t\t\tstruct strbuf last_key, struct string_view in)\n+int reftable_decode_key(struct strbuf *last_key, uint8_t *extra,\n+\t\t\tstruct string_view in)\n {\n \tint start_len = in.len;\n \tuint64_t prefix_len = 0;\n \tuint64_t suffix_len = 0;\n-\tint n = get_var_int(&prefix_len, &in);\n+\tint n;\n+\n+\tn = get_var_int(&prefix_len, &in);\n \tif (n < 0)\n \t\treturn -1;\n \tstring_view_consume(&in, n);\n \n-\tif (prefix_len > last_key.len)\n-\t\treturn -1;\n-\n \tn = get_var_int(&suffix_len, &in);\n \tif (n <= 0)\n \t\treturn -1;\n@@ -181,12 +180,12 @@ int reftable_decode_key(struct strbuf *key, uint8_t *extra,\n \t*extra = (uint8_t)(suffix_len & 0x7);\n \tsuffix_len >>= 3;\n \n-\tif (in.len < suffix_len)\n+\tif (in.len < suffix_len ||\n+\t    prefix_len > last_key->len)\n \t\treturn -1;\n \n-\tstrbuf_reset(key);\n-\tstrbuf_add(key, last_key.buf, prefix_len);\n-\tstrbuf_add(key, in.buf, suffix_len);\n+\tstrbuf_setlen(last_key, prefix_len);\n+\tstrbuf_add(last_key, in.buf, suffix_len);\n \tstring_view_consume(&in, suffix_len);\n \n \treturn start_len - in.len;\ndiff --git a/reftable/record.h b/reftable/record.h\nindex a05e2be179..91c9c6ebfd 100644\n--- a/reftable/record.h\n+++ b/reftable/record.h\n@@ -81,9 +81,12 @@ int reftable_encode_key(int *is_restart, struct string_view dest,\n \t\t\tstruct strbuf prev_key, struct strbuf key,\n \t\t\tuint8_t extra);\n \n-/* Decode into `key` and `extra` from `in` */\n-int reftable_decode_key(struct strbuf *key, uint8_t *extra,\n-\t\t\tstruct strbuf last_key, struct string_view in);\n+/*\n+ * Decode into `last_key` and `extra` from `in`. `last_key` is expected to\n+ * contain the decoded key of the preceding record, if any.\n+ */\n+int reftable_decode_key(struct strbuf *last_key, uint8_t *extra,\n+\t\t\tstruct string_view in);\n \n /* reftable_index_record are used internally to speed up lookups. */\n struct reftable_index_record {\ndiff --git a/reftable/record_test.c b/reftable/record_test.c\nindex a86cff5526..89209894d8 100644\n--- a/reftable/record_test.c\n+++ b/reftable/record_test.c\n@@ -295,7 +295,8 @@ static void test_key_roundtrip(void)\n \tEXPECT(!restart);\n \tEXPECT(n > 0);\n \n-\tm = reftable_decode_key(&roundtrip, &rt_extra, last_key, dest);\n+\tstrbuf_addstr(&roundtrip, \"refs/heads/master\");\n+\tm = reftable_decode_key(&roundtrip, &rt_extra, dest);\n \tEXPECT(n == m);\n \tEXPECT(0 == strbuf_cmp(&key, &roundtrip));\n \tEXPECT(rt_extra == extra);\n-- \n2.44.0\n\n"},{"id":"489531","messageId":"99b238a40da1837013c45112aa5dea38bba54df9.1709045927.git.ps@pks.im","threadId":"60913","inReplyTo":"cover.1709045927.git.ps@pks.im","subject":"[PATCH v2 12/13] reftable: allow inlining of a few functions","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-02-27T15:07:03Z","receivedAt":"2024-02-27T15:07:07Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"We have a few functions which are basically just accessors to\nstructures. As those functions are executed inside the hot loop when\niterating through many refs, the fact that they cannot be inlined is\ncosting us some performance.\n\nMove the function definitions into their respective headers so that they\ncan be inlined. This results in a performance improvement when iterating\nover 1 million refs:\n\n    Benchmark 1: show-ref: single matching ref (revision = HEAD~)\n      Time (mean ± σ):     105.9 ms ±   3.6 ms    [User: 103.0 ms, System: 2.8 ms]\n      Range (min … max):   103.1 ms … 133.4 ms    1000 runs\n\n    Benchmark 2: show-ref: single matching ref (revision = HEAD)\n      Time (mean ± σ):     100.7 ms ±   3.4 ms    [User: 97.8 ms, System: 2.8 ms]\n      Range (min … max):    97.8 ms … 124.0 ms    1000 runs\n\n    Summary\n      show-ref: single matching ref (revision = HEAD) ran\n        1.05 ± 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     | 10 ----------\n reftable/pq.h     | 12 ++++++++++--\n reftable/record.c | 11 -----------\n reftable/record.h | 12 ++++++++++--\n 4 files changed, 20 insertions(+), 25 deletions(-)\n\ndiff --git a/reftable/pq.c b/reftable/pq.c\nindex 0074d6bc43..7fb45d8c60 100644\n--- a/reftable/pq.c\n+++ b/reftable/pq.c\n@@ -20,16 +20,6 @@ int pq_less(struct pq_entry *a, struct pq_entry *b)\n \treturn cmp < 0;\n }\n \n-struct pq_entry merged_iter_pqueue_top(struct merged_iter_pqueue pq)\n-{\n-\treturn pq.heap[0];\n-}\n-\n-int merged_iter_pqueue_is_empty(struct merged_iter_pqueue pq)\n-{\n-\treturn pq.len == 0;\n-}\n-\n struct pq_entry merged_iter_pqueue_remove(struct merged_iter_pqueue *pq)\n {\n \tint i = 0;\ndiff --git a/reftable/pq.h b/reftable/pq.h\nindex ce23972c16..f796c23179 100644\n--- a/reftable/pq.h\n+++ b/reftable/pq.h\n@@ -22,12 +22,20 @@ struct merged_iter_pqueue {\n \tsize_t cap;\n };\n \n-struct pq_entry merged_iter_pqueue_top(struct merged_iter_pqueue pq);\n-int merged_iter_pqueue_is_empty(struct merged_iter_pqueue pq);\n void merged_iter_pqueue_check(struct merged_iter_pqueue pq);\n struct pq_entry merged_iter_pqueue_remove(struct merged_iter_pqueue *pq);\n void merged_iter_pqueue_add(struct merged_iter_pqueue *pq, const struct pq_entry *e);\n void merged_iter_pqueue_release(struct merged_iter_pqueue *pq);\n int pq_less(struct pq_entry *a, struct pq_entry *b);\n \n+static inline struct pq_entry merged_iter_pqueue_top(struct merged_iter_pqueue pq)\n+{\n+\treturn pq.heap[0];\n+}\n+\n+static inline int merged_iter_pqueue_is_empty(struct merged_iter_pqueue pq)\n+{\n+\treturn pq.len == 0;\n+}\n+\n #endif\ndiff --git a/reftable/record.c b/reftable/record.c\nindex 37682cc7d0..fdda28645c 100644\n--- a/reftable/record.c\n+++ b/reftable/record.c\n@@ -1176,11 +1176,6 @@ void reftable_record_key(struct reftable_record *rec, struct strbuf *dest)\n \treftable_record_vtable(rec)->key(reftable_record_data(rec), dest);\n }\n \n-uint8_t reftable_record_type(struct reftable_record *rec)\n-{\n-\treturn rec->type;\n-}\n-\n int reftable_record_encode(struct reftable_record *rec, struct string_view dest,\n \t\t\t   int hash_size)\n {\n@@ -1302,12 +1297,6 @@ int reftable_log_record_is_deletion(const struct reftable_log_record *log)\n \treturn (log->value_type == REFTABLE_LOG_DELETION);\n }\n \n-void string_view_consume(struct string_view *s, int n)\n-{\n-\ts->buf += n;\n-\ts->len -= n;\n-}\n-\n static void *reftable_record_data(struct reftable_record *rec)\n {\n \tswitch (rec->type) {\ndiff --git a/reftable/record.h b/reftable/record.h\nindex 91c9c6ebfd..5e8304e052 100644\n--- a/reftable/record.h\n+++ b/reftable/record.h\n@@ -25,7 +25,11 @@ struct string_view {\n };\n \n /* Advance `s.buf` by `n`, and decrease length. */\n-void string_view_consume(struct string_view *s, int n);\n+static inline void string_view_consume(struct string_view *s, int n)\n+{\n+\ts->buf += n;\n+\ts->len -= n;\n+}\n \n /* utilities for de/encoding varints */\n \n@@ -127,7 +131,6 @@ 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-uint8_t reftable_record_type(struct reftable_record *rec);\n void reftable_record_copy_from(struct reftable_record *rec,\n \t\t\t       struct reftable_record *src, int hash_size);\n uint8_t reftable_record_val_type(struct reftable_record *rec);\n@@ -138,6 +141,11 @@ int reftable_record_decode(struct reftable_record *rec, struct strbuf key,\n \t\t\t   int hash_size);\n int reftable_record_is_deletion(struct reftable_record *rec);\n \n+static inline uint8_t reftable_record_type(struct reftable_record *rec)\n+{\n+\treturn rec->type;\n+}\n+\n /* frees and zeroes out the embedded record */\n void reftable_record_release(struct reftable_record *rec);\n \n-- \n2.44.0\n\n"},{"id":"489532","messageId":"627bd1f5f784a2a34d7dabf95c3adf279c3a81a9.1709045927.git.ps@pks.im","threadId":"60913","inReplyTo":"cover.1709045927.git.ps@pks.im","subject":"[PATCH v2 13/13] refs/reftable: precompute prefix length","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-02-27T15:07:07Z","receivedAt":"2024-02-27T15:07:11Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"We're recomputing the prefix length on every iteration of the ref\niterator. Precompute it for another speedup when iterating over 1\nmillion refs:\n\n    Benchmark 1: show-ref: single matching ref (revision = HEAD~)\n      Time (mean ± σ):     100.3 ms ±   3.7 ms    [User: 97.3 ms, System: 2.8 ms]\n      Range (min … max):    97.5 ms … 139.7 ms    1000 runs\n\n    Benchmark 2: show-ref: single matching ref (revision = HEAD)\n      Time (mean ± σ):      95.8 ms ±   3.4 ms    [User: 92.9 ms, System: 2.8 ms]\n      Range (min … max):    93.0 ms … 121.9 ms    1000 runs\n\n    Summary\n      show-ref: single matching ref (revision = HEAD) ran\n        1.05 ± 0.05 times faster than show-ref: single matching ref (revision = HEAD~)\n\nSigned-off-by: Patrick Steinhardt <ps@pks.im>\n---\n refs/reftable-backend.c | 6 ++++--\n 1 file changed, 4 insertions(+), 2 deletions(-)\n\ndiff --git a/refs/reftable-backend.c b/refs/reftable-backend.c\nindex a14f2ad7f4..4d27fdde54 100644\n--- a/refs/reftable-backend.c\n+++ b/refs/reftable-backend.c\n@@ -346,6 +346,7 @@ struct reftable_ref_iterator {\n \tstruct object_id oid;\n \n \tconst char *prefix;\n+\tsize_t prefix_len;\n \tunsigned int flags;\n \tint err;\n };\n@@ -371,8 +372,8 @@ static int reftable_ref_iterator_advance(struct ref_iterator *ref_iterator)\n \t\tif (!starts_with(iter->ref.refname, \"refs/\"))\n \t\t\tcontinue;\n \n-\t\tif (iter->prefix &&\n-\t\t    strncmp(iter->prefix, iter->ref.refname, strlen(iter->prefix))) {\n+\t\tif (iter->prefix_len &&\n+\t\t    strncmp(iter->prefix, iter->ref.refname, iter->prefix_len)) {\n \t\t\titer->err = 1;\n \t\t\tbreak;\n \t\t}\n@@ -481,6 +482,7 @@ static struct reftable_ref_iterator *ref_iterator_for_stack(struct reftable_ref_\n \titer = xcalloc(1, sizeof(*iter));\n \tbase_ref_iterator_init(&iter->base, &reftable_ref_iterator_vtable, 1);\n \titer->prefix = prefix;\n+\titer->prefix_len = prefix ? strlen(prefix) : 0;\n \titer->base.oid = &iter->oid;\n \titer->flags = flags;\n \titer->refs = refs;\n-- \n2.44.0\n\n"},{"id":"489544","messageId":"Zd4Ss37Yl4d-oEzE@ncase","threadId":"60913","inReplyTo":"qprofop624nevbicid4rplfqlanfrujyxiilfqwchrppnmw7u4@3dvw5udjtrah","subject":"Re: [PATCH 02/12] reftable/merged: make `merged_iter` structure private","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-02-27T16:49:55Z","receivedAt":"2024-02-27T16:50:00Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"On Tue, Feb 20, 2024 at 12:15:23PM -0600, Justin Tobler wrote:\n> On 24/02/14 08:45AM, Patrick Steinhardt wrote:\n> > The `merged_iter` structure is not used anywhere outside of \"merged.c\",\n> > but is declared in its header. Move it into the code file so that it is\n> > clear that its implementation details are never exposed to anything.\n> > \n> > Signed-off-by: Patrick Steinhardt <ps@pks.im>\n> > ---\n> >  reftable/merged.c | 9 +++++++++\n> >  reftable/merged.h | 9 ---------\n> >  2 files changed, 9 insertions(+), 9 deletions(-)\n> > \n> > diff --git a/reftable/merged.c b/reftable/merged.c\n> > index 1aa6cd31b7..12ebd732e8 100644\n> > --- a/reftable/merged.c\n> > +++ b/reftable/merged.c\n> > @@ -17,6 +17,15 @@ license that can be found in the LICENSE file or at\n> >  #include \"reftable-error.h\"\n> >  #include \"system.h\"\n> >  \n> \n> suggestion: I think it would be nice to document a little about the\n> merge iterator here at a high-level. Maybe just to explain that this\n> allows iteration over multiple tables as if it were a single table.\n\nAgreed. I have planned to invest more time into documenting the reftable\nlibrary overall, but would rather want to push this out to another patch\nseries.\n\n> > +struct merged_iter {\n> > +\tstruct reftable_iterator *stack;\n> > +\tuint32_t hash_id;\n> > +\tsize_t stack_len;\n> > +\tuint8_t typ;\n> > +\tint suppress_deletions;\n> > +\tstruct merged_iter_pqueue pq;\n> > +};\n> > +\n> >  static int merged_iter_init(struct merged_iter *mi)\n> >  {\n> >  \tfor (size_t i = 0; i < mi->stack_len; i++) {\n> > diff --git a/reftable/merged.h b/reftable/merged.h\n> > index 7d9f95d27e..288ad66656 100644\n> > --- a/reftable/merged.h\n> > +++ b/reftable/merged.h\n> > @@ -24,15 +24,6 @@ struct reftable_merged_table {\n> >  \tuint64_t max;\n> >  };\n> >  \n> \n> Since we are removing `merge_iter` from the header here, I think we can\n> also remove the `#include \"pg.h\"`.\n\nGood catch! We can replace it with \"system.h\", which makes sure to\ninclude <git-compat-util.h>.\n\nPatrick\n"},{"id":"489545","messageId":"Zd4SuYKesIE07nlp@ncase","threadId":"60913","inReplyTo":"ns2yw3icnl3udejbgsv4ojwgzbe7eg57bvsm53kciuemlvmgbr@mpjtogpzdavi","subject":"Re: [PATCH 03/12] reftable/merged: advance subiter on subsequent iteration","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-02-27T16:50:01Z","receivedAt":"2024-02-27T16:50:05Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"On Tue, Feb 20, 2024 at 12:25:10PM -0600, Justin Tobler wrote:\n> On 24/02/14 08:45AM, Patrick Steinhardt wrote:\n> > When advancing the merged iterator, we pop the top-most entry from its\n> \n> s/top-most/topmost\n> \n> > priority queue and then advance the sub-iterator that the entry belongs\n> > to, adding the result as a new entry. This is quite sensible in the case\n> > where the merged iterator is used to actual iterate through records. But\n> \n> s/actual/actually\n> \n> > the merged iterator is also used when we look up a single record, only,\n> > so advancing the sub-iterator is wasted effort because we would never\n> > even look at the result.\n> > \n> > Instead of immediately advancing the sub-iterator, we can also defer\n> > this to the next iteration of the merged iterator by storing the\n> > intent-to-advance. This results in a small speedup when reading many\n> > records. The following benchmark creates 10000 refs, which will also end\n> > up with many ref lookups:\n> > \n> >     Benchmark 1: update-ref: create many refs (revision = HEAD~)\n> >       Time (mean ± σ):     337.2 ms ±   7.3 ms    [User: 200.1 ms, System: 136.9 ms]\n> >       Range (min … max):   329.3 ms … 373.2 ms    100 runs\n> > \n> >     Benchmark 2: update-ref: create many refs (revision = HEAD)\n> >       Time (mean ± σ):     332.5 ms ±   5.9 ms    [User: 197.2 ms, System: 135.1 ms]\n> >       Range (min … max):   327.6 ms … 359.8 ms    100 runs\n> > \n> >     Summary\n> >       update-ref: create many refs (revision = HEAD) ran\n> >         1.01 ± 0.03 times faster than update-ref: create many refs (revision = HEAD~)\n> > \n> > While this speedup alone isn't really worth it, this refactoring will\n> > also allow two additional optimizations in subsequent patches. First, it\n> > will allow us to special-case when there is only a single sub-iter left\n> > to circumvent the priority queue altogether. And second, it makes it\n> > easier to avoid copying records to the caller.\n> > \n> > Signed-off-by: Patrick Steinhardt <ps@pks.im>\n> > ---\n> >  reftable/merged.c | 26 ++++++++++++--------------\n> >  1 file changed, 12 insertions(+), 14 deletions(-)\n> > \n> > diff --git a/reftable/merged.c b/reftable/merged.c\n> > index 12ebd732e8..9b1ccfff00 100644\n> > --- a/reftable/merged.c\n> > +++ b/reftable/merged.c\n> > @@ -19,11 +19,12 @@ license that can be found in the LICENSE file or at\n> >  \n> >  struct merged_iter {\n> >  \tstruct reftable_iterator *stack;\n> > +\tstruct merged_iter_pqueue pq;\n> >  \tuint32_t hash_id;\n> >  \tsize_t stack_len;\n> >  \tuint8_t typ;\n> >  \tint suppress_deletions;\n> > -\tstruct merged_iter_pqueue pq;\n> > +\tssize_t advance_index;\n> >  };\n> >  \n> >  static int merged_iter_init(struct merged_iter *mi)\n> > @@ -96,13 +97,17 @@ static int merged_iter_next_entry(struct merged_iter *mi,\n> >  \tstruct pq_entry entry = { 0 };\n> >  \tint err = 0;\n> >  \n> > +\tif (mi->advance_index >= 0) {\n> > +\t\terr = merged_iter_advance_subiter(mi, mi->advance_index);\n> > +\t\tif (err < 0)\n> > +\t\t\treturn err;\n> > +\t\tmi->advance_index = -1;\n> > +\t}\n> > +\n> \n> Without additional context, it isn't immediately clear to me why the\n> sub-iterator is condionally advanced at the beginning. Maybe a comment\n> could be added to explain as done in the commit message to help with\n> clarity?\n\nI tried to mention this in the commit message with the last paragraph.\nAdding a comment doesn't make much sense at this point in the patch\nseires because a later patch changes how this works.\n\n> >  \tif (merged_iter_pqueue_is_empty(mi->pq))\n> >  \t\treturn 1;\n> >  \n> >  \tentry = merged_iter_pqueue_remove(&mi->pq);\n> > -\terr = merged_iter_advance_subiter(mi, entry.index);\n> > -\tif (err < 0)\n> > -\t\treturn err;\n> >  \n> >  \t/*\n> >  \t  One can also use reftable as datacenter-local storage, where the ref\n> > @@ -116,14 +121,6 @@ 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> \n> I'm not quite sure I follow by the above check is removed as part of\n> this change. Would you mind clarifying?\n\nThe loop that this comparison has been part of was popping all entries\nfrom the priority queue that are being shadowed by the sub-iterator from\nwhich we're about to return the entry. So e.g. in the case of a ref\nrecord, we discard all records with the same refname which are shadowed\nby a newer (higher update-index) table.\n\nThe removed condition was an optimization was a micro-optimization: when\nthe next entry in the pqueue is from the same index as the entry we are\nabout to return, then we know that it cannot have been shadowed. This\nallowed us to avoid a key comparison.\n\nBut with the change in this commit we don't even add the next record of\nthe current sub-iter to the pqueue, and thus the condition cannot happen\nanymore.\n\nPatrick\n"},{"id":"489585","messageId":"CZG9LAWHCYSO.1D9F91KOUYHIZ@jamesliu.io","threadId":"60913","inReplyTo":"68bd6871132bac3ff8d67e908dd31647feab6bc3.1707895758.git.ps@pks.im","subject":"Re: [PATCH 08/12] reftable/merged: avoid duplicate pqueue emptiness check","fromName":"James Liu","fromEmail":"james@jamesliu.io","sentAt":"2024-02-27T23:53:30Z","receivedAt":"2024-02-27T23:53:36Z","isPatch":true,"sender":{"key":"james@jamesliu.io","avatar":"https://avatars.githubusercontent.com/u/4476568?v=4"},"body":"On Wed Feb 14, 2024 at 6:46 PM AEDT, Patrick Steinhardt wrote:\n> Now if this check was there to accellerate the common case it might have\n\ns/accellerate/accelerate\n"},{"id":"489586","messageId":"CZG9VJKP1EA8.432Y9U39737O@jamesliu.io","threadId":"60913","inReplyTo":"3ba697036c1db3837f46775823a7bd55602b4bac.1707895758.git.ps@pks.im","subject":"Re: [PATCH 09/12] reftable/record: reuse refname when decoding","fromName":"James Liu","fromEmail":"james@jamesliu.io","sentAt":"2024-02-28T00:06:52Z","receivedAt":"2024-02-28T00:06:58Z","isPatch":true,"sender":{"key":"james@jamesliu.io","avatar":"https://avatars.githubusercontent.com/u/4476568?v=4"},"body":"On Wed Feb 14, 2024 at 6:46 PM AEDT, Patrick Steinhardt wrote:\n> This refactoring is safe to do because all functions that assigning to\n> the refname will first call `release_reftable_record()`, which will zero\n> out the complete record after releasing memory.\n\ns/release_reftable_record/reftable_ref_record_release\n\n> Furthermore, with this change we now perform a mostly constant number of\n> allocations when iterating.\n\nThat's awesome!\n\n> +\tSWAP(refname, r->refname);\n> +\tSWAP(refname_cap, r->refname_cap);\n>  \treftable_ref_record_release(r);\n> +\tSWAP(refname, r->refname);\n> +\tSWAP(refname_cap, r->refname_cap);\n\nWhat do you think about reversing the order of the `SWAP` arguments in\nthe last two invocations? If my understanding is correct that we're\npreserving the `refname` and `refname_cap` fields so we can set them back\ninto a freshly initialised `r`, reversing the args might make that intent\na bit clearer.\n\nAlso, since we're unconditionally `memcpy`ing the key into `r->refname`\nbelow, can we avoid the `SWAP(refname, r->refname)` call altogether?\n\n> -\tassert(hash_size > 0);\n> -\n> -\tr->refname = reftable_malloc(key.len + 1);\n> +\tREFTABLE_ALLOC_GROW(r->refname, key.len + 1, r->refname_cap);\n>  \tmemcpy(r->refname, key.buf, key.len);\n>  \tr->refname[key.len] = 0;\n\n"},{"id":"489587","messageId":"CZG9WY119NCG.2ID9DQE6T030U@jamesliu.io","threadId":"60913","inReplyTo":"d7311598c0f81ad3fa41560b54b0974d41485a23.1707895758.git.ps@pks.im","subject":"Re: [PATCH 10/12] reftable/record: reuse refname when copying","fromName":"James Liu","fromEmail":"james@jamesliu.io","sentAt":"2024-02-28T00:08:42Z","receivedAt":"2024-02-28T00:08:47Z","isPatch":true,"sender":{"key":"james@jamesliu.io","avatar":"https://avatars.githubusercontent.com/u/4476568?v=4"},"body":"On Wed Feb 14, 2024 at 6:46 PM AEDT, Patrick Steinhardt wrote:\n> +\tSWAP(refname, ref->refname);\n> +\tSWAP(refname_cap, ref->refname_cap);\n>  \treftable_ref_record_release(ref);\n> +\tSWAP(refname, ref->refname);\n> +\tSWAP(refname_cap, ref->refname_cap);\n\nLikewise here, what are your thoughts about reversing the SWAP arguments for\nthe last two invocations?\n\n"},{"id":"489589","messageId":"CZGA0UX31LAO.1QWOAGQ6BUKIS@jamesliu.io","threadId":"60913","inReplyTo":"f0663c1d62d13d01afb1fa6c3760a38741bdfc8e.1707895758.git.ps@pks.im","subject":"Re: [PATCH 11/12] reftable/record: decode keys in place","fromName":"James Liu","fromEmail":"james@jamesliu.io","sentAt":"2024-02-28T00:13:49Z","receivedAt":"2024-02-28T00:13:53Z","isPatch":true,"sender":{"key":"james@jamesliu.io","avatar":"https://avatars.githubusercontent.com/u/4476568?v=4"},"body":"On Wed Feb 14, 2024 at 6:46 PM AEDT, Patrick Steinhardt wrote:\n> -\tstrbuf_reset(key);\n> -\tstrbuf_add(key, last_key.buf, prefix_len);\n> -\tstrbuf_add(key, in.buf, suffix_len);\n> +\tstrbuf_setlen(last_key, prefix_len);\n> +\tstrbuf_add(last_key, in.buf, suffix_len);\n>  \tstring_view_consume(&in, suffix_len);\n>  \n>  \treturn start_len - in.len;\n\nSince we're using `strbuf`, there's no need to worry about extra bytes\nfor the null terminator here right?\n\n"},{"id":"489868","messageId":"ZeWk2WL18-XGjTlO@tanuki","threadId":"60913","inReplyTo":"CZGA0UX31LAO.1QWOAGQ6BUKIS@jamesliu.io","subject":"Re: [PATCH 11/12] reftable/record: decode keys in place","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-03-04T10:39:21Z","receivedAt":"2024-03-04T10:39:28Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"On Wed, Feb 28, 2024 at 11:13:49AM +1100, James Liu wrote:\n> On Wed Feb 14, 2024 at 6:46 PM AEDT, Patrick Steinhardt wrote:\n> > -\tstrbuf_reset(key);\n> > -\tstrbuf_add(key, last_key.buf, prefix_len);\n> > -\tstrbuf_add(key, in.buf, suffix_len);\n> > +\tstrbuf_setlen(last_key, prefix_len);\n> > +\tstrbuf_add(last_key, in.buf, suffix_len);\n> >  \tstring_view_consume(&in, suffix_len);\n> >  \n> >  \treturn start_len - in.len;\n> \n> Since we're using `strbuf`, there's no need to worry about extra bytes\n> for the null terminator here right?\n\nExactly, the `struct strbuf` interface handles this for us.\n\nPatrick\n"},{"id":"489869","messageId":"ZeWk34iSgTQllpFc@tanuki","threadId":"60913","inReplyTo":"CZG9VJKP1EA8.432Y9U39737O@jamesliu.io","subject":"Re: [PATCH 09/12] reftable/record: reuse refname when decoding","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-03-04T10:39:27Z","receivedAt":"2024-03-04T10:39:31Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"On Wed, Feb 28, 2024 at 11:06:52AM +1100, James Liu wrote:\n> On Wed Feb 14, 2024 at 6:46 PM AEDT, Patrick Steinhardt wrote:\n> > This refactoring is safe to do because all functions that assigning to\n> > the refname will first call `release_reftable_record()`, which will zero\n> > out the complete record after releasing memory.\n> \n> s/release_reftable_record/reftable_ref_record_release\n> \n> > Furthermore, with this change we now perform a mostly constant number of\n> > allocations when iterating.\n> \n> That's awesome!\n> \n> > +\tSWAP(refname, r->refname);\n> > +\tSWAP(refname_cap, r->refname_cap);\n> >  \treftable_ref_record_release(r);\n> > +\tSWAP(refname, r->refname);\n> > +\tSWAP(refname_cap, r->refname_cap);\n> \n> What do you think about reversing the order of the `SWAP` arguments in\n> the last two invocations? If my understanding is correct that we're\n> preserving the `refname` and `refname_cap` fields so we can set them back\n> into a freshly initialised `r`, reversing the args might make that intent\n> a bit clearer.\n\nYeah, fair enough.\n\n> Also, since we're unconditionally `memcpy`ing the key into `r->refname`\n> below, can we avoid the `SWAP(refname, r->refname)` call altogether?\n\nNo, otherwise `reftable_ref_record_release()` would have already\nreleased the underlying pointer of `r->refname` and the call to\n`REFTABLE_ALLOC_GROW()` would always have to reallocate it.\n\nPatrick\n\n> > -\tassert(hash_size > 0);\n> > -\n> > -\tr->refname = reftable_malloc(key.len + 1);\n> > +\tREFTABLE_ALLOC_GROW(r->refname, key.len + 1, r->refname_cap);\n> >  \tmemcpy(r->refname, key.buf, key.len);\n> >  \tr->refname[key.len] = 0;\n> \n"},{"id":"489871","messageId":"cover.1709548907.git.ps@pks.im","threadId":"60913","inReplyTo":"cover.1707895758.git.ps@pks.im","subject":"[PATCH v3 00/13] reftable: improve ref iteration performance (pt.2)","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-03-04T10:48:43Z","receivedAt":"2024-03-04T10:48:48Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"Hi,\n\nthis is the third version of my patch series that aims to improve raw\nref iteration performance with the reftable backend. Changes compared to\nv2:\n\n    - Reversed the order of the second set of `SWAP()` macro calls.\n\n    - Fixed typos in commit messages.\n\nThanks!\n\nPatrick\n\nPatrick Steinhardt (13):\n  reftable/pq: use `size_t` to track iterator index\n  reftable/merged: make `merged_iter` structure private\n  reftable/merged: advance subiter on subsequent iteration\n  reftable/merged: make subiters own their records\n  reftable/merged: remove unnecessary null check for subiters\n  reftable/merged: handle subiter cleanup on close only\n  reftable/merged: circumvent pqueue with single subiter\n  reftable/merged: avoid duplicate pqueue emptiness check\n  reftable/record: reuse refname when decoding\n  reftable/record: reuse refname when copying\n  reftable/record: decode keys in place\n  reftable: allow inlining of a few functions\n  refs/reftable: precompute prefix length\n\n refs/reftable-backend.c    |   6 +-\n reftable/block.c           |  25 +++----\n reftable/block.h           |   2 -\n reftable/iter.c            |   5 --\n reftable/iter.h            |   4 --\n reftable/merged.c          | 139 +++++++++++++++++++------------------\n reftable/merged.h          |  11 +--\n reftable/pq.c              |  18 +----\n reftable/pq.h              |  16 +++--\n reftable/pq_test.c         |  41 +++++------\n reftable/record.c          |  64 +++++++++--------\n reftable/record.h          |  21 ++++--\n reftable/record_test.c     |   3 +-\n reftable/reftable-record.h |   1 +\n 14 files changed, 175 insertions(+), 181 deletions(-)\n\nRange-diff against v2:\n 1:  292e5f8888 =  1:  c998039333 reftable/pq: use `size_t` to track iterator index\n 2:  95e1ccafc4 =  2:  cb144e28a1 reftable/merged: make `merged_iter` structure private\n 3:  0e327e5fe3 =  3:  1bf09661e5 reftable/merged: advance subiter on subsequent iteration\n 4:  494d74deff =  4:  9aa1733aef reftable/merged: make subiters own their records\n 5:  0adf34d08b =  5:  b413006159 reftable/merged: remove unnecessary null check for subiters\n 6:  01152ce130 =  6:  0ab1be740e reftable/merged: handle subiter cleanup on close only\n 7:  370b6cfc6c =  7:  2199881d47 reftable/merged: circumvent pqueue with single subiter\n 8:  1e279f21e6 !  8:  04435f515c reftable/merged: avoid duplicate pqueue emptiness check\n    @@ Commit message\n         down the stack in `merged_iter_next_entry()` though, which makes this\n         check redundant.\n     \n    -    Now if this check was there to accellerate the common case it might have\n    +    Now if this check was there to accelerate the common case it might have\n         made sense to keep it. But the iterator being exhausted is rather the\n         uncommon case because you can expect most reftable stacks to contain\n         more than two refs.\n 9:  15a8cbf678 !  9:  92f83dd404 reftable/record: reuse refname when decoding\n    @@ Commit message\n         to the required number of bytes via `REFTABLE_ALLOC_GROW()`.\n     \n         This refactoring is safe to do because all functions that assigning to\n    -    the refname will first call `release_reftable_record()`, which will zero\n    -    out the complete record after releasing memory.\n    +    the refname will first call `reftable_ref_record_release()`, which will\n    +    zero out the complete record after releasing memory.\n     \n         This change results in a nice speedup when iterating over 1 million\n         refs:\n    @@ reftable/record.c: static int reftable_ref_record_decode(void *rec, struct strbu\n     +\tSWAP(refname, r->refname);\n     +\tSWAP(refname_cap, r->refname_cap);\n      \treftable_ref_record_release(r);\n    -+\tSWAP(refname, r->refname);\n    -+\tSWAP(refname_cap, r->refname_cap);\n    ++\tSWAP(r->refname, refname);\n    ++\tSWAP(r->refname_cap, refname_cap);\n      \n     -\tassert(hash_size > 0);\n     -\n10:  35b1af2f06 ! 10:  eb600f3bf3 reftable/record: reuse refname when copying\n    @@ reftable/record.c: static void reftable_ref_record_copy_from(void *rec, const vo\n     +\tSWAP(refname, ref->refname);\n     +\tSWAP(refname_cap, ref->refname_cap);\n      \treftable_ref_record_release(ref);\n    -+\tSWAP(refname, ref->refname);\n    -+\tSWAP(refname_cap, ref->refname_cap);\n    ++\tSWAP(ref->refname, refname);\n    ++\tSWAP(ref->refname_cap, refname_cap);\n     +\n      \tif (src->refname) {\n     -\t\tref->refname = xstrdup(src->refname);\n11:  d7151ef361 = 11:  f7915f1df8 reftable/record: decode keys in place\n12:  99b238a40d = 12:  527c15e5da reftable: allow inlining of a few functions\n13:  627bd1f5f7 ! 13:  de4a1e2239 refs/reftable: precompute prefix length\n    @@ refs/reftable-backend.c: static int reftable_ref_iterator_advance(struct ref_ite\n      \t\t}\n     @@ refs/reftable-backend.c: static struct reftable_ref_iterator *ref_iterator_for_stack(struct reftable_ref_\n      \titer = xcalloc(1, sizeof(*iter));\n    - \tbase_ref_iterator_init(&iter->base, &reftable_ref_iterator_vtable, 1);\n    + \tbase_ref_iterator_init(&iter->base, &reftable_ref_iterator_vtable);\n      \titer->prefix = prefix;\n     +\titer->prefix_len = prefix ? strlen(prefix) : 0;\n      \titer->base.oid = &iter->oid;\n\nbase-commit: b387623c12f3f4a376e4d35a610fd3e55d7ea907\n-- \n2.44.0\n\n"},{"id":"489872","messageId":"c998039333739d07ed2c68c5bbedd6129efbd1fd.1709548907.git.ps@pks.im","threadId":"60913","inReplyTo":"cover.1709548907.git.ps@pks.im","subject":"[PATCH v3 01/13] reftable/pq: use `size_t` to track iterator index","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-03-04T10:48:47Z","receivedAt":"2024-03-04T10:48:51Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"The reftable priority queue is used by the merged iterator to yield\nrecords from its sub-iterators in the expected order. Each entry has a\nrecord corresponding to such a sub-iterator as well as an index that\nindicates which sub-iterator the record belongs to. But while the\nsub-iterators are tracked with a `size_t`, we store the index as an\n`int` in the entry.\n\nFix this and use `size_t` consistently.\n\nSigned-off-by: Patrick Steinhardt <ps@pks.im>\n---\n reftable/pq.h | 2 +-\n 1 file changed, 1 insertion(+), 1 deletion(-)\n\ndiff --git a/reftable/pq.h b/reftable/pq.h\nindex e85bac9b52..9e25a43a36 100644\n--- a/reftable/pq.h\n+++ b/reftable/pq.h\n@@ -12,7 +12,7 @@ license that can be found in the LICENSE file or at\n #include \"record.h\"\n \n struct pq_entry {\n-\tint index;\n+\tsize_t index;\n \tstruct reftable_record rec;\n };\n \n-- \n2.44.0\n\n"},{"id":"489873","messageId":"cb144e28a154ce19f4b2a98ef68ca3df103e3cb8.1709548907.git.ps@pks.im","threadId":"60913","inReplyTo":"cover.1709548907.git.ps@pks.im","subject":"[PATCH v3 02/13] reftable/merged: make `merged_iter` structure private","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-03-04T10:48:51Z","receivedAt":"2024-03-04T10:48:55Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"The `merged_iter` structure is not used anywhere outside of \"merged.c\",\nbut is declared in its header. Move it into the code file so that it is\nclear that its implementation details are never exposed to anything.\n\nSigned-off-by: Patrick Steinhardt <ps@pks.im>\n---\n reftable/merged.c |  9 +++++++++\n reftable/merged.h | 11 +----------\n 2 files changed, 10 insertions(+), 10 deletions(-)\n\ndiff --git a/reftable/merged.c b/reftable/merged.c\nindex 1aa6cd31b7..12ebd732e8 100644\n--- a/reftable/merged.c\n+++ b/reftable/merged.c\n@@ -17,6 +17,15 @@ license that can be found in the LICENSE file or at\n #include \"reftable-error.h\"\n #include \"system.h\"\n \n+struct merged_iter {\n+\tstruct reftable_iterator *stack;\n+\tuint32_t hash_id;\n+\tsize_t stack_len;\n+\tuint8_t typ;\n+\tint suppress_deletions;\n+\tstruct merged_iter_pqueue pq;\n+};\n+\n static int merged_iter_init(struct merged_iter *mi)\n {\n \tfor (size_t i = 0; i < mi->stack_len; i++) {\ndiff --git a/reftable/merged.h b/reftable/merged.h\nindex 7d9f95d27e..a2571dbc99 100644\n--- a/reftable/merged.h\n+++ b/reftable/merged.h\n@@ -9,7 +9,7 @@ license that can be found in the LICENSE file or at\n #ifndef MERGED_H\n #define MERGED_H\n \n-#include \"pq.h\"\n+#include \"system.h\"\n \n struct reftable_merged_table {\n \tstruct reftable_table *stack;\n@@ -24,15 +24,6 @@ struct reftable_merged_table {\n \tuint64_t max;\n };\n \n-struct merged_iter {\n-\tstruct reftable_iterator *stack;\n-\tuint32_t hash_id;\n-\tsize_t stack_len;\n-\tuint8_t typ;\n-\tint suppress_deletions;\n-\tstruct merged_iter_pqueue pq;\n-};\n-\n void merged_table_release(struct reftable_merged_table *mt);\n \n #endif\n-- \n2.44.0\n\n"},{"id":"489874","messageId":"1bf09661e5c6533b0da9bdf0f05c7459db314a64.1709548907.git.ps@pks.im","threadId":"60913","inReplyTo":"cover.1709548907.git.ps@pks.im","subject":"[PATCH v3 03/13] reftable/merged: advance subiter on subsequent iteration","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-03-04T10:48:55Z","receivedAt":"2024-03-04T10:48:59Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"When advancing the merged iterator, we pop the topmost entry from its\npriority queue and then advance the sub-iterator that the entry belongs\nto, adding the result as a new entry. This is quite sensible in the case\nwhere the merged iterator is used to actually iterate through records.\nBut the merged iterator is also used when we look up a single record,\nonly, so advancing the sub-iterator is wasted effort because we would\nnever even look at the result.\n\nInstead of immediately advancing the sub-iterator, we can also defer\nthis to the next iteration of the merged iterator by storing the\nintent-to-advance. This results in a small speedup when reading many\nrecords. The following benchmark creates 10000 refs, which will also end\nup with many ref lookups:\n\n    Benchmark 1: update-ref: create many refs (revision = HEAD~)\n      Time (mean ± σ):     337.2 ms ±   7.3 ms    [User: 200.1 ms, System: 136.9 ms]\n      Range (min … max):   329.3 ms … 373.2 ms    100 runs\n\n    Benchmark 2: update-ref: create many refs (revision = HEAD)\n      Time (mean ± σ):     332.5 ms ±   5.9 ms    [User: 197.2 ms, System: 135.1 ms]\n      Range (min … max):   327.6 ms … 359.8 ms    100 runs\n\n    Summary\n      update-ref: create many refs (revision = HEAD) ran\n        1.01 ± 0.03 times faster than update-ref: create many refs (revision = HEAD~)\n\nWhile this speedup alone isn't really worth it, this refactoring will\nalso allow two additional optimizations in subsequent patches. First, it\nwill allow us to special-case when there is only a single sub-iter left\nto circumvent the priority queue altogether. And second, it makes it\neasier to avoid copying records to the caller.\n\nSigned-off-by: Patrick Steinhardt <ps@pks.im>\n---\n reftable/merged.c | 26 ++++++++++++--------------\n 1 file changed, 12 insertions(+), 14 deletions(-)\n\ndiff --git a/reftable/merged.c b/reftable/merged.c\nindex 12ebd732e8..9b1ccfff00 100644\n--- a/reftable/merged.c\n+++ b/reftable/merged.c\n@@ -19,11 +19,12 @@ license that can be found in the LICENSE file or at\n \n struct merged_iter {\n \tstruct reftable_iterator *stack;\n+\tstruct merged_iter_pqueue pq;\n \tuint32_t hash_id;\n \tsize_t stack_len;\n \tuint8_t typ;\n \tint suppress_deletions;\n-\tstruct merged_iter_pqueue pq;\n+\tssize_t advance_index;\n };\n \n static int merged_iter_init(struct merged_iter *mi)\n@@ -96,13 +97,17 @@ static int merged_iter_next_entry(struct merged_iter *mi,\n \tstruct pq_entry entry = { 0 };\n \tint err = 0;\n \n+\tif (mi->advance_index >= 0) {\n+\t\terr = merged_iter_advance_subiter(mi, mi->advance_index);\n+\t\tif (err < 0)\n+\t\t\treturn err;\n+\t\tmi->advance_index = -1;\n+\t}\n+\n \tif (merged_iter_pqueue_is_empty(mi->pq))\n \t\treturn 1;\n \n \tentry = merged_iter_pqueue_remove(&mi->pq);\n-\terr = merged_iter_advance_subiter(mi, entry.index);\n-\tif (err < 0)\n-\t\treturn err;\n \n \t/*\n \t  One can also use reftable as datacenter-local storage, where the ref\n@@ -116,14 +121,6 @@ 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@@ -137,6 +134,7 @@ static int merged_iter_next_entry(struct merged_iter *mi,\n \n \treftable_record_release(rec);\n \t*rec = entry.rec;\n+\tmi->advance_index = entry.index;\n \n done:\n \tif (err)\n@@ -160,9 +158,8 @@ static int merged_iter_next(struct merged_iter *mi, struct reftable_record *rec)\n static int merged_iter_next_void(void *p, struct reftable_record *rec)\n {\n \tstruct merged_iter *mi = p;\n-\tif (merged_iter_pqueue_is_empty(mi->pq))\n+\tif (merged_iter_pqueue_is_empty(mi->pq) && mi->advance_index < 0)\n \t\treturn 1;\n-\n \treturn merged_iter_next(mi, rec);\n }\n \n@@ -255,6 +252,7 @@ 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.advance_index = -1,\n \t};\n \tstruct merged_iter *p;\n \tint err;\n-- \n2.44.0\n\n"},{"id":"489875","messageId":"9aa1733aef372bb81516aa0c62f427a1a78e9e66.1709548907.git.ps@pks.im","threadId":"60913","inReplyTo":"cover.1709548907.git.ps@pks.im","subject":"[PATCH v3 04/13] reftable/merged: make subiters own their records","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-03-04T10:48:59Z","receivedAt":"2024-03-04T10:49:03Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"For each subiterator, the merged table needs to track their current\nrecord. This record is owned by the priority queue though instead of by\nthe merged iterator. This is not optimal performance-wise.\n\nFor one, we need to move around records whenever we add or remove a\nrecord from the priority queue. Thus, the bigger the entries the more\nbytes we need to copy around. And compared to pointers, a reftable\nrecord is rather on the bigger side. The other issue is that this makes\nit harder to reuse the records.\n\nRefactor the code so that the merged iterator tracks ownership of the\nrecords per-subiter. Instead of having records in the priority queue, we\ncan now use mere pointers to the per-subiter records. This also allows\nus to swap records between the caller and the per-subiter record instead\nof doing an actual copy via `reftable_record_copy_from()`, which removes\nthe need to release the caller-provided record.\n\nThis results in a noticeable speedup when iterating through many refs.\nThe following benchmark iterates through 1 million refs:\n\n  Benchmark 1: show-ref: single matching ref (revision = HEAD~)\n    Time (mean ± σ):     145.5 ms ±   4.5 ms    [User: 142.5 ms, System: 2.8 ms]\n    Range (min … max):   141.3 ms … 177.0 ms    1000 runs\n\n  Benchmark 2: show-ref: single matching ref (revision = HEAD)\n    Time (mean ± σ):     139.0 ms ±   4.7 ms    [User: 136.1 ms, System: 2.8 ms]\n    Range (min … max):   134.2 ms … 182.2 ms    1000 runs\n\n  Summary\n    show-ref: single matching ref (revision = HEAD) ran\n      1.05 ± 0.05 times faster than show-ref: single matching ref (revision = HEAD~)\n\nThis refactoring also allows a subsequent refactoring where we start\nreusing memory allocated by the reftable records because we do not need\nto release the caller-provided record anymore.\n\nSigned-off-by: Patrick Steinhardt <ps@pks.im>\n---\n reftable/merged.c  | 54 ++++++++++++++++++++++++----------------------\n reftable/pq.c      |  8 ++-----\n reftable/pq.h      |  2 +-\n reftable/pq_test.c | 41 ++++++++++++++++-------------------\n 4 files changed, 49 insertions(+), 56 deletions(-)\n\ndiff --git a/reftable/merged.c b/reftable/merged.c\nindex 9b1ccfff00..ae74234472 100644\n--- a/reftable/merged.c\n+++ b/reftable/merged.c\n@@ -17,8 +17,13 @@ license that can be found in the LICENSE file or at\n #include \"reftable-error.h\"\n #include \"system.h\"\n \n+struct merged_subiter {\n+\tstruct reftable_iterator iter;\n+\tstruct reftable_record rec;\n+};\n+\n struct merged_iter {\n-\tstruct reftable_iterator *stack;\n+\tstruct merged_subiter *subiters;\n \tstruct merged_iter_pqueue pq;\n \tuint32_t hash_id;\n \tsize_t stack_len;\n@@ -32,16 +37,18 @@ static int merged_iter_init(struct merged_iter *mi)\n \tfor (size_t i = 0; i < mi->stack_len; i++) {\n \t\tstruct pq_entry e = {\n \t\t\t.index = i,\n+\t\t\t.rec = &mi->subiters[i].rec,\n \t\t};\n \t\tint err;\n \n-\t\treftable_record_init(&e.rec, mi->typ);\n-\t\terr = iterator_next(&mi->stack[i], &e.rec);\n+\t\treftable_record_init(&mi->subiters[i].rec, mi->typ);\n+\t\terr = iterator_next(&mi->subiters[i].iter,\n+\t\t\t\t    &mi->subiters[i].rec);\n \t\tif (err < 0)\n \t\t\treturn err;\n \t\tif (err > 0) {\n-\t\t\treftable_iterator_destroy(&mi->stack[i]);\n-\t\t\treftable_record_release(&e.rec);\n+\t\t\treftable_iterator_destroy(&mi->subiters[i].iter);\n+\t\t\treftable_record_release(&mi->subiters[i].rec);\n \t\t\tcontinue;\n \t\t}\n \n@@ -56,9 +63,11 @@ static void merged_iter_close(void *p)\n \tstruct merged_iter *mi = p;\n \n \tmerged_iter_pqueue_release(&mi->pq);\n-\tfor (size_t i = 0; i < mi->stack_len; i++)\n-\t\treftable_iterator_destroy(&mi->stack[i]);\n-\treftable_free(mi->stack);\n+\tfor (size_t i = 0; i < mi->stack_len; i++) {\n+\t\treftable_iterator_destroy(&mi->subiters[i].iter);\n+\t\treftable_record_release(&mi->subiters[i].rec);\n+\t}\n+\treftable_free(mi->subiters);\n }\n \n static int merged_iter_advance_nonnull_subiter(struct merged_iter *mi,\n@@ -66,17 +75,16 @@ static int merged_iter_advance_nonnull_subiter(struct merged_iter *mi,\n {\n \tstruct pq_entry e = {\n \t\t.index = idx,\n+\t\t.rec = &mi->subiters[idx].rec,\n \t};\n \tint err;\n \n-\treftable_record_init(&e.rec, mi->typ);\n-\terr = iterator_next(&mi->stack[idx], &e.rec);\n+\terr = iterator_next(&mi->subiters[idx].iter, &mi->subiters[idx].rec);\n \tif (err < 0)\n \t\treturn err;\n-\n \tif (err > 0) {\n-\t\treftable_iterator_destroy(&mi->stack[idx]);\n-\t\treftable_record_release(&e.rec);\n+\t\treftable_iterator_destroy(&mi->subiters[idx].iter);\n+\t\treftable_record_release(&mi->subiters[idx].rec);\n \t\treturn 0;\n \t}\n \n@@ -86,7 +94,7 @@ static int merged_iter_advance_nonnull_subiter(struct merged_iter *mi,\n \n static int merged_iter_advance_subiter(struct merged_iter *mi, size_t idx)\n {\n-\tif (iterator_is_null(&mi->stack[idx]))\n+\tif (iterator_is_null(&mi->subiters[idx].iter))\n \t\treturn 0;\n \treturn merged_iter_advance_nonnull_subiter(mi, idx);\n }\n@@ -121,25 +129,19 @@ 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\tcmp = reftable_record_cmp(&top.rec, &entry.rec);\n+\t\tcmp = reftable_record_cmp(top.rec, entry.rec);\n \t\tif (cmp > 0)\n \t\t\tbreak;\n \n \t\tmerged_iter_pqueue_remove(&mi->pq);\n \t\terr = merged_iter_advance_subiter(mi, top.index);\n \t\tif (err < 0)\n-\t\t\tgoto done;\n-\t\treftable_record_release(&top.rec);\n+\t\t\treturn err;\n \t}\n \n-\treftable_record_release(rec);\n-\t*rec = entry.rec;\n \tmi->advance_index = entry.index;\n-\n-done:\n-\tif (err)\n-\t\treftable_record_release(&entry.rec);\n-\treturn err;\n+\tSWAP(*rec, *entry.rec);\n+\treturn 0;\n }\n \n static int merged_iter_next(struct merged_iter *mi, struct reftable_record *rec)\n@@ -257,10 +259,10 @@ static int merged_table_seek_record(struct reftable_merged_table *mt,\n \tstruct merged_iter *p;\n \tint err;\n \n-\tREFTABLE_CALLOC_ARRAY(merged.stack, mt->stack_len);\n+\tREFTABLE_CALLOC_ARRAY(merged.subiters, mt->stack_len);\n \tfor (size_t i = 0; i < mt->stack_len; i++) {\n \t\terr = reftable_table_seek_record(&mt->stack[i],\n-\t\t\t\t\t\t &merged.stack[merged.stack_len], rec);\n+\t\t\t\t\t\t &merged.subiters[merged.stack_len].iter, rec);\n \t\tif (err < 0)\n \t\t\tgoto out;\n \t\tif (!err)\ndiff --git a/reftable/pq.c b/reftable/pq.c\nindex e0ccce2b97..0074d6bc43 100644\n--- a/reftable/pq.c\n+++ b/reftable/pq.c\n@@ -14,7 +14,7 @@ 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-\tint cmp = reftable_record_cmp(&a->rec, &b->rec);\n+\tint cmp = reftable_record_cmp(a->rec, b->rec);\n \tif (cmp == 0)\n \t\treturn a->index > b->index;\n \treturn cmp < 0;\n@@ -82,10 +82,6 @@ void merged_iter_pqueue_add(struct merged_iter_pqueue *pq, const struct pq_entry\n \n void merged_iter_pqueue_release(struct merged_iter_pqueue *pq)\n {\n-\tint i = 0;\n-\tfor (i = 0; i < pq->len; i++) {\n-\t\treftable_record_release(&pq->heap[i].rec);\n-\t}\n \tFREE_AND_NULL(pq->heap);\n-\tpq->len = pq->cap = 0;\n+\tmemset(pq, 0, sizeof(*pq));\n }\ndiff --git a/reftable/pq.h b/reftable/pq.h\nindex 9e25a43a36..ce23972c16 100644\n--- a/reftable/pq.h\n+++ b/reftable/pq.h\n@@ -13,7 +13,7 @@ license that can be found in the LICENSE file or at\n \n struct pq_entry {\n \tsize_t index;\n-\tstruct reftable_record rec;\n+\tstruct reftable_record *rec;\n };\n \n struct merged_iter_pqueue {\ndiff --git a/reftable/pq_test.c b/reftable/pq_test.c\nindex c202eff848..b7d3c80cc7 100644\n--- a/reftable/pq_test.c\n+++ b/reftable/pq_test.c\n@@ -27,48 +27,43 @@ void merged_iter_pqueue_check(struct merged_iter_pqueue pq)\n \n static void test_pq(void)\n {\n-\tchar *names[54] = { NULL };\n-\tint N = ARRAY_SIZE(names) - 1;\n-\n \tstruct merged_iter_pqueue pq = { NULL };\n+\tstruct reftable_record recs[54];\n+\tint N = ARRAY_SIZE(recs) - 1, i;\n \tchar *last = NULL;\n \n-\tint i = 0;\n \tfor (i = 0; i < N; i++) {\n-\t\tchar name[100];\n-\t\tsnprintf(name, sizeof(name), \"%02d\", i);\n-\t\tnames[i] = xstrdup(name);\n+\t\tstruct strbuf refname = STRBUF_INIT;\n+\t\tstrbuf_addf(&refname, \"%02d\", i);\n+\n+\t\treftable_record_init(&recs[i], BLOCK_TYPE_REF);\n+\t\trecs[i].u.ref.refname = strbuf_detach(&refname, NULL);\n \t}\n \n \ti = 1;\n \tdo {\n-\t\tstruct pq_entry e = { .rec = { .type = BLOCK_TYPE_REF,\n-\t\t\t\t\t       .u.ref = {\n-\t\t\t\t\t\t       .refname = names[i],\n-\t\t\t\t\t       } } };\n+\t\tstruct pq_entry e = {\n+\t\t\t.rec = &recs[i],\n+\t\t};\n+\n \t\tmerged_iter_pqueue_add(&pq, &e);\n \t\tmerged_iter_pqueue_check(pq);\n+\n \t\ti = (i * 7) % N;\n \t} while (i != 1);\n \n \twhile (!merged_iter_pqueue_is_empty(pq)) {\n \t\tstruct pq_entry e = merged_iter_pqueue_remove(&pq);\n-\t\tstruct reftable_record *rec = &e.rec;\n \t\tmerged_iter_pqueue_check(pq);\n \n-\t\tEXPECT(reftable_record_type(rec) == BLOCK_TYPE_REF);\n-\t\tif (last) {\n-\t\t\tEXPECT(strcmp(last, rec->u.ref.refname) < 0);\n-\t\t}\n-\t\t/* this is names[i], so don't dealloc. */\n-\t\tlast = rec->u.ref.refname;\n-\t\trec->u.ref.refname = NULL;\n-\t\treftable_record_release(rec);\n-\t}\n-\tfor (i = 0; i < N; i++) {\n-\t\treftable_free(names[i]);\n+\t\tEXPECT(reftable_record_type(e.rec) == BLOCK_TYPE_REF);\n+\t\tif (last)\n+\t\t\tEXPECT(strcmp(last, e.rec->u.ref.refname) < 0);\n+\t\tlast = e.rec->u.ref.refname;\n \t}\n \n+\tfor (i = 0; i < N; i++)\n+\t\treftable_record_release(&recs[i]);\n \tmerged_iter_pqueue_release(&pq);\n }\n \n-- \n2.44.0\n\n"},{"id":"489876","messageId":"b4130061591e71117a47f7d505e0f6f9e0b57df5.1709548907.git.ps@pks.im","threadId":"60913","inReplyTo":"cover.1709548907.git.ps@pks.im","subject":"[PATCH v3 05/13] reftable/merged: remove unnecessary null check for subiters","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-03-04T10:49:03Z","receivedAt":"2024-03-04T10:49:07Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"Whenever we advance a subiter we first call `iterator_is_null()`. This\nis not needed though because we only ever advance subiters which have\nentries in the priority queue, and we do not end entries to the priority\nqueue when the subiter has been exhausted.\n\nDrop the check as well as the now-unused function. This results in a\nsurprisingly big speedup:\n\n    Benchmark 1: show-ref: single matching ref (revision = HEAD~)\n      Time (mean ± σ):     138.1 ms ±   4.4 ms    [User: 135.1 ms, System: 2.8 ms]\n      Range (min … max):   133.4 ms … 167.3 ms    1000 runs\n\n    Benchmark 2: show-ref: single matching ref (revision = HEAD)\n      Time (mean ± σ):     134.4 ms ±   4.2 ms    [User: 131.5 ms, System: 2.8 ms]\n      Range (min … max):   130.0 ms … 164.0 ms    1000 runs\n\n    Summary\n      show-ref: single matching ref (revision = HEAD) ran\n        1.03 ± 0.05 times faster than show-ref: single matching ref (revision = HEAD~)\n\nSigned-off-by: Patrick Steinhardt <ps@pks.im>\n---\n reftable/iter.c   |  5 -----\n reftable/iter.h   |  4 ----\n reftable/merged.c | 10 +---------\n 3 files changed, 1 insertion(+), 18 deletions(-)\n\ndiff --git a/reftable/iter.c b/reftable/iter.c\nindex 8b5ebf6183..7aa30c4a51 100644\n--- a/reftable/iter.c\n+++ b/reftable/iter.c\n@@ -16,11 +16,6 @@ license that can be found in the LICENSE file or at\n #include \"reader.h\"\n #include \"reftable-error.h\"\n \n-int iterator_is_null(struct reftable_iterator *it)\n-{\n-\treturn !it->ops;\n-}\n-\n static void filtering_ref_iterator_close(void *iter_arg)\n {\n \tstruct filtering_ref_iterator *fri = iter_arg;\ndiff --git a/reftable/iter.h b/reftable/iter.h\nindex 47d67d84df..537431baba 100644\n--- a/reftable/iter.h\n+++ b/reftable/iter.h\n@@ -16,10 +16,6 @@ license that can be found in the LICENSE file or at\n #include \"reftable-iterator.h\"\n #include \"reftable-generic.h\"\n \n-/* Returns true for a zeroed out iterator, such as the one returned from\n- * iterator_destroy. */\n-int iterator_is_null(struct reftable_iterator *it);\n-\n /* iterator that produces only ref records that point to `oid` */\n struct filtering_ref_iterator {\n \tint double_check;\ndiff --git a/reftable/merged.c b/reftable/merged.c\nindex ae74234472..29ad09f3d8 100644\n--- a/reftable/merged.c\n+++ b/reftable/merged.c\n@@ -70,8 +70,7 @@ static void merged_iter_close(void *p)\n \treftable_free(mi->subiters);\n }\n \n-static int merged_iter_advance_nonnull_subiter(struct merged_iter *mi,\n-\t\t\t\t\t       size_t idx)\n+static int merged_iter_advance_subiter(struct merged_iter *mi, size_t idx)\n {\n \tstruct pq_entry e = {\n \t\t.index = idx,\n@@ -92,13 +91,6 @@ static int merged_iter_advance_nonnull_subiter(struct merged_iter *mi,\n \treturn 0;\n }\n \n-static int merged_iter_advance_subiter(struct merged_iter *mi, size_t idx)\n-{\n-\tif (iterator_is_null(&mi->subiters[idx].iter))\n-\t\treturn 0;\n-\treturn merged_iter_advance_nonnull_subiter(mi, idx);\n-}\n-\n static int merged_iter_next_entry(struct merged_iter *mi,\n \t\t\t\t  struct reftable_record *rec)\n {\n-- \n2.44.0\n\n"},{"id":"489877","messageId":"0ab1be740ef3f067b6464f9982324f5ff7815ee9.1709548907.git.ps@pks.im","threadId":"60913","inReplyTo":"cover.1709548907.git.ps@pks.im","subject":"[PATCH v3 06/13] reftable/merged: handle subiter cleanup on close only","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-03-04T10:49:08Z","receivedAt":"2024-03-04T10:49:12Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"When advancing one of the subiters fails we immediately release\nresources associated with that subiter. This is not necessary though as\nwe will release these resources when closing the merged iterator anyway.\n\nDrop the logic and only release resources when the merged iterator is\ndone. This is a mere cleanup that should help reduce the cognitive load\nwhen reading through the code.\n\nSigned-off-by: Patrick Steinhardt <ps@pks.im>\n---\n reftable/merged.c | 12 ++----------\n 1 file changed, 2 insertions(+), 10 deletions(-)\n\ndiff --git a/reftable/merged.c b/reftable/merged.c\nindex 29ad09f3d8..d9ed4a19dd 100644\n--- a/reftable/merged.c\n+++ b/reftable/merged.c\n@@ -46,11 +46,8 @@ static int merged_iter_init(struct merged_iter *mi)\n \t\t\t\t    &mi->subiters[i].rec);\n \t\tif (err < 0)\n \t\t\treturn err;\n-\t\tif (err > 0) {\n-\t\t\treftable_iterator_destroy(&mi->subiters[i].iter);\n-\t\t\treftable_record_release(&mi->subiters[i].rec);\n+\t\tif (err > 0)\n \t\t\tcontinue;\n-\t\t}\n \n \t\tmerged_iter_pqueue_add(&mi->pq, &e);\n \t}\n@@ -79,13 +76,8 @@ static int merged_iter_advance_subiter(struct merged_iter *mi, size_t idx)\n \tint err;\n \n \terr = iterator_next(&mi->subiters[idx].iter, &mi->subiters[idx].rec);\n-\tif (err < 0)\n+\tif (err)\n \t\treturn err;\n-\tif (err > 0) {\n-\t\treftable_iterator_destroy(&mi->subiters[idx].iter);\n-\t\treftable_record_release(&mi->subiters[idx].rec);\n-\t\treturn 0;\n-\t}\n \n \tmerged_iter_pqueue_add(&mi->pq, &e);\n \treturn 0;\n-- \n2.44.0\n\n"},{"id":"489878","messageId":"2199881d476875d37bba0a510e3d74a594b8c61a.1709548907.git.ps@pks.im","threadId":"60913","inReplyTo":"cover.1709548907.git.ps@pks.im","subject":"[PATCH v3 07/13] reftable/merged: circumvent pqueue with single subiter","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-03-04T10:49:13Z","receivedAt":"2024-03-04T10:49:17Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"The merged iterator uses a priority queue to order records so that we\ncan yielid them in the expected order. This priority queue of course\ncomes with some overhead as we need to add, compare and remove entries\nin that priority queue.\n\nIn the general case, that overhead cannot really be avoided. But when we\nhave a single subiter left then there is no need to use the priority\nqueue anymore because the order is exactly the same as what that subiter\nwould return.\n\nWhile having a single subiter may sound like an edge case, it happens\nmore frequently than one might think. In the most common scenario, you\ncan expect a repository to have a single large table that contains most\nof the records and then a set of smaller tables which contain later\nadditions to the reftable stack. In this case it is quite likely that we\nexhaust subiters of those smaller stacks before exhausting the large\ntable.\n\nSpecial-case this and return records directly from the remaining\nsubiter. This results in a sizeable speedup when iterating over 1m refs\nin a repository with a single table:\n\n  Benchmark 1: show-ref: single matching ref (revision = HEAD~)\n    Time (mean ± σ):     135.4 ms ±   4.4 ms    [User: 132.5 ms, System: 2.8 ms]\n    Range (min … max):   131.0 ms … 166.3 ms    1000 runs\n\n  Benchmark 2: show-ref: single matching ref (revision = HEAD)\n    Time (mean ± σ):     126.3 ms ±   3.9 ms    [User: 123.3 ms, System: 2.8 ms]\n    Range (min … max):   122.7 ms … 157.0 ms    1000 runs\n\n  Summary\n    show-ref: single matching ref (revision = HEAD) ran\n      1.07 ± 0.05 times faster than show-ref: single matching ref (revision = HEAD~)\n\nSigned-off-by: Patrick Steinhardt <ps@pks.im>\n---\n reftable/merged.c | 24 ++++++++++++++++++++++--\n 1 file changed, 22 insertions(+), 2 deletions(-)\n\ndiff --git a/reftable/merged.c b/reftable/merged.c\nindex d9ed4a19dd..29161a32cf 100644\n--- a/reftable/merged.c\n+++ b/reftable/merged.c\n@@ -87,16 +87,36 @@ static int merged_iter_next_entry(struct merged_iter *mi,\n \t\t\t\t  struct reftable_record *rec)\n {\n \tstruct pq_entry entry = { 0 };\n-\tint err = 0;\n+\tint err = 0, empty;\n+\n+\tempty = merged_iter_pqueue_is_empty(mi->pq);\n \n \tif (mi->advance_index >= 0) {\n+\t\t/*\n+\t\t * When there are no pqueue entries then we only have a single\n+\t\t * subiter left. There is no need to use the pqueue in that\n+\t\t * case anymore as we know that the subiter will return entries\n+\t\t * in the correct order already.\n+\t\t *\n+\t\t * While this may sound like a very specific edge case, it may\n+\t\t * happen more frequently than you think. Most repositories\n+\t\t * will end up having a single large base table that contains\n+\t\t * most of the refs. It's thus likely that we exhaust all\n+\t\t * subiters but the one from that base ref.\n+\t\t */\n+\t\tif (empty)\n+\t\t\treturn iterator_next(&mi->subiters[mi->advance_index].iter,\n+\t\t\t\t\t     rec);\n+\n \t\terr = merged_iter_advance_subiter(mi, mi->advance_index);\n \t\tif (err < 0)\n \t\t\treturn err;\n+\t\tif (!err)\n+\t\t\tempty = 0;\n \t\tmi->advance_index = -1;\n \t}\n \n-\tif (merged_iter_pqueue_is_empty(mi->pq))\n+\tif (empty)\n \t\treturn 1;\n \n \tentry = merged_iter_pqueue_remove(&mi->pq);\n-- \n2.44.0\n\n"},{"id":"489879","messageId":"04435f515cfd9a1f86527d82e87bf7a27182d964.1709548907.git.ps@pks.im","threadId":"60913","inReplyTo":"cover.1709548907.git.ps@pks.im","subject":"[PATCH v3 08/13] reftable/merged: avoid duplicate pqueue emptiness check","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-03-04T10:49:18Z","receivedAt":"2024-03-04T10:49:22Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"When calling `merged_iter_next_void()` we first check whether the iter\nhas been exhausted already. We already perform this check two levels\ndown the stack in `merged_iter_next_entry()` though, which makes this\ncheck redundant.\n\nNow if this check was there to accelerate the common case it might have\nmade sense to keep it. But the iterator being exhausted is rather the\nuncommon case because you can expect most reftable stacks to contain\nmore than two refs.\n\nSimplify the code by removing the check. As `merged_iter_next_void()` is\nbasically empty except for calling `merged_iter_next()` now, merge these\ntwo functions. This also results in a tiny speedup when iterating over\nmany refs:\n\n    Benchmark 1: show-ref: single matching ref (revision = HEAD~)\n      Time (mean ± σ):     125.6 ms ±   3.8 ms    [User: 122.7 ms, System: 2.8 ms]\n      Range (min … max):   122.4 ms … 153.4 ms    1000 runs\n\n    Benchmark 2: show-ref: single matching ref (revision = HEAD)\n      Time (mean ± σ):     124.0 ms ±   3.9 ms    [User: 121.1 ms, System: 2.8 ms]\n      Range (min … max):   120.1 ms … 156.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\nSigned-off-by: Patrick Steinhardt <ps@pks.im>\n---\n reftable/merged.c | 20 ++++++--------------\n 1 file changed, 6 insertions(+), 14 deletions(-)\n\ndiff --git a/reftable/merged.c b/reftable/merged.c\nindex 29161a32cf..f85a24c678 100644\n--- a/reftable/merged.c\n+++ b/reftable/merged.c\n@@ -148,27 +148,19 @@ static int merged_iter_next_entry(struct merged_iter *mi,\n \treturn 0;\n }\n \n-static int merged_iter_next(struct merged_iter *mi, struct reftable_record *rec)\n+static int merged_iter_next_void(void *p, struct reftable_record *rec)\n {\n+\tstruct merged_iter *mi = p;\n \twhile (1) {\n \t\tint err = merged_iter_next_entry(mi, rec);\n-\t\tif (err == 0 && mi->suppress_deletions &&\n-\t\t    reftable_record_is_deletion(rec)) {\n+\t\tif (err)\n+\t\t\treturn err;\n+\t\tif (mi->suppress_deletions && reftable_record_is_deletion(rec))\n \t\t\tcontinue;\n-\t\t}\n-\n-\t\treturn err;\n+\t\treturn 0;\n \t}\n }\n \n-static int merged_iter_next_void(void *p, struct reftable_record *rec)\n-{\n-\tstruct merged_iter *mi = p;\n-\tif (merged_iter_pqueue_is_empty(mi->pq) && mi->advance_index < 0)\n-\t\treturn 1;\n-\treturn merged_iter_next(mi, rec);\n-}\n-\n static struct reftable_iterator_vtable merged_iter_vtable = {\n \t.next = &merged_iter_next_void,\n \t.close = &merged_iter_close,\n-- \n2.44.0\n\n"},{"id":"489880","messageId":"92f83dd4046d117bdae77fc88dbdefb8742139fe.1709548907.git.ps@pks.im","threadId":"60913","inReplyTo":"cover.1709548907.git.ps@pks.im","subject":"[PATCH v3 09/13] reftable/record: reuse refname when decoding","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-03-04T10:49:22Z","receivedAt":"2024-03-04T10:49:26Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"When decoding a reftable record we will first release the user-provided\nrecord and then decode the new record into it. This is quite inefficient\nas we basically need to reallocate at least the refname every time.\n\nRefactor the function to start tracking the refname capacity. Like this,\nwe can stow away the refname, release, restore and then grow the refname\nto the required number of bytes via `REFTABLE_ALLOC_GROW()`.\n\nThis refactoring is safe to do because all functions that assigning to\nthe refname will first call `reftable_ref_record_release()`, which will\nzero out the complete record after releasing memory.\n\nThis change results in a nice speedup when iterating over 1 million\nrefs:\n\n  Benchmark 1: show-ref: single matching ref (revision = HEAD~)\n\n    Time (mean ± σ):     124.0 ms ±   3.9 ms    [User: 121.1 ms, System: 2.7 ms]\n    Range (min … max):   120.4 ms … 152.7 ms    1000 runs\n\n  Benchmark 2: show-ref: single matching ref (revision = HEAD)\n    Time (mean ± σ):     114.4 ms ±   3.7 ms    [User: 111.5 ms, System: 2.7 ms]\n    Range (min … max):   111.0 ms … 152.1 ms    1000 runs\n\n  Summary\n    show-ref: single matching ref (revision = HEAD) ran\n      1.08 ± 0.05 times faster than show-ref: single matching ref (revision = HEAD~)\n\nFurthermore, with this change we now perform a mostly constant number of\nallocations when iterating. Before this change:\n\n  HEAP SUMMARY:\n      in use at exit: 13,603 bytes in 125 blocks\n    total heap usage: 1,006,620 allocs, 1,006,495 frees, 25,398,363 bytes allocated\n\nAfter this change:\n\n  HEAP SUMMARY:\n      in use at exit: 13,603 bytes in 125 blocks\n    total heap usage: 6,623 allocs, 6,498 frees, 509,592 bytes allocated\n\nSigned-off-by: Patrick Steinhardt <ps@pks.im>\n---\n reftable/record.c          | 16 ++++++++++++----\n reftable/reftable-record.h |  1 +\n 2 files changed, 13 insertions(+), 4 deletions(-)\n\ndiff --git a/reftable/record.c b/reftable/record.c\nindex d6bb42e887..2b52e47c30 100644\n--- a/reftable/record.c\n+++ b/reftable/record.c\n@@ -368,16 +368,24 @@ static int reftable_ref_record_decode(void *rec, struct strbuf key,\n \tstruct reftable_ref_record *r = rec;\n \tstruct string_view start = in;\n \tuint64_t update_index = 0;\n-\tint n = get_var_int(&update_index, &in);\n+\tconst char *refname = NULL;\n+\tsize_t refname_cap = 0;\n+\tint n;\n+\n+\tassert(hash_size > 0);\n+\n+\tn = get_var_int(&update_index, &in);\n \tif (n < 0)\n \t\treturn n;\n \tstring_view_consume(&in, n);\n \n+\tSWAP(refname, r->refname);\n+\tSWAP(refname_cap, r->refname_cap);\n \treftable_ref_record_release(r);\n+\tSWAP(r->refname, refname);\n+\tSWAP(r->refname_cap, refname_cap);\n \n-\tassert(hash_size > 0);\n-\n-\tr->refname = reftable_malloc(key.len + 1);\n+\tREFTABLE_ALLOC_GROW(r->refname, key.len + 1, r->refname_cap);\n \tmemcpy(r->refname, key.buf, key.len);\n \tr->refname[key.len] = 0;\n \ndiff --git a/reftable/reftable-record.h b/reftable/reftable-record.h\nindex bb6e99acd3..e657001d42 100644\n--- a/reftable/reftable-record.h\n+++ b/reftable/reftable-record.h\n@@ -22,6 +22,7 @@ license that can be found in the LICENSE file or at\n /* reftable_ref_record holds a ref database entry target_value */\n struct reftable_ref_record {\n \tchar *refname; /* Name of the ref, malloced. */\n+\tsize_t refname_cap;\n \tuint64_t update_index; /* Logical timestamp at which this value is\n \t\t\t\t* written */\n \n-- \n2.44.0\n\n"},{"id":"489881","messageId":"eb600f3bf38857a2d08bfdad5f8c6a51be029c16.1709548907.git.ps@pks.im","threadId":"60913","inReplyTo":"cover.1709548907.git.ps@pks.im","subject":"[PATCH v3 10/13] reftable/record: reuse refname when copying","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-03-04T10:49:26Z","receivedAt":"2024-03-04T10:49:31Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"Do the same optimization as in the preceding commit, but this time for\n`reftable_record_copy()`. While not as noticeable, it still results in a\nsmall speedup when iterating over 1 million refs:\n\n  Benchmark 1: show-ref: single matching ref (revision = HEAD~)\n    Time (mean ± σ):     114.0 ms ±   3.8 ms    [User: 111.1 ms, System: 2.7 ms]\n    Range (min … max):   110.9 ms … 144.3 ms    1000 runs\n\n  Benchmark 2: show-ref: single matching ref (revision = HEAD)\n    Time (mean ± σ):     112.5 ms ±   3.7 ms    [User: 109.5 ms, System: 2.8 ms]\n    Range (min … max):   109.2 ms … 140.7 ms    1000 runs\n\n  Summary\n    show-ref: single matching ref (revision = HEAD) ran\n      1.01 ± 0.05 times faster than show-ref: single matching ref (revision = HEAD~)\n\nSigned-off-by: Patrick Steinhardt <ps@pks.im>\n---\n reftable/record.c | 18 +++++++++++++++---\n 1 file changed, 15 insertions(+), 3 deletions(-)\n\ndiff --git a/reftable/record.c b/reftable/record.c\nindex 2b52e47c30..12a44f70e5 100644\n--- a/reftable/record.c\n+++ b/reftable/record.c\n@@ -205,14 +205,26 @@ static void reftable_ref_record_copy_from(void *rec, const void *src_rec,\n {\n \tstruct reftable_ref_record *ref = rec;\n \tconst struct reftable_ref_record *src = src_rec;\n+\tchar *refname = NULL;\n+\tsize_t refname_cap = 0;\n+\n \tassert(hash_size > 0);\n \n-\t/* This is simple and correct, but we could probably reuse the hash\n-\t * fields. */\n+\tSWAP(refname, ref->refname);\n+\tSWAP(refname_cap, ref->refname_cap);\n \treftable_ref_record_release(ref);\n+\tSWAP(ref->refname, refname);\n+\tSWAP(ref->refname_cap, refname_cap);\n+\n \tif (src->refname) {\n-\t\tref->refname = xstrdup(src->refname);\n+\t\tsize_t refname_len = strlen(src->refname);\n+\n+\t\tREFTABLE_ALLOC_GROW(ref->refname, refname_len + 1,\n+\t\t\t\t    ref->refname_cap);\n+\t\tmemcpy(ref->refname, src->refname, refname_len);\n+\t\tref->refname[refname_len] = 0;\n \t}\n+\n \tref->update_index = src->update_index;\n \tref->value_type = src->value_type;\n \tswitch (src->value_type) {\n-- \n2.44.0\n\n"},{"id":"489882","messageId":"f7915f1df8c3fc1c25a5d7c52c8f9de87dbffc30.1709548907.git.ps@pks.im","threadId":"60913","inReplyTo":"cover.1709548907.git.ps@pks.im","subject":"[PATCH v3 11/13] reftable/record: decode keys in place","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-03-04T10:49:31Z","receivedAt":"2024-03-04T10:49:35Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"When reading a record from a block, we need to decode the record's key.\nAs reftable keys are prefix-compressed, meaning they reuse a prefix from\nthe preceding record's key, this is a bit more involved than just having\nto copy the relevant bytes: we need to figure out the prefix and suffix\nlengths, copy the prefix from the preceding record and finally copy the\nsuffix from the current record.\n\nThis is done by passing three buffers to `reftable_decode_key()`: one\nbuffer that holds the result, one buffer that holds the last key, and\none buffer that points to the current record. The final key is then\nassembled by calling `strbuf_add()` twice to copy over the prefix and\nsuffix.\n\nPerforming two memory copies is inefficient though. And we can indeed do\nbetter by decoding keys in place. Instead of providing two buffers, the\ncaller may only call a single buffer that is already pre-populated with\nthe last key. Like this, we only have to call `strbuf_setlen()` to trim\nthe record to its prefix and then `strbuf_add()` to add the suffix.\n\nThis refactoring leads to a noticeable performance bump when iterating\nover 1 million refs:\n\n  Benchmark 1: show-ref: single matching ref (revision = HEAD~)\n    Time (mean ± σ):     112.2 ms ±   3.9 ms    [User: 109.3 ms, System: 2.8 ms]\n    Range (min … max):   109.2 ms … 149.6 ms    1000 runs\n\n  Benchmark 2: show-ref: single matching ref (revision = HEAD)\n    Time (mean ± σ):     106.0 ms ±   3.5 ms    [User: 103.2 ms, System: 2.7 ms]\n    Range (min … max):   103.2 ms … 133.7 ms    1000 runs\n\n  Summary\n    show-ref: single matching ref (revision = HEAD) ran\n      1.06 ± 0.05 times faster than show-ref: single matching ref (revision = HEAD~)\n\nSigned-off-by: Patrick Steinhardt <ps@pks.im>\n---\n reftable/block.c       | 25 +++++++++++--------------\n reftable/block.h       |  2 --\n reftable/record.c      | 19 +++++++++----------\n reftable/record.h      |  9 ++++++---\n reftable/record_test.c |  3 ++-\n 5 files changed, 28 insertions(+), 30 deletions(-)\n\ndiff --git a/reftable/block.c b/reftable/block.c\nindex 72eb73b380..ad9074dba6 100644\n--- a/reftable/block.c\n+++ b/reftable/block.c\n@@ -291,9 +291,8 @@ static int restart_key_less(size_t idx, void *args)\n \t/* the restart key is verbatim in the block, so this could avoid the\n \t   alloc for decoding the key */\n \tstruct strbuf rkey = STRBUF_INIT;\n-\tstruct strbuf last_key = STRBUF_INIT;\n \tuint8_t unused_extra;\n-\tint n = reftable_decode_key(&rkey, &unused_extra, last_key, in);\n+\tint n = reftable_decode_key(&rkey, &unused_extra, in);\n \tint result;\n \tif (n < 0) {\n \t\ta->error = 1;\n@@ -326,35 +325,34 @@ int block_iter_next(struct block_iter *it, struct reftable_record *rec)\n \tif (it->next_off >= it->br->block_len)\n \t\treturn 1;\n \n-\tn = reftable_decode_key(&it->key, &extra, it->last_key, in);\n+\tn = reftable_decode_key(&it->last_key, &extra, in);\n \tif (n < 0)\n \t\treturn -1;\n-\n-\tif (!it->key.len)\n+\tif (!it->last_key.len)\n \t\treturn REFTABLE_FORMAT_ERROR;\n \n \tstring_view_consume(&in, n);\n-\tn = reftable_record_decode(rec, it->key, extra, in, it->br->hash_size);\n+\tn = reftable_record_decode(rec, it->last_key, extra, in, it->br->hash_size);\n \tif (n < 0)\n \t\treturn -1;\n \tstring_view_consume(&in, n);\n \n-\tstrbuf_swap(&it->last_key, &it->key);\n \tit->next_off += start.len - in.len;\n \treturn 0;\n }\n \n int block_reader_first_key(struct block_reader *br, struct strbuf *key)\n {\n-\tstruct strbuf empty = STRBUF_INIT;\n-\tint off = br->header_off + 4;\n+\tint off = br->header_off + 4, n;\n \tstruct string_view in = {\n \t\t.buf = br->block.data + off,\n \t\t.len = br->block_len - off,\n \t};\n-\n \tuint8_t extra = 0;\n-\tint n = reftable_decode_key(key, &extra, empty, in);\n+\n+\tstrbuf_reset(key);\n+\n+\tn = reftable_decode_key(key, &extra, in);\n \tif (n < 0)\n \t\treturn n;\n \tif (!key->len)\n@@ -371,7 +369,6 @@ int block_iter_seek(struct block_iter *it, struct strbuf *want)\n void block_iter_close(struct block_iter *it)\n {\n \tstrbuf_release(&it->last_key);\n-\tstrbuf_release(&it->key);\n }\n \n int block_reader_seek(struct block_reader *br, struct block_iter *it,\n@@ -408,8 +405,8 @@ int block_reader_seek(struct block_reader *br, struct block_iter *it,\n \t\tif (err < 0)\n \t\t\tgoto done;\n \n-\t\treftable_record_key(&rec, &it->key);\n-\t\tif (err > 0 || strbuf_cmp(&it->key, want) >= 0) {\n+\t\treftable_record_key(&rec, &it->last_key);\n+\t\tif (err > 0 || strbuf_cmp(&it->last_key, want) >= 0) {\n \t\t\terr = 0;\n \t\t\tgoto done;\n \t\t}\ndiff --git a/reftable/block.h b/reftable/block.h\nindex 17481e6331..51699af233 100644\n--- a/reftable/block.h\n+++ b/reftable/block.h\n@@ -84,12 +84,10 @@ struct block_iter {\n \n \t/* key for last entry we read. */\n \tstruct strbuf last_key;\n-\tstruct strbuf key;\n };\n \n #define BLOCK_ITER_INIT { \\\n \t.last_key = STRBUF_INIT, \\\n-\t.key = STRBUF_INIT, \\\n }\n \n /* initializes a block reader. */\ndiff --git a/reftable/record.c b/reftable/record.c\nindex 12a44f70e5..b9c6eee88a 100644\n--- a/reftable/record.c\n+++ b/reftable/record.c\n@@ -159,20 +159,19 @@ int reftable_encode_key(int *restart, struct string_view dest,\n \treturn start.len - dest.len;\n }\n \n-int reftable_decode_key(struct strbuf *key, uint8_t *extra,\n-\t\t\tstruct strbuf last_key, struct string_view in)\n+int reftable_decode_key(struct strbuf *last_key, uint8_t *extra,\n+\t\t\tstruct string_view in)\n {\n \tint start_len = in.len;\n \tuint64_t prefix_len = 0;\n \tuint64_t suffix_len = 0;\n-\tint n = get_var_int(&prefix_len, &in);\n+\tint n;\n+\n+\tn = get_var_int(&prefix_len, &in);\n \tif (n < 0)\n \t\treturn -1;\n \tstring_view_consume(&in, n);\n \n-\tif (prefix_len > last_key.len)\n-\t\treturn -1;\n-\n \tn = get_var_int(&suffix_len, &in);\n \tif (n <= 0)\n \t\treturn -1;\n@@ -181,12 +180,12 @@ int reftable_decode_key(struct strbuf *key, uint8_t *extra,\n \t*extra = (uint8_t)(suffix_len & 0x7);\n \tsuffix_len >>= 3;\n \n-\tif (in.len < suffix_len)\n+\tif (in.len < suffix_len ||\n+\t    prefix_len > last_key->len)\n \t\treturn -1;\n \n-\tstrbuf_reset(key);\n-\tstrbuf_add(key, last_key.buf, prefix_len);\n-\tstrbuf_add(key, in.buf, suffix_len);\n+\tstrbuf_setlen(last_key, prefix_len);\n+\tstrbuf_add(last_key, in.buf, suffix_len);\n \tstring_view_consume(&in, suffix_len);\n \n \treturn start_len - in.len;\ndiff --git a/reftable/record.h b/reftable/record.h\nindex a05e2be179..91c9c6ebfd 100644\n--- a/reftable/record.h\n+++ b/reftable/record.h\n@@ -81,9 +81,12 @@ int reftable_encode_key(int *is_restart, struct string_view dest,\n \t\t\tstruct strbuf prev_key, struct strbuf key,\n \t\t\tuint8_t extra);\n \n-/* Decode into `key` and `extra` from `in` */\n-int reftable_decode_key(struct strbuf *key, uint8_t *extra,\n-\t\t\tstruct strbuf last_key, struct string_view in);\n+/*\n+ * Decode into `last_key` and `extra` from `in`. `last_key` is expected to\n+ * contain the decoded key of the preceding record, if any.\n+ */\n+int reftable_decode_key(struct strbuf *last_key, uint8_t *extra,\n+\t\t\tstruct string_view in);\n \n /* reftable_index_record are used internally to speed up lookups. */\n struct reftable_index_record {\ndiff --git a/reftable/record_test.c b/reftable/record_test.c\nindex a86cff5526..89209894d8 100644\n--- a/reftable/record_test.c\n+++ b/reftable/record_test.c\n@@ -295,7 +295,8 @@ static void test_key_roundtrip(void)\n \tEXPECT(!restart);\n \tEXPECT(n > 0);\n \n-\tm = reftable_decode_key(&roundtrip, &rt_extra, last_key, dest);\n+\tstrbuf_addstr(&roundtrip, \"refs/heads/master\");\n+\tm = reftable_decode_key(&roundtrip, &rt_extra, dest);\n \tEXPECT(n == m);\n \tEXPECT(0 == strbuf_cmp(&key, &roundtrip));\n \tEXPECT(rt_extra == extra);\n-- \n2.44.0\n\n"},{"id":"489883","messageId":"527c15e5dae59a85947f0278683c341a0310ee04.1709548907.git.ps@pks.im","threadId":"60913","inReplyTo":"cover.1709548907.git.ps@pks.im","subject":"[PATCH v3 12/13] reftable: allow inlining of a few functions","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-03-04T10:49:35Z","receivedAt":"2024-03-04T10:49:40Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"We have a few functions which are basically just accessors to\nstructures. As those functions are executed inside the hot loop when\niterating through many refs, the fact that they cannot be inlined is\ncosting us some performance.\n\nMove the function definitions into their respective headers so that they\ncan be inlined. This results in a performance improvement when iterating\nover 1 million refs:\n\n    Benchmark 1: show-ref: single matching ref (revision = HEAD~)\n      Time (mean ± σ):     105.9 ms ±   3.6 ms    [User: 103.0 ms, System: 2.8 ms]\n      Range (min … max):   103.1 ms … 133.4 ms    1000 runs\n\n    Benchmark 2: show-ref: single matching ref (revision = HEAD)\n      Time (mean ± σ):     100.7 ms ±   3.4 ms    [User: 97.8 ms, System: 2.8 ms]\n      Range (min … max):    97.8 ms … 124.0 ms    1000 runs\n\n    Summary\n      show-ref: single matching ref (revision = HEAD) ran\n        1.05 ± 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     | 10 ----------\n reftable/pq.h     | 12 ++++++++++--\n reftable/record.c | 11 -----------\n reftable/record.h | 12 ++++++++++--\n 4 files changed, 20 insertions(+), 25 deletions(-)\n\ndiff --git a/reftable/pq.c b/reftable/pq.c\nindex 0074d6bc43..7fb45d8c60 100644\n--- a/reftable/pq.c\n+++ b/reftable/pq.c\n@@ -20,16 +20,6 @@ int pq_less(struct pq_entry *a, struct pq_entry *b)\n \treturn cmp < 0;\n }\n \n-struct pq_entry merged_iter_pqueue_top(struct merged_iter_pqueue pq)\n-{\n-\treturn pq.heap[0];\n-}\n-\n-int merged_iter_pqueue_is_empty(struct merged_iter_pqueue pq)\n-{\n-\treturn pq.len == 0;\n-}\n-\n struct pq_entry merged_iter_pqueue_remove(struct merged_iter_pqueue *pq)\n {\n \tint i = 0;\ndiff --git a/reftable/pq.h b/reftable/pq.h\nindex ce23972c16..f796c23179 100644\n--- a/reftable/pq.h\n+++ b/reftable/pq.h\n@@ -22,12 +22,20 @@ struct merged_iter_pqueue {\n \tsize_t cap;\n };\n \n-struct pq_entry merged_iter_pqueue_top(struct merged_iter_pqueue pq);\n-int merged_iter_pqueue_is_empty(struct merged_iter_pqueue pq);\n void merged_iter_pqueue_check(struct merged_iter_pqueue pq);\n struct pq_entry merged_iter_pqueue_remove(struct merged_iter_pqueue *pq);\n void merged_iter_pqueue_add(struct merged_iter_pqueue *pq, const struct pq_entry *e);\n void merged_iter_pqueue_release(struct merged_iter_pqueue *pq);\n int pq_less(struct pq_entry *a, struct pq_entry *b);\n \n+static inline struct pq_entry merged_iter_pqueue_top(struct merged_iter_pqueue pq)\n+{\n+\treturn pq.heap[0];\n+}\n+\n+static inline int merged_iter_pqueue_is_empty(struct merged_iter_pqueue pq)\n+{\n+\treturn pq.len == 0;\n+}\n+\n #endif\ndiff --git a/reftable/record.c b/reftable/record.c\nindex b9c6eee88a..367de04600 100644\n--- a/reftable/record.c\n+++ b/reftable/record.c\n@@ -1176,11 +1176,6 @@ void reftable_record_key(struct reftable_record *rec, struct strbuf *dest)\n \treftable_record_vtable(rec)->key(reftable_record_data(rec), dest);\n }\n \n-uint8_t reftable_record_type(struct reftable_record *rec)\n-{\n-\treturn rec->type;\n-}\n-\n int reftable_record_encode(struct reftable_record *rec, struct string_view dest,\n \t\t\t   int hash_size)\n {\n@@ -1302,12 +1297,6 @@ int reftable_log_record_is_deletion(const struct reftable_log_record *log)\n \treturn (log->value_type == REFTABLE_LOG_DELETION);\n }\n \n-void string_view_consume(struct string_view *s, int n)\n-{\n-\ts->buf += n;\n-\ts->len -= n;\n-}\n-\n static void *reftable_record_data(struct reftable_record *rec)\n {\n \tswitch (rec->type) {\ndiff --git a/reftable/record.h b/reftable/record.h\nindex 91c9c6ebfd..5e8304e052 100644\n--- a/reftable/record.h\n+++ b/reftable/record.h\n@@ -25,7 +25,11 @@ struct string_view {\n };\n \n /* Advance `s.buf` by `n`, and decrease length. */\n-void string_view_consume(struct string_view *s, int n);\n+static inline void string_view_consume(struct string_view *s, int n)\n+{\n+\ts->buf += n;\n+\ts->len -= n;\n+}\n \n /* utilities for de/encoding varints */\n \n@@ -127,7 +131,6 @@ 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-uint8_t reftable_record_type(struct reftable_record *rec);\n void reftable_record_copy_from(struct reftable_record *rec,\n \t\t\t       struct reftable_record *src, int hash_size);\n uint8_t reftable_record_val_type(struct reftable_record *rec);\n@@ -138,6 +141,11 @@ int reftable_record_decode(struct reftable_record *rec, struct strbuf key,\n \t\t\t   int hash_size);\n int reftable_record_is_deletion(struct reftable_record *rec);\n \n+static inline uint8_t reftable_record_type(struct reftable_record *rec)\n+{\n+\treturn rec->type;\n+}\n+\n /* frees and zeroes out the embedded record */\n void reftable_record_release(struct reftable_record *rec);\n \n-- \n2.44.0\n\n"},{"id":"489884","messageId":"de4a1e22396bae955d428251d475476885176fa8.1709548907.git.ps@pks.im","threadId":"60913","inReplyTo":"cover.1709548907.git.ps@pks.im","subject":"[PATCH v3 13/13] refs/reftable: precompute prefix length","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-03-04T10:49:40Z","receivedAt":"2024-03-04T10:49:43Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"We're recomputing the prefix length on every iteration of the ref\niterator. Precompute it for another speedup when iterating over 1\nmillion refs:\n\n    Benchmark 1: show-ref: single matching ref (revision = HEAD~)\n      Time (mean ± σ):     100.3 ms ±   3.7 ms    [User: 97.3 ms, System: 2.8 ms]\n      Range (min … max):    97.5 ms … 139.7 ms    1000 runs\n\n    Benchmark 2: show-ref: single matching ref (revision = HEAD)\n      Time (mean ± σ):      95.8 ms ±   3.4 ms    [User: 92.9 ms, System: 2.8 ms]\n      Range (min … max):    93.0 ms … 121.9 ms    1000 runs\n\n    Summary\n      show-ref: single matching ref (revision = HEAD) ran\n        1.05 ± 0.05 times faster than show-ref: single matching ref (revision = HEAD~)\n\nSigned-off-by: Patrick Steinhardt <ps@pks.im>\n---\n refs/reftable-backend.c | 6 ++++--\n 1 file changed, 4 insertions(+), 2 deletions(-)\n\ndiff --git a/refs/reftable-backend.c b/refs/reftable-backend.c\nindex 6c11c4a5e3..249a618b5a 100644\n--- a/refs/reftable-backend.c\n+++ b/refs/reftable-backend.c\n@@ -346,6 +346,7 @@ struct reftable_ref_iterator {\n \tstruct object_id oid;\n \n \tconst char *prefix;\n+\tsize_t prefix_len;\n \tunsigned int flags;\n \tint err;\n };\n@@ -371,8 +372,8 @@ static int reftable_ref_iterator_advance(struct ref_iterator *ref_iterator)\n \t\tif (!starts_with(iter->ref.refname, \"refs/\"))\n \t\t\tcontinue;\n \n-\t\tif (iter->prefix &&\n-\t\t    strncmp(iter->prefix, iter->ref.refname, strlen(iter->prefix))) {\n+\t\tif (iter->prefix_len &&\n+\t\t    strncmp(iter->prefix, iter->ref.refname, iter->prefix_len)) {\n \t\t\titer->err = 1;\n \t\t\tbreak;\n \t\t}\n@@ -481,6 +482,7 @@ static struct reftable_ref_iterator *ref_iterator_for_stack(struct reftable_ref_\n \titer = xcalloc(1, sizeof(*iter));\n \tbase_ref_iterator_init(&iter->base, &reftable_ref_iterator_vtable);\n \titer->prefix = prefix;\n+\titer->prefix_len = prefix ? strlen(prefix) : 0;\n \titer->base.oid = &iter->oid;\n \titer->flags = flags;\n \titer->refs = refs;\n-- \n2.44.0\n\n"}]}