Is there a better name for «moving array elements»?

Brad Richardson’s most recent Fortran beginners class includes an array operation which I was not aware, nor found a better name than «moving array elements». Is there a better, i.e. well-recognized name for this?

There is an array like one in depicted in the top line with seven elements:

The operation defines a slice (blue box) which overwrite en bloc the elements prior to this. As a result (second line), the particular block starts earlier. On the other hand, I speculate it might not be called a move per se because it isn’t a shift leaving a gap as the slot on array(5) isn’t vacated (elements array(6:7) aren’t affected anyway).

The underlying minimal working example used here:

program update
   implicit none

   integer :: i, start_point, end_point
   integer :: testarray(7)

   start_point = 1
   end_point = 4

! explicitly populate array with non-zero data
   do i = 1, 7
      testarray(i) = 2*i
   end do
   print *, testarray

! the operation
   do i = start_point, end_point
      testarray(i) = testarray(i + 1)
   end do
   print *, testarray

end program update

The operation you describe is a bit specific. It seems similar to Circular Shift which applies to the whole array.
In NumPy, there is a function named numpy.roll() function that does this.

1 Like

I hadn’t thought about this as a common pattern, let alone whether it had a name. Interesting. I’ll note though that you can actually accomplish it in a single line like

testarray(start_point:end_point) = testarray(start_point+1:end_point+1)
2 Likes

Where testarray is an object of intrinsic type, the above generally works well with current processors.

But with testarray as derived types with various levels of object composition and/or inheritance, the one-liner can prove extremely expensive unless the author(s) have taken tremendous care to achieve the equivalent of what other languages such as C++ offer conveniently as move semantics.

1 Like

If I understand correctly, eoshift is another way to do this.

x(i:j) = eoshift(x(i:j), 1, x(j))
3 Likes

You mean the following with respect to the depiction in the original post?

x(i:j) = eoshift(x(i:j), 1, x(j+1))
1 Like

I would avoid terms such as circular shift or rotate left because they both imply that the numbers are preserved, which is clearly not the case here (first element is destroyed in this example, and fifth element is duplicated.) I also think the term rolling left is misleading.
Such an operation reminds Assembly but, at least for the CPUs I know Assembly, there is no equivalent instruction. All “shift” and “rotate” operations are non-destructive, in the sense elements are somehow preserved - either by cycling all the elements or by using an external register to store the element that is lost. There is no instruction such as this, destroying one element and duplicating another one.
So I am not aware of a proper name for this, but if I had to pick one, I would call it partial left shift. As others already pointed out, this is a one-liner for Fortran 90 or above; there is no need for a do-loop.

1 Like

The example Wikipedia’s article uses to illustrate the circular shift on an array (A, B, C, D) is the sequence

A, B, C, D
D, A, B, C
C, D, A, B
B, C, D, A

Processing this line by line, the result is like the truncation of the last element of the array so that it is prepended to the remainder of the array (in a way, recycled).

This pattern however does not match my observation applying Brad’s instruction. Thus (including the input provided by subsequent answers and their ramifications) move now appears to me as acceptable description about the result shown in the figure. On the other hand, cyclic shift (because of cycle) does not.

I speculate the bit derived from your class (and now this one) are examples of an elegant transformation for what the execution requires only few instructions in the source code (e.g., no do loop, as @Pap hints). And without background in computer science, past the aha moment of first encounter, a pattern one likely does not forget / “unsee” soon.

There are (much deeper than I anticipated) insights about move semantics in dedicated answers on stackoverflow. Though addressing C++, one of the take home messages for me is move in move elements of the original question likely is an acceptable description.

Based on the example on Fortran wiki, I modified my MWE to include your suggestion:

program update
   implicit none

   integer :: i, start_point, end_point
   integer :: testarray(7)

   start_point = 1
   end_point = 4

! explicitly populate array with non-zero data
   do i = 1, 7
      testarray(i) = 2*i
   end do
   print *, testarray

!! the operation
!   do i = start_point, end_point
!      testarray(i) = testarray(i + 1)
!   end do

! suggestion nshaffer:
! x(i:j) = eoshift(x(i:j), 1, x(j))
   testarray(start_point:end_point) = eoshift(testarray(start_point:end_point), 1, testarray(end_point))
   print *, testarray

end program update

which indeed, as correctly spot by @FortranFan, is off by one compared to the result shown in the original question.

Here it becomes puzzling for me. Adjusting my initial MWE to accommodate your suggestion, i.e.

program update
   implicit none

   integer :: i, start_point, end_point
   integer :: testarray(7)

   start_point = 1
   end_point = 4

! explicitly populate array with non-zero data
   do i = 1, 7
      testarray(i) = 2*i
   end do
   print *, testarray

!! the operation
!   do i = start_point, end_point
!      testarray(i) = testarray(i + 1)
!   end do

!! suggestion natshaffer:
!! x(i:j) = eoshift(x(i:j), 1, x(j))
!   testarray(start_point:end_point) = eoshift(testarray(start_point:end_point), 1, testarray(end_point))
!   print *, testarray

! suggestion fortranfan
! x(i:j) = eoshift(x(i:j), 1, x(j + 1))
   testarray(start_point:end_point) = eoshift(testarray(start_point:end_point), 1, testarray(end_point + 1))
   print *, testarray

end program update

yields a result matching my observation in the original post.

With what I learned by now, I agree shift is succinct, brief, acceptable.

@nbehrnd, are you sure about “the result matches the one based on @nshaffer suggestion”?

A rather terse case with Intel oneAPI behaves as I implied above:

   integer :: x(7), y(7)
   x = [( i, integer :: i=2,14,2 )] ; y = x
   print *, "Initially, x = ", x
   print *, "Initially, y = ", y
   x(1:4) = eoshift( x(1:4), 1, x(5) )
   y(1:4) = eoshift( y(1:4), 1, y(4) )
   print *, 'Following EOSHIFT with "x(j+1)" as boundary, x = ', x
   print *, 'Following EOSHIFT with x(j) as boundary, y = ', y
end
C:\temp>ifort /standard-semantics p.f90
Intel(R) Fortran Intel(R) 64 Compiler Classic for applications running on Intel(R) 64, Version 2021.6.0 Build 20220226_000000
Copyright (C) 1985-2022 Intel Corporation.  All rights reserved.

Microsoft (R) Incremental Linker Version 14.30.30706.0
Copyright (C) Microsoft Corporation.  All rights reserved.

-out:p.exe
-subsystem:console
p.obj

C:\temp>p.exe
 Initially, x =  2 4 6 8 10 12 14
 Initially, y =  2 4 6 8 10 12 14
 Following EOSHIFT with "x(j+1)" as boundary, x =  4 6 8 10 10 12 14
 Following EOSHIFT with "x(j)" as boundary, y =  4 6 8 8 10 12 14
1 Like

Thank you very much @FortranFan for pointing this out; I re-run each individually and compared the results. gfortran can only assist in spotting some, but can’t warn against all errors possible.