On Friday, July 2, 2021 at 10:01:16 AM UTC-7, Ron Shepard wrote:
(snip, I wrote)
> > A loop using MOVE_ALLOC isn't so bad in most cases, though something
> > closer to C's realloc() might be nice.
> If the realloc cannot be done in-place, then this requires up to N**2
> data moves to read an array of length N. Not so bad if done in blocks
> maybe rather than individual elements, but still O(N**2) scaling. I
> think Fortran deserves a better solution to this common problem than that.
I always write mine to increase the size exponentially. I think my favorite
(I haven't done it recently) increased by 5/3 each time. So the number
of reallocations is O(log N), and so the elements moved is O(N logN).
But it does remind me of a (C) program I worked on many years ago,
where someone wrote an input routine which would read data a
line at a time, and strcat() it into a big (already allocated) array.
It turns out that, even without the reallocation that you note,
a strcat() loop is O(N**2). With N only (?) in the millions, it was
the dominant time for that program.
I also remember working on R program, which read in data and create
a matrix column by column, (or row by row) appending to the existing matrix.
That is, as you note, O(N**2). And many programs do this, even when the
size is known in advance.
Fortran fixed size (large) arrays were first done with single-task systems,
where there was no reason not to use all the memory. But then after
some years, there were multi-task real memory systems, where there
was a cost. (Though in the interests of keeping fragmentation down,
there weren't that many different sizes you could use.)
But then there was virtual memory, where the costs of large arrays
are mostly virtual storage. And with lazy allocation, many systems
don't even allocate any backing store for large arrays, until it
is used.
I now have Spice 2g6, the last of the Fortran Spice programs, running
with gfortran. From the notes, it looks like it was last done with f2c,
and then some of the C routines were modified later. In any case,
it was last used in the times of virtual memory systems, and uses the
the large (200000) element array system.
This is from the Fortran 77 days, when there is a large array, which is
then divided up for the various uses, keeping an index where each
array starts in the large array. For reasons that I don't know, it
fails with even -O1 in gfortran, but works with -O0.