| Message ID | 20240328101356.300374-1-e@80x24.org (mailing list archive) |
|---|---|
| Headers | show |
| Series | switch to tombstone-free khashl table | expand |
Sorry, been running on fumes all week :<
Eric Wong <e@80x24.org> writes: > Fortunately, this set of changes is unintrusive; but I'm > hoping to have more time to make deeper changes this year. > > Eric Wong (3): > list-objects-filter: use kh_size API > treewide: switch to khashl for memory savings > khashl: fix ensemble lookups on empty table > > builtin/fast-import.c | 2 +- > builtin/fsmonitor--daemon.c | 4 +- > delta-islands.c | 4 +- > khash.h | 338 ----------------------- > khashl.h | 522 ++++++++++++++++++++++++++++++++++++ > list-objects-filter.c | 2 +- > object-store-ll.h | 2 +- > object-store.h | 7 +- > oidset.h | 2 +- > pack-bitmap.h | 2 +- > 10 files changed, 535 insertions(+), 350 deletions(-) > delete mode 100644 khash.h > create mode 100644 khashl.h > > Range-diff: > -: ---------- > 1: 3bf3148cab list-objects-filter: use kh_size API > 1: e74965907e ! 2: 09900edb48 treewide: switch to khashl for memory savings Do you have the correct range-diff? The previous round had the change to the list-object-filter.c to use kh_size() already. But I see the 0 -> NULL fixes. Perhaps the left-side base was off by one when you took the range-diff and there is nothing else going on that we should be worried about... > @@ Commit message > > khashl is an updated version of khash with less memory overhead > (one bit/bucket instead of two) than the original khash and > - similar overall performance. Insertions are simpler (linear > - probing) but deletions may be slightly slower[1]. Of course, > - the majority of hash tables in git do not delete individual > - elements. > + similar overall performance. According to its author, > + insertions are simpler (linear probing) but deletions may be > + slightly slower[1]. Of course, the majority of hash tables in > + git do not delete individual elements. > > Overall memory usage did not decrease much, as the hash tables > and elements we store in them are big and currently dwarf the > overhead of the khash internals. Only around 10 MB in > - allocations (not peak use) is saved when doing a no-op `git gc' > - of a Linux kernel object store with thousands of refs and > - islands. > + allocations (and a few dozen KB peak use out of ~6 GB) is saved > + when doing a no-op `git gc' of a Linux kernel object store with > + thousands of refs and islands. > > A summary of differences I've found from khash to khashl: > > @@ Commit message > * flesh out KHASHL_{SET,MAP}_INIT wrappers with *_clear, *_resize, > and *_release functions > > + * sparse fixes from Junio and Jeff > + > [1] https://attractivechaos.wordpress.com/2019/12/28/deletion-from-hash-tables-without-tombstones/ > [2] git clone https://github.com/attractivechaos/klib.git > 2895a16cb55e (support an ensemble of hash tables, 2023-12-18) > @@ Commit message > typedef) and was the only place where I had to change a definition. > > Signed-off-by: Eric Wong <e@80x24.org> > + Helped-by: Junio C Hamano <gitster@pobox.com> > + Helped-by: Jeff King <peff@peff.net> > > ## builtin/fast-import.c ## > @@ > @@ khashl.h (new) > +#define __KHASHL_IMPL_GET(SCOPE, HType, prefix, khkey_t, __hash_fn, __hash_eq) \ > + SCOPE khint_t prefix##_getp_core(const HType *h, const khkey_t *key, khint_t hash) { \ > + khint_t i, last, n_buckets, mask; \ > -+ if (h->keys == 0) return 0; \ > ++ if (!h->keys) return 0; \ > + n_buckets = (khint_t)1U << h->bits; \ > + mask = n_buckets - 1U; \ > + i = last = __kh_h2b(hash, h->bits); \ > @@ khashl.h (new) > + > +#define __KHASHL_IMPL_RESIZE(SCOPE, HType, prefix, khkey_t, __hash_fn, __hash_eq) \ > + SCOPE void prefix##_resize(HType *h, khint_t new_n_buckets) { \ > -+ khint32_t *new_used = 0; \ > ++ khint32_t *new_used = NULL; \ > + khint_t j = 0, x = new_n_buckets, n_buckets, new_bits, new_mask; \ > + while ((x >>= 1) != 0) ++j; \ > + if (new_n_buckets & (new_n_buckets - 1)) ++j; \ > @@ khashl.h (new) > +#define __KHASHL_IMPL_DEL(SCOPE, HType, prefix, khkey_t, __hash_fn) \ > + SCOPE int prefix##_del(HType *h, khint_t i) { \ > + khint_t j = i, k, mask, n_buckets; \ > -+ if (h->keys == 0) return 0; \ > ++ if (!h->keys) return 0; \ > + n_buckets = (khint_t)1U<<h->bits; \ > + mask = n_buckets - 1U; \ > + while (1) { \ > 2: 744e1b7198 = 3: bfb20eae37 khashl: fix ensemble lookups on empty table
Junio C Hamano <gitster@pobox.com> wrote: > Eric Wong <e@80x24.org> writes: > > Range-diff: > > -: ---------- > 1: 3bf3148cab list-objects-filter: use kh_size API > > 1: e74965907e ! 2: 09900edb48 treewide: switch to khashl for memory savings > > Do you have the correct range-diff? The previous round had the > change to the list-object-filter.c to use kh_size() already. > > But I see the 0 -> NULL fixes. Perhaps the left-side base was off > by one when you took the range-diff and there is nothing else going > on that we should be worried about... Odd... I switched to a different machine (w) for v2 due to connectivity problems to the original machine (m) I did v1 on and applied the patches sent to the list. I did end up rebasing v1 on (w) against the newer master: c75fd8d815 (The eleventh batch, 2024-03-25) instead of commit 11c821f2f2 (The tenth batch, 2024-03-21) on (m). On (w): git format-patch -o $OUT/ khashl-base..khashl-v2 \ --cover-letter --range-diff=khashl-v1 -v2 Seems to mess up infer_range_diff_ranges and it chose `khashl-v2' instead of `khash-base' as the `a' part of the range for r1. (m) doesn't do this, both running 2.44.0.32*-ish Here it is from (w) with the explicit `a..' part for --range-diff: git format-patch -o $OUT/ khashl-base..khashl-v2 \ --cover-letter --range-diff=khashl-base..khashl-v1 -v2 Range-diff against v1: 1: 3bf3148cab = 1: 3bf3148cab list-objects-filter: use kh_size API 2: e74965907e ! 2: 09900edb48 treewide: switch to khashl for memory savings @@ Commit message khashl is an updated version of khash with less memory overhead (one bit/bucket instead of two) than the original khash and - similar overall performance. Insertions are simpler (linear - probing) but deletions may be slightly slower[1]. Of course, - the majority of hash tables in git do not delete individual - elements. + similar overall performance. According to its author, + insertions are simpler (linear probing) but deletions may be + slightly slower[1]. Of course, the majority of hash tables in + git do not delete individual elements. Overall memory usage did not decrease much, as the hash tables and elements we store in them are big and currently dwarf the overhead of the khash internals. Only around 10 MB in - allocations (not peak use) is saved when doing a no-op `git gc' - of a Linux kernel object store with thousands of refs and - islands. + allocations (and a few dozen KB peak use out of ~6 GB) is saved + when doing a no-op `git gc' of a Linux kernel object store with + thousands of refs and islands. A summary of differences I've found from khash to khashl: @@ Commit message * flesh out KHASHL_{SET,MAP}_INIT wrappers with *_clear, *_resize, and *_release functions + * sparse fixes from Junio and Jeff + [1] https://attractivechaos.wordpress.com/2019/12/28/deletion-from-hash-tables-without-tombstones/ [2] git clone https://github.com/attractivechaos/klib.git 2895a16cb55e (support an ensemble of hash tables, 2023-12-18) @@ Commit message typedef) and was the only place where I had to change a definition. Signed-off-by: Eric Wong <e@80x24.org> + Helped-by: Junio C Hamano <gitster@pobox.com> + Helped-by: Jeff King <peff@peff.net> ## builtin/fast-import.c ## @@ @@ khashl.h (new) +#define __KHASHL_IMPL_GET(SCOPE, HType, prefix, khkey_t, __hash_fn, __hash_eq) \ + SCOPE khint_t prefix##_getp_core(const HType *h, const khkey_t *key, khint_t hash) { \ + khint_t i, last, n_buckets, mask; \ -+ if (h->keys == 0) return 0; \ ++ if (!h->keys) return 0; \ + n_buckets = (khint_t)1U << h->bits; \ + mask = n_buckets - 1U; \ + i = last = __kh_h2b(hash, h->bits); \ @@ khashl.h (new) + +#define __KHASHL_IMPL_RESIZE(SCOPE, HType, prefix, khkey_t, __hash_fn, __hash_eq) \ + SCOPE void prefix##_resize(HType *h, khint_t new_n_buckets) { \ -+ khint32_t *new_used = 0; \ ++ khint32_t *new_used = NULL; \ + khint_t j = 0, x = new_n_buckets, n_buckets, new_bits, new_mask; \ + while ((x >>= 1) != 0) ++j; \ + if (new_n_buckets & (new_n_buckets - 1)) ++j; \ @@ khashl.h (new) +#define __KHASHL_IMPL_DEL(SCOPE, HType, prefix, khkey_t, __hash_fn) \ + SCOPE int prefix##_del(HType *h, khint_t i) { \ + khint_t j = i, k, mask, n_buckets; \ -+ if (h->keys == 0) return 0; \ ++ if (!h->keys) return 0; \ + n_buckets = (khint_t)1U<<h->bits; \ + mask = n_buckets - 1U; \ + while (1) { \ 3: 744e1b7198 = 3: bfb20eae37 khashl: fix ensemble lookups on empty table
This is another step in slowly reducing memory usage of `git gc' and associated tasks. khashl is an updated version of khash which eliminates tombstones for deleted elements to save space. The overall memory improvement with our codebase is tiny (a few dozen KB out of several GB at peak, about 10MB over the lifetime of a process). Any memory reduction at all is welcome at this point; and khashl comes with some new optional features and enhancements which may come in handy someday. I haven't been able to validate CPU-dependent improvements claimed by the author due to system noise from working on a shared server. No aberrant behavior has been noticed in day-to-day `production' use on public facing servers. Keep in mind the switch linear probing for performance is consistent with findings made for the open-coded ->obj_hash in object.c Fortunately, this set of changes is unintrusive; but I'm hoping to have more time to make deeper changes this year. Eric Wong (3): list-objects-filter: use kh_size API treewide: switch to khashl for memory savings khashl: fix ensemble lookups on empty table builtin/fast-import.c | 2 +- builtin/fsmonitor--daemon.c | 4 +- delta-islands.c | 4 +- khash.h | 338 ----------------------- khashl.h | 522 ++++++++++++++++++++++++++++++++++++ list-objects-filter.c | 2 +- object-store-ll.h | 2 +- object-store.h | 7 +- oidset.h | 2 +- pack-bitmap.h | 2 +- 10 files changed, 535 insertions(+), 350 deletions(-) delete mode 100644 khash.h create mode 100644 khashl.h Range-diff: -: ---------- > 1: 3bf3148cab list-objects-filter: use kh_size API 1: e74965907e ! 2: 09900edb48 treewide: switch to khashl for memory savings @@ Commit message khashl is an updated version of khash with less memory overhead (one bit/bucket instead of two) than the original khash and - similar overall performance. Insertions are simpler (linear - probing) but deletions may be slightly slower[1]. Of course, - the majority of hash tables in git do not delete individual - elements. + similar overall performance. According to its author, + insertions are simpler (linear probing) but deletions may be + slightly slower[1]. Of course, the majority of hash tables in + git do not delete individual elements. Overall memory usage did not decrease much, as the hash tables and elements we store in them are big and currently dwarf the overhead of the khash internals. Only around 10 MB in - allocations (not peak use) is saved when doing a no-op `git gc' - of a Linux kernel object store with thousands of refs and - islands. + allocations (and a few dozen KB peak use out of ~6 GB) is saved + when doing a no-op `git gc' of a Linux kernel object store with + thousands of refs and islands. A summary of differences I've found from khash to khashl: @@ Commit message * flesh out KHASHL_{SET,MAP}_INIT wrappers with *_clear, *_resize, and *_release functions + * sparse fixes from Junio and Jeff + [1] https://attractivechaos.wordpress.com/2019/12/28/deletion-from-hash-tables-without-tombstones/ [2] git clone https://github.com/attractivechaos/klib.git 2895a16cb55e (support an ensemble of hash tables, 2023-12-18) @@ Commit message typedef) and was the only place where I had to change a definition. Signed-off-by: Eric Wong <e@80x24.org> + Helped-by: Junio C Hamano <gitster@pobox.com> + Helped-by: Jeff King <peff@peff.net> ## builtin/fast-import.c ## @@ @@ khashl.h (new) +#define __KHASHL_IMPL_GET(SCOPE, HType, prefix, khkey_t, __hash_fn, __hash_eq) \ + SCOPE khint_t prefix##_getp_core(const HType *h, const khkey_t *key, khint_t hash) { \ + khint_t i, last, n_buckets, mask; \ -+ if (h->keys == 0) return 0; \ ++ if (!h->keys) return 0; \ + n_buckets = (khint_t)1U << h->bits; \ + mask = n_buckets - 1U; \ + i = last = __kh_h2b(hash, h->bits); \ @@ khashl.h (new) + +#define __KHASHL_IMPL_RESIZE(SCOPE, HType, prefix, khkey_t, __hash_fn, __hash_eq) \ + SCOPE void prefix##_resize(HType *h, khint_t new_n_buckets) { \ -+ khint32_t *new_used = 0; \ ++ khint32_t *new_used = NULL; \ + khint_t j = 0, x = new_n_buckets, n_buckets, new_bits, new_mask; \ + while ((x >>= 1) != 0) ++j; \ + if (new_n_buckets & (new_n_buckets - 1)) ++j; \ @@ khashl.h (new) +#define __KHASHL_IMPL_DEL(SCOPE, HType, prefix, khkey_t, __hash_fn) \ + SCOPE int prefix##_del(HType *h, khint_t i) { \ + khint_t j = i, k, mask, n_buckets; \ -+ if (h->keys == 0) return 0; \ ++ if (!h->keys) return 0; \ + n_buckets = (khint_t)1U<<h->bits; \ + mask = n_buckets - 1U; \ + while (1) { \ 2: 744e1b7198 = 3: bfb20eae37 khashl: fix ensemble lookups on empty table