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



Here's a fix users can apply immediately to a running Maxima.

:lisp (defun require-set (x context-string)  (cond (($setp x) (cdr x))(t
(merror "Function ~:M expects a set, instead found ~:M" context-string x))))

The results are dramatic:

Test: XXreduce('union,create_list({random(100000)},i,1,1000))$

        lreduce rreduce tree_reduce
Before   1.44    1.38    0.08
After    0.30    0.20         0.05

With the old code, doing this for 10000 took a rather long time.  With the
new code:

        lreduce rreduce tree_reduce
        21.19   17.67    0.35

And with {i}, we see the expected result that lreduce is the worst case and
rreduce is fast.

        lreduce rreduce tree_reduce
        27.28    4.17    0.36

With some additional optimization in the core merge function (reducing list
copies) for this (important) special case, rreduce would become even faster
than tree_reduce.

One note: the new version of require-set will break set operations when
simp:false.  But that is true for large parts of Maxima: turning simp off is
a very dangerous thing.

             -s