I notice that Barton's timings show the same (somewhat unlikely)
situation that I see. The "runtime" and "elapsed time" appear to be the
same. This makes me suspicious that the runtime is not being computed at
all. (in xmaxima 5.9.3)
It seems to me that doing apply("+",list_of_stuff)$ is sometimes about as
fast as tree_reduce("+",list_of_stuff)$. Reversing the order of the
list_of_stuff can make a major difference in speed, shown below.
(%i20) h:makelist(r[i],i,0,120)$
(%i21) g:makelist(r[120-i],i,0,120)$
(%i22) apply("+",h)$
Evaluation took 1.16 seconds (1.16 elapsed)
(%i23) apply("+",g)$
Evaluation took 00.30 seconds (00.30 elapsed) // 4X faster.
... here, using tree_reduce IS faster, either order.
The point of my newsimp patch is to store sums in a hash table, unordered.
And also to do comparisons when necessary (the internal program "great") by
memoization. That means that figuring out the order of r(r(r(r(0))))) vs
r(r(r(....r(0)....))) doesn't need to count how many r's there are, except
once.
I am familiar with the (excellent) profiling tools in Allegro CL, which
easily show that there is normally a large amount of time spent in "great";
my hack decreases this substantially. It does increase the use of memory
though. And also makes the kind of processing that goes on much closer to
what is designed in Maple. (Unique copies of subexpressions, in particular).
I don't know about GCL profiling tools though.
The program simplus (I think this is what Barton means by simp-add?)
implicitly does do a sort, but it is at best a quadratic-time algorithm like
insertion sort. It might even be worse, in the sense that adding 2 sums of n
and m items, it should do a merge, but probably just does n (or m)
insertions, and might even unintentionally be n^3. Since the cost for
comparisons ("great"), even repeated comparisons, is rather high, that is
the other target for improvement.
The benchmarks I used take a long time to compute, essentially,
<big expression> - <the same big expression> because of the clumsiness of
the sorting/merging.
Maybe there are easier ways to do this without breaking anything else.
RJF
-----Original Message-----
From: maxima-admin at math.utexas.edu [mailto:maxima-admin at math.utexas.edu] On
Behalf Of Barton Willis
Sent: Monday, July 17, 2006 4:26 PM
To: Richard Fateman
Cc: maxima at math.utexas.edu
Subject: Re: [Maxima] summertime hacking; making maxima 10X faster or more
-----maxima-admin at math.utexas.edu wrote: -----
>15 years ago I wrote a bunch of patches to the
>Maxima / Macsyma simplifier
>using hash coding and memorization, to make it
>much faster. 10X or more - replacing
> exponential-time routines with constant-time
>routines!
I think the time required to simplify some of
these sums could be doubled with some modest
changes to simp-add. My evidence: (some time
ago RJF and I chatted about this same example)
(%i11) m1:sum(z[i],i,0,200)$
Evaluation took 0.45 seconds (0.45 elapsed)
(%i12) m1 : tree_reduce("+",makelist(z[i],i,0,200))$
Evaluation took 0.00 seconds (0.00 elapsed) <-- average about 0.15 sec
As I remember, simp-add doesn't take advantage of
sorting as well as it might.
Barton
_______________________________________________
Maxima mailing list
Maxima at math.utexas.edu
http://www.math.utexas.edu/mailman/listinfo/maxima