| Message ID | 0597e6944a1a65720d050f47bc82766d5bcf860b.1706687982.git.ps@pks.im (mailing list archive) |
|---|---|
| State | Superseded |
| Headers | show |
| Series | reftable: code style improvements | expand |
On Wed, Jan 31, 2024 at 3:01 AM Patrick Steinhardt <ps@pks.im> wrote: > Throughout the reftable library we have many cases where we need to grow > arrays. In order to avoid too many reallocations, we roughly double the > capacity of the array on each iteration. The resulting code pattern is > thus duplicated across many sites. > > We have similar patterns in our main codebase, which is why we have > eventually introduced an `ALLOC_GROW()` macro to abstract it away and > avoid some code duplication. We cannot easily reuse this macro here > though because `ALLOC_GROW()` uses `REALLOC_ARRAY()`, which in turn will > call realloc(3P) to grow the array. The reftable code is structured as a > library though (even if the boundaries are fuzzy), and one property this > brings with it is that it is possible to plug in your own allocators. So > instead of using realloc(3P), we need to use `reftable_realloc()` that > knows to use the user-provided implementation. > > So let's introduce two new macros `REFTABLE_REALLOC_ARRAY()` and > `REFTABLE_ALLOC_GROW()` that mirror what we do in our main codebase, > with two modifications: > > - They use `reftable_realloc()`, as explained above. > > - They use a different growth factor of `2 * cap + 1` instead of `(cap > + 16) * 3 / 2`. > > The second change is because we know a bit more about the allocation > patterns in the reftable library. For In most cases, we end up only having a s/For In/In/ > single item in the array, so the initial capacity that our global growth > factor uses (which is 24), significantly overallocates in a lot of code Perhaps? s/overallocates/over-allocates/ > paths. This effect is indeed measurable: > [...] > > Convert the reftable library to use these new macros. > > Signed-off-by: Patrick Steinhardt <ps@pks.im> (Neither above comment is worth a reroll.)
Patrick Steinhardt <ps@pks.im> writes: > patterns in the reftable library. For In most cases, we end up only having a > single item in the array, so the initial capacity that our global growth > factor uses (which is 24), significantly overallocates in a lot of code > paths. You need to know not just that you very often initially have only one but you rarely grow it beyond 3, or something like that to explain "significantly overallocates", though. > This effect is indeed measurable: And measuring is very good, but I somehow expected that you would measure not the time (if you often under-allocate and end up reallocating too many times, it might consume more time, though) but the peak memory usage. I cannot quite tell what to think of that 2% time difference. > Convert the reftable library to use these new macros. In any case, the conversion shortens the code and is a good thing. I wish we had a way to tell these macros that we are actually using the same single allocator (which we are doing in our code when linking the reftable thing to us anyway), which would have made this even simpler because you did not have to introduce separate macros.. > Signed-off-by: Patrick Steinhardt <ps@pks.im> > --- > reftable/basics.c | 8 ++------ > reftable/basics.h | 11 +++++++++++ > reftable/block.c | 7 +------ > reftable/merged_test.c | 20 ++++++-------------- > reftable/pq.c | 8 ++------ > reftable/stack.c | 29 ++++++++++++----------------- > reftable/writer.c | 14 ++------------ > 7 files changed, 36 insertions(+), 61 deletions(-) > > diff --git a/reftable/basics.c b/reftable/basics.c > index f761e48028..af9004cec2 100644 > --- a/reftable/basics.c > +++ b/reftable/basics.c > @@ -89,17 +89,13 @@ void parse_names(char *buf, int size, char ***namesp) > next = end; > } > if (p < next) { > - if (names_len == names_cap) { > - names_cap = 2 * names_cap + 1; > - names = reftable_realloc( > - names, names_cap * sizeof(*names)); > - } > + REFTABLE_ALLOC_GROW(names, names_len + 1, names_cap); > names[names_len++] = xstrdup(p); > } > p = next + 1; > } > > - names = reftable_realloc(names, (names_len + 1) * sizeof(*names)); > + REFTABLE_REALLOC_ARRAY(names, names_len + 1); > names[names_len] = NULL; > *namesp = names; > } > diff --git a/reftable/basics.h b/reftable/basics.h > index 096b36862b..2f855cd724 100644 > --- a/reftable/basics.h > +++ b/reftable/basics.h > @@ -53,6 +53,17 @@ void *reftable_realloc(void *p, size_t sz); > void reftable_free(void *p); > void *reftable_calloc(size_t sz); > > +#define REFTABLE_REALLOC_ARRAY(x, alloc) (x) = reftable_realloc((x), st_mult(sizeof(*(x)), (alloc))) > +#define REFTABLE_ALLOC_GROW(x, nr, alloc) \ > + do { \ > + if ((nr) > alloc) { \ > + alloc = 2 * (alloc) + 1; \ > + if (alloc < (nr)) \ > + alloc = (nr); \ > + REFTABLE_REALLOC_ARRAY(x, alloc); \ > + } \ > + } while (0) > + > /* Find the longest shared prefix size of `a` and `b` */ > struct strbuf; > int common_prefix_size(struct strbuf *a, struct strbuf *b); > diff --git a/reftable/block.c b/reftable/block.c > index 1df3d8a0f0..6952d0facf 100644 > --- a/reftable/block.c > +++ b/reftable/block.c > @@ -51,12 +51,7 @@ static int block_writer_register_restart(struct block_writer *w, int n, > if (2 + 3 * rlen + n > w->block_size - w->next) > return -1; > if (is_restart) { > - if (w->restart_len == w->restart_cap) { > - w->restart_cap = w->restart_cap * 2 + 1; > - w->restarts = reftable_realloc( > - w->restarts, sizeof(uint32_t) * w->restart_cap); > - } > - > + REFTABLE_ALLOC_GROW(w->restarts, w->restart_len + 1, w->restart_cap); > w->restarts[w->restart_len++] = w->next; > } > > diff --git a/reftable/merged_test.c b/reftable/merged_test.c > index 46908f738f..e05351e035 100644 > --- a/reftable/merged_test.c > +++ b/reftable/merged_test.c > @@ -231,14 +231,10 @@ static void test_merged(void) > while (len < 100) { /* cap loops/recursion. */ > struct reftable_ref_record ref = { NULL }; > int err = reftable_iterator_next_ref(&it, &ref); > - if (err > 0) { > + if (err > 0) > break; > - } > - if (len == cap) { > - cap = 2 * cap + 1; > - out = reftable_realloc( > - out, sizeof(struct reftable_ref_record) * cap); > - } > + > + REFTABLE_ALLOC_GROW(out, len + 1, cap); > out[len++] = ref; > } > reftable_iterator_destroy(&it); > @@ -368,14 +364,10 @@ static void test_merged_logs(void) > while (len < 100) { /* cap loops/recursion. */ > struct reftable_log_record log = { NULL }; > int err = reftable_iterator_next_log(&it, &log); > - if (err > 0) { > + if (err > 0) > break; > - } > - if (len == cap) { > - cap = 2 * cap + 1; > - out = reftable_realloc( > - out, sizeof(struct reftable_log_record) * cap); > - } > + > + REFTABLE_ALLOC_GROW(out, len + 1, cap); > out[len++] = log; > } > reftable_iterator_destroy(&it); > diff --git a/reftable/pq.c b/reftable/pq.c > index dcefeb793a..2461daf5ff 100644 > --- a/reftable/pq.c > +++ b/reftable/pq.c > @@ -75,13 +75,9 @@ void merged_iter_pqueue_add(struct merged_iter_pqueue *pq, const struct pq_entry > { > int i = 0; > > - if (pq->len == pq->cap) { > - pq->cap = 2 * pq->cap + 1; > - pq->heap = reftable_realloc(pq->heap, > - pq->cap * sizeof(struct pq_entry)); > - } > - > + REFTABLE_ALLOC_GROW(pq->heap, pq->len + 1, pq->cap); > pq->heap[pq->len++] = *e; > + > i = pq->len - 1; > while (i > 0) { > int j = (i - 1) / 2; > diff --git a/reftable/stack.c b/reftable/stack.c > index bf3869ce70..1dfab99e96 100644 > --- a/reftable/stack.c > +++ b/reftable/stack.c > @@ -551,7 +551,7 @@ struct reftable_addition { > struct reftable_stack *stack; > > char **new_tables; > - int new_tables_len; > + size_t new_tables_len, new_tables_cap; > uint64_t next_update_index; > }; > > @@ -602,8 +602,9 @@ static int reftable_stack_init_addition(struct reftable_addition *add, > > static void reftable_addition_close(struct reftable_addition *add) > { > - int i = 0; > struct strbuf nm = STRBUF_INIT; > + size_t i; > + > for (i = 0; i < add->new_tables_len; i++) { > stack_filename(&nm, add->stack, add->new_tables[i]); > unlink(nm.buf); > @@ -613,6 +614,7 @@ static void reftable_addition_close(struct reftable_addition *add) > reftable_free(add->new_tables); > add->new_tables = NULL; > add->new_tables_len = 0; > + add->new_tables_cap = 0; > > delete_tempfile(&add->lock_file); > strbuf_release(&nm); > @@ -631,8 +633,8 @@ int reftable_addition_commit(struct reftable_addition *add) > { > struct strbuf table_list = STRBUF_INIT; > int lock_file_fd = get_tempfile_fd(add->lock_file); > - int i = 0; > int err = 0; > + size_t i; > > if (add->new_tables_len == 0) > goto done; > @@ -660,12 +662,12 @@ int reftable_addition_commit(struct reftable_addition *add) > } > > /* success, no more state to clean up. */ > - for (i = 0; i < add->new_tables_len; i++) { > + for (i = 0; i < add->new_tables_len; i++) > reftable_free(add->new_tables[i]); > - } > reftable_free(add->new_tables); > add->new_tables = NULL; > add->new_tables_len = 0; > + add->new_tables_cap = 0; > > err = reftable_stack_reload_maybe_reuse(add->stack, 1); > if (err) > @@ -792,11 +794,9 @@ int reftable_addition_add(struct reftable_addition *add, > goto done; > } > > - add->new_tables = reftable_realloc(add->new_tables, > - sizeof(*add->new_tables) * > - (add->new_tables_len + 1)); > - add->new_tables[add->new_tables_len] = strbuf_detach(&next_name, NULL); > - add->new_tables_len++; > + REFTABLE_ALLOC_GROW(add->new_tables, add->new_tables_len + 1, > + add->new_tables_cap); > + add->new_tables[add->new_tables_len++] = strbuf_detach(&next_name, NULL); > done: > if (tab_fd > 0) { > close(tab_fd); > @@ -1367,17 +1367,12 @@ static int stack_check_addition(struct reftable_stack *st, > while (1) { > struct reftable_ref_record ref = { NULL }; > err = reftable_iterator_next_ref(&it, &ref); > - if (err > 0) { > + if (err > 0) > break; > - } > if (err < 0) > goto done; > > - if (len >= cap) { > - cap = 2 * cap + 1; > - refs = reftable_realloc(refs, cap * sizeof(refs[0])); > - } > - > + REFTABLE_ALLOC_GROW(refs, len + 1, cap); > refs[len++] = ref; > } > > diff --git a/reftable/writer.c b/reftable/writer.c > index ee4590e20f..4483bb21c3 100644 > --- a/reftable/writer.c > +++ b/reftable/writer.c > @@ -200,12 +200,7 @@ static void writer_index_hash(struct reftable_writer *w, struct strbuf *hash) > return; > } > > - if (key->offset_len == key->offset_cap) { > - key->offset_cap = 2 * key->offset_cap + 1; > - key->offsets = reftable_realloc( > - key->offsets, sizeof(uint64_t) * key->offset_cap); > - } > - > + REFTABLE_ALLOC_GROW(key->offsets, key->offset_len + 1, key->offset_cap); > key->offsets[key->offset_len++] = off; > } > > @@ -674,12 +669,7 @@ static int writer_flush_nonempty_block(struct reftable_writer *w) > if (err < 0) > return err; > > - if (w->index_cap == w->index_len) { > - w->index_cap = 2 * w->index_cap + 1; > - w->index = reftable_realloc( > - w->index, > - sizeof(struct reftable_index_record) * w->index_cap); > - } > + REFTABLE_ALLOC_GROW(w->index, w->index_len + 1, w->index_cap); > > ir.offset = w->next; > strbuf_reset(&ir.last_key);
On Wed, Jan 31, 2024 at 12:35:51PM -0800, Junio C Hamano wrote: > Patrick Steinhardt <ps@pks.im> writes: > > > patterns in the reftable library. For In most cases, we end up only having a > > single item in the array, so the initial capacity that our global growth > > factor uses (which is 24), significantly overallocates in a lot of code > > paths. > > You need to know not just that you very often initially have only > one but you rarely grow it beyond 3, or something like that to > explain "significantly overallocates", though. True. > > This effect is indeed measurable: > > And measuring is very good, but I somehow expected that you would > measure not the time (if you often under-allocate and end up > reallocating too many times, it might consume more time, though) but > the peak memory usage. I cannot quite tell what to think of that 2% > time difference. Very good point indeed. I don't think peak memory usage is really all that helpful either because the problem is not that we are allocating arrays that we keep around all the time, but many small arrays which are short lived. So what is telling is the total number of bytes we end up allocating: Before change: HEAP SUMMARY: in use at exit: 671,983 bytes in 152 blocks total heap usage: 3,843,446 allocs, 3,843,294 frees, 223,761,402 bytes allocated Growth factor (alloc * 2 + 1): HEAP SUMMARY: in use at exit: 671,983 bytes in 152 blocks total heap usage: 3,843,446 allocs, 3,843,294 frees, 223,761,410 bytes allocated Growth factor (alloc + 16) * 2 / 3: HEAP SUMMARY: in use at exit: 671,983 bytes in 152 blocks total heap usage: 3,833,673 allocs, 3,833,521 frees, 4,728,251,742 bytes allocated Allocating 21 times as many bytes with our default growth factor should be a much more compelling argument why we don't actually want to use it compared to the 2% speedup. It's somewhat amazing though that this huge difference only makes for a 2% speedup. > > Convert the reftable library to use these new macros. > > In any case, the conversion shortens the code and is a good thing. > I wish we had a way to tell these macros that we are actually using > the same single allocator (which we are doing in our code when > linking the reftable thing to us anyway), which would have made this > even simpler because you did not have to introduce separate macros.. Yeah, I wasn't a huge fan of this, either. I initially just wanted to reuse our usual macros, but when I noticed the resulting difference in allocated bytes I already had two arguments against this: the fact that we have pluggable allocators in the reftable library and the growth factor. While we could make our macros more flexible so that they can accommodate for both, I don't think that the result would be pretty. So at that point I decided to just duplicate the code. It still ends up removing a lot of code duplication in the reftable library itself, so I don't think it is too bad. Patrick
Patrick Steinhardt <ps@pks.im> writes: > Very good point indeed. I don't think peak memory usage is really all > that helpful either because the problem is not that we are allocating > arrays that we keep around all the time, but many small arrays which are > short lived. So what is telling is the total number of bytes we end up > allocating: True. sum of requested sizes to all the calls to malloc() and friends to allocate, ignoring what gets free()d in between, is what would show how much we try to consume. > Allocating 21 times as many bytes with our default growth factor should > be a much more compelling argument why we don't actually want to use it > compared to the 2% speedup. ;-).
diff --git a/reftable/basics.c b/reftable/basics.c index f761e48028..af9004cec2 100644 --- a/reftable/basics.c +++ b/reftable/basics.c @@ -89,17 +89,13 @@ void parse_names(char *buf, int size, char ***namesp) next = end; } if (p < next) { - if (names_len == names_cap) { - names_cap = 2 * names_cap + 1; - names = reftable_realloc( - names, names_cap * sizeof(*names)); - } + REFTABLE_ALLOC_GROW(names, names_len + 1, names_cap); names[names_len++] = xstrdup(p); } p = next + 1; } - names = reftable_realloc(names, (names_len + 1) * sizeof(*names)); + REFTABLE_REALLOC_ARRAY(names, names_len + 1); names[names_len] = NULL; *namesp = names; } diff --git a/reftable/basics.h b/reftable/basics.h index 096b36862b..2f855cd724 100644 --- a/reftable/basics.h +++ b/reftable/basics.h @@ -53,6 +53,17 @@ void *reftable_realloc(void *p, size_t sz); void reftable_free(void *p); void *reftable_calloc(size_t sz); +#define REFTABLE_REALLOC_ARRAY(x, alloc) (x) = reftable_realloc((x), st_mult(sizeof(*(x)), (alloc))) +#define REFTABLE_ALLOC_GROW(x, nr, alloc) \ + do { \ + if ((nr) > alloc) { \ + alloc = 2 * (alloc) + 1; \ + if (alloc < (nr)) \ + alloc = (nr); \ + REFTABLE_REALLOC_ARRAY(x, alloc); \ + } \ + } while (0) + /* Find the longest shared prefix size of `a` and `b` */ struct strbuf; int common_prefix_size(struct strbuf *a, struct strbuf *b); diff --git a/reftable/block.c b/reftable/block.c index 1df3d8a0f0..6952d0facf 100644 --- a/reftable/block.c +++ b/reftable/block.c @@ -51,12 +51,7 @@ static int block_writer_register_restart(struct block_writer *w, int n, if (2 + 3 * rlen + n > w->block_size - w->next) return -1; if (is_restart) { - if (w->restart_len == w->restart_cap) { - w->restart_cap = w->restart_cap * 2 + 1; - w->restarts = reftable_realloc( - w->restarts, sizeof(uint32_t) * w->restart_cap); - } - + REFTABLE_ALLOC_GROW(w->restarts, w->restart_len + 1, w->restart_cap); w->restarts[w->restart_len++] = w->next; } diff --git a/reftable/merged_test.c b/reftable/merged_test.c index 46908f738f..e05351e035 100644 --- a/reftable/merged_test.c +++ b/reftable/merged_test.c @@ -231,14 +231,10 @@ static void test_merged(void) while (len < 100) { /* cap loops/recursion. */ struct reftable_ref_record ref = { NULL }; int err = reftable_iterator_next_ref(&it, &ref); - if (err > 0) { + if (err > 0) break; - } - if (len == cap) { - cap = 2 * cap + 1; - out = reftable_realloc( - out, sizeof(struct reftable_ref_record) * cap); - } + + REFTABLE_ALLOC_GROW(out, len + 1, cap); out[len++] = ref; } reftable_iterator_destroy(&it); @@ -368,14 +364,10 @@ static void test_merged_logs(void) while (len < 100) { /* cap loops/recursion. */ struct reftable_log_record log = { NULL }; int err = reftable_iterator_next_log(&it, &log); - if (err > 0) { + if (err > 0) break; - } - if (len == cap) { - cap = 2 * cap + 1; - out = reftable_realloc( - out, sizeof(struct reftable_log_record) * cap); - } + + REFTABLE_ALLOC_GROW(out, len + 1, cap); out[len++] = log; } reftable_iterator_destroy(&it); diff --git a/reftable/pq.c b/reftable/pq.c index dcefeb793a..2461daf5ff 100644 --- a/reftable/pq.c +++ b/reftable/pq.c @@ -75,13 +75,9 @@ void merged_iter_pqueue_add(struct merged_iter_pqueue *pq, const struct pq_entry { int i = 0; - if (pq->len == pq->cap) { - pq->cap = 2 * pq->cap + 1; - pq->heap = reftable_realloc(pq->heap, - pq->cap * sizeof(struct pq_entry)); - } - + REFTABLE_ALLOC_GROW(pq->heap, pq->len + 1, pq->cap); pq->heap[pq->len++] = *e; + i = pq->len - 1; while (i > 0) { int j = (i - 1) / 2; diff --git a/reftable/stack.c b/reftable/stack.c index bf3869ce70..1dfab99e96 100644 --- a/reftable/stack.c +++ b/reftable/stack.c @@ -551,7 +551,7 @@ struct reftable_addition { struct reftable_stack *stack; char **new_tables; - int new_tables_len; + size_t new_tables_len, new_tables_cap; uint64_t next_update_index; }; @@ -602,8 +602,9 @@ static int reftable_stack_init_addition(struct reftable_addition *add, static void reftable_addition_close(struct reftable_addition *add) { - int i = 0; struct strbuf nm = STRBUF_INIT; + size_t i; + for (i = 0; i < add->new_tables_len; i++) { stack_filename(&nm, add->stack, add->new_tables[i]); unlink(nm.buf); @@ -613,6 +614,7 @@ static void reftable_addition_close(struct reftable_addition *add) reftable_free(add->new_tables); add->new_tables = NULL; add->new_tables_len = 0; + add->new_tables_cap = 0; delete_tempfile(&add->lock_file); strbuf_release(&nm); @@ -631,8 +633,8 @@ int reftable_addition_commit(struct reftable_addition *add) { struct strbuf table_list = STRBUF_INIT; int lock_file_fd = get_tempfile_fd(add->lock_file); - int i = 0; int err = 0; + size_t i; if (add->new_tables_len == 0) goto done; @@ -660,12 +662,12 @@ int reftable_addition_commit(struct reftable_addition *add) } /* success, no more state to clean up. */ - for (i = 0; i < add->new_tables_len; i++) { + for (i = 0; i < add->new_tables_len; i++) reftable_free(add->new_tables[i]); - } reftable_free(add->new_tables); add->new_tables = NULL; add->new_tables_len = 0; + add->new_tables_cap = 0; err = reftable_stack_reload_maybe_reuse(add->stack, 1); if (err) @@ -792,11 +794,9 @@ int reftable_addition_add(struct reftable_addition *add, goto done; } - add->new_tables = reftable_realloc(add->new_tables, - sizeof(*add->new_tables) * - (add->new_tables_len + 1)); - add->new_tables[add->new_tables_len] = strbuf_detach(&next_name, NULL); - add->new_tables_len++; + REFTABLE_ALLOC_GROW(add->new_tables, add->new_tables_len + 1, + add->new_tables_cap); + add->new_tables[add->new_tables_len++] = strbuf_detach(&next_name, NULL); done: if (tab_fd > 0) { close(tab_fd); @@ -1367,17 +1367,12 @@ static int stack_check_addition(struct reftable_stack *st, while (1) { struct reftable_ref_record ref = { NULL }; err = reftable_iterator_next_ref(&it, &ref); - if (err > 0) { + if (err > 0) break; - } if (err < 0) goto done; - if (len >= cap) { - cap = 2 * cap + 1; - refs = reftable_realloc(refs, cap * sizeof(refs[0])); - } - + REFTABLE_ALLOC_GROW(refs, len + 1, cap); refs[len++] = ref; } diff --git a/reftable/writer.c b/reftable/writer.c index ee4590e20f..4483bb21c3 100644 --- a/reftable/writer.c +++ b/reftable/writer.c @@ -200,12 +200,7 @@ static void writer_index_hash(struct reftable_writer *w, struct strbuf *hash) return; } - if (key->offset_len == key->offset_cap) { - key->offset_cap = 2 * key->offset_cap + 1; - key->offsets = reftable_realloc( - key->offsets, sizeof(uint64_t) * key->offset_cap); - } - + REFTABLE_ALLOC_GROW(key->offsets, key->offset_len + 1, key->offset_cap); key->offsets[key->offset_len++] = off; } @@ -674,12 +669,7 @@ static int writer_flush_nonempty_block(struct reftable_writer *w) if (err < 0) return err; - if (w->index_cap == w->index_len) { - w->index_cap = 2 * w->index_cap + 1; - w->index = reftable_realloc( - w->index, - sizeof(struct reftable_index_record) * w->index_cap); - } + REFTABLE_ALLOC_GROW(w->index, w->index_len + 1, w->index_cap); ir.offset = w->next; strbuf_reset(&ir.last_key);
Throughout the reftable library we have many cases where we need to grow arrays. In order to avoid too many reallocations, we roughly double the capacity of the array on each iteration. The resulting code pattern is thus duplicated across many sites. We have similar patterns in our main codebase, which is why we have eventually introduced an `ALLOC_GROW()` macro to abstract it away and avoid some code duplication. We cannot easily reuse this macro here though because `ALLOC_GROW()` uses `REALLOC_ARRAY()`, which in turn will call realloc(3P) to grow the array. The reftable code is structured as a library though (even if the boundaries are fuzzy), and one property this brings with it is that it is possible to plug in your own allocators. So instead of using realloc(3P), we need to use `reftable_realloc()` that knows to use the user-provided implementation. So let's introduce two new macros `REFTABLE_REALLOC_ARRAY()` and `REFTABLE_ALLOC_GROW()` that mirror what we do in our main codebase, with two modifications: - They use `reftable_realloc()`, as explained above. - They use a different growth factor of `2 * cap + 1` instead of `(cap + 16) * 3 / 2`. The second change is because we know a bit more about the allocation patterns in the reftable library. For In most cases, we end up only having a single item in the array, so the initial capacity that our global growth factor uses (which is 24), significantly overallocates in a lot of code paths. This effect is indeed measurable: Benchmark 1: update-ref: create many refs (growth factor = 2 * cap + 1) Time (mean ± σ): 4.834 s ± 0.020 s [User: 2.219 s, System: 2.614 s] Range (min … max): 4.793 s … 4.871 s 20 runs Benchmark 2: update-ref: create many refs (growth factor = (cap + 16) * 3 + 2) Time (mean ± σ): 4.933 s ± 0.021 s [User: 2.325 s, System: 2.607 s] Range (min … max): 4.889 s … 4.962 s 20 runs Summary update-ref: create many refs (growth factor = 2 * cap + 1) ran 1.02 ± 0.01 times faster than update-ref: create many refs (growth factor = (cap + 16) * 3 + 2) Convert the reftable library to use these new macros. Signed-off-by: Patrick Steinhardt <ps@pks.im> --- reftable/basics.c | 8 ++------ reftable/basics.h | 11 +++++++++++ reftable/block.c | 7 +------ reftable/merged_test.c | 20 ++++++-------------- reftable/pq.c | 8 ++------ reftable/stack.c | 29 ++++++++++++----------------- reftable/writer.c | 14 ++------------ 7 files changed, 36 insertions(+), 61 deletions(-)