mbox series

[0/3] switch to tombstone-free khashl table

Message ID 20240328101356.300374-1-e@80x24.org (mailing list archive)
Headers show
Series switch to tombstone-free khashl table | expand

Message

Eric Wong March 28, 2024, 10:13 a.m. UTC
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

Comments

Eric Wong March 28, 2024, 10:14 a.m. UTC | #1
Sorry, been running on fumes all week :<
Junio C Hamano March 28, 2024, 3:52 p.m. UTC | #2
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
Eric Wong March 28, 2024, 5:56 p.m. UTC | #3
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