From: Stefan Sperling Subject: speed up reading of deltas a bit To: gameoftrees@openbsd.org Date: Fri, 20 May 2022 14:04:26 +0200 Testing gotadmin pack with a pack file which contains proper deltas, performance bottlenecks show up elsewhere. Reading deltified tree objects is actually quite slow :-/ This patch speeds things up a little by not reading deltas twice during expansion. The old code first reads in all deltas to find the largest delta in the chain, then allocates appropriately-sized buffers to process the chain again and actually apply the deltas. The delta cache may help a little to avoid overhead from reading the same deltas again, but it is better to avoid doing any unnecessary work in the first place. With this patch we do everything in one pass, and grow our buffers as needed when a larger delta appears somewhere in the chain. In got_pack_dump_delta_chain_to_file() the same approach can be used to decide whether to apply a delta in memory or to a tempfile. We start out with memory buffers if possible and eventually switch to files if needed. For simplicity, once we have switched to files we won't go back to using memory buffers, even if delta sizes shrink. More performance improvements will be needed, but this is a start. ok? diff refs/heads/main refs/heads/delta-membuf blob - 4bac59b80e15c0c64099a61c98b1dd60cd3e01a4 blob + 2c612a33c5d96977b8bbe4ac08c2fc41cc78381b --- lib/pack.c +++ lib/pack.c @@ -1257,34 +1257,25 @@ got_pack_dump_delta_chain_to_file(size_t *result_size, const struct got_error *err = NULL; struct got_delta *delta; uint8_t *base_buf = NULL, *accum_buf = NULL, *delta_buf; - size_t base_bufsz = 0, accum_size = 0, delta_len; - uint64_t max_size; - int n = 0; - - *result_size = 0; - - if (STAILQ_EMPTY(&deltas->entries)) - return got_error(GOT_ERR_BAD_DELTA_CHAIN); - + size_t base_bufsz = 0, accum_bufsz = 0, accum_size = 0, delta_len; /* We process small enough files entirely in memory for speed. */ - err = got_pack_get_delta_chain_max_size(&max_size, deltas, pack); - if (err) - return err; - if (max_size < GOT_DELTA_RESULT_SIZE_CACHED_MAX) { - accum_buf = malloc(max_size); - if (accum_buf == NULL) - return got_error_from_errno("malloc"); - base_file = NULL; - accum_file = NULL; - } else { - if (fseeko(base_file, 0L, SEEK_SET) == -1) - return got_error_from_errno("fseeko"); - if (fseeko(accum_file, 0L, SEEK_SET) == -1) - return got_error_from_errno("fseeko"); - } + const size_t max_bufsize = GOT_DELTA_RESULT_SIZE_CACHED_MAX; + uint64_t max_size = 0; + int n = 0; + *result_size = 0; + + if (STAILQ_EMPTY(&deltas->entries)) + return got_error(GOT_ERR_BAD_DELTA_CHAIN); + + if (fseeko(base_file, 0L, SEEK_SET) == -1) + return got_error_from_errno("fseeko"); + if (fseeko(accum_file, 0L, SEEK_SET) == -1) + return got_error_from_errno("fseeko"); + /* Deltas are ordered in ascending order. */ STAILQ_FOREACH(delta, &deltas->entries, entry) { + uint64_t base_size, result_size = 0; int cached = 1; if (n == 0) { size_t mapoff; @@ -1311,7 +1302,9 @@ got_pack_dump_delta_chain_to_file(size_t *result_size, goto done; } } - if (base_file) { + if (delta->size > max_size) + max_size = delta->size; + if (max_size > max_bufsize) { if (pack->map) { mapoff = (size_t)delta_data_offset; err = got_inflate_to_file_mmap( @@ -1323,6 +1316,12 @@ got_pack_dump_delta_chain_to_file(size_t *result_size, &base_bufsz, NULL, NULL, pack->fd, base_file); } else { + accum_buf = malloc(max_size); + if (accum_buf == NULL) { + err = got_error_from_errno("malloc"); + goto done; + } + accum_bufsz = max_size; if (pack->map) { mapoff = (size_t)delta_data_offset; err = got_inflate_to_mem_mmap(&base_buf, @@ -1337,7 +1336,7 @@ got_pack_dump_delta_chain_to_file(size_t *result_size, if (err) goto done; n++; - if (base_file) + if (base_buf == NULL) rewind(base_file); continue; } @@ -1359,6 +1358,50 @@ got_pack_dump_delta_chain_to_file(size_t *result_size, goto done; } } + + err = got_delta_get_sizes(&base_size, &result_size, + delta_buf, delta_len); + if (err) + goto done; + if (base_size > max_size) + max_size = base_size; + if (result_size > max_size) + max_size = result_size; + + if (base_buf && max_size > max_bufsize) { + /* Switch from buffers to temporary files. */ + size_t w = fwrite(base_buf, 1, base_bufsz, + base_file); + if (w != base_bufsz) { + err = got_ferror(outfile, GOT_ERR_IO); + goto done; + } + free(base_buf); + base_buf = NULL; + free(accum_buf); + accum_buf = NULL; + } + + if (base_buf && max_size > base_bufsz) { + uint8_t *p = realloc(base_buf, max_size); + if (p == NULL) { + err = got_error_from_errno("realloc"); + goto done; + } + base_buf = p; + base_bufsz = max_size; + } + + if (accum_buf && max_size > accum_bufsz) { + uint8_t *p = realloc(accum_buf, max_size); + if (p == NULL) { + err = got_error_from_errno("realloc"); + goto done; + } + accum_buf = p; + accum_bufsz = max_size; + } + if (base_buf) { err = got_delta_apply_in_mem(base_buf, base_bufsz, delta_buf, delta_len, accum_buf, @@ -1380,25 +1423,11 @@ got_pack_dump_delta_chain_to_file(size_t *result_size, /* Accumulated delta becomes the new base. */ if (base_buf) { uint8_t *tmp = accum_buf; - /* - * Base buffer switches roles with accumulation - * buffer. Ensure it can hold the largest - * result in the delta chain. The initial - * allocation might have been smaller. - */ - if (base_bufsz < max_size) { - uint8_t *p; - p = reallocarray(base_buf, 1, max_size); - if (p == NULL) { - err = got_error_from_errno( - "reallocarray"); - goto done; - } - base_buf = p; - base_bufsz = max_size; - } + size_t tmp_size = accum_bufsz; accum_buf = base_buf; + accum_bufsz = base_bufsz; base_buf = tmp; + base_bufsz = tmp_size; } else { FILE *tmp = accum_file; accum_file = base_file; @@ -1430,8 +1459,8 @@ got_pack_dump_delta_chain_to_mem(uint8_t **outbuf, siz const struct got_error *err = NULL; struct got_delta *delta; uint8_t *base_buf = NULL, *accum_buf = NULL, *delta_buf; - size_t base_bufsz = 0, accum_size = 0, delta_len; - uint64_t max_size; + size_t base_bufsz = 0, accum_bufsz = 0, accum_size = 0, delta_len; + uint64_t max_size = 0; int n = 0; *outbuf = NULL; @@ -1440,15 +1469,9 @@ got_pack_dump_delta_chain_to_mem(uint8_t **outbuf, siz if (STAILQ_EMPTY(&deltas->entries)) return got_error(GOT_ERR_BAD_DELTA_CHAIN); - err = got_pack_get_delta_chain_max_size(&max_size, deltas, pack); - if (err) - return err; - accum_buf = malloc(max_size); - if (accum_buf == NULL) - return got_error_from_errno("malloc"); - /* Deltas are ordered in ascending order. */ STAILQ_FOREACH(delta, &deltas->entries, entry) { + uint64_t base_size, result_size = 0; int cached = 1; if (n == 0) { size_t delta_data_offset; @@ -1467,6 +1490,10 @@ got_pack_dump_delta_chain_to_mem(uint8_t **outbuf, siz err = got_error(GOT_ERR_PACK_OFFSET); goto done; } + + if (delta->size > max_size) + max_size = delta->size; + if (pack->map) { size_t mapoff = (size_t)delta_data_offset; err = got_inflate_to_mem_mmap(&base_buf, @@ -1505,6 +1532,36 @@ got_pack_dump_delta_chain_to_mem(uint8_t **outbuf, siz goto done; } } + + err = got_delta_get_sizes(&base_size, &result_size, + delta_buf, delta_len); + if (err) + goto done; + if (base_size > max_size) + max_size = base_size; + if (result_size > max_size) + max_size = result_size; + + if (max_size > base_bufsz) { + uint8_t *p = realloc(base_buf, max_size); + if (p == NULL) { + err = got_error_from_errno("realloc"); + goto done; + } + base_buf = p; + base_bufsz = max_size; + } + + if (max_size > accum_bufsz) { + uint8_t *p = realloc(accum_buf, max_size); + if (p == NULL) { + err = got_error_from_errno("realloc"); + goto done; + } + accum_buf = p; + accum_bufsz = max_size; + } + err = got_delta_apply_in_mem(base_buf, base_bufsz, delta_buf, delta_len, accum_buf, &accum_size, max_size); @@ -1517,24 +1574,11 @@ got_pack_dump_delta_chain_to_mem(uint8_t **outbuf, siz if (n < deltas->nentries) { /* Accumulated delta becomes the new base. */ uint8_t *tmp = accum_buf; - /* - * Base buffer switches roles with accumulation buffer. - * Ensure it can hold the largest result in the delta - * chain. Initial allocation might have been smaller. - */ - if (base_bufsz < max_size) { - uint8_t *p; - p = reallocarray(base_buf, 1, max_size); - if (p == NULL) { - err = got_error_from_errno( - "reallocarray"); - goto done; - } - base_buf = p; - base_bufsz = max_size; - } + size_t tmp_size = accum_bufsz; accum_buf = base_buf; + accum_bufsz = base_bufsz; base_buf = tmp; + base_bufsz = tmp_size; } }