Go language
Andrew Reilly
http://golang.com/ ? It's a Rob Pike et-al C-family (via lingo and
oberon) native-compilation language explicitly intended to support large-
scale parallelism with erlang-style CSP (in the language, rather than as
a library.)
Other interesting features that bear on some of the discussions we've had
here recently:
Its arrays (and strings) are bounds-safe and first-class, so there's a
big tick-box from the security crowd.
Its solution to losing pointer arithmetic is to make array slices first
class. Array slices know how large the underlying array is, so bounds
are still checked.
If you read most of the doco at the site and some of the comments on the
mailing list/google group, its clear that several largish issues have
been punted into the "too hard: we'd like that but don't know how"
basket, so it is certainly quite green.
I think it's heading in the right direction, though.
The use of closures and lightweight thread scheduling is very reminiscent
of Apple's "grand central dispatch" modification to C (addition of read-
only closures aka "blocks".)
On first glance, I think it has a lot going for it.
Cheers,
--
Andrew
nm...@cam.ac.uk
Andrew Reilly <areil...@bigpond.net.au> wrote:
>
>Its arrays (and strings) are bounds-safe and first-class, so there's a
>big tick-box from the security crowd.
Nah. A small one. Seriously. Modern Fortran can tick both of those
boxes, for example, as could Algol 68 and PL/I. While they account
for a lot of errors made by inexperienced and undisciplined coders,
the really foul problems arise in the areas of aliasing and scoping.
>Its solution to losing pointer arithmetic is to make array slices first
>class. Array slices know how large the underlying array is, so bounds
>are still checked.
As in Algol 68, PL/I and modern Fortran.
>If you read most of the doco at the site and some of the comments on the
>mailing list/google group, its clear that several largish issues have
>been punted into the "too hard: we'd like that but don't know how"
>basket, so it is certainly quite green.
I will take a look, but I will bet that they include aliasing and scoping.
In particular, and relating to the paragraph of yours I snipped, those
are THE areas that are brought to the fore by shared-memory parallelism
and asynchronicity.
Regards,
Nick Maclaren.
Andrew Reilly
> In article <7m1cksF...@mid.individual.net>, Andrew Reilly
> <areil...@bigpond.net.au> wrote:
>>
>>Its arrays (and strings) are bounds-safe and first-class, so there's a
>>big tick-box from the security crowd.
>
> Nah. A small one. Seriously. Modern Fortran can tick both of those
> boxes, for example, as could Algol 68 and PL/I. While they account for
> a lot of errors made by inexperienced and undisciplined coders, the
> really foul problems arise in the areas of aliasing and scoping.
While that's certainly true, none of those smell like "C", even a little
bit. They're also "old", and so stand little chance of picking up new
converts. (sadly) There are lots (and lots) (most?) of other languages
that have first class arrays (Modula-x, Ada, D, Java, C#, lisp/scheme,
everything). They just don't seem to be particularly popular.
> I will take a look, but I will bet that they include aliasing and
> scoping.
I don't think that it's as bad as it is in C: lack of pointer arithmetic
means that you can only pass arrays by the base address or through
slices. You might still be able to mess everything up through abuse of
*void. I'll have to check...
> In particular, and relating to the paragraph of yours I snipped, those
> are THE areas that are brought to the fore by shared-memory parallelism
> and asynchronicity.
It *does* seem that they're trying to guide people away from (mutable)
shared-memory altogether. Not even sure that they've got mutexes and
semaphores. "Pass messages, CSP-style" seems to be the design. The
gotcha is that it is possible to pass mutable structures and these can be
modified asynchonously. The comments in the mailing list simply said
"don't do that"...
Cheers,
--
Andrew
nm...@cam.ac.uk
Andrew Reilly <areil...@bigpond.net.au> wrote:
>>
>> Nah. A small one. Seriously. Modern Fortran can tick both of those
>> boxes, for example, as could Algol 68 and PL/I. While they account for
>> a lot of errors made by inexperienced and undisciplined coders, the
>> really foul problems arise in the areas of aliasing and scoping.
>
>While that's certainly true, none of those smell like "C", even a little
>bit. They're also "old", and so stand little chance of picking up new
>converts.
Technically, that isn't the case, but politically perhaps.
>There are lots (and lots) (most?) of other languages
>that have first class arrays (Modula-x, Ada, D, Java, C#, lisp/scheme,
>everything). They just don't seem to be particularly popular.
That is not true. I would need to look at some of those again to
double check, but Java and C# don't, and I am pretty sure that
Modula-x and D don't. I doubt that Lisp or Scheme do, but haven't
looked at them in years. Fortran hasn't retained its followers for
no reason - and one reason is that its array handling is SO much
better than almost all of its competitors.
>> I will take a look, but I will bet that they include aliasing and
>> scoping.
>
>I don't think that it's as bad as it is in C: lack of pointer arithmetic
>means that you can only pass arrays by the base address or through
>slices. You might still be able to mess everything up through abuse of
>*void. I'll have to check...
There is no problem in causing the trouble in languages without
pointers - try Fortran 77, for a start.
>> In particular, and relating to the paragraph of yours I snipped, those
>> are THE areas that are brought to the fore by shared-memory parallelism
>> and asynchronicity.
>
>It *does* seem that they're trying to guide people away from (mutable)
>shared-memory altogether. Not even sure that they've got mutexes and
>semaphores. "Pass messages, CSP-style" seems to be the design. The
>gotcha is that it is possible to pass mutable structures and these can be
>modified asynchonously. The comments in the mailing list simply said
>"don't do that"...
Precisely. That's known as throwing the baby out with the bathwater,
which is what Pascal and (most of?) the Modulas did with arrays.
Simply eliminating mutable shared-memory merely converts the problem
from an aliasing one to a logical one, in the same was as universal
garbage collection merely converts the problem from scoping to a
logical one. A broken design will fail in either case, but in
different ways. A correct design will work in either case.
Regards,
Nick Maclaren.
Torben Ægidius Mogensen
The above are good ideas, certainly, but they are neither new nor very
radical. As said, CSP-like concurrency is known from Erlang, but also
from Occam before this. Bounds-safe arrays all the way back to Algol
60, and them being first-class is nothing new either. Array slices are
very much like the "fat pointers" of Cyclone and closures are also old
hat (Algol 60 thunks were very similar and real closures go back at
least to ML).
I have seen better thought-trough designs for new systems-programming
languages.
Torben
Rob Warnock
+---------------
| Andrew Reilly <areil...@bigpond.net.au> wrote:
| >There are lots (and lots) (most?) of other languages
| >that have first class arrays (Modula-x, Ada, D, Java, C#, lisp/scheme,
| >everything). They just don't seem to be particularly popular.
|
| That is not true. I would need to look at some of those again to
| double check, but Java and C# don't, and I am pretty sure that
| Modula-x and D don't. I doubt that Lisp or Scheme do, but haven't
| looked at them in years.
Scheme [R5RS, I don't know R6RS very well] certainly has first-class
vectors [single-dimension arrays]; but Common Lisp has first-class
multidimensional arrays, including the ability to dynamically re-use
the storage as a different "shape" [the :DISPLACED-TO arguments to
MAKE-ARRAY] at runtime. Said another way, array displacing gives you
a clean way to do bounds-checked aliasing.
Unfortunately, Common Lisp *doesn't* provide "slices"; displaced arrays
must be dense in their usage of the underlying storage [though they
need not cover *all* of it, see the :DISPLACED-INDEX-OFFSET argument
to MAKE-ARRAY].
Common Lisp also provides ROW-MAJOR-AREF, which allows safe access to
the underlying storage of an array, that is, lets you view any array
as a vector in row-major order. [It also has ARRAY-ROW-MAJOR-INDEX,
which takes an array and a list of indices and returns an index to
that element suitable for use by ROW-MAJOR-AREF.]
-Rob
-----
Rob Warnock <rp...@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
Noob
> Anyone else here had a positive initial reaction to the "go" language at
> http://golang.com/ ? It's a Rob Pike et-al C-family (via lingo and
> oberon) native-compilation language explicitly intended to support large-
> scale parallelism with erlang-style CSP (in the language, rather than as
> a library.)
Seems a storm (in a teacup) is brewing :-)
Google Under Fire For Calling Their Language "Go"
http://developers.slashdot.org/story/09/11/12/1256234/Google-Under-Fire-For-Calling-Their-Language-Go
http://en.wikipedia.org/wiki/Go_(programming_language)
http://en.wikipedia.org/wiki/Go!_(programming_language)
eternal september
<nm...@cam.ac.uk> wrote in message
news:hdgs8g$b25$1...@soup.linux.pwf.cam.ac.uk...
> In article <7m29g5F...@mid.individual.net>,
> Andrew Reilly <areil...@bigpond.net.au> wrote:
>>>
>>There are lots (and lots) (most?) of other languages
>>that have first class arrays (Modula-x, Ada, D, Java, C#, lisp/scheme,
>>everything). They just don't seem to be particularly popular.
>
> That is not true. I would need to look at some of those again to
> double check, but Java and C# don't, and I am pretty sure that
> Modula-x and D don't. I doubt that Lisp or Scheme do, but haven't
> looked at them in years. Fortran hasn't retained its followers for
> no reason - and one reason is that its array handling is SO much
> better than almost all of its competitors.
Not sure which D you are referring to (and what are your criteria for first
class), but Digital Mars D has built-in arrays (int[] myIntArray;).
Ned
nm...@cam.ac.uk
eternal september <ned...@yahoo.com> wrote:
>>>>
>>>There are lots (and lots) (most?) of other languages
>>>that have first class arrays (Modula-x, Ada, D, Java, C#, lisp/scheme,
>>>everything). They just don't seem to be particularly popular.
>>
>> That is not true. I would need to look at some of those again to
>> double check, but Java and C# don't, and I am pretty sure that
>> Modula-x and D don't. I doubt that Lisp or Scheme do, but haven't
>> looked at them in years. Fortran hasn't retained its followers for
>> no reason - and one reason is that its array handling is SO much
>> better than almost all of its competitors.
>
>Not sure which D you are referring to (and what are your criteria for first
>class), but Digital Mars D has built-in arrays (int[] myIntArray;).
Well, firstly, supporting merely vectors (i.e. only one-dimensional
arrays) scarcely counts. Even some of the autocodes did that, and
multi-dimensional arrays have been standard in high-level languages
since the 1950s.
Secondly, to count as "first-class", at the very least the language
has to permit the arrays to be operated on as composite objects,
and include at least the basic array-specific operations (such as
subsections).
Look at Algol 68, Fortran 90/95/2003, PL/I (if I recall correctly),
Matlab and so on.
Regards,
Nick Maclaren.
Andrew Reilly
That's a substantially stronger meaning for "first class" than I was
using, and in that sense, Go doesn't have 'em. I was using first class
in the common computer science sense that they are types supplied by and
managed by the language itself, rather than by user-supplied libraries or
by convention.
> Look at Algol 68, Fortran 90/95/2003, PL/I (if I recall correctly),
> Matlab and so on.
Heck, even interpreted Basic had multi-dimensional arrays. Languages
have definitely gone backwards in that respect, over the years. Clearly
language designers don't do any actual computation; stopping when they've
got something that can be used to write compilers and operating systems,
as though that was enough.
In your sense, of the languages that I mentioned before, only lisp has
proper first-class multi-dimensional arrays. Maybe Ada (I don't know it
at all.) Scheme has some widely-available standards-track (SRFI) multi-
dimensional arrays in libraries. C++ has quite fancy arrays supplied by
template libraries, even though it doesn't have first-class arrays or
vectors at all. Work-arounds for lack of garbage collection make it a
bit more painful to use than fully-collected systems like Matlab.
Matlab's arrays are limited to two dimensions.
Cheers,
--
Andrew
nm...@cam.ac.uk
Andrew Reilly <areil...@bigpond.net.au> wrote:
>>
>> Secondly, to count as "first-class", at the very least the language has
>> to permit the arrays to be operated on as composite objects, and include
>> at least the basic array-specific operations (such as subsections).
>
>That's a substantially stronger meaning for "first class" than I was
>using, and in that sense, Go doesn't have 'em. I was using first class
>in the common computer science sense that they are types supplied by and
>managed by the language itself, rather than by user-supplied libraries or
>by convention.
Yup.
Since the "computer science" bandwagon started rolling, a good half
of it has been abusing existing concepts and terminology, often
dumbing them down to the point where even facile results can be
claimed to be innovative.
I predate that bandwagon, and do not wish to be associated with it.
More to the point, many of the great names of computing didn't,
either.
>> Look at Algol 68, Fortran 90/95/2003, PL/I (if I recall correctly),
>> Matlab and so on.
>
>Heck, even interpreted Basic had multi-dimensional arrays. Languages
>have definitely gone backwards in that respect, over the years. Clearly
>language designers don't do any actual computation; stopping when they've
>got something that can be used to write compilers and operating systems,
>as though that was enough.
Precisely. When I, the Fortran community, and people like that refer
to concepts, we are referring to them for actual use.
Regards,
Nick Maclaren.
Anton Ertl
>On Sat, 14 Nov 2009 15:43:19 +0000, nmm1 wrote:
>> Secondly, to count as "first-class", at the very least the language has
>> to permit the arrays to be operated on as composite objects, and include
>> at least the basic array-specific operations (such as subsections).
Nick playing Humpty-Dumpty as usual.
>That's a substantially stronger meaning for "first class" than I was
>using, and in that sense, Go doesn't have 'em. I was using first class
>in the common computer science sense that they are types supplied by and
>managed by the language itself, rather than by user-supplied libraries or
>by convention.
That's not the common meaning used in programming language terminology
(and Nick's meaning isn't either). A first-class type in a
programming language is a type on which you can performq all the
non-type-specific operations of the programming language.
E.g., in C you can have variables of type int, you can copy ints by a
simple assignment, you can pass them to a function as parameter, and
return them as function result, you can create arrays of ints and have
int fields in structs and unions. So, int is a first-class data type
in C. You can also do all of these things for structs, so structs are
first-class data types in (modern) C. You cannot do all of these
things for arrays (you can do some, but for others you only get a
pointer to the first element), so arrays are not a first-class data
type in C.
- anton
--
M. Anton Ertl Some things have to be seen to be believed
an...@mips.complang.tuwien.ac.at Most things have to be believed to be seen
http://www.complang.tuwien.ac.at/anton/home.html
nm...@cam.ac.uk
Anton Ertl <an...@mips.complang.tuwien.ac.at> wrote:
>
>>That's a substantially stronger meaning for "first class" than I was
>>using, and in that sense, Go doesn't have 'em. I was using first class
>>in the common computer science sense that they are types supplied by and
>>managed by the language itself, rather than by user-supplied libraries or
>>by convention.
>
>That's not the common meaning used in programming language terminology
>(and Nick's meaning isn't either). A first-class type in a
>programming language is a type on which you can performq all the
>non-type-specific operations of the programming language.
The aphorism "Nothing to do with computing and not a science" fits
that usage extremely well.
In many languages, there are NO non-type-specific operations, for
a start! None, zilch, zero, nihilum, de nada, .... Indeed, that
is true of MOST traditional languages, definitely not excluding
C, C++ and Fortran.
I will give you that, UNLIKE so many of the terms that computer
scientists have abused to justify their non-results, the term
"first-class type" did originate in computer science. But my
recollection is that it meant closer to my definition than yours
when it was first introduced.
Regards,
Nick Maclaren.
ChrisQ
Just one question from this. Are there languages that pass whole arrays
through the call interface
?. ie: Langauges that don't support pointers in the language definition
must still use pointers at some point internally, or use some sort of
global mechanism. Copying a very large array would be very inefficient.
How does Fortran handle this internally, early and later versions ?...
Regards,
Chris
nm...@cam.ac.uk
ChrisQ <me...@devnull.com> wrote:
>
>Just one question from this. Are there languages that pass whole arrays
>through the call interface
>?. ie: Langauges that don't support pointers in the language definition
>must still use pointers at some point internally, or use some sort of
>global mechanism. Copying a very large array would be very inefficient.
Yes, many, starting (?) from Algol 60.
>How does Fortran handle this internally, early and later versions ?...
It's unspecified in all versions, and compilers differ. No stronger
statement is universally true.
Regards,
Nick Maclaren.
Anton Ertl
>Just one question from this. Are there languages that pass whole arrays
>through the call interface
>?. ie: Langauges that don't support pointers in the language definition
>must still use pointers at some point internally, or use some sort of
>global mechanism. Copying a very large array would be very inefficient.
The language can leave this to the programmer to decide, just like C
does for structs.
Also, there are languages where it does not make a difference, because
the array cannot be modified, e.g., functional languages.
Or the language can pass all types by reference, without a
call-by-value option. Then such an option is not necessary for arrays
to be first-class.
>How does Fortran handle this internally, early and later versions ?...
AFAIK Fortran has language restrictions (such as disallowing aliasing
of parameters) that allow the implementation to choose between passing
parameters by reference or by value-return. And that's the same for
all types.
(see below)
Reilly" <areil...@bigpond.net.au> wrote:
> On Sat, 14 Nov 2009 15:43:19 +0000, nmm1 wrote:
...
>> Well, firstly, supporting merely vectors (i.e. only one-dimensional
>> arrays) scarcely counts. Even some of the autocodes did that, and
>> multi-dimensional arrays have been standard in high-level languages
>> since the 1950s.
>>
>> Secondly, to count as "first-class", at the very least the language has
>> to permit the arrays to be operated on as composite objects, and include
>> at least the basic array-specific operations (such as subsections).
>
> That's a substantially stronger meaning for "first class" than I was
> using, and in that sense, Go doesn't have 'em. I was using first class
> in the common computer science sense that they are types supplied by and
> managed by the language itself, rather than by user-supplied libraries or
> by convention.
...
> In your sense, of the languages that I mentioned before, only lisp has
> proper first-class multi-dimensional arrays. Maybe Ada
It does.
FWIW, I agree with Nick's definition, and his complaint about abusing
existing concepts and terminology.
--
Bill Findlay
<surname><forename> chez blueyonder.co.uk
ChrisQ
> ChrisQ <me...@devnull.com> writes:
>> Just one question from this. Are there languages that pass whole arrays
>> through the call interface
>> ?. ie: Langauges that don't support pointers in the language definition
>> must still use pointers at some point internally, or use some sort of
>> global mechanism. Copying a very large array would be very inefficient.
>
> The language can leave this to the programmer to decide, just like C
> does for structs.
What i'm getting at is the mechanism that the system provides, either
compiler or linker, to pass the address of an array from a calling
function to the called, in languages that don't support pointers. You
either have to declare the array global, so the linker can find it and
do the necessary association, or do some other skullduggery under the hood.
I understand the thing about structures and on Vax assembler there was a
'call by descriptor' which calls by reference to a 'frame' of variables.
I always saw that as the equivalent of a pointer to structure in C.
How did the world of serious programming get by before pointers ?...
Regards,
Chris
nm...@cam.ac.uk
ChrisQ <me...@devnull.com> wrote:
>
>What i'm getting at is the mechanism that the system provides, either
>compiler or linker, to pass the address of an array from a calling
>function to the called, in languages that don't support pointers. You
>either have to declare the array global, so the linker can find it and
>do the necessary association, or do some other skullduggery under the hood.
You are thoroughly confused, I am afraid. The facilities supported
by a language and the facilities used by its implementation are,
to a first approximation, entirely unrelated.
>I understand the thing about structures and on Vax assembler there was a
>'call by descriptor' which calls by reference to a 'frame' of variables.
>I always saw that as the equivalent of a pointer to structure in C.
Well, vaguely.
>How did the world of serious programming get by before pointers ?...
It used indices. In any case, at the bottom level, a pointer is
nothing more than an index into the array of words/bytes/whatevers
that is mapped to all memory.
That is for modern, flat-memory, systems, of course. Segmented
memory ones are slightly different and capability ones are very
different.
Regards,
Nick Maclaren.
Robert Myers
> What i'm getting at is the mechanism that the system provides, either
> compiler or linker, to pass the address of an array from a calling
> function to the called, in languages that don't support pointers. You
> either have to declare the array global, so the linker can find it and
> do the necessary association, or do some other skullduggery under the hood.
>
> I understand the thing about structures and on Vax assembler there was a
> 'call by descriptor' which calls by reference to a 'frame' of variables.
> I always saw that as the equivalent of a pointer to structure in C.
>
> How did the world of serious programming get by before pointers ?...
>
Common blocks in Fortran do everything you want, only without a net.
A common block base address is globally known (it's an external to the
linker), and you (in any version of Fortran I ever used), you could
(whether legally or not) use that base address to point to anything
within the common block or beyond by renaming variables, overrunning
or under-running subscript arrays, or just about anything else
imaginable. The potential for mischief, spectacular stupidity, and
mysterious bugs was almost unlimited. Nothing in the language
enforced consistency in common block declarations between compilation
units. That could be a powerful tool if you knew what you were doing,
or a chronic invitation to disaster if you didn't.
Robert.
ChrisQ
> You are thoroughly confused, I am afraid. The facilities supported
> by a language and the facilities used by its implementation are,
> to a first approximation, entirely unrelated.
No wonder we are in so much trouble with performance if there's such a
wide gulf :-). Sorry, but the question was quite simple in the way that
how languages that don't support pointers or the implicit taking of an
address, pass arrays to called functions ?. This is not specific to any
language, more a function of the compiler or linker, but the language
must provide some mechanism to do this.
>
> It used indices. In any case, at the bottom level, a pointer is
> nothing more than an index into the array of words/bytes/whatevers
> that is mapped to all memory.
Not necessarily. A pointer access usually translates directly to a
register indirect access, with or without auto increment or decrement to
provide the indexing capability. Indexed addressing modes may be used
where the compiler knows that this is more efficient for a particular
machine, but the address of the array must still be taken at some point
to index from and it's not usually as efficient as register indirect mode...
Regards,
Chris
ChrisQ
>>
> Common blocks in Fortran do everything you want, only without a net.
> A common block base address is globally known (it's an external to the
> linker), and you (in any version of Fortran I ever used), you could
> (whether legally or not) use that base address to point to anything
> within the common block or beyond by renaming variables, overrunning
> or under-running subscript arrays, or just about anything else
> imaginable. The potential for mischief, spectacular stupidity, and
> mysterious bugs was almost unlimited. Nothing in the language
> enforced consistency in common block declarations between compilation
> units. That could be a powerful tool if you knew what you were doing,
> or a chronic invitation to disaster if you didn't.
>
> Robert.
>
Thanks. Never had much to do with Fortran, but an interesting way of
dealing with the problem. Obviously dates back to an earlier age before
concepts such as encapsulation and library based development.
I guess the last sentence says it all really and suggests that a
language needs to have potentially dangerous features to get anything
usefull done at all :-)...
Regards,
Chris
Anton Ertl
>What i'm getting at is the mechanism that the system provides, either
>compiler or linker, to pass the address of an array from a calling
>function to the called, in languages that don't support pointers.
Pointers are just the name of some programming language features
(e.g., in C and Pascal; they are translated to addresses on the
machine level). Some other languages have other features (some not
named "pointer") that are translated into addresses.
And some languages have features that may be translated into
addresses, but can also be implemented in other ways. E.g., in
Fortran 77, there are no pointers or addresses or references, but
parameters may be implemented by passing the address, or by passing
and returning the value.
>You
>either have to declare the array global, so the linker can find it and
>do the necessary association
If you access a global array from several functions, why do you
consider that to be passing the address?
I think I still don't get what you want to know.
>How did the world of serious programming get by before pointers ?...
Well, of course before C (and its pointers) the serious (aka real)
programmers programmed in assembly language, and there they used
addresses:-).
Stephen Fuld
I think the other posters who answered your question are missing the the
"simpleness" of your question. In Fortran when you call a function or a
subroutine, you pass it a list of variables which are called the actual
arguments. These can be simple variables or arrays. You just use the
name. In the subroutine or function, you have an argument list (called
the dummy arguments) that should "match" the order and types of the
actual arguments, though the names are arbitrary. If the actual
argument is an array, the corresponding dummy argument should be an
array. In the simples case, the dimensions (note the pleural as Fortran
supports multi-dimensional arrays) should match, but there are legal
ways to have the dummy array get its size from the actual arguments.
The mechanism using common blocks that Robert talked about is an
alternative that is typically used for more complex situations (i.e. a
set of variables shared among several subroutines.)
If you want to pass a particular element of an array, you use use the
relevant subscripts in the actual argument, as Nick pointed out. In
that case, the dummy argument would not be an array, but a scaler of the
appropriate type.
There are all sorts of ways of abusing this, but in general it works
pretty well. You can have errors, but I think the potential for
inadvertent errors is a lot less than the general use/abuse of pointers
the C encourages/requires.
--
- Stephen Fuld
(e-mail address disguised to prevent spam)
Robert Myers
wrote:
> ChrisQ wrote:
> > Anton Ertl wrote:
Fortran was actually a base address and some block of allocated
contiguous storage that would be known in any routine that declared
it. The base address could be globally known whenever it was declared
within a main program or subroutine. Absolutely the only thing that
was guaranteed was the common block base address. Everything else was
up to the programmer to keep track of.
While you *could* copy the common block and use the same ways of
referring to offsets within it within every occurrence, you didn't
have to. You could change the data type, or the name, or whether
something was an array or not and, if so, how if was addressed. If
was a very powerful mechanism, but also very dangerous. It could be
base address plus (optionally labelled) offset programming, just like
in assembly language.
Robert.
nm...@cam.ac.uk
Robert Myers <rbmye...@gmail.com> wrote:
>
>While you *could* copy the common block and use the same ways of
>referring to offsets within it within every occurrence, you didn't
>have to. You could change the data type, or the name, or whether
>something was an array or not and, if so, how if was addressed. If
>was a very powerful mechanism, but also very dangerous. It could be
>base address plus (optionally labelled) offset programming, just like
>in assembly language.
The Department of Obfuscation writes:
In OpenMP, you can specify that COMMON blocks are private to threads
(i.e. every thread has a separate copy).
Regards,
Nick Maclaren.
ChrisQ
>
> I think the other posters who answered your question are missing the the
> "simpleness" of your question. In Fortran when you call a function or a
> subroutine, you pass it a list of variables which are called the actual
> arguments. These can be simple variables or arrays. You just use the
> name. In the subroutine or function, you have an argument list (called
> the dummy arguments) that should "match" the order and types of the
> actual arguments, though the names are arbitrary. If the actual
> argument is an array, the corresponding dummy argument should be an
> array. In the simples case, the dimensions (note the pleural as Fortran
> supports multi-dimensional arrays) should match, but there are legal
> ways to have the dummy array get its size from the actual arguments.
>
> The mechanism using common blocks that Robert talked about is an
> alternative that is typically used for more complex situations (i.e. a
> set of variables shared among several subroutines.)
>
> If you want to pass a particular element of an array, you use use the
> relevant subscripts in the actual argument, as Nick pointed out. In
> that case, the dummy argument would not be an array, but a scaler of the
> appropriate type.
>
>
> There are all sorts of ways of abusing this, but in general it works
> pretty well. You can have errors, but I think the potential for
> inadvertent errors is a lot less than the general use/abuse of pointers
> the C encourages/requires.
>
The question was more about the internals and how variables like arrays
are communicated between functions in languages that don't support
pointers or the taking of an address, at programmer level. Robert's post
about common blocks was very good, but it seems very limiting to think
that some languages effectively have only call by value or a global
mechanism to do this.
I'm quite glad that I learned a procedural language first. It was all
assembler in the early days and never liked basic at all. C was a
revelation in 1983 and the structure of the language translated mentally
into an assembler mind set very well. That is, it was easy to visualise
how C constructs became machine instructions. For someone coming from a
hardware background, it was important to have visibility of the whole
process to be confident about the results. C provided that and still does.
If there were any of the older languages that I would like to have a
play with, it would be something like Algol 68, though there are
probably no embedded target compilers available...
Regards,
Chris
Stephen Fuld
Yes, of course I agree. But I was trying to answer what I thought was a
very basic question without getting too much into the complexities. I
took the basic tenor of his question as "How could you possible have a
programming language without pointers", and coming from someone too
young to realize that it had been done many times. I was just trying to
show that you could (with the caveat of no dynamically allocated storage
- although there were some language extensions that even allowed that).
Stephen Fuld
Arrrgh! What would anyone choose to abuse the language like that??? :-(
nm...@cam.ac.uk
Stephen Fuld <SF...@Alumni.cmu.edu.invalid> wrote:
>>
>> The Department of Obfuscation writes:
>>
>> In OpenMP, you can specify that COMMON blocks are private to threads
>> (i.e. every thread has a separate copy).
>
>Arrrgh! What would anyone choose to abuse the language like that??? :-(
I am currently writing a course on OpenMP. That is one feature that
I shall not be teaching (except, perhaps, to say "don't") :-)
Regards,
Nick Maclaren.
Stephen Fuld
When you use the subroutine/function call mechanism, what typically got
passed was the address of the variable. In the case of an array, it was
the address of the first element of the array.
Of course, with common blocks, you didn't pass anything and the linker
made sure that all the references to variables within common blocks got
resolved correctly.
Robert's post
> about common blocks was very good, but it seems very limiting to think
> that some languages effectively have only call by value or a global
> mechanism to do this.
>
> I'm quite glad that I learned a procedural language first. It was all
> assembler in the early days and never liked basic at all. C was a
> revelation in 1983 and the structure of the language translated mentally
> into an assembler mind set very well. That is, it was easy to visualise
> how C constructs became machine instructions. For someone coming from a
> hardware background, it was important to have visibility of the whole
> process to be confident about the results. C provided that and still does.
While I understand that C would be easier to learn when coming from a
hardware/assembler background, you should understand that it has a lot
of disadvantages (IMHO, of course), that cause problems for many
programmers. Again, IMHO, allowing the programmer to do pretty much
anything with pointers (i.e. pointer arithmetic) is the source of many
problems.
> If there were any of the older languages that I would like to have a
> play with, it would be something like Algol 68, though there are
> probably no embedded target compilers available...
BTW, in the late 1970's, I was developing code for a bit slice
microprocessor used in our proprietary disk controller. The code was
assembler level, of course, and the assembler itself was written in
Fortran. It worked pretty well.
Andrew Reilly
> Sorry, but the question was quite simple in the way that how languages
> that don't support pointers or the implicit taking of an address, pass
> arrays to called functions ?. This is not specific to any language, more
> a function of the compiler or linker, but the language must provide some
> mechanism to do this.
What makes you think that there is any such language? The only languages
that I know of that don't pass an address for large objects to called
functions are either the ones that just don't have function call
arguments, use extra indirection (handles of some sort) or pass instead a
closure or future or object that will compute the "array" elements on
demand.
Pretty much everything else just passes a pointer to the data or the meta-
data).
Cheers,
--
Andrew
Rob Warnock
for a while since it seemed liekly someone else in this thread was
going to pick this up & elaborate, but no joy... So here goes...]
<nm...@cam.ac.uk> wrote:
+---------------
| ChrisQ <me...@devnull.com> wrote:
| >Just one question from this. Are there languages that pass whole arrays
| >through the call interface
| >?. ie: Langauges that don't support pointers in the language definition
| >must still use pointers at some point internally, or use some sort of
| >global mechanism. Copying a very large array would be very inefficient.
|
| Yes, many, starting (?) from Algol 60.
+---------------
Algol 60 is particularly weird (at least by current standards), since
it was *none* of "call by value", "call by reference" (pointers), nor
"call by copy-in/copy-out", but was instead "call by name" -- a terribly
misleading term which probably should have been "call by alias" or
"call by proxy" or something. See:
http://en.wikipedia.org/wiki/Evaluation_strategy#Call_by_name
...
Call by name
In call-by-name evaluation, the arguments to functions are not
evaluated at all -- rather, function arguments are substituted
directly into the function body using capture-avoiding substitution.
If the argument is not used in the evaluation of the function,
it is never evaluated; if the argument is used several times,
it is re-evaluated each time. (See Jensen's Device.)
http://en.wikipedia.org/wiki/Jensen%27s_Device
http://en.wikipedia.org/wiki/Thunk
In Algol 60, arguments were actually passed internally as "thunks" --
accessor and [for things that were single objects, such as constants
or variables or arrays, but *not* complex expressions] setter functions,
usually dynamically constructed on the stack so as to properly capture
the lexical environment in the caller [the "capture-avoiding substitution"
mentioned in the wikipedia article]. The semantics of "call by name" are
that *each* reference to a parameter must act "as if" you had at that
point jumped back into the caller and (re)evaluated the argument IN THE
CALLING LEXICAL ENVIRONMENT. This could produce some rather weird effects,
the most memorable of which was enshrined as "Jensen's Device" (q.v.),
which allowed a called function to [among other things] access multiple
elements of arrays by passing *both* some expression involving arrays
*and* the relevant indices involved in the expression. The key hack is
that if IN THE CALLEE one assigns a new value to a formal parameter,
then the value of the *actual* parameter is also changed IN THE CALLER!
Moreover, any other actual parameters which are functions of the changed
parameter are *also* changed!
The above URL to "Jensen's Device" gives one example in correct
Algol 60, but here's another in simpler C-like pseudocode:
int sum(int n, int i, int thing) {
int accum = 0;
for(i = 0; i < n; ++i)
accume += thing;
return accum;
}
Now in real C, the only possible result is "tmp = thing, tmp * n",
but if we call the above as follows in a call-by-name language:
int a[100] = {...some contents...};
int b[100] = {...some contents...};
int k = 17;
int c = sum(100, k, a[k] * b[k]);
then what's in "c" is *not* 100*a[17]*b[17], but instead is the dot-product
of the arrays "a" & "b"!! That is, a[0]*b[0] + a[1]*b[1] ... + a[99]*b[99]!!
That's because each time "i" gets assigned within "sum()", "k" *also*
gets assigned, and each time "thing" is referenced within "sum()", the
expression "a[k]*b[k]" gets *re-evaluated* with the current/new value
of "k".
Told you it was weird... ;-}
-Rob
-----
Rob Warnock <rp...@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
John Levine
> since it was *none* of "call by value", "call by reference"
> (pointers), nor "call by copy-in/copy-out", but was instead "call by
> name" -- a terribly misleading term which probably should have been
> "call by alias" or "call by proxy" or something.
Alan Perlis, who was on the Algol 60 committee, told me that call by
name was a mistake. They were trying to come up with an elegant way
to describe Fortran-style call by reference, and didn't realize until
much later (perhaps when Jensen published his note) what they'd
invented instead.
Regards,
John Levine, jo...@iecc.com, Primary Perpetrator of "The Internet for Dummies",
Information Superhighwayman wanna-be, http://www.johnlevine.com, ex-Mayor
"More Wiener schnitzel, please", said Tom, revealingly.
nm...@cam.ac.uk
>> Algol 60 is particularly weird (at least by current standards),
>> since it was *none* of "call by value", "call by reference"
>> (pointers), nor "call by copy-in/copy-out", but was instead "call by
>> name" -- a terribly misleading term which probably should have been
>> "call by alias" or "call by proxy" or something.
>
>Alan Perlis, who was on the Algol 60 committee, told me that call by
>name was a mistake. They were trying to come up with an elegant way
>to describe Fortran-style call by reference, and didn't realize until
>much later (perhaps when Jensen published his note) what they'd
>invented instead.
Interesting. I didn't know that, and it makes a lot of sense, but
I have one niggle. You should have said "Fortran-style call by
association".
Mainstream Fortran has NEVER had call by reference, though some
versions of Fortran IV allowed it as a special hack (typically
enclosing arguments in slashes). Fortran has call by association,
which is very different and, as far as I know, is unique to Fortran.
Describing call by reference simply and cleanly isn't too bad;
describing call by association is very tricky.
Regards,
Nick Maclaren.
Ken Hagan
> No wonder we are in so much trouble with performance if there's such a
> wide gulf :-). Sorry, but the question was quite simple in the way that
> how languages that don't support pointers or the implicit taking of an
> address, pass arrays to called functions ?. This is not specific to any
> language, more a function of the compiler or linker, but the language
> must provide some mechanism to do this.
I suppose it depends on what you understand by "support ... the implicit
taking of an address". If the only way to imply the taking of an address
is argument passing, and the only way to receive that address elsewhere in
the program is a function body, then does the language support pointers? I
don't think so.
C++ supports exceptions and stack unwinding, now usually implemented with
lists of addresses of unwinding thunks that can be traversed and invoked
at run-time, with much mangling of stack pointers all along the way. None
of the tables, thunks or stack pointer manipulations are available to the
programmer in any other context.
Anton Ertl
>C was a
>revelation in 1983 and the structure of the language translated mentally
>into an assembler mind set very well. That is, it was easy to visualise
>how C constructs became machine instructions. For someone coming from a
>hardware background, it was important to have visibility of the whole
>process to be confident about the results. C provided that and still does.
Depends on what you mean by "C". The standards purists that dominate
in comp.lang.c and among the GCC maintainers mean the standardized
subset of what you or I understand as "C", and they think about it in
a very abstract way that is described in the standard document and is
totally removed from any concrete hardware.
What's worse, they claim that programs that do not conform to the
standard (i.e., most programs in the real world) do not have any
meaning, and that the compiler is allowed to compile them to anything;
and GCC does, at least with optimization; strangely, older versions of
GCC and (usually) GCC without optimization know quite well what is
meant by that supposedly meaningless program.
An example where GCC does not map C directly to machine instructions: I
needed to check whether a variable x with a 2s-complement integer
type (at least as long as int) has lowest representable value. One
way to check it is to do an equality compare with that value, but that
value is type-dependent, and the method is slow and uses quite a bit
of space on some platforms.
I was thinking in machine terms, and came up with the idea to check
whether x-1 wrapped around; the operation used for that would be the
signed comparison. The way to code this check in classic C is x<x-1.
Sure, that may not be the most obvious code, but that disadvantage was
acceptable for me in this situation.
But is it standard C? Probably because standard C is supposed to port
between different representations of signed numbers (2s-complement,
1s-complement, and sign-magnitude), wraparound is not defined for
signed numbers in standard C (it is defined for unsigned numbers).
In this particular case my program was only intended to work on
2s-complement machines, so I did not care if it would not port to
other machines (although I think that this particular test would still
work on other machines if the C compiler compiles it like I intended).
Yet GCC takes this as excuse for optimizing this program into not
working as intended even on 2s-complement machines.
Here's some experiments involving this example:
[c7:~/tmp:25848] cat xxx.c
#include <stdio.h>
#include <stdlib.h>
int check(int x)
{
return x<x-1;
}
int main(int argc, char *argv[])
{
if (check(atoi(argv[1])))
printf("smallest int\n");
else
printf("check failed\n");
return 0;
}
[c7:~/tmp:25849] gcc-4.0 -Wall xxx.c
[c7:~/tmp:25850] a.out -2147483648
smallest int
[c7:~/tmp:25851] gcc-4.0 -Wall -O2 xxx.c
[c7:~/tmp:25852] a.out -2147483648
check failed
This particular "optimization" seems to have caused enough trouble
that they added a warning in a later version:
[c7:~/tmp:25853] gcc-4.2 -Wall -O2 xxx.c
xxx.c: In function 'check':
xxx.c:5: warning: assuming signed overflow does not occur when assuming that (X - c) > X is always false
Of course one can work around this "optimization" by doing an equality
comparison with the smallest value, and maybe the compiler is smart
enough to compile it into code that uses the trick I wanted to use,
but that's even further from a direct mapping to machine operations.
And I doubt that the compiler uses the trick, so the end result is
that this "optimization" leads to bigger and often slower code.
Here's how gcc-4.3 compiles the workaround code (the integer type has
64 bits here) on an AMD64 machine:
0x0000000000404e5a <gforth_engine+3162>: mov $0x8000000000000000,%rax
0x0000000000404e64 <gforth_engine+3172>: cmp %rax,%r14
0x0000000000404e67 <gforth_engine+3175>: nop
0x0000000000404e68 <gforth_engine+3176>: jne 0x404e74 <gforth_engine+3188>
Terje Mathisen
> I was thinking in machine terms, and came up with the idea to check
> whether x-1 wrapped around; the operation used for that would be the
> signed comparison. The way to code this check in classic C is x<x-1.
> Sure, that may not be the most obvious code, but that disadvantage was
> acceptable for me in this situation.
>
> But is it standard C? Probably because standard C is supposed to port
> between different representations of signed numbers (2s-complement,
> 1s-complement, and sign-magnitude), wraparound is not defined for
> signed numbers in standard C (it is defined for unsigned numbers).
Since wraparound _is_ defined for unsigned, could you work around this
by a couple of casts, in order to force the compiler to do "as you want"?
I.e.
int is_lowest_signed(int64_t n)
{
uint64_t un = (uint64_t) n;
un--;
int64_t n_minus_1 = (int64_t) un;
return (n < n_minus_1);
}
(Or, since such casts are also somewhat problematical, could you use a
union to map a signed and an unsigned int type on top of each other?)
Terje
--
- <Terje.Mathisen at tmsw.no>
"almost all programming can be viewed as an exercise in caching"
Torben Ægidius Mogensen
> ChrisQ <me...@devnull.com> writes:
>>C was a
>>revelation in 1983 and the structure of the language translated mentally
>>into an assembler mind set very well. That is, it was easy to visualise
>>how C constructs became machine instructions. For someone coming from a
>>hardware background, it was important to have visibility of the whole
>>process to be confident about the results. C provided that and still does.
>
> Depends on what you mean by "C". The standards purists that dominate
> in comp.lang.c and among the GCC maintainers mean the standardized
> subset of what you or I understand as "C", and they think about it in
> a very abstract way that is described in the standard document and is
> totally removed from any concrete hardware.
I don't see this as a bad thing. A programming language that is meant
to be used across multiple platforms should not be specified in terms of
the behaviour of one specific concrete machine.
What I don't like is that the C standard leaves many things
machine-dependent, so you can't guarantee equivalent behaviour across
multiple platforms, even for programs that are legal by the standard.
It is not only the size of number types that are machine dependent: How
integer division of negative numbers round the result is another
example.
As for how close C is to "the machine" in a wider sense, I would say
that it is fairly close to most 1980s computers, but not so much to
recent hardware. The same closeness to the 1980s model of machine
execution that allowed C programmers to write programs that ran
efficiently on past hardware now hinder efficient exploitation of modern
hardware.
Torben
Torben Ægidius Mogensen
>> Algol 60 is particularly weird (at least by current standards),
>> since it was *none* of "call by value", "call by reference"
>> (pointers), nor "call by copy-in/copy-out", but was instead "call by
>> name" -- a terribly misleading term which probably should have been
>> "call by alias" or "call by proxy" or something.
>
> Alan Perlis, who was on the Algol 60 committee, told me that call by
> name was a mistake. They were trying to come up with an elegant way
> to describe Fortran-style call by reference, and didn't realize until
> much later (perhaps when Jensen published his note) what they'd
> invented instead.
What I heard from Peter Naur was that the purpose was to define a
parameter-passing mechanism that allowed unfolding/inlining without
changing behaviour: When you have a call f(<some expression>) and a
definition of f(x) with body B, you can replace the call with a copy of
B with all occurrences of x replaced by <some expression> (modulo
renaming to avoid variable capture).
If you don't allow side effects, call-by-name is actually quite natural,
as it gives results consistent with call-by-value but terminates more
often. It will, however, often take more time to finish, as you repeat
identical computations. For this reason, call-by-need (also called
"lazy evaluation") was introduced. This passes unevaluated parameters
like call-by-name, but evaluates a parameter at most once.
But in the presence of side-effects or exceptions, call-by-value,
call-by-name and call-by-need all give different results. So you need
to be much more careful about defining the exact behaviour of parameter
passing when designing a language with side-effects.
Torben
Bernd Paysan
> As for how close C is to "the machine" in a wider sense, I would say
> that it is fairly close to most 1980s computers, but not so much to
> recent hardware. The same closeness to the 1980s model of machine
> execution that allowed C programmers to write programs that ran
> efficiently on past hardware now hinder efficient exploitation of modern
> hardware.
I don't get this. Anton's example was that GCC rendered code that was well-
defined on two's complement into garbage, because it's not well-defined by
the C standard, which also allows one's complement machines. When did you
see your last one's complement machine? We need people like Lynn Wheeler to
remember that. Writing standards with one's complement in mind is mostly
bogus, and writing a C compiler so that it optimizes away things that won't
work on one's complement, which has not a single port to a one's complement
machine is even more bogus.
Current hardware is usually a lot less exotic than it used to be, and the
hardware model people have in mind when programming C is a reason. E.g.
take DSPs: They used to have word-addressed memory, so C didn't run well
(with C programmer's assumption of char=byte). So more recent DSPs are much
more likely byte addressed.
--
Bernd Paysan
"If you want it done right, you have to do it yourself"
http://www.jwdt.com/~paysan/
ChrisQ
>
> BTW, in the late 1970's, I was developing code for a bit slice
> microprocessor used in our proprietary disk controller. The code was
> assembler level, of course, and the assembler itself was written in
> Fortran. It worked pretty well.
>
>
From what i've heard, there were some early compilers written in Cobol,
so Fortran may not be such a bad choice. If a langauge is the only one
available, or the one you are most familiar with, then it probably makes
sense to use it. A friend in London wrote a 68k cross assembler, partly
in 6502 asm and partly in applesoft basic to run on an Apple II. It
produced good code, but there was no link capability. Just an include
directive to pull in more source files, so everything built at once !. I
bought a KIM1 for $100 in 1977 while working in the us. It was
completely new and unknown. An exciting time to be working in the art
and computing became something of an obsession that i'm still trying to
recover from even now :-).
I read Mick & Brick in the 80's, but never got the opportunity to do any
bit slice work. As an individual, the development tools and software
were too expensive and tended to run on vax or sun machines, both of
which I worked with later, but no chance at the time. There was also a
Philips 8x300 bipolar micro which looked interesting, which I think was
designed for disk controller type apps, but again, never had the
opportunity. Instead, spent 30 years or so in embedded systems, 6502,
680x, 68k and many others...
Regards,
Chris
nm...@cam.ac.uk
Torben =?iso-8859-1?Q?=C6gidius?= Mogensen <tor...@pc-003.diku.dk> wrote:
>
>But in the presence of side-effects or exceptions, call-by-value,
>call-by-name and call-by-need all give different results. So you need
>to be much more careful about defining the exact behaviour of parameter
>passing when designing a language with side-effects.
As do call-by-reference and call-by-association. Admittedly, the
last more-or-less means that any of the other four can be used,
and a different one could be used for each call, or even for
different sections of code within a single call :-)
Regards,
Nick Maclaren.
nm...@cam.ac.uk
Bernd Paysan <bernd....@gmx.de> wrote:
>Torben Ægidius Mogensen wrote:
>> As for how close C is to "the machine" in a wider sense, I would say
>> that it is fairly close to most 1980s computers, but not so much to
>> recent hardware. The same closeness to the 1980s model of machine
>> execution that allowed C programmers to write programs that ran
>> efficiently on past hardware now hinder efficient exploitation of modern
>> hardware.
>
>I don't get this. Anton's example was that GCC rendered code that was well-
>defined on two's complement into garbage, because it's not well-defined by
>the C standard, which also allows one's complement machines. When did you
>see your last one's complement machine? We need people like Lynn Wheeler to
>remember that. Writing standards with one's complement in mind is mostly
>bogus, and writing a C compiler so that it optimizes away things that won't
>work on one's complement, which has not a single port to a one's complement
>machine is even more bogus.
No, it's not. What you have missed is that over-specification and
optimisability are incompatible, which is perhaps the main reason
that the Java Grande project was so obviously doomed to being the
dismal failute that it was, and Fortran STILL rules in the high
performance arena.
Consider expressions like (M*N)/N, which are often in the middle of
performance-critical code in C, because of macro generation. gcc
quite rightly regards it as acceptable to simplify that to M; Java
does not. Ones' complement has nothing to do with it.
Regards,
Nick Maclaren.
ChrisQ
Sorry to quibble, but would argue that the coding style used isn't
explicit enough. In this case, they check() function is assuming a
definate order of evaluation for correct operation, which may not be the
case with optimisation turned on, irrespective of what the compiler
manual or C standard says. Also, you are using the result of an
arithmetic operation as a return flag, which might confuse the optimiser
if it works at global level. You have to assume that the compiler is
stupid. I would write it something like:
int check (int x) {
int y = x - 1;
if ( x < y) {
return 0;
}
else {
return 1;
}
}
I may have the sense wrong there, but you see what i'm driving at. It
might look labored, but only takes a few added lines of code. It makes
everything unambiguous and still gives plenty of scope for the optimiser
to do it's work. Ime, if you want complete portability and bug free
code, you need to be quite defensive in terms of coding style.
>
> 0x0000000000404e5a <gforth_engine+3162>: mov $0x8000000000000000,%rax
> 0x0000000000404e64 <gforth_engine+3172>: cmp %rax,%r14
> 0x0000000000404e67 <gforth_engine+3175>: nop
> 0x0000000000404e68 <gforth_engine+3176>: jne 0x404e74 <gforth_engine+3188>
>
Not familiar at all with amd64 asm, but why has it put a nop after the
compare ?. Does the following branch need to be aligned on a quad word
boundary or something ?...
Regards,
Chris
ChrisQ
Having gone on about coding style, I get exactly the same results as
you did on a Sparc 64, Sol 10 and gcc 3.4.3.
#include <stdio.h>
#include <stdlib.h>
int check (int x) {
int y = x - 1;
if ( x < y) {
return 1;
}
else {
return 0;
}
}
int main(int argc, char *argv[])
{
if (check(atoi(argv[1])))
printf("smallest int\n");
else
printf("check failed\n");
return 0;
}
(return sense was wrong).
darkstar: gcc -Wall main.c
darkstar: a.out -2147483648
smallest int
darkstar: gcc -Wall -O2 main.c
darkstar: a.out -2147483648
check failed
Perhaps use an insigned int to wrap to zero, on the basis that unsigned
and signed ints are the same size on most (?) machines and the smallest
value is thus inplied from this...
Regards,
Chris
Bernd Paysan
> Consider expressions like (M*N)/N, which are often in the middle of
> performance-critical code in C, because of macro generation. gcc
> quite rightly regards it as acceptable to simplify that to M; Java
> does not. Ones' complement has nothing to do with it.
Well, let's say it's a general potential overflow issue, and of course x<x-1
is one (it can only be true if x-1 overflows). And whether an expression
like M*N/N can be simplified IMHO simply depends on how you define the
multiplication: If you define it that it is widening (i.e. 32x32 -> 64
bits), *then* you can simplify without changing the semantics, i.e. ((long
long)M*N)/N. A Forth compiler could safely optimize away N N */, because */
is defined to widen up the intermediate result. This is a well-specified
operator that is friendly to the optimizer. C's * and / are under-specified
operators, which either cause surprises for the programmer, or are
impossible to optimize.
The point in question is always a quality of implementation issue: Do you
want to write programs that work or do you want to write programs that fail,
but incredibly fast so? Breaking existing programs (and many of them,
massively) is usually not an option to a compiler vendor.
nm...@cam.ac.uk
Bernd Paysan <bernd....@gmx.de> wrote:
>nm...@cam.ac.uk wrote:
>> Consider expressions like (M*N)/N, which are often in the middle of
>> performance-critical code in C, because of macro generation. gcc
>> quite rightly regards it as acceptable to simplify that to M; Java
>> does not. Ones' complement has nothing to do with it.
>
>want to write programs that work or do you want to write programs that fail,
>but incredibly fast so? Breaking existing programs (and many of them,
>massively) is usually not an option to a compiler vendor.
That is nonsense. It is FAR more often a question of whether you
want a broken program to give the same erroneous answers on all
systems (as Java specifies). 99 times out of a 100, overflow is
an ERROR, and all that Java and you do is to turn an arithmetic
error into a logical one.
Regards,
Nick Maclaren.
Anton Ertl
>Anton Ertl wrote:
>> I was thinking in machine terms, and came up with the idea to check
>> whether x-1 wrapped around; the operation used for that would be the
>> signed comparison. The way to code this check in classic C is x<x-1.
>> Sure, that may not be the most obvious code, but that disadvantage was
>> acceptable for me in this situation.
>>
>> But is it standard C? Probably because standard C is supposed to port
>> between different representations of signed numbers (2s-complement,
>> 1s-complement, and sign-magnitude), wraparound is not defined for
>> signed numbers in standard C (it is defined for unsigned numbers).
>
>Since wraparound _is_ defined for unsigned, could you work around this
>by a couple of casts, in order to force the compiler to do "as you want"?
I thought the same and gave it a try, but the result of my try was the
same with the gcc version that I tried. I am not enough of a
standards lawyer to know whether my program or gcc was not
standards-conforming in this case.
>(Or, since such casts are also somewhat problematical, could you use a
>union to map a signed and an unsigned int type on top of each other?)
That probably has a better chance of working in gcc, but I think the
cast has a better chance of being standards-compliant; also, if I have
to write a union definition, assignments to members and member
accesses, the source code becomes pretty large; and all that to
express two basic machine operations; not really something one would
expect in a language that's close to the machine.
Anton Ertl
>Anton Ertl wrote:
>> int check(int x)
>> {
>> return x<x-1;
>> }
>Sorry to quibble, but would argue that the coding style used isn't
>explicit enough. In this case, they check() function is assuming a
>definate order of evaluation for correct operation, which may not be the
>case with optimisation turned on, irrespective of what the compiler
>manual or C standard says.
No particular order is assumed (apart from data flow, which is
inevitable). Evaluating x-1 does not change x, if that's what you
have in mind. If you have something else in mind, please show the
evaluation order that you think would be legal and would have a
different result.
>> 0x0000000000404e5a <gforth_engine+3162>: mov $0x8000000000000000,%rax
>> 0x0000000000404e64 <gforth_engine+3172>: cmp %rax,%r14
>> 0x0000000000404e67 <gforth_engine+3175>: nop
>> 0x0000000000404e68 <gforth_engine+3176>: jne 0x404e74 <gforth_engine+3188>
>>
>
>Not familiar at all with amd64 asm, but why has it put a nop after the
>compare ?. Does the following branch need to be aligned on a quad word
>boundary or something ?...
It's not necessary as far as the architecture is concerned, so I guess
that it helps some implementation. However, this particular case is
strange, because I thought that the Core microarchitecture combines a
compare and a dependent branch into a macro-instruction, and such a
nop would hurt that; hmm, I remember that the macro-instructions don't
work in 64-bit mode, and maybe the nop is there to avoid a hickup due
to that. Can anyone shed light on this?
Bernd Paysan
> That is nonsense. It is FAR more often a question of whether you
> want a broken program to give the same erroneous answers on all
> systems (as Java specifies). 99 times out of a 100, overflow is
> an ERROR, and all that Java and you do is to turn an arithmetic
> error into a logical one.
Are you sure? I've had, more than 10 years ago, some similar discussion
with a VHDL guy, who claimed that VHDL's error handling of overflow was
right, and at the same time, he made stupid mistakes like converting a bit
vector to an integer, adding one, and then converting it back to the bit
vector again, which caused the simulator to bail out on the wraparound
(which was intended as such). Resulted in constructs like when i=15 then 0
else i+1 or so, cluttering up the code, generating lots of unnecessary
comparators and multiplexers, and still missing this or that case where it
would have been necessary, too.
It is quite surprising how often you just want bit vectors (i.e. a mod 2^n
group), not integers. Especially, when you are close to the hardware. For
numerical applications, your 99% figure is probably right. But most C
programs aren't numerical applications.
Anton Ertl
>an...@mips.complang.tuwien.ac.at (Anton Ertl) writes:
>
>> ChrisQ <me...@devnull.com> writes:
>>>C was a
>>>revelation in 1983 and the structure of the language translated mentally
>>>into an assembler mind set very well. That is, it was easy to visualise
>>>how C constructs became machine instructions. For someone coming from a
>>>hardware background, it was important to have visibility of the whole
>>>process to be confident about the results. C provided that and still does.
>>
>> Depends on what you mean by "C". The standards purists that dominate
>> in comp.lang.c and among the GCC maintainers mean the standardized
>> subset of what you or I understand as "C", and they think about it in
>> a very abstract way that is described in the standard document and is
>> totally removed from any concrete hardware.
>
>I don't see this as a bad thing. A programming language that is meant
>to be used across multiple platforms should not be specified in terms of
>the behaviour of one specific concrete machine.
Sure, making the language specific to one machine makes it
non-portable, but that's not what I mean with "close to the machine".
What I mean is what earlier versions of gcc gave me: A language where
the mapping to the usual (VAX-like:-) machines is relatively
straightforward and where the compiler performs that mapping.
If the hardware is unusual, the compiler also has to do some unusual
mapping, and some of the idioms for the usual machines won't work, but
that's no reason to break these idioms on usual machines.
>What I don't like is that the C standard leaves many things
>machine-dependent, so you can't guarantee equivalent behaviour across
>multiple platforms, even for programs that are legal by the standard.
>It is not only the size of number types that are machine dependent: How
>integer division of negative numbers round the result is another
>example.
C99 standardized on symmetric division, so I think your complaint is
addressed.
What does this example mean in terms of "close to the hardware"? This
standardizes the behaviour of AFAIK all hardware that supports signed
integer division (whereas many argue that floored division is what is
needed in more applications).
As for the general issue of leaving things undefined or
implementation-defined: Yes, that is the foundation on which the
"far-from-the-machine" viewpoint is based.
People write C programs that work nicely on most machines (e.g., those
with a flat address space, or with 2s-complement arithmetics).
However there are some other machines, or at least there used to be,
so the C standard does not standardize the behaviour that these people
depend on (after all, the C standard is about describing what is
portable to all machines), so we get a weak standard. A decade later
or so we get a generation of language lawyers in comp.lang.c and among
the GCC mainainers (and probably elsewhere) who actually say that the
programs mentioned above are not C programs and have no meaning, and
that a compiler is allowed to (and some even suggest that it should)
break these programs even on the machines for which they were
designed.
IMO a weak standard is not necessarily bad in itself; it could be a
starting point for a stronger standard. But treating a weak standard
as a complete language definition is wrong.
>As for how close C is to "the machine" in a wider sense, I would say
>that it is fairly close to most 1980s computers, but not so much to
>recent hardware.
In what way? The instruction sets have not changed much since the
1980s (e.g., the IA-32 architecture is from 1985, and AMD64 is pretty
close to it; MIPS and ARM are also from the mid-80s), and ISA is the
level that I would expect a close-to-hardware language to map to.
The major ISA additions were SIMD extensions, and that's probably best
addressed with some array or vector extensions. There is something
along these lines in the GNU C extensions
<http://gcc.gnu.org/onlinedocs/gcc/Vector-Extensions.html>, but I
think something a little more high-level would be better.
>The same closeness to the 1980s model of machine
>execution that allowed C programmers to write programs that ran
>efficiently on past hardware now hinder efficient exploitation of modern
>hardware.
Then one would expect other languages to produce faster code for all
kinds of problems. In my experience that's not the case in general.
E.g., one of my students implements Postscript (the language) in C#.
I found that very instructive: Even though Postscript is a high-level
language, and one might expect that implementing it in another
high-level language should be pretty straightforward, there are a
number of things that are used frequently when interpreting Postscript
that are inherently inefficient in C#, and that I would do differently
and more efficiently in a language that's close to the hardware.
nm...@cam.ac.uk
Bernd Paysan <bernd....@gmx.de> wrote:
>
>> That is nonsense. It is FAR more often a question of whether you
>> want a broken program to give the same erroneous answers on all
>> systems (as Java specifies). 99 times out of a 100, overflow is
>> an ERROR, and all that Java and you do is to turn an arithmetic
>> error into a logical one.
>
>
>It is quite surprising how often you just want bit vectors (i.e. a mod 2^n
>group), not integers. Especially, when you are close to the hardware. For
>numerical applications, your 99% figure is probably right. But most C
>programs aren't numerical applications.
Yes, I am sure, and I wasn't just talking about numerical programming.
Overall, I doubt that bit vectors are more heavily used than floating
point, but let's ignore both as specialist (in different ways). For
numerical applications, make it 99.9% or even 99.9%.
Almost all integers in normal applications are used for things like
counts, sizes, offsets/indices, times/dates, money etc., or are used
as tokens. In all of the former cases, overflow is always an error
and wrapping is precisely what you don't want. In the latter case,
it indicates the program has got completely knotted.
Even when the integer represents a bit vector, mask or whatever,
overflow means a shift has lost information. Is it stuff that the
program will mask off or not use, anyway, or does it indicate that
the result will be wrong? It can be either, and cautious people
mask first and then shift - and positively WANT the error trapped
(which it never is, because the wrapping camp has won).
Regards,
Nick Maclaren.
Stephen Fuld
> Stephen Fuld wrote:
>
>>
>> BTW, in the late 1970's, I was developing code for a bit slice
>> microprocessor used in our proprietary disk controller. The code was
>> assembler level, of course, and the assembler itself was written in
>> Fortran. It worked pretty well.
>>
>>
>
> From what i've heard, there were some early compilers written in Cobol,
> so Fortran may not be such a bad choice.
At one point, more as an exercise to show that I could do it than
anything else, I developed a simulator of a simple computer system.
That simulator was written entirely in COBOL.
> If a langauge is the only one
> available, or the one you are most familiar with, then it probably makes
> sense to use it.
I suspect the motivation for AMDASM (the assembler I was talking about)
being written in Fortran, was portability, as the vendor really didn't
know what system its customers would use. We ran ours on an LSI-11.
Stephen Fuld
> Torben Ægidius Mogensen wrote:
>> As for how close C is to "the machine" in a wider sense, I would say
>> that it is fairly close to most 1980s computers, but not so much to
>> recent hardware. The same closeness to the 1980s model of machine
>> execution that allowed C programmers to write programs that ran
>> efficiently on past hardware now hinder efficient exploitation of modern
>> hardware.
>
> I don't get this.
While I can't comment on the specific example, I agree with Torben. Let
me give another example. On machines of the 1980s, memory references
were cheaper than multiplies. C defines multi-dimensional arrays such
that addressing requires memory references to resolve (i.e. an array of
pointers to the sets of values in the next dimension). This eliminates
the multiply and was more deficient on those machines. Now, since
multiplies are much less costly than an arbitrary memory reference, that
mechanism is a performance loser.
Another example is the allowing of aliases, which allowed programmers of
the 80s to do some "nice" optimizations, but now cause performance
problems by preventing various optimizations on current CPUs.
> Anton's example was that GCC rendered code that was well-
> defined on two's complement into garbage, because it's not well-defined by
> the C standard, which also allows one's complement machines. When did you
> see your last one's complement machine?
The Unisys systems that are descendants of the 1100 series are still
being made, sold and used, and they have a C compiler. I admit that
this is a small number of machines.
ChrisQ
Dodn't really mean to be critical. More habit and tust the first thing I
look at in the sort of work I do. The average coding standard in some
sectors of industry is abysmal.
Any, had a play with this for an hour or so and it's the compare that
seems to be broken. This seems to work for both cases:
#include <stdio.h>
#include <stdlib.h>
int check (int x) {
int y = x + 1;
int z = x - 1;
printf ("%d\t %d\t %d\n", x, y, z); /* Debug */
printf ("%x\t %x\t %x\n", x, y, z);
if ((y + z) == 0) {
return 1;
}
else {
return 0;
}
}
int main(int argc, char *argv[])
{
if (check(atoi(argv[1])))
printf("smallest int\n");
else
printf("check failed\n");
return 0;
}
Results are:
darkstar:
darkstar: gcc -Wall main.c
darkstar: a.out -2147483647
-2147483647 -2147483646 -2147483648
80000001 80000002 80000000
check failed
darkstar: a.out -2147483648
-2147483648 -2147483647 2147483647
80000000 80000001 7fffffff
smallest int
darkstar: a.out -2147483649
2147483647 -2147483648 2147483646
7fffffff 80000000 7ffffffe
check failed
darkstar:
darkstar: gcc -Wall -o2 main.c
darkstar: a.out -2147483647
-2147483647 -2147483646 -2147483648
80000001 80000002 80000000
check failed
darkstar: a.out -2147483648
-2147483648 -2147483647 2147483647
80000000 80000001 7fffffff
smallest int
darkstar: a.out -2147483649
2147483647 -2147483648 2147483646
7fffffff 80000000 7ffffffe
check failed
darkstar:
I suspect the use of the intermediate variable, then compare against 0
may be more of a definate hint to the optimiser, but I would class that
as a compiler bug. Maybe it's been reported already.
Can you see anything wrong with the above ?...
Regards,
Chris
nm...@cam.ac.uk
Stephen Fuld <SF...@Alumni.cmu.edu.invalid> wrote:
>
>While I can't comment on the specific example, I agree with Torben. Let
>me give another example. On machines of the 1980s, memory references
>were cheaper than multiplies. C defines multi-dimensional arrays such
>that addressing requires memory references to resolve (i.e. an array of
>pointers to the sets of values in the next dimension). This eliminates
>the multiply and was more deficient on those machines. Now, since
>multiplies are much less costly than an arbitrary memory reference, that
>mechanism is a performance loser.
Not quite. On PCs of the 1980s. They trailed mainframes and even
the more powerful minicomputers by a decade. We went though that
one in the 1970s on mainframes, but the only thing that one learns
from history is that nobody learns from history.
Also, that isn't true for C multi-dimensional arrays, though it is
for many languages derived from C. C multi-dimensional arrrays are
pretty second-class objects, but that isn't one of their defects.
Indeed, C99 has raised itself to the level of Fortran II in its
support for them (or, more kindly, Fortran 77).
Regards,
Nick Maclaren.
Anton Ertl
>This seems to work for both cases:
>
>
>#include <stdio.h>
>#include <stdlib.h>
>
>int check (int x) {
>
>int y = x + 1;
>int z = x - 1;
>
>printf ("%d\t %d\t %d\n", x, y, z); /* Debug */
>printf ("%x\t %x\t %x\n", x, y, z);
>
>if ((y + z) == 0) {
> return 1;
> }
>else {
> return 0;
> }
>}
>Can you see anything wrong with the above ?...
It also returns 1 for check(0).
Shorter ways to get the same result would be:
return x+x == 0;
return 2*x == 0;
return x<<1 == 0;
Anton Ertl
>On machines of the 1980s, memory references
>were cheaper than multiplies. C defines multi-dimensional arrays such
>that addressing requires memory references to resolve (i.e. an array of
>pointers to the sets of values in the next dimension). This eliminates
>the multiply and was more deficient on those machines. Now, since
>multiplies are much less costly than an arbitrary memory reference, that
>mechanism is a performance loser.
Even if it was true that C requires multi-dimensional arrays to be
implemented in this way (it isn't true, and I have not heard about an
implementation that works that way), it would still possible to
implement the other way: If you want a specific implementation in this
area, you can code it explicitly (and maybe write a few macros to hide
the ugly details).
I also would not bet on the multiplying implementation being faster on
average these days; I would expect pretty good cache hit rates for the
dope vector in most programs, and D-cache hits are usually still
faster than multiplies. The main disadvantage of the dope vector
approach is that it takes additional space (and that disadvantage
probably counted more in the old times).
>Another example is the allowing of aliases, which allowed programmers of
>the 80s to do some "nice" optimizations, but now cause performance
>problems by preventing various optimizations on current CPUs.
CPUs have no problem with potential aliasing. Compilers may have a
problem optimizing code with potential aliasing, but in a language
that is close to the hardware I don't expect such optimizations; if I
want them, I write them in the source code; or maybe I use a
programming language feature (like C's restrict) to tell the compiler
about non-aliases.
ChrisQ
>> Can you see anything wrong with the above ?...
>
> It also returns 1 for check(0).
Agreed :-).
>
> Shorter ways to get the same result would be:
>
> return x+x == 0;
> return 2*x == 0;
> return x<<1 == 0;
>
> - anton
It's not optimised, more to find an algorithm that works reliably. In
finding a minimum value for a signed type, what's interesting is the
point where the sign bit is flipped.
I looked at the asm output and didn't like the look of that either.
Using static variables external to the function reduces the number of
lines of asm, but still a lot of code to do not very much...
Regards,
Chris
ChrisQ
>
> At one point, more as an exercise to show that I could do it than
> anything else, I developed a simulator of a simple computer system. That
> simulator was written entirely in COBOL.
>
That sounds like hard work, but a challenge, without doubt :-).
>
>> If a langauge is the only one available, or the one you are most
>> familiar with, then it probably makes sense to use it.
>
> I suspect the motivation for AMDASM (the assembler I was talking about)
> being written in Fortran, was portability, as the vendor really didn't
> know what system its customers would use. We ran ours on an LSI-11.
>
>
From what I remember, some of the early development systems were
targeted at mainframes as well as mini's and Fortran was arguably the
most common language in that environment. Did you have to build the
tools from source tape, or were binaries supplied ?.
LSI11 brings back fond memories and spent many years programming macro11
on embedded qbus systems. 11/23, /73 and Falcon board mainly. Still one
of the most elegant and orthoganal architectures i've ever worked on...
Regards,
Chris
Stephen Fuld
> Stephen Fuld wrote:
snip
>> I suspect the motivation for AMDASM (the assembler I was talking
>> about) being written in Fortran, was portability, as the vendor really
>> didn't know what system its customers would use. We ran ours on an
>> LSI-11.
>>
>>
>
> From what I remember, some of the early development systems were
> targeted at mainframes as well as mini's and Fortran was arguably the
> most common language in that environment. Did you have to build the
> tools from source tape, or were binaries supplied ?.
When I got there, the executable for AMDASM was already on the LSI-11's
disk. I got involved in modifying the source because as our code
expanded, we exceeded the capacity of the in core symbol table, and
running with the symbol table on disk, which was a configuration option,
was far too slow. I wrote Fortran code to essentially page the symbol
table in large chunks to overcome those problems. The Fortran compiler,
etc, as well as the AMDASM source were all on the disk. Remember, we
were in the disk business, so we had plenty of disk space. At one
point, we had a 300 MB washing machine sized disk on our single board
LSI-11!
> LSI11 brings back fond memories and spent many years programming macro11
> on embedded qbus systems. 11/23, /73 and Falcon board mainly. Still one
> of the most elegant and orthoganal architectures i've ever worked on...
I never did anything but Fortran. But I remember a problem where our
home grown inventory/MRP system, which was written in Pascal, overflowed
the 16 bit registers and the manufacturing manager wondered where 64K of
some part had disappeared to. :-)
Gavin Scott
> Not familiar at all with amd64 asm, but why has it put a nop after the
> compare ?. Does the following branch need to be aligned on a quad word
> boundary or something ?...
Perhaps you just compiled without optimization?
G.
Chris Dodd
news:2009Nov1...@mips.complang.tuwien.ac.at:
> Here's some experiments involving this example:
>
> [c7:~/tmp:25848] cat xxx.c
> #include <stdio.h>
> #include <stdlib.h>
> int check(int x)
> {
> return x<x-1;
> }
>
> int main(int argc, char *argv[])
> {
> if (check(atoi(argv[1])))
> printf("smallest int\n");
> else
> printf("check failed\n");
> return 0;
> }
> [c7:~/tmp:25849] gcc-4.0 -Wall xxx.c
> [c7:~/tmp:25850] a.out -2147483648
> smallest int
> [c7:~/tmp:25851] gcc-4.0 -Wall -O2 xxx.c
> [c7:~/tmp:25852] a.out -2147483648
> check failed
If you use the obvious fix of putting in casts to ensure that the subtract is
done with an unsigned type (and so should wrap properly rather than having
undefined wrapping behavior), it works just fine:
int check(int x)
{
return x < (int)(x - 1U);
}
:
$ gcc -Wall -O3 xxx.x
$ ./a.out -2147483648
smallest int
Looking at the output with -S it seems pretty close to ideal:
call strtol
leal -1(%rax), %edx
cmpl %eax, %edx
jg .L8
-chris
Andrew Reilly
> Shorter ways to get the same result would be:
>
> return x+x == 0;
> return 2*x == 0;
> return x<<1 == 0;
Those three would seem to have a false positive for x==0. Maybe initial
conditions in the particular case argue against it.
Cheers,
--
Andrew
Torben Ægidius Mogensen
> tor...@pc-003.diku.dk (Torben =?iso-8859-1?Q?=C6gidius?= Mogensen) writes:
>>As for how close C is to "the machine" in a wider sense, I would say
>>that it is fairly close to most 1980s computers, but not so much to
>>recent hardware.
>
> In what way? The instruction sets have not changed much since the
> 1980s (e.g., the IA-32 architecture is from 1985, and AMD64 is pretty
> close to it; MIPS and ARM are also from the mid-80s), and ISA is the
> level that I would expect a close-to-hardware language to map to.
>
> The major ISA additions were SIMD extensions, and that's probably best
> addressed with some array or vector extensions. There is something
> along these lines in the GNU C extensions
> <http://gcc.gnu.org/onlinedocs/gcc/Vector-Extensions.html>, but I
> think something a little more high-level would be better.
SIMD is just one thing. Modern computers also have multiple cores, in
increasing numbers.
>>The same closeness to the 1980s model of machine
>>execution that allowed C programmers to write programs that ran
>>efficiently on past hardware now hinder efficient exploitation of modern
>>hardware.
>
> Then one would expect other languages to produce faster code for all
> kinds of problems. In my experience that's not the case in general.
Expecting one language to outperform another on all kinds of problems
is, I think, unrealistic.
Also, if you know exactly what hardware you are working on, a low-level
language like C can allow you to write directly to that hardware and get
highly efficient code. The code will not be portable at all, but quite
efficient. What I meant (but didn't say very clearly) was that the C
programming model hinders efficient exploitation of modern hardware in a
portable way. Basically, a C program overspecifies data structure
layout, order of evaluation, deallocation, and so on in a way that
hinders automatic optimisation to parallel architectures.
Torben
Terje Mathisen
> Stephen Fuld<SF...@alumni.cmu.edu.invalid> writes:
>> On machines of the 1980s, memory references
>> were cheaper than multiplies. C defines multi-dimensional arrays such
>> that addressing requires memory references to resolve (i.e. an array of
>> pointers to the sets of values in the next dimension). This eliminates
>> the multiply and was more deficient on those machines. Now, since
>> multiplies are much less costly than an arbitrary memory reference, that
>> mechanism is a performance loser.
>
> Even if it was true that C requires multi-dimensional arrays to be
> implemented in this way (it isn't true, and I have not heard about an
> implementation that works that way), it would still possible to
> implement the other way: If you want a specific implementation in this
> area, you can code it explicitly (and maybe write a few macros to hide
> the ugly details).
>
> I also would not bet on the multiplying implementation being faster on
> average these days; I would expect pretty good cache hit rates for the
> dope vector in most programs, and D-cache hits are usually still
> faster than multiplies. The main disadvantage of the dope vector
> approach is that it takes additional space (and that disadvantage
> probably counted more in the old times).
"It depends!"
If the major stride is a power or two, or has a limited number of
significant bits, then a shift&add combo instead of MUL can be faster
than a dope vector which is totally L1-cache resident.
If the size of the dope vector is significant, then it will either be
flushed out of L1, or force something else to be thrown out.
If the dimension is larger than 2, then you can calculate the full
address in parallel for each of the higher-order dimensions whereas
multiple levels of dope vectors introduce a lot of extra minimum latency.
If the element size isn't a power of two, then you need some form of
multiplication anyway, which tends to make explicit calculation better.
I.e. I've _mostly_ stopped believing in dope vectors. :-)
Terje
--
- <Terje.Mathisen at tmsw.no>
"almost all programming can be viewed as an exercise in caching"
Anton Ertl
That's code compiled with -O3. Why would a compiler without
optimization insert a nop?
Anton Ertl
>If you use the obvious fix of putting in casts to ensure that the subtract is
>done with an unsigned type (and so should wrap properly rather than having
>undefined wrapping behavior), it works just fine:
>
>int check(int x)
>{
> return x < (int)(x - 1U);
>}
I tried something like this (but without the elegant usage of "1U"),
and it did not work at the time. So I tried your code with a number
of gcc versions:
[c7:~/tmp:25942] for i in gcc-3.3 gcc-3.4 gcc-4.0 gcc-4.1 gcc-4.2 gcc-4.3 gcc-4.4.0; do echo $i && $i -Wall -O3 xxx.c && ./a.out -2147483648; done
gcc-3.3
check failed
gcc-3.4
check failed
gcc-4.0
check failed
gcc-4.1
smallest int
gcc-4.2
smallest int
gcc-4.3
smallest int
gcc-4.4.0
smallest int
And the assembly language for the check function generated by gcc-4.0
is:
xorl %eax, %eax
ret
Anton Ertl
>On Wed, 18 Nov 2009 20:22:31 +0000, Anton Ertl wrote:
>
>> Shorter ways to get the same result would be:
>>
>> return x+x == 0;
>> return 2*x == 0;
>> return x<<1 == 0;
>
>Those three would seem to have a false positive for x==0.
Yes, the same as the code by ChrisQ.
>Maybe initial
>conditions in the particular case argue against it.
No, this code is not usable for my application.
Anton Ertl
>an...@mips.complang.tuwien.ac.at (Anton Ertl) writes:
>
>> tor...@pc-003.diku.dk (Torben =?iso-8859-1?Q?=C6gidius?= Mogensen) writes:
>
>>>As for how close C is to "the machine" in a wider sense, I would say
>>>that it is fairly close to most 1980s computers, but not so much to
>>>recent hardware.
>>
>> In what way? The instruction sets have not changed much since the
>> 1980s (e.g., the IA-32 architecture is from 1985, and AMD64 is pretty
>> close to it; MIPS and ARM are also from the mid-80s), and ISA is the
>> level that I would expect a close-to-hardware language to map to.
>>
>> The major ISA additions were SIMD extensions, and that's probably best
>> addressed with some array or vector extensions. There is something
>> along these lines in the GNU C extensions
>> <http://gcc.gnu.org/onlinedocs/gcc/Vector-Extensions.html>, but I
>> think something a little more high-level would be better.
>
>SIMD is just one thing. Modern computers also have multiple cores, in
>increasing numbers.
C with thread libraries appears to be a good way to program
multi-cores close to the hardware.
>>>The same closeness to the 1980s model of machine
>>>execution that allowed C programmers to write programs that ran
>>>efficiently on past hardware now hinder efficient exploitation of modern
>>>hardware.
>>
>> Then one would expect other languages to produce faster code for all
>> kinds of problems. In my experience that's not the case in general.
>
>Expecting one language to outperform another on all kinds of problems
>is, I think, unrealistic.
I did not say that one language would achieve this feat. But if C was
really as inefficient on modern hardware as you claim, I would also
expect one language to produce faster code for most kinds of problems.
>Also, if you know exactly what hardware you are working on, a low-level
>language like C can allow you to write directly to that hardware and get
>highly efficient code. The code will not be portable at all, but quite
>efficient. What I meant (but didn't say very clearly) was that the C
>programming model hinders efficient exploitation of modern hardware in a
>portable way.
In my experience C (at least the full language, not necessarily the
standardized subset) allows to write code that is pretty efficient and
pretty portable. Sure, this kind of code can be beaten by people like
Terje writing assembly code for select places, and it may not be
portable to the Univac 1100 series, but it certainly ports to all
platforms that it was intended for (unlike the assembly code).
>Basically, a C program overspecifies data structure
>layout, order of evaluation, deallocation, and so on in a way that
>hinders automatic optimisation to parallel architectures.
Yes, and there are a number of other ways in which full C hinders
automatic optimisations. But the more abstract languages hinder
manual optimizations, and in my experience the manual optimizations
are way more effective. Moreover, the more abstract languages also
abstract the programmers from getting an idea of the costs of various
things, resulting in even less efficient code than would otherwise be
possible in these languages.
Mayan Moudgill
>
> C with thread libraries appears to be a good way to program
> multi-cores close to the hardware.
C with some (non-pthread) version of thread libraries is probably a way
to program multi-cores close to the hardware, and, with sufficient
effort, get close-to-optimal results on that particular hardware.
Extrapolating from my experience, however, I think that the *sufficient
effort* is going to be a lot more than one would be happy with.
Consider the case of what we have to do to optimize for serial
execution. Generally it will involve things like:
1. rewriting functions
2. changing data structures
3. changing algorithms
Most, if not all, of these changes are local - they impact a small
fraction of the code, and/or can be analyzed in isolation.
In my experience, multi-threaded optimization tends to knowing (and
tackling) the big-picture. There are more moving parts that need to be
fitted together. Perhaps HPC people with experience with
non-embarassingly/trivially-parallelizable codes can corroborate?
I'm not sure that this is an issue that can be fixed at the language
level, or if it arises from the fact that the problem is harder, or if
it is an issue of lack-of-experience coupled with tool immaturity.
Ultimately multi-core programming is about:
1. one thread writing to a memory location that is read by other(s)
2. coordinating this communication
There are multiple hardware mechanisms to achieve this. These mechanisms
may vary between threads on the same core vs. threads on different
cores. These mechanisms may differ from implementation to implementation
of the same architecture.
There are many more decisions: Do you want to optimize for the case
where the number of threads is less than the number of cores, or not?
Spinning vs. non-spinning? Which operating system will you be using?
What facilities does it offer? Or will you be using your own thread
management? Async I/O vs blocking I/O? Kernel mode vs user mode?
For instance, the task division is different between N and N+1 cores.
Redoing the task division so that work the per core is balanced is
non-trivial. One solution is to divide up the work for some number M >>
N parallel tasks, and then rely on time-sharing or work-queues to get
balanced work loads. But that adds inefficiencies, particularily in the
matter of additional synchronization.
The other scary bit for most people is the debugging. Some of the push
to shared nothing models is to decrease the number of ways a bug in one
process can impact other processes, and thereby make it easier to
isolate and correct bugs; sort of like garbage collected languages as a
reaction to the non-local bugs caused by various pointer bugs.
Robert Myers
You could have written a similarly dour assessment at almost any point
in the history of technology.
New technologies are finicky, poorly-understood, labor-intensive, and
unreliable.
As technologists gain confidence, experience, and insight, they learn
how to automate or mechanize difficult, exacting, and labor intensive
tasks. They invent new abstractions that made what once seemed nearly
impossible almost easy. The miraculous becomes routine. I don't see
anything fundamental about parallel computation to say that it will go
differently. It's hard to imagine that it would be worse than what we
have already.
Roberty.
nm...@cam.ac.uk
Mayan Moudgill <ma...@bestweb.net> wrote:
>Anton Ertl wrote:
>>
>> C with thread libraries appears to be a good way to program
>> multi-cores close to the hardware.
>
>C with some (non-pthread) version of thread libraries is probably a way
>to program multi-cores close to the hardware, and, with sufficient
>effort, get close-to-optimal results on that particular hardware.
>
>Extrapolating from my experience, however, I think that the *sufficient
>effort* is going to be a lot more than one would be happy with.
I think that we are agreed there!
Regards,
Nick Maclaren.
Niels Jørgen Kruse
> Even if it was true that C requires multi-dimensional arrays to be
> implemented in this way (it isn't true, and I have not heard about an
> implementation that works that way), it would still possible to
> implement the other way: If you want a specific implementation in this
> area, you can code it explicitly (and maybe write a few macros to hide
> the ugly details).
A C compiler is not allowed to use a dope vector implementation.
You can set it up yourself easily and the syntax of array access is
identical. Pehaps that is what confused Stephen Fuld.
--
Mvh./Regards, Niels J�rgen Kruse, Vanl�se, Denmark
Mayan Moudgill
>
> You could have written a similarly dour assessment at almost any point
> in the history of technology.
>
> New technologies are finicky, poorly-understood, labor-intensive, and
> unreliable.
But tend to mature at a particular pace. We've had 40+ years to
determine the slope for parallelization & parallel computers (and their
cousin, distributed computation). Its not all that encouraging.
> As technologists gain confidence, experience, and insight, they learn
> how to automate or mechanize difficult, exacting, and labor intensive
> tasks.
Sometimes the insight they gain is - no way!
People have been trying to solve the parallel problem for the same amout
of time roughly as compilation, distributed programming & vectorization.
What factors are responsible for the differences in maturity amongst all
of these fields? How come one is relatively automated (compilation), one
is so-so (vectorization; you still have to code appropriately), and the
other two are stuck at labor-intensive.
About the only field that I can think of in modern times with a similar
lack of success would be fusion.
> They invent new abstractions that made what once seemed nearly
> impossible almost easy.
Yes, but you pay in terms of inefficiency for each of these
abstractions. Remember the context - trying to get near-optimal
performance (by using C for close-to-bare-metal programming).
> The miraculous becomes routine. I don't see
> anything fundamental about parallel computation to say that it will go
> differently.
Most people can't visualize multiple complex tasks running in parallel,
specially where there is irregular communication between the tasks. IMO,
any general solution will have to start off with auto-parallelization.
And that technology is currently unimpressive.
Robert Myers
> Robert Myers wrote:
>
> > You could have written a similarly dour assessment at almost any point
> > in the history of technology.
>
> > New technologies are finicky, poorly-understood, labor-intensive, and
> > unreliable.
>
> But tend to mature at a particular pace. We've had 40+ years to
> determine the slope for parallelization & parallel computers (and their
> cousin, distributed computation). Its not all that encouraging.
>
The knee in the curve has always come when the technology has become
sufficiently inexpensive and pervasive so as to be susceptible to
broad-based tinkering and needed disruptive challenges to and
adaptations of the technology from non-incumbents. We are, for
example, just at that point with virtualization. The discouraging
time scale you have identified is only a measure of the broadness of
the knee of the curve of introduction of parallel methods into wide
use. Rather than arriving as an irresistible force with energetic,
greedy, and well-funded advocates, as in the case of the
microprocessor, parallel methods have seeped very slowly into the
mainstream, leading to fragmented efforts with lots of discouraging,
half-baked results.
> > As technologists gain confidence, experience, and insight, they learn
> > how to automate or mechanize difficult, exacting, and labor intensive
> > tasks.
>
> Sometimes the insight they gain is - no way!
>
Never say never. ;-)
> People have been trying to solve the parallel problem for the same amout
> of time roughly as compilation, distributed programming & vectorization.
> What factors are responsible for the differences in maturity amongst all
> of these fields? How come one is relatively automated (compilation), one
> is so-so (vectorization; you still have to code appropriately), and the
> other two are stuck at labor-intensive.
>
> About the only field that I can think of in modern times with a similar
> lack of success would be fusion.
>
Fusion suffers from a different problem, IMNSHO.
> > They invent new abstractions that made what once seemed nearly
> > impossible almost easy.
>
> Yes, but you pay in terms of inefficiency for each of these
> abstractions. Remember the context - trying to get near-optimal
> performance (by using C for close-to-bare-metal programming).
>
The habitual pursuit of near-optimal performance has been one of the
bugbears of software development. I associate the phrase premature
optimization with Andy Glew, but he'll probably only tell me where it
really comes from. Always be prepared to give up without hesitation a
factor of two in performance as a small price for clarity and
maintainability.
Robert.
Anton Ertl
>Always be prepared to give up without hesitation a
>factor of two in performance as a small price for clarity and
>maintainability.
Of course, on typical current PCs this can typically be achieved by
staying sequential.
Anton Ertl
>Anton Ertl wrote:
>>
>> C with thread libraries appears to be a good way to program
>> multi-cores close to the hardware.
>
>C with some (non-pthread) version of thread libraries is probably a way
>to program multi-cores close to the hardware, and, with sufficient
>effort, get close-to-optimal results on that particular hardware.
>
>Extrapolating from my experience, however, I think that the *sufficient
>effort* is going to be a lot more than one would be happy with.
Yes. And the performance is probably not very scalable across a wide
range of parallel hardware.
But do we get good parallel performance from higher-level languages?
My impression is that we don't, apart from a few niches (scientific
applications and mapreduce, not much else comes to my mind).
My guess is that once we find good ways to parallelise, we will be
able to add them to low-level languages just as we can add them to
high-level languages. My guess is also that this way does not involve
fancy static program analysis. Instead, there will be dynamic
resource allocation.
I think that pipes/streams/channels are a part of the puzzle, because
they not only allow to parallelise, they also allow to modularise, so
they make the programs more manageable.
>One solution is to divide up the work for some number M >>
>N parallel tasks, and then rely on time-sharing or work-queues to get
>balanced work loads. But that adds inefficiencies, particularily in the
>matter of additional synchronization.
To avoid these overheads and to achieve load balancing, I have been
thinking about an implementation that automatically switches between
communicating between threads and using coroutining for efficient
communication within a thread. Currently these are just ideas, but I
have written them down in
<http://www.complang.tuwien.ac.at/kps09/pdfs/ertl.pdf>
Terje Mathisen
> Robert Myers<rbmye...@gmail.com> writes:
>> Always be prepared to give up without hesitation a
>> factor of two in performance as a small price for clarity and
>> maintainability.
I've preached the same for a number of years, in the form:
"First you determine (if possible) what the 'speed of light' is, i.e.
how fast could you run in a perfect world. If you can then come up with
code that's within a factor of two of this speed, then it is probably fine."
>
> Of course, on typical current PCs this can typically be achieved by
> staying sequential.
See above: For an N-core cpu you need to either use at least half of
them optimally, or all of them at half speed or better. :-)
Mayan Moudgill
> On Nov 22, 7:12 am, Mayan Moudgill <ma...@bestweb.net> wrote:
>
>>Robert Myers wrote:
>>
>>
>>>You could have written a similarly dour assessment at almost any point
>>>in the history of technology.
>>
>>>New technologies are finicky, poorly-understood, labor-intensive, and
>>>unreliable.
>>
>
>>But tend to mature at a particular pace. We've had 40+ years to
>>determine the slope for parallelization & parallel computers (and their
>>cousin, distributed computation). Its not all that encouraging.
>>
>
> The knee in the curve has always come when the technology has become
> sufficiently inexpensive and pervasive so as to be susceptible to
> broad-based tinkering and needed disruptive challenges to and
> adaptations of the technology from non-incumbents. We are, for
> example, just at that point with virtualization.
IIRC, VM/370 was deployed commercially in 1972. There may have been
other virtualization efforts inside IBM prior to that as well.
[Here is the appropriate time for the Wheelers to jump in.]
> The discouraging
> time scale you have identified is only a measure of the broadness of
> the knee of the curve of introduction of parallel methods into wide
> use.
How do you know we're not riding the asymptote? The rate of progress,
IMO, is slowing. Can you point to *one* new parallelization technology
that has been introduced in the last 10 years?
> The habitual pursuit of near-optimal performance has been one of the
> bugbears of software development. I associate the phrase premature
> optimization with Andy Glew
Its either Knuth or Tony Hoare; I've heard the story both ways.
> Always be prepared to give up without hesitation a
> factor of two in performance as a small price for clarity and
> maintainability.
If you're willing to give up 2x, then (for <= 4-8 cores):
- optimize the serial version of the program.
- buy a higher end machine
Mayan Moudgill
> Mayan Moudgill <ma...@bestweb.net> writes:
>
>>Anton Ertl wrote:
>>
>
> I think that pipes/streams/channels are a part of the puzzle, because
> they not only allow to parallelise, they also allow to modularise, so
> they make the programs more manageable.
Not really.
Consider the following: a pipe combines a data-copy from source to
destination, and attaches a synchronziation mechanism to it.
What if there is a ton of data being produced? Do you want to copy it at
the end?
What if there are multiple people who need to co-ordinate, where the
ideal sync model is a barrier?
>
>>One solution is to divide up the work for some number M >>
>>N parallel tasks, and then rely on time-sharing or work-queues to get
>>balanced work loads. But that adds inefficiencies, particularily in the
>>matter of additional synchronization.
>
>
> To avoid these overheads and to achieve load balancing, I have been
> thinking about an implementation that automatically switches between
> communicating between threads and using coroutining for efficient
> communication within a thread. Currently these are just ideas, but I
> have written them down in
> <http://www.complang.tuwien.ac.at/kps09/pdfs/ertl.pdf>
I'll look.
But, IME, there is a huge difference between programming for #tasks >
#processors and #tasks < #processors.
Robert
> I think that pipes/streams/channels are a part of the puzzle, because
> they not only allow to parallelise, they also allow to modularise, so
> they make the programs more manageable.
I propose something like this:
1) Atom chip, low power, etc. ARM, whatever.
2) 4 gigs of ram to max out 32 bit
3) 256 gigs of flash drive
4) 3.5 inch rotating disk
5) ultracapacitor for UPS
6) SATA port. Most motherboards have 6-8 SATA ports. They have decent
bandwidth, are cheap and readily available.
Put some smarts in the OS, caching to ram, backed by flash, backed by
rotating disk. Allow loading arbitrary Java/.Net code to massage the data.
Just DMA raw bytes into the hosts address space. Put the above in a
standard 3.5 inch disk form factor. Maybe 2 of these fit in 3 standard
bays.
Keep the power down to say 20 watts and put as many as your IO busses can
stand into your compute server. Keep it async and you have scalable IO and
distributed low power compute. Do as much compute as possible as close to
the data as you are able. Cache the rest. 2 cores would allow 1 to do IO
stuff, and one to do a bit of compute.
Get the price down to 1000 USD and they would sell fast!
Robert Myers
> Robert Myers wrote:
>
> > The knee in the curve has always come when the technology has become
> > sufficiently inexpensive and pervasive so as to be susceptible to
> > broad-based tinkering and needed disruptive challenges to and
> > adaptations of the technology from non-incumbents. We are, for
> > example, just at that point with virtualization.
>
> IIRC, VM/370 was deployed commercially in 1972. There may have been
> other virtualization efforts inside IBM prior to that as well.
>
> [Here is the appropriate time for the Wheelers to jump in.]
>
The critical moment is not when the technology is demonstrated, but
when the market is ready for it and it becomes widely available at a
mass market price. The enduring example is the facsimile machine.
I'm keen on criticizing some players in the microcomputer revolution,
such as Microsoft, but it isn't obvious to me that, even had IBM been
treated more fairly or been less clumsy, we'd all now be using OS/2.
By fair means or foul, Wintel got the processors into the market in a
volume that made all kinds of previously unthinkable things possible.
We *might* have better software, and even that is no certainty, but
IBM would still be focused more on ways to milk a small market with
high gross margin (as it did with virtualization) than it would be in
creating a market that supports huge volume. IBM never really learned
how to create and serve mass markets and it has never been all that
interested, anyway. It would rather defend mainframes, where
virtualization still plays a key role.
Now that I can get a bare-metal hypervisor for free and a VT-capable
platform for a few hundred dollars, I can do everything IBM would have
been able to do for me, without my having to pay the salaries of its
sales, marketing, and management staffs. Unfortunately for you, and
for basic science, the overhead to support places like Watson
disappears, too. Now that there are so many players in
virtualization, though, things will really take off. If and when
itanium flickers back into life, I will probably have the same kind of
security by obscurity that mainframes offer, as well (no script
kiddies need apply).
> > The discouraging
> > time scale you have identified is only a measure of the broadness of
> > the knee of the curve of introduction of parallel methods into wide
> > use.
>
> How do you know we're not riding the asymptote? The rate of progress,
> IMO, is slowing. Can you point to *one* new parallelization technology
> that has been introduced in the last 10 years?
>
GPGPU's have made huge progress in the last few years, and the
progress continues apace. The key is that serious capability is
within the reach of many and it is actually being used, rather than
being a DARPA project. I can't keep up with Andy (to many acronyms),
but he seems pretty excited.
<snip>
>
> If you're willing to give up 2x, then (for <= 4-8 cores):
> - optimize the serial version of the program.
> - buy a higher end machine
A single socket Nehalem with four cores might not be all that
interesting from a capability point of view. A two-socket board (a
sweet spot, apparently) with eight cores per socket will be 16-core
SMP. How far does this have to go before you will admit that the
rules have changed?
As it is, my desktop does many different things at once that no
desktop could have managed ten years ago. I don't even think of
myself as a real power user. Little plastic boxes from places like
network gear suppliers will soon be hoovered up by a rather modest
dual core box and I will have more capability, security, flexibility,
and manageablility. IBM first explored many of these tricks, but it
won't be the organization to move them into the mass market.
Robert.
Anne & Lynn Wheeler
Mayan Moudgill <ma...@bestweb.net> writes:
> IIRC, VM/370 was deployed commercially in 1972. There may have been
> other virtualization efforts inside IBM prior to that as well.
>
> [Here is the appropriate time for the Wheelers to jump in.]
some number of the ctss people went to multics on 5th flr of 545 tech sq
... some other ctss people went to multics on 4th flr of 545 tech sq.
misc. past posts
http://www.garlic.com/~lynn/subtopic.html#545tech
science center started off trying to get a 360/50 for virtual memory
hardware modifications ... but so many 360/50s were going to the FAA ATC
program ... they had to settle for 360/40 ... and so the first was
called cp/40 (instead of cp/50). When the standard 360 product with
virtual memory came out, 360/67 ... cp/40 morphed into cp/67.
cp/67 found its way into a large number of different places including
gov. agencies ...
http://www.nsa.gov/research/selinux/list-archive/0409/8362.shtml
note with regard to the above ... as part of evolving to support vm370
... the cp/67 group split off and became distinct from the science
center. As it grew, it absorbed the "boston programming center" that
was on the 3rd flr of 545 tech sq and moved into the 3rd flr. the 3rd
flr was shared with another occupant listed on the bldg. roster as some
law firm. however, the 3rd flr telco closet was on the boston
programming center side of the 3rd flr ... and the telco labled the law
firm's telco box as a fed gov. three letter agency.
i was doing a lot of work with cp67 as undergraduate at the univ. and
would sometimes get various requests from the vendor for enhancements.
I didn't know about the customers (mentioned above) ... but in
retrospect, some of the enhancements requests might reasonably be
construed as having originated from them (i've recently joked that there
may be some security issues that current generation of security experts
don't even realize are security issues ... they are so preoccupied with
more fundamental problems).
for random other reference ... from my rfc index
http://www.garlic.com/~lynn/rfcietff.htm
rfc from lincoln labs:
rfc 109
http://www.garlic.com/~lynn/rfcidx0.htm#109
rfc 198
http://www.garlic.com/~lynn/rfcidx0.htm#198
from rfc 198:
We have exercised Lincoln Labs Network software as follows: NCP,
ICP, ASCII Telnet (user and server), login procedure, access to CMS, and
operator and console communication. All behave according to current
specifications.
Multiple message responses, such as listing users, were very
smooth under moderate to heavy load of the /67.
... snip ...
as part of the morph from cp67 to vm370, CMS was renamed from the
"cambridge monitor system" to the "conversational monitor system".
there were a couple cp67-based commercial online time-sharing service
bureaus that spun-off in the 60s ... and two of them appeared to move
fairly quickly upstream into financial services.
in the congressional hearings last fall into credit rating agencies
blamed for major spoke in the current financial mess ... recent ref:
Ohio Sues Credit Rating Agencies
http://www.consumeraffairs.com/news04/2009/11/oh_credit_agencies.html
there was comments that the seeds of the problem was from the early 70s
when the rating agencies switched from the buyers paying for the ratings
to the sellers paying for the ratings (creating the opening for conflict
of interest with the sellers being able to pay for specific rating).
Website for one of those early cp67 online timesharing service bureaus
mentioned the bought the "pricing services" division from one of the
rating agencies in 1972 (speculation that if the rating agencies were
just giving the ratings requested by the sellers ... they may no longer
need to do detailed evaluations). There was some brief item early jan
... that the company was helping "price" the toxic assets (original
appropriation of TARP funds was to be used to buy the toxic assets being
carried off-balance by the "too-big-to-fail" financial institutions).
--
40+yrs virtualization experience (since Jan68), online at home since Mar1970
Anne & Lynn Wheeler
> creating a market that supports huge volume. IBM never really learned
> how to create and serve mass markets and it has never been all that
> interested, anyway. It would rather defend mainframes, where
> virtualization still plays a key role.
re:
http://www.garlic.com/~lynn/2009q.html#47 Is C close to the machine?
I would contend that virtualization saw an "enormous" mass market uptake
... modulo limits of the hardware price/performance in the period.
there were frequent discussions at user group meetings that the uptake
frequently was "in spite" of mainstream corporate activity (lots of
customer installs were viral ... results of existing customers talking
about the wonders & benefits of the technology).
Andy "Krazy" Glew
> How do you know we're not riding the asymptote? The rate of progress,
> IMO, is slowing. Can you point to *one* new parallelization technology
> that has been introduced in the last 10 years?
Although I agree with Mayan's gist, and what I am about to say is not
really a parallelization technology, but a parallelism
microarchitecture, nevertheless:
SIMT (Single Instruction Multiple Threads) / Coherent Threading (CT) is
new, within the last few years, at least to me.
All of the big GPU companies - Nvidia, Intel, ATI - introduced something
like SIMT at about the same time, circa 2004.
I do not know when or where it originated.
The coincidence of its introduction suggests that it may have originated
at a common source, e.g. a failed company, from whence the idea spread.
Masspar has been suggested as a possibility, as has John Nickolls.
But I find no evidence in publication.
I'd love to know, because I like giving people proper credit.
Mayan Moudgill
> To avoid these overheads and to achieve load balancing, I have been
> thinking about an implementation that automatically switches between
> communicating between threads and using coroutining for efficient
> communication within a thread. Currently these are just ideas, but I
> have written them down in
> <http://www.complang.tuwien.ac.at/kps09/pdfs/ertl.pdf>
>
Did a quick read of the paper. My summary [Correct me if I'm wrong]
Basic idea:
1. Write code as a series of tasks connected by pipes, using pretty much
the same idiom as piping together programs in Unix: e.g. to count
non-blank lines by c and h files in a tree:
find . -name '*.[ch]' | grep -v '^$' | wc -l
Lets call these tasks kernels A,B,....
2. The pipeline of kernels is partitioned between cores. In the case of
5 tasks A,B,C,D,E,F running on 3 cores 0,1,2, a possible partition might
be (A,B,C),(D,E),(F)
Dynamic load balancing
3. If a mismatch in workloads is noticed, the pipeline may be
repartitioned, generally by moving one kernel across threads. Thus, if
core 0 has more work than core 1, C may move to core 1, resulting in
partition (A,B),(C,D,E),(F)
4. The repartitioning is mediated by the states of the inter-thread
buffers; if C is writing to D and generally sees an empty queue, then
(A,B,C) is probably running slower than (D,E), and so C can move over.
If C is writing to D and generally sees a full queue, then the that core
is overloaded, and D may move over onto core 0, resulting in (A,B,C,D).
Alternatively, it may make sense for the task at the other end of the
pipe to be moved (i.e. instead of the C/D boundary moving, the E/F
boundary may move).
Kernel scheduling
5. If kenel Ki pipes information to a Ki+1 on the same core, it may
yield (using coroutine semantics) to Ki+1 after writing the information
Critique:
1. Only works for pipelines; it doesn't work with more complicated
graphs such as DAGs.
2. POSIX pipes are byte-streams of potentially unbounded length (i.e.
you can write an arbitrary number of bytes before the first one is read).
a. You probably want a stronger type system on the data
b. Do you want to bound the buffer size?
3. You're going to have to worry about copying the data at least once
and probably twice (data gets created, copied into buffer, data gets
copied from buffer, data gets used). It is possible to come up with
implementations of 2b that, if the data is not copied, can lead to lockup.
4. The overhead of coroutining is not the state save, its the loss of
locality of the caching and prediction structures.
5. What if the kernels have different data sizes (e.g. kernel A produces
data in chunks of 512 and the next one, B, processes it in a chunk of
2K; your workload will be AbAbAbAB where b is kernel B reading the 512B,
and then blocking waiting for the next read).
Its a neat little idea, but it will require more engineering than you
might expect. My main objection is (1) - I don't expect that pipelines
is going to be a very interesting case.
Mayan Moudgill
> On Nov 23, 2:15 am, Mayan Moudgill <ma...@bestweb.net> wrote:
>
>>Robert Myers wrote:
>
>
>>>The knee in the curve has always come when the technology has become
>>>sufficiently inexpensive and pervasive so as to be susceptible to
>>>broad-based tinkering and needed disruptive challenges to and
>>>adaptations of the technology from non-incumbents. We are, for
>>>example, just at that point with virtualization.
>>
>>IIRC, VM/370 was deployed commercially in 1972. There may have been
>>other virtualization efforts inside IBM prior to that as well.
>>
>>[Here is the appropriate time for the Wheelers to jump in.]
>>
Huh? We're talking about the fact that parallelization for multi-core
has shown little advances, even at the level of research compilers. You
proferred virtualization of something that is now becoming pervasive. I
pointed out that virtualization has been available as a
_commercial_product_ since 1972! There is no comparable advance in
auto-parallelization (outside of vectorization - and most of that was
worked out by the end of the 70s).
>>>The discouraging
>>>time scale you have identified is only a measure of the broadness of
>>>the knee of the curve of introduction of parallel methods into wide
>>>use.
>>
>>How do you know we're not riding the asymptote? The rate of progress,
>>IMO, is slowing. Can you point to *one* new parallelization technology
>>that has been introduced in the last 10 years?
>>
>
> GPGPU's have made huge progress in the last few years, and the
> progress continues apace.
GPGPU are NOT a parallelization technology. It is a platform for
executing parallel code. I guess you can't name a parallelization
technology.
> ... A two-socket board (a
> sweet spot, apparently) with eight cores per socket will be 16-core
> SMP. How far does this have to go before you will admit that the
> rules have changed?
>
Once they start hitting 100s of cores. 16-ways have been available and
worked on since, oh, forever. I don't know if C.mmp is the earliest, but
that dates back to 1971. Clusters (which are fairly similar as far as
the programming is concerned) pre-date this.
Anton Ertl
>Anton Ertl wrote:
>
>> To avoid these overheads and to achieve load balancing, I have been
>> thinking about an implementation that automatically switches between
>> communicating between threads and using coroutining for efficient
>> communication within a thread. Currently these are just ideas, but I
>> have written them down in
>> <http://www.complang.tuwien.ac.at/kps09/pdfs/ertl.pdf>
>>
>
>Did a quick read of the paper. My summary [Correct me if I'm wrong]
No correction needed.
>Kernel scheduling
>5. If kenel Ki pipes information to a Ki+1 on the same core, it may
>yield (using coroutine semantics) to Ki+1 after writing the information
The way I envision is that it yields, eliminating the need for
buffering between the tasks (kernels) in this case.
>Critique:
>1. Only works for pipelines; it doesn't work with more complicated
>graphs such as DAGs.
Does this refer to the load balancing? It would certainly get more
complicated with DAGs. However, I don't think that DAGs would be used
much even if they are supported.
>2. POSIX pipes are byte-streams of potentially unbounded length (i.e.
>you can write an arbitrary number of bytes before the first one is read).
Normally a buffer (typical size: 4KB) is associated with a Unix pipe,
and once that buffer is full, the writer blocks.
> a. You probably want a stronger type system on the data
That's up to the language designer. I would expect that if you add
such a feature to a statically type-checked language, you would also
statically type-check the communication over a channel. That's what
programmers in such a language expect, want, and would miss if a
feature was added without such typechecking.
Personally, I feel that the lack of static type-checking and the
uniformity of data in files and pipes in Unix is a strength that
allows the reuse of filters for many tasks.
> b. Do you want to bound the buffer size?
No bound is guaranteed, but there has to be a bound because of (at
least) hardware constraints (e.g., address space), and practical
considerations (such as wanting to process the data warm in some cache
rather than letting is chill out into main memory and later having to
drag it back in).
>3. You're going to have to worry about copying the data at least once
>and probably twice (data gets created, copied into buffer, data gets
>copied from buffer, data gets used).
My idea is that (on a shared-memory machine) the writing task stores
the data directly into the buffer, and later the reading task fetches
the data exactly from the same place. The tasks may copy the data
from/to another buffer, or the data may come directly from a
computation, or may be used directly in a computation; that's up to
the tasks. There will of course be an implicit copy of the cache line
from the writing task's core to the reading task's core, but no
explicit copy is necessary.
>It is possible to come up with
>implementations of 2b that, if the data is not copied, can lead to lockup.
Do you have a particular scenario in mind?
>4. The overhead of coroutining is not the state save, its the loss of
>locality of the caching and prediction structures.
Yes, that's a potential problem. We will have to see if it's a real
problem (and if so, maybe the hardware designers can come up with
prediction structures that also work well under these circumstances).
Why I think that it might be no problem: Today nearly all programs are
sequential. For dealing with the problems that can be divided into
pipelines, they often have quite convoluted control flow. Now if we
divide such a program (part) into pipeline stages, each stage will be
simpler and smaller, and maybe more predictable. If we then combine
some of these stages back together again on one core using
coroutining, they will still not be as bad as a sequential program;
and the hardware was designed to perform well on the sequential
program.
There is one exception: the return stack (predicting function return
addresses) of current machines will not work well when coroutining is
involved. Let's see it as opportunity for computer architects to come
up with a better return predictor.
>5. What if the kernels have different data sizes (e.g. kernel A produces
>data in chunks of 512 and the next one, B, processes it in a chunk of
>2K; your workload will be AbAbAbAB where b is kernel B reading the 512B,
>and then blocking waiting for the next read).
That's for the case when the tasks/kernels are on different cores,
right? My idea is that the load balancing will try to avoid cases
where a buffer is completely empty or completely full. But yes, if it
cannot avoid that, one of the threads involved will block.
>My main objection is (1) - I don't expect that pipelines
>is going to be a very interesting case.
I think there are several reasons why pipes are interesting:
* They help modularity (most other parallel and concurrent programming
practices are at odds with modularity).
* They encourage reusable components (filters).
* They are so useful that programmers have used pipelines even when
they did not intend to exploit parallelism (in Unix shell scripts).
* Not much synchronization is necessary; when the buffer is neither
empty nor full, you get very cheap communication. And you can make
the buffer larger to reduce the expensive cases.
Mayan Moudgill
>>you can write an arbitrary number of bytes before the first one is read).
>
>
> Normally a buffer (typical size: 4KB) is associated with a Unix pipe,
> and once that buffer is full, the writer blocks.
IIRC, the behavior specification is kind of unclear. There are two
limits involved (SSIZE_MAX & PIPE_BUF). Based on a reading of the
specification, its possible that any writes of size < SSIZE_MAX must
eventually complete, which would imply that the buffer must be about 32K.
Mayan Moudgill
> Mayan Moudgill <ma...@bestweb.net> writes:
>
>>Anton Ertl wrote:
>>
>>
>>>To avoid these overheads and to achieve load balancing, I have been
>>>thinking about an implementation that automatically switches between
>>>communicating between threads and using coroutining for efficient
>>>communication within a thread. Currently these are just ideas, but I
>>>have written them down in
>>><http://www.complang.tuwien.ac.at/kps09/pdfs/ertl.pdf>
>>>
>
>>3. You're going to have to worry about copying the data at least once
>>and probably twice (data gets created, copied into buffer, data gets
>>copied from buffer, data gets used).
>
>
> My idea is that (on a shared-memory machine) the writing task stores
> the data directly into the buffer, and later the reading task fetches
> the data exactly from the same place. The tasks may copy the data
> from/to another buffer, or the data may come directly from a
> computation, or may be used directly in a computation; that's up to
> the tasks. There will of course be an implicit copy of the cache line
> from the writing task's core to the reading task's core, but no
> explicit copy is necessary.
>
How does the writer know that he can write to the buffer? Does he
explicitly allocate a buffer of the appropriate size? Or does he need to
wait for the reader to signal that he is done?
What if the writer writes 16KB, but the reader can't start processing
until he has 64KB? Do you preallocate 64KB of data for that channel? Or
do you allocate more? What happens if the two ends are on different
cores? What happens when the reader is rewritten to use different block
sizes?
Almost certainly you're going to end up allocating buffers on demand for
the writer. Now you've got the job of freeing them up. Who does the
garbage collection?
If the writer writes to 4 separately allocated chunks of 16KB, they will
not be contiguous in memory. The reader can then not treat them as a
continuous memory segment (unless you're going to play VM games - gag!);
so the reader will have to be aware of the shape they are written.
In the end, you're going to end up concluding that the "elegant"
solution is to copy the data at both ends, similarily to how write() and
read() work.
Robert Myers
> Robert Myers wrote:
> GPGPU are NOT a parallelization technology. It is a platform for
> executing parallel code. I guess you can't name a parallelization
> technology.
>
I seem to have run into the language game, which I'm usually on the
lookout for.
By parallelization technology, I take it you mean: view the world as
Donald Knuth stubbornly viewed it and as you apparently learned to
think inevitable, write code that way, and depend on some automagical
process so that that code will take advantage of mutliple cores,
threads, streams, etc.
Won't happen. We're agreed.
I'm not going to get into an argument over language, now that I see
that that's what's at stake.
My proposition is that radically different and pervasively available
hardware will change the way people think and write code. Call it by
whatever name you like. It will change the rules. You apparently
don't like it to the extent that you're in a state of denial.
> > ... A two-socket board (a
> > sweet spot, apparently) with eight cores per socket will be 16-core
> > SMP. How far does this have to go before you will admit that the
> > rules have changed?
>
> Once they start hitting 100s of cores. 16-ways have been available and
> worked on since, oh, forever. I don't know if C.mmp is the earliest, but
> that dates back to 1971. Clusters (which are fairly similar as far as
> the programming is concerned) pre-date this.
Typical IBM-centric response. The fax machine was available as
commercial technology long before it was widely-adopted, too.
Robert Myers.
Stefan Monnier
> sufficiently inexpensive and pervasive so as to be susceptible to
> broad-based tinkering and needed disruptive challenges to and
> adaptations of the technology from non-incumbents. We are, for
In the case of parallelisation, I think the issue is not so much "how"
but "what". I.e. we're looking for a solution to predefined problems
(e.g. parallelise some existing program), but really parallelism will
spread and become standard for different problems.
Actually, I don't know why I use the future tense. It's already clearly
the case for numerical computing, computer graphics, web serving, ...
Stefan
Andy "Krazy" Glew
> GPGPU are NOT a parallelization technology. It is a platform for
> executing parallel code. I guess you can't name a parallelization
> technology.
I think this is key:
The way to parallel code is not parallelization of sequential code, but
making it easier for programmers to express the natural parallelism of
their code. Heck, maybe not even easier - it's always been easy - but
removing the penalties for expressing parallel code.
The "sequential" Von Neuman model was created not because parallel code
was hard to write, but to make it easier to debug. So I place high value
on, not so much parallel debuggers (which, like parallelization, are
always just around the corner [*]) but on programming styles, support
for, which intrinsically provide deterministic parallel execution.
([*] at SC09 in one of the workshops the presenter said "What is the
gold standard for debugging parallel programs? Printf. Not Totalview,
not..." This was one of the most experienced parallel programmers in
the world.)
Michael Wolfe, author of Optimizing Supercompilers for Supercomputers,
in a compiler class I took from him, said that vectorizing compilers did
not really advance. Rather, programmers learned to use the idioms that
the compiler could vectorize well. True for all optimization.
Including parallelization.
Brett Davis
Your best post ever. That is exactly how programmers like me work.
Here, let me pimp Grand Central Dispatch again:
Even though I have not used it yet. ;)
http://images.apple.com/macosx/technology/docs/GrandCentral_TB_brief_20090903.pdf
Brett
Andy "Krazy" Glew
> Robert Myers wrote:
>> How far does this have to go before you will admit that the
>> rules have changed?
>>
>
> Once they start hitting 100s of cores. 16-ways have been available and
> worked on since, oh, forever. I don't know if C.mmp is the earliest, but
> that dates back to 1971. Clusters (which are fairly similar as far as
> the programming is concerned) pre-date this.
Amen to this. 100s or 1000s of cores. Although, for some workloads,
coherent threads will suffice.
I'm not in this argument. I'm just chiming in.
Andy "Krazy" Glew
>
>> To avoid these overheads and to achieve load balancing, I have been
>> thinking about an implementation that automatically switches between
>> communicating between threads and using coroutining for efficient
>> communication within a thread. Currently these are just ideas, but I
>> have written them down in
>> <http://www.complang.tuwien.ac.at/kps09/pdfs/ertl.pdf>
Amen!
One of the most important parallelization technologies is
anti-parallelization - converting parallel code to sequential, when
sequential is more efficient.
Chris M. Thomasson
"Brett Davis" <gg...@yahoo.com> wrote in message
news:ggtgp-038A98....@netnews.asp.att.net...
work stealing? Intel and Clik++ together? Genius...
http://software.intel.com/en-us/articles/intel-cilk/
;^)
Andy "Krazy" Glew
> Mayan Moudgill <ma...@bestweb.net> writes:
>> Anton Ertl wrote:
>>
>>> To avoid these overheads and to achieve load balancing, I have been
>>> thinking about an implementation that automatically switches between
>>> communicating between threads and using coroutining for efficient
>>> communication within a thread. Currently these are just ideas, but I
>>> have written them down in
>>> <http://www.complang.tuwien.ac.at/kps09/pdfs/ertl.pdf>
>>>
>> Did a quick read of the paper. My summary [Correct me if I'm wrong]
>
> No correction needed.
>
>> Kernel scheduling
>> 5. If kenel Ki pipes information to a Ki+1 on the same core, it may
>> yield (using coroutine semantics) to Ki+1 after writing the information
>
> The way I envision is that it yields, eliminating the need for
> buffering between the tasks (kernels) in this case.
>
>> Critique:
>> 1. Only works for pipelines; it doesn't work with more complicated
>> graphs such as DAGs.
>
> Does this refer to the load balancing? It would certainly get more
> complicated with DAGs. However, I don't think that DAGs would be used
> much even if they are supported.
There are many existing examples of DAGs. Cycles, even.
At SC09 (last week in Portland) IBM made a fuss about stream computing.
*NOT* stream processing a la Daly. More like "Flow based programming" a
la Morrison (http://www.jpaulmorrison.com/fbp/), which dates back to the
60s and 70s.
Googling "stream computing IBM" finds stuff like
--> Stream computing for financial services (sorry, link expired, use
google's cache)
-->
http://domino.research.ibm.com/comm/research_projects.nsf/pages/esps.index.html
SPADE (short for "Stream Processing Application Declarative Engine") has
been around at least since 2007 when IBM rolled out its System S stream
computing solution, a system with 800 or so processors. The System S
software lets application software split up tasks, then reassemble the
data into something that makes sense.