experchange > fortran

BaRud (10-29-18, 10:24 AM)
Dera friends,
Today I saw a post that says Linux kernel got free from C's variable length array(VLA). Though my C knowledge is very limited, it is the length of array determined in runtime, which is similar to allocatable array.

Now in the post it seems that, according to the post VLA slows the code. Though my codes are 1000 times smaller than the kernel, does it affect the speed and overhead of fortran as well? Can someone kindly explain?

This is the website link:
Arjen Markus (10-29-18, 12:18 PM)
On Monday, October 29, 2018 at 9:24:22 AM UTC+1, BaRud wrote:
> Dera friends,
> Today I saw a post that says Linux kernel got free from C's variable length array(VLA). Though my C knowledge is very limited, it is the length of array determined in runtime, which is similar to allocatable array.
> Now in the post it seems that, according to the post VLA slows the code. Though my codes are 1000 times smaller than the kernel, does it affect the speed and overhead of fortran as well? Can someone kindly explain?
> This is the website link:
>


VLAs in C are comparable to automatic arrays in Fortran:

subroutine use_work( n )
integer, intent(in) :: n

real, dimension(n) :: work ! Local array, with variable size n
...
end subroutine use_work

From the post I understand that VLAs are also used in structures - how thatworks out I do not know, but I can imagine that that causes a lot of overhead: the position of elements from such a structure in memory then depends on the actual size and thus can not be determined at compile-time.

Well, in Fortran you do not have that sort of feature: automatic arrays cannot be part of a structure.

I would not worry about the overhead such arrays cause in a typical program.. The alternative would be to use fixed-size arrays or allocatable arrays and they come at a cost as well. The most important cost, however, is the time spent by the programmer and the user. Automatic arrays make it easier tocreate a flexible program and the user has less to worry about wrt array sizes that are too small for the problem at hand.

Regards,

Arjen
FortranFan (10-29-18, 03:16 PM)
On Monday, October 29, 2018 at 6:18:33 AM UTC-4, Arjen Markus wrote:

> ..
> Well, in Fortran you do not have that sort of feature: automatic arrays cannot be part of a structure.
> ..


@Arjen Markus,

Re: "Fortran you do not have that sort of feature: automatic arrays cannot be part of a structure" is incorrect e.g., with parameterized derived types (PDTs), one can have variable length arrays in structures:

module m
type :: t(n)
integer, len :: n
character(len=n) :: s
end type
contains
subroutine sub( n )
integer, intent(in) :: n
type(t(n=n)) :: foo
foo%s = repeat("x", ncopies=foo%n)
print *, "len(foo%s) = ", len(foo%s), "; expected is ", n
print *, "foo%s = ", foo%s
end subroutine
end module
use m, only : sub
call sub( n=1 )
call sub( n=3 )
end

The above code is supported by both Intel Fortran and gfortran to give the output:
len(foo%s) = 1 ; expected is 1
foo%s = x
len(foo%s) = 3 ; expected is 3
foo%s = xxx

As to whether such code is performant, it is a separate matter altogether: one needs to have a good overall understanding of one's code and be able to analyze it vis-a-vis the needs and applications before jumping to any conclusions.
Arjen Markus (10-29-18, 05:32 PM)
On Monday, October 29, 2018 at 2:16:50 PM UTC+1, FortranFan wrote:
[..]
> len(foo%s) = 3 ; expected is 3
> foo%s = xxx
> As to whether such code is performant, it is a separate matter altogether: one needs to have a good overall understanding of one's code and be able to analyze it vis-a-vis the needs and applications before jumping to any conclusions.


Ah, that is true indeed, I had overlooked that possibility. Thanks for this correction!

Regards,

Arjen
James Van Buskirk (10-30-18, 02:06 AM)
"BaRud" wrote in message
news:bf58

> Today I saw a post that says Linux kernel got free from C's
> variable length array(VLA). Though my C knowledge is very
> limited, it is the length of array determined in runtime,
> which is similar to allocatable array.


> Now in the post it seems that, according to the post VLA
> slows the code. Though my codes are 1000 times smaller
> than the kernel, does it affect the speed and overhead of
> fortran as well? Can someone kindly explain?


I imagine the Linux kernel doesn't do a whole lot of linear
algebra. Before C99, the language didn't have any arrays,
just fancy syntax for dereferencing pointers. The result was
that what looked like a 2D array was actually a C_PTR that
pointed at an array of C_PTRs that pointed at conventionally
the rows of the array.

