Access violation during compilation

FTN95 aborts with an access violation (attempting to read from location 0000000C) when asked to compile the following simplified version of John Campbell's adaptation of Arjen Markus's quicksort in a recent thread, please see https://forums.silverfrost.com/Forum/Topic/3814 . The access violation occurs whether or not the /64 option is specified.

module qsort_m
contains
 subroutine test_sort (N)
   integer N
   integer, allocatable :: ia(:), ia_sort(:)
   real, allocatable :: aa(:)
!
    allocate ( aa(N), ia(N), ia_sort(N) )
    call random_number (aa)
    ia = nint(aa*1023.0)
    deallocate(aa)
    print 10,n, ia
!
    ia_sort = qsort_int ( ia )
    print 10,n,ia_sort
 10 format(1x,i3,(4x,10I6))
!
 end subroutine test_sort

 recursive function qsort_int ( data ) result ( sorted )
    integer, dimension(:), intent(in) :: data
    integer, dimension(1:size(data))  :: sorted

    if ( size(data) > 1 ) then
        sorted = (/ qsort_int(pack(data(2:), data(2:) <  data(1))), &
                                pack(data(1:), data(1:) == data(1)),  &
                    qsort_int(pack(data(2:), data(2:) >  data(1))) /)
    else
        sorted = data
    endif
  end function qsort_int
 end module
 
  Program test_sort_int
  use qsort_m
   integer n

    N = 5
    call test_sort(N)

 end Program test_sort_int

Here is a second version of the program, with the sorting algorithm slightly changed to preserve the order of items that match the pivot element.

module qsort_m
    implicit none
 contains
  recursive function qsort_int ( data ) result ( sorted )
    integer, dimension(:), intent(in) :: data
    integer, dimension(1:size(data))  :: sorted
    integer ilt, ieq, igt

    if ( size(data) > 1 ) then
        ilt = count(data < data(1))
        if(ilt > 0)then
           sorted(1:ilt) = pack( data, data < data(1) )
           if(ilt > 1)sorted(1:ilt) = qsort_int(sorted(1:ilt))
        endif
        ieq = count(data == data(1))
        if(ieq > 0)then
           sorted(ilt+1:ilt+ieq) = pack( data, data == data(1) )
        endif
        igt = count(data > data(1))
        if(igt > 0)then
           sorted(ilt+ieq+1:) = pack(data,data > data(1))
           if(igt > 1)sorted(ilt+ieq+1:) = qsort_int(sorted(ilt+ieq+1:))
        endif
    endif
  end function qsort_int

end module qsort_m

Program test_sort_int
   use qsort_m
   integer n
   integer, allocatable :: aa(:), aa_sort(:)
!
   N = 5
   allocate ( aa(N), aa_sort(N) )
   aa = (/ 204, 158, 835, 774, 932 /)
   write (*,10) aa

   aa_sort = qsort_int ( aa )

   write (*,10) aa_sort
10 format(1x,5I10)
!
 end program test_sort_int

With other compilers, I get the expected output

158       204       774       835       932

With FTN95 (32-bit) this program starts running but aborts with Stack Overflow. Compiled with /64, the program aborts with Access Violation. Compiled with /check, the 32-bit program runs to completion but the output is

   56687580  56687580  56687580  56687580  56687580

With /check /64, the program aborts, saying this about Line-6:

Attempt to call a routine with an incorrect or missing INTERFACE regarding argument number one, which needs to be declared as assumed-shape in both the caller and callee at address ...

Thank you for the feedback. I have logged both of these issues.

The second version will now run when using the next release of FTN95.

The first version remains outstanding.

Regarding the first program and qsort_int, a number of FTN95 issues connected with this program have now been fixed.

Unfortunately FTN95 has a major issue when it comes to recursive functions that are called within an array constructor so for the time being it has proved necessary to simply flag this as a known limitation of FTN95.

