[gambit-list] Re: simple unoptimized gsc nontail recursion

Bill Richter richter at math.northwestern.edu
Sun Dec 25 00:06:54 EST 2005


I made a tail recursion improvement (using mutation, as Christian
suggested), and Brad Lucier's conjecture of Feb 6, 2005 becomes true.
Now, on a machine with 2GB memory, I can "differentiate" my polynomial
of length 75299 in 8.2 minutes, with essentially *no* garbage
collection:

(time (pretty-print (Poly-first (D X))))
    495310 ms real time, 8.2 minutes
    495314 ms cpu time (494923 user, 391 system)
    35 collections accounting for 2568 ms real time, 0.0 minutes
    1193260824 bytes allocated
    10180 minor faults
    no major faults

Brad replied to me on Feb 6:

   > (time (pretty-print (Poly-first (D X))))
   >     998093 ms real time, 16.6 minutes
   >     997940 ms cpu time (997840 user, 100 system)
   >     3204 collections accounting for 365525 ms real time (365690 user, 
   > 30 system)
   >     112648202368 bytes allocated
   >     13318 minor faults
   >     3 major faults
   >
   > Did I really use 112.6 gB?  My machine "only" has 1 gB of memory.

   Probably, yes.  Each of the 3204 garbage collections collected on
   average about 30+ megabytes of data, which it could reuse until the
   next GC, etc.  My guess is that if you doubled the amount of real
   memory to 2GB the number of collections would drop to a few
   hundred.


The improvement I made was to replace this non-tail recursive merge
function 

;; merge-1 : (listof X)^2 (X X -> boolean) -> (listof X) 
;; to merge two sorted lists into a longer sorted list, deleting
;; repetitions, using less-than?.
(define (merge-1 shortlist longlist less-than?)
 (cond
   [(empty? shortlist) longlist]
   [(empty? longlist) shortlist]
   [else (let ([a (first shortlist)] [x (first longlist)])
           (cond
             [(equal? a x)
              (merge-1 (rest shortlist) (rest longlist) less-than?)]
             [(less-than? a x) (cons a
                                     (merge-1 (rest shortlist) longlist less-than?))]
             [else (cons x
                         (merge-1 shortlist (rest longlist) less-than?))]))]))


with this tail-recursive merge function (which I then renamed):


;; merge-sort : (listof X)^2 (X X -> boolean) -> (listof X) 
;; to merge two sorted lists into a longer sorted list, deleting
;; repetitions, using less-than?.
;; Tail recursive with mutation. 
(define (merge-sort shortlist longlist less-than?)
  (let ([M (cons 'start longlist)])
             ;; we need a kludge because when we consume longlist,
             ;; there's no pointer left to attach shortlist to.
  (let loop ([shortlist shortlist]
             [p M])
    (cond
     [(empty? shortlist) (rest M)]
     [(empty? (rest p))
      (and (set-rest! p shortlist) (rest M))]
     [else
      (let* ([a (first shortlist)]
             [R (rest p)]
             [x (first R)]
             [RR (rest R)])
        (cond
         [(equal? a x)
          ;; delete x by replacing R by RR
              (and (set-rest! p RR)
                   (loop (rest shortlist) p))]
         [(less-than? a x)
          (and (set-first! R a)
               (set-rest! R (cons x RR))
               (loop (rest shortlist) R))]
         [else
          (loop shortlist (rest p))]))]))))

I feel like there ought to be a more elegant way to code this...



More information about the Gambit-list mailing list