Hi,

> Unless you are allocating a huge amount of data, it is almost
> certainly not worthwhile trying to second-guess the vendor - just do
> it the natural way for the algorithm.

Well, I am writing some codes for a data-structures class, but eventually I
want to apply these to some very demanding applications, where I allocate
several million nodes in the trees or lists.

Since my data arrays are so huge, I have decided to allocate all the nodes
at once and then use them one by one with each Insert operation. A really
efficient implementation would avoid derived data-types (structures)
completely because of their allignment problems and need for extra padding
space. For example, if one has the data-type (structure)

type example
    character :: letter
    integer :: key
    type(example), pointer :: next_in_list
end type

this would have to be padded with 3 bytes for allignment. Sturdy FORTRAN 77
emulations would have declared enough space to hold the data up front:

character, dimension(n) :: letters
integer, dimension(n) :: keys
integer, dimension(n) :: next_pointers

and then used the integers next_pointers in the linked list to point to
certain data-objects.

Now, I too have been spoiled by the dynamic approaches first introduced in
C, and now in F90, so I will not bother implementing the above efficient
methods for now, but this is mostly a choice of necessity and
time-considerations, not of efficiency's point of view.

> The C "malloc" does have some unfortunate characteristics, e.g. it
> adds an unnecessary storage overhead to each item, to store the size
> of that item.  (Well, there are techniques to avoid that, but not
> many implementations of malloc do.)

I see no way ALLOCATE can avoid this because of DEALLOCATE (other than
garbage collection), and of course malloc can do all the same things
ALLOCATE can, if the underlying system them. S, I think it's not malloc as
much as dynamic allocation itself.

> You probably have a machine with a bigger-than-32 bit address space,
> thus 8 byte (64 bit) pointers.
Not really, a Linux Pentium 32 bit machine, which as far as I know has
32-bit addresses. Anyway, I will not bother you all over 4 bytes :)

> Then, hardware alignment probably rounds your 12 bytes up to 16 bytes
> before we start adding any malloc overhead
Not really, as far as I know the alignment is 4 bytes on my system...

> Perhaps you should talk to your vendor directly?
> He is certainly in a better position to explain his own memory
> allocator!
These are not issues for my vendor. Fix one, break another is not my goal. I
am about to switch compilers soon anyway. I am very interested in
portability...

Thanks for the advice. I will just go with allocating large blocks of memory
and then using this when adding nodes to the dynamic structures. This fits
my applications well since I know the (maximum) number of nodes upfront. Not
ideal, but it should spare me some 36 bytes or so per datum!

Aleksandar

_____________________________________________
Aleksandar Donev
http://www.pa.msu.edu/~donev/
[log in to unmask]
(517) 432-6770
Department of Physics and Astronomy
Michigan State University
East Lansing, MI 48824-1116
_____________________________________________