[re-sent to -internals; sorry, Chaim]
Chaim Frenkel <[EMAIL PROTECTED]> writes:
> [cc'ed to perl6-internals]
>
> >>>>> "AS" == Ariel Scolnicov <[EMAIL PROTECTED]> writes:
>
> AS> A TIL doesn't stand in the way. You just don't get the same
> AS> advantages (e.g. code compactness, e.g. reasonably easy peephole
> AS> optimisation for unthreaded code) if you try to compile to a TIL.
> AS> Which is not surprising, since Perl is not Forth.
>
> Sorry, I'm not following.
Then I should be the one apologising.
> Why do you lose all these?
Your average Forth word is quite short; certainly much shorter than
your average Perl sub. There are lots of reasons for this; they stem
from the different natures of the languages, as well as different
"knowledge" of what is efficient and what is not.
> Why is a TIL not compact? (Hard to imagine anything more compact.)
The more words defined, the more compact the TIL. In Perl, you'd
never define
sub inc {
$_[0]+1
}
but in Forth you might have cause to say (and apologies for errors;
it's been a while since I last programmed Forth in anger)
: INC 1 + ;
Think of your program (or top-level Forth word) as a tree. Each node
has as sub-nodes all the subs and Perl operators (words) that it uses,
in order. TIL execution is simply in-order execution of the leaves of
this tree. Every time you use a word like INC (instead of saying "1
+"), you gain 2 words ("1 +" is 3 words, but if you think of it as 2
you'll still be on target for space reduction), since you're reusing a
node of the tree in another place. The more words you have that you
continually reuse, the more space you save.
If you (or your compiler) identify these opportunities and use them,
your code size shrinks miraculously. Otherwise it doesn't.
> What does a TIL have to do with peephole optimization? A word has to
> be done or not. If there are some magic combinations of operations that
> are done very regularly, a new word that does that combo could be provided.
> If the representation doesn't allow for certain optimizations, the TIL is
> not the optree, but rather the final executable form. The compiler could
> in fact create new words optimized just for the job.
"Peephole optimisation" in Forth refers to the following: An
unthreaded compiler can work merely by inlining all word definitions.
So your primitives just get strung together, and new compiled words
are also primitives ("DUP +" becomes something like "POP A, PUSH A,
PUSH A; POP A, POP B, ADD A,B, PUSH A", in an appropriately
unspecified machine language). Of course, in practice you _don't_
perform inlining on all the words (that would not be compact). But
this form too has its problems -- you keep on PUSHing and POPping
uselessly. One improvement you can make is to tag each word with
specific information about its stack use. Say your convention is that
the top 4 stack levels always come from registers D,C,B,A (in that
order). Then you can flag each primitive with one of 16 tags, saying
how many stack levels it *can* take from registers instead, and how
many it *can* leave in registers. In fact, with clever coding, your
compiler can figure it out for itself (typically implementations end
each primitive with "JMP SEMI"; instead you can use "JMP PUSH", "JMP
PUSH2", etc., and e.g. "JMP PUSH2" is "PUSH B, PUSH A, JMP SEMI"; and
your compiler can simply look for calls to the unstacking routine and
jumps to the stacking routine). Then it can strip (some of) the
extraneous pushes and pops. You can go a bit further, and have
several versions of the primitives with different flags (e.g. a 1->2
version of DUP is simply "MOV B,A"; then a compiler can compile "DUP
+" as "POP A, MOV B,A, ADD A,B, PUSH A"; if it were a word (": DOUBLE
DUP + ;") then it would have the mode 1->1.
This type of optimisation is relatively easy to implement, and makes a
huge difference compared to threaded code. For carefully-chosen
examples, it generates really good machine code.
BUT...
1. If you can't promise that no words are redefined, you can't even
unthread. Not really a problem for Perl; you can either stick to a
really conservative syntactic analysis or add a pragma (or both).
2. The core Perl words aren't like the core Forth words. So sure, IF
you have something like "+" or method call, then its behaviour has
a simple stack mode (although you probably can't inline method
calls; then again, who can?). But if you have more complex words
(like unpack) then they don't have a good stack mode.
Even `my ($a, $b) = unpack "A*", $str' doesn't have a good stack
mode, unless you have a really clever unpack. And many of your
subs (especially existing ones) return lists, and they won't have
good stack modes. So peephole optimisation wins you less. (Also,
one of the reasons peephole optimisation gets such good Forth press
is that threaded code is so much slower; this can also be seen as
an indictment of threaded code).
OK, I think that's a long enough essay. Sorry for any lack of
clarity!
--
Ariel Scolnicov |"GCAAGAATTGAACTGTAG" | [EMAIL PROTECTED]
Compugen Ltd. |Tel: +972-2-5713025 (Jerusalem) \ We recycle all our Hz
72 Pinhas Rosen St. |Tel: +972-3-7658514 (Main office)`---------------------
Tel-Aviv 69512, ISRAEL |Fax: +972-3-7658555 http://3w.compugen.co.il/~ariels