As it happens, this algorithm, although very clever, does not appear to present an efficient way of sorting. You will see that it uses array sections that are passed to PACK which is a function returning an array of varying size. The result is passed to qsort_int which also returns an array of varying size (as well as being recursive); all of this is within an array constructor.

As it happens, this algorithm, although very clever, does not appear to present an efficient way of sorting.

I agree completely; it would, however, be worthwhile to know how inefficient it is. For arrays of size less than 100, say, with elements of a user-defined type with diverse components, it may be worth using simply because it is so readable.

Quoted from mecej4 I agree completely; it would, however, be worthwhile to know how inefficient it is.

Well I have done some testing using gFortran with options -g -fimplicit-none -Wall -O3 -march=native -fopenmp and for a number of variations of mecej4's variation on Arjen Markus' concise code.

Using FTN95 /64, it compiles but crashes at 'real, dimension(1:size(data)) :: sorted'

The results are 'surprising' in that mecej4's code is quite fast, and performs better that my quick sort for N = 2^27. I say 'surprising' based on the sort uses both COUNT and PACK 3 times, so does a 6x scan of the data array. ( not surprising that mecej4's code is fast )

I have tested a number of variations of the quick sort:

1. Markus' original sort : this has recursion within an array generation, so is very memory hungry, (although I didn't get a stack overflow ?) (pivot selection poor for sorted data)
2. Mecej4's sort, divides the 2 recursive sub-sorts to seperate statements, which would have a less complex memory allocation, but still uses a lot of temporary memory (heap rather than stack ?).
3. Modified pivot selection : uses median of 3 : first:middle:last to select a better pivot, although this only offers a slight improvement.
4. My indexed quick sort, which uses a bubble sort when the array size < 9. This is much faster for small sorts (5.8x N= 1024, 3.7x N= 1M (2^{20), 2.0x N=16M, but 0.93x for N=2}27), so I stoped there ) My sort returns an order index and maintains duplicate order.
5. An improved version of mecej4's sort that uses only 2 x COUNT + PACK, avoiding DATA=pivot and also introduces small bubble sorts for 15% improvement.

Note: these tests are for a list of real*4 random numbers, so doesn't test some extreme cases (eg ordered, reverse order, lots or repetition)

So the use of COUNT and PACK for quick sort does have some advantages. Although a duplicated search, it could be that PACK and COUNT have been optimised.

Paul, It would be good to get FTN95 able to compile (assuming it is not a bug or F03+ code)

    recursive function mecej4_qsort_reals ( data ) result ( sorted )
!
!  real version of mecej4's qsort_int
!    we assume ilt+ieq+igt == size(data)
!    we need ilt or igt < size(data)
!
      real, dimension(:), intent(in) :: data
      real, dimension(1:size(data))  :: sorted
      integer ilt, ieq, igt, n

I have created a dropbox link to my test program and a batch file (make_run) to rebuild the test using gFortran.

The program updates a file 'markus_sort.txt' with timing results. I did the tests on an i5-2300 and i7-8700K up to N = 2^27 (make sure you have enough memory for the temporary heap arrays)

https://www.dropbox.com/s/qblccz5z253u8wc/test_mecej4_sort.zip?dl=0

I have found my hybrid quick sort to be a robust sort for n = 2^{1 to 2}30 in size. My quick sort has replaced recursion with a pairs stack array, which should be of size k > log(N)/log(2), so very small.

As mecej4, has pointed out, PACK needs COUNT to be used effectively. It works very well for this sort.

Please let me know if have different findings.

John

John

Which program is it that you want FTN95 compile? Maybe you can post it again so that I can be clear.

Paul,

I did the gFortran tests using Markus_sort_test.f90 with 'logical :: test_markus = .true.'. (line 19)

I changed to 'logical :: test_markus = .false.' for the FTN95 test, as I thought the recursive function marcus_qsort_reals was the only routine that used F03+ array allocation.

