Code Complexity Classes II: Revisited

Here's that C code I've been promising:


Compiled in 64-bit Ubuntu 10.4.

When you run the code, just as in Java, you can see the difference in time between the "row by row" and "column by column" implementations:

The row by row implementation ran in 2.64 seconds according to the timer built into the program, with the column by column example running in 3.67 seconds.

This is in a VM, so comparisons to the Java example done before should not be made, as those examples were tested in the host OS.  As always with things like this, the time is subject to your unique system and what is running at the time of execution.

What is important though, is to notice the difference in time between the two implementations, it is still there, and it is a noticeable amount, even with this relatively small amount of data.

Just for curiosity's sake, I decided to see how turning optimization flags on would affect the execution time:

With first level optimization, our row by row time dropped considerably to 2.32 seconds, and our column by column implementation time went up to 3.88 seconds, further increasing the gap.

With second level optimization, row by row dropped again to 2.27, and column by column further increased to 3.95. As you can see, this time the change was negligible.

With third level optimization, we saw a decrease about half that of first level optimization in the time for row by row copying to 2.16. This optimization also decreased the column by column time to below that of first level optimization, but higher than that of no optimization, putting it at 3.81 seconds.

I'm not going to go into what exactly these optimization flags do, as that's a topic for another post, and I'm not even sure what all is done myself at this point. I'm extremely new to C, so if you see anything incorrect in this post, feel free to point out my mistakes, and I'll be happy to correct them and give credit where credit is due.

Speaking of where credit is due, I must give some to my Assembly Language teacher, Dr. Chen, for providing the basic version of this code (I only added the timer and made some minor tweaks to suit my cosmetic style) and for providing the inspiration for these posts on complexity classes and how they stack up in the real world.  Perhaps in the future I'll revisit this topic more in depth, for now though, I am done with it.