changing the stack at runtime?

Steve,

Before looking for a faster sort, I would be interested to know:

1. how long it takes to read the 85m timestamps and convert them to 'microseconds within the current day'.
2. Then you can sort them.
3. Then what do you do with them ?

My interpretation of the sort problem description shows that for the timestamps, how close they are to ordered could influence which sort to choose, although quick_sort is usually a safe choice.

This is an interesting complimentary problem to the earlier forum post about file reading speeds, as it is important to know what the total processing time is and where to target effort for improved performance.

Look forward to hearing how the project evolves.

Hi John - sorry for much delayed reply. The Portugal robot trials finished. Some big problems with the robots which the engineers are hurriedly fixing before next trials in the uk during May. But I tracked down my own problem which was nothing to do with memory but was a basic array allocation error. I found that one of the allocatable arrays was getting a zero dimension passed to it. Instead of failing at the time of allocation it was blowing up when I tried to use it.

Reading and converting the 85m 19-digit timestamps is actually very fast. I didn't time it, but it was only a few seconds. The timestamps on inut were held as a string, and data was extracted from them using a simple formatted read. Not just the microseconds within the day but also the conventional date and time (as strings). These data are points extracted (within the robot) from laser stripes produced by a structured-light system, and almost but not entirely in timestamp order.

They they need to be joined with navigation data (which thankfully are in timestamp order) which can be used to convert the points from robot coordinates to absolute 'world' coordinates, using a standard quaternion transformation.

Hi Steve,

I have improved my sort testing and reporting, producing some charts of speed vs sample size for degree of randomness (based on max out of position bandwidth) These results basically show that adapted bubble (2.1 sec) and insert (1.2 sec) sorts can work very well for data that is near ordered (max bandwidth of < 16) while quick is 2.6 sec for 85m. For random data, quick sort is the most reliable (18 sec for 85m) while bubble is 1,000 sec for only 850k and insert is 250 sec for 850k sample size. However, I find that quick sort is by far the best. There have been reports that quick sort does not work well for some initial ordered states (ordered or reverse ordered) but the sort I have does not show this problem. The use of multi-threading for sorting is an interesting approach, but might only be necessary for projects requiring unusually fast times.

What would be good to see is some comparative time of the stages of the processing (assuming it is staged), as there has been a lot of comment in this forum on the speed of some stages, especially disk reading and writing of large files. I have always pushed the idea that this performance should be seen in the context of all stages of the processing. I could suggest you may have the following stages:

• Obtain data from the recording device and store on local disk
• Read data into memory
• obtain a time stamp for each record
• generate a sorted index for the data records
• process these records
• write processed data for future review

Whatever the stages, it would be good to know if reading data at 200 megabytes per second (rather than say 1+ gigabytes/second) would have a significant impact on the total analysis task.

For the marine surveys I have analysed in the past (data sets about a gigabyte), I have found that step 1, combined with step 1a: review/filter/correct the data for errors and estimate a range of sensible values is by far the most time consuming stage. (this could take hours > days > weeks, such as when the survey datum surface had to redefined; mean sea level is not a flat surface !)

Then again, I could imagine that when processing a continuous feed of digital data that the slowest stage is going to be critical, although I have not worked in a field where high speed data supply occurs (radio astronomy?)

It would be good to see some real performance measures and understand the relative performance requirements for sorting, reading and processing.

John

(link to test results shortly) Sorry for delay in posting. The linked .zip file includes the sort test .f90 code, batch file to run, .xls file of imported results and a .doc file which has charts and some description of results. To comment on mecej4's comments below: The latest tests includes two types of insertion sorts; binary search and reverse linear search which is good for very ordered data. Neither are good for random data. The quick sort coded includes a bubble or a linear insert sort when sort packet size < 18. This improves speed by about 10% for the small increase in complexity. I hope these results give some context to the comments.

https://www.dropbox.com/s/oae3tcpq29tdic4/sort_test2.zip?dl=0

Hi John - We are finding that by far the slowest part of our processing is the data acquisition - transfer from the robot or from a central server. We are now using USB3.1 and a 2-terabyte SSD which is a lot faster than the external hard drives that are our main archival storage medium, and using a hard-wired ethernet link to the submersible instead of the wifi we had used earlier. Data volumes per bag-file are typically in the tens of gigabytes. The next slowest part of the operation is extracting data from the ROS bag files. Rather than relying on the robot engineers to do this for us, we now use VirtualBox and our own python scripts to extract CSV files and PNG images. It's only when we get to see the data in an intelligible format that the Fortran processing comes into play - and is relatively fast. Following your comments I might well replace our shell-sort by quick-sort: will do some time tests, but it's already apparent that this is far from the slowest part of the process.

The Fortran step includes import of pixel-by-pixel data from multispectral images. I then pass the data on to our 3d modelling whiz-kid who projects the multispectral data on to the point cloud (he does everything in C++ of course because they don't teach Fortran in universities any more). We haven't yet got to do that stage though, because of a number of practical (engineering) problems in getting a reliable point cloud.

Quoted from JohnCampbell I have done some testing of 85 million values on 2.8ghz i5.

If the numbers are only slightly out of sequence: do i = 1,n call random_number(real_array(i)) real_array(i) = real_array(i) + real(i)*0.125 end do This results in quick sort of 4 seconds, while bubble sort of 2 seconds. (shell takes 4 seconds also)

For such inputs with mild disorder, if the data set consists of a sequence of blocks, with disorder only within blocks but such that every element of block k +1 is larger than every element of block k, insertion sort is a good choice. Oddly, you did not include this algorithm in your repertoire in the test program. Try the following program, please.

program tinssrt
! test insertion sort
implicit none
integer :: i, N, ktr
double precision, allocatable :: A(:)
integer, allocatable :: idx(:)
real :: t1,t2
!
N=10000000               ! start with N = 10 million
do ktr = 1,4
   allocate(A(N),idx(N))
   call random_number(A)
   idx=(/ (i,i=1,N) /)
   A=A+idx*0.125d0       ! (random real between 0 and 1) + (1:N)*0.125
   if (N <= 100) print '(' Unsorted:',/,(10F8.4))',A
   call cpu_time(t1)
   call inssort(N,idx,A)
   call cpu_time(t2)
   if (N <= 100) then
      print '(' Sorted:  ',/,(10F8.4))',A
      print '(20I4)',idx
   end if
   deallocate(A,idx)
   print 10,N,t2-t1
10 format(1x,i10,2x,F7.3)
   N = N*2                ! double N
end do   
end program

subroutine inssort(N,idx,A)
implicit none
integer, intent(in) :: N
integer, intent(in out) :: idx(N)
double precision, intent(in) :: A(N)
integer :: i,j,itmp
!
do i = 2, N
   j = i-1
   do while (j > 0)
      if (A(idx(j)) < A(idx(j+1))) exit
      itmp = idx(j+1)
      idx(j+1) = idx(j)
      idx(j)   = itmp
      j = j - 1
   end do
end do
return
end subroutine inssort

On a laptop with a i7-2720QM CPU, this program took about 1 second for N = 80 million.

If the values are random ( call random_number(real_array) ) my quick sort takes about 50 seconds. My bubble and shell sorts are still running after 2 hours 50 minutes !!

Many algorithms (Quicksort, Mergesort, etc.) perform better when they are augmented by incorporating a switch to insertion sort for small partitions.

The sort routines of the standard libraries of C++, Java, C# and Python use such hybrid algorithms. For example, Google Search with 'standard sort algorithm in .net'.