Hello,
I am starting to play with dynamic data structures, such as linked lists and
trees, in Fortran 95 and I am running into some "interesting" observations
and problems related to the ammount of memory reserved for pointers, data
types, and allocation.
Attached is a simple program malloc.f90 that illustrates the need for the
following question: hat is the preferred strategy for allocating a lot of
small data, such as for example allocating nodes to be inserted in a large
linked list or tree? The UNIX malloc must mark each allocated block, and it
is usually smart enough to reserve certain blocks of memory before hand and
then use this block for small allocations, however, I have read in C books
that one should do this alloction manually and not leave it to the hands of
malloc. I assume most UNIX Fortran implementations dellegate all allocations
to malloc?
For example, in the attached program, I have two versions of allocating a
bunch of pointers to be used in a linked list--by allocating them one by one
via:
do i=1, n
allocate(next_node)
end do
and by allocating them all at once via:
allocate(memory_block(n))
Using the memory profiler memprof I came to the following scary conclusion:
EACH allocation allocate(next_node) allocates a total of 48 bytes !!! The
basic unit next_node costs only 12 bytes though, 4 for the integer key and 8
for the pointer (I am not sure why the pointer is 8 and not 4 bytes
either...). Each allocate thus creates a record of 32 or so bytes. I am not
sure if this is including the record created by malloc or this is just the
record created by the Fortran run-time library.
I don't have much experience with anything other than array pointers in
Fortran 95, and of course I have read many places that these kind of issues
exist. But 48 bytes is way too much for a datum of 12 bytes. I would
appreciate any advice and pointers from people that use Fortran 95 for
dynamic data structures, if such people exist at all.
Thanks,
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
_____________________________________________
program malloc
integer :: n
integer :: i
type node_type
integer :: key=0
type(node_type), pointer :: next=>null()
end type
type(node_type), pointer :: node, next_node
type(node_type), dimension(:), allocatable, target :: memory_block
write(*,*) "n :?"
read(*,*) n
allocate(node)
node%key=1 ! First node in list
do i=2, n
allocate(next_node)
next_node%next=>node
next_node%key=i
node=>next_node
end do
! TEST
! call print_list(node)
allocate(memory_block(n))
memory_block(1)%key=1
do i=n, 2, -1
memory_block(i)%next=>memory_block(i-1)
memory_block(i)%key=i
end do
node=>memory_block(n)
! TEST:
! call print_list(node)
contains
subroutine print_list(node)
type(node_type), pointer :: node
type(node_type), pointer :: finger
write(*,*) "List:"
if(.not.associated(node)) return
finger=>node
do
write(*,*) finger%key
if (.not.associated(finger%next)) return
finger=>finger%next
end do
end subroutine print_list
end program malloc
|