linked list memory usage

Accelerated Computing HPC Compilers Legacy PGI Compilers
1

Hi,

I am trying to figure out the memory usage of a linked list in fortran 90. I use the following simple test code.

program test_sub
  implicit none

  type:: mytype
     integer :: ij(2)
     type(mytype), pointer :: next
  end type mytype

  integer :: k, n
  type(mytype), pointer :: head, tail, item
  
  n=1e7  !---> length of the list
  nullify(head, tail)
  do k=1,n
     nullify(item)
     allocate(item)
     item%ij=1
     if (k==1) then
        head=>item
        tail=>item
     else
        tail%next=>item
        tail=>item
     end if
  end do

  stop
end program test_sub

I expect 16 byte per node (8 byte for the integers and 8 for the pointer) and ~150mb memory usage in total. However when I check the usage through the system using ‘top’ command, I see 764mb. If I increase the length of the list to 1e8, memory usage is 7.5gb while I expect it to be 1.5gb. Am I doing something stupid in this code? Or my calculations are wrong? I am using pgf90 version 7.0 on a linux 64 bit machine without any flags. Can anybody help me out?

Thank you for your time
Onur Bakir

2

Hi Onur,

I see the same thing. Here’s how I diagnose the issue:

  1. First, F90 pointers are different than C pointers. We have to keep a little bit of information around in a header for for some of the fortran 90 semantics. I gets much bigger if the pointer points to an array section, but in your case, just a pointer to a “scalar”, I think we need 16 bytes.

  2. The actual data takes 16 bytes.

  3. You have uncovered an inefficiency in our alignment algorithm. We should be able to get by with 32 bytes total per allocate, but due to alignment problems, we actually add another 32 bytes total of padding. I think we can do something about that in a future release.

3

Thanks brentl, that was helpful. I did not know that pointers are taking this much space. Having few variables at each node, the linked-list data structure becomes very inefficient, even if each allocation takes 32bytes space. Linked lists have a big disadvantage in there.