# space vs time

## Tim Budd <budd@mist.CS.ORST.EDU>

Thu, 18 Aug 88 16:34:29 pdt

*From comp.compilers*

Related articles |

**space vs time ***budd@mist.CS.ORST.EDU (Tim Budd)* (1988-08-18) |

| List of all articles for this month |

**Date: ** | Thu, 18 Aug 88 16:34:29 pdt |

**From: ** | Tim Budd <budd@mist.CS.ORST.EDU> |

Recently I've been thinking about code generation for APL (yes, APL), for

parallel processors, such as the Cray or the Connection Machine.

In this situation time/space tradeoffs become more obvious.

Consider inner-product, which is a generalized matrix multiplication (a

built-in operation in APL). If we are multiplying a n-by-m matrix with a

m-by-r matrix, resulting in a n-by-r result, there are quite a number of

choices.

1) If we want to optimize for speed, there is a simple log(m) algorithm

which takes n*m*r space. (That is, an algorithm which takes O(log(m))

vector operations, the largest of which operate on vectors of length n*m*r.

My analysis assumes vector operations work in constant time regardless of

the size of the vector).

2) On the other hand, if we don't have n*m*r space there is a slightly

slower algorithm which requires only the minimum n*r space (enough for the

output), but which takes O(m) time.

3) If the results are being further compressed (such as by a reduction

surrounding the inner product), then there are even slower algorithms which

will generate the values one by one, using only O(1) space but, of course,

polynomial time.

Which is the ``correct'' algorithm to generate for the inner product

operator? it depends. sometimes one and sometimes the other.

I'm now trying to find heuristics and/or what hints the programmer might

provide which would help in determining the kind of code to put out.

--tim budd, oregon state university

[For people interested in APL compilation in general, see Tim's recent book

"An APL Compiler" published by Springer. I reviewed it for Computing

Surveys and found it pretty interesting. -John]

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.