[Axiom-developer] dense is slower than sparse

[Tim Daly]

> could you please give me some suggestion why my DUP is slower than SUP

This is a significant pile of code you sent. You have to hand-optimize
each line rather than copy SUP. It has nothing to do with fixnum
arithmetic. The difference between an SUP and a DUP representation is
the key to speedups.

In general, a dense representation will be slower than a sparse
representation for the simple reason that the dense representation has
more terms. Given good code I'd expect sparse to outperform dense in
almost every case.

If the sparse representation does an O(1) lookup (such as an array
access or hash table) for terms then it should be approximately as
fast as the dense representation in the worst case. This won't be true
in practice because a dense representation can assume the index of the
next term and can use a straight loop to walk terms. Thus a dense
representation can do:

  for i in 0..maxterm (process term i)

whereas a sparse representation must do

  for i in (lookup(term))..(lookup(term)) (process term i)

and thus the lookup speed is vital. Depending on the cost to process
a term this can be a dominant factor (e.g. adding terms) or not (e.g.
computing the integral of the term). 

Find all of the places where terms are accessed and make sure you
are fully using the fact that you know the bounds.

Another cost tradeoff is that a dense representation knows how large
the result must be whereas a sparse representation does not. So memory
allocation can be fast in a dense representation. If you assume worst
case terms in a sparse representation you can do a fast memory allocate,
collect the nonzero terms, and reallocate. By definition it's still
going to be more expensive. Thus a dense representation can do:

   allocate max memory
   compute all the terms

whereas a sparse does

   compute a term
   add it to a list (or whatever rep it uses)

or 
   allocate max memory
   compute the terms
   compute new memory bound
   allocate smaller memory
   copy the results
   deallocate max memory

So, did you find every place that SUP uses dynamic memory allocation
rather than fore-knowledge? 

Sparse representation can also be clever in storing the terms so
that maximum cancellation occurs (e.g. knowing that X=0 means
that you don't have to compute a lot of terms because they vanish).
To use this trick you need to know a lot about the domain and I
don't see SUP using it anywhere.

Tim