Path: csiph.com!v102.xanadu-bbs.net!xanadu-bbs.net!eternal-september.org!feeder.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail From: Walter Banks Newsgroups: comp.lang.forth Subject: Re: Metrics on stack usage Date: Mon, 22 Sep 2014 10:54:59 -0400 Organization: A noiseless patient Spider Lines: 219 Message-ID: <54203843.BD257924@bytecraft.com> References: <541855C0.2558D27D@bytecraft.com> <7xmw9zletd.fsf@ruckus.brouhaha.com> <541891FE.9157C03@bytecraft.com> <2014Sep17.092044@mips.complang.tuwien.ac.at> <5419F72B.F5EC2F16@bytecraft.com> <2014Sep18.134054@mips.complang.tuwien.ac.at> Mime-Version: 1.0 Content-Type: multipart/alternative; boundary="------------81D5DE8C66C33817F91FE127" Injection-Info: mx05.eternal-september.org; posting-host="5fdc219d0f92ef4fb1c3abf3c39d738e"; logging-data="22289"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX190o8+GYON38Ti1rZmWMKBNy5HBHLuDMxA=" X-Mailer: Mozilla 4.79 [en]C-CCK-MCD NSCPCD479 (Windows NT 5.0; U) X-Accept-Language: en Cancel-Lock: sha1:fNmVN4OcxBWJodRNjfR29sZ2x4g= Xref: csiph.com comp.lang.forth:33509 --------------81D5DE8C66C33817F91FE127 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Anton Ertl wrote: > Walter Banks writes: > >One thing that compilers are good at is accounting and if there is an > >advantage to creating a stack allocation scheme across basic blocks > >I think it could be done. The simple question is "why do it?" This is > >not a challenge but a real question. > > Ok, let's consider a Java VM-like instruction set. Keeping a value > (or two) in a stack item within a loop can reduce the number of > (dynamically executed as well as static) instructions significantly. > E.g., it reduced the inner loop of the sieve benchmark from 11 > instructions (7 of which are locals accesses) to 8 (with two locals > accesses and two stack manipulations), giving a speedup of 20% with > the JDK Java VM interpreter. > > In contrast, we found that allocating locals to the stack within basic > blocks does not reduce the number of instructions and is only > profitable if you assume that a local variable access is significantly > more expensive than a stack manipulation instruction; in essence the > basic block optimization replaced a locals loads with an instruction > that corresponds to Forth's DUP or TUCK, so if the stack manipulations > cost the same as a locals load, this does not buy you anything. > > This work comes from: > > url = "http://www.complang.tuwien.ac.at/papers/maierhofer%26ertl98.ps.gz", > > > @Proceedings{cc98, > title = "Compiler Construction (CC'98)", > booktitle = "Compiler Construction (CC'98)", > Thanks for the links. > > Can stack allocation across basic blocks be done? Sure, but can we do > it well? I don't see a heuristic for choosing which variables to keep > on the stack where spring out at me. If viewed like register > allocation, this is like a very small register set with irregular > access rules; the usual register sets are not very good at this kind > of thing, despite decades of research and development; that's why > architectures intended to be used with compilers have settled for > larger, regular ("general-purpose") register sets. Many of the ISA designs have larger general purpose register sets so that they can use open source public domain compiler tools most of which are using old compiler technology. Non orthogonal and special purpose register sets can be supported with current compiler technology especially those using strategy passes that process the full application data and control structure to plan out the actual code implementation. > >You made a comment, "behave like hand-written Forth?" I think that > >this is more than an off hand comment. What makes hand-written > >forth special? and why? > > Many different things, in particular: > > * Shorter definitions than your typical Algol-family language program, > because it's easier to add definitions, and harder to make them long > than in Algol. This can have a real impact on code size. We did a study on C optimization and found that even bad C compilers generated reasonably good code if the source statements were kept short. > * Forth programmers use a wide variety of techniques for dealing with > the limitations of stack-based programming, often very specific to > the program at hand, and exploiting knowledge that the Algol > compiler does not have (because it's not expressed in the Algol > source code). Do you have an example of the kind information that would be useful? I think you are correct but am having a hard time coming up with an example. > * Studies of Forth programs have found fewer dynamic conditional > branches and far more calls and returns than instruction statistics > for e.g., C-compiler generated programs. E.g., compare the date from > with > f%20x86%20Instruction%20Set%20Usage%20for%20DOS%20Windows%20 > Applications%20and%20Its%20Implication%20on%20Superscalar%20Design.pdf What is the underlying reason for lower dynamic conditionals. Is it the higher overall cost for using them encouraging the use of branchless code? The higher call / return metrics is understandable with the macro language origins of Forth. Do you know of any papers on code reliability in Forth applications given that functions don't have a formal interface? (The implication is the series terms in the system reliably are larger than say algol languages) w.. --------------81D5DE8C66C33817F91FE127 Content-Type: text/html; charset=us-ascii Content-Transfer-Encoding: 7bit Anton Ertl wrote:
Walter Banks <walter@bytecraft.com> writes:
>One thing that compilers are good at is accounting and if there is an
>advantage to creating a stack allocation scheme across basic blocks
>I think it could be done. The simple question is "why do it?" This is
>not a challenge but a real question.

