* It is possible to artificially get into a state where there are many * duplicate copies of objects. That can create high memory pressure if * we are to create a list of all objects before de-duplication. To reduce * this memory pressure without a significant performance drop, automatically * group objects by the first byte of their object id. Use the IDX fanout * tables to group the data, c
| 391 | * of a packfile containing the object). |
| 392 | */ |
| 393 | static void compute_sorted_entries(struct write_midx_context *ctx, |
| 394 | uint32_t start_pack) |
| 395 | { |
| 396 | uint32_t cur_fanout, cur_pack, cur_object; |
| 397 | size_t alloc_objects, total_objects = 0; |
| 398 | struct midx_fanout fanout = { 0 }; |
| 399 | |
| 400 | if (ctx->compact) |
| 401 | ASSERT(!start_pack); |
| 402 | |
| 403 | for (cur_pack = start_pack; cur_pack < ctx->nr; cur_pack++) |
| 404 | total_objects = st_add(total_objects, |
| 405 | ctx->info[cur_pack].p->num_objects); |
| 406 | |
| 407 | /* |
| 408 | * As we de-duplicate by fanout value, we expect the fanout |
| 409 | * slices to be evenly distributed, with some noise. Hence, |
| 410 | * allocate slightly more than one 256th. |
| 411 | */ |
| 412 | alloc_objects = fanout.alloc = total_objects > 3200 ? total_objects / 200 : 16; |
| 413 | |
| 414 | ALLOC_ARRAY(fanout.entries, fanout.alloc); |
| 415 | ALLOC_ARRAY(ctx->entries, alloc_objects); |
| 416 | ctx->entries_nr = 0; |
| 417 | |
| 418 | for (cur_fanout = 0; cur_fanout < 256; cur_fanout++) { |
| 419 | fanout.nr = 0; |
| 420 | |
| 421 | if (ctx->compact) |
| 422 | midx_fanout_add_compact(&fanout, ctx, cur_fanout); |
| 423 | else |
| 424 | midx_fanout_add(&fanout, ctx, start_pack, cur_fanout); |
| 425 | midx_fanout_sort(&fanout); |
| 426 | |
| 427 | /* |
| 428 | * The batch is now sorted by OID and then mtime (descending). |
| 429 | * Take only the first duplicate. |
| 430 | */ |
| 431 | for (cur_object = 0; cur_object < fanout.nr; cur_object++) { |
| 432 | if (cur_object && oideq(&fanout.entries[cur_object - 1].oid, |
| 433 | &fanout.entries[cur_object].oid)) |
| 434 | continue; |
| 435 | if (ctx->incremental && ctx->base_midx && |
| 436 | midx_has_oid(ctx->base_midx, |
| 437 | &fanout.entries[cur_object].oid)) |
| 438 | continue; |
| 439 | |
| 440 | ALLOC_GROW(ctx->entries, st_add(ctx->entries_nr, 1), |
| 441 | alloc_objects); |
| 442 | memcpy(&ctx->entries[ctx->entries_nr], |
| 443 | &fanout.entries[cur_object], |
| 444 | sizeof(struct pack_midx_entry)); |
| 445 | ctx->entries_nr++; |
| 446 | } |
| 447 | } |
| 448 | |
| 449 | free(fanout.entries); |
| 450 | } |
no test coverage detected