SPO Final Assigment Phase II

So for Phase 2, I complete redid my plan for Optimizing the code, Instead of rewriting and after talking to my Prof we decided that optimizing the code to work on a 64-bit processor instead of a 32-bit processor would be a good idea.

So before I could optimize this, I needed to understand what this function was doing 100% and figure out to optimize it. So after looking over the entire function, I realized the first part of this function could really not be optimized. Since it is creating an ASCII table and marking what parts of the reject string are in the ASCII table. but then it was really only going through the string by fours (Supporting 32-bit processors).

if (p[s[0]]) return 0;
if (p[s[1]]) return 1;
if (p[s[2]]) return 2;
if (p[s[3]]) return 3;

unsigned int c0, c1, c2, c3;
do
{
s += 4;
c0 = p[s[0]];
c1 = p[s[1]];
c2 = p[s[2]];
c3 = p[s[3]];
} while ((c0 | c1 | c2 | c3) == 0);

 

So rewriting this code was pretty simple, just had to create another 4 more unsigned int.   Allowing it for cycling 8 at a time (Supporting 64-bit processors).  Here is how I rewrote it

if (p[s[0]]) return 0;
if (p[s[1]]) return 1;
if (p[s[2]]) return 2;
if (p[s[3]]) return 3;
if (p[s[4]]) return 4;
if (p[s[5]]) return 5;
if (p[s[6]]) return 6;
if (p[s[7]]) return 7;
unsigned int c0, c1, c2, c3, c4, c5, c6, c7;
do
{
s += 8;
c0 = p[s[0]];
c1 = p[s[1]];
c2 = p[s[2]];
c3 = p[s[3]];
c4 = p[s[4]];
c5 = p[s[5]];
c6 = p[s[6]];
c7 = p[s[7]];
} while ((c0 | c1 | c2 | c3 | c4 | c5 | c6 | c7) == 0);

This was a simple fix and just had to make sure my code was consistent with their code and not trying to add my own touch to it. The only problem was trying to read a return ternary statement they left.

return (c0 | c1) != 0 ? count – c0 + 1 : count – c2 + 3;

During a discussion in class, we learned that a ternary statement and if the statement had the same exact run time except in certain situation but they did not apply for my code. This allowed me to make a more readable if statements with multiple return statements.

if (c0 | c1 != 0) {
return count – c0 + 1;
}
else if ((c2 | c3) != 0) {
return count – c2 + 3;
}
else if ((c4 | c5) != 0) {
return count – c4 + 5;
}
else {
return count – c6 + 5;
}

Now the only thing was testing my code. The first thing I tested was to make sure that my function returned the proper indexes. Then I wanted to compare run times, here is a small part what my tester looked like

printf(“Test 2 for optimizing STRCSPN \n ———————— \n\n”);
int i = 0;
char * str;
str = (char*)malloc(Size2 + 1);
str[Size2 + 1] = 9;
memset(str, “A”, Size2);
char rej[] = “123456789”;
clock_t start = clock(), diff;
i = STRCSPN_GNU(str, rej);
diff = clock() – start;

int msec = diff * 1000 / CLOCKS_PER_SEC;
printf(“Time taken %d seconds %d milliseconds \n”, msec / 1000, msec % 1000);
printf(“Index found at : %d \n\n”, i);
clock_t start2 = clock(), diff2;
i = STRCSPN_JJ(str, rej);
diff2 = clock() – start2;

int msec2 = diff2 * 1000 / CLOCKS_PER_SEC;
printf(“Time taken %d seconds %d milliseconds \n”, msec2 / 1000, msec2 % 1000);
printf(“Index found at : %d \n\n”, i);

Now the runtime. unfortunately I did not notice that much of improvements in seconds but in milliseconds I did notice some difference. My function is the second one, the first one is the GNU one.

feeb4f7947a015c87b315671312bd079.png

As you can see, there are subtle differences within milliseconds but not in seconds. I was able to optimize this function, but not as fast as I would like to be able to. I need to do more future testing, such as testing this on the two servers that my class has provided for me.

Conclusion

I believe this optimization is efficient enough to upload it. It’s not a strong as an optimization as I thought I could do, but at least it became faster instead of slower!

 

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s