Ok, let's consider a Java VM-like instruction set.  Keeping a value
(or two) in a stack item within a loop can reduce the number of
(dynamically executed as well as static) instructions significantly.
E.g., it reduced the inner loop of the sieve benchmark from 11
instructions (7 of which are locals accesses) to 8 (with two locals
accesses and two stack manipulations), giving a speedup of 20% with
the JDK Java VM interpreter.

In contrast, we found that allocating locals to the stack within basic
blocks does not reduce the number of instructions and is only
profitable if you assume that a local variable access is significantly
more expensive than a stack manipulation instruction; in essence the
basic block optimization replaced a locals loads with an instruction
that corresponds to Forth's DUP or TUCK, so if the stack manipulations
cost the same as a locals load, this does not buy you anything.

This work comes from:

  url =          "http://www.complang.tuwien.ac.at/papers/maierhofer%26ertl98.ps.gz",
 

@Proceedings{cc98,
  title =        "Compiler Construction (CC'98)",
  booktitle =    "Compiler Construction (CC'98)",
 

Thanks for the links.
 
Can stack allocation across basic blocks be done?  Sure, but can we do
it well?  I don't see a heuristic for choosing which variables to keep
on the stack where spring out at me.  If viewed like register
allocation, this is like a very small register set with irregular
access rules; the usual register sets are not very good at this kind
of thing, despite decades of research and development; that's why
architectures intended to be used with compilers have settled for
larger, regular ("general-purpose") register sets.
Many of the ISA designs have larger general purpose register sets
so that they can use open source public domain compiler tools most
of which are using old compiler technology.  Non orthogonal and
special purpose register sets can be supported with current compiler
technology especially those using strategy passes that process the full
application data and control structure to plan out the actual code
implementation.
>You made a comment, "behave  like hand-written Forth?"  I think that
>this is more than an off hand comment. What makes hand-written
>forth special?  and why?

Many different things, in particular:

* Shorter definitions than your typical Algol-family language program,
  because it's easier to add definitions, and harder to make them long
  than in Algol.

This can have a real impact on code size. We did a study on C optimization
and found that even bad C compilers generated reasonably good code
if the source statements were kept short.
* Forth programmers use a wide variety of techniques for dealing with
  the limitations of stack-based programming, often very specific to
  the program at hand, and exploiting knowledge that the Algol
  compiler does not have (because it's not expressed in the Algol
  source code).
Do you have an example of the kind information that would be useful?
I think you are correct but am having a hard time coming up with an
example.
* Studies of Forth programs have found fewer dynamic conditional
  branches and far more calls and returns than instruction statistics
  for e.g., C-compiler generated programs.  E.g., compare the date from
  <http://www.complang.tuwien.ac.at/anton/euroforth/ef01/gregg01.pdf> with
<http://eslab.cse.nsysu.edu.tw/publications/paper/conference/Analysis%20o
f%20x86%20Instruction%20Set%20Usage%20for%20DOS%20Windows%20
Applications%20and%20Its%20Implication%20on%20Superscalar%20Design.pdf
What is the underlying reason for lower dynamic conditionals. Is it the
higher overall cost for using them encouraging the use of branchless
code?

The higher call / return metrics is understandable with the macro language
origins of Forth.

Do you know of any papers on code reliability in Forth applications given
that functions don't have a formal interface? (The implication is the series
terms in the system reliably are larger than say algol languages)

w..
 

 
  --------------81D5DE8C66C33817F91FE127--