How about comparing Factor to the execution of a C program. If only
C used a stack...but it does! The callstack in C keeps a stack frame
for each function, which consists of the arguments to the function,
the return address to the previous stack frame, and the local
variables. You don't have to execute a C program to see what's going
on because you can look at the disassembly and run it in your mind.
Here's an unoptimized C program that computes (e^3)^(3^2)
#include <stdio.h>
#include <math.h>
float foo(float w) {
float x,y,z;
x = exp(w);
y = sqrt(w);
z = pow(x,y);
return z;
}
int main(void) {
printf("%f\n", foo(3.0f));
return 0;
}
// gcc foo.c -lm
Here's what happens in pseudo-assembly language:
push 3.0
call foo
push w
x = call exp
push w
y = call sqrt
push y
push x
z = call pow
drop_stack_frame // foo's stack frame gets destroyed
return z
That is exactly analogous to the factor code:
3
! foo
dup exp
over sqrt
2dup ^
3nip ! drop_stack_frame
! return z
In both cases, we push the function arguments before calling the
function. This is how C/ASM/Factor works. Factor gets away without
naming the function arguments and local variables, but it's exactly
analogous to if you wrote it in C like this:
float foo(float w) {
return pow(exp(w), sqrt(w)); // no temporary x,y,z
}
Notice how the Factor code (above) looks pretty bad--it 3nips the
w,x,y variables. We can optimize it to reduce the number of shuffle
words called by removing some of the copying of the "local" variables.
3 dup exp swap sqrt ^
Now it doesn't leave three temporary variables on the stack when it's
done, and it's clearer how the dataflow looks. However, if we had to
reuse w,x,y at the end, we couldn't optimize as much because we're in
essence throwing their values away as we use them. You can't do this
in C because they stick around til the end of your function, when the
stack frame goes away. All you can do is avoid using local variables.
Now let's explore how this applies to pushing to vectors and adding
to arrays in Factor.
: push ( elt seq -- ) ... ;
: add ( seq elt -- newseq ) ... ;
V{ } dup 1 over push .
V{ 1 }
V{ 1 }
{ } dup 1 add
{ }
{ 1 }
Notice that while using a vector modifies the vector literal, adding
to an array instead creates an entirely new array. Making an
entirely new array is expensive -- if you're willing to pay this
price, chances are you don't need the old array. Thus, the stack
effect is such that it throws this array away for you, rather than
making you do it manually. So, add is optimized for stack shuffling,
even though it still works like the C example above.
In the ideal case, you wouldn't need any temporary/local variables
and each value would be used, and the intermediate result would flow
into the next calculation,
e.g.
3 sqrt exp sq sin tan
tan(sin(sq(exp(sqrt(3))))); // most calculations are not like
this..
So, it turns out stack shuffling is the glue for reusing variables
without naming them, and we need this glue in all but a very few
places where it's natural to optimize it away. From analysis of the
Factor source repository and experience, words that modify a
structure or retain it for later use "dup" their arguments, and words
that return new structures usually do not.
Words that dup their arguments: push, set-nth, nth, set-nth
Words that usually do not dup their arguments: add, remove, prune,
map, subset, >upper
Doug
-------------------------------------------------------------------------
This SF.net email is sponsored by: Microsoft
Defy all challenges. Microsoft(R) Visual Studio 2005.
http://clk.atdmt.com/MRT/go/vse0120000070mrt/direct/01/
_______________________________________________
Factor-talk mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/factor-talk
