|
forums.silverfrost.com Welcome to the Silverfrost forums
|
View previous topic :: View next topic |
Author |
Message |
mecej4
Joined: 31 Oct 2006 Posts: 1886
|
Posted: Mon Aug 10, 2020 1:12 am Post subject: 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 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 |
|
|
mecej4
Joined: 31 Oct 2006 Posts: 1886
|
Posted: Mon Aug 10, 2020 2:44 am Post subject: |
|
|
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 |
|
|
PaulLaidler Site Admin
Joined: 21 Feb 2005 Posts: 7925 Location: Salford, UK
|
Posted: Mon Aug 10, 2020 8:30 am Post subject: |
|
|
Thank you for the feedback. I have logged both of these issues. |
|
Back to top |
|
|
PaulLaidler Site Admin
Joined: 21 Feb 2005 Posts: 7925 Location: Salford, UK
|
Posted: Tue Aug 18, 2020 11:58 am Post subject: |
|
|
The second version will now run when using the next release of FTN95.
The first version remains outstanding. |
|
Back to top |
|
|
PaulLaidler Site Admin
Joined: 21 Feb 2005 Posts: 7925 Location: Salford, UK
|
Posted: Thu Sep 24, 2020 3:20 pm Post subject: |
|
|
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 |
|
|
mecej4
Joined: 31 Oct 2006 Posts: 1886
|
Posted: Thu Sep 24, 2020 6:00 pm Post subject: |
|
|
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 |
|
|
JohnCampbell
Joined: 16 Feb 2006 Posts: 2554 Location: Sydney
|
Posted: Sun Sep 27, 2020 11:04 am Post subject: Re: |
|
|
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 |
|
|
PaulLaidler Site Admin
Joined: 21 Feb 2005 Posts: 7925 Location: Salford, UK
|
Posted: Sun Sep 27, 2020 12:09 pm Post subject: |
|
|
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 |
|
|
JohnCampbell
Joined: 16 Feb 2006 Posts: 2554 Location: Sydney
|
Posted: Sun Sep 27, 2020 2:31 pm Post subject: |
|
|
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 |
|
|
PaulLaidler Site Admin
Joined: 21 Feb 2005 Posts: 7925 Location: Salford, UK
|
Posted: Sun Sep 27, 2020 3:24 pm Post subject: |
|
|
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 |
|
|
JohnCampbell
Joined: 16 Feb 2006 Posts: 2554 Location: Sydney
|
Posted: Sun Sep 27, 2020 3:59 pm Post subject: |
|
|
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 |
|
|
PaulLaidler Site Admin
Joined: 21 Feb 2005 Posts: 7925 Location: Salford, UK
|
Posted: Sun Sep 27, 2020 4:56 pm Post subject: |
|
|
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 |
|
|
John-Silver
Joined: 30 Jul 2013 Posts: 1520 Location: Aerospace Valley
|
Posted: Mon Sep 28, 2020 9:30 pm Post subject: |
|
|
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 ... " |
|
Back to top |
|
|
PaulLaidler Site Admin
Joined: 21 Feb 2005 Posts: 7925 Location: Salford, UK
|
Posted: Tue Sep 29, 2020 7:23 am Post subject: |
|
|
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 |
|
|
JohnCampbell
Joined: 16 Feb 2006 Posts: 2554 Location: Sydney
|
Posted: Tue Sep 29, 2020 8:52 am Post subject: |
|
|
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 |
|
|
|
|
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
|