From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.io!.POSTED.ciao.gmane.io!not-for-mail From: =?utf-8?Q?Ludovic_Court=C3=A8s?= Newsgroups: gmane.lisp.guile.devel Subject: Re: CPU and GC cost of bignums Date: Thu, 06 Feb 2020 14:37:52 +0100 Message-ID: <878slfalan.fsf@gnu.org> References: <87imkmwass.fsf@gnu.org> <87zhdxknf9.fsf@gnu.org> <87y2tgawel.fsf@igalia.com> Mime-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable Injection-Info: ciao.gmane.io; posting-host="ciao.gmane.io:159.69.161.202"; logging-data="112977"; mail-complaints-to="usenet@ciao.gmane.io" User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/26.3 (gnu/linux) Cc: Guile Devel To: Andy Wingo Original-X-From: guile-devel-bounces+guile-devel=m.gmane-mx.org@gnu.org Thu Feb 06 14:38:11 2020 Return-path: Envelope-to: guile-devel@m.gmane-mx.org Original-Received: from lists.gnu.org ([209.51.188.17]) by ciao.gmane.io with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.92) (envelope-from ) id 1izhMB-000TIf-MU for guile-devel@m.gmane-mx.org; Thu, 06 Feb 2020 14:38:11 +0100 Original-Received: from localhost ([::1]:39254 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1izhMA-0001yQ-Ny for guile-devel@m.gmane-mx.org; Thu, 06 Feb 2020 08:38:10 -0500 Original-Received: from eggs.gnu.org ([2001:470:142:3::10]:56854) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1izhLx-0001uj-6z for guile-devel@gnu.org; Thu, 06 Feb 2020 08:37:59 -0500 Original-Received: from fencepost.gnu.org ([2001:470:142:3::e]:48060) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1izhLx-0006a1-2u; Thu, 06 Feb 2020 08:37:57 -0500 Original-Received: from [2001:660:6102:320:e120:2c8f:8909:cdfe] (port=55890 helo=ribbon) by fencepost.gnu.org with esmtpsa (TLS1.2:RSA_AES_256_CBC_SHA1:256) (Exim 4.82) (envelope-from ) id 1izhLv-0002RT-OP; Thu, 06 Feb 2020 08:37:56 -0500 X-URL: http://www.fdn.fr/~lcourtes/ X-Revolutionary-Date: 18 =?utf-8?Q?Pluvi=C3=B4se?= an 228 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: <87y2tgawel.fsf@igalia.com> (Andy Wingo's message of "Thu, 06 Feb 2020 10:37:54 +0100") X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.2.x-3.x [generic] X-BeenThere: guile-devel@gnu.org X-Mailman-Version: 2.1.23 Precedence: list List-Id: "Developers list for Guile, the GNU extensibility library" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: guile-devel-bounces+guile-devel=m.gmane-mx.org@gnu.org Original-Sender: "guile-devel" Xref: news.gmane.io gmane.lisp.guile.devel:20396 Archived-At: Hi! Andy Wingo skribis: > Nice investigation! Perhaps slot-allocation should track live variables > using something that's not bigints, but who knows. Yeah I wondered; it=E2=80=99s not clear whether bitvectors would be more efficient, for instance, although we could make it perhaps locally imperative. > On Wed 05 Feb 2020 17:29, Ludovic Court=C3=A8s writes: > >> /* The next three functions (custom_libgmp_*) are passed to >> mp_set_memory_functions (in GMP) so that memory used by the digits >> themselves is known to the garbage collector. This is needed so >> @@ -237,19 +227,20 @@ finalize_bignum (void *ptr, void *data) >> static void * >> custom_gmp_malloc (size_t alloc_size) >> { >> - return scm_malloc (alloc_size); >> + return scm_gc_malloc (alloc_size, "GMP"); >> } >>=20=20 >> static void * >> custom_gmp_realloc (void *old_ptr, size_t old_size, size_t new_size) >> { >> - return scm_realloc (old_ptr, new_size); >> + return scm_gc_realloc (old_ptr, old_size, new_size, "GMP"); >> } >>=20=20 >> static void >> custom_gmp_free (void *ptr, size_t size) >> { >> - free (ptr); >> + /* Do nothing: all memory allocated by GMP is under GC control and >> + will be freed when needed. */ >> } > > I think this makes sense to me as a short-term fix. The down-side is > that limbs can alias Scheme objects. Yes. To my surprise, on a pure bignum microbenchmark, this is counterproductive: --8<---------------cut here---------------start------------->8--- $ guile ~/src/guile-debugging/bignum-finalizers.scm # 3.0.0 clock utime stime cutime cstime gctime 2.42 6.20 0.17 0.00 0.00 5.62 heap size: 2.0 MiB $ /data/src/guile-3.0/meta/guile ~/src/guile-debugging/bignum-finalizers.s= cm clock utime stime cutime cstime gctime 3.97 10.91 0.15 0.00 0.00 10.60 heap size: 3.0 MiB $ cat ~/src/guile-debugging/bignum-finalizers.scm (use-modules (ice-9 time)) (time (let loop ((n (expt 2 18)) (i 1)) (unless (zero? n) ;; (display ".") (loop (- n 1) (logior 0 (ash i 1)))))) (format #t "heap size: ~a MiB~%" (round (/ (assoc-ref (gc-stats) 'heap-size) (expt 2. 20)))) --8<---------------cut here---------------end--------------->8--- (Here we=E2=80=99re creating ~24 bignums, no more.) I wonder if there=E2=80=99s another part of the story that I=E2=80=99m miss= ing here. Perf report for 3.0.0: --8<---------------cut here---------------start------------->8--- 46.93% guile libgc.so.1.3.6 [.] GC_mark_from 17.61% guile libgc.so.1.3.6 [.] GC_header_cache_miss 9.96% guile libgc.so.1.3.6 [.] GC_add_to_black_list_normal 5.20% guile libgmp.so.10.3.2 [.] __gmpn_lshift_coreisbr 4.13% guile libgc.so.1.3.6 [.] GC_find_header 2.28% guile libgc.so.1.3.6 [.] GC_finalize 2.09% guile libgc.so.1.3.6 [.] GC_base --8<---------------cut here---------------end--------------->8--- With the patch: --8<---------------cut here---------------start------------->8--- 48.40% guile libgc.so.1.3.6 [.] GC_mark_from 17.74% guile libgc.so.1.3.6 [.] GC_header_cache_miss 11.90% guile libgc.so.1.3.6 [.] GC_add_to_black_list_= normal 4.45% guile libgc.so.1.3.6 [.] GC_find_header 2.31% guile libgmp.so.10.3.2 [.] __gmpn_lshift_coreisbr 2.30% guile libgc.so.1.3.6 [.] GC_base 1.73% guile libgc.so.1.3.6 [.] GC_finalize --8<---------------cut here---------------end--------------->8--- IOW, the relative part of computations drops from 5% to 2%. Thoughts? > In the long-term I think we should be representing bignums as > pointerless objects whose first word is the tag and a word count, > followed by inline "limbs" (in the sense of > https://gmplib.org/manual/Nomenclature-and-Types.html#Nomenclature-and-Ty= pes). > Generally we can use the low-level API to work on these > (https://gmplib.org/manual/Low_002dlevel-Functions.html#Low_002dlevel-Fun= ctions), > and if we need to use mpz_t, we can easily create an mpz_t that points > to these values. Yes, that sounds like the right approach longer-term. Note that =E2=80=98m= pz_t=E2=80=99 is exposed through =E2=80=9Cnumbers.h=E2=80=9D, which I guess means we cann= ot change that in 3.0.x. Thanks, Ludo=E2=80=99.