RE: [Dev-C++] Mixed Language Programming w/Dev-Cpp

The speed issue isn't in this case a question about the efficiency of
Fortran or C, but the efficiency of porting an algorithm written for one
language to another language.

The array index  order of a language - many languages, but not all - may
not be changed in the language implementation, but are specified in the
description of the language.

The internal cache lines in the processor have a lot wider access path
than the primary memory. For a 32-bit processor, the memory access path
might be 64 bit, but the cache-lines might be 128 bit, 256 bit or even
wider. Everytime the processor doesn't find it's data in a cache line, it
has to wait for the data to be fetched from primary memory. That takes a
lot of time. Obviously, any memory-intensive algorithm should make sure
that the access pattern matches the physical storage of the data. Data
here isn't just integers and floats to perform math on, but just as
well the generated object code.

When programming in a high-level language, you normally doesn't have to
think so much about generated object code. That's up to the compiler.

However, the data layout is important. If I know that a specific processor
always loads at least 16 bytes from memory, whenever a cache line fails, I
may decide to place my 16 byte of "favorite" data first in any used
struct, so that the processor loads all the data from memory at a single
time, thereby reducing number of cache stalls.

On a bigger scale, when solving linear equations, the used matrices might
very well be 10000x10000 entries large. If each entry is a 8-byte double,
such a matrix will then consume 800 MB memory. If the machine hasn't that
amount of memory, it will start to swap out data to disk. A typical swap
block size might be 4kB, or 500 double numbers. If the program accesses
the entries in a sequential way, each disk load will guarantee 500
successful accesses before a new disk load is needed. If the program
accesses the entries in a random order (or with row/column swapped), EVERY
new accessed entry will require a disk load operation...

This isn't a problem for script languages etc, but a reason why few
"efficiency-oriented" programming languages leaves the definition
of array index order up to the implementation. For small structures, a
row/column transpose might double the execution time because of cache
trashing. For large structures, where swapping is needed, the speed
difference might be a factor of several thousand.

Most good Fortran algorithms contains thousands of thousands of lines of
code specifically designed to access the needed data in optimum order.
That is an important reason why it takes thousands of thousands of lines
of C code to match the performance. The same goes with just about any
programming language. Understanding of language and target machine might
be the difference between being able to solve a problem, or having to wait
a couple of years for faster machines to be released.

/Per W

On Wed, 30 Oct 2002, Ioannis Vranos wrote:

> > -----Original Message-----
> > From: Per Westermark [mailto:pw...@ia...] 
> > Sent: Wednesday, October 30, 2002 2:11 PM
> > To: Marc Heiligers
> > Cc: Ioannis Vranos; Dev-C++ Mailing List
> > Subject: RE: [Dev-C++] Mixed Language Programming w/Dev-Cpp
> > 
> > 
> > When you have declared
> > double a[10][10]
> > it is quite important to know in which order the individual values are
> > stored in memory, when trying to interface between two languages.
> > 
> > If your C program does a[x][y] and your Fortran program has do do
> > a[z][y] to reach the same entry. No problem when you have all three
> > index variables available.
> 
> 
> It's a syntax matter. As far as i can guess Fortran implementation is
> not required to store them in that order.
> 
> 
> 
> > However, when you take a pointer to a an entry inside the array, the
> > operation might be seen as a projection down to an array with fewer
> > dimensions. Obviously, if the entry order in memory has been 
> > transposed,
> > the such a projection will fail misserably when switching 
> > languages. The 
> > sender thought it sent a row, but the receiver got a column.
> > 
> > When people originally started to push for the C language, the above
> > problem gave rise to a related problem. When referencing large memory
> > structures, it is important to assure that the code uses locality of
> > reference and doesn't jump around everywhere in the data. Large linear
> > packages are always implemented so that they process entries 
> > in the same
> > order that they are stored in memory. When converting such an 
> > algorithm -
> > might be thousands uppon thousands of lines of code - it 
> > isn't s easy to
> > just try and adjust for row/column switches. The result is that a C
> > translation of a Fortran algorithm might loose 10-30% or 
> > maybe more of the
> > speed when the same Fortran algorithm was run.
> 
> Why?
> 
> > The mathematical world decided that C was a slower language 
> > :-) 
> 
> 
> Well, one of the reasons that Fortran is fast is because it is heavily
> optimised during those years and not because its syntax is close to the
> metal. Now this doesn't apply anymore.
> 
> Check the following: 
> 
> http://csweb1.cs.tamu.edu/seminars/dlecture/abstracts/stroustrup.MPP-sli
> des.pdf
Very good document. Exactly my point. A language is efficient when it is
used in the correct way. One interesting note.
On page 7, the "bumpines" of the curves clearly display how the different
algorithms and compiler optimization has managed to optimize the memory
accesses.

> 
> 
> where it has the graphh with the title "Uncompromising Performance".
> 
> 
> 
> > Nowadays,
> > there are a lot of good algorithms originally written for C, 
> > so this issue
> > shouldn't be a problem anymore. But still, there are some billion
> > Fortran lines of optimized and very advanced mathematics 
> > algorithms out
> > there.
> 
> 
> Yes there are indeed.
> 
> 
> Btw, Fortran has the notion of pointers?
Call by reference is an important concept, and one where the index order
is significant, if you only send a reference to a part of a larger matrix.
> 
> 
> Ioannis
> 
> * Ioannis Vranos
> * Programming pages: http://www.noicys.freeurl.com
> * Alternative URL: http://run.to/noicys
> 
> 
> -------------------------------------------------------
> This sf.net email is sponsored by: Influence the future 
> of Java(TM) technology. Join the Java Community 
> Process(SM) (JCP(SM)) program now. 
> http://ads.sourceforge.net/cgi-bin/redirect.pl?sunm0004en
> _______________________________________________
> Dev-cpp-users mailing list
> Dev...@li...
> TO UNSUBSCRIBE: http://www.noicys.cjb.net/devcpp/ub.htm
> https://lists.sourceforge.net/lists/listinfo/dev-cpp-users
>