Path: utzoo!attcan!uunet!lll-winken!ames!mailrus!cornell!uw-beaver!uw-june!pardo
From: pardo@june.cs.washington.edu (David Keppel)
Newsgroups: comp.lang.misc
Subject: Re: Dynamic array dimensioning
Summary: long, specific example
Message-ID: <6888@june.cs.washington.edu>
Date: 7 Jan 89 19:53:30 GMT
References: <117400002@uxa.cso.uiuc.edu> <827@laura.UUCP>
Reply-To: pardo@cs.washington.edu (David Keppel)
Organization: U of Washington, Computer Science, Seattle
Lines: 129

>In article <117400002@uxa.cso.uiuc.edu> gsg0384@uxa.cso.uiuc.edu writes:
>>[What languages have run-time array sizing in a particular module?]

In article <827@laura.UUCP> hmm@laura.UUCP (Hans-Martin Mosner) writes:
>These languages are quite unrelated to Fortran, but you asked for it:
>Smalltalk, most (all ?) Lisps, some Basics & Pascals, C (if you accept a
>pointer for an array and implement growing by copying)
>[...]
>[Summary: only added cost is an extra indirection]

I'd like to belabor a particular point, namely the difference between
array sizing at procedure invocation, and dynamic array sizing.

In dynamic sizing, a statement "a[i]:=val;" is meaningful for all
values of i (for which there is sufficient memory); the array "a" is
grown if necessary.  In arrays that are sized at procedure invocation,
the array has some fixed upper/lower bound for the duration of the
procedure call.

The first is certainly more flexible.  It is also more expensive, and
for several reasons.  In addition, *both* are (in general) less
efficient than statically-sized (even stack-allocated) arrays since it
is not generally possible to do as much constant folding or remove as
much computation via loop induction.  It is also usually necessary to
keep both a stack pointer and a frame pointer.


Here is a case to ponder:

    functin foo(x:integer);
	s[1..x], t[1..x] : character;
	i integer;

	for i := 1 to x do
	    ... use s[i] & t[i] ...
    }

In function-invocation sizing, the optimizer can determine (at compile
time) that no reference into s or t will ever be outside the range
0..x-1, so no bounds checking is needed.  Also, if the function call
frame looks like:

	+-----------+
	| call stuff|  <- fp
	+-----------+
	| i storage |
	+-----------+
	| s storage |
	|     :     |
	+-----------+
	| t storage |
	|     :     |
	+-----------+
			<- sp

Then access to "i" is always by a constant offset off of the stack
pointer

	movl	fp+4,r0

Access in to s is similarly cheap -- as cheap as a statically-sized
array:

	movl	(fp+4)[r0],r1

Since the size of s and t are bound at runtime, the location of t[i]
is a runtime value relative to both of fp and sp and must be computed
dynamically.  The cheapest (general) way to do this is keep a pointer
to the storage for t.  This pointer lives at a constant offset from
the frame pointer.

	+-----------+
	| call stuff|  <- fp
	+-----------+
	| i storage |
	+-----------+
	| tp storage|
	+-----------+
	| s storage |
	|     :     |

				; assume r0 holds "i"
	mov	(fp+8),r1	; r1 <- pointer to t storage
	mov	r1[r0],r1	; r1 <- t[i]

Thus reference in to an arbitrary array location takes an extra
reference.  [Although the "for" loop may be coded to keep track of
both "i" and "x-i" and thus keep track of t[i] as an offset from "sp",
this only works for two arrays and so does not generalize for the
worst-case cost for access.]

If we are stepping through the array, as in a "for" loop, we can
optimize accesses in memory references by, say, loading the pointer
"tp" into a register.  In certain cases, we need not even allocate "tp"
on the stack, we keep it in a register and/or recompute it on demand.

In the above description, the procedure must have both a frame pointer
and a stack pointer.  This adds an extra few instructions to
call/return, but only for those functions with variable-sized arrays
(probably acceptable).  For the extra price of copying the call frame
(and arguments), we can get rid of the frame pointer.


If the arrays are *dynamically* sized, we lose several things:

* It is impossible to perform loop induction to remove overhead on
  dynamically-sized arrays.  A big problem here is that we must check
  for overflow on every array access.  This is typically a lot of
  extra overhead, a significant portion of the runtime of a given
  function.
* The storage can be allocated on the stack only when there is only
  one dynamically-sized array in a given procedure.  Thus procudure
  entry/exit will generally be expensive (calls a memory allocator)
  even if the array is never resized.
* It's harder to get rid of the frame pointer.
* It is not as often possible to allocate a dynamically-sized array
  on the stack.

As a language designer, one choice is to make all three mechanisms
available and choose the most efficient implementation for each.
Those who rely on more general models will pay the price (code size,
runtime), while those who do not need it will not pay for it.

I hope that this is helpful.

  ;-D on  ( Now if I can just get rid of the array, it'll be *fast* )  Pardo
-- 
		    pardo@cs.washington.edu
    {rutgers,cornell,ucsd,ubc-cs,tektronix}!uw-beaver!june!pardo