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: < <mailto:[log in to unmask]> [log in to unmask]>
USA
Linked-In: <http://www.linkedin.com/in/craigdedo> 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.
