Maxima/Ecl on 32-bit machine cannot evaluate "apply(union, listify({{..}}))"

On Sat, Sep 06, 2008 at 03:54:53PM -0400, Stavros Macrakis wrote:
> On Sat, Sep 6, 2008 at 2:58 PM, Oliver Kullmann <O.Kullmann at swansea.ac.uk>wrote:
> 
> > Regarding union and intersection.
> > The really big speed-up seems to take place when replacing "apply" by
> > "tree_reduce". But this already with 5.15.0 (and with clisp and ecl).
> >
> > Now I downloaded the new nset (CVS), and this speeds up tree_reduce a tiny
> > bit for ecl, and more noticeable for clisp; while for apply nothing happens.
> >
> > Is this as expected?
> >
> 
> Yes, apply has not been changed at all.  The bug that was patched should
> give a large performance increase for x/l/r/tree reduce when the
> intermediate results are large sets.  When that happens depends on exactly
> what arguments you are supplying, and their order, but in many common cases,
> tree_reduce has smaller intermediate results.
>

My (first) results show a clear pattern (on various machines, with CLisp
and with ECL):

 - A union where there is a large overlap between the sets is faster done
   with "apply" (than with "tree_reduce" (or any other "reduce"); the
   extreme case is that where all sets are identical, and in this case
   tree_reduce needs (quite precisely)  2x as much time (and more space).
 - The other extreme is where all sets are rather disjoint, and then
   tree_reduce is much faster than apply.

My library provides now, similar to "lmin", "lmax", functions

 lunion, lintersection

which are just defined as

lunion(L) := tree_reduce(union,L,{})$
lintersection(L) := tree_reduce(intersection,L)$

In this way one is on the "safe side"; though it results in certain cases in
a slowdown (where the sets have large overlaps).

--------------------

My main question is now how to proceed:

In my understanding, one has to take away from the user the worry about
"apply" and various "reduce's", so I've implemented now the above
lunion, lintersection
and also an unrestricted apply:

uapply(_op,L,blocksize) :=  block([l : length(L)],
  if l <= blocksize then apply('_op,L)
  else block([d : divide(l-1, blocksize), res : apply('_op,[first(L)])],
    L : rest(L),
    thru d[1] do (
      res : apply('_op, [res, apply('_op, take_elements(blocksize,L))]),
      L : rest(L, blocksize)
    ),
    if d[2] # 0 then
      apply('_op, [res, apply('_op, take_elements(d[2],L))])
    else
      res))$
/* To be used with "append" etc.: */
uaapply(_op,L) := uapply(_op,L,maximal_argument_length)$


However, I would much appreciate if Maxima would take away these worries from
my (and any other user), and would supply a version of "apply" without restrictions,
and implementations of list-unions and list-intersections which use the best
possibilities available --- the Maxima implementers should be in a better position
than for example me to provide this basic functionality (so that it works well
under "many" circumstances).


Are there plans for Maxima to provide such basic functions?

For me that's the most important question at this point: Shall I now go through
all the application of "apply" and replace it suitably with uaapply, lintersection,
lunion?

> 
> On a different topic, the current union/intersect/etc. functions are pretty
> fast, but could be made faster in many important special cases.  I had not
> done that up to now because I wasn't aware that anyone was using them for
> large arguments.  Now that I know, I'll improve them.
>

Great!

Oliver