speed and consing (Re: DHARMI project)

[Telford Tendys <telford@triangle.triode.net.au>]

> > One thing that I have noticed is that using `cons' is very expensive
> > with regards to speed. Firstly, cons is quite slow and secondly,
> > the garbage collector turns up more often if you use cons. The trouble
> > is that almost everything uses cons somewhere or other. Does anyone
> > know how to get around this?
> 
> i'm sure you've heard these things before, but...

Actually, I have done buckets of C programming where you have to go
out of your way to allocate dynamic memory, adjusting to scheme where
you have to go out of your way NOT to allocate memory is taking some time.

> if you know the size of your data, use static allocation (array).  if
> your data is uniform, use uniform arrays.  look for array-transform
> primitives (rather than list-transform variants).

Hmmm, using arrays sounds painful and exactly the reason I moved away
from C. I have a matrix SMOB that is reasonable quick and efficient for
data that I can index by integer however, in this case my data is a stack
and surely if you can't use a list to implement a stack then the list
is a useless structure (and we should all go home).

Each cycle does this:

* Scan the stack looking for how many values to pop off and pop them
  (most cases only the top element is popped).

* If the stack is empty then use an absolute calculation to find
  the next element and push it onto the stack.

* If the stack is not empty then use a relative calculation to find
  the next element and push it onto the stack.

So the result is that the top of the stack is pushed and popped very
often but now and then the stack changes size, either growing by 1 or
shrinking by 1 or more.

>  avoid `map', using
> `for-each' and `set-car!' (for lists) or the array equivalent.

I didn't know about set-car! and set-cdr!, I gave these a go so that
the stack keeps it's top value whenever possible and just adjusts the
contents of the cons cell (rather than popping and pushing).
That helps quite a bit but using gprof still shows the mark and sweep
phases of garbage collection to be the two largest consumers of CPU time.

(roughly:
  25% scm_gc_mark
  25% scm_gc_sweep
  25% scm_deval
  25% everything else in the program)

I guess I'll keep looking for ways to cut it down.

	- Tel