Prev: New gfortran bug
Next: optimized code crashes under ifort
From: glen herrmannsfeldt on 4 Jun 2010 01:02
Ian Harvey <ian_harvey(a)bigpond.com> wrote:
(snip, I wrote)

>> In some theoretical calculations log(n) is used, and as an
>> approximation that probably isn't so bad.

> Perhaps I misunderstand, but I don't think the time for access to
> physical memory is order log(n), where n is the total allocated memory.
> Perhaps it is if n is the size of the working set (so the time takes
> into account things like cache and swapping?), but arrays that are
> allocated and not accessed aren't what I'd consider part of the working
> set. Or are you referring to the time needed to allocate the memory in
> the first place?

In discussion of the radix sort, the algorithm naturally seems
to have O(N) time. The time is proportional to N and to the
number of digits in the values being sorted. On a machine with
fixed sized variables, that should be constant. But as N goes
to infinity, some claim that it doesn't make sense to compare
fixed sized values, but that the number of digits should increase
os log(N).

OK, now for memory access. The address decoders on semiconductor
RAMs require log(N) level of logic to address N bits. As memory
arrays get bigger, the wires connecting them together get longer,
requiring longer delays.

As for instructions executed, on many machines it takes more
instructions to address larger arrays than smaller ones.
It won't be a continuous increase, but it often does increase.
Consider, for example near and far modes in x86 code.
Many RISC machines with 32 bit instructions can directly
address up to about 20 bits with one instruction, but it
takes two instructions as addresses get larger. VAX has
addressing modes with 8, 16, and 32 bit offsets, with longer
instructions and execution time for the longer offsets.

For the sizes of N likely to be encountered, it is a rough
approximation, but averaged over many machines and sizes
it isn't so bad.

-- glen

From: Richard Maine on 4 Jun 2010 02:12
glen herrmannsfeldt <gah(a)ugcs.caltech.edu> wrote:

> OK, now for memory access. The address decoders on semiconductor
> RAMs require log(N) level of logic to address N bits. As memory
> arrays get bigger, the wires connecting them together get longer,
> requiring longer delays.
>
> As for instructions executed, on many machines it takes more
> instructions to address larger arrays than smaller ones...

However, this all seems irrelevant to the OP's problem.

The number of wires and their length isn't going to change with his
memory size. That sounds like a comparison of different hardware - not
different sizes of code running on the same hardware. Yes, if his code
gets big enough, it could eventually require different hardware, but
that was one of the first, most basic, and most obvious points - that he
needed to worry if his memory size neared the limits of his system.

And the possible different instructions just aren't going to come up in
his case. Maybe if you were custom coding in assembly, but that's not
the case. In all but the most localized and special cases, the
instructions in the compiled code are going to be the ones that can
handle the largest arrays. That's because most of the code won't know at
compile time what size array it is dealing with.

For the OP's problem, which involved running a compiled code on a
particular architecture, the answer to his question is that there won't
be any difference from these matters.

--
Richard Maine | Good judgment comes from experience;
email: last name at domain . net | experience comes from bad judgment.
domain: summertriangle | -- Mark Twain
From: glen herrmannsfeldt on 4 Jun 2010 07:14
Richard Maine <nospam(a)see.signature> wrote:
> glen herrmannsfeldt <gah(a)ugcs.caltech.edu> wrote:

>> OK, now for memory access. The address decoders on semiconductor
>> RAMs require log(N) level of logic to address N bits. As memory
>> arrays get bigger, the wires connecting them together get longer,
>> requiring longer delays.

>> As for instructions executed, on many machines it takes more
>> instructions to address larger arrays than smaller ones...

> However, this all seems irrelevant to the OP's problem.

> The number of wires and their length isn't going to change with his
> memory size. That sounds like a comparison of different hardware - not
> different sizes of code running on the same hardware. Yes, if his code
> gets big enough, it could eventually require different hardware, but
> that was one of the first, most basic, and most obvious points - that he
> needed to worry if his memory size neared the limits of his system.

Yes.

> And the possible different instructions just aren't going to come up in
> his case. Maybe if you were custom coding in assembly, but that's not
> the case. In all but the most localized and special cases, the
> instructions in the compiled code are going to be the ones that can
> handle the largest arrays. That's because most of the code won't know at
> compile time what size array it is dealing with.

In the static case the compiler knows.

In the allocatable case, the compiler knows the size of the
variable holding the size. It seems likely that a compile
would generate different code for array accesses when the
subscript variables are larger than default integer, assuming
that the compiler allows for that.

(One complaint about Java is that the language definition
doesn't allow for larger than int (by definition, 32 bits)
when allocating arrays.)

> For the OP's problem, which involved running a compiled code on a
> particular architecture, the answer to his question is that there won't
> be any difference from these matters.

Most likely, yes. But then log() grows pretty slowly.

-- glen
From: glen herrmannsfeldt on 4 Jun 2010 07:21
Richard Maine <nospam(a)see.signature> wrote:
(snip)

> For the OP's problem, which involved running a compiled code on a
> particular architecture, the answer to his question is that there won't
> be any difference from these matters.

integer*8 i,j,k
integer*1, allocatable:: x(:)
i=3000000000
j=i
allocate(x(i))
print *,size(x)
x(j)=j
print *,j,x(j)
print *,huge(i)
end

It seems that when run with gfortran on 64 bit linux, the
allocate fails, but no error is indicated. It fails with
segmentation fault on the assignment. Fortran 2003 says:

"If an error condition occurs during execution of an
ALLOCATE statement that does not contain the STAT=
specifier, execution of the program is terminated."

It seems that size(x) returns zero, but the program was
not terminated on the ALLOCATE.

-- glen
From: helvio on 4 Jun 2010 08:31
On Jun 3, 5:55 pm, glen herrmannsfeldt <g...(a)ugcs.caltech.edu> wrote:
> helvio <helvio.vairin...(a)googlemail.com> wrote:
>
> (snip)
>
> > I think that everytime I create a module for my code, and after I
> > defrag it, I will create two copies of it. Something like
> > 'mod_modname_static.f90' and 'mod_modname_alloc.f90'. I will use the
> > static allocation version by default, and the dynamic allocation
> > version only if I see that my temporary arrays are too big.
>
> Well, you could use the C preprocessor, which is supported by
> many Fortran compilers, to select between the appropriate statements
> based on compiler command line options.
>
> #ifdef ALLOC
>    real, allocatable:: x(:,:)
> #else
>    real x(100,100)
> #endif
>
> Then, at least for compilers based on gcc, the -DALLOC
> command line option will select the allocatable version.
>
> -- glen

Thank you! I didn't consider this option previously, and it will be
very helpful in my code (and not just for the large array issue). I am
a physicist first and programmer second, and a consequence of that is
an incomplete understanding of Fortran, which I only use as an
auxiliary tool. I was unaware of C preprocessing and most details on
memory issues discussed here, and it's been great learning from the
masters. ;)

--helvio
First  |  Prev  |  Next  |  Last
Pages: 1 2 3 4 5
Prev: New gfortran bug
Next: optimized code crashes under ifort