Thoughts on the C/Assembly Debate

In article <1185722378.498383.20410@d55g2000hsg.googlegroups.com>,
William Hughes  <wpihughes@hotmail.com> wrote:
>On Jul 29, 10:19 am, Randy Yates <ya...@ieee.org> wrote:
>> Phil Carmody <thefatphil_demun...@yahoo.co.uk> writes:
>> > [...]
>> > But of course that's the programmer taking control.

>> To some extent it is, but if you need to "take control," and
>> you must delve into architecture specifics and write non-portable
>> C code (at least C code that won't run _fast_ on multiple platforms),

>A far cry from non-portable code.

Consider the badly designed C function frexp.  If executed
as a function call AT ALL, the function call is likely to
be more costly in time and space than inlining it using
assembler instructions, on whatever machine it is to be
executed.  It also should not use the C language; this is
one clear place where an adequate HLL would have to have
more than one argument to the left of the replacement call.

Another bad example is the switch operator.  It requires
an argument for the switch process, and also requires a
return to the switch operator even if one knows where to
go.  In this case, the "argument" should be kept in the
location ONLY; this removes an argument assignment, using
a multibranch test on argument, as well as a simple 
transfer when a simple transfer would do as well.  This
CAN be avoided in C by a liberal use of goto's, which 
the HLL advocates demean.

A semi-HLL assembler can be produced which is easy to 
read and write, and almost as concise as a HLL.  One
could include important instructions which HLLs handle
badly.  How one carries out multiple precision operations
depends heavily on the architecture, and architectures
are declining in their ability to do this well.
-- 
This address is for information only.  I do not claim that these views
are those of the Statistics Department or of Purdue University.
Herman Rubin, Department of Statistics, Purdue University
hrubin@stat.purdue.edu         Phone: (765)494-6054   FAX: (765)494-0558

Herman Rubin wrote:
(snip)

> A semi-HLL assembler can be produced which is easy to 
> read and write, and almost as concise as a HLL.  One
> could include important instructions which HLLs handle
> badly.  How one carries out multiple precision operations
> depends heavily on the architecture, and architectures
> are declining in their ability to do this well.

There have been a few examples of high-level assembler
languages, PL/360 as one.  Consider the PL/360 statement.

R1:=R1+R1+R1;

You might think that it would triple the value in R1
(that is, register one), but it quadruples it.  The effect
of the first addition takes place immediately, there are
no temporary registers.

That is, in some sense, the difference between a high level
language and an assembler level language.

-- glen

On Jul 30, 2:02 pm, hru...@odds.stat.purdue.edu (Herman Rubin) wrote:
> In article <1185722378.498383.20...@d55g2000hsg.googlegroups.com>,
> William Hughes  <wpihug...@hotmail.com> wrote:
>
> >On Jul 29, 10:19 am, Randy Yates <ya...@ieee.org> wrote:
> >> Phil Carmody <thefatphil_demun...@yahoo.co.uk> writes:
> >> > [...]
> >> > But of course that's the programmer taking control.
> >> To some extent it is, but if you need to "take control," and
> >> you must delve into architecture specifics and write non-portable
> >> C code (at least C code that won't run _fast_ on multiple platforms),
> >A far cry from non-portable code.
>
> Consider the badly designed C function frexp.  If executed
> as a function call AT ALL, the function call is likely to
> be more costly in time and space than inlining it using
> assembler instructions, on whatever machine it is to be
> executed.  It also should not use the C language; this is
> one clear place where an adequate HLL would have to have
> more than one argument to the left of the replacement call.


I fail to see your point.  When the compiler sees the
function frexp it can emit the appropriate machine
code without a function call.
Compilers can always use compiler magic on
a library fuction.  [Sure I can force the compiler to use
a function call and this will slow things down.
So what?  There are lots of stupid things I can do to
defeat optimization]

Or is your point that the compiler cannot store the
exponent in a register.  This is simply false.
The abstract machine cannot store the exponent in a register
but the abtract machine does not have the concept of register.
The compiler can use a register for any variable
it wants.   (If the address of this variable is taken
then the compiler has to be able to determine that
the address is not actually needed, trivial here).  True you
cannot use a "register" qualifier for the variable
used to store the exponent, but in theory we are
allowed to assume that the compiler is as good or better
than a good assembly programmer
at chosing which variable should go into registers
(the fact that this is true in practice is only icing
on the cake)

>
> Another bad example is the switch operator.  It requires
> an argument for the switch process, and also requires a
> return to the switch operator even if one knows where to
> go.  In this case, the "argument" should be kept in the
> location ONLY; this removes an argument assignment, using
> a multibranch test on argument, as well as a simple
> transfer when a simple transfer would do as well.  This
> CAN be avoided in C by a liberal use of goto's, which
> the HLL advocates demean.

There is nothing to stop the compiler from recognizing
when a switch construct can be simplified in the way
you describe and doing exactly what you describe.
Again you seem to think that if there is an assignment
in the abstract machine, the compiler must use
and assignment.  This is nonsense.


>
> A semi-HLL assembler can be produced which is easy to
> read and write, and almost as concise as a HLL.

But no where near as portable.

> One
> could include important instructions which HLLs handle
> badly.  How one carries out multiple precision operations
> depends heavily on the architecture and architectures
> are declining in their ability to do this well.

You provide no argument that a compiler coud not chose
the appropriate way of carrying out multiple precision
operations depending on the architecture.

           - William Hughes

Here are some examples which give great difficulties
in even semi-efficient programs in HLLs.

For x > 0, let x = \sum a_i/2^i be the binary expansion.
Define f(x) = \sum i*a_i/2^i; this includes the negative
i's as well if x is at least 2.  Given x in a "standard"
floating point form, how can one compute f(x) efficiently?

Here is one which would be rather useful if it could be
carried out somewhat efficiently.  I do have a way of 
doing it in C, but whether in can be reasonably done or
not depends on the architecture.  It might well need an
fpga to carry out one step, which I will assume done.

So let me describe the algorithm as a fixed point algorithm;
it does work on floating point.  At any time, there are three
numbers, q, t, and b.  The number p is an ordinary floating
point number, and is computed as stated.  Suppose the binary
expansion of q is \sum r_n/2^n.  Then the numbers q, t, and
b have the form

	q = .q_1 ... q_{k-1} 1 q_{k+1} q_{k+2} ...
	t = .q_1 ... q_{k-1} 1    0      0   ...
	b = .q_1 ... q_{k-1} 0    0      0   ...

The procedure multiplies q by a number z <= 1.  If 
the new q >= t, just accept.  If q < b, reject and
reset with q=t=1, b=0 (the first time this is used,
do the next step with k=0).  Let m be the number of
bits in a random bit stream to the next 1; set k = k+m.
If the new q_k is 1, set things up as before and 
accept; if it is 0 reject and start over.

The idea here is that one is carrying out acceptance-
rejection tests, with the z being the acceptance 
probability.  There is a random number R, whose value
is unknown to the programmer, except that at any time,
it is uniformly distributed between 0 and q.  This 
means that the test has the desired properties.

However, the machine has gotten some information; R
is uniformly distributed between b and t.  One can
verify that this algorithm has the desired property,
and uses far fewer random bits than would be required
if R were known.  However, it does require more work.

This CAN be programmed in C, as scaling does not affect
the algorithm.  It works much better if there is a good
floating integer part operation and the parity of a
such an integer is easily tested.  For good algorithms,
most of the time the new q will be greater than t.

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

In article <46ADC381.51EB0A39@bytecraft.com>,
Walter Banks  <walter@bytecraft.com> wrote:


>Randy Yates wrote:

>> To some extent it is, but if you need to "take control," and
>> you must delve into architecture specifics and write non-portable
>> C code (at least C code that won't run _fast_ on multiple platforms),
>> then assembly provides the ultimate "control."

>> I wouldn't use the word "offend" - I consider it an abuse of the
>> high level language.

>> Hey People, this is ludicrous. All these arguments treat assembly
>> as if it were the ultimate evil. It ain't that bad, folks. Honest.

>If you need to switch to asm then that specific application will
>not be portable. If the HLL can duplicate all of the functionality
>that asm has then the advantages of the HLL are not lost.

>Regards

>Walter Banks

The HLL can duplicate all the functionality of the
assembler, for arithmetic by operating on all the bits as
the assembler instruction achieves it, not as it does it.
For example, there might be an operation which efficiently
takes three arguments, multiplies two mxm numbers and adds
a third, and places the 2m-length result in appropriate
places.  Multiple precision arithmetic is difficult on most
computers; the present "single precision" should be called
"half precision", and the "double precision" single or full.

Now the best the HLL can do in general is to use mxm -> m
instructions, and if only the lower part can be gotten,
this means that things have to be broken up into size m/2.
The advantages of the asm ARE lost.

In some situations, it is even worse.  There are many
algorithms for producing random variables efficiently,
if the appropriate hardware is present, by using Boolean
operations on "fixed-point" numbers.  These are not
integers, but fixed-point reals.  Try this in any HLL;
it will be difficult, even if the same registers can
be used for Boolean and floating operations.  


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

In article <ObidnWOaJvBvszPbnZ2dnUVZ_hKdnZ2d@comcast.com>,
glen herrmannsfeldt  <gah@ugcs.caltech.edu> wrote:
>Herman Rubin wrote:
>(snip)

>> A semi-HLL assembler can be produced which is easy to 
>> read and write, and almost as concise as a HLL.  One
>> could include important instructions which HLLs handle
>> badly.  How one carries out multiple precision operations
>> depends heavily on the architecture, and architectures
>> are declining in their ability to do this well.

>There have been a few examples of high-level assembler
>languages, PL/360 as one.  Consider the PL/360 statement.

>R1:=R1+R1+R1;

>You might think that it would triple the value in R1
>(that is, register one), but it quadruples it.  The effect
>of the first addition takes place immediately, there are
>no temporary registers.

>That is, in some sense, the difference between a high level
>language and an assembler level language.

I would not call this an assembler language.  It might
be a macro added to it, but an assembler instruction is
a representation of hardware.  

I did produce a reasonable attempt at a readable, slightly
high level, assembler language for the VAX.  Much of it
can be used on any machine.  It is a somewhat typed language
designed to be easily understood, written, and read.

For example, what is the subtraction instruction in an
assembler?  I would write

	x ={t} y - z

where {t} is the type of subtraction to be used if not
the type of x.  There would be no promotion of type as
in most HLLs; the arguments can be typed, but used as
they are stored, in memory or registers.

Now what is needed in most assemblers?  One would have
to write

	subT a, b, c

where T is a type declaration, and a, b, c are x, y, z
in some order, although I have never seen x in the middle.
THAT is what is hard to work with.



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

Herman Rubin wrote:

> In some situations, it is even worse.  There are many
> algorithms for producing random variables efficiently,
> if the appropriate hardware is present, by using Boolean
> operations on "fixed-point" numbers.  These are not
> integers, but fixed-point reals.  Try this in any HLL;
> it will be difficult, even if the same registers can
> be used for Boolean and floating operations.

C99 and ISO/IEC 18037 have real fixed point
numbers (accums) can you send me a example
of this type of algorithm.

Many Thanks

Walter Banks..

hrubin@odds.stat.purdue.edu (Herman Rubin) writes:
> In article <46ADC381.51EB0A39@bytecraft.com>,
> Walter Banks  <walter@bytecraft.com> wrote:
> 
> 
> >Randy Yates wrote:
> 
> >> To some extent it is, but if you need to "take control," and
> >> you must delve into architecture specifics and write non-portable
> >> C code (at least C code that won't run _fast_ on multiple platforms),
> >> then assembly provides the ultimate "control."
> 
> >> I wouldn't use the word "offend" - I consider it an abuse of the
> >> high level language.
> 
> >> Hey People, this is ludicrous. All these arguments treat assembly
> >> as if it were the ultimate evil. It ain't that bad, folks. Honest.
> 
> >If you need to switch to asm then that specific application will
> >not be portable. If the HLL can duplicate all of the functionality
> >that asm has then the advantages of the HLL are not lost.
> 
> >Regards
> 
> >Walter Banks
> 
> The HLL can duplicate all the functionality of the
> assembler, for arithmetic by operating on all the bits as
> the assembler instruction achieves it, not as it does it.
> For example, there might be an operation which efficiently
> takes three arguments, multiplies two mxm numbers and adds
> a third, and places the 2m-length result in appropriate
> places.  Multiple precision arithmetic is difficult on most
> computers; the present "single precision" should be called
> "half precision", and the "double precision" single or full.

Potayto, potahto. 

> Now the best the HLL can do in general is to use mxm -> m
> instructions, and if only the lower part can be gotten,
> this means that things have to be broken up into size m/2.
> The advantages of the asm ARE lost.

OK, there's no muladd on x86, but there is a 32x32->64 multiply,
and gcc's perfectly capable of using that:

...
   uint32_t x=atol(argv[1]);
   uint32_t y=atol(argv[2]);
   uint64_t z=(uint64_t)y*x;
   printf("%llu\n",z);
...

gcc-4.1 ->

...
        call    __strtol_internal
        movl    $.LC0, (%esp)
        mull    %esi
        movl    %eax, 4(%esp)
        movl    %edx, 8(%esp)
        call    printf
...

The actual 32x32->64 multiply has been turned into a single 
instruction.

What advantage would asm have had over that?

> In some situations, it is even worse.  There are many
> algorithms for producing random variables efficiently,
> if the appropriate hardware is present, by using Boolean
> operations on "fixed-point" numbers.  These are not
> integers, but fixed-point reals.  Try this in any HLL;
> it will be difficult, even if the same registers can
> be used for Boolean and floating operations.  

Care to show an actual example of a high level language
performing badly in such a case? 

There's definitely a case for the use of assembly in some 
tight corner cases, don't get me wrong. It's just that from
what I've seen of (in particular chip-vendor's) development 
tools, many of the obvious and annoying flaws that HLLs 
suffered from years ago are fixed.

Phil
-- 
Dear aunt, let's set so double the killer delete select all.
-- Microsoft voice recognition live demonstration

In article <1185822779.498334.240000@r34g2000hsd.googlegroups.com>,
William Hughes  <wpihughes@hotmail.com> wrote:
>On Jul 30, 2:02 pm, hru...@odds.stat.purdue.edu (Herman Rubin) wrote:
>> In article <1185722378.498383.20...@d55g2000hsg.googlegroups.com>,
>> William Hughes  <wpihug...@hotmail.com> wrote:

>> >On Jul 29, 10:19 am, Randy Yates <ya...@ieee.org> wrote:
>> >> Phil Carmody <thefatphil_demun...@yahoo.co.uk> writes:
>> >> > [...]
>> >> > But of course that's the programmer taking control.
>> >> To some extent it is, but if you need to "take control," and
>> >> you must delve into architecture specifics and write non-portable
>> >> C code (at least C code that won't run _fast_ on multiple platforms),
>> >A far cry from non-portable code.

>> Consider the badly designed C function frexp.  If executed
>> as a function call AT ALL, the function call is likely to
>> be more costly in time and space than inlining it using
>> assembler instructions, on whatever machine it is to be
>> executed.  It also should not use the C language; this is
>> one clear place where an adequate HLL would have to have
>> more than one argument to the left of the replacement call.


>I fail to see your point.  When the compiler sees the
>function frexp it can emit the appropriate machine
>code without a function call.
>Compilers can always use compiler magic on
>a library fuction.  [Sure I can force the compiler to use
>a function call and this will slow things down.
>So what?  There are lots of stupid things I can do to
>defeat optimization]

The form of frexp was b = frexp(a, &m), which 
meant that, unless a = 0, .5 <= |b| < 1, and
a = 2^m*b.  The form of this statement forces
m into memory.  To avoid this, one would have
to write

	b, m = frexp(a)

>Or is your point that the compiler cannot store the
>exponent in a register.  This is simply false.
>The abstract machine cannot store the exponent in a register
>but the abtract machine does not have the concept of register.

Alas, the abstract machine needs the concept of a register.

>The compiler can use a register for any variable
>it wants.   (If the address of this variable is taken
>then the compiler has to be able to determine that
>the address is not actually needed, trivial here).

Not if the address of the variable is explicitly given.

		 True you
>cannot use a "register" qualifier for the variable
>used to store the exponent, but in theory we are
>allowed to assume that the compiler is as good or better
>than a good assembly programmer
>at chosing which variable should go into registers
>(the fact that this is true in practice is only icing
>on the cake)

It is true in practice?  Not to my knowledge.

>> Another bad example is the switch operator.  It requires
>> an argument for the switch process, and also requires a
>> return to the switch operator even if one knows where to
>> go.  In this case, the "argument" should be kept in the
>> location ONLY; this removes an argument assignment, using
>> a multibranch test on argument, as well as a simple
>> transfer when a simple transfer would do as well.  This
>> CAN be avoided in C by a liberal use of goto's, which
>> the HLL advocates demean.

>There is nothing to stop the compiler from recognizing
>when a switch construct can be simplified in the way
>you describe and doing exactly what you describe.
>Again you seem to think that if there is an assignment
>in the abstract machine, the compiler must use
>and assignment.  This is nonsense.

I doubt that the compiler will be able to recognize that
the switch variable is ONLY going to be used in the 
switch statement, nor will it recognize that a setup
like that may call for additional entries from outside
the subroutine.  I have not noticed additional entries
to a function or subroutine in any HLL since early
versions of Fortran, and few assemblers even have them.
One problem is the return statement.

>> A semi-HLL assembler can be produced which is easy to
>> read and write, and almost as concise as a HLL.

>But no where near as portable.

More portable than you think.

>> One
>> could include important instructions which HLLs handle
>> badly.  How one carries out multiple precision operations
>> depends heavily on the architecture and architectures
>> are declining in their ability to do this well.

>You provide no argument that a compiler coud not chose
>the appropriate way of carrying out multiple precision
>operations depending on the architecture.

>           - William Hughes

I have not seen the language alternatives which allow for
it.  In addition, different hardwares will have different
possibilities, so this provides additional problems.  The
problem is complicated by the fact that if one wants 200
bits of precision, the size of the hardware constructs is
such that 212 may be easier to get than 200; PLI did not
allow for this.


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

In article <46AE4CA1.CB8A3355@bytecraft.com>,
Walter Banks  <walter@bytecraft.com> wrote:


>Herman Rubin wrote:

>> In some situations, it is even worse.  There are many
>> algorithms for producing random variables efficiently,
>> if the appropriate hardware is present, by using Boolean
>> operations on "fixed-point" numbers.  These are not
>> integers, but fixed-point reals.  Try this in any HLL;
>> it will be difficult, even if the same registers can
>> be used for Boolean and floating operations.

>C99 and ISO/IEC 18037 have real fixed point
>numbers (accums) can you send me a example
>of this type of algorithm.

>Many Thanks

>Walter Banks..


The easiest one of these is the density 2x from 0 to 1.

In a random bit stream, find the distance to the first
one; call it K.  Change the K-th bit of a uniform random
variable to 1.

A slightly more complicated one is density 6x(1-x) in the
unit interval.  Here, get the distance K to the first one
as before, and the distance M from that to the next.  Let
J = K/2, rounded up.  Replace the J+M-th bit by the complement
of the J-th bit.


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