Re: Programming languages

In article <P79rzeI98nCLFw1K@xxxxxxxxxxxxxx>,
Richard Herring <richard.herring@xxxxxxxxxxxxxx> wrote:
In message <he4d94$47ja@xxxxxxxxxxxxxxxxxxxx>, Herman Rubin
<hrubin@xxxxxxxxxxxxxxxxxxxx> writes
In article <QMBc+1HBZTBLFwMD@xxxxxxxxxxxxxx>,
Richard Herring <richard.herring@xxxxxxxxxxxxxx> wrote:
In message <he1eoj$25ng@xxxxxxxxxxxxxxxxxxxx>, Herman Rubin
<hrubin@xxxxxxxxxxxxxxxxxxxx> writes
In article <NSb7Z7CuX8ALFw2a@xxxxxxxxxxxxxx>,
Richard Herring <richard.herring@xxxxxxxxxxxxxx> wrote:
In message <hdurji$4koc@xxxxxxxxxxxxxxxxxxxx>, Herman Rubin
<hrubin@xxxxxxxxxxxxxxxxxxxx> writes
In article <64oWjjHh2nALFwjJ@xxxxxxxxxxxxxx>,
Richard Herring <richard.herring@xxxxxxxxxxxxxx> wrote:
In message <1om3g5l6hd74a5fp3t9dp3diob0qk274ar@xxxxxxx>, Ruud Harmsen
<rh@xxxxxxxxx> writes
16 Nov 2009 16:19:50 -0500: hrubin@xxxxxxxxxxxxxxxxxxxx (Herman
Rubin): in sci.lang:

[...]

At the level at which the CPU caches and pipelines instructions and
attempts to predict, they constitute unpredictable interruptions of what
is otherwise an orderly flow of execution, requiring the cache and
pipeline to be flushed.

These are places which occur frequently and are predictable.
Subroutine calls are interruptions of an orderly flow, as the
subroutine may be far away in memory.

But the interruption is orderly, with well-defined entry and exit
points, and the subroutine arguments quite likely already in the right
registers. The compiler may even inline the function if it's small. It
can't inline spaghetti code. Moreover, at every point that's potentially
the target of a goto, the compiler has to discard all cache and register
contents and reload its variables form memory. That's expensive.

Why? There is no reason that the compiler cannot
consider the locations from which a goto can be
reached.

The compiler can "consider" all it likes, but that won't change the fact
that at the target of an unstructured jump, the machine state will be
different according to the route by which it arrived there.

[...]

Few gotos will be called from a large number of places;
on the other hand, functions and other subroutines
will be so called. Consider a goto as a semi-subroutine,
but as part of the local block.

There's an old computer-science joke about the "computed comefrom
statement" which is relevant here.

It's not the goto that's the problem, but the comefrom. A subroutine
always returns to the place it was invoked from (OK, there are
exceptions like Fortran's "alternate return" syntax, but they have the
same problem as unstructured gotos) and the only way to arrive there is
via that return, so the machine state at the point of return is well
defined.

In compiling a subroutine, unless otherwise stated,
gotos are only to and from locations in the subroutine.
Otherwise, those locations have to be declared global.
Thus the compiler need only consider what happens in
those few locations, and does not have to flush.

[...]

It is clearly more
efficient to transfer to a particular location than to place
that location or case number somewhere and call a subroutine
whose only purpose here is to make that transfer.

When you take into account the overheads of flushing caches and
pipelines, there's no "clearly" about it.

Why flush the caches and pipelines? This is the stupidity.

Maintaining consistency is "stupidity"?

Consistency with what? If the location of the goto is
not declared global, it is local to the subprogram.
It seems that computers are not designed to do numerical
computing very well any more.

Anything which HAS TO BE flushed will have to be flushed
even if no gotos are used.

It's unstructured gotos which create your "HAS TO BE" condition.

It is only "unstructured" in the mind of the compiler.
Everything in a finite program is in a real sense
structured. It is just that the structure in not
as trivial as those people trying to design everything
except computation want.

Also, doesn't the pipeline have to be flushed on a
subroutine call? I do not see how it can be otherwise
when calling one not inlineable. This is especially
the case when calling a system subroutine, like a
standard mathematical function.

Unlike structured code, spaghetti code isn't amenable to important
optimization techniques like instruction scheduling, branch predication
and (hardware) branch prediction.

Why not? When dealing with random number generating
routines, one can rather easily calculate branch
prediction.

Not what I'm talking about. The phrase "(hardware) branch prediction"
refers to something the hardware does: in a pipelined processor,
depending on the likely outcome of a conditional branch, it may be much
faster to queue up a sequence of instructions whose results may
sometimes be discarded when the condition is finally determined, rather
than actually branching, which requires the pipeline to be flushed.

Even assuming the pipeline does not have to be flushed,
this is true.

And when writing assembler code, the programmer can take
this into account. A forward goto over a short distance
is one way of doing this.

Not the same thing. The whole point of the hardware technique is to
_avoid_ the use of a "forward goto".

I still do not see why the pipeline has to be flushed on
a short forward goto. Just the intermediate instructions
will be ignored.

There are few numerical algorithms which do not need forward
gotos. But even a backward goto can be a problem.


--
This address is for information only. I do not claim that these views
are those of the Statistics Department or of Purdue University.
Herman Rubin, Department of Statistics, Purdue University
hrubin@xxxxxxxxxxxxxxx Phone: (765)494-6054 FAX: (765)494-0558
.

Relevant Pages

  • Re: Programming languages
    ... they constitute unpredictable interruptions of what ... Subroutine calls are interruptions of an orderly flow, ... the target of a goto, the compiler has to discard all cache and register ... which requires the pipeline to be flushed. ...
    (sci.lang)
  • Re: Problem writing code to go to a label after calling a procedure
    ... >>I first tried to create procedures for parts of the program to avoid ... Thanks for the advice J French. ... I know a good program structure avoids many goto ... subroutine, this is somthing I found that Visual Basic can't do. ...
    (comp.lang.basic.visual.misc)
  • Re: UART RS232 "hello world" really taking shape now.
    ... executed at ELABORATION time - the COMPILER takes ... the hardware just sees a lookup table. ... you could stick with the nice simple "goto address" ... MSG "At B" ...
    (comp.arch.fpga)
  • Re: FORSTY - The Fortran Styler :-)
    ... What's wrong with a subroutine call? ... you *CAN* get by without the goto. ... You artifically put a loop around all the executable code in the ... but just because Fortran has a loop exit construct. ...
    (comp.lang.fortran)
  • Re: FORSTY - The Fortran Styler :-)
    ... I've got a subroutine like that. ... you *CAN* get by without the goto. ... You artifically put a loop around all the executable code in the ... but just because Fortran has a loop exit construct. ...
    (comp.lang.fortran)