{"thread":{"id":"63448","subject":"[PATCH] reftable: fix perf regression when reading blocks of unwanted type","startedAt":"2025-05-12T15:16:03Z","lastAt":"2025-05-12T15:16:03Z","messageCount":1,"participants":["Patrick Steinhardt"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"517858","messageId":"20250512-pks-reftable-perf-fix-v1-1-002cab9fdb08@pks.im","threadId":"63448","inReplyTo":null,"subject":"[PATCH] reftable: fix perf regression when reading blocks of unwanted type","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2025-05-12T15:15:56Z","receivedAt":"2025-05-12T15:16:03Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"In fd888311fbc (reftable/table: move reading block into block reader,\n2025-04-07), we have refactored how reftable blocks are read so that\nmost of the logic is contained in the \"block.c\" subsystem itself. Most\nimportantly, the whole logic to read the data itself is now contained in\nthat subsystem.\n\nThis change caused a significant performance regression though when\nreading blocks that aren't of the specific type one is searching for:\n\n    Benchmark 1: update-ref: create 100k refs (revision = fd888311fbc~)\n      Time (mean ± σ):      2.171 s ±  0.028 s    [User: 1.189 s, System: 0.977 s]\n      Range (min … max):    2.117 s …  2.206 s    10 runs\n\n    Benchmark 2: update-ref: create 100k refs (revision = fd888311fbc)\n      Time (mean ± σ):      3.418 s ±  0.030 s    [User: 2.371 s, System: 1.037 s]\n      Range (min … max):    3.377 s …  3.473 s    10 runs\n\n    Summary\n      update-ref: create 100k refs (revision = fd888311fbc~) ran\n        1.57 ± 0.02 times faster than update-ref: create 100k refs (revision = fd888311fbc)\n\nThe root caute of the performance regression is that we changed when\nexactly blocks of an uninteresting type are being discarded. Previous to\nthe refactoring in the mentioned commit we'd load the block data, read\nits type, notice that it's not the wanted type and discard the block.\nAfter the commit though we don't discard the block immediately, but we\nfully decode it only to realize that it's not the desired type. We then\ndiscard the block again, but have already performed a bunch of pointless\nwork.\n\nFix the regression by making `reftable_block_init()` return early in\ncase the block is not of the desired type. This fixes the performance\nhit:\n\n    Benchmark 1: update-ref: create 100k refs (revision = HEAD~)\n      Time (mean ± σ):      2.712 s ±  0.018 s    [User: 1.990 s, System: 0.716 s]\n      Range (min … max):    2.682 s …  2.741 s    10 runs\n\n    Benchmark 2: update-ref: create 100k refs (revision = HEAD)\n      Time (mean ± σ):      1.670 s ±  0.012 s    [User: 0.991 s, System: 0.676 s]\n      Range (min … max):    1.652 s …  1.693 s    10 runs\n\n    Summary\n      update-ref: create 100k refs (revision = HEAD) ran\n        1.62 ± 0.02 times faster than update-ref: create 100k refs (revision = HEAD~)\n\nNote that the baseline performance is lower than in the original due to\na couple of unrelated performance improvements that have landed since\nthe original commit.\n\nSigned-off-by: Patrick Steinhardt <ps@pks.im>\n---\nHi,\n\nthis patch fixes a performance regression that I have recently\nintroduced into the reftable library. This regression has been flagged\nto us via Bencher [1], see the \"Create refs atomically\" benchmark.\n\nThanks!\n\nPatrick\n\n[1]: https://bencher.dev/console/projects/git/plots\n---\n reftable/block.c                |  7 ++++++-\n reftable/reftable-block.h       |  3 ++-\n reftable/table.c                | 11 +----------\n t/unit-tests/t-reftable-block.c | 15 ++++++++++-----\n 4 files changed, 19 insertions(+), 17 deletions(-)\n\ndiff --git a/reftable/block.c b/reftable/block.c\nindex 471faa1642a..920b3f44867 100644\n--- a/reftable/block.c\n+++ b/reftable/block.c\n@@ -227,7 +227,8 @@ static int read_block(struct reftable_block_source *source,\n int reftable_block_init(struct reftable_block *block,\n \t\t\tstruct reftable_block_source *source,\n \t\t\tuint32_t offset, uint32_t header_size,\n-\t\t\tuint32_t table_block_size, uint32_t hash_size)\n+\t\t\tuint32_t table_block_size, uint32_t hash_size,\n+\t\t\tuint8_t want_type)\n {\n \tuint32_t guess_block_size = table_block_size ?\n \t\ttable_block_size : DEFAULT_BLOCK_SIZE;\n@@ -247,6 +248,10 @@ int reftable_block_init(struct reftable_block *block,\n \t\terr = REFTABLE_FORMAT_ERROR;\n \t\tgoto done;\n \t}\n+\tif (want_type != REFTABLE_BLOCK_TYPE_ANY && block_type != want_type) {\n+\t\terr = 1;\n+\t\tgoto done;\n+\t}\n \n \tblock_size = reftable_get_be24(block->block_data.data + header_size + 1);\n \tif (block_size > guess_block_size) {\ndiff --git a/reftable/reftable-block.h b/reftable/reftable-block.h\nindex 04c3b518c87..0b05a8f7e37 100644\n--- a/reftable/reftable-block.h\n+++ b/reftable/reftable-block.h\n@@ -56,7 +56,8 @@ struct reftable_block {\n int reftable_block_init(struct reftable_block *b,\n \t\t\tstruct reftable_block_source *source,\n \t\t\tuint32_t offset, uint32_t header_size,\n-\t\t\tuint32_t table_block_size, uint32_t hash_size);\n+\t\t\tuint32_t table_block_size, uint32_t hash_size,\n+\t\t\tuint8_t want_type);\n \n /* Release resources allocated by the block. */\n void reftable_block_release(struct reftable_block *b);\ndiff --git a/reftable/table.c b/reftable/table.c\nindex ee831276158..56362df0eda 100644\n--- a/reftable/table.c\n+++ b/reftable/table.c\n@@ -173,16 +173,7 @@ int table_init_block(struct reftable_table *t, struct reftable_block *block,\n \t\treturn 1;\n \n \terr = reftable_block_init(block, &t->source, next_off, header_off,\n-\t\t\t\t  t->block_size, hash_size(t->hash_id));\n-\tif (err < 0)\n-\t\tgoto done;\n-\n-\tif (want_typ != REFTABLE_BLOCK_TYPE_ANY && block->block_type != want_typ) {\n-\t\terr = 1;\n-\t\tgoto done;\n-\t}\n-\n-done:\n+\t\t\t\t  t->block_size, hash_size(t->hash_id), want_typ);\n \tif (err)\n \t\treftable_block_release(block);\n \treturn err;\ndiff --git a/t/unit-tests/t-reftable-block.c b/t/unit-tests/t-reftable-block.c\nindex 7dbd93601c7..52f1dae1c95 100644\n--- a/t/unit-tests/t-reftable-block.c\n+++ b/t/unit-tests/t-reftable-block.c\n@@ -64,7 +64,8 @@ static void t_ref_block_read_write(void)\n \tblock_writer_release(&bw);\n \n \tblock_source_from_buf(&source ,&block_data);\n-\treftable_block_init(&block, &source, 0, header_off, block_size, REFTABLE_HASH_SIZE_SHA1);\n+\treftable_block_init(&block, &source, 0, header_off, block_size,\n+\t\t\t    REFTABLE_HASH_SIZE_SHA1, REFTABLE_BLOCK_TYPE_REF);\n \n \tblock_iter_init(&it, &block);\n \n@@ -153,7 +154,8 @@ static void t_log_block_read_write(void)\n \tblock_writer_release(&bw);\n \n \tblock_source_from_buf(&source, &block_data);\n-\treftable_block_init(&block, &source, 0, header_off, block_size, REFTABLE_HASH_SIZE_SHA1);\n+\treftable_block_init(&block, &source, 0, header_off, block_size,\n+\t\t\t    REFTABLE_HASH_SIZE_SHA1, REFTABLE_BLOCK_TYPE_LOG);\n \n \tblock_iter_init(&it, &block);\n \n@@ -245,7 +247,8 @@ static void t_obj_block_read_write(void)\n \tblock_writer_release(&bw);\n \n \tblock_source_from_buf(&source, &block_data);\n-\treftable_block_init(&block, &source, 0, header_off, block_size, REFTABLE_HASH_SIZE_SHA1);\n+\treftable_block_init(&block, &source, 0, header_off, block_size,\n+\t\t\t    REFTABLE_HASH_SIZE_SHA1, REFTABLE_BLOCK_TYPE_OBJ);\n \n \tblock_iter_init(&it, &block);\n \n@@ -329,7 +332,8 @@ static void t_index_block_read_write(void)\n \tblock_writer_release(&bw);\n \n \tblock_source_from_buf(&source, &block_data);\n-\treftable_block_init(&block, &source, 0, header_off, block_size, REFTABLE_HASH_SIZE_SHA1);\n+\treftable_block_init(&block, &source, 0, header_off, block_size,\n+\t\t\t    REFTABLE_HASH_SIZE_SHA1, REFTABLE_BLOCK_TYPE_INDEX);\n \n \tblock_iter_init(&it, &block);\n \n@@ -411,7 +415,8 @@ static void t_block_iterator(void)\n \tcheck_int(err, >, 0);\n \n \tblock_source_from_buf(&source, &data);\n-\treftable_block_init(&block, &source, 0, 0, data.len, REFTABLE_HASH_SIZE_SHA1);\n+\treftable_block_init(&block, &source, 0, 0, data.len,\n+\t\t\t    REFTABLE_HASH_SIZE_SHA1, REFTABLE_BLOCK_TYPE_REF);\n \n \terr = reftable_block_init_iterator(&block, &it);\n \tcheck_int(err, ==, 0);\n\n---\nbase-commit: 7a1d2bd0a596f42a8a7a68d55577967bb454fec0\nchange-id: 20250512-pks-reftable-perf-fix-c64d5f54e950\n\n"}]}