ROBOTC.net forumshttp://www.robotc.net/forums/ RobotC: extremely slow array sort performancehttp://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.62int 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 Grouphttp://www.phpbb.com/