Remove element of array

[BEAGHTON__PJ]

I am dealing with millions of sequential repetitions of the removal of the N-th element from 1D dynamic array that has been allocated size M(>=N) before the removal of the element (the integers N and M change before each repetition of the array element removal). The syntax I use is:

 A=[A(:N-1),A(N+1:)]

This removes the Nth element and changes the size of the real*8 array A from M to M-1. This step is revisited again and again millions of times as it is part of a DO loop with other operations taking place before and after this step (which may also change M).

I also tried another syntax:

A(N)=999.
A=PACK(A,A.ne.999.)

(the elements of my array are all different from 999. to start with so the PACK with the MASK removes the modified N-th element and shrinks the size of the array by 1).

Both methods are simply too slow when you have to repeat the step sequentially millions of times. My array size M is typically between 100000 and 1000000.

Can anybody suggest an alternative method that is faster? I compile using -O3 optimisation although it makes no real difference. Is there anything in the MKL library that could be of use?

[mecej4]

The old fashioned way of handling this is to allocate the array (either statically or dynamically) just once, to the maximum size expected. From then on, the active portion of the array will only shrink (if your description is complete), and the inactive portion is memory that is idle -- wasted, perhaps, but do you care much today about wasted memory? This way, you skip the overhead from loading the memory manager with millions of resizing requests.

An alternative would be to use a different data structure, such as a linked list, instead of an array.

[BEAGHTON__PJ]

Thanks mecej4. The code is used to simulate individual insects in a 3-D domain. The array A contains (X, Y or Z) coordinates of insects that are born, die or move at a given time-step (and there is do-loop with millions of time steps) so the size of A can increase in a given time step (via newly-born insects), decrease (via death, as described above) or maintain its size but have some or all of its elements change value due to movement. Your suggestion of an array with max size that shrinks over time would work if the births of new insects did not add to the size of the array in some of the time steps.

Given my explanation above, do you still think that linked lists may be a suitable alternative?

[mecej4]

Are you using an array to represent an unordered set? Do the insects interact, or does each come into existence, live and die independently?

You can cover the increase in population by allocating the array to be larger than the maximum expected population -- say, twice the estimated size, with a check for overflow. Of course, if your model allows explosive grown/infestation, that idea would not work well.

Before choosing a linked list or some other data structure, you need to cogitate and list the types of operations that you will need to do with the data. Related question: singly linked list or doubly linked list?

[FortranFan]

@BEAGHTON, PJ,

Please see this thread: https://software.intel.com/en-us/forums/intel-visual-fortran-compiler-for-windows/topic/701985

As you see in the above thread, resizing arrays can prove costly as you have found, particularly with large arrays.  One inevitably has to develop some 'custom' design to suit one's needs and actively manage the 'data' during execution.  Linked lists are an option but simulations may then suffer from critical 'data' not being in CONTIGUOUS memory.  Computational analysis of one's code and simulation then becomes rather important.

[jimdempseyatthecove]

Apparently because you are in effect squishing out dead insects, the position (or relative positions) in the array is immaterial. Therefore

(re)Allocate only when array needs to grow
keep count of number of used elements: Array(1:nInsects) as apposed to Array without range.

For deletion, move the last live insect to overstrike the dead one (if dead one not last) then decrement the count of insects.

Jim Dempsey