Thus access across rows had to be through that array of
pointers with unpredictable strides so such operations were
less efficient than the Fortran (or VLA) way. Of course one
could allocate the storage for a 2D array and then find
the offset of any array element by hand and write that into
your code but to a Fortran programmer that starts to look
more like assembly language than a high level programming
language.

C99 VLAs seem to have to start out their lives as automatic
arrays unless you can malloc() to a simple pointer and cast
it somehow as a VLA. Automatic arrays in C have the same
problem as in Fortran in that they go on the stack and just
an innocent change in problem size can cause a crash at
runtime even though there is plenty of physical and virtual
memory available to store the array.
Tim Prince (10-30-18, 04:48 AM)
On 10/29/2018 8:06 PM, James Van Buskirk wrote:
[..]
> an innocent change in problem size can cause a crash at
> runtime even though there is plenty of physical and virtual
> memory available to store the array.

C VLA or Fortran automatic array, compared with local static array,
incurs some performance penalty when entering or leaving
function/procedure. Although VLA was incorporated in C99, it has been
made optional since, possibly because it wasn't always done right, isn't
standard in C++, and for the reason James mentioned (there's no recovery
from unexpected faults). malloc() or Fortran ALLOCATE offer a fault
detection option, don't hide what is going on, and shouldn't have
significant additional overhead. Now that Fortran has implicit dynamic
reallocation, more overhead occurs whenever the array is extended (which
could previously have been a program bug not easily detectable other
than by compiling with bounds checking).
Ron Shepard (10-30-18, 06:59 AM)
On 10/29/18 9:48 PM, Tim Prince wrote:
> Now that Fortran has implicit dynamic
> reallocation, more overhead occurs whenever the array is extended (which
> could previously have been a program bug not easily detectable other
> than by compiling with bounds checking).


Are you talking about automatic or allocatable arrays here. Can you give
an example of this?

$.02 -Ron Shepard
JCampbell (10-30-18, 07:38 AM)
I have found that suggestions of the relative performance of local, automatic or allocatable arrays can be very subjective and often misleading. Therecan be particular cases where allocatable arrays perform poorly, such as deep in nested DO loops, but typically there is not a lot of performance difference in the way you allocate arrays on the stack or heap. The question should be why allocate so many times?

In recent experience, I have had 2 cases that I found interesting:
1) for small arrays in !$OMP, I would have expected to get better results with automatic arrays allocated in separate thread stacks, rather than use ALLOCATE on a single heap. The hope was to demonstrate less cache coherence conflicts, but the results were not consistently better.
2) using "small" allocatable components in a derived type, looks more elegant, but can come at a significant storage overhead for defining the allocatable attribute, although with 64-bit either fixed array size or definition overhead is often not a serious issue.

My Fortran experience is that this is usually a very minor issue, although I am sure there are some particular cases where it might be more important.
My closest case could be connectivity analysis, but even there choosing an appropriate linked list structure is far more significant. (For equation ordering in FE analysis, I now find the !$OMP equation solver is faster than the re-ordering strategies. How times have changed!)
Louis Krupp (10-30-18, 07:42 AM)
On Mon, 29 Oct 2018 18:06:03 -0600, "James Van Buskirk"
<not_valid> wrote:

<snip>
[..]
>your code but to a Fortran programmer that starts to look
>more like assembly language than a high level programming
>language. <snip>


To the best of my knowledge, C has always had fixed-size arrays that
went into static storage if they were declared static or extern or
onto the stack if they were automatic.

One-dimensional arrays look like this:

int a[4];

and two-dimensional arrays look like this:

int b[3][4];

which is stored as a one-dimensional array, call it x, of 12 ints
broken down into three groups of four, with a predictable stride, and
b[i][j] being the same as x[i * 4 + j].

An equivalent Fortran declaration would be:

integer fb(4, 3)

In C, it's also possible to declare an array of three pointers:

int (*c)[3];

and assign values to each one. For example, each element of c could
point to its own newly-allocated one-dimensional array of four ints:

c[0] = (int*)malloc(4 * sizeof(int));
....

In this case, c[i][j] would access elements through pointers.

b[2][0] and c[2][0] are similar, and you'd have to look at the
declarations of b and c to see what's really going on.

Not everyone thinks this is a wonderful way to design a language.

(Once upon a time, I used a version of ALGOL that always allocated
arrays on the heap and always set up two-dimensional arrays as arrays
of pointers to one-dimensional arrays. Like it or not, it was at least
consistent.)

Louis
James Van Buskirk (10-30-18, 08:09 AM)
"Louis Krupp" wrote in message
news:oqdu