I thought all other routines were F95 compatible, including COUNT, PACK and the recursive function mecej4_qsort_reals. I compiled with : ftn95 Markus_sort_test.f90 /64 /debug /link Then ran with : sdbg64 Markus_sort_test.exe

This failed on line 70 when running in sdbg64 at : real, dimension(1:size(data)) :: sorted I didn't investigate further, but assumed it was a FTN95 problem.

I didn't try 32-bit, although now shows a similar [problem on entry to mecej4_qsort_reals. The declarations of data and sorted are reporting problems. real, dimension(1:size(data)) :: sorted

I am not sure if this is supported in F95 or later, although shouldn't it be available for vector functions.

John

John

For the time being FTN95 cannot handle functions that return a varying sized array when they are called from within an array constructor. (I mentioned the recursive attribute above - it might be either or both).

I don't think that there is a simple way to modify the program so that it avoids this construction. If you try to make the call before the array constructor assignment then the resulting temporary array assignment will have an unknown size.

Paul,

My understanding is that the only array constructor is in function marcus_qsort_reals. This routine is not called in the FTN95 test.

Does the function mecej4_qsort_reals use an 'array constructor' ? It does return a varying sized array, being the same size as the supplied array. Is that not supported ? I presume if this is the case, this would be a significant change to FTN95 functionality.

John

John

Can you either post the code for the test or provide a link? I can't work out which program you are referring to.

John-Silver

If you mean the last program in that thread then that is essentially the same as the one at the beginning of this thread and it is the subject of my comments above.

Just to summarise, the issue in this thread is still unresolved and is proving to be exceedingly difficult to fix.

Paul,

I have created a new mecej4_sort_test.f90 file (see link below)

https://www.dropbox.com/s/lprhgto6izz1m78/mecej4_sort.zip?dl=0

In this file I have removed the makus_sort, which had the complex array generation, but retained the declaration 'real, dimension(1:size(data)) :: sorted' in other routines.

This compiles with ftn95 Mecej4_sort_test /64 /debug /link, but crashes when run. It would be good to know if FTN95 can support this code. The use of 'real, dimension(1:size(data)) :: sorted' is necessary for vector functions of variable array size, unless there is an alternative ? perhaps use a subroutine.

Regarding the quick sort examples: For those interested in the sort performance, I have replaced my indexed quick_sort in the previous linked example with a direct quick sort. This appears to be about 3x faster than the recursive quick sort approach.

I use an indexed sort in most of my work, as returning an index to the order is in practice much more useful and does not modify the original data. In other routines, I have removed the use of COUNT and PACK for DATA==pivot, as iEQ = size(data) - iLT - iGT. (if a bad pivot is selected where iEQ = 0 and iGT or iLT = 0, this will generate an endless loop, so pivot should be an element of DATA) It is surprising that using both COUNT and PACK twice in the mecej4 sort still appears to provide an acceptable performance.

The other aspects of the quick sort that I have addressed in these examples are:

choice of an alternative pivot: I use median of 3, although other options could give a better choice. Choosing the first is not good, especially for an ordered set. use of a bubble sort when the sort data gets small : although bubble (or insertion) are O(N^2) they are much faster for small N.

The Markus sort and Mecej4's adaptation are certainly an interesting use of array functions to produce concise sort code.

I have found my quick sort approach to be robust for most data sets, including the extremes of ordered, reverse order or with multiple data repeats. I would certainly be interested if others have better suggestions.

John Campbell

I get the same failure when I run the code from your link.

I have added it to the list. At the moment I don't know how difficult it will be to fix.

Here is an update on the original issue at the start of this thread.

