Re: s48 and bibop garbage collector

On Thu, 25 Feb 2010 15:01:34 +0100
Vladimir Konrad <[email protected]> wrote:

> 
> Hello,
> 
> When I run a simple factorial function (iterative definition, file attached) for one million, like:
> 
> (define x (factorial 1000000))
> 
> the scheme48 (both, 1.8 and 1.9T) with bibop garbage collector starts to allocate a _lot_ of ram
> after a longish while (killed at around 3[GB] allocated).

The BIBOP collector allocates each large object (more than 2^16 bytes
long) in its own block of memory.  If it already has a large enough
block allocated, but unoccupied, it will use that block for the new
object; otherwise, it will use malloc(3) to allocate a new block, just
large enough for the new large object.  The BIBOP GC currently does not
call free(3) on these blocks of memory, even if they become unoccupied.

As a consequence, your ‘benchmark’ causes Scheme 48 to malloc(3) (and
hold on to) at least two blocks of each length divisible by 2^12, from
(2^16 + 2^12) to over 2^20.

> Also, should "-h" option limit the maximum heap even for twospace garbage collector, when the number != 0 ?
> 
> My understanding is that _yes it should_, but just want to make sure (I think it does not in this case).

It should limit the heap, but keep in mind that the heap does not
contain the interpreter, or any shared libraries that are loaded.

The twospace collector does not support the ‘-h 0’ unlimited-heap-size
option.

> (btw, I know that micro-benchmarks do not prove much, my guess is that there could be a bug in scheme48 and
> you might like to know.)

Yes, it's a bug, known at least since mid-January.



If you really want to calculate huge (multi-kilobyte) exact factorials,
the traditional technique for concatenating a huge sequence of strings
using only a two-string concatenation function is to accumulate them
into a list (with the earliest string at the tail of the list),
concatenating the last two strings (the two head-most strings) together
whenever the string at the head of the list is larger; this technique
can be adapted to bignum multiplication (use the logarithm of a bignum
as its size if you can't get its actual length in memory).

See the attachments for an example implementation.

> Please access the attached hyperlink for an important electronic communications disclaimer: http://www.lse.ac.uk/collections/planningAndCorporatePolicy/legalandComplianceTeam/legal/disclaimer.htm

No.

(define (int->x n) (cons (log n) n))
(define (reduce-xs/2 x1 x2) (cons (+ (car x1) (car x2))
				  (* (cdr x1) (cdr x2))))
(define (x-size x) (car x))
(define null-x '(0 . 0))

(define (add-x-to-reducer reducer x)
  (cond
   ((null? reducer)
    (cons x '()))
   (else
    (let* ((reducer-head (car reducer)))
      (if (>= (x-size x) (x-size reducer-head))
	  (add-x-to-reducer (cdr reducer) (reduce-xs/2 x reducer-head))
	  (cons x reducer))))))

(define (add-xs-to-reducer reducer xs)
  (do ((xs xs (cdr xs))
       (reducer reducer (add-x-to-reducer reducer (car xs))))
      ((null? xs) reducer)))

(define (finish-reducer reducer)
  (cond
   ((null? reducer)
    null-x)
   (else
    (do ((x (car reducer) (reduce-xs/2 x (car reducer)))
	 (reducer (cdr reducer) (cdr reducer)))
	((null? reducer) x)))))



(define (huge-factorial n)
  (do ((i 1 (+ i 1))
       (reducer '() (add-x-to-reducer reducer (int->x i))))
      ((> i n) (cdr (finish-reducer reducer)))))

(define (reduce-xs/2 x1 x2) (string-append x2 x1)) ;note reversed args
(define (x-size x) (string-length x))
(define null-x "")

(define (add-x-to-reducer reducer x)
  (cond
   ((null? reducer)
    (cons x '()))
   (else
    (let* ((reducer-head (car reducer)))
      (if (>= (x-size x) (x-size reducer-head))
	  (add-x-to-reducer (cdr reducer) (reduce-xs/2 x reducer-head))
	  (cons x reducer))))))

(define (add-xs-to-reducer reducer xs)
  (do ((xs xs (cdr xs))
       (reducer reducer (add-x-to-reducer reducer (car xs))))
      ((null? xs) reducer)))

(define (finish-reducer reducer)
  (cond
   ((null? reducer)
    null-x)
   (else
    (do ((x (car reducer) (reduce-xs/2 x (car reducer)))
	 (reducer (cdr reducer) (cdr reducer)))
	((null? reducer) x)))))



(define (test-string-reducer n)
  (do ((i 1 (+ i 1))
       (reducer
	(add-x-to-reducer '() "0")
	(add-xs-to-reducer reducer (list ", " (number->string i)))))
      ((> i n) (finish-reducer reducer))))