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

[Per W. <pw...@ia...>]

On Thu, 31 Oct 2002, Ioannis Vranos wrote:

> > -----Original Message-----
> > From: Per Westermark [mailto:pw...@ia...] 
> > Sent: Wednesday, October 30, 2002 11:49 PM
> > To: Ioannis Vranos
> > Cc: 'Dev-C++ Mailing List'
> > Subject: 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...
> 
> 
> All these are true. However all these that you say apply to dedicated
> machines. In a regular whatever PC with whatever multitasking OS you
> can't control the cache etc. So regarding the question of the fellow,
> there can not be an impact in speed.
No, the concept is just about the same for any machine. It is just the
width of the memory interface, the cache line sizes, the number of cache
lines etc that are different. A Fortran (or C, Pascal etc) program
optimized for locality of reference of data accesses will will gain speed
on just about any computer architecture. It doesn't matter if we talk
about Von Neuman, SIMD, MIMD or whatever kind of machine. The physical
properties of memory still applies, i.e. cache is faster than primary
memory, primary memory is faster than disk.
The original Fortran algorithms might have been written for a Vax machine,
but the same optimizations still improves the speed on a Xeon processor.
> 
> 
> > 
> > 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. 
> 
> I disagree. If you mean C algorithms accessing Fortran structures i can
> agree, only when talking about a dedicated system.
> On non-dedicated systems, and C structures C code can be the same
> efficient (and sometimes even more).
You disagree, while still agreeing :-) I am talking about algorithmig
optimization, not language optimization, and I am talking about the
problem of just translating an algorithm from one language to another
while still keeping the speed. Take a C++ template solution with sort. I
can't easily convert that code to another language. However, I can still
get the same speed in a Pascal program by doing a full rewrite, doing a
hand-coded qsort with inline comparison. The same goes the other way. I
can't take an optimized  Fortran program and convert statement for
statement to a C++ program and match the speed.

Since we are talking about algorithmic efficiency, and locality of
reference of data accesses, it shouldn't matter so much about which
computer architecture. The location of the break points in your referenced
document moves a bit to the left or right because of cache sizes, but htey
wouldn't even be there if locality of reference wasn't an issue, since
these break points isn't about code generation, but about data access
patterns of the algorithm.
> 
> 
> 
> > 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.
> 
> Yes.
> 
> 
> 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
>