> On Mon, 29 Oct 2018 18:06:03 -0600, "James Van Buskirk"
> <not_valid> wrote:


> >I imagine the Linux kernel doesn't do a whole lot of linear
> >algebra. Before C99, the language didn't have any arrays,
> >just fancy syntax for dereferencing pointers. The result was
> >that what looked like a 2D array was actually a C_PTR that
> >pointed at an array of C_PTRs that pointed at conventionally
> >the rows of the array.



> To the best of my knowledge, C has always had fixed-size arrays that
> went into static storage if they were declared static or extern or
> onto the stack if they were automatic.


> One-dimensional arrays look like this:


> int a[4];


> and two-dimensional arrays look like this:


> int b[3][4];


> which is stored as a one-dimensional array, call it x, of 12 ints
> broken down into three groups of four, with a predictable stride, and
> b[i][j] being the same as x[i * 4 + j].


> An equivalent Fortran declaration would be:


> integer fb(4, 3)


> In C, it's also possible to declare an array of three pointers:


> int (*c)[3];


> and assign values to each one. For example, each element of c could
> point to its own newly-allocated one-dimensional array of four ints:


> c[0] = (int*)malloc(4 * sizeof(int));
> ...


> In this case, c[i][j] would access elements through pointers.


> b[2][0] and c[2][0] are similar, and you'd have to look at the
> declarations of b and c to see what's really going on.


> Not everyone thinks this is a wonderful way to design a language.


> (Once upon a time, I used a version of ALGOL that always allocated
> arrays on the heap and always set up two-dimensional arrays as arrays
> of pointers to one-dimensional arrays. Like it or not, it was at least
> consistent.)


But I mentioned doing linear algebra in C in my first sentence. Think
about what a subroutine to perform QR factorization in pre-C99 C
would look like, for example. In such a context fixed-size arrays are
not useful.
Ron Shepard (10-30-18, 05:38 PM)
On 10/30/18 1:09 AM, James Van Buskirk wrote:
> But I mentioned doing linear algebra in C in my first sentence.  Think
> about what a subroutine to perform QR factorization in pre-C99 C
> would look like, for example.  In such a context fixed-size arrays are
> not useful.


I guess I could look at assembly code to figure this out, but how has
this situation changed with C99? Are array elements indexed with fixed
strides between rows and columns (as in fortran), or are they indexed
with offsets from pointers? I know that the lower bound of all arrays in
C is still zero, so array handling is still brain dead in C for that
reason, but within that primitive environment, how has 2D and higher
array referencing changed for variable sized arrays?

$.02 -Ron Shepard
FortranFan (10-30-18, 09:33 PM)
On Monday, October 29, 2018 at 4:24:22 AM UTC-4, BaRud wrote:

> Dera friends, .. according to the post VLA slows the code. Though my codes are 1000 times smaller than the kernel, does it affect the speed and overhead of fortran as well? Can someone kindly explain? ..


Dera BaRud,

You seem to be working in a science-related field and appear to be an educator too based on your other recent thread: (). So why don't you make some effort to answer your question yourself, at least within the context of the kinds of codes you write, and post your own findings here for the benefit of everyone?

Here's a place you can start to read with examples in both C and Fortran toboot!
James Van Buskirk (10-30-18, 09:35 PM)
Sorry my reply seems to have gotten lost. Hope this isn't a duplicate.

"Ron Shepard" wrote in message news:1617

> On 10/30/18 1:09 AM, James Van Buskirk wrote:
> > But I mentioned doing linear algebra in C in my first sentence. Think
> > about what a subroutine to perform QR factorization in pre-C99 C
> > would look like, for example. In such a context fixed-size arrays are
> > not useful.


> I guess I could look at assembly code to figure this out, but how has
> this situation changed with C99? Are array elements indexed with fixed
> strides between rows and columns (as in fortran), or are they indexed
> with offsets from pointers? I know that the lower bound of all arrays in
> C is still zero, so array handling is still brain dead in C for that
> reason, but within that primitive environment, how has 2D and higher
> array referencing changed for variable sized arrays?


That's exactly the difference. To pass a 2D array of variable shape in
pre-C99 C, you had to resort to

void var(size_t m, size_t n, intptr_t **A);

or

void var(size_t m, size_t n, intptr_t *A);

In the first case what got passed was literally a pointer to an array of
pointers to the rows of a (potentially ragged) array. Since the rows
could be located at random locations in memory the only way to
address an array element was through its row pointer. In the second
case the array could be neatly laid out in row-major order in memory,
but to access A[i][j] you needed to perform the arithmetic within the
program as A[n*i+j].

With C99 variable length arrays you can declare

