This slowness is due to silliness in simp-%sin; setting %piargs to
false changes all this:
(%i1) g(x):=if x=0 then z else sin(g(x-1));
(%o1) g(x):=if x=0 then z else sin(g(x-1))
(%i2) showtime : all$
Evaluation took 0.00 seconds (0.00 elapsed)
(%i3) g(15);
Evaluation took 35.05 seconds (35.05 elapsed)
(%o3)
sin(sin(sin(sin(sin(sin(sin(sin(sin(sin(sin(sin(sin(sin(sin(z)))))))))))))))
(%i4) g(15), %piargs : false;
Evaluation took 0.00 seconds (0.00 elapsed)
(%o4)
sin(sin(sin(sin(sin(sin(sin(sin(sin(sin(sin(sin(sin(sin(sin(z)))))))))))))))
The number of calls to simp-%sin to simplify the n-fold composition
sin(sin(...sin(x))..) is something like 3^n, if I recall correctly.
Barton
"Richard Fateman" <fateman at cs.berkeley.edu> wrote on 02/17/2007 01:06:47
PM:
> Putting the wxmaxima stuff in a hash table might be a way to get it off
the
> property list so that other programs more intensively using the property
> list would not have to shuffle through wxmaxima properties.
>
> I'm not entirely convinced that running the test suite is a good test of
> whether the move-to-front heuristic for the simplifier is worth doing or
> not. The cost to run this heuristic is zero at runtime, so any runtime
> speedup is pure gain.
>
> The length of the plist for %sin in wxmaxima is 46. To say that it is
just
> as fast to get item 1 as item 46 is clearly false. Why does it seem that
in
> the larger benchmark of the test suite that it makes no difference?
Perhaps
> the test is not doing anything particularly time-consuming with respect
to
> simplification, or just doing (+,*,expt) simplification most of the
time,
> and/or this is just a minor enhancement on a very clumsy program.
Consider
> this:
>
> g(x):=if x=0 then z else sin(g(x-1));
>
> How long should it take to compute g(15)? Would you believe my computer
> takes about 28 seconds?
> How much faster is it to compute if the operators property is moved to
the
> front? My computer takes maybe 1/3 second less.
> Why is g(15) so slow? Why does g(16) take time 3X ?
>
>
> .... Note that simplification of + and * and expt expressions are not
done
> by looking for their simplification operators on their property list,
> because it was considered to be inefficient, and the program simplifya
has a
> hack to avoid this property-list access. But that was in 1966.
>
> RJF
>
>
>
> > -----Original Message-----
> > From: maxima-bounces at math.utexas.edu [mailto:maxima-
> > bounces at math.utexas.edu] On Behalf Of Raymond Toy
> > Sent: Saturday, February 17, 2007 10:17 AM
> > To: Barton Willis
> > Cc: fateman at cs.berkeley.edu; maxima at math.utexas.edu
> > Subject: Re: [Maxima] speeding up the simplifier
> >
> > Barton Willis wrote:
> > > I suppose a nice solution would be to move all this property list
> > > stuff into CL hash tables. In trigi.lisp, you'll see that a hash
> > > table is used to store functions for floating point evaluation
> > > of trig functions (I think this innovation is due to Raymond).
> > >
> > >
> > I'm guessing, but I think a hash table lookup would be slower than the
> > finding the first symbol in the property list.
> > > Maxima has functions (I'm going on memory, so some names might be
wrong)
> > > mget, zl-get, putprop, and getprop that all access property list
data.
> > > I sure would be nice to unify all this junk into hash tables with
one
> > > programming interface to this data.
> > >
> > >
> > I had given a little thought about this some time ago. It seemed like
> > an all or nothing change (that is, I couldn't think of a way to only
do
> > a small set of changes, preserving the original parts). Thus, I
didn't
> > try it.
> > Plus, the hashed array stuff is also stored in the plist, and arranged
> > in a very confusing way.
> >
> > Ray
> > _______________________________________________
> > Maxima mailing list
> > Maxima at math.utexas.edu
> > http://www.math.utexas.edu/mailman/listinfo/maxima
>