forums.silverfrost.com Forum Index forums.silverfrost.com
Welcome to the Silverfrost forums
 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister 
 ProfileProfile   Log in to check your private messagesLog in to check your private messages   Log inLog in 

Access violation during compilation
Goto page 1, 2, 3  Next
 
Post new topic   Reply to topic    forums.silverfrost.com Forum Index -> Support
View previous topic :: View next topic  
Author Message
mecej4



Joined: 31 Oct 2006
Posts: 1430

PostPosted: Mon Aug 10, 2020 1:12 am    Post subject: Access violation during compilation Reply with quote

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 http://forums.silverfrost.com/viewtopic.php?t=4280 . The access violation occurs whether or not the /64 option is specified.

Code:
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
Back to top
View user's profile Send private message
mecej4



Joined: 31 Oct 2006
Posts: 1430

PostPosted: Mon Aug 10, 2020 2:44 am    Post subject: Reply with quote

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.

Code:
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

Code:
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

Code:
   56687580  56687580  56687580  56687580  56687580


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

Code:
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 ...
Back to top
View user's profile Send private message
PaulLaidler
Site Admin


Joined: 21 Feb 2005
Posts: 6609
Location: Salford, UK

PostPosted: Mon Aug 10, 2020 8:30 am    Post subject: Reply with quote

Thank you for the feedback. I have logged both of these issues.
Back to top
View user's profile Send private message AIM Address
PaulLaidler
Site Admin


Joined: 21 Feb 2005
Posts: 6609
Location: Salford, UK

PostPosted: Tue Aug 18, 2020 11:58 am    Post subject: Reply with quote

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

The first version remains outstanding.
Back to top
View user's profile Send private message AIM Address
PaulLaidler
Site Admin


Joined: 21 Feb 2005
Posts: 6609
Location: Salford, UK

PostPosted: Thu Sep 24, 2020 3:20 pm    Post subject: Reply with quote

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.
Back to top
View user's profile Send private message AIM Address
mecej4



Joined: 31 Oct 2006
Posts: 1430

PostPosted: Thu Sep 24, 2020 6:00 pm    Post subject: Reply with quote

Quote:
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.
Back to top
View user's profile Send private message
JohnCampbell



Joined: 16 Feb 2006
Posts: 2241
Location: Sydney

PostPosted: Sun Sep 27, 2020 11:04 am    Post subject: Re: Reply with quote

mecej4 wrote:
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)
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
Back to top
View user's profile Send private message
PaulLaidler
Site Admin


Joined: 21 Feb 2005
Posts: 6609
Location: Salford, UK

PostPosted: Sun Sep 27, 2020 12:09 pm    Post subject: Reply with quote

John

Which program is it that you want FTN95 compile? Maybe you can post it again so that I can be clear.
Back to top
View user's profile Send private message AIM Address
JohnCampbell



Joined: 16 Feb 2006
Posts: 2241
Location: Sydney

PostPosted: Sun Sep 27, 2020 2:31 pm    Post subject: Reply with quote

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
Back to top
View user's profile Send private message
PaulLaidler
Site Admin


Joined: 21 Feb 2005
Posts: 6609
Location: Salford, UK

PostPosted: Sun Sep 27, 2020 3:24 pm    Post subject: Reply with quote

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.
Back to top
View user's profile Send private message AIM Address
JohnCampbell



Joined: 16 Feb 2006
Posts: 2241
Location: Sydney

PostPosted: Sun Sep 27, 2020 3:59 pm    Post subject: Reply with quote

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
Back to top
View user's profile Send private message
PaulLaidler
Site Admin


Joined: 21 Feb 2005
Posts: 6609
Location: Salford, UK

PostPosted: Sun Sep 27, 2020 4:56 pm    Post subject: Reply with quote

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.
Back to top
View user's profile Send private message AIM Address
John-Silver



Joined: 30 Jul 2013
Posts: 1451
Location: Aerospace Valley

PostPosted: Mon Sep 28, 2020 9:30 pm    Post subject: Reply with quote

Paul, the Markus code can be found here:
http://forums.silverfrost.com/viewtopic.php?t=4280&postdays=0&postorder=asc&start=0
(last post on p.1, Aug 1st 2020))
_________________
''Computers (HAL and MARVIN excepted) are incredibly rigid. They question nothing. Especially input data.Human beings are incredibly trusting of computers and don't check input data. Together cocking up even the simplest calculation ... Smile "
Back to top
View user's profile Send private message
PaulLaidler
Site Admin


Joined: 21 Feb 2005
Posts: 6609
Location: Salford, UK

PostPosted: Tue Sep 29, 2020 7:23 am    Post subject: Reply with quote

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.
Back to top
View user's profile Send private message AIM Address
JohnCampbell



Joined: 16 Feb 2006
Posts: 2241
Location: Sydney

PostPosted: Tue Sep 29, 2020 8:52 am    Post subject: Reply with quote

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.
Back to top
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic    forums.silverfrost.com Forum Index -> Support All times are GMT + 1 Hour
Goto page 1, 2, 3  Next
Page 1 of 3

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum


Powered by phpBB © 2001, 2005 phpBB Group