From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!.POSTED!not-for-mail From: ludo@gnu.org (Ludovic =?UTF-8?Q?Court=C3=A8s?=) Newsgroups: gmane.lisp.guile.bugs Subject: bug#19180: Weak tables harmful to GC? Date: Tue, 31 Oct 2017 00:13:51 +0100 Message-ID: <87zi88ut3k.fsf__42200.0722297982$1509405258$gmane$org@gnu.org> References: <87wp9gwz8m.fsf@gnu.org> <87fug4o8z2.fsf@pobox.com> <87wp54z3p5.fsf@gnu.org> <87zi9th1i6.fsf_-_@gnu.org> <87y3o454pr.fsf@gnu.org> <87r2tvncs5.fsf@dustycloud.org> <87wp3mwwef.fsf@gnu.org> <87mv4gd0ik.fsf@elephly.net> <87a80eie63.fsf@gnu.org> <87k1zimhmt.fsf@elephly.net> <87bmktn96e.fsf@elephly.net> <87tvyl9n22.fsf@gnu.org> <87r2tnlhno.fsf@elephly.net> <87a8087qz7.fsf@gnu.org> <87she0lf1y.fsf@igalia.com> NNTP-Posting-Host: blaine.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable X-Trace: blaine.gmane.org 1509405258 12172 195.159.176.226 (30 Oct 2017 23:14:18 GMT) X-Complaints-To: usenet@blaine.gmane.org NNTP-Posting-Date: Mon, 30 Oct 2017 23:14:18 +0000 (UTC) User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/25.3 (gnu/linux) Cc: 19180@debbugs.gnu.org, Ricardo Wurmus , guile-devel@gnu.org To: Andy Wingo Original-X-From: bug-guile-bounces+guile-bugs=m.gmane.org@gnu.org Tue Oct 31 00:14:13 2017 Return-path: Envelope-to: guile-bugs@m.gmane.org Original-Received: from lists.gnu.org ([208.118.235.17]) by blaine.gmane.org with esmtp (Exim 4.84_2) (envelope-from ) id 1e9JG0-0002ck-Pf for guile-bugs@m.gmane.org; Tue, 31 Oct 2017 00:14:13 +0100 Original-Received: from localhost ([::1]:42964 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1e9JG7-0006I0-VG for guile-bugs@m.gmane.org; Mon, 30 Oct 2017 19:14:19 -0400 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:47361) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1e9JFs-0006At-VS for bug-guile@gnu.org; Mon, 30 Oct 2017 19:14:08 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1e9JFr-00073G-3L for bug-guile@gnu.org; Mon, 30 Oct 2017 19:14:04 -0400 Original-Received: from debbugs.gnu.org ([208.118.235.43]:34198) by eggs.gnu.org with esmtps (TLS1.0:RSA_AES_128_CBC_SHA1:16) (Exim 4.71) (envelope-from ) id 1e9JFq-00072v-SM for bug-guile@gnu.org; Mon, 30 Oct 2017 19:14:02 -0400 Original-Received: from Debian-debbugs by debbugs.gnu.org with local (Exim 4.84_2) (envelope-from ) id 1e9JFq-00053z-9r for bug-guile@gnu.org; Mon, 30 Oct 2017 19:14:02 -0400 X-Loop: help-debbugs@gnu.org Resent-From: ludo@gnu.org (Ludovic =?UTF-8?Q?Court=C3=A8s?=) Original-Sender: "Debbugs-submit" Resent-CC: bug-guile@gnu.org Resent-Date: Mon, 30 Oct 2017 23:14:02 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 19180 X-GNU-PR-Package: guile X-GNU-PR-Keywords: Original-Received: via spool by 19180-submit@debbugs.gnu.org id=B19180.150940523719444 (code B ref 19180); Mon, 30 Oct 2017 23:14:02 +0000 Original-Received: (at 19180) by debbugs.gnu.org; 30 Oct 2017 23:13:57 +0000 Original-Received: from localhost ([127.0.0.1]:42879 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1e9JFk-00053Y-OY for submit@debbugs.gnu.org; Mon, 30 Oct 2017 19:13:57 -0400 Original-Received: from hera.aquilenet.fr ([141.255.128.1]:39235) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1e9JFi-00053P-RR for 19180@debbugs.gnu.org; Mon, 30 Oct 2017 19:13:55 -0400 Original-Received: from localhost (localhost [127.0.0.1]) by hera.aquilenet.fr (Postfix) with ESMTP id 1FA3CFA43; Tue, 31 Oct 2017 00:13:55 +0100 (CET) X-Virus-Scanned: Debian amavisd-new at aquilenet.fr Original-Received: from hera.aquilenet.fr ([127.0.0.1]) by localhost (hera.aquilenet.fr [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id sb4ssdygCnrL; Tue, 31 Oct 2017 00:13:54 +0100 (CET) Original-Received: from ribbon (unknown [IPv6:2a01:e0a:1d:7270:af76:b9b:ca24:c465]) by hera.aquilenet.fr (Postfix) with ESMTPSA id 65DB0F9DF; Tue, 31 Oct 2017 00:13:53 +0100 (CET) X-URL: http://www.fdn.fr/~lcourtes/ X-Revolutionary-Date: 10 Brumaire an 226 de la =?UTF-8?Q?R=C3=A9volution?= X-PGP-Key-ID: 0x090B11993D9AEBB5 X-PGP-Key: http://www.fdn.fr/~lcourtes/ludovic.asc X-PGP-Fingerprint: 3CE4 6455 8A84 FDC6 9DB4 0CFB 090B 1199 3D9A EBB5 X-OS: x86_64-pc-linux-gnu In-Reply-To: <87she0lf1y.fsf@igalia.com> (Andy Wingo's message of "Mon, 30 Oct 2017 18:29:45 +0100") X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.2.x-3.x [generic] X-Received-From: 208.118.235.43 X-BeenThere: bug-guile@gnu.org List-Id: "Bug reports for GUILE, GNU's Ubiquitous Extension Language" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: bug-guile-bounces+guile-bugs=m.gmane.org@gnu.org Original-Sender: "bug-guile" Xref: news.gmane.org gmane.lisp.guile.bugs:8876 Archived-At: 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=E2=80=99s gre= at. > 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=E2=80=99t yet taken the time to re= build 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 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 > 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 =3D > 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 =E2=80=98wcar_pair_descr=E2=80=99 in= weaks.c in 2.0.) Other than that, it looks good on a cursory look. We=E2=80=99ll have to do= some more testing afterwards to gain more confidence, like what Ricardo has been doing. Thanks a lot for your help! Ludo=E2=80=99.