Hi
Naomi,
Thanks
for saying, “Any ideas are welcome!” All of my ideas are in
the area of seriously looking at alternatives to developing your own memory
manager.
Your
original and follow-up messages suggest that there are a large number of issues
that you need to address together. I suggest that you first take a deep
breath, pause for a few hours, and think through the overall design of your
program from scratch.
First,
I am no expert on compiler design, algorithms, or memory management. I
like to use Fortran to solve practical problems, much like you are apparently
doing. My experience with Fortran goes back to my undergraduate days in
the mid-1970s. I still follow the latest developments, such as the
soon-to-be-released Fortran 2008 standard. Although I do not have a
Computer Science, Software Engineering, or Information Systems degree at either
the undergraduate or graduate level, I have taken many university courses for
credit on various topics of software development and I have read extensively in
the professional and popular literature on software development topics.
My
education and reading teaches me that optimization of any kind is one of the
things that you should do last in the software development process. Here
are two quotes from giants of the software development profession that illustrate
this point perfectly.
Donald
Knuth: “We should forget about small efficiencies, say about 97% of
the time; premature optimization is the root of all evil.”
M.
A. Jackson: “Jackson’s Rules of Optimization: Rule
1. Don’t do it. Rule 2 (for experts only). Don’t
do it yet – that is, not until you have a perfectly clear and unoptimized
solution.”
There
is a very good introduction to the strategic issues of optimization in both
editions of Code Complete by Steve McConnell. See Code Complete,
1st ed., ch. 28, pp. 675–694; Code Complete, 2nd
ed., ch. 25, pp. 587–608. I strongly recommend that you get one or
both editions of this book and read the relevant chapters.
You
need to realize that developing a memory manager is an extremely complex and
sophisticated system programming task. Specialists in this kind of work have
been developing memory management algorithms for 50 years. It is
extremely unlikely that anything that you develop by yourself will not be
nearly as efficient as the memory management capabilities that are contained
within the compilers, run-time libraries, and operating system. There is
also a high likelihood of defects in anything that you develop yourself.
I
suggest that you reconsider many of your assumptions.
You
say, “Frequent allocate/deallocates of large arrays is very inefficient.”
Are you sure? Have you actually measured how much time the allocates and
deallocates take? Do you know anything about how much overhead a large number
of allocates and deallocates take? How many allocates and deallocates are
there in a typical run of your program? What have you actually
measured? If you have few or no measurements, then I would strongly
recommend that you first measure the cost of the numbers of allocations and
deallocations that you anticipate your production program will have. Developing
measurement programs like this involves far less complexity and requires far
less effort than developing a memory manager does.
You
say, “This will eliminate system interrupts and paging.” How
do you know if allocation or deallocation causes any system interrupts or
paging? Again, this is something that needs to be measured or, at
the very least, needs to be researched in the relevant documentation. It is
plausible that allocation and deallocation could involve few, if any,
interrupts and/or paging. Allocatable arrays already have a data
structure created for them at compile time, when they are declared. When they
are allocated at run time, the RTL allocates the memory, and if the allocation
is successful, fills in the components of the data structure. It is plausible
that the procedure calls involved in this operation generate few or zero
interrupts. How many page faults there are would depend largely on the
operation and design of the virtual memory manager of the OS.
You
say, “This application will be running for many days and . . .”
How do you know that this is an accurate estimate of the run time? Have
you measured the size of the data and the number of iteration cycles of any
simulation that you may be doing? Again, these sizes and their consequent
run times are things that should be measured.
You
say, “This application will be . . . dividing a huge matrix into pieces
of varying sizes, doing operations on them, and then moving on to process other
pieces of the matrix.” This sounds very much like the way that
large scale matrix operations were done in the dark ages of the 1960s and 1970s
before virtual memory was invented and implemented in commercial operating
systems. In fact, avoiding the need for doing this was the main reason
that virtual memory was invented. Does the origin of this program date
back to this time? If so, then I strongly recommend that you seriously
consider refactoring the program so that it implements a much more straightforward
solution, and therefore, passes off the task of memory management to the OS
virtual memory manager.
Here
is another issue about this matrix. Does the one large matrix represent a
single conceptual entity? If not, then it should be refactored into several
smaller matrices that have a one-to-one correspondence with their real world
conceptual entities.
What
about the sizes of the arrays in your example? Are they typical of the
arrays in your program? If so, then they consume very little memory
compared to the main memory (RAM) and virtual memory that is available on the
modern generation of computers. Assume that they are arrays of IEEE double
precision floating point elements, with 64 bits or 8 bytes per element. An
array of 10,000 elements would take up less than 80KB, an array of 100,000
elements less than 800KB, and an array of 1,000,000 elements less than 8
MB. This is very small compared to the sizes of RAM on the current
generation of computers. My current desktop PC has 8GB (i.e., 8192 MB) of
RAM and a paging file of 8483 MB. If the arrays sizes in your example are
typical, then the allocations and deallocations should generate very few page
faults, since your program will be much smaller than the physical memory on
your system.
What
operating systems and compilers do you have available? If you have
several compilers on several different systems available, then you can make
comparisons between systems to see what differences there might be running your
program on different platforms. Some Fortran compilers, such as G95 and Gfortran,
are free.
Are
you working on an aging mainframe system with an older Fortran compiler?
If so, then you may find it profitable to migrate your application to a modern
PC or workstation with an up-to-date Fortran compiler and OS.
I
hope you find my ideas useful. Please think thought these ideas and apply
them to your problem as well as you can. Any comments or concerns that
you or any other reader of this group would have, positive, negative, or
neutral, are most welcome.
Sincerely,
Craig T. Dedo
17130
W. Burleigh Place
P.
O. Box
423
Mobile Phone: (414) 412-5869
Brookfield,
WI 53008-0423 E-mail: <[log in to unmask]>
USA
Linked-In:
http://www.linkedin.com/in/craigdedo
>
-----Original Message-----
>
From: Fortran 90 List [mailto:[log in to unmask]] On Behalf Of
>
Greenberg, Naomi
>
Sent: Thursday, June 24, 2010 14:42
>
To: [log in to unmask]
>
Subject: Re: Memory management question
>
>
I'll try to clarify with an example. What I want to do is replace:
>
Real, allocatable :: array1(:), array2(:), array(3)
>
Allocate (array1(7000))
>
Allocate (array2(444))
>
...
>
Deallocate (array1)
>
Allocate (array1(33333))
>
Etc. with something like
>
Initialize up front, once: allocate Memory(100000)
>
>
Real, allocatable :: array1(:), array2(:), array(3)
>
Call allocMemMgr ( 7000, array1 )
>
Call allocMemMgr ( 444, array2 )
>
Etc. and have array1(100) be addressable in the main program.
The only thing I
>
can think of is having the manager return a start location and having the user
of
>
this manager explicitly use Memory(startLoc:startLoc+size) instead of an array.
>
>
Even were I to use equivalence, I'd have to declare each
array a fixed size
>
before equivalencing it to Memory(startLoc), wouldn't I? And this size
changes
>
during the program. So equivalence won't work. I'm no expert on
pointers, but I
>
thought they were dynamically allocated as well, which would defeat my purpose.
>
This application will be running for many days and will be dividing a huge
matrix
>
into pieces of varying sizes, doing operations on them, and then moving on to
>
process other pieces of the matrix.
>
>
Thanks,
>
Naomi
>
>
-----Original Message-----
>
From: Fortran 90 List [mailto:[log in to unmask]] On Behalf Of
Peter
>
Shenkin
>
Sent: Thursday, June 24, 2010 3:22 PM
>
To: [log in to unmask]
>
Subject: Re: Memory management question
>
>
On Thu, Jun 24, 2010 at 2:49 PM, Ted Stern <[log in to unmask]> wrote:
>
> On 24 Jun 2010 11:40:59 -0700, Vivek Rao wrote:
>
>>
>
>> Hello.
>
>>
>
>> If x(:) is your big array, in Fortran 90+ you can define a pointers
x1(:), x2
>
>> (:) etc. that refer to sections of it, for example
>
>>
>
>> allocate (x(1000000)
>
>> x1 => x(1:300000)
>
>> x2 => x(300001:1000000)
>
>>
>
>> Vivek Rao
>
>
>
> Naomi was specifically asking how to avoid slowdowns due to use of
>
> pointers.
>
>
Not the way I read her email.
>
>
I thought she was asking how to avoid slowdowns due to dynamic allocation.
>
>
But I have to say that I've never met anyone who tried to outwit the
>
system's dynamic allocator who came to a good end. The system Naomi is
>
suggesting is what we had to do in the bad old days, when we'd malloc
>
a huge array in C and find some kludgy way to equivalence Fortran
>
arrays to it.
>
>
-P.