Re: Weak tables harmful to GC?

[ludo@gnu.org (Ludovic Courtès)]

Hi Andy,

Andy Wingo <wingo@igalia.com> skribis:

> As discussed on IRC, what do you think of this patch?  It preserves the
> thread-safety properties of weak tables and just adapts them to be
> bucket-and-chain tables.  Let me know how it works for you.

That was fast!  The code certainly looks nicer than the old entangled
weak hash table code, and it preserves thread-safety, so that’s great.

> If it works, we'll need to adapt weak sets as well.

Yes, though I think weak sets are less critical.

I built libguile with the patch (I haven’t yet taken the time to rebuild
all of Guile).  It works, but unfortunately it still shows quick growth
of the heap on this example (<https://bugs.gnu.org/28590>):

--8<---------------cut here---------------start------------->8---
(use-modules (ice-9 format))

(define (display-heap-size)
  (format #t "heap size: ~,2h MiB~%"
          (/ (assoc-ref (gc-stats) 'heap-size) (expt 2. 20))))

(define table
  (make-weak-key-hash-table))

(let loop ((i 0))
  (unless #f
    (when (zero? (modulo i 100000))
      (pk 'table table)
      (display-heap-size))
    (hashq-set! table (make-list 10) (make-list 10))
    (loop (1+ i))))
--8<---------------cut here---------------end--------------->8---

Could it me that some of the disappearing links are not getting
unregistered?

> From 6ec4642516eaabf7a63644463a7836eb3efbcd60 Mon Sep 17 00:00:00 2001
> From: Andy Wingo <wingo@pobox.com>
> Date: Mon, 30 Oct 2017 18:19:37 +0100
> Subject: [PATCH] Weak tables are now bucket-and-chain tables
>
> This change should make weak tables work better with libgc, as the weak
> components that need mark functions are smaller, so they don't overflow
> the mark queue.  Also this prevents the need to move disappearing
> links.
>
> * libguile/weak-table.c (scm_t_weak_entry): Change to be a hash table
>   chain entry.
>   (struct weak_entry_data, do_read_weak_entry, read_weak_entry): Read
>   out the key and value directly.
>   (GC_move_disappearing_link, move_disappearing_links, move_weak_entry):
>   Remove.
>   (scm_t_weak_table): Rename "entries" member to "buckets", and "size" to
>   "n_buckets".
>   (hash_to_index, entry_distance, rob_from_rich, give_to_poor): Remove.
>   (mark_weak_key_entry, mark_weak_value_entry): Mark a single link, and
>   the next link.
>   (mark_doubly_weak_entry): New kind.
>   (allocate_entry): Allocate a single entry.
>   (add_entry): New helper.
>   (resize_table): Reimplement more like normal hash tables.
>   (vacuum_weak_table): Adapt to new implementation.
>   (weak_table_ref, weak_table_put_x, weak_table_remove_x): Adapt.
>   (make_weak_table): Adapt.
>   (scm_weak_table_clear_x): Actually unregister the links to prevent a
>   memory leak.
>   (scm_c_weak_table_fold): Collect items in an alist, then fold outside
>   the lock.
>   (scm_weak_table_prehistory): Initialize doubly_weak_gc_kind.

[...]

> +mark_weak_key_entry (GC_word *addr, struct GC_ms_entry *mark_stack_ptr,
>                       struct GC_ms_entry *mark_stack_limit, GC_word env)

[...]

>    weak_key_gc_kind =
>      GC_new_kind (GC_new_free_list (),
> -		 GC_MAKE_PROC (GC_new_proc (mark_weak_key_table), 0),
> +		 GC_MAKE_PROC (GC_new_proc (mark_weak_key_entry), 0),
>  		 0, 0);

I think we should avoid custom mark procedures and use a bitmap here, as
recommended in the libgc headers (like ‘wcar_pair_descr’ in weaks.c in
2.0.)

Other than that, it looks good on a cursory look.  We’ll have to do some
more testing afterwards to gain more confidence, like what Ricardo has
been doing.

Thanks a lot for your help!

Ludo’.