Hello all, This patch changes the way that bignums are allocated, so that digits are now allocated using the GC allocation functions instead of standard malloc/realloc/free.
Without this patch, computing (factorial 100000), where factorial is implemented using the straightforward iterative approach below, causes Guile to allocate a huge amount of memory. This happens because the majority of the memory used by large bignums (the digits themselves) is not allocated by the GC, and so the GC doesn't run until a huge amount of memory has been allocated. (define (factorial n) (define (fac n acc) (if (<= n 1) accum (fac (1- n) (* n acc)))) (fac n 1)) With this patch, (factorial 100000) takes a long time but memory usage is modest. The main reason I haven't already pushed this patch is that there is a slight complication: when you register custom allocation functions for use by GMP, they get used for _all_ allocation, not just for digits. In particular, they get used to allocate the block returned by mpz_get_str (when the first argument is NULL). This means that if the user of mpz_get_str uses the standard "free" to deallocate this block, it will fail badly. This could potentially affect programs which use libguile but also use the GMP functions directly. What do you think? Best, Mark
>From 964e43e579d9be310d5eaecde4c560c01c4c1afc Mon Sep 17 00:00:00 2001 From: Mark H Weaver <m...@netris.org> Date: Tue, 31 May 2011 15:26:41 -0400 Subject: [PATCH] Configure GMP to use GC allocation functions, remove bignum finalizers * libguile/numbers.c (custom_gmp_malloc, custom_gmp_realloc, custom_gmp_free): New static functions used by GMP for allocation. These are just wrappers for scm_gc_malloc, scm_gc_realloc, and scm_gc_free. (scm_init_numbers): Use mp_set_memory_functions to configure GMP to use custom_gmp_{malloc,realloc,free} for memory allocation. (make_bignum): Allocate the mpz_t (and type tag) using scm_gc_malloc, so that the GC will see the pointer to the digits, which are now allocated using custom_gmp_malloc. Previously, scm_gc_malloc_pointerless was used to allocate the mpz_t, and a finalizer was used to free the digits. (finalize_bignum): Remove this static function. (scm_bigprint): Use custom_gmp_free to deallocate the string returned by mpz_get_str. --- libguile/numbers.c | 53 ++++++++++++++++++++++++++++++++++++--------------- 1 files changed, 37 insertions(+), 16 deletions(-) diff --git a/libguile/numbers.c b/libguile/numbers.c index 5aeced6..1bf894a 100644 --- a/libguile/numbers.c +++ b/libguile/numbers.c @@ -172,14 +172,32 @@ scm_from_complex_double (complex double z) static mpz_t z_negative_one; -/* Clear the `mpz_t' embedded in bignum PTR. */ -static void -finalize_bignum (GC_PTR ptr, GC_PTR data) + +/* The next three functions (custom_libgmp_*) are passed to + mp_set_memory_functions (in GMP) so that memory used by the digits + themselves are allocated by the garbage collector. This is needed so + that GC will be run at appropriate times. Otherwise, a program which + creates many large bignums would malloc a huge amount of memory + before the GC runs. */ +static void * +custom_gmp_malloc (size_t alloc_size) +{ + /* Unfortunately we cannot safely use scm_gc_malloc_pointerless here, + because the GMP docs specifically warns that it may use allocated + blocks to hold pointers to other allocated blocks. */ + return scm_gc_malloc (alloc_size, "bignum-digits"); +} + +static void * +custom_gmp_realloc (void *old_ptr, size_t old_size, size_t new_size) { - SCM bignum; + return scm_gc_realloc (old_ptr, old_size, new_size, "bignum-digits"); +} - bignum = PTR2SCM (ptr); - mpz_clear (SCM_I_BIG_MPZ (bignum)); +static void +custom_gmp_free (void *ptr, size_t size) +{ + scm_gc_free (ptr, size, "bignum-digits"); } /* Return a new uninitialized bignum. */ @@ -187,18 +205,12 @@ static inline SCM make_bignum (void) { scm_t_bits *p; - GC_finalization_proc prev_finalizer; - GC_PTR prev_finalizer_data; /* Allocate one word for the type tag and enough room for an `mpz_t'. */ - p = scm_gc_malloc_pointerless (sizeof (scm_t_bits) + sizeof (mpz_t), - "bignum"); + p = scm_gc_malloc (sizeof (scm_t_bits) + sizeof (mpz_t), + "bignum"); p[0] = scm_tc16_big; - GC_REGISTER_FINALIZER_NO_ORDER (p, finalize_bignum, NULL, - &prev_finalizer, - &prev_finalizer_data); - return SCM_PACK (p); } @@ -5360,9 +5372,10 @@ int scm_bigprint (SCM exp, SCM port, scm_print_state *pstate SCM_UNUSED) { char *str = mpz_get_str (NULL, 10, SCM_I_BIG_MPZ (exp)); + size_t len = (size_t) strlen (str); scm_remember_upto_here_1 (exp); - scm_lfwrite (str, (size_t) strlen (str), port); - free (str); + scm_lfwrite (str, len, port); + custom_gmp_free (str, len + 1); return !0; } /*** END nums->strs ***/ @@ -9668,6 +9681,14 @@ scm_init_numbers () { int i; + /* IMPORTANT: mp_set_memory_functions _must_ be called before any GMP + functions are called, or else custom_gmp_realloc and/or + custom_gmp_free could be called on a memory block allocated with + plain malloc, which would be bad. */ + mp_set_memory_functions (custom_gmp_malloc, + custom_gmp_realloc, + custom_gmp_free); + mpz_init_set_si (z_negative_one, -1); /* It may be possible to tune the performance of some algorithms by using -- 1.7.1