The following code presents a modified version of qsort_int that runs correctly on my machine (i.e. using the current developers' version).

It illustrates the essence of what the compiler has to do on behalf of programmers when they call a function (that returns an array) from within an array constructor.

tmp1, tmp2 and tmp3 represent temporary arrays that the compiler must create in addition to those already provided to handle the PACK routine. Internal code must also be provided that allows the returned size (of the result of PACK) to be zero.

 recursive function qsort_int (data) result(sorted)
    integer, dimension(:), intent(in) :: data
    integer, dimension(1:size(data))  :: sorted
    integer, dimension(1:size(data))  :: tmp1,tmp2,tmp3
    integer isize1,isize2,isize3
    isize1 = count(data(2:) <  data(1))
    if(isize1 > 0) tmp1 = qsort_int(pack(data(2:), data(2:) <  data(1)))
    isize2 = count(data(1:) == data(1))
    tmp2 = pack(data(1:), data(1:) == data(1))
    isize3 = count(data(2:) >  data(1))
    if(isize3 > 0) tmp3 = qsort_int(pack(data(2:), data(2:) >  data(1)))
    if ( size(data) > 1 ) then
        sorted = (/ tmp1(1:isize1), tmp2(1:isize2), tmp3(1:isize3) /)
    else
        sorted = data
    endif
  end function qsort_int

Paul,

Thanks for the change, although it does not run on my version of FTN95.

I am not sure where the restrictions are that required your changes. Would be good to better understand the limitations.

Could the following change work with your version of FTN95 ?

 recursive function qsort_int (data) result(sorted)
    integer, dimension(:), intent(in) :: data
    integer, dimension(1:size(data))  :: sorted
    integer, dimension(1:size(data))  :: tmp1
    integer ilt,ieq,igt
!
    if ( size(data) > 1 ) then
        ilt = count(data(2:) <  data(1))
        if (ilt > 0) tmp1(1:ilt) = qsort_int(pack(data(2:), data(2:) <  data(1)))
        igt = count(data(2:) >  data(1))
        ieq = size(data) - ilt - igt
        if (igt > 0) tmp1(ilt+ieq+1:) = qsort_int(pack(data(2:), data(2:) >  data(1)))
        tmp1(ilt+1:ilt+ieq) = data(1)
!
        sorted = tmp1
    else
        sorted = data
    endif
  end function qsort_int

John

At the moment FTN95 can't parse code that calls a function from within an array constructor where the function returns a varying sized array.

This is not an exact description. The function qsort_int contains calls to a function of a function (i.e. PACK) and is also recursive.

PACK returns a varying sized array whilst qsort_int returns a fixed sized array.

At compiler level, PACK has a number of obvious arguments but also passes a temporary array that is the same size as the array to be packed. PACK fills the destination array and also returns the number of elements filled.

When PACK is called as an argument in another function call, the temporary array for PACK can be passed on to the calling function together with the information about the current value of its varying size.

Also, for a simple assignment ARRAY = PACK(...), the compiler can use ARRAY as the destination rather than create a temporary array. This means that the calls to COUNT in my code above become redundant when everything is done internally.

Paul,

Does the following variation address your comment, or is it worse ? recursive function qsort_int (data) result(sorted) integer, dimension(:), intent(in) :: data integer, dimension(1:size(data)) :: sorted integer, dimension(1:size(data)) :: tmp1 integer ilt,ieq,igt ! if ( size(data) > 1 ) then ilt = count (data(2:) < data(1) ) if (ilt > 0) then tmp1 = pack (data(2:), data(2:) < data(1) ) sorted(1:ilt) = qsort_int ( tmp1(1:ilt) ) end if igt = count (data(2:) > data(1)) ieq = size(data) - ilt - igt sorted(ilt+1:ilt+ieq) = data(1) if (igt > 0) then tmp1 = pack (data(2:), data(2:) > data(1) ) sorted(ilt+ieq+1:) = qsort_int( tmp1(1:igt) ) end if ! else sorted = data endif end function qsort_int

Is FTN95 Ver 8.65 the compiler you are using ?

John

I prefer not to get into a discussion about alternatives at the moment. There is still the possibility that the primary issue might be resolved.

I am using the developers' version of FTN95 that is post v8.65.