Jeff King <peff@xxxxxxxx> wrote:
> On Wed, Nov 16, 2022 at 10:50:13AM +0000, Eric Wong wrote:
> > Will try to hunt down more memory savings in the nearish future.
>
> Yes, you've probably noticed that pack-objects does not distinguish much
> between what is necessary for the various phases. A few obvious things
> to look at:
>
> 1. After the write phase, you can probably ditch the island bitmaps,
> too. In many repacks we're basically done then, but if you're
> generating bitmaps, that happens afterwards in the same process.
Also, island_marks oid_map gets pretty big itself (300M?), and
realloc gets painful when resizing a big khash especially on
non-GNU/Linux systems without MREMAP_MAYMOVE realloc. Currently
experimenting with tweaks to make oidtree handle kh_oid_map
functionality to avoid resizes...[1]
> 2. The object traversal for pack-objects is done in-process these
> days. But after it finishes, I suspect that we do not generally
> need those object structs anymore, because all of the book-keeping
> is done in the bit object_entry array in packing_data.
pdata->objects is 1.4G for me atm after many hours (still going).
I think packing_data could be split to avoid reallocs, but that
might need to touch a lot of code...
I need to get better data on my next attempts. I suspect gcc
-O2 is throwing off mwrap-perl[2]+addr2line and I need to
rebuild w/ -O0.
[1] WIP oidtree map, but I feel like I forgot C, again :<
diff --git a/delta-islands.c b/delta-islands.c
index 90c0d6958f..9e824d7a0d 100644
--- a/delta-islands.c
+++ b/delta-islands.c
@@ -18,11 +18,13 @@
#include "pack-objects.h"
#include "delta-islands.h"
#include "oid-array.h"
+#include "oidtree.h"
#include "config.h"
KHASH_INIT(str, const char *, void *, 1, kh_str_hash_func, kh_str_hash_equal)
-static kh_oid_map_t *island_marks;
+struct oidtree island_marks_storage;
+static struct oidtree *island_marks;
static unsigned island_counter;
static unsigned island_counter_core;
@@ -93,7 +95,7 @@ static int island_bitmap_get(struct island_bitmap *self, uint32_t i)
int in_same_island(const struct object_id *trg_oid, const struct object_id *src_oid)
{
- khiter_t trg_pos, src_pos;
+ struct island_bitmap *trg, *src;
/* If we aren't using islands, assume everything goes together. */
if (!island_marks)
@@ -103,37 +105,30 @@ int in_same_island(const struct object_id *trg_oid, const struct object_id *src_
* If we don't have a bitmap for the target, we can delta it
* against anything -- it's not an important object
*/
- trg_pos = kh_get_oid_map(island_marks, *trg_oid);
- if (trg_pos >= kh_end(island_marks))
+ trg = oidtree_get(island_marks, trg_oid);
+ if (!trg)
return 1;
/*
* if the source (our delta base) doesn't have a bitmap,
* we don't want to base any deltas on it!
*/
- src_pos = kh_get_oid_map(island_marks, *src_oid);
- if (src_pos >= kh_end(island_marks))
+ src = oidtree_get(island_marks, src_oid);
+ if (!src)
return 0;
- return island_bitmap_is_subset(kh_value(island_marks, trg_pos),
- kh_value(island_marks, src_pos));
+ return island_bitmap_is_subset(trg, src);
}
int island_delta_cmp(const struct object_id *a, const struct object_id *b)
{
- khiter_t a_pos, b_pos;
- struct island_bitmap *a_bitmap = NULL, *b_bitmap = NULL;
+ struct island_bitmap *a_bitmap, *b_bitmap;
if (!island_marks)
return 0;
- a_pos = kh_get_oid_map(island_marks, *a);
- if (a_pos < kh_end(island_marks))
- a_bitmap = kh_value(island_marks, a_pos);
-
- b_pos = kh_get_oid_map(island_marks, *b);
- if (b_pos < kh_end(island_marks))
- b_bitmap = kh_value(island_marks, b_pos);
+ a_bitmap = oidtree_get(island_marks, a);
+ b_bitmap = oidtree_get(island_marks, b);
if (a_bitmap) {
if (!b_bitmap || !island_bitmap_is_subset(a_bitmap, b_bitmap))
@@ -149,30 +144,28 @@ int island_delta_cmp(const struct object_id *a, const struct object_id *b)
static struct island_bitmap *create_or_get_island_marks(struct object *obj)
{
- khiter_t pos;
- int hash_ret;
+ void **val;
+ size_t n = sizeof(struct island_bitmap *);
- pos = kh_put_oid_map(island_marks, obj->oid, &hash_ret);
- if (hash_ret)
- kh_value(island_marks, pos) = island_bitmap_new(NULL);
+ if (oidtree_put(island_marks, &obj->oid, &val, n))
+ *val = island_bitmap_new(NULL);
- return kh_value(island_marks, pos);
+ return *val;
}
static void set_island_marks(struct object *obj, struct island_bitmap *marks)
{
struct island_bitmap *b;
- khiter_t pos;
- int hash_ret;
+ void **val;
+ size_t n = sizeof(struct island_bitmap *);
- pos = kh_put_oid_map(island_marks, obj->oid, &hash_ret);
- if (hash_ret) {
+ if (oidtree_put(island_marks, &obj->oid, &val, n)) {
/*
* We don't have one yet; make a copy-on-write of the
* parent.
*/
marks->refcount++;
- kh_value(island_marks, pos) = marks;
+ *val = marks;
return;
}
@@ -180,10 +173,10 @@ static void set_island_marks(struct object *obj, struct island_bitmap *marks)
* We do have it. Make sure we split any copy-on-write before
* updating.
*/
- b = kh_value(island_marks, pos);
+ b = *val;
if (b->refcount > 1) {
b->refcount--;
- b = kh_value(island_marks, pos) = island_bitmap_new(b);
+ *val = b = island_bitmap_new(b);
}
island_bitmap_or(b, marks);
}
@@ -275,14 +268,11 @@ void resolve_tree_islands(struct repository *r,
struct tree *tree;
struct tree_desc desc;
struct name_entry entry;
- khiter_t pos;
- pos = kh_get_oid_map(island_marks, ent->idx.oid);
- if (pos >= kh_end(island_marks))
+ root_marks = oidtree_get(island_marks, &ent->idx.oid);
+ if (!root_marks)
continue;
- root_marks = kh_value(island_marks, pos);
-
tree = lookup_tree(r, &ent->idx.oid);
if (!tree || parse_tree(tree) < 0)
die(_("bad tree object %s"), oid_to_hex(&ent->idx.oid));
@@ -485,7 +475,8 @@ void load_delta_islands(struct repository *r, int progress)
{
struct island_load_data ild = { 0 };
- island_marks = kh_init_oid_map();
+ oidtree_init(&island_marks_storage);
+ island_marks = &island_marks_storage;
git_config(island_config_callback, &ild);
ild.remote_islands = kh_init_str();
@@ -500,11 +491,11 @@ void load_delta_islands(struct repository *r, int progress)
void propagate_island_marks(struct commit *commit)
{
- khiter_t pos = kh_get_oid_map(island_marks, commit->object.oid);
+ struct island_bitmap *root_marks;
- if (pos < kh_end(island_marks)) {
+ root_marks = oidtree_get(island_marks, &commit->object.oid);
+ if (root_marks) {
struct commit_list *p;
- struct island_bitmap *root_marks = kh_value(island_marks, pos);
parse_commit(commit);
set_island_marks(&get_commit_tree(commit)->object, root_marks);
@@ -522,16 +513,13 @@ int compute_pack_layers(struct packing_data *to_pack)
for (i = 0; i < to_pack->nr_objects; ++i) {
struct object_entry *entry = &to_pack->objects[i];
- khiter_t pos = kh_get_oid_map(island_marks, entry->idx.oid);
+ struct island_bitmap *bitmap;
oe_set_layer(to_pack, entry, 1);
- if (pos < kh_end(island_marks)) {
- struct island_bitmap *bitmap = kh_value(island_marks, pos);
-
- if (island_bitmap_get(bitmap, island_counter_core))
- oe_set_layer(to_pack, entry, 0);
- }
+ bitmap = oidtree_get(island_marks, &entry->idx.oid);
+ if (bitmap && island_bitmap_get(bitmap, island_counter_core))
+ oe_set_layer(to_pack, entry, 0);
}
return 2;
diff --git a/oidtree.c b/oidtree.c
index 0d39389bee..eb7e76335e 100644
--- a/oidtree.c
+++ b/oidtree.c
@@ -28,15 +28,16 @@ void oidtree_clear(struct oidtree *ot)
}
}
-void oidtree_insert(struct oidtree *ot, const struct object_id *oid)
+static void **oidtree_insert3(struct oidtree *ot, const struct object_id *oid,
+ size_t extra)
{
struct cb_node *on;
struct object_id k;
if (!oid->algo)
- BUG("oidtree_insert requires oid->algo");
+ BUG("oidtree insertion requires oid->algo");
- on = mem_pool_alloc(&ot->mem_pool, sizeof(*on) + sizeof(*oid));
+ on = mem_pool_alloc(&ot->mem_pool, sizeof(*on) + sizeof(*oid) + extra);
/*
* Clear the padding and copy the result in separate steps to
@@ -45,19 +46,22 @@ void oidtree_insert(struct oidtree *ot, const struct object_id *oid)
oidcpy_with_padding(&k, oid);
memcpy(on->k, &k, sizeof(k));
- /*
- * n.b. Current callers won't get us duplicates, here. If a
- * future caller causes duplicates, there'll be a a small leak
- * that won't be freed until oidtree_clear. Currently it's not
- * worth maintaining a free list
- */
- cb_insert(&ot->tree, on, sizeof(*oid));
+ if (!cb_insert(&ot->tree, on, sizeof(*oid)))
+ return (void **)(on->k + sizeof(k)); /* success */
+
+ warning("oidtree leak (check contains/get before insert/put)");
+ return NULL;
}
+void oidtree_insert(struct oidtree *ot, const struct object_id *oid)
+{
+ (void)oidtree_insert3(ot, oid, 0);
+}
-int oidtree_contains(struct oidtree *ot, const struct object_id *oid)
+static void **oidtree_find(struct oidtree *ot, const struct object_id *oid)
{
struct object_id k;
+ struct cb_node *on;
size_t klen = sizeof(k);
oidcpy_with_padding(&k, oid);
@@ -69,7 +73,31 @@ int oidtree_contains(struct oidtree *ot, const struct object_id *oid)
klen += BUILD_ASSERT_OR_ZERO(offsetof(struct object_id, hash) <
offsetof(struct object_id, algo));
- return cb_lookup(&ot->tree, (const uint8_t *)&k, klen) ? 1 : 0;
+ on = cb_lookup(&ot->tree, (const uint8_t *)&k, klen);
+ return on ? (void **)(on->k + sizeof(k)) : NULL;
+}
+
+int oidtree_put(struct oidtree *ot, const struct object_id *oid,
+ void ***p, size_t n)
+{
+ *p = oidtree_find(ot, oid);
+ if (*p)
+ return 0;
+
+ *p = oidtree_insert3(ot, oid, n);
+ assert(*p);
+ return 1;
+}
+
+void *oidtree_get(struct oidtree *ot, const struct object_id *oid)
+{
+ void **p = oidtree_find(ot, oid);
+ return p ? *p : NULL;
+}
+
+int oidtree_contains(struct oidtree *ot, const struct object_id *oid)
+{
+ return oidtree_find(ot, oid) ? 1 : 0;
}
static enum cb_next iter(struct cb_node *n, void *arg)
diff --git a/oidtree.h b/oidtree.h
index 77898f510a..2f6e6f1beb 100644
--- a/oidtree.h
+++ b/oidtree.h
@@ -12,6 +12,8 @@ struct oidtree {
void oidtree_init(struct oidtree *);
void oidtree_clear(struct oidtree *);
+
+/* oid_set-like API */
void oidtree_insert(struct oidtree *, const struct object_id *);
int oidtree_contains(struct oidtree *, const struct object_id *);
@@ -19,4 +21,17 @@ typedef enum cb_next (*oidtree_iter)(const struct object_id *, void *data);
void oidtree_each(struct oidtree *, const struct object_id *,
size_t oidhexsz, oidtree_iter, void *data);
+/* oid_map-like API */
+
+/* returns a pointer to the data payload associated with object_id */
+void *oidtree_get(struct oidtree *, const struct object_id *);
+
+/*
+ * points @p to the destination of the value
+ * @n must be consistent for the entire oidtree
+ * returns true if a new oidtree node was created,
+ * returns false if reusing an existing oidtree node
+ */
+int oidtree_put(struct oidtree *, const struct object_id *,
+ void ***p, size_t n);
#endif /* OIDTREE_H */
[2] https://80x24.org/mwrap-perl.git
# after install, run gc under mwrap-perl with backtrace 10
MWRAP=socket_dir:/tmp/mwrap,bt:10 mwrap-perl git gc
# recommended: use GNU addr2line 2.39+ (Aug 2022) for +OFFSET decoding
# start HTTP reverse proxy
ADDR2LINE='/path/to/addr2line -p -f -i' \
mwrap-rproxy --socket-dir=/tmp/mwrap
# the per-PID each/2000 URLs can get really expensive for browsers
# even w3m struggles:
w3m http://0:5000/ # follow per-PID links
