View unanswered posts | View active topics It is currently Thu Mar 21, 2019 4:02 am

 Page 1 of 1 [ 5 posts ]
 Print view Previous topic | Next topic
RobotC: extremely slow array sort performance
Author Message
Guru

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

_________________
regards,
HaWe aka Ford
#define S sqrt(t+2*i*i)<2
#define F(a,b) for(a=0;a<b;++a)

Sat Jan 11, 2014 5:52 am

Joined: Wed Mar 05, 2008 8:14 am
Posts: 3654
Location: Rotterdam, The Netherlands
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
Guru

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

Sun Jan 12, 2014 5:55 am

Joined: Wed Jan 24, 2007 10:42 am
Posts: 620
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
Guru

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

Thu Jan 16, 2014 4:07 pm
Display posts from previous:  Sort by
 Page 1 of 1 [ 5 posts ]

#### Who is online

Users browsing this forum: No registered users and 1 guest

 You cannot post new topics in this forumYou cannot reply to topics in this forumYou cannot edit your posts in this forumYou cannot delete your posts in this forumYou cannot post attachments in this forum

Search for:
 Jump to:  Select a forum ------------------ ROBOTC Applications    ROBOTC for LEGO MINDSTORMS       Third-party sensors    ROBOTC for CORTEX & PIC    ROBOTC for VEX IQ    ROBOTC for Arduino    Robot Virtual Worlds    Multi-Robot Communications    Issues and Bugs Competitions & Partners    Mini Urban Challenge    CS2N Robot Virtual Worlds Competitions       VEX Skyrise Competition 2014-2015       VEX Toss Up 2013-2014       FTC Block Party! 2013-2014    Competitions using VEX - BEST, TSA, VEX, and RoboFest!    FTC Programming    RoboCup Junior and Other ROBOT Competitions Virtual Brick Robotics Discussions    General Discussions    Project Discussions Off-Topic ROBOTC Forum & ROBOTC.net Suggestions/Feedback    ROBOTC Forums Suggestions/Comments    ROBOTC.net Suggestions/Comments       NXT Programming: Tips for Beginning with ROBOTC       VEX Programming: Tips for Beginning with ROBOTC    2013 Robotics Summer Of Learning       VEX Toss Up Programming Challenge       FTC Ring It Up! Programming Challenge    International Forums       Spanish Forums          ROBOTC for MINDSTORMS          ROBOTC for VEX       French Forums          ROBOTC pour Mindstorms          ROBOTC pour IFI VEX       Japanese Forums （日本語のフォーラム）       German Forums    2015 Spring Carnival Event    PLTW (Project Lead The Way)    Robotics Merit Badge    2014 Robotics Academy Summer of Learning

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