void var(size_t m, size_t n, intptr_t A[m][n]);

And then only the address of the start of the array gets passed -- no
intermediate array of pointers of rows. The compiler knows that
the array must be laid out in row-major order so it can compute the
offsets without further human intervention:

D:\gfortran\clf\VLA>type vla_c.c
// file: vla_c.c
// gcc -Wall -c vla_c.c

#include <sys/types.h>

void var(size_t m, size_t n, intptr_t A[m][n]);

void vla_c(size_t m, size_t n)
{
intptr_t A[m][n];
size_t i;
size_t j;
for(i = 0; i < m; i++)
{
for(j = 0; j < n; j++)
{
A[i][j] = n*i+j;
}
}
var(m, n, A);
}

D:\gfortran\clf\VLA>gcc -Wall -c vla_c.c

D:\gfortran\clf\VLA>type vla_f.f90
! File: vla_f.f90
! gfortran -Wall vla_f.f90 vla_c.o -ovla_f

module vla
use ISO_C_BINDING
implicit none
interface
subroutine vla_c(m, n) bind(C,name='vla_c')
import
implicit none
integer(C_SIZE_T), value :: m
integer(C_SIZE_T), value :: n
end subroutine vla_c
end interface
contains
subroutine var(m, n, A) bind(C, name='var')
integer(C_SIZE_T), value :: m
integer(C_SIZE_T), value :: n
type(C_PTR), value :: A
integer(C_INTPTR_T), pointer :: fA(:,:)
integer(C_SIZE_T) i
integer(C_SIZE_T) j
write(*,'(*(g0))') 'In var, m = ', m, ', n = ', n
write(*,'(*(g0))') transfer(A,0_C_INTPTR_T)
call C_F_POINTER(A, fA, [m,n])
do i = 1, m
do j = 1, n
write(*,'(*(g0))') 'A(', i, ',', j, ') = ', fA(i,j)
end do
end do
end subroutine var
end module vla

program main
use vla
implicit none
integer(C_SIZE_T) m
integer(C_SIZE_T) n
m = 3
n = 3
call vla_c(m, n)
end program main

D:\gfortran\clf\VLA>gfortran -Wall vla_f.f90 vla_c.o -ovla_f

D:\gfortran\clf\VLA>vla_f
In var, m = 3, n = 3
2358544
A(1,1) = 0
A(1,2) = 3
A(1,3) = 6
A(2,1) = 1
A(2,2) = 4
A(2,3) = 7
A(3,1) = 2
A(3,2) = 5
A(3,3) = 8
FortranFan (10-31-18, 04:18 AM)
On Tuesday, October 30, 2018 at 3:35:51 PM UTC-4, James Van Buskirk wrote:

> ..
> void var(size_t m, size_t n, intptr_t A[m][n]);
> void vla_c(size_t m, size_t n)
> {
> intptr_t A[m][n]; ..


To the extent one can meaningfully determine the extra overhead compared tofixed-size arrays (touted by Torvalds et al. for their Linux kernel patch)in an application involving a function with variable-length arrays such asvla_c above which has to set up an automatic object of varying shape at run-time upon each invocation, any performance hit will depend upon of the frequency of such function calls and to some extent also the overall size of the object relative to hardware and memory read/write considerations ratherthan whether the object is 1D/2D/3D/.. arrays.
gah4 (12-14-18, 10:23 AM)
On Tuesday, October 30, 2018 at 12:35:51 PM UTC-7, James Van Buskirk wrote:

(snip)

> That's exactly the difference. To pass a 2D array of variable shape in
> pre-C99 C, you had to resort to


> void var(size_t m, size_t n, intptr_t **A);


> or


> void var(size_t m, size_t n, intptr_t *A);


> In the first case what got passed was literally a pointer to an array of
> pointers to the rows of a (potentially ragged) array. Since the rows
> could be located at random locations in memory the only way to
> address an array element was through its row pointer. In the second
> case the array could be neatly laid out in row-major order in memory,
> but to access A[i][j] you needed to perform the arithmetic within the
> program as A[n*i+j].


> With C99 variable length arrays you can declare


> void var(size_t m, size_t n, intptr_t A[m][n]);


> And then only the address of the start of the array gets passed -- no
> intermediate array of pointers of rows. The compiler knows that
> the array must be laid out in row-major order so it can compute the
> offsets without further human intervention:


Like Fortran has been able to do inside subroutines
since Fortran 66.

While the array of pointers method is often useful,
especially when you can use a ragged array, the other form is
also useful. It was missing from C for a long time.

Similar Threads