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)))