View unanswered posts | View active topics It is currently Thu Jul 24, 2014 6:45 am






Reply to topic  [ 5 posts ] 
RobotC: extremely slow array sort performance 
Author Message
Guru
User avatar

Joined: Sat Mar 01, 2008 12:52 pm
Posts: 1030
Post 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 ?

_________________
regards,
HaWe aka Ford
#define S sqrt(t+2*i*i)<2
#define F(a,b) for(a=0;a<b;++a)
float x,y,r,i,s,j,t,n;task main(){F(y,64){F(x,99){r=i=t=0;s=x/33-2;j=y/32-1;F(n,50&S){t=r*r-i*i;i=2*r*i+j;r=t+s;}if(S){PutPixel(x,y);}}}while(1)}


Sat Jan 11, 2014 5:52 am
Profile
Moderator
Moderator
User avatar

Joined: Wed Mar 05, 2008 8:14 am
Posts: 3162
Location: Rotterdam, The Netherlands
Post Re: RobotC: extremely slow array sort performance
Helmut,

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

= Xander

_________________
| Professional Conduit of Reasonableness
| (Title bestowed upon on the 8th day of November, 2013)
| My Blog: I'd Rather Be Building Robots
| ROBOTC 3rd Party Driver Suite: [Project Page]


Sun Jan 12, 2014 2:00 am
Profile WWW
Guru
User avatar

Joined: Sat Mar 01, 2008 12:52 pm
Posts: 1030
Post 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...

_________________
regards,
HaWe aka Ford
#define S sqrt(t+2*i*i)<2
#define F(a,b) for(a=0;a<b;++a)
float x,y,r,i,s,j,t,n;task main(){F(y,64){F(x,99){r=i=t=0;s=x/33-2;j=y/32-1;F(n,50&S){t=r*r-i*i;i=2*r*i+j;r=t+s;}if(S){PutPixel(x,y);}}}while(1)}


Sun Jan 12, 2014 5:55 am
Profile
Site Admin
Site Admin

Joined: Wed Jan 24, 2007 10:42 am
Posts: 601
Post 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.

_________________
Timothy Friez
ROBOTC Developer - SW Engineer
tfriez@robotc.net


Thu Jan 16, 2014 3:49 pm
Profile
Guru
User avatar

Joined: Sat Mar 01, 2008 12:52 pm
Posts: 1030
Post 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.

_________________
regards,
HaWe aka Ford
#define S sqrt(t+2*i*i)<2
#define F(a,b) for(a=0;a<b;++a)
float x,y,r,i,s,j,t,n;task main(){F(y,64){F(x,99){r=i=t=0;s=x/33-2;j=y/32-1;F(n,50&S){t=r*r-i*i;i=2*r*i+j;r=t+s;}if(S){PutPixel(x,y);}}}while(1)}


Thu Jan 16, 2014 4:07 pm
Profile
Display posts from previous:  Sort by  
Reply to topic   [ 5 posts ] 

Who is online

Users browsing this forum: No registered users and 2 guests


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 post attachments in this forum

Search for:
Jump to:  



Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group.
Designed by ST Software for PTF.