This is a long post. Part one is background to motivate the
implementation outline in part two. If you already understand order
analysis (i.e. the asymptotic analysis of program runtime), then you
already understand everything I'll say in Part 1; you can skip to Part 2.
Part 1 - Motivation
So long as you can work with data of definite size, APL is able to
allocate the correct amount of storage in time proportional to
(assuming that allocation must be accompanied by initialization) the
size of the storage. That's pretty good. (There might be OS-dependent
tricks to finesse the initialization time, but that's not the subject
of this note...)
If you have to work with data of indeterminate size and store that
data in an APL vector or array, that's where things get tricky.
The classic example of this is accumulating data elements from an
input stream of indeterminate length:
0.Initialize an empty vector; this will, while the program is running,
accumulate data elements.
1. If there's no more data to read, we're done. The vector contains
the result.
2. Read a data element from the input stream and append the element to
the vector.
3. Go to step 1.
As this program runs, the vector will take on lengths in the series 0,
1, 2, 3, 4, 5, ... Each time the vector expands, all of the data must
be copied to the new vector before appending the next element. If you
look at copying the data as the "cost" of this algorithm, you'll see
that this is a really inefficient way to do things. The runtime is
O(n^2). In other works, the runtime grows as the square of the input size.
One way to optimize this program is to extend the vector by a fixed
size every time you need more space for the next element. IOW, rather
than making space for one more element, you'd make space for a hundred
or a thousand elements; by doing so, you reduce the number of times
you must copy all the existing data to an expanded vector. This seems
like a smart approach. It definitely gives you better performance for
a data set of a given size. However, looking at the asymptotic limit,
this is still an O(n^2) algorithm.
So how do you improve the runtime of this algorithm...? A common
approach is to double the size of the vector each time you run out of
space. The size of the vector will increase pretty rapidly.
Intuitively, you're giving yourself twice as much time to run a linear
algorithm each time you run out of space for a new element. The
asymptotic runtime won't be linear (you'll still have to stop and copy
at increasingly infrequent intervals), but it'll be better than O(n^2).
What's the downside? Your program will eat more memory than it really
needs. In fact, depending upon where you run out of input, the program
may have allocated up to twice as much memory as it really needs.
Here's where I argue that trading memory for time is a good thing...
Memory is cheap. If you're going to be solving a problme that taxes
physical memory on a modern computer, you (or your employer) can
almost certainly afford to double your machine's memory. Also, memory
is slow. A modern processor can execute lots and lots of cycles in the
time it takes to read or write one word of data in memory. This is why
copies dominate the runtime of many algorithms.
The trick in making this "double the size before copying" algorithm is
to somehow manage that overallocated space. That the subject of Part 2.
Part 2 - Double, Copy, Trim
I haven't yet looked at how all this might fit into GNU APL. Some of
my assumptions may be wrong. This section is intended to provoke
discussion, not to serve as a design sketch.
The "double the size before copying" part of the algorithm seems
simple enough. (Keep in mind that I'll use this phrase repeatedly
without also mentioning the necessary test for having run out of
allocated-but-unused space.) The only tricky parts are (a) knowing
when to do it, (b) using a new bit of header information that keeps
track of allocated size as opposed to actual size, and (c) handling
the new case of mutating an existing variable (specifically, doing an
update-in-place over a previously allocated-but-unused element) rather
than allocating a fresh copy of a precise size and copying the entire
result.
Why is "knowing when to do it" tricky? I'm assuming that GNU APL
evaluates an expression of the form a←a,x by computing the size of a,x
before allocating a new a and copying all the data. We could blindly
double the size of a each time we need to make more room; at the
worst, our programs would use about twice as much memory. But we might
be able to do better...
What we need is an inexpensive way of predicting that a vector may be
subject to repeated expansion.
We could use static analysis of the program text: Every time we see an
expression of the form a←a,... we could choose the "double the size
before copying" technique. We might even strengthen the test by
confirming that the assignment appears inside a loop.
Alternatively, we might somehow look at access patterns. If the
variable is infrequently updated (this assumes that we can have a
timestamp associated with the variable's header), then we might take a
chance and do minimal (i.e. just enough space for the new element)
reallocation. On the other hand, if we're updating that variable
frequently (as we'd do in a tight loop), then it'd make sense to apply
the "double the size before copying" technique.
That's about all I can say for now about the double and copy parts.
What about trim?
Let's assume that we'd like to do better than to potentially double
the runtime size of our GNU APL programs. What techniques might we use
to mitigate that memory growth.
We might set an upper bound on "overhead" memory allocation. (In this
case, the overhead is the allocated-but-unused space consumed by
reserving unused space in variables that might be subject to growth.
That seems like an attractive approach until you consider that
whatever threshold you select at which to stop reserving extra space,
you could reach that threshold before hitting the one part of your
program that's really going to benefit from the optimization. We
really need to make this work without having to tweak interpreter
parameters on a per-program and per-run basis.
One possible approach might be to "garbage-collect" reserved space
upon some trigger condition. (Maybe memory pressure, maybe time, maybe
something else...) The downside is that this can fragment the heap. On
the other hand, we might get away with it thanks to VM and locality of
access; it may take some experiments to work out the best approach.
Another possible approach might be to dynamically prioritize which
variables are subject to reservation of extra space upon expansion,
based upon frequency of updates or how recently the variable was
updated. Again, experimentation may be necessary.
Finally, the same "double the size before copying" technique should be
applied to array assignments (e.g. a[m]←a[m],x).
Appendix
The attached test.apl file contains two functions: test1 and test2.
(I'm tempted to break into Dr. Seuss rhyme, but I'll refrain...)
The test1 function expands a vector by one element each time an
element is added.
The test2 function doubles the size of the vector each time the
current allocation fills up.
For small N, you'd be hard pressed to notice a difference between the
runtime of test1 and test2. For example, try
test1 5
test2 5
test1 50
test2 50
... etc
At some point, you'll see a dramatic difference. On my machine,
there's a noticeable difference at 5000. At 50000, the difference is
stunning.
--
"The secret to creativity is knowing how to hide your sources."
Albert Einstein
http://soundcloud.com/davidlamkins
http://reverbnation.com/lamkins
http://reverbnation.com/lcw
http://lamkins-guitar.com/
http://lamkins.net/
http://successful-lisp.com/