Arrays and lists

Help
33

Just out of simple curiosity, I wanted to test how the nice linked-list/stack approach both @FortranFan and @RonShepard have highlited (firstly mentioned here by @everythingfunctional) was performing compared to the “classical” array-growth approach as @PierU has shown, after some modifications:

   implicit none
   integer, parameter :: N_MAX = 10000000
   integer :: i, n, waste = 0
   integer, allocatable :: array(:)  ! final target array.
   integer :: istart
   integer :: last_size = 1
   integer, allocatable :: tmp(:)

   allocate(array(last_size))
   istart = 1
   10 do i = istart, last_size
      array(i) = i
   enddo
   if (last_size < N_MAX) then  ! save current array batch, then grow
      call move_alloc(from=array, to=tmp)
      allocate(array(last_size*2))
      array(1:last_size) = tmp     ! memcpy ....
      deallocate(tmp)
      istart    = last_size+1
      last_size = last_size*2
      if (last_size > N_MAX) then
         waste     = last_size - N_MAX
         last_size = N_MAX
      endif
      goto 10
   endif

It turns out that, using compiling with ifort /stand /standard-semantics /Od main.f90, the array-growth approach is much faster (0.22s vs. 1.6s, factor around 7-8x, same if using /O3).
Which has quite surprised me.

Does, as stated in this answer:

A note on performance:

    1. Yes linked lists have some overhead compared with arrays

fully justify such a difference in performances?

Indeed, it remains the fact that linked-list/stack approach is the way-to-go in order to avoid any memory waste.

But it looks like that the time actually spent doing the n = {\rm ceil}({\frac{\log{N_{max}}}{\log{2}}}) memory copies (and consequent new allocations) in the “array-growth” case is lower than the time needed for the N_{max} node allocations allocate( new ) plus the time to fully traverse the list in the other case.

4 Likes