Re: All languages are equally fit
Herman Rubin
=?ISO-8859-1?Q?Ant=F3nio_Marques?= <ent...@gmail.com> wrote:
>On Nov 6, 9:19=A0pm, Joachim Pense <s...@pense-mainz.eu> wrote:
>> Ant=F3nio Marques (in sci.lang):
>> > On 6 Nov, 18:44, Joachim Pense <s...@pense-mainz.eu> wrote:
>> >> Why do you think higher level
>> >> programming languages exist? They have been invented because it is eas=
>ier
>> >> to write complex programs in them than it is if you write machine code
>> >> that does the equivalent job. Some programming languages are flexible =
>in
>> >> the code they accept precisely to allow for pragmatics in the code.
Machine code, yes. I believe that a properly designed
"higher level" assembler code can be almost as concise,
and every bit as easy to write, as the current high
level languages, which are very definitely weak in many
places.
--
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
hru...@stat.purdue.edu Phone: (765)494-6054 FAX: (765)494-0558
DKleinecke
> In article <afe54dcf-aa3a-4076-bbfe-de821b21a...@d21g2000yqn.googlegroups.com>,
Assuming that by assembly code you mean code that mirrors a computer's
internal instruction set this is a reasonable opinion. But the
results are computer-dependent. The assembly code must be rewritten
for each different species of computer. I do not know how many
versions would required today but at least a half dozen would be
needed. People who aim to code for all computers - like the GNU
project - simply cannot afford that much investment. A business like
Microsoft can cope because it is a near monopoly and simply ignores
all but a few kinds of computers.
Modern compilers work in three (at least steps). The first step reads
the higher-order language and compiles it into an intermediate
language. The second step optimizes the code in the intermediate
language and the third step realizes that language in the internal
instruction set of the target computer. Assembly language refers to
either the intermediate language or the final instruction set. If you
want to all you have to do is interrupt this process after the second
step and meddle with the code.
There are good reasons why nobody actually does this. The assembly
language versions the compiler presents are too hard to understand.
Perhaps better (equals more comprehensible) assembly languages can be
invented (I have done this and decided that nobody cared). But the
real barrier is comprehension. Almost everything done on computers
these days in done in a fashion that almost defeats human
comprehension even when it not a secret. Have you ever tried to
understand the Linux kernel? Or the Gnome window manager? And these
aren't even application programs.
Perhaps someday we will have few enough different kinds of computers
(one would be optimal) and good enough current programs that we can
afford to use assembly language. I don't expect it in my lifetime.
Herman Rubin
DKleinecke <dklei...@gmail.com> wrote:
>On Nov 7, 7:32=A0am, hru...@odds.stat.purdue.edu (Herman Rubin) wrote:
>> In article <afe54dcf-aa3a-4076-bbfe-de821b21a...@d21g2000yqn.googlegroups=
>.com>,
>> =3D?ISO-8859-1?Q?Ant=3DF3nio_Marques?=3D =A0<ento...@gmail.com> wrote:
>> >On Nov 6, 9:19=3DA0pm, Joachim Pense <s...@pense-mainz.eu> wrote:
>> >> Ant=3DF3nio Marques (in sci.lang):
>> >> > On 6 Nov, 18:44, Joachim Pense <s...@pense-mainz.eu> wrote:
>> >> >> Why do you think higher level
>> >> >> programming languages exist? They have been invented because it is =
>eas=3D
>> >ier
>> >> >> to write complex programs in them than it is if you write machine c=
>ode
>> >> >> that does the equivalent job. Some programming languages are flexib=
>le =3D
>> >in
>> >> >> the code they accept precisely to allow for pragmatics in the code.
>> Machine code, yes. =A0I believe that a properly designed
>> "higher level" assembler code can be almost as concise,
>> and every bit as easy to write, as the current high
>> level languages, which are very definitely weak in many
>> places. =A0
>Assuming that by assembly code you mean code that mirrors a computer's
>internal instruction set this is a reasonable opinion. But the
>results are computer-dependent. The assembly code must be rewritten
>for each different species of computer. I do not know how many
>versions would required today but at least a half dozen would be
>needed. People who aim to code for all computers - like the GNU
>project - simply cannot afford that much investment. A business like
>Microsoft can cope because it is a near monopoly and simply ignores
>all but a few kinds of computers.
When one produces programs for generation of non-uniform
(or even uniform) random variables, any procedure which
ignores the actual computer instruction set will be poor.
One can, in an appropriately designed assembler language,
which does NOT mirror a computer's internal instruction
set, but allows it to be deduced, see where the problems
lie. The use of heavily overloaded operators and WEAK
typing allows this to be done.
There are operations which can be done quickly on one
computer, but are slow on another, and vice versa. The
algorithm to be used is computer dependent, but usually
easy to write.
>Modern compilers work in three (at least steps). The first step reads
>the higher-order language and compiles it into an intermediate
>language. The second step optimizes the code in the intermediate
>language and the third step realizes that language in the internal
>instruction set of the target computer. Assembly language refers to
>either the intermediate language or the final instruction set. If you
>want to all you have to do is interrupt this process after the second
>step and meddle with the code.
The problem is that optimizing the second step without
knowing the hardware creates great inefficiencies.
Those of us who know what goes on in hardware have to
keep pointing out to those who do not that generating
an exponential random variable as the negative
logarithm of a uniform is much more expensive than
other methods. BTW, in the area of generation of
random variables, it is not the particular numbers
produced which is relevant, but their distribution,
and different generators produce different results.
>There are good reasons why nobody actually does this. The assembly
>language versions the compiler presents are too hard to understand.
>Perhaps better (equals more comprehensible) assembly languages can be
>invented (I have done this and decided that nobody cared). But the
>real barrier is comprehension. Almost everything done on computers
>these days in done in a fashion that almost defeats human
>comprehension even when it not a secret. Have you ever tried to
>understand the Linux kernel? Or the Gnome window manager? And these
>aren't even application programs.
>Perhaps someday we will have few enough different kinds of computers
>(one would be optimal) and good enough current programs that we can
>afford to use assembly language. I don't expect it in my lifetime.
The question is, what kind of assembly language.
The usual ones are clumsy and long-winded. Cray's
are less clumsy and less long-winded. But the use
of overloaded operators can make things easy.
DKleinecke
> In article <4d2ac6cc-a57e-4cca-a7bf-2360f4976...@m7g2000prd.googlegroups.com>,
There is a very great conceptual difference between the Linux kernel
and a random number generator. Which is more important to mankind?
Herman Rubin
DKleinecke <dklei...@gmail.com> wrote:
>On Nov 8, 5:50=A0pm, hru...@odds.stat.purdue.edu (Herman Rubin) wrote:
<> In article <4d2ac6cc-a57e-4cca-a7bf-2360f4976...@m7g2000prd.googlegroups.=
>com>,
<> DKleinecke =A0<dkleine...@gmail.com> wrote:
<> >On Nov 7, 7:32=3DA0am, hru...@odds.stat.purdue.edu (Herman Rubin) wrote:
<> >> In article <afe54dcf-aa3a-4076-bbfe-de821b21a...@d21g2000yqn.googlegro=
>ups=3D
<> >.com>,
<> >> =3D3D?ISO-8859-1?Q?Ant=3D3DF3nio_Marques?=3D3D =3DA0<ento...@gmail.com=
<> wrote:
<> >> >On Nov 6, 9:19=3D3DA0pm, Joachim Pense <s...@pense-mainz.eu> wrote:
<> >> >> Ant=3D3DF3nio Marques (in sci.lang):
<> >> >> > On 6 Nov, 18:44, Joachim Pense <s...@pense-mainz.eu> wrote:
<> >> >> >> Why do you think higher level
<> >> >> >> programming languages exist? They have been invented because it =
>is =3D
<> >eas=3D3D
<> >> >ier
<> >> >> >> to write complex programs in them than it is if you write machin=
>e c=3D
<> >ode
<> >> >> >> that does the equivalent job. Some programming languages are fle=
>xib=3D
<> >le =3D3D
<> >> >in
<> >> >> >> the code they accept precisely to allow for pragmatics in the co=
>de.
<> >> Machine code, yes. =3DA0I believe that a properly designed
<> >> "higher level" assembler code can be almost as concise,
<> >> and every bit as easy to write, as the current high
<> >> level languages, which are very definitely weak in many
<> >> places. =3DA0
<> >Assuming that by assembly code you mean code that mirrors a computer's
<> >internal instruction set this is a reasonable opinion. =A0But the
<> >results are computer-dependent. The assembly code must be rewritten
<> >for each different species of computer. I do not know how many
<> >versions would required today but at least a half dozen would be
<> >needed. People who aim to code for all computers - like the GNU
<> >project - simply cannot afford that much investment. A business like
<> >Microsoft can cope because it is a near monopoly and simply ignores
<> >all but a few kinds of computers.
<> When one produces programs for generation of non-uniform
<> (or even uniform) random variables, any procedure which
<> ignores the actual computer instruction set will be poor.
<> One can, in an appropriately designed assembler language,
<> which does NOT mirror a computer's internal instruction
<> set, but allows it to be deduced, see where the problems
<> lie. =A0The use of heavily overloaded operators and WEAK
<> typing allows this to be done.
<> There are operations which can be done quickly on one
<> computer, but are slow on another, and vice versa. =A0The
<> algorithm to be used is computer dependent, but usually
<> easy to write.
<> >Modern compilers work in three (at least steps). The first step reads
<> >the higher-order language and compiles it into an intermediate
<> >language. The second step optimizes the code in the intermediate
<> >language and the third step realizes that language in the internal
<> >instruction set of the target computer. Assembly language refers to
<> >either the intermediate language or the final instruction set. If you
<> >want to all you have to do is interrupt this process after the second
<> >step and meddle with the code.
<> The problem is that optimizing the second step without
<> knowing the hardware creates great inefficiencies.
<> Those of us who know what goes on in hardware have to
<> keep pointing out to those who do not that generating
<> an exponential random variable as the negative
<> logarithm of a uniform is much more expensive than
<> other methods. =A0BTW, in the area of generation of
<> random variables, it is not the particular numbers
<> produced which is relevant, but their distribution,
<> and different generators produce different results.
<> >There are good reasons why nobody actually does this. The assembly
<> >language versions the compiler presents are too hard to understand.
<> >Perhaps better (equals more comprehensible) assembly languages can be
<> >invented (I have done this and decided that nobody cared). But the
<> >real barrier is comprehension. =A0Almost everything done on computers
<> >these days in done in a fashion that almost defeats human
<> >comprehension even when it not a secret. Have you ever tried to
<> >understand the Linux kernel? Or the Gnome window manager? And these
<> >aren't even application programs.
<> >Perhaps someday we will have few enough different kinds of computers
<> >(one would be optimal) and good enough current programs that we can
<> >afford to use assembly language. I don't expect it in my lifetime.
<> The question is, what kind of assembly language.
<> The usual ones are clumsy and long-winded. =A0Cray's
<> are less clumsy and less long-winded. =A0But the use
<> of overloaded operators can make things easy.
>There is a very great conceptual difference between the Linux kernel
>and a random number generator. Which is more important to mankind?
Probably a Linux kernel, but does that mean that the other
should not be reasonably available? There are many simulations
being done which involve more than a teranumber of random
variables, and these are used for decisions about nuclear
devices and biological planning.
Food is more important than football, but should we make
football difficult because of this.
Also, it may be that the higher order assemblers of the
type I suggest may make it possible to produce more
efficient Linux kernels in less time. They provide
access to the operations which the current high level
languages do not, with many of the natural computer
operations no longer present in the language, so they
dropped out of the computers.
DKleinecke
> Also, it may be that the higher order assemblers of the
> type I suggest may make it possible to produce more
> efficient Linux kernels in less time. They provide
> access to the operations which the current high level
> languages do not, with many of the natural computer
> operations no longer present in the language, so they
> dropped out of the computers.
Can you offer any examples of natural computer operations that have
dropped out of computers because they are not accessible to current
high level languages? And any examples of how older high level
languages were better (the word "current' in paragraph aboive)?
LEE Sau Dan
>> There is a very great conceptual difference between the Linux
>> kernel and a random number generator. Which is more important to
>> mankind?
Herman> Probably a Linux kernel, but does that mean that the other
Herman> should not be reasonably available?
It's simply non-sense to compare an apple to an orange and ask which is
more "important".
"more important than" is not a total-order relation. You cannot
randomly pick two things and determine whether one is _in general_ more
important than the other.
A Linux kernel is important for making a machine run applications that
you need. But a random number generator is also important for
encryption and many other algorithms.
Herman> Food is more important than football, but should we make
Herman> football difficult because of this.
Policeman vs. fireman. Which is more important?
--
Lee Sau Dan 李守敦 ~{@nJX6X~}
E-mail: dan...@informatik.uni-freiburg.de
Home page: http://www.informatik.uni-freiburg.de/~danlee
Herman Rubin
DKleinecke <dklei...@gmail.com> wrote:
>On Nov 9, 9:46=A0am, hru...@odds.stat.purdue.edu (Herman Rubin) wrote:
>> Also, it may be that the higher order assemblers of the
>> type I suggest may make it possible to produce more
>> efficient Linux kernels in less time. =A0They provide
>> access to the operations which the current high level
>> languages do not, with many of the natural computer
>> operations no longer present in the language, so they
>> dropped out of the computers.
>Can you offer any examples of natural computer operations that have
>dropped out of computers because they are not accessible to current
>high level languages? And any examples of how older high level
>languages were better (the word "current' in paragraph aboive)?
High level languages rarely if ever, to my knowledge, had
these operations. Many of the early computers had division
giving an integer quotient and a remainder in one operation;
I have not seen that lately. Also, the separation of a
floating point number into exponent and mantissa, and the
converse production of floats. Fixed point (not integer)
arithmetic. Multiplication giving both the most and least
significant parts, both for fixed point and floating point
numbers. Unnormalized floating arithmetic. Boolean operations
on fixed point numbers, or on floating point.
DKleinecke
> In article <cfef2492-e489-42dd-aeb9-765c3e7ce...@12g2000pri.googlegroups.com>,
Thank you the list.
It seem to me that all of your examples are too hardware dependent to
be accomodated in a general purpose higher order language. The authors
of C would tell you that these are, because of the machine dependence,
more suitable for handling as subroutines than as operations of the
language. I would agree. You will find suitable subroutines in C
subroutine libraries.
C relegated input-output to subroutines for the same reason and
thereby offended a great many people at the time it came out.
So far as I know all modern higher-order languages are descended from
C and share its attributes.
Joachim Pense
if Ada counts as modern, it descended from Pascal. Then, we have LISP
descendants like Scheme, and Postscript coming from FORTH. And Visual Basic
coming from Basic.
Joachim
Helmut Wollmersdorfer
Linux kernel needs system programming. I did system programming in
assembly language during 8 years of my life and I _never_ needed
floating point operations. But I agree with you that assembly language
allows very efficient coding in the area of systems programming - with
the disadvantage of poor portability.
Helmut Wollmersdorfer
LEE Sau Dan
>> Can you offer any examples of natural computer operations that
>> have dropped out of computers because they are not accessible to
>> current high level languages? And any examples of how older high
>> level languages were better (the word "current' in paragraph
>> aboive)?
Herman> High level languages rarely if ever, to my knowledge, had
Herman> these operations. Many of the early computers had division
Herman> giving an integer quotient and a remainder in one operation;
Herman> I have not seen that lately.
But the Intel x86 family has such an instruction, and this is inherited
by all processors in that family, including the newest GHz processors
from Intel.
Herman> Multiplication giving both the most and least significant
Herman> parts, both for fixed point and floating point numbers.
Herman> Unnormalized floating arithmetic.
Denormalized floating points numbers is employed by the IEEE754 standard
to represent very small (in magnitude) numbers. Modern processors all
follow this standard when implementing floating point arithmetic.
http://en.wikipedia.org/wiki/Denormal_number
António Marques
As I read Herman, I think he was saying 'current' as opposed to 'future
hypothetical', rather than to 'old'.
> It seem to me that all of your examples are too hardware dependent to
> be accomodated in a general purpose higher order language. The authors
> of C would tell you that these are, because of the machine dependence,
> more suitable for handling as subroutines than as operations of the
> language. I would agree. You will find suitable subroutines in C
> subroutine libraries.
I would disagree. It's awful that there's no way to both know the
quotient and remainder with a single statement - not only clumsy, but it
forces you to do the division twice (or do some other costly
computation). And there is no way this can be adequately pushed to a
library - unless, perhaps, the library is ASM, then you at least don't
get extra penalties.
> C relegated input-output to subroutines for the same reason and
> thereby offended a great many people at the time it came out.
>
> So far as I know all modern higher-order languages are descended from
> C and share its attributes.
What?? Lisp, Smalltalk, Eiffel, Haskell, are descended from C?? (Rebol?
Ruby? Javascript, even?)
Herman Rubin
DKleinecke <dklei...@gmail.com> wrote:
>On Nov 10, 2:06=A0pm, hru...@odds.stat.purdue.edu (Herman Rubin) wrote:
>> In article <cfef2492-e489-42dd-aeb9-765c3e7ce...@12g2000pri.googlegroups.=
>com>,
>> DKleinecke =A0<dkleine...@gmail.com> wrote:
>> >On Nov 9, 9:46=3DA0am, hru...@odds.stat.purdue.edu (Herman Rubin) wrote:
>> >> Also, it may be that the higher order assemblers of the
>> >> type I suggest may make it possible to produce more
>> >> efficient Linux kernels in less time. =3DA0They provide
>> >> access to the operations which the current high level
>> >> languages do not, with many of the natural computer
>> >> operations no longer present in the language, so they
>> >> dropped out of the computers.
>> >Can you offer any examples of natural computer operations that have
>> >dropped out of computers because they are not accessible to current
>> >high level languages? And any examples of how older high level
>> >languages were better (the word "current' in paragraph aboive)?
>> High level languages rarely if ever, to my knowledge, had
>> these operations. =A0Many of the early computers had division
>> giving an integer quotient and a remainder in one operation;
>> I have not seen that lately. =A0Also, the separation of a
>> floating point number into exponent and mantissa, and the
>> converse production of floats. =A0Fixed point (not integer)
>> arithmetic. =A0Multiplication giving both the most and least
>> significant parts, both for fixed point and floating point
>> numbers. =A0Unnormalized floating arithmetic. =A0Boolean operations
>> on fixed point numbers, or on floating point.
>Thank you the list.
>It seem to me that all of your examples are too hardware dependent to
>be accomodated in a general purpose higher order language. The authors
>of C would tell you that these are, because of the machine dependence,
>more suitable for handling as subroutines than as operations of the
>language. I would agree. You will find suitable subroutines in C
>subroutine libraries.
Not all of them are that hardware dependent, and there
are needs for hardware dependent operations even in
higher level language. Conversion between integers
and floats is very much hardware dependent.
Also, subroutine accesses are SLOW. The VAX C subroutine
for frexp, later replaced by the machine dependent one, was
so slow that the cost of preparing for the square root or
logarithm routine was far greater than the cost of those
routines, and those are not that cheap.
>C relegated input-output to subroutines for the same reason and
>thereby offended a great many people at the time it came out.
>So far as I know all modern higher-order languages are descended from
>C and share its attributes.
Not so. We still have Fortran, Pascal, Forth, Haskell,
and many others not descended from C.
Also, a language can be descended from C and not share
these attributes.
DKleinecke
> DKleinecke wrote:
> > So far as I know all modern higher-order languages are descended from
> > C and share its attributes.
>
> What?? Lisp, Smalltalk, Eiffel, Haskell, are descended from C?? (Rebol?
> Ruby? Javascript, even?)
Some people seem to have a different notion of what "modern" means
than I do. I don't know anything about Rebol but Ruby and Javascript
seem like obvious C descendents to me. Of course i may have a
different idea of what "C descendent" means than some other people.
Herman Rubin
LEE Sau Dan <dan...@informatik.uni-freiburg.de> wrote:
>>>>>> "Herman" =3D=3D Herman Rubin <hru...@odds.stat.purdue.edu> writes:
> >> Can you offer any examples of natural computer operations that
> >> have dropped out of computers because they are not accessible to
> >> current high level languages? And any examples of how older high
> >> level languages were better (the word "current' in paragraph
> >> aboive)?
> Herman> High level languages rarely if ever, to my knowledge, had
> Herman> these operations. Many of the early computers had division
> Herman> giving an integer quotient and a remainder in one operation;
> Herman> I have not seen that lately.=20=20
>But the Intel x86 family has such an instruction, and this is inherited
>by all processors in that family, including the newest GHz processors
>from Intel.
> Herman> Multiplication giving both the most and least significant
> Herman> parts, both for fixed point and floating point numbers.
> Herman> Unnormalized floating arithmetic.
>Denormalized floating points numbers is employed by the IEEE754 standard
>to represent very small (in magnitude) numbers. Modern processors all
>follow this standard when implementing floating point arithmetic.
It is needed for usual sized numbers. Most computers are
so slow in integer multiplication that one wants to use
floats for multiple precision. This is hard to do, and
inefficient, without unnormalized numbers; one wants the
exponents of the various parts to be in arithmetic progression,
or even the same if keeping the parts ordered. Try doing
this with unnormalized numbers.
Multiplying denormalized numbers will give underflow or
zero; they do not behave as wanted.
> http://en.wikipedia.org/wiki/Denormal_number
>--=20
>Lee Sau Dan =A7=F5=A6u=B4=B0 ~=
>{@nJX6X~}
>E-mail: dan...@informatik.uni-freiburg.de
>Home page: http://www.informatik.uni-freiburg.de/~danlee
Helmut Wollmersdorfer
Algol was first (1958) and got major improvement by Backus & Naur, Wirth
et. al. (1960). Algol had support of structured programming, lexical
scope, code blocks and formal syntax definition ('BNF').
IMHO all programming languages, including modern versions of Fortran,
Cobol and Basic are influenced by Algol.
Helmut Wollmersdorfer
LEE Sau Dan
Helmut> Algol was first (1958) and got major improvement by Backus &
Helmut> Naur, Wirth et. al. (1960). Algol had support of structured
Helmut> programming, lexical scope, code blocks and formal syntax
Helmut> definition ('BNF').
Helmut> IMHO all programming languages, including modern versions of
Helmut> Fortran, Cobol and Basic are influenced by Algol.
So, Assembly languages aren't "programming languages"?
How much are Forth, Postscript, LISP influenced by Algol?
--
Lee Sau Dan 李守敦 ~{@nJX6X~}
Helmut Wollmersdorfer
>>>>>> "Helmut" == Helmut Wollmersdorfer <hel...@wollmersdorfer.at> writes:
>
> Helmut> Algol was first (1958) and got major improvement by Backus &
> Helmut> Naur, Wirth et. al. (1960). Algol had support of structured
> Helmut> programming, lexical scope, code blocks and formal syntax
> Helmut> definition ('BNF').
> Helmut> IMHO all programming languages, including modern versions of
> Helmut> Fortran, Cobol and Basic are influenced by Algol.
> So, Assembly languages aren't "programming languages"?
Of course they are, but not 'higher' ones.
> How much are Forth, Postscript, LISP influenced by Algol?
How _much_ I don't know.
Helmut Wollmersdorfer
António Marques
> On Nov 11, 9:08 am, António Marques<m...@sapo.pt> wrote:
>> DKleinecke wrote:
>
>>> So far as I know all modern higher-order languages are descended from
>>> C and share its attributes.
>>
>> What?? Lisp, Smalltalk, Eiffel, Haskell, are descended from C?? (Rebol?
>> Ruby? Javascript, even?)
>
> Some people seem to have a different notion of what "modern" means
> than I do.
To me at least 'modern' means something which is keeping pace with the
latest developments in its field or even leading it. What does it matter
when it first appeared? To determine affiliation? Eiffel, Haskell and
the dialects of Lisp and Smalltalk in use today all appeared after C.
> I don't know anything about Rebol but Ruby and Javascript
> seem like obvious C descendents to me. Of course i may have a
> different idea of what "C descendent" means than some other people.
To me, a 'descendent' means inspired by, following similar principles,
derived from, and the like. Ruby or Javascript have very little to do
with C by any of those criteria. Javascript does use {}, [], =, == and
so on similarly, but that's merely cosmetics.
And really, forgetting cosmetics, how many real-world languages are
there inspired by C? C++, C#, Java, Python, PHP ('inspired' reaching its
limit) and little else. Perl with its weird grammar is certainly no example.
DKleinecke
C is not a modern computer language. C++ is just on the edge and will
shortly stop being modern. Likewise Java.
C is an extremely basic language and it is almost impossible to create
a language, knowing C, without descending from it. It's salient
characteristics are nesting blocks, structured programming constructs,
the relegation of all machine-dependent matters to sub-routines and
its type system.
The brand new Go language looks good to me because it fixes the parts
of C that were broken - header files, the preprocessor and how types
are declared and adds two things that make it modern - concurrent
programming and objects. I intend to make a serious attempt to use Go.
I observe that they may have to change its name. Maybe G?
LEE Sau Dan
António> And really, forgetting cosmetics, how many real-world
António> languages are there inspired by C? C++, C#, Java, Python,
António> PHP ('inspired' reaching its limit) and little else. Perl
António> with its weird grammar is certainly no example.
Perl syntax has a C-like subset. And I think that is inherited
indirectly via awk-like languages.
LEE Sau Dan
DKleinecke> C is an extremely basic language and it is almost
DKleinecke> impossible to create a language, knowing C, without
DKleinecke> descending from it.
I've known C for almost 2 decades. But I've also designed new
small-scale, special languages that do not show any resemblance to C.
They're LISP-like or XML-based. These latter are much better suited for
*declarative* languages (e.g. rule-based languages) than imperative
languages. Look at XSL, for instance, and tell me which part of it
looks like C. How about SQL?
DKleinecke> It's salient characteristics are nesting blocks,
DKleinecke> structured programming constructs, the relegation of all
DKleinecke> machine-dependent matters to sub-routines and its type
DKleinecke> system.
All of these are mainly for languages of an imperative nature.
Helmut Wollmersdorfer
>>>>>> "António" == António Marques <m....@sapo.pt> writes:
>
> António> And really, forgetting cosmetics, how many real-world
> António> languages are there inspired by C? C++, C#, Java, Python,
> António> PHP ('inspired' reaching its limit) and little else. Perl
> António> with its weird grammar is certainly no example.
> Perl syntax has a C-like subset. And I think that is inherited
> indirectly via awk-like languages.
Read from Larry Wall himself:
http://www.wall.org/~larry/pm.html
----quote---
When I started designing Perl, I explicitly set out to deconstruct all
the computer languages I knew and recombine or reconstruct them in a
different way, because there were many things I liked about other
languages, and many things I disliked. I lovingly reused features from
many languages. (I suppose a Modernist would say I stole the features,
since Modernists are hung up about originality.) Whatever the verb you
choose, I've done it over the course of the years from C, sh, csh, grep,
sed, awk, Fortran, COBOL, PL/I, BASIC-PLUS, SNOBOL, Lisp, Ada, C++, and
Python.
----end of quote----
Helmut Wollmersdorfer
Joachim Pense
>>>>>> "António" == António Marques <m....@sapo.pt> writes:
>
> António> And really, forgetting cosmetics, how many real-world
> António> languages are there inspired by C? C++, C#, Java, Python,
> António> PHP ('inspired' reaching its limit) and little else. Perl
> António> with its weird grammar is certainly no example.
>
> Perl syntax has a C-like subset. And I think that is inherited
> indirectly via awk-like languages.
>
I think that it was put into the Language directly. "Perl"
means "Pathologically Eclectic Rubbish Lister", and eclectic it is for
sure. Nevertheless, in my opinion one of the most elegant and best designed
of all imperative programming languages. (Now they'll all come and shoot
me).
Joachim
Herman Rubin
DKleinecke <dklei...@gmail.com> wrote:>> > On Nov 11, 9:08 am, Ant=F3nio Marques<m...@sapo.pt> =A0wrote:
>> >> DKleinecke wrote:
>> >>> So far as I know all modern higher-order languages are descended from
>> >>> C and share its attributes.
>> >> What?? Lisp, Smalltalk, Eiffel, Haskell, are descended from C?? (Rebol=
>?
>> >> Ruby? Javascript, even?)
...............
>C is not a modern computer language. C++ is just on the edge and will
>shortly stop being modern. Likewise Java.
>C is an extremely basic language and it is almost impossible to create
>a language, knowing C, without descending from it. It's salient
>characteristics are nesting blocks, structured programming constructs,
>the relegation of all machine-dependent matters to sub-routines and
>its type system.
Nesting blocks goes back to Fortran at least.
As with many others, I find "structured programming"
highly inefficient; even the advocates have had to
find ways around using it strictly. There is a paper
criticizing the attempts to prohibit gotos by a Rubin,
no relation to me, which I believe is quite clear; it
uses a simple Fortran program and compares the two.
There are other cases where I see no good way out of
using gotos, especially in "state machines", but also
elsewhere.
Relegating all machine-dependent matters to subroutines
can be VERY expensive.
As for the type system, it needs to be arbitrarily
extensible. Too many types are basically lacking,
and this inhibits including them in hardware.
>The brand new Go language looks good to me because it fixes the parts
>of C that were broken - header files, the preprocessor and how types
>are declared and adds two things that make it modern - concurrent
>programming and objects. I intend to make a serious attempt to use Go.
>I observe that they may have to change its name. Maybe G?
Herman Rubin
>Helmut Wollmersdorfer
This is why there needs to be a high level assembler;
it will allow better portability and still efficient
coding.
I have no access to assistants, and I do not believe
that a good language can be produced without more
than one person doing it. Also, my research consists
in probability and mathematical statistics, and they
do influence what I see as missing.
One simple item missing in all programming languages
I know is the possibility of a list of results to
the left of the replacement symbol. This would enable
those results to be produced and stored as convenient,
in registers or in memory, instead of listing their
addresses in the arguments, which requires passing
the addresses and putting all the results in memory.
LEE Sau Dan
Herman> One simple item missing in all programming languages I know
Herman> is the possibility of a list of results to the left of the
Herman> replacement symbol. This would enable those results to be
Herman> produced and stored as convenient, in registers or in
Herman> memory, instead of listing their addresses in the arguments,
Herman> which requires passing the addresses and putting all the
Herman> results in memory.
Have you ever looked at Perl?
e.g. to swap 2 variables in Perl, one can simply write:
($a, $b) = ($b, $a); # swap $a and $b
No need to (uglily) introduce a temp. variable.
and of course, the list can be longer:
($a, $b, $c, $d) = ($b, $c, $d, $a); # rotate left
This syntax also allows you get the multiple values returned from a
single function:
($a, $b, $c) = split(/,/, "a,b,c");
And Perl is not the only language with such a convenience. Prolog has
something analoguous and provides a variable unification mechanism.
LEE Sau Dan
Herman> Nesting blocks goes back to Fortran at least.
Herman> As with many others, I find "structured programming" highly
Herman> inefficient; even the advocates have had to find ways around
Herman> using it strictly.
Inefficient when you're writing tiny programs (e.g. <500 lines).
However, when you need to develop a big program (e.g. >10000 lines),
you'll find structuring indispensible. Without structuring the code
properly, you'll find the program unmanageable and soon lose track of
it. Bugs will be hard to locate, and eliminate, and when you attempt to
do so, you'll simply introduce a few more bugs because the bugs simply
"crawl" around via the "spaghetti" tunnels without you being about to
track them.
Herman> There is a paper criticizing the attempts to prohibit gotos
Herman> by a Rubin, no relation to me, which I believe is quite
Herman> clear;
Gotos make the effects (and hence side-effects) of an action hard to
trace. While you may get it right and never change it again in your
one-man project with only 100 lines of code, they soon become a big
technical debt in the long run in big projects. When you need to
maintain code with such gotos, you'll suddenly need to pay back that
debt (with the accumulated compounded interest) and that becomes
prohibitively costly. Result? Bugs left unfixed because of the high
cost. (You'll have to spend days to track the side effects of those
gotos, and make sure your "bug fix" won't disturb the rest of the 10000
(or 100000) lines of codes in the rest of the project.
Herman> it uses a simple Fortran program and compares the two.
Keyword: "simple".
If it used a big project (such as the source code of the GCC -- the GNU
Compiler Collection), it may come up with a very different conclusion.
Herman> There are other cases where I see no good way out of using
Herman> gotos, especially in "state machines", but also elsewhere.
I agree. Gotos are appropriate for state machines, esp. when you want
to generate efficient code. A disciplined use of gotos is important.
But there are also alternative to it which are not that inconvenient.
e.g. using class inheritance in the Object-Oriented paradigm. Or using
a language with closures (e.g. LISP, Perl, Javascript).
Herman> Relegating all machine-dependent matters to subroutines can
Herman> be VERY expensive.
That's incorrect. GCC, for instance, can recognize
int x = strlen("abcd");
and optimize as
int x = 4;
!!
It's just a matter of how smart the code optimizer is. (Sometimes,
you'll need to specify compiler options to enable such aggressive
optimizations, and also tell the compiler/optimizer to forgo some
portability or standards-conformance to allow such optimizations.)
Herman Rubin
> Herman> Nesting blocks goes back to Fortran at least.
> Herman> As with many others, I find "structured programming" highly
> Herman> inefficient; even the advocates have had to find ways around
> Herman> using it strictly.
>Inefficient when you're writing tiny programs (e.g. <500 lines).
>However, when you need to develop a big program (e.g. >10000 lines),
>you'll find structuring indispensible. Without structuring the code
>properly, you'll find the program unmanageable and soon lose track of
>it. Bugs will be hard to locate, and eliminate, and when you attempt to
>do so, you'll simply introduce a few more bugs because the bugs simply
>"crawl" around via the "spaghetti" tunnels without you being about to
>track them.
One can break a program into blocks, and even in Fortran
set up a "structured" hierarchy.
> Herman> There is a paper criticizing the attempts to prohibit gotos
> Herman> by a Rubin, no relation to me, which I believe is quite
> Herman> clear;=20
>Gotos make the effects (and hence side-effects) of an action hard to
>trace. While you may get it right and never change it again in your
>one-man project with only 100 lines of code, they soon become a big
>technical debt in the long run in big projects. When you need to
>maintain code with such gotos, you'll suddenly need to pay back that
>debt (with the accumulated compounded interest) and that becomes
>prohibitively costly. Result? Bugs left unfixed because of the high
>cost. (You'll have to spend days to track the side effects of those
>gotos, and make sure your "bug fix" won't disturb the rest of the 10000
>(or 100000) lines of codes in the rest of the project.
I don't see any problems with it, especially with labeled,
instead of numerical, gotos.
> Herman> it uses a simple Fortran program and compares the two.
>Keyword: "simple".
>If it used a big project (such as the source code of the GCC -- the GNU
>Compiler Collection), it may come up with a very different conclusion.
> Herman> There are other cases where I see no good way out of using
> Herman> gotos, especially in "state machines", but also elsewhere.
>I agree. Gotos are appropriate for state machines, esp. when you want
>to generate efficient code. A disciplined use of gotos is important.
>But there are also alternative to it which are not that inconvenient.
>e.g. using class inheritance in the Object-Oriented paradigm. Or using
>a language with closures (e.g. LISP, Perl, Javascript).
> Herman> Relegating all machine-dependent matters to subroutines can
> Herman> be VERY expensive.
>That's incorrect. GCC, for instance, can recognize=20=20
> int x =3D strlen("abcd");
>and optimize as
> int x =3D 4;
>!!
>It's just a matter of how smart the code optimizer is. (Sometimes,
>you'll need to specify compiler options to enable such aggressive
>optimizations, and also tell the compiler/optimizer to forgo some
>portability or standards-conformance to allow such optimizations.)
That depends on what the one producing the optimizer thought
might be needed. Unfortunately, the ones doing this typically
do not know enough mathematics or science to realize what will
be needed.
Every routine for trigonometric and exponential functions,
and they certainly occur quite often in mathematical
computations, starts out by needing to break up a float
into an integer and a fraction, or something similar.
So why is that, which is needed elsewhere, not in hardware?
Also, exponential function routines need to add an integer
to the exponent of a float; also not in hardware on any of
the current machines to my knowledge. BTW, all of those
instructions were easy on the CYBER 205.
LEE Sau Dan
>> It's just a matter of how smart the code optimizer is.
>> (Sometimes, you'll need to specify compiler options to enable
>> such aggressive optimizations, and also tell the
>> compiler/optimizer to forgo some portability or
>> standards-conformance to allow such optimizations.)
Herman> That depends on what the one producing the optimizer thought
Herman> might be needed. Unfortunately, the ones doing this
Herman> typically do not know enough mathematics or science to
Herman> realize what will be needed.
Really? You think they can get the optimizations correct withing
knowing enough mathematics (esp. logic)?
Herman> Every routine for trigonometric and exponential functions,
Those are often delegated to library routines (which then uses the
hardware instructions) for a few reasons:
1) The function has to support a wide range of argument values in order
to conform to standards (e.g. C), but the hardware instructions can
only support a limited range of argument values (e.g. -pi < x <= pi
for sin(x)).
2) The standards require the implementation to do something platform
independent, and hence the call must go through the library functions
to smooth out the platform-specific differences.
Herman> and they certainly occur quite often in mathematical
Herman> computations, starts out by needing to break up a float into
Herman> an integer and a fraction, or something similar.
What? I've never heard that floating point computations have to be
broken up into integer and fractional parts. Are you talking about
FIXED POINT arithmetics instead?
With FLOATING POINT computations, the numbers are broken up into a
mantissa and an exponent (let's forget about the sign for simplicity).
And this breaking up is done in the compiler or I/O routines. The
numbers are already stored in mantissa-exponent representation.
Herman> So why is that, which is needed elsewhere, not in hardware?
What do you mean?
Why not in hardware? Maybe to reduce cost, because the hardware can be
simplified. e.g. supporting trigonometric functions with a limited
argument range (e.g. only -pi <= x <= pi) may simply the circuit design,
and hence reduce hardware design/production costs.
Herman> Also, exponential function routines need to add an integer
Herman> to the exponent of a float;
What!?
Herman> also not in hardware on any of the current machines to my
Herman> knowledge. BTW, all of those instructions were easy on the
Herman> CYBER 205.
Helmut Wollmersdorfer
> In article <87y6m9de...@informatik.uni-freiburg.de>,
> LEE Sau Dan <dan...@informatik.uni-freiburg.de> wrote:
>> However, when you need to develop a big program (e.g. >10000 lines),
>> you'll find structuring indispensible. Without structuring the code
>> properly, you'll find the program unmanageable and soon lose track of
>> it. Bugs will be hard to locate, and eliminate, and when you attempt to
>> do so, you'll simply introduce a few more bugs because the bugs simply
>> "crawl" around via the "spaghetti" tunnels without you being about to
>> track them.
> One can break a program into blocks, and even in Fortran
> set up a "structured" hierarchy.
Of course you can. But then you use 'structured programming'.
I even did it in assembly language.
>> Gotos make the effects (and hence side-effects) of an action hard to
>> trace. While you may get it right and never change it again in your
>> one-man project with only 100 lines of code, they soon become a big
>> technical debt in the long run in big projects. When you need to
>> maintain code with such gotos, you'll suddenly need to pay back that
>> debt (with the accumulated compounded interest) and that becomes
>> prohibitively costly. Result? Bugs left unfixed because of the high
>> cost. (You'll have to spend days to track the side effects of those
>> gotos, and make sure your "bug fix" won't disturb the rest of the 10000
>> (or 100000) lines of codes in the rest of the project.
> I don't see any problems with it, especially with labeled,
> instead of numerical, gotos.
You never had to maintain such a beast.
I remember one (~3000 lines of code). After patching ~30 bugs I couldn't
locate a 'wait for nothing' bug. The only solution was a completely
rewrite resulting in ~100 (!) lines of code.
And hey, wake up! We have the year 2009. Who needs 'numerical goto'? As
long as I remember back (35 years), even with assembly language
compilers it was not necessary to use numerical addresses or literals.
Even the length of an address could be defined symbolically - for
convenient maintenance.
Helmut Wollmersdorfer
Helmut Wollmersdorfer
>>>>>> "Herman" == Herman Rubin <hru...@odds.stat.purdue.edu> writes:
> Herman> As with many others, I find "structured programming" highly
> Herman> inefficient; even the advocates have had to find ways around
> Herman> using it strictly.
> Inefficient when you're writing tiny programs (e.g. <500 lines).
Inefficient by what? In terms of coding time, testability, readability
and maintainability there is no way around 'structured programming'.
Try yourself to recode 'if ... then ... else' with 'goto', e.g.
if ($cond) {
foo();
} else {
bar();
}
or the short form
$cond ? foo() : bar();
Of course there are many examples where you do not need the overhead
(compile and execution time) of block context. But how often is it
necessary to care about microseconds in an average application program?
Helmut Wollmersdorfer
Herman Rubin
> >> It's just a matter of how smart the code optimizer is.
> >> (Sometimes, you'll need to specify compiler options to enable
> >> such aggressive optimizations, and also tell the
> >> compiler/optimizer to forgo some portability or
> >> standards-conformance to allow such optimizations.)
> Herman> That depends on what the one producing the optimizer thought
> Herman> might be needed. Unfortunately, the ones doing this
> Herman> typically do not know enough mathematics or science to
> Herman> realize what will be needed.
>Really? You think they can get the optimizations correct withing
>knowing enough mathematics (esp. logic)?
> Herman> Every routine for trigonometric and exponential functions,
>Those are often delegated to library routines (which then uses the
>hardware instructions) for a few reasons:
>1) The function has to support a wide range of argument values in order
> to conform to standards (e.g. C), but the hardware instructions can
> only support a limited range of argument values (e.g. -pi < x <=3D pi
> for sin(x)).
>2) The standards require the implementation to do something platform
> independent, and hence the call must go through the library functions
> to smooth out the platform-specific differences.
> Herman> and they certainly occur quite often in mathematical
> Herman> computations, starts out by needing to break up a float into
> Herman> an integer and a fraction, or something similar.=20=20
>What? I've never heard that floating point computations have to be
>broken up into integer and fractional parts. Are you talking about
>FIXED POINT arithmetics instead?
No, I am talking about the computation of the elementary
transcendental functions. The algorithms mostly require
this to be done. I know this is the case for the
trigonometric, exponential and logarithmic functions.
It might not be the original argument so handled, but
a multiple of it.
>With FLOATING POINT computations, the numbers are broken up into a
>mantissa and an exponent (let's forget about the sign for simplicity).
>And this breaking up is done in the compiler or I/O routines. The
>numbers are already stored in mantissa-exponent representation.
> Herman> So why is that, which is needed elsewhere, not in hardware?
>What do you mean?
>Why not in hardware? Maybe to reduce cost, because the hardware can be
>simplified. e.g. supporting trigonometric functions with a limited
>argument range (e.g. only -pi <=3D x <=3D pi) may simply the circuit design,
>and hence reduce hardware design/production costs.
This is done for a smaller range. The original argument
is multiplied by a constant, and the product separated out
into integer and fractional part. The appropriate function
of the fractional part is computed, and the least few bits
of the integer part is used to give the answer.
> Herman> Also, exponential function routines need to add an integer
> Herman> to the exponent of a float;=20
>What!?
Yes; exp(a + n*ln(2)) = 2^n*exp(a). This is what is done
on computers.
> Herman> also not in hardware on any of the current machines to my
> Herman> knowledge. BTW, all of those instructions were easy on the
> Herman> CYBER 205.
--
Herman Rubin
How much do you work with mathematical routines?
It is even harder with routines for generating random
variables with specified distributions, when one has
to consider optimization considerations. Often, these
routines are spaghetti routines, as doing it otherwise
causes most of the time to be spent in subroutine call
procedures.
It may be necessary to make the blocks communicate in
several ways. How would you jump from the middle of
one state machine into the middle of another?
>I remember one (~3000 lines of code). After patching ~30 bugs I couldn't
>locate a 'wait for nothing' bug. The only solution was a completely
>rewrite resulting in ~100 (!) lines of code.
>And hey, wake up! We have the year 2009. Who needs 'numerical goto'? As
>long as I remember back (35 years), even with assembly language
>compilers it was not necessary to use numerical addresses or literals.
>Even the length of an address could be defined symbolically - for
>convenient maintenance.
>Helmut Wollmersdorfer
Ruud Harmsen
Rubin): in sci.lang:
>>> I don't see any problems with it, especially with labeled,
>>> instead of numerical, gotos.
>
>>You never had to maintain such a beast.
>
>How much do you work with mathematical routines?
>
>It is even harder with routines for generating random
>variables with specified distributions, when one has
>to consider optimization considerations. Often, these
>routines are spaghetti routines, as doing it otherwise
>causes most of the time to be spent in subroutine call
>procedures.
>
>It may be necessary to make the blocks communicate in
>several ways. How would you jump from the middle of
>one state machine into the middle of another?
Switch/case? Pass a state variable?
Did you ever actually MEASURE the performance consequences and did
they really matter in ACTUAL applications running on CURRENT
(including 1995+) hardware?
Remember we're not in 8088 days anymore.
I've been writing some performance critical code myself until some 10
years ago, like a database driven application that never needed more
than 2 megabytes of core despite being fast and powerful, but I never
even touched anything else than C, let alone assembly, and used
perhaps 3 gotos in all those years, DOCUMENTED, telling any later
maintainers why and how I used them.
--
Ruud Harmsen, http://rudhar.eu
Richard Herring
<r...@rudhar.eu> writes
>16 Nov 2009 16:19:50 -0500: hru...@odds.stat.purdue.edu (Herman
>Rubin): in sci.lang:
>
>>>> I don't see any problems with it, especially with labeled,
>>>> instead of numerical, gotos.
>>
>>>You never had to maintain such a beast.
>>
>>How much do you work with mathematical routines?
>>
>>It is even harder with routines for generating random
>>variables with specified distributions, when one has
>>to consider optimization considerations. Often, these
>>routines are spaghetti routines, as doing it otherwise
>>causes most of the time to be spent in subroutine call
>>procedures.
>>
>>It may be necessary to make the blocks communicate in
>>several ways. How would you jump from the middle of
>>one state machine into the middle of another?
>
>Switch/case? Pass a state variable?
What does he even _mean_? A finite-state automaton ("state machine") is
by definition always in one of a finite set of states, with an
associated set of invariants defining the rules for transitions between
them. Talking of "jumping" between different automata suggests that one
has lost track of the invariants: what is the state of a FSA supposed to
be when one has "jumped out" from it?
>Did you ever actually MEASURE the performance consequences and did
>they really matter in ACTUAL applications running on CURRENT
>(including 1995+) hardware?
I suspect the overheads of spaghetti-coding are far greater than those
for function calls on any modern computer architecture. Random gotos are
not good for instruction pipelining.
>
>Remember we're not in 8088 days anymore.
Herman's reference to "subroutine call procedures" suggests that he's
still writing FORTRAN II for an IBM 709.
>
>I've been writing some performance critical code myself until some 10
>years ago, like a database driven application that never needed more
>than 2 megabytes of core despite being fast and powerful, but I never
>even touched anything else than C, let alone assembly, and used
>perhaps 3 gotos in all those years, DOCUMENTED, telling any later
>maintainers why and how I used them.
>
>
--
Richard Herring
Ruud Harmsen
in sci.lang:
>>>It may be necessary to make the blocks communicate in
>>>several ways. How would you jump from the middle of
>>>one state machine into the middle of another?
>>
>>Switch/case? Pass a state variable?
>
>What does he even _mean_? A finite-state automaton ("state machine") is
>by definition always in one of a finite set of states, with an
>associated set of invariants defining the rules for transitions between
>them. Talking of "jumping" between different automata suggests that one
>has lost track of the invariants: what is the state of a FSA supposed to
>be when one has "jumped out" from it?
Moreover, are state machines ever hand coded? Aren't they more usually
generated, like with yacc/lex? In that case, who cares how ugly the
code is, if only it works? Maintanance is then done on the grammar and
associated code fragments, not on the full resulting code.
LEE Sau Dan
>> What does he even _mean_? A finite-state automaton ("state
>> machine") is by definition always in one of a finite set of
>> states, with an associated set of invariants defining the rules
>> for transitions between them. Talking of "jumping" between
>> different automata suggests that one has lost track of the
>> invariants: what is the state of a FSA supposed to be when one
>> has "jumped out" from it?
Ruud> Moreover, are state machines ever hand coded? Aren't they more
Ruud> usually generated, like with yacc/lex?
They ARE still coded. For simpler things like DTMF voice systems that
automatically answers phone calls, give out voice instructions and
receive input from touch-tone phones. Or for the states of automatic
vending machines. Or for automatic control systems of some high-end
cars. etc.
Or you're expecting these to be generated by lex/yacc?
Ruud Harmsen
<dan...@informatik.uni-freiburg.de>: in sci.lang:
>They ARE still coded. For simpler things like DTMF voice systems that
>automatically answers phone calls, give out voice instructions and
>receive input from touch-tone phones. Or for the states of automatic
>vending machines. Or for automatic control systems of some high-end
>cars. etc.
OK, that makes sense.
>Or you're expecting these to be generated by lex/yacc?
I probably can be done. They are very flexible.
Richard Herring
<dan...@informatik.uni-freiburg.de> writes
>>>>>> "Ruud" == Ruud Harmsen <r...@rudhar.eu> writes:
>
> >> What does he even _mean_? A finite-state automaton ("state
> >> machine") is by definition always in one of a finite set of
> >> states, with an associated set of invariants defining the rules
> >> for transitions between them. Talking of "jumping" between
> >> different automata suggests that one has lost track of the
> >> invariants: what is the state of a FSA supposed to be when one
> >> has "jumped out" from it?
>
> Ruud> Moreover, are state machines ever hand coded? Aren't they more
> Ruud> usually generated, like with yacc/lex?
>
>They ARE still coded. For simpler things like DTMF voice systems that
>automatically answers phone calls, give out voice instructions and
>receive input from touch-tone phones. Or for the states of automatic
>vending machines. Or for automatic control systems of some high-end
>cars. etc.
http://www.theregister.co.uk/2007/08/16/verity_stob_software_diagramming/
page2.html
>Or you're expecting these to be generated by lex/yacc?
Any finite-state automaton is equivalent to a parser for some regular
language, so why not?
--
Richard Herring
LEE Sau Dan
Ruud> Moreover, are state machines ever hand coded? Aren't they more
Ruud> usually generated, like with yacc/lex?
>> They ARE still coded. For simpler things like DTMF voice systems
>> that automatically answers phone calls, give out voice
>> instructions and receive input from touch-tone phones. Or for
>> the states of automatic vending machines. Or for automatic
>> control systems of some high-end cars. etc.
>> Or you're expecting these to be generated by lex/yacc?
Richard> Any finite-state automaton is equivalent to a parser for
Richard> some regular language, so why not?
Then, why don't you count in binary? It's equivalent to counting in
decimal, isn't it?
Richard Herring
<dan...@informatik.uni-freiburg.de> writes
>
> Ruud> Moreover, are state machines ever hand coded? Aren't they more
> Ruud> usually generated, like with yacc/lex?
>
> >> They ARE still coded. For simpler things like DTMF voice systems
> >> that automatically answers phone calls, give out voice
> >> instructions and receive input from touch-tone phones. Or for
> >> the states of automatic vending machines. Or for automatic
> >> control systems of some high-end cars. etc.
>
> >> Or you're expecting these to be generated by lex/yacc?
YACC grammar for a simple thermostat controller:
http://www.faqs.org/docs/Linux-HOWTO/Lex-YACC-HOWTO.html#ss4.1
>
> Richard> Any finite-state automaton is equivalent to a parser for
> Richard> some regular language, so why not?
>
>Then, why don't you count in binary?
If I want to count up to 1023 without using my toes, I do. Otherwise I
don't because it's more error-prone and less convenient for humans than
using decimal. Just as writing ad-hoc state machines is more error-prone
and less convenient than defining a formal grammar and using a tool
(which can perform consistency checks and detect errors) to convert the
grammar to a correct state machine.
> It's equivalent to counting in
>decimal, isn't it?
And your point is?
--
Richard Herring
Herman Rubin
Ruud Harmsen <r...@rudhar.eu> wrote:
>16 Nov 2009 16:19:50 -0500: hru...@odds.stat.purdue.edu (Herman
>Rubin): in sci.lang:
>>>> I don't see any problems with it, especially with labeled,
>>>> instead of numerical, gotos.
>>>You never had to maintain such a beast.
>>How much do you work with mathematical routines?
>>It is even harder with routines for generating random
>>variables with specified distributions, when one has
>>to consider optimization considerations. Often, these
>>routines are spaghetti routines, as doing it otherwise
>>causes most of the time to be spent in subroutine call
>>procedures.
>>It may be necessary to make the blocks communicate in
>>several ways. How would you jump from the middle of
>>one state machine into the middle of another?
>Switch/case? Pass a state variable?
Others have indicated already that I have a point
in not doing that.
>Did you ever actually MEASURE the performance consequences and did
>they really matter in ACTUAL applications running on CURRENT
>(including 1995+) hardware?
Even getting access to machine instructions is difficult
in these days. Also, the manuals are poorly written; the
last machine I was able to get them easily, the CYBER 205,
whose successor died out because the manufacturer did not
even try, had its manual of over 100 pages, which easily
could have been reduced to 10 or so.
Also, I have been pointing out that natural hardware
operations are not even present on the current machines.
About 20% of the time in computing elementary functions
is due to their absence; the following simple routine to
generate random variables with density 6x(1-x) on the
unit interval may not even be programmable on the current
machines to run as fast as highly computationally
inefficient routine:
m = G();
j = int(m+1/2);
n = G();
x = U() with the j+n-th bit replaced by the
opposite of the j-th bit;
end:
In this, G finds the distance from the current pointer
in a random bit stream and updates the pointer, and
U gets a uniform random variable on (0,1).
I cannot even see a good way of programming G on the
current machines, assuming unlimited register availability.
>Remember we're not in 8088 days anymore.
THAT machine, and its descendents, of which I believe
the current PCs are, was a gross mistake, and from what
I have led to believe it only prospered because IBM did
not appreciate the market. Apple was not able to keep
its superior design against the strong opposition.
So to some extent we still are in those days.
I understand that Intel coined the name "Pentium" because
it was ruled that the use of a number for computational
devices could not be copyrighted or trademarked.
>I've been writing some performance critical code myself until some 10
>years ago, like a database driven application that never needed more
>than 2 megabytes of core despite being fast and powerful, but I never
>even touched anything else than C, let alone assembly, and used
>perhaps 3 gotos in all those years, DOCUMENTED, telling any later
>maintainers why and how I used them.
I have not ruled out documentation.
Herman Rubin
One does exit from a subroutine and passes information
to another subroutine. In the case I was considering,
the output of the first state machine consists of two
integers and two masks, and the second state machine
operates on the masks, using one of the integers. The
transfer can be made to the instruction corresponding
to that integer on the second machine.
>>Did you ever actually MEASURE the performance consequences and did
>>they really matter in ACTUAL applications running on CURRENT
>>(including 1995+) hardware?
>I suspect the overheads of spaghetti-coding are far greater than those
>for function calls on any modern computer architecture. Random gotos are
>not good for instruction pipelining.
The gotos are not random, but called for by the procedure.
As for function call procedures, I have not seen any
other than putting values and addresses on a stack,
and also addresses of output values on the stack.
I have also seen some complicated ones which put
items in registers, and rename the registers on the
call and the return. Some even require many to be
passed in specific registers. How else would you
do it? In any case, the arguments have to be moved,
and usually the results also.
Some functions require less space and less time
than just the setup of the call.
>>Remember we're not in 8088 days anymore.
>Herman's reference to "subroutine call procedures" suggests that he's
>still writing FORTRAN II for an IBM 709.
How about the VAX 780, the CYBER 205, and the
IBM 6000?
>>I've been writing some performance critical code myself until some 10
>>years ago, like a database driven application that never needed more
>>than 2 megabytes of core despite being fast and powerful, but I never
>>even touched anything else than C, let alone assembly, and used
>>perhaps 3 gotos in all those years, DOCUMENTED, telling any later
>>maintainers why and how I used them.
>--
>Richard Herring
LEE Sau Dan
Herman> I understand that Intel coined the name "Pentium" because it
Herman> was ruled that the use of a number for computational devices
Herman> could not be copyrighted or trademarked.
Copyrighting... of course not. You cannot copyright a name, a book
title, a simple sentence, or any trivial amount of literary work.
Trademarking: yes. Numbers cannot be trademarked, or else your phone
number or street address may constitute an infringement! Dictionary
words are not acceptable for trademark registration, either.
(Trademarks which have become _defacto_ dictionary words, like "xerox",
"kleenex", "band-aid", risk being revoked. Those trademark owners are
trying hard to defend them.) So, "Pentium" satisfies these 2
requirements (besides others): it's not a number; and it is not a
dictionary word.
(But note: once upon a time, a farmer opened his own restaurant called
McDonalds and McDonalds -- the big American brand -- tried to sue him
for trademark infringement. The farmer won the case, because the judge
thinks the laws shouldn't forbid a person from using his own family(?)
name as the name of his business.)
Richard Herring
<hru...@odds.stat.purdue.edu> writes
He's talking about using real-time instrumentation tools like profilers,
not poring through the machine instructions.
Some modern just-in-time compilers even have the option of recompiling
code during execution, as the profiler statistics accumulate, so that
the most common sequences of operation can be pipelined without
interruption.
>
>Also, I have been pointing out that natural hardware
>operations are not even present on the current machines.
>About 20% of the time in computing elementary functions
>is due to their absence; the following simple routine to
>generate random variables with density 6x(1-x) on the
>unit interval may not even be programmable on the current
>machines to run as fast as highly computationally
>inefficient routine:
>
> m = G();
> j = int(m+1/2);
> n = G();
> x = U() with the j+n-th bit replaced by the
> opposite of the j-th bit;
> end:
>
>In this, G finds the distance from the current pointer
>in a random bit stream and updates the pointer, and
>U gets a uniform random variable on (0,1).
>
>I cannot even see a good way of programming G on the
>current machines, assuming unlimited register availability.
I cannot even see a _bad_ way of programming G on the basis of the
inadequate description above.
[...]
>
>I have not ruled out documentation.
Oh, the irony.
--
Richard Herring
Richard Herring
<hru...@odds.stat.purdue.edu> writes
Which is not the same thing as "jumping" from some point in the first
into some point within the second.
>In the case I was considering,
>the output of the first state machine consists of two
>integers and two masks, and the second state machine
>operates on the masks, using one of the integers. The
>transfer can be made to the instruction corresponding
>to that integer on the second machine.
So the first machine reaches its "stop" state, terminates, and you then
start the second one. That's not what is normally considered "jump[ing]
from the middle of one state machine into the middle of another".
>
>>>Did you ever actually MEASURE the performance consequences and did
>>>they really matter in ACTUAL applications running on CURRENT
>>>(including 1995+) hardware?
>
>>I suspect the overheads of spaghetti-coding are far greater than those
>>for function calls on any modern computer architecture. Random gotos are
>>not good for instruction pipelining.
>
>The gotos are not random, but called for by the procedure.
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.
Unlike structured code, spaghetti code isn't amenable to important
optimization techniques like instruction scheduling, branch predication
and (hardware) branch prediction.
>
>As for function call procedures, I have not seen any
>other than putting values and addresses on a stack,
>and also addresses of output values on the stack.
>I have also seen some complicated ones which put
>items in registers, and rename the registers on the
>call and the return. Some even require many to be
>passed in specific registers. How else would you
>do it? In any case, the arguments have to be moved,
>and usually the results also.
>
>Some functions require less space and less time
>than just the setup of the call.
True, but less often than you'd think. When code is systematically
factored into a large number of small functions which call each other,
many of the arguments are already in registers from the previous call.
Combined with structured coding techniques, a function doesn't have to
be very big before the savings from the optimizations greatly outweigh
the cost of setting up the call.
--
Richard Herring
LEE Sau Dan
>> Some functions require less space and less time than just the
>> setup of the call.
Richard> True, but less often than you'd think. When code is
Richard> systematically factored into a large number of small
Richard> functions which call each other, many of the arguments are
Richard> already in registers from the previous call. Combined with
Richard> structured coding techniques, a function doesn't have to be
Richard> very big before the savings from the optimizations greatly
Richard> outweigh the cost of setting up the call.
Don't forget that many modern compilers are smart enough to
automatically inline invocations of relatively short functions, thereby
eliminating the function call overhead, as well as allowing more
aggressive code optimizations (e.g. smarter register allocation) after
the inlining. It's stupid and a waste of time and energy for a human
programmer to try to repeat these optimizations manually, only to find
out that they usually can't do better than smart compilers.
Ruud Harmsen
in sci.lang:
>>One does exit from a subroutine and passes information
>>to another subroutine.
>
>Which is not the same thing as "jumping" from some point in the first
>into some point within the second.
That can be done portably in C:
http://publications.gbdirect.co.uk/c_book/chapter9/nonlocal_jumps.html
António Marques
> When code is systematically factored into a large number of small
> functions which call each other, many of the arguments are already in
> registers from the previous call. Combined with structured coding
> techniques, a function doesn't have to be very big before the savings
> from the optimizations greatly outweigh the cost of setting up the
> call.
Well, that's as may be, but the fact remains that the best of compilers
can't do as good a job as the best of ASM programmers, and for some
performance critical code the difference is relevant. Of course,
'performance critical' does mean 'performance critical', as in 'intense
computations needed everywhere such as graphics processing', not as in
'someone said this app bettre be fast or else'.
Richard Herring
<r...@rudhar.eu> writes
that's still active, not to a random label in spaghetti code.
--
Richard Herring
Richard Herring
<m....@sapo.pt> writes
>Richard Herring wrote:
>
>> When code is systematically factored into a large number of small
>> functions which call each other, many of the arguments are already in
>> registers from the previous call. Combined with structured coding
>> techniques, a function doesn't have to be very big before the savings
>> from the optimizations greatly outweigh the cost of setting up the
>> call.
>
>Well, that's as may be, but the fact remains that the best of compilers
>can't do as good a job as the best of ASM programmers, and for some
>performance critical code the difference is relevant.
Is that really still true, given the kind of complex micro-optimization
of instruction-level parallelism, speculative execution, branch
prediction etc. that modern compilers routinely perform to make the best
use of cache and pipelines?
>Of course,
>'performance critical' does mean 'performance critical', as in 'intense
>computations needed everywhere such as graphics processing', not as in
>'someone said this app bettre be fast or else'.
--
Richard Herring
Herman Rubin
Richard Herring <richard...@baesystems.com> wrote:
>In message <hduqap$4u...@odds.stat.purdue.edu>, Herman Rubin
><hru...@odds.stat.purdue.edu> writes
>>In article <1om3g5l6hd74a5fp3...@4ax.com>,
>>Ruud Harmsen <r...@rudhar.eu> wrote:
>>>16 Nov 2009 16:19:50 -0500: hru...@odds.stat.purdue.edu (Herman
>>>Rubin): in sci.lang:
...............
>>>>How much do you work with mathematical routines?
>>>>It is even harder with routines for generating random
>>>>variables with specified distributions, when one has
>>>>to consider optimization considerations. Often, these
>>>>routines are spaghetti routines, as doing it otherwise
>>>>causes most of the time to be spent in subroutine call
>>>>procedures.
>>>>It may be necessary to make the blocks communicate in
>>>>several ways. How would you jump from the middle of
>>>>one state machine into the middle of another?
>>>Switch/case? Pass a state variable?
>>Others have indicated already that I have a point
>>in not doing that.
>>>Did you ever actually MEASURE the performance consequences and did
>>>they really matter in ACTUAL applications running on CURRENT
>>>(including 1995+) hardware?
>>Even getting access to machine instructions is difficult
>>in these days. Also, the manuals are poorly written; the
>>last machine I was able to get them easily, the CYBER 205,
>>whose successor died out because the manufacturer did not
>>even try, had its manual of over 100 pages, which easily
>>could have been reduced to 10 or so.
>He's talking about using real-time instrumentation tools like profilers,
>not poring through the machine instructions.
No, I am not. The alternate methods may well involve
machine instructions in ways not intended by those who
produce the compilers.
When designing relatively short programs like those
generating random variables, there is not need for
profilers; the algorithm determines in a usually
easily obtainable way the relative frequency of the
various pathe. What can mess things up, however, is
the effect of paging. Changing a routine to a more
efficient one by increasing the size of tables to be
looked up can increase the running time of a program.
>Some modern just-in-time compilers even have the option of recompiling
>code during execution, as the profiler statistics accumulate, so that
>the most common sequences of operation can be pipelined without
>interruption.
The CYBER 205 Fortran had a means of inserting machine
instructions, and the optimizer could change the order
of instructions, including those.
>>Also, I have been pointing out that natural hardware
>>operations are not even present on the current machines.
>>About 20% of the time in computing elementary functions
>>is due to their absence; the following simple routine to
>>generate random variables with density 6x(1-x) on the
>>unit interval may not even be programmable on the current
>>machines to run as fast as highly computationally
>>inefficient routine:
>> m = G();
>> j = int(m+1/2);
>> n = G();
>> x = U() with the j+n-th bit replaced by the
>> opposite of the j-th bit;
>> end:
>>In this, G finds the distance from the current pointer
>>in a random bit stream and updates the pointer, and
>>U gets a uniform random variable on (0,1).
>>I cannot even see a good way of programming G on the
>>current machines, assuming unlimited register availability.
>I cannot even see a _bad_ way of programming G on the basis of the
>inadequate description above.
We assume that there is, somewhere, a file of random bits,
which may be refilled if needed. Therer is also a pointer
to the current location of the last read random bit. The
G operation finds the next one in the file, and moves the
pointer to that place.
Another needed instruction is to read the next bit and move
the pointer.
The challenge is to find a way of including such calls in
a subroutine which will be run millions to quadrillions of
times. From a human standpoint, this is a simple instruction.
From a computer standpoint, as far as I know a nightmare.
The asymptotically best ways to generate non-uniform random
variables involves operations such as these.
Herman Rubin
But that could EASILY be the most efficient method.
>>In the case I was considering,
>>the output of the first state machine consists of two
>>integers and two masks, and the second state machine
>>operates on the masks, using one of the integers. The
>>transfer can be made to the instruction corresponding
>>to that integer on the second machine.
>So the first machine reaches its "stop" state, terminates, and you then
>start the second one. That's not what is normally considered "jump[ing]
>from the middle of one state machine into the middle of another".
It does not reach a stop state; it reaches a state from
which it is most efficient to jump to a location in the
second one. The finish of mask generation is sufficiently
similar from various points in the first machine to be done
by the second machine, as various streams merge. The second
machine is, apart from the number being large, a one-way
machine, and one can efficiently use gotos and dropthroughs
to speed the operation.
I repeat that there are many points in the operation of the
first machine from which it exits to the second machine.
>>>>Did you ever actually MEASURE the performance consequences and did
>>>>they really matter in ACTUAL applications running on CURRENT
>>>>(including 1995+) hardware?
>>>I suspect the overheads of spaghetti-coding are far greater than those
>>>for function calls on any modern computer architecture. Random gotos are
>>>not good for instruction pipelining.
>>The gotos are not random, but called for by the procedure.
>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. 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.
>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. If the input does not consist of random
numbers, or numbers which behave sufficiently like
them, the output will not be useful.
>>As for function call procedures, I have not seen any
>>other than putting values and addresses on a stack,
>>and also addresses of output values on the stack.
>>I have also seen some complicated ones which put
>>items in registers, and rename the registers on the
>>call and the return. Some even require many to be
>>passed in specific registers. How else would you
>>do it? In any case, the arguments have to be moved,
>>and usually the results also.
>>Some functions require less space and less time
>>than just the setup of the call.
>True, but less often than you'd think. When code is systematically
>factored into a large number of small functions which call each other,
>many of the arguments are already in registers from the previous call.
>Combined with structured coding techniques, a function doesn't have to
>be very big before the savings from the optimizations greatly outweigh
>the cost of setting up the call.
I am quite aware of that. Of course, one also has to
consider the interruption from the call and return, and
that the return might not be where it is wanted.
António Marques
> In message <he13v5$ugs$1...@news.eternal-september.org>, António Marques
> <m....@sapo.pt> writes
>> Richard Herring wrote:
>>
>>> When code is systematically factored into a large number of small
>>> functions which call each other, many of the arguments are already in
>>> registers from the previous call. Combined with structured coding
>>> techniques, a function doesn't have to be very big before the savings
>>> from the optimizations greatly outweigh the cost of setting up the
>>> call.
>>
>> Well, that's as may be, but the fact remains that the best of compilers
>> can't do as good a job as the best of ASM programmers, and for some
>> performance critical code the difference is relevant.
>
> Is that really still true, given the kind of complex micro-optimization
> of instruction-level parallelism, speculative execution, branch
> prediction etc. that modern compilers routinely perform to make the best
> use of cache and pipelines?
All that's very well, but at least until very recently it hardly touched
the kind of local challenges found in intense computation such as
graphical computations and A/V codecs. Medium logic is much better left
to the compiler, but local low level (and though of as atomic)
calculations usually have little to exploit in terms of ILP (since
parallelism is best spent with parallel higher-level execution paths) or
branching optimisations. Why is so much of x264 done in ASM? Why is
MenuetOS so fast?
I also like to think that the higher level the language the faster the
code will run one day, but I don't think we're quite there yet.
Herman Rubin
LEE Sau Dan <dan...@informatik.uni-freiburg.de> wrote:
>>>>>> "Richard" =3D=3D Richard Herring <junk@[127.0.0.1]> writes:
> >> Some functions require less space and less time than just the
> >> setup of the call.
> Richard> True, but less often than you'd think. When code is
> Richard> systematically factored into a large number of small
> Richard> functions which call each other, many of the arguments are
> Richard> already in registers from the previous call. Combined with
> Richard> structured coding techniques, a function doesn't have to be
> Richard> very big before the savings from the optimizations greatly
> Richard> outweigh the cost of setting up the call.
>Don't forget that many modern compilers are smart enough to
>automatically inline invocations of relatively short functions, thereby
>eliminating the function call overhead, as well as allowing more
>aggressive code optimizations (e.g. smarter register allocation) after
>the inlining. It's stupid and a waste of time and energy for a human
>programmer to try to repeat these optimizations manually, only to find
>out that they usually can't do better than smart compilers.
Only if they know that the function can be inlined.
A computer is a superfast subimbecile, and should be
treated as such. If the compiler writer did not
anticipate the type of insertion, it is unlikely to
be inlined. Even worse, especially in working with
random numbers, the compiler has to be hit over the
head to accept that repeated calls to the same type
of random number are NOT the same.
Herman Rubin
However, it is clearly not as efficient, and the
text indicates that it is not done by a direct
hardware goto, but by an inserted piece of code
which does more.
Herman Rubin
Richard Herring <richard...@baesystems.com> wrote:
>In message <he13v5$ugs$1...@news.eternal-september.org>, Antnio Marques
>>Richard Herring wrote:
>>> When code is systematically factored into a large number of small
>>> functions which call each other, many of the arguments are already in
>>> registers from the previous call. Combined with structured coding
>>> techniques, a function doesn't have to be very big before the savings
>>> from the optimizations greatly outweigh the cost of setting up the
>>> call.
>>Well, that's as may be, but the fact remains that the best of compilers
>>can't do as good a job as the best of ASM programmers, and for some
>>performance critical code the difference is relevant.
>Is that really still true, given the kind of complex micro-optimization
>of instruction-level parallelism, speculative execution, branch
>prediction etc. that modern compilers routinely perform to make the best
>use of cache and pipelines?
They TRY to, but they do not have the relevant information
to do so. When dealing with random numbers, as I am, the
programmer knows the path probabilities, even if the paths
are convoluted.
>>Of course,
>>'performance critical' does mean 'performance critical', as in 'intense
>>computations needed everywhere such as graphics processing', not as in
>>'someone said this app bettre be fast or else'.
>--
>Richard Herring
Ruud Harmsen
Rubin): in sci.lang:
>>That can be done portably in C:
>>http://publications.gbdirect.co.uk/c_book/chapter9/nonlocal_jumps.html
>
>However, it is clearly not as efficient, and the
>text indicates that it is not done by a direct
>hardware goto, but by an inserted piece of code
>which does more.
Yes, it takes 0.2 microseconds (if that) instead of 10 nanoseconds.
Who cares?
Ruud Harmsen
Rubin): in sci.lang:
But I was. I used to use the Borland profiler and found some
interesting results. Primarily, it tells you where optimization is
just wasted effort.
>The alternate methods may well involve
>machine instructions in ways not intended by those who
>produce the compilers.
--
Ruud Harmsen, http://rudhar.eu
António Marques
> I used to use the Borland profiler and found some
> interesting results. Primarily, it tells you where optimization is
> just wasted effort.
and
The guy writing code that has to be run a trillion times all the time
cares. The problem with profiling-driven optimisation is that it can
help you smooth out the big wasters, but can't help you as much when
trying to get the baseline code to be faster. Analogically speaking: it
can help you bulldoze the landscape to a flatland, but it's not so easy
to make the flatland's base height go nearer sea level.
Now, it matters very little whether some piece of code that is called
every so often takes 0.2 microseconds instead of 10 nanoseconds. But it
matters a great deal more if some blocks that get used permanently take
9 instead of 10 nanoseconds to complete. And the kind of optimisation
we're talking here isn't the higher-level type; we're talking very small
code that does very small things but is being called to do it all of the
time.
LEE Sau Dan
>> Don't forget that many modern compilers are smart enough to
>> automatically inline invocations of relatively short functions,
>> thereby eliminating the function call overhead, as well as
>> allowing more aggressive code optimizations (e.g. smarter
>> register allocation) after the inlining. It's stupid and a waste
>> of time and energy for a human programmer to try to repeat these
>> optimizations manually, only to find out that they usually can't
>> do better than smart compilers.
Herman> Only if they know that the function can be inlined.
And they do. They're smart enough to discover that those functions are
pure and hence inlinable.
Herman> A computer is a superfast subimbecile, and should be treated
Herman> as such. If the compiler writer did not anticipate the type
Herman> of insertion, it is unlikely to be inlined. Even worse,
Herman> especially in working with random numbers, the compiler has
Herman> to be hit over the head to accept that repeated calls to the
Herman> same type of random number are NOT the same.
Modern C compilers are smart enough to know that these functions have
side effects, i.e. are impure.
Compilers like GCC even have extended syntax to let you tag functions as
"pure", "no return", etc. C++ introduced the "inline" keyword. All
these are meant to give better *hints* (not orders) to the compielrs so
that they can generate better optimized code. (Even the very old C
compilers supported the hinting keyword "register", which is no longer
useful nowadays (and hence its use is discouraged) because compilers can
usually make a better decision on register allocation than human
programmers.)
LEE Sau Dan
António> Now, it matters very little whether some piece of code that
António> is called every so often takes 0.2 microseconds instead of
António> 10 nanoseconds. But it matters a great deal more if some
António> blocks that get used permanently take 9 instead of 10
António> nanoseconds to complete. And the kind of optimisation we're
António> talking here isn't the higher-level type; we're talking
António> very small code that does very small things but is being
António> called to do it all of the time.
If that tiny piece of code only takes up 0.1% of the execution time
(after doing all other optimizations), does it worth the human
time/effort to hand-optimize it?
António Marques
wrote:
> >>>>> "António" == António Marques <m...@sapo.pt> writes:
>
> António> Now, it matters very little whether some piece of code that
> António> is called every so often takes 0.2 microseconds instead of
> António> 10 nanoseconds. But it matters a great deal more if some
> António> blocks that get used permanently take 9 instead of 10
> António> nanoseconds to complete. And the kind of optimisation we're
> António> talking here isn't the higher-level type; we're talking
> António> very small code that does very small things but is being
> António> called to do it all of the time.
>
> If that tiny piece of code only takes up 0.1% of the execution time
> (after doing all other optimizations), does it worth the human
> time/effort to hand-optimize it?
I think the answer lies in the ASM code one does find in real world
performance-critical software. The issue is not some tiny pieces of
code that take 0.1% of the execution time; it's the code itself that
is typically 0.1% of the total code, but used in a disproportionately
high frequency. Maybe compilers will be able to cope wit it too in the
near future, but right now they're not so powerful as convenience
would have us believe. GCC isn't the end and all of compilers, either,
in what regards producing optimal binaries, only the one with the
highest number of supported front-ends and targets.
I think it will be necessary to build better expressiveness into
languages ('inline' is but a small step, and a misguided one at that,
if there is comething the compiler should be able to do by itself, it
should be inlining) before we get to the next level of optimisations
(and here, yes, it may not be worth the cost, though it would be
nice). Then there is the problem that you optimise one way but lose
the other way. Maybe we're hitting a wall. Maybe the only way forward
is to develop languages better suited to parallelism. Not that
functional languages don't do a good job, but the world has to make do
with average programmers and those can't cope with anything else than
imperative stuff.
LEE Sau Dan
>> If that tiny piece of code only takes up 0.1% of the
>> execution time (after doing all other optimizations), does
>> it worth the human time/effort to hand-optimize it?
António> I think the answer lies in the ASM code one does find in
António> real world performance-critical software. The issue is not
António> some tiny pieces of code that take 0.1% of the execution
António> time; it's the code itself that is typically 0.1% of the
António> total code, but used in a disproportionately high
António> frequency.
Neither the frequency nor the length of the code matters here. What
matters is: how much time the CPU *really* spends on that fragment of
code. If a piece of code (A) is invoked a billion times in the course
of 10 hours, but each invocation takes only 1 microsecond (including all
call-return overheas), that's only 1000s out of 10 hours, or 2.8% of the
total execution time. That's not a good candidate for optimization.
There may be another piece of code (B) that gets invoked only 1000
times, but spends the CPU 4 hours (14.4s per call). This is a better
candidate for optimization because it occupies 40% of the execution
time.
Why?
Suppose you can very skillfully optimize code fragment A to reduce its
execution time down to 10% of the original. i.e. 0.1ms per call. So, 1
billion calls now takes only 100s instead of 1000s. That saves 900s
(out of 10 hours).
OTOH, I choose to optimize code fragment B instead. I'm not as smart
and skillful as you are. So, I can only reduce the execution time of B
by 10%. i.e. the time it takes for each invocation of B is reduce down
to 90% of the original. Each call now takes 12.96s instead of 14.4s.
But don't forget that this code gets called "merely" 1000 times. So,
the total time taken by this code fragment is now 12960s instead of
14400 sec. That's a saving of 1440s (out of 10 hours).
So, who is smarter? The one who uses all his highly specialized skills
and spends a lot of time effort, saving 900s in the end? Or the one who
just pulls a few simple tricks (or turns on a few compiler flags) and
effectively saves 1440s?
That's why one should profile the code to locate good candidates for
optimization.
António> Maybe compilers will be able to cope wit it too in the near
António> future, but right now they're not so powerful as
António> convenience would have us believe.
I used to think like that 10 years ago. But playing with 'gcc -O3 -s'
has changed my mind.
António> GCC isn't the end and all of compilers, either, in what
António> regards producing optimal binaries, only the one with the
António> highest number of supported front-ends and targets.
Yes. But it's already very amazing in terms of aggressive
optimizations. It does more than I would/could have done manually.
António> I think it will be necessary to build better expressiveness
António> into languages ('inline' is but a small step, and a
António> misguided one at that, if there is comething the compiler
António> should be able to do by itself, it should be inlining)
Well... "inline" is just like "register", or writing "++i;" instead of
"i++;". Things that some programmers thought would help the compiler.
But it turns out that modern compilers are better at this than we are.
Just leave it to the compiler, and only intervene when find that it is
really less smart than you are.
"misguided"... haha... modern compiler writers discourage programmers
from using "register". This is because compilers can now identify
candidates for register allocation much better than the human
programmer. If the compiler really obey your "register" hint, the
resulting code may be even less efficient than what the compiler would
choose. In other words, it is you the program who is "misguiding" the
compiler. (So, some compilers simply ignore "register" and the like,
and makes its own decision, allowing you to override this with
command-line switches or pragma directives. Usually, you won't be
better of with the overriding.)
António> before we get to the next level of optimisations (and here,
António> yes, it may not be worth the cost, though it would be
António> nice). Then there is the problem that you optimise one way
António> but lose the other way. Maybe we're hitting a wall.
So, just trust the modern compilers, and examine the generated code.
Most of the time, they can get it right. Save yourself the time for
more challenging optimization tasks.
António> Maybe the only way forward is to develop languages better
António> suited to parallelism. Not that functional languages don't
António> do a good job, but the world has to make do with average
António> programmers and those can't cope with anything else than
António> imperative stuff.
Fire those who cannot think outside the imperative jail!
If a programmer writes SQL imperatively, he's likely to get very
inefficient code like this:
resultSet = conn.execute("SELECT * FROM users");
while (resultSet.next()) {
if (resultSet.get("expiry_date")+7 < today()) {
userId = resultSet.get("id");
// issue more 'SELECT *' statements to pull in more
// info about this user from other tables
// and then send reminder email to 'userId'
}
}
resultSet.close();
This code not only runs more slowly, but also puts unnecessary load on
the DB server and the network. Don't laugh. Many "programmers" write
code like this. They simply can't think in a non-imperative way:
relational algebra (joins, projections, selections), declarative
programming, etc.
Well... but you should be happy that there are so many such sloppy
programmers. They have driven higher and higher demands for computers
of bigger and bigger computational and storage capacities. This
economic power drives applied research for faster computers and higher
storeage capacities at lower and lower prices. So, we can now buy
computers that are 1000s times more powerful than those 20 years ago, at
half the price.
Ruud Harmsen
<dan...@informatik.uni-freiburg.de>: in sci.lang:
>Well... "inline" is just like "register", /
Yes. A recommendation to the compiler, that it might ignore.
>or writing "++i;" instead of "i++;".
If used as part of another expression, these are really different. In
contexts where only the side-effect is important, i.e. the evaluation
result is not used, it isn't even a recommendation to the compiler,
but the statements are simply identical in effect.
>Things that some programmers thought would help the compiler.
Some, not all.
Helmut Wollmersdorfer
>>>>>> "António" == António Marques <m....@sapo.pt> writes:
> António> Now, it matters very little whether some piece of code that
> António> is called every so often takes 0.2 microseconds instead of
> António> 10 nanoseconds. But it matters a great deal more if some
> António> blocks that get used permanently take 9 instead of 10
> António> nanoseconds to complete. And the kind of optimisation we're
> António> talking here isn't the higher-level type; we're talking
> António> very small code that does very small things but is being
> António> called to do it all of the time.
> If that tiny piece of code only takes up 0.1% of the execution time
> (after doing all other optimizations), does it worth the human
> time/effort to hand-optimize it?
Of course this would not be worth human time. As a rule of thumb which I
usually show in such discussions about optimizations on the instruction
level: Saving of 1 microsecond costs a mimimum of 10 minutes of human
time (coding two examples and do a benchmark). 10 minutes = 10 x 60
seconds = 600 Mio. microseconds. Thus such optimizations are only worth
the human investment if your code will be executed ~600 Mio. times.
But António means a sort of code executed very often. Think about
something like transformations of pixel-images doing calculations on
every single pixel in every layer (Red, Green, Blue). Then it counts how
you walk through the data structure, how you address the items, which
machine operations are used.
Helmut Wollmersdorfer
LEE Sau Dan
>> If that tiny piece of code only takes up 0.1% of the execution
>> time (after doing all other optimizations), does it worth the
>> human time/effort to hand-optimize it?
Helmut> Of course this would not be worth human time. As a rule of
Helmut> thumb which I usually show in such discussions about
Helmut> optimizations on the instruction level: Saving of 1
Helmut> microsecond costs a mimimum of 10 minutes of human time
Helmut> (coding two examples and do a benchmark). 10 minutes = 10 x
Helmut> 60 seconds = 600 Mio. microseconds. Thus such optimizations
Helmut> are only worth the human investment if your code will be
Helmut> executed ~600 Mio. times.
This calculation is too simplistic. It naively assumes that the time
spent on optimization is proportional to the program execution time
saved. Unfortunately, this assumption is not true.
Very often, reducing time from a big piece of code is easy. Trying to
reduce the execution time of a few lines of code is very very difficult.
The last mile is always the most costly. This is the law of diminishing
return. The last 10% reduction in program execution time would cost you
90% of programming time and effort.
Helmut> But António means a sort of code executed very often. Think
Helmut> about something like transformations of pixel-images doing
Helmut> calculations on every single pixel in every layer (Red,
Helmut> Green, Blue). Then it counts how you walk through the data
Helmut> structure, how you address the items, which machine
Helmut> operations are used.
Explain how this won't be located by a profiler.
If the program spends little time (e.g. <1%) on that code fragment (even
if it is invoked a billion times), it won't worth hand-optimization.
This is because even if you reduce its time to zero, the total reduction
in execution time is <1%. If a fragment really worths
hand-optimization, the program must be spending a lot of time on it, and
this is caught by a profiler.
Helmut Wollmersdorfer
>>>>>> "Helmut" == Helmut Wollmersdorfer <hel...@wollmersdorfer.at> writes:
> >> If that tiny piece of code only takes up 0.1% of the execution
> >> time (after doing all other optimizations), does it worth the
> >> human time/effort to hand-optimize it?
> Helmut> Of course this would not be worth human time. As a rule of
> Helmut> thumb which I usually show in such discussions about
> Helmut> optimizations on the instruction level: Saving of 1
> Helmut> microsecond costs a mimimum of 10 minutes of human time
> Helmut> (coding two examples and do a benchmark). 10 minutes = 10 x
> Helmut> 60 seconds = 600 Mio. microseconds. Thus such optimizations
> Helmut> are only worth the human investment if your code will be
> Helmut> executed ~600 Mio. times.
> This calculation is too simplistic.
'Rule of thumb' implies 'simplistic'.
> It naively assumes that the time
> spent on optimization is proportional to the program execution time
> saved. Unfortunately, this assumption is not true.
ACK. That's why I wrote 'minimum'.
> Very often, reducing time from a big piece of code is easy.
Yes. Use a profiler and optimize the 'low hanging fruits'.
> Trying to
> reduce the execution time of a few lines of code is very very difficult.
Yes and no.
'Few lines of code' also could use a better algorithm. But I would only
change it if it is not 'fast enough'.
Helmut Wollmersdorfer
Richard Herring
<hru...@odds.stat.purdue.edu> writes
>In article <87my2kb...@sdleepc.cs.hku.hk>,
>LEE Sau Dan <dan...@informatik.uni-freiburg.de> wrote:
>>>>>>> "Richard" =3D=3D Richard Herring <junk@[127.0.0.1]> writes:
>
>> >> Some functions require less space and less time than just the
>> >> setup of the call.
>
>> Richard> True, but less often than you'd think. When code is
>> Richard> systematically factored into a large number of small
>> Richard> functions which call each other, many of the arguments are
>> Richard> already in registers from the previous call. Combined with
>> Richard> structured coding techniques, a function doesn't have to be
>> Richard> very big before the savings from the optimizations greatly
>> Richard> outweigh the cost of setting up the call.
>
>>Don't forget that many modern compilers are smart enough to
>>automatically inline invocations of relatively short functions, thereby
>>eliminating the function call overhead, as well as allowing more
>>aggressive code optimizations (e.g. smarter register allocation) after
>>the inlining. It's stupid and a waste of time and energy for a human
>>programmer to try to repeat these optimizations manually, only to find
>>out that they usually can't do better than smart compilers.
>
>Only if they know that the function can be inlined.
>
>A computer is a superfast subimbecile, and should be
>treated as such. If the compiler writer did not
>anticipate the type of insertion, it is unlikely to
>be inlined.
Since the writers of modern compilers most certainly _did_ anticipate
the possibility of inlining and many other kinds of code resequencing,
that's both true and irrelevant.
> Even worse, especially in working with
>random numbers, the compiler has to be hit over the
>head to accept that repeated calls to the same type
>of random number are NOT the same.
What ancient language are you programming in? All the compilers I'm
familiar with recognise that repeated calls of a function mean it has to
be called repeatedly, _unless_ they can prove that the call has no
side-effects.
Your acquaintance with compiler technology appears to be about 30 years
behind the times.
--
Richard Herring
Richard Herring
<hru...@odds.stat.purdue.edu> writes
>In article <K5hKz1WD...@baesystems.com>,
>Richard Herring <richard...@baesystems.com> wrote:
>>In message <he13v5$ugs$1...@news.eternal-september.org>, Antnio Marques
>><m....@sapo.pt> writes
>>>Richard Herring wrote:
>
>>>> When code is systematically factored into a large number of small
>>>> functions which call each other, many of the arguments are already in
>>>> registers from the previous call. Combined with structured coding
>>>> techniques, a function doesn't have to be very big before the savings
>>>> from the optimizations greatly outweigh the cost of setting up the
>>>> call.
>
>>>Well, that's as may be, but the fact remains that the best of compilers
>>>can't do as good a job as the best of ASM programmers, and for some
>>>performance critical code the difference is relevant.
>
>>Is that really still true, given the kind of complex micro-optimization
>>of instruction-level parallelism, speculative execution, branch
>>prediction etc. that modern compilers routinely perform to make the best
>>use of cache and pipelines?
>
>They TRY to, but they do not have the relevant information
>to do so. When dealing with random numbers, as I am, the
>programmer knows the path probabilities, even if the paths
>are convoluted.
Hence the use of techniques like speculative execution and branch
prediction, where the _hardware_ gathers real-time statistics about the
paths and pipelines the instructions accordingly..
--
Richard Herring
António Marques
> Well... but you should be happy that there are so many such sloppy
> programmers. They have driven higher and higher demands for computers
> of bigger and bigger computational and storage capacities. This
> economic power drives applied research for faster computers and
> higher storeage capacities at lower and lower prices.
Yes, this much is right. I'm only afraid because I feel some limits are
being reached and there is Amdahl's law.
Richard Herring
I know you're not. The "he" above is Ruud Harmsen.
> The alternate methods may well involve
>machine instructions in ways not intended by those who
>produce the compilers.
>
>When designing relatively short programs like those
>generating random variables, there is not need for
>profilers; the algorithm determines in a usually
>easily obtainable way the relative frequency of the
>various pathe. What can mess things up, however, is
>the effect of paging. Changing a routine to a more
>efficient one by increasing the size of tables to be
>looked up can increase the running time of a program.
>
>>Some modern just-in-time compilers even have the option of recompiling
>>code during execution, as the profiler statistics accumulate, so that
>>the most common sequences of operation can be pipelined without
>>interruption.
Exactly. Hence the need for profilers.
--
Richard Herring
António Marques
> Helmut> But António means a sort of code executed very often. Think
> Helmut> about something like transformations of pixel-images doing
> Helmut> calculations on every single pixel in every layer (Red,
> Helmut> Green, Blue). Then it counts how you walk through the data
> Helmut> structure, how you address the items, which machine
> Helmut> operations are used.
>
> Explain how this won't be located by a profiler.
>
> If the program spends little time (e.g.<1%) on that code fragment (even
> if it is invoked a billion times), it won't worth hand-optimization.
> This is because even if you reduce its time to zero, the total reduction
> in execution time is <1%. If a fragment really worths
> hand-optimization, the program must be spending a lot of time on it, and
> this is caught by a profiler.
It will be spending a lot of time on it because it is used intensely,
not because it is slow. It is already as fast as the compiler can make
it to be. And again, profiling can spot the slower parts of the system,
but it can help you little regarding the baseline's speed. When
everything is slower than it should (think massive misuse of data
structures, this is a different thing we're discussing now), when
everything is slower than it should profiling is little help. And
unfortunately software is full of that, do you remember a paper some
time ago that did a quick look into just how much waste is there in
booting up Linux, starting X and running some Gnome programs?
Richard Herring
Then my original point stands: how are the invariants maintained?
>
>
>>>>>Did you ever actually MEASURE the performance consequences and did
>>>>>they really matter in ACTUAL applications running on CURRENT
>>>>>(including 1995+) hardware?
>
>>>>I suspect the overheads of spaghetti-coding are far greater than those
>>>>for function calls on any modern computer architecture. Random gotos are
>>>>not good for instruction pipelining.
>
>>>The gotos are not random, but called for by the procedure.
>
>>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.
> 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.
>
>>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.
--
Richard Herring
Herman Rubin
> >> Don't forget that many modern compilers are smart enough to
> >> automatically inline invocations of relatively short functions,
> >> thereby eliminating the function call overhead, as well as
> >> allowing more aggressive code optimizations (e.g. smarter
> >> register allocation) after the inlining. It's stupid and a waste
> >> of time and energy for a human programmer to try to repeat these
> >> optimizations manually, only to find out that they usually can't
> >> do better than smart compilers.
> Herman> Only if they know that the function can be inlined.
>And they do. They're smart enough to discover that those functions are
>pure and hence inlinable.
And what if those functions can only be inlined by using
procedures which are not in the language? Will the compiler
consider using such combinations of instructions? Without
using assembler, or some means of giving instructions, the
computer cannot even know that this can be done.
> Herman> A computer is a superfast subimbecile, and should be treated
> Herman> as such. If the compiler writer did not anticipate the type
> Herman> of insertion, it is unlikely to be inlined. Even worse,
> Herman> especially in working with random numbers, the compiler has
> Herman> to be hit over the head to accept that repeated calls to the
> Herman> same type of random number are NOT the same.
>Modern C compilers are smart enough to know that these functions have
>side effects, i.e. are impure.
Only if they are told.
>Compilers like GCC even have extended syntax to let you tag functions as
>"pure", "no return", etc. C++ introduced the "inline" keyword.
The use of inline functions goes back at least to old
Fortrans. I believe the term used was "implicit". But
the producers of C seemed either not to know of it, or
to consider it irrelevant.
All
>these are meant to give better *hints* (not orders) to the compielrs so
>that they can generate better optimized code. (Even the very old C
>compilers supported the hinting keyword "register", which is no longer
>useful nowadays (and hence its use is discouraged) because compilers can
>usually make a better decision on register allocation than human
>programmers.)
I have seen some of these. They do not.
Sometimes it is necessary to give orders. If a compiler
does not like what you have put down, it should discuss
the problem with you.
Herman Rubin
>Yes and no.
>Helmut Wollmersdorfer
As I said before, I believe that one can come up with a
high level version of an assembler, which will enable the
efficient use of the machine. One can allow the optimiser
to rearrange instructions, or to ask if certain revisions,
which might actually include more computation for
efficiency, should be used. Also, if programmers keep
efficiency in mind, they are likely to save much time with
little expenditure of effort.
Herman Rubin
One of the methods used for improving performance is
to eliminate repeated calls. As 99%+ of all function
calls have no side effects, optimizers should assume
this unless otherwise stated.
>Your acquaintance with compiler technology appears to be about 30 years
>behind the times.
--
Herman Rubin
How is a compiler going to do speculative execution, when
in many parts of the code it has no idea of what is going on?
The compiler is not going to know the branch probabilities in
a procedure to generate output with a certain distribution,
but the mathematician does.
Herman Rubin
Why? There is no reason that the compiler cannot
consider the locations from which a goto can be
reached. It is no harder to do this for gotos local
to a subroutine than for function calls; in fact, it
is much easier. Any compiler stupid enough not to
locate the environment of the goto will produce bad
code with gotos; if the current compilers do this,
THEY are the ones to blame.
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.
I agree that one will rarely want to inline spaghetti
code, but even this is possible. I did expect to be
able to keep track of the registers in the multiple
state machine situation I was considering, with gotos
and a necessarily spaghetti-like structure to the
first machine. A spaghetti program needs spaghetti code.
>> 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.
Anything which HAS TO BE flushed will have to be flushed
even if no gotos are used.
>>>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.
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. A local block can also do this
in an equivalent structured manner, usually.
If I can tell the compiler how often the branches will be
taken, even if it depends on branch history, why should the
compiler not use that information, instead of guessing?
The case I was discussing, of the two state machines, should
be handled by the second machine using the "output registers"
of the first machine, no matter which state is called. This
is a case of real register optimization, which is likely to
be better done by a human than a compiler of the kind you
mention which flushes at the sign of a goto.
LEE Sau Dan
Herman> Only if they know that the function can be inlined.
>> And they do. They're smart enough to discover that those
>> functions are pure and hence inlinable.
Herman> And what if those functions can only be inlined by using
Herman> procedures which are not in the language?
Why would that make a difference?
The compiler will assume that those procedures are impure (i.e. can have
side effects) unless it can prove the contrary. So, it won't attempt to
consider repeated calls to thsoe procedures for common subexpression
optimization.
Herman> Will the compiler consider using such combinations of
Herman> instructions?
Which? And why does that affect inlining?
Herman> Without using assembler, or some means of giving
Herman> instructions, the computer cannot even know that this can be
Herman> done.
Why not? The compiler can be given information, such as which external
procedures are pure, and it also knows which machine instructions have
which side effects.
>> Modern C compilers are smart enough to know that these functions
>> have side effects, i.e. are impure.
Herman> Only if they are told.
So, your job is to tell them so, instead of wasting time on
hand-optimization.
Herman> Sometimes it is necessary to give orders.
Only on rare occasions.
Herman> If a compiler does not like what you have put down, it
Herman> should discuss the problem with you.
--
LEE Sau Dan
>> What ancient language are you programming in? All the compilers
>> I'm familiar with recognise that repeated calls of a function
>> mean it has to be called repeatedly, _unless_ they can prove that
>> the call has no side-effects.
Herman> One of the methods used for improving performance is to
Herman> eliminate repeated calls. As 99%+ of all function calls
Herman> have no side effects, optimizers should assume this unless
Herman> otherwise stated.
99%+ of function invocations (e.g. "printf") in real-world applications
DO have side effects. They're impure functions. That's why in
practice, optimizers are written to assume the functions are impure.
PaulJK
You didn't you notice the word _hardware_?
I guess Richard underlined it specifically for your benefit but
you still didn't see it.
There are hardware architectures that do that dynamically during
the real execution of the program. It has nothing to do with a compiler.
There are also dual pipeline hardware mill architectures that manage
to look ahead into _both_ alternative paths to prefetch arguments and
instructions that follow every conditional jump. When the result of the
condition is known and tested the contents of one of the pipeline
branches is discarded and the mill pipeline "fork" waits for the next
conditional jump.
pjk
LEE Sau Dan
>> Hence the use of techniques like speculative execution and branch
>> prediction, where the _hardware_ gathers real-time statistics
>> about the paths and pipelines the instructions accordingly..
Herman> How is a compiler going to do speculative execution, when in
Herman> many parts of the code it has no idea of what is going on?
Why not? The processor manufacturers document the behaviours in
details.
Herman> The compiler is not going to know the branch probabilities
Herman> in a procedure to generate output with a certain
Herman> distribution, but the mathematician does.
A profiler can gather the data *empirically*, not theoretically. This
data could be used to feed back to the compiler. (Some people have
proposed languages extensions to allow the programmers to state (as
hints) the probabilities of the conditional branches, so that compilers
can make smarter choices.)
DKleinecke
wrote:
>
> A profiler can gather the data *empirically*, not theoretically. This
> data could be used to feed back to the compiler. (Some people have
> proposed languages extensions to allow the programmers to state (as
> hints) the probabilities of the conditional branches, so that compilers
> can make smarter choices.)
>
The original Fortan language had such a statement about the relative
frequencies of each branch in a conditional branch. Nobody used it and
it quickly dropped away.
Richard Herring
<hru...@odds.stat.purdue.edu> writes
>In article <P95LyXEi...@baesystems.com>,
>Richard Herring <richard...@baesystems.com> wrote:
>
>>What ancient language are you programming in? All the compilers I'm
>>familiar with recognise that repeated calls of a function mean it has to
>>be called repeatedly, _unless_ they can prove that the call has no
>>side-effects.
>
>One of the methods used for improving performance is
>to eliminate repeated calls. As 99%+ of all function
>calls have no side effects, optimizers should assume
>this unless otherwise stated.
Nonsense. Optimizers _must not_ make unverified assumptions which might
change the semantics of the code. If they do, the compiler is broken.
--
Richard Herring
Richard Herring
>In article <QMBc+1HB...@baesystems.com>,
>Richard Herring <richard...@baesystems.com> wrote:
>>In message <he1eoj$25...@odds.stat.purdue.edu>, Herman Rubin
>><hru...@odds.stat.purdue.edu> writes
>>>In article <NSb7Z7Cu...@baesystems.com>,
>>>Richard Herring <richard...@baesystems.com> wrote:
>>>>In message <hdurji$4k...@odds.stat.purdue.edu>, Herman Rubin
>>>><hru...@odds.stat.purdue.edu> writes
>>>>>In article <64oWjjHh...@baesystems.com>,
>>>>>Richard Herring <richard...@baesystems.com> wrote:
>>>>>>In message <1om3g5l6hd74a5fp3...@4ax.com>, Ruud Harmsen
>>>>>><r...@rudhar.eu> writes
>>>>>>>16 Nov 2009 16:19:50 -0500: hru...@odds.stat.purdue.edu (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.
[...]
>>> 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"?
>
>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.
>
>>>>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.
>
>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".
--
Richard Herring
Herman Rubin
>[...]
>[...]
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.
Richard Herring
>In article <P79rzeI9...@baesystems.com>,
>Richard Herring <richard...@baesystems.com> wrote:
>>In message <he4d94$47...@odds.stat.purdue.edu>, Herman Rubin
>><hru...@odds.stat.purdue.edu> writes
>
>It seems that computers are not designed to do numerical
>computing very well any more.
They are designed to work particularly efficiently with code which uses
a small (but sufficient) set of flow-control structures. As a
consequence it is probably true that they are not designed to handle
unstructured spaghetti code very well any more. But there's noting
specifically "numerical" about that.
>>>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.
No, "unstructured" here is a term of art which goes back at least to
Edsger Dijkstra in the 1960s. There are different more-or-less
equivalent definitions, but one example is code whose flow graph
contains intersecting loops. It's those loops which cause problems.
>Everything in a finite program is in a real sense
>structured.
No. In this sense, it's only structured if its flow graph consists
entirely of sequence, selection and repetition. It's not the gotos that
are the problem, but the structures they implement; you can write
structured code which contains gotos, so long as they only implement
those structured patterns.
--
Richard Herring
DKleinecke
> In message <heeuld$...@odds.stat.purdue.edu>, Herman Rubin
> <hru...@odds.stat.purdue.edu> writes
>
> >In article <P79rzeI98nCLF...@baesystems.com>,
> >Richard Herring <richard.herr...@baesystems.com> wrote:
> >>In message <he4d94$4...@odds.stat.purdue.edu>, Herman Rubin
Starting with unstructured code it is possible to analyze the implicit
structure in the code by detecting loops and then dissecting them each
individually. It is not at all uncommon for apparent spaghetti code to
be actually structured if you reorder the instructions and introduce a
few new controls. But if a loop has more than one entry point the easy
approaches fail and if a loop has multiple exits you need to introduce
a case variable, execute once and then do a switch. The easiest way to
handle multiple entries is the same way - assign each entry a case
number, enter at a single point and then switch.
All of this can be coded, automatically converting spaghetti code to
structured code - I have done it - but why bother? No one in their
right mind writes spaghetti code anymore.
On the other hand the code for a state machine may be almost solid
goto statements - but they are used in an orderly way. Structured
programming is not, as has been multiply suggested, coding without
goto statements (pace Dijkstra).
Herman Rubin
I see the problem you pose, and I have a solution for
it. The programmer knows which variables carry over
from one block of code to another, and even when a
variable can be dropped, and so can inform the compiler.
These are variables which are local to the subroutine or
are required for communication between the subroutine and
the outside world.
In this particular problem, there are some variables which
are used only for completion and returning results, which
are placed in an array. There are calls to the file of
random bits all over, so these must be passed on. There are
other variables local to the situation, which I will call b,
m, g4, and g16. Only b, n, and m are initialized. The flow is
start goto cont
loop
cont
if(...)goto c1
...
if(...)goto c2
---
if(...)goto c3 g4 is initialized
if(...)goto c4 g4 is initialized
....
if(...)goto c5 g16 is initialized
...
if(...)
there are several places where one of a continue, a goto ch,
a goto cont, or a goto loop occurs.
In the state machine, n is not used, calls to the random
bit array are.
ch ...
either continue in ch, or go to one of the other c's
c5... g4 is ignored
q = G();
if(B){if ODD(q)goto c2; else goto c1}
g4 = int((q+1)/2);
if(ODD(q)goto c3);
c4 ... there are gotos to c2 and c1
c3 ...
c2 ...
Here only n and m are used
c1 This is out of the state machine;
it communicates a result, and if
the required array is not filled,
has a goto to start
Now which compilers will accept this and do it efficiently?
I believe it meets the standard of "structured", and nothing
needs to be flushed at gotos unless there are not enough registers,
or the cache will be compromised.
LEE Sau Dan
>>> Everything in a finite program is in a real sense structured.
>> No. In this sense, it's only structured if its flow graph
>> consists entirely of sequence, selection and repetition. It's not
>> the gotos that are the problem, but the structures they
>> implement; you can write structured code which contains gotos, so
>> long as they only implement those structured patterns.
Herman> I see the problem you pose, and I have a solution for it.
You're just reinventing the wheels. Please update your knowledge of
*modern* compiler technologies. Yours is 30-years out of date!
Quoting from: <P95LyXEi...@baesystems.com>:
Richard> Your acquaintance with compiler technology appears to be
Richard> about 30 years behind the times.
Herman> The programmer knows which variables carry over from one
Herman> block of code to another, and even when a variable can be
Herman> dropped, and so can inform the compiler.
With structured programming, such information are *implicitly* passed to
the compiler via the structure, esp. with lexical scoping.
Herman> These are variables which are local to the subroutine or are
Herman> required for communication between the subroutine and the
Herman> outside world.
And modern compilers are smart enough to find out such variable
dependencies, without the programmers's explicit designations. I
remembers that at least 15 years ago, C compilers were already able to
detect declared-but-unused variables, and issue a warning about that.
You as a programmer does not need to tell the compiler when and where a
variable is used. The compilers can discover it accurately, and reuse
memory effectively. They'll allocate suitable variables on registers to
boost performance. All automagicially (when you turn on the appropriate
compiler switches).
Herman> In this particular problem, there are some variables which
Herman> are used only for completion and returning results, which
Herman> are placed in an array. There are calls to the file of
Herman> random bits all over, so these must be passed on. There are
Herman> other variables local to the situation, which I will call b,
Herman> m, g4, and g16. Only b, n, and m are initialized. The flow
Herman> is
[Snippet]
Herman> Now which compilers will accept this and do it efficiently?
If you dare to write it in C/C++/fortran/Java, I'll dare trying it out
with GNU GCC to see how far it goes.
Herman> I believe it meets the standard of "structured", and nothing
Herman> needs to be flushed at gotos unless there are not enough
Herman> registers, or the cache will be compromised.
BTW, have you worked out what my code in messages
<87my2zf...@gmail.com>, <87y6lw4...@sdleepc.cs.hku.hk> or
<87my2c4...@sdleepc.cs.hku.hk> computes? It's more than 3 weeks
since I posted the first!