ROBOTC.net forums
http://www.robotc.net/forums/

RobotC: extremely slow array sort performance
http://www.robotc.net/forums/viewtopic.php?f=1&t=7667
Page 1 of 1

Author:  Ford Prefect [ Sat Jan 11, 2014 5:52 am ]
Post subject:  RobotC: extremely slow array sort performance

why has RobotC 3.62 got such an extremely slow array sort performance ?
for the same arrays RobotC needs ~96 sec while NXC only needs 0.33 sec, that is 300 x as much !
Code:
progr.language, API              NXC     RobotC 3.62
int array sort  (ms)             332      95879


Code:
void shellsort(int size, int *A)
{
   int mid = 0;
   for(int m = size/2 ; m > 0; m /= 2)
   {
     for(int j = m; j < size; j++)
     {
       for(int i = j - m; i >= 0; i -= m)
       {
         if(A[i + m] >= A[i])
           break;
         else
         {
           mid = A[i];
           A[i] = A[i + m];
           A[i + m] = mid;
         }
       }
     }
   }
}


how can be this improved ?

Author:  mightor [ Sun Jan 12, 2014 2:00 am ]
Post subject:  Re: RobotC: extremely slow array sort performance

Helmut,

Is the algorithm the same as in NXC? Maybe I made a mistake implementing it.

= Xander

Author:  Ford Prefect [ Sun Jan 12, 2014 5:55 am ]
Post subject:  Re: RobotC: extremely slow array sort performance

NXC has a built-in ArraySort algorithm which uses this one (acc. to John Hansen): http://sourceforge.net/apps/phpbb/mindboards/viewtopic.php?f=3&t=1740&p=15732&hilit=shellsort#p15732
(but no idea by which way it's been low-level implemented)

nxtOSEK uses this one, about the same performance as NXC - it's exactly the same algorithm which I am using for gpp C in my original code:
Code:
void shellsort(int size, int* A)
{
  int i, j, increment;
  int temp;
  increment = size / 2;

  while (increment > 0) {
    for (i = increment; i < size; i++) {
      j = i;
      temp = A[i];
      while ((j >= increment) && (A[j-increment] > temp)) {
        A[j] = A[j - increment];
        j = j - increment;
      }
      A[j] = temp;
    }

    if (increment == 2)
       increment = 1;
    else
       increment = (unsigned int) (increment / 2.2);
  }
}


ps,
edit:
yes, it seems that the implementation for RobotC possibly should be changed...

Author:  tfriez [ Thu Jan 16, 2014 3:49 pm ]
Post subject:  Re: RobotC: extremely slow array sort performance

Well sure - if NXC and other languages implement it at the firmware level, and you're comparing it at the VM level for ROBOTC there will be speed differences.

We can put it on the "to-do" list, but I'll warn you that list is fairly large at the moment.

Author:  Ford Prefect [ Thu Jan 16, 2014 4:07 pm ]
Post subject:  Re: RobotC: extremely slow array sort performance

for the moment I suspect that above all Xander's transcoded implementation is faulty.
I can't modify and test it by myself because I don't own a 3.6 licence.

Anyway, having quick array sort algorithms surely is very important, e.g., for real-time statistical and stochastical sensor data filtering, but admittedly not for my own current purposes concerning the NXT.

Page 1 of 1 All times are UTC - 5 hours [ DST ]
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
http://www.phpbb.com/