Christian & Marc, my problems are not all of a tail-recursion nature. I just made a very dramatic speedup in a different way, which more or less cuts my cons-cell usage in half. First the drama:
My "Curtis algorithm" calculation for t = 73, s = 14 (included below) formerly took more than 3 hours, on a machine with 2 GB memory. With the new code (now on my web page), it's less than 5 minutes!
I was thinking about what Marc wrote Feb 8, 2005:
on a 32 bit machine, each call to "cons" counts for 24 bytes (each field of the pair takes 4 bytes (header, car, cdr) and there is an extra factor of 2 for the space reserved in the to-space so that the garbage collector can copy the pair if it is live when the GC is performed).
The speedup was simple: I changed my definition of tree from
;; Tree ::= empty | (listof (n Tree)) to ;; Tree ::= empty | (append (n Tree) Tree)
so a tree is now an alternating list of numbers & trees, so that's half the cons cells. First let's go back to Marc's cons = 24 B.
Let's see how much storage a large "polynomials" might use. I include on on my web page tar file a polynomial of length 75299 which starts:
(4 8 4 5 3 5 9 3 5 7 7) (4 8 4 5 3 5 6 6 5 7 7) (4 8 4 5 3 5 3 5 9 7 7)
OK. A list of 11 numbers is 10 cons cells, so 24*10 B, so in the whole polynomial, that's 24*10*75299, but it's also a list, which means 75298 cons cells, so that's
(* 24 (+ 75298 752990)) = 19878912 B = 20 MB
not counting how much space is needed to store the actual numbers (all small integers, as you see). That's a lot, considering that the whole data file takes 1856775 B = 1.8 MB, but 20 MB won't make me page out to disk, with 2 GB RAM (or even 1 GB RAM). But somehow differentiating my polynomials and merging them together takes a lot of memory.
So I just differentiated this large polynomial, and it took 12.7 minutes, including 3.8 minutes GC, and allocated 112648198848 B = 112.6 GB So a lot of calculation is done on that original 20 MB of data, but my point is that we don't want to double the cons cell usage on such a calculation. Now this code doesn't use trees anyway. I just noticed that the "derivative" of this polynomial of length 75299 has itself the smaller length of 56570. Here's my output:
75299 (4 8 4 5 3 5 9 3 5 7 7) (time (D X)) 765468 ms real time, 12.7 minutes 765522 ms cpu time (765256 user, 266 system) 3203 collections accounting for 228700 ms real time, 3.8 minutes 112648198848 bytes allocated 13276 minor faults no major faults 56570 (3 4 4 2 3 5 3 5 9 7 7 7)
Notice that Brad's conjecture of Feb 6, 2005 seems false, as I'm still getting 3203 collections. Brad wrote:
(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.
OK, back to my new slim trees:
gsi adem -
(define zeta '((4 4 1 1 1) (4 2 2 2 1) (4 1 1 2 3) (3 3 2 2 1) (3 2 4 1 1) (3 1 2 4 1) (2 2 4 2 1) (2 2 2 2 3) (1 1 2 4 3))) (D zeta) (Poly->Tree zeta)
gives the output
(D zeta) ()
(Poly->Tree zeta)
(4 (4 (1 (1 (1))) 2 (2 (2 (1))) 1 (1 (2 (3)))) 3 (3 (2 (2 (1))) 2 (4 (1 (1))) 1 (2 (4 (1)))) 2 (2 (4 (2 (1)) 2 (2 (3)))) 1 (1 (2 (4 (3)))))
So zeta is a "cycle", i.e. D(zeta) = 0, and turning zeta into a tree just factors out the first coefficients 4 & 3 terms. But previously I had double the number of parentheses:
(Poly->Tree zeta)
((4 ((4 ((1 ((1 ((1))))))) (2 ((2 ((2 ((1))))))) (1 ((1 ((2 ((3))))))))) (3 ((3 ((2 ((2 ((1))))))) (2 ((4 ((1 ((1))))))) (1 ((2 ((4 ((1))))))))) (2 ((2 ((4 ((2 ((1))))) (2 ((2 ((3))))))))) (1 ((1 ((2 ((4 ((3))))))))))
That was really dumb coding on my part. I should say that for me, it was a pain to modify the code to use half the parentheses, and I failed before, but I did it this time with the debugger! Every time I goofed it up, I got the debugger to print out a variable for me, and gradually sense dawned on me.
The calculation for t = 73, s = 14 doesn't produce much:
(B 15 73 ((1 1 2 2 4 3 5 5 6 5 2 3 5 7 7) (2 3 2 4 3 5 5 6 5 2 3 5 7 7)) ((3 2 2 2 2 4 3 5 6 5 2 3 5 7 7) (6 2 2 2 4 3 5 6 5 2 3 5 7 7)) ((3 5 2 2 2 2 4 5 5 5 3 6 6 5 3) (4 7 2 2 2 4 5 5 5 3 6 6 5 3)) ((5 10 2 2 2 2 2 4 3 3 3 6 6 5 3) (6 11 5 6 2 2 2 2 2 3 5 7 3 3)) ((7 14 2 2 2 2 2 2 2 2 3 5 7 3 3) (8 15 6 2 2 2 2 2 2 4 5 3 3 3)) ((9 2 2 4 1 1 2 4 7 3 3 6 6 5 3) (16 2 2 2 2 2 4 3 3 3 6 6 5 3)) ((10 1 2 4 1 1 2 4 7 3 3 6 6 5 3) (12 2 4 1 1 2 4 7 3 3 6 6 5 3)) ((11 22 2 4 1 1 2 4 1 1 2 4 1 1 1) (12 24 4 1 1 2 4 1 1 2 4 1 1 1)) ((19 2 2 2 2 2 2 2 2 2 3 5 7 3 3) (20 3 6 2 2 2 2 2 2 4 5 3 3 3)) ((25 2 2 4 1 1 2 4 1 1 2 4 3 3 3) (26 3 6 2 3 4 4 1 1 2 4 1 1 1)) ((26 1 2 4 1 1 2 4 1 1 2 4 3 3 3) (28 2 4 1 1 2 4 1 1 2 4 3 3 3)) ((27 6 2 4 1 1 2 4 1 1 2 4 1 1 1) (28 8 4 1 1 2 4 1 1 2 4 1 1 1)) ((28 3 4 4 1 1 2 4 1 1 2 4 1 1 1) (34 2 4 1 1 2 4 1 1 2 4 1 1 1)) ((31 2 2 4 1 1 2 4 1 1 2 4 1 1 1) (32 4 4 1 1 2 4 1 1 2 4 1 1 1)))