Re: Weak tables harmful to GC?

[Ludovic Courtès]

Hi Andy,

Andy Wingo  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 ():

--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 10))
  (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 
> 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’.

Re: Weak tables harmful to GC?

[Ludovic Courtès]

Hi,

Ricardo Wurmus  skribis:

> previously I wrote:
>
>> The “guile-awesome” package finished compiling (after about 46 minutes).
>> I’m now testing “guix pull” with a version of Guix that uses
>> “guile-awesome”.
>
> I’m sure I’m doing something wrong (see below for guesses).  Here’s what
> I get:
>
> ./pre-inst-env guix pull
> loading...   26.0% of 645 filesrandom seed for tests: 1509382171
> compiling... 18.9% of 645 filesIn thread:
> ERROR: In procedure return: return used outside of 'with-monad'Error while 
> printing exception.
> compiling... 54.7% of 645 files^C

The error above is the other bug you reported, not related (but just as
serious): .

> I modified build-self.scm to use the modified Guile:
>
> diff --git a/build-aux/build-self.scm b/build-aux/build-self.scm
> index ed8ff5f..9af6504 100644
> --- a/build-aux/build-self.scm
> +++ b/build-aux/build-self.scm
> @@ -126,7 +126,7 @@ running Guile."
>(package->derivation (cond-expand
>   (guile-2.2
>(canonical-package
> -   (specification->package "guile@2.2")))
> +   (specification->package "guile-awesome@2.2")))
>   (else
>(canonical-package
> (specification->package "guile@2.0"))
>
> I also confirmed that the Guile process that is spawned as “bin/guile
> --no-auto-compile /home/rwurmus/guix/scripts/guix pull” is indeed the
> modified Guile, but I noticed that it spawns yet another Guile process
> to load and compile Guix.
>
> I guess that comes from the daemon?  If that’s the case I can’t really
> test this on this big server, because the daemon is currently in use, so
> I can’t just reconfigure it to use the modified Guile.

Your patch above should have led to the use of “guile-awesome” to
compile Guix; I’m not sure why it didn’t.

> When compiling Guix from source with “make -j 32” using that version of
> Guile I got a segfault.

Oh?

Let’s put this on hold since Andy offers a different solution.

Thanks for testing!

Ludo’.

Re: guile 3 update

[Christopher Allan Webber]

Andy Wingo writes:

> Hi :)
>
> On Sun 22 Oct 2017 15:22, Christopher Allan Webber  
> writes:
>
>>  - Could native code compilation also be a step towards WASM, assuming
>>they lend us their GC?
>
> Regarding this question: yes!  Specifically with the "GC" proposal
> (which in reality is much more:
> https://github.com/WebAssembly/gc/blob/master/proposals/gc/Overview.md)
> I think that we will approach WASM's semantic level.  There are some
> open questions of course, like how to deal with the stack and delimited
> continuations, how to do bignums with overflow, etc; but yeah we're
> getting there.
>
> Andy

This is very exciting!

Re: Weak tables harmful to GC?

[Andy Wingo]

Hi!

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.  If it
works, we'll need to adapt weak sets as well.

Andy

>From 6ec4642516eaabf7a63644463a7836eb3efbcd60 Mon Sep 17 00:00:00 2001
From: Andy Wingo 
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.
---
 libguile/weak-table.c | 723 +++---
 1 file changed, 212 insertions(+), 511 deletions(-)

diff --git a/libguile/weak-table.c b/libguile/weak-table.c
index 599c4cf0e..ff8a01fb0 100644
--- a/libguile/weak-table.c
+++ b/libguile/weak-table.c
@@ -1,4 +1,4 @@
-/* Copyright (C) 2011, 2012, 2013, 2014 Free Software Foundation, Inc.
+/* Copyright (C) 2011, 2012, 2013, 2014, 2017 Free Software Foundation, Inc.
  * 
  * This library is free software; you can redistribute it and/or
  * modify it under the terms of the GNU Lesser General Public License
@@ -44,83 +44,62 @@
data, but when you don't have space to store the data in the object.
For example, procedure properties are implemented with weak tables.
 
-   Weak tables are implemented using an open-addressed hash table.
-   Basically this means that there is an array of entries, and the item
-   is expected to be found the slot corresponding to its hash code,
-   modulo the length of the array.
-
-   Collisions are handled using linear probing with the Robin Hood
-   technique.  See Pedro Celis' paper, "Robin Hood Hashing":
-
- http://www.cs.uwaterloo.ca/research/tr/1986/CS-86-14.pdf
-
-   The vector of entries is allocated in such a way that the GC doesn't
-   trace the weak values.  For doubly-weak tables, this means that the
-   entries are allocated as an "atomic" piece of memory.  Key-weak and
-   value-weak tables use a special GC kind with a custom mark procedure.
-   When items are added weakly into table, a disappearing link is
-   registered to their locations.  If the referent is collected, then
-   that link will be zeroed out.
+   This is a normal bucket-and-chain hash table, except that the chain
+   entries are allocated in such a way that the GC doesn't trace the
+   weak values.  For doubly-weak tables, this means that the entries are
+   allocated as an "atomic" piece of memory.  Key-weak and value-weak
+   tables use a special GC kind with a custom mark procedure.  When
+   items are added weakly into table, a disappearing link is registered
+   to their locations.  If the referent is collected, then that link
+   will be zeroed out.
 
An entry in the table consists of the key and the value, together
-   with the hash code of the key.  We munge hash codes so that they are
-   never 0.  In this way we can detect removed entries (key of zero but
-   nonzero hash code), and can then reshuffle elements as needed to
-   maintain the robin hood ordering.
-
-   Compared to buckets-and-chains hash tables, open addressing has the
-   advantage that it is very cache-friendly.  It also uses less memory.
-
-   Implementation-wise, there are two things to note.
-
- 1. We assume that hash codes are evenly distributed across the
-range of unsigned longs.  The actual hash code stored in the
-entry is left-shifted by 1 bit (losing 1 bit of hash precision),
-and then or'd with 1.  In this way we ensure that the hash field
-of an occupied entry is nonzero.  To map to an index, we
-right-shift the hash by one, divide by the size, and take the
-remainder.
-
- 2. Since the weak references are stored in an atomic region 

Re: Weak tables harmful to GC?

[Ricardo Wurmus]

Hi again,

previously I wrote:

> The “guile-awesome” package finished compiling (after about 46 minutes).
> I’m now testing “guix pull” with a version of Guix that uses
> “guile-awesome”.

I’m sure I’m doing something wrong (see below for guesses).  Here’s what
I get:

--8<---cut here---start->8---
./pre-inst-env guix pull
loading...   26.0% of 645 filesrandom seed for tests: 1509382171
compiling... 18.9% of 645 filesIn thread:
ERROR: In procedure return: return used outside of 'with-monad'Error while 
printing exception.
compiling... 54.7% of 645 files^C
--8<---cut here---end--->8---

I modified build-self.scm to use the modified Guile:

--8<---cut here---start->8---
diff --git a/build-aux/build-self.scm b/build-aux/build-self.scm
index ed8ff5f..9af6504 100644
--- a/build-aux/build-self.scm
+++ b/build-aux/build-self.scm
@@ -126,7 +126,7 @@ running Guile."
   (package->derivation (cond-expand
  (guile-2.2
   (canonical-package
-   (specification->package "guile@2.2")))
+   (specification->package "guile-awesome@2.2")))
  (else
   (canonical-package
(specification->package "guile@2.0"))
--8<---cut here---end--->8---

I also confirmed that the Guile process that is spawned as “bin/guile
--no-auto-compile /home/rwurmus/guix/scripts/guix pull” is indeed the
modified Guile, but I noticed that it spawns yet another Guile process
to load and compile Guix.

I guess that comes from the daemon?  If that’s the case I can’t really
test this on this big server, because the daemon is currently in use, so
I can’t just reconfigure it to use the modified Guile.

When compiling Guix from source with “make -j 32” using that version of
Guile I got a segfault.

--
Ricardo

Re: Compiler memory consumption

[Ludovic Courtès]

Hello,

Andy Wingo  skribis:

> On Wed 25 Oct 2017 19:42, l...@gnu.org (Ludovic Courtès) writes:
>
>> In short, compiling the top-level thunk is what’s killing us, because
>> the space and time complexity is proportional to the number of labels
>> therein.
>>
>> Also, our 16K line python.scm file translates into 428K labels, which
>> during slot allocation translates into a dozen of 428K-element intmaps
>> and intsets.  So the compilation cost is space per source line of code
>> is high.
>>
>> Andy, what are your thoughts?
>
> I think that probably these 428K labels are partitioned into a number of
> functions.  It is true that the biggest one takes the most time.  Should
> we attempt to speed this up, or should we try harder to simplify this
> graph even at low optimization levels (e.g. "simplify" pass), or should
> we avoid CSE and periodically split liveness ranges, or should we use a
> different register allocation strategy on large functions?

The space taken by the data structures used to represent functions and
live variables is huge: we’re at 1+ GiB heap after the
‘compute-live-variables’ call for the big top-level function (compiling
the 4K subsequent functions, which are small, does not increase heap
size and is very fast).  I think it’s primarily a space complexity
issue.

Ideally memory consumption would not be proportional to the number of
definitions in a file (top-level statements).  Periodically splitting
liveness ranges could probably help avoid this pathological behavior: it
would place an upper bound on memory consumption.

Hopefully this wouldn’t have any noticeable impact on the generated
code, definitely not for top-level functions like that one.

WDYT?

I’m not sure what it takes to implement this splitting, though!

> Or would a transversal solution like a JIT actually be the solution?
> Or does the stack marking show the same pessimal behavior as the weak
> table, in that it's a large object behind a mark function?

My impression is that these are secondary issues.

Thanks for your feedback!

Ludo’.

Re: Compiler memory consumption

[Andy Wingo]

On Wed 25 Oct 2017 19:42, l...@gnu.org (Ludovic Courtès) writes:

> In short, compiling the top-level thunk is what’s killing us, because
> the space and time complexity is proportional to the number of labels
> therein.
>
> Also, our 16K line python.scm file translates into 428K labels, which
> during slot allocation translates into a dozen of 428K-element intmaps
> and intsets.  So the compilation cost is space per source line of code
> is high.
>
> Andy, what are your thoughts?

I think that probably these 428K labels are partitioned into a number of
functions.  It is true that the biggest one takes the most time.  Should
we attempt to speed this up, or should we try harder to simplify this
graph even at low optimization levels (e.g. "simplify" pass), or should
we avoid CSE and periodically split liveness ranges, or should we use a
different register allocation strategy on large functions?  Or would a
transversal solution like a JIT actually be the solution?  Or does the
stack marking show the same pessimal behavior as the weak table, in that
it's a large object behind a mark function?  I do not know.  I have
tried many of the tests that you have done but I don't have a conclusive
answer.

Andy

Re: Weak tables harmful to GC?

[Ricardo Wurmus]

Hi Ludo,

> I’m attaching updated patches.  I’ve let the Guix build run to
> completion this time.  Let me know if it works for you!

The “guile-awesome” package finished compiling (after about 46 minutes).
I’m now testing “guix pull” with a version of Guix that uses
“guile-awesome”.

I’m very hopeful :)

--
Ricardo

guile 3 update: lowered conditionals

[Andy Wingo]

Hi,

An update on the Guile 3 effort.  Since last week I attacked the
conditional instructions, replacing e.g. "br-if-< A B OFFSET" with a
sequence of "

Re: guile 3 update

[Andy Wingo]

Hi :)

On Sun 22 Oct 2017 15:22, Christopher Allan Webber  
writes:

>  - Could native code compilation also be a step towards WASM, assuming
>they lend us their GC?

Regarding this question: yes!  Specifically with the "GC" proposal
(which in reality is much more:
https://github.com/WebAssembly/gc/blob/master/proposals/gc/Overview.md)
I think that we will approach WASM's semantic level.  There are some
open questions of course, like how to deal with the stack and delimited
continuations, how to do bignums with overflow, etc; but yeah we're
getting there.

Andy

Re: Weak tables harmful to GC?

[Ludovic Courtès]

Hi Ricardo,

Ricardo Wurmus  skribis:

> In language/tree-il/analyze.scm:
>   1053:33  3 Exception thrown while printing backtrace:
> ERROR: In procedure assq: Wrong type argument in position 2 (expecting 
> association list): ((system base pmatch) car . #f)
>
> ice-9/boot-9.scm:760:25: In procedure dispatch-exception:
> ice-9/boot-9.scm:760:25: In procedure assq: Wrong type argument in position 2 
> (expecting association list): ((system base pmatch) car . #f)

It’s a sign that the weak tables were too weak, this time.  :-)

The problem stems from the fact that weak pairs were initialized too
late.  Thus, the first calls to ‘scm_weak_car_pair’ were happening
before the weak-car pair GC descriptor had been initialized; they were
therefore using 0 as their descriptor, and ended up not being traced at
all by the GC.

The fix is to initialize weak pairs before symbols, as in 2.0:

modified   libguile/hashtab.c
@@ -1608,10 +1608,11 @@ scm_c_weak_table_fold (scm_t_hash_fold_fn fn, void *closure,
 
 
 
+/* Initialize weak pairs, used by weak hash tables.  This needs to be
+   done early on because it's used by interned symbols etc.  */
 void
-scm_init_hashtab ()
+scm_init_weak_pairs ()
 {
-  /* Initialize weak pairs.  */
   GC_word wcar_pair_bitmap[GC_BITMAP_SIZE (scm_t_cell)] = { 0 };
   GC_word wcdr_pair_bitmap[GC_BITMAP_SIZE (scm_t_cell)] = { 0 };
 
@@ -1627,6 +1628,11 @@ scm_init_hashtab ()
   wcdr_pair_descr = GC_make_descriptor (wcdr_pair_bitmap,
 	GC_WORD_LEN (scm_t_cell));
 
+}
+
+void
+scm_init_hashtab ()
+{
 #include "libguile/hashtab.x"
 }
 
modified   libguile/hashtab.h
@@ -174,6 +174,7 @@ SCM_API SCM scm_hash_map_to_list (SCM proc, SCM hash);
 SCM_API SCM scm_hash_count (SCM hash, SCM pred);
 SCM_INTERNAL void scm_i_hashtable_print (SCM exp, SCM port, scm_print_state *pstate);
 SCM_INTERNAL void scm_init_hashtab (void);
+SCM_INTERNAL void scm_init_weak_pairs (void);
 
 
 /* Guile 2.2.x (x <= 2) weak-table API.  */
modified   libguile/init.c
@@ -390,7 +390,8 @@ scm_i_init_guile (void *base)
 #ifdef GUILE_DEBUG_MALLOC
   scm_debug_malloc_prehistory ();
 #endif
-  scm_symbols_prehistory ();  /* requires weak_table_prehistory */
+  scm_init_weak_pairs ();
+  scm_symbols_prehistory ();  /* requires weak_pairs */
   scm_modules_prehistory ();
   scm_init_array_handle ();

I’m attaching updated patches.  I’ve let the Guix build run to
completion this time.  Let me know if it works for you!

Ludo’.

>From df8dd0b91adc0fca8fafc098eb8db9650f634652 Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?Ludovic=20Court=C3=A8s?= 
Date: Sat, 21 Oct 2017 16:18:39 -0600
Subject: [PATCH 1/2] Remove weak tables and revert to weak hash tables.

This removes weak-tables.[ch] and reintroduces weak hash tables as
implemented in Guile 2.0 into hashtab.[ch].  This reduces wall-clock
time by more than 15% on some GC-intensive benchmarks (compiling code)
where big weak hash tables are in use, such as source properties.

For more details on the rationale, see
.

* libguile/weak-table.c, libguile/weak-table.h: Remove.
* libguile.h: Don't include "weak-table.h".
* libguile/Makefile.am (libguile_@GUILE_EFFECTIVE_VERSION@_la_SOURCES)
(DOT_X_FILES, DOT_DOC_FILES, modinclude_HEADERS): Remove weak-table.*
files.
* libguile/evalext.c (scm_self_evaluating_p): Remove reference to
scm_tc7_weak_table.
* libguile/hashtab.c (SCM_HASHTABLEF_WEAK_CAR)
(SCM_HASHTABLEF_WEAK_CDR): New macros.
* libguile/hashtab.c (scm_fixup_weak_alist, vacuum_weak_hash_table)
(do_weak_bucket_fixup, weak_bucket_assoc)
(weak_bucket_assoc_by_hash): New function.
(make_hash_table, scm_make_hash_table): Add support for weak hash
tables.
(weak_gc_callback, weak_gc_hook, weak_gc_finalizer)
(scm_c_register_weak_gc_callback, scm_make_weak_key_hash_table)
(scm_make_weak_value_hash_table, scm_make_doubly_weak_hash_table): New
functions.
(SCM_WEAK_TABLE_P): Remove.
(scm_weak_key_hash_table_p, scm_weak_value_hash_table_p)
(scm_doubly_weak_hash_table_p, scm_hash_fn_get_handle_by_hash): New
functions.
(scm_hash_fn_create_handle_x): Add support for weak hash tables.
(get_weak_cdr, weak_pair_cdr): New functions.
(scm_hash_fn_set_x): Add support for weak hash tables.
(scm_hash_fn_remove_x): Likewise.
(scm_hashq_get_handle, scm_hashq_create_handle_x): Likewise.
(scm_hashv_get_handle, scm_hashv_create_handle_x): Likewise.
(scm_hashq_ref, scm_hashq_set_x, scm_hashq_remove_x): Remove special
cases for 'SCM_WEAK_TABLE_P'.
(scm_hashv_ref, scm_hashv_set_x, scm_hashv_remove_x): Likewise.
(scm_hash_ref, scm_hash_set_x, scm_hash_remove_x): Likewise.
(scm_hashx_ref, scm_hashx_set_x, scm_hashx_remove_x): Likewise.
(assv_predicate, assoc_predicate, assx_predicate): Remove.
(scm_hash_map_to_list, scm_internal_hash_fold): Likewise, and check for
deleted entries.
(scm_internal_hash_for_each_handle): Likewise.
(scm_t_ihashx_closure): Remove 'key' field.
(wcar_pair_descr,