Vectorization of Linked-list in Fortran

Question

I have millions of data points which each go through the same mathematical operations, and they do not depend on each other. Hence, this problem should in theory be vectorizable.

Now these data points would most conveniently be stored as a linked-list in Fortran so delete/add is straight-forward. The main loop would then be something like

do while(associated(data_points)) 

     data_points => data_points% next
       ......
enddo 

How does this work with vectorization?

Another option would be to store all variables in an organised declared type and allocate an array of that type equal to the number of data points, something like:

type(type_data_points) :: data_points(1:no_data_types)

and then the do-loop would just be

do i = 1, no_data_types 
    data_points(i)% x = (...) 
    data_points(i)% y = (...) 
     ....
enddo

Would even the latter be vectorized - and what options do I have beside defining each variable (x,y, ...) as arrays of no_data_points and carry out the calculations.

Answer 1

Apart from what you've already mentioned in the question, the following options can be considered:

1. deallocate and allocate an array every time a datapoint is added or deleted.

2. Declaring an array which is much larger than the expected data and track how many datapoints have been added. Then you can perform the math on the sliced array itself. This is expected to give very good performance. If you hit a point where you need a larger array, you may have to deallocate and allocate the array again. This requires fewer allocations than before thus is a cleaner option.

3. A non-standard language extension as suggested here.

The linked list data structure you have is also ok but due considerations is to be made when parallelising with MPI. Communication with arrays is far more efficient and also convenient. Since the data is independent and you intend to perform operations independently I presume you also need all data gathered again. In the linked list case, you may have to first collect all data to communicate in a buffer and then send/receive/allgather. However, if it is already structured in an array this is far more easier.