Content-Type: RST

.. figure :: http://blog.opensourcenerd.com/upload/picard-facepalm

Boy, was I wrong. Or right, I suppose. One of my readers did know what
I did wrong in my `previous post`_ about how Python is faster than C++
at bubble-sorting a list of files. I was also wrong about the
execution time overall of such a task, which should have tipped me
off. A proper bubble sort of 150000 items would have taken almost an
hour to accomplish. The fact mine was only taking a few seconds should
have been a cause for worry.

.. _`previous post`: http://blog.opensourcenerd.com/python-is-faster-than-cpp

The problem was in my while loop. It should have been:

.. sourcecode :: python

   while bubble(names):
       pass

Because otherwise it would end *because* it did a swap, and wouldn't
really sort. So, okay, I had two programs that did the same stupid
thing, except Python did the stupid thing faster than C++ did. That
was because I used ``endl`` to end my lines in C++. For my more
computer-savvy readers, ``endl`` does a flush after the line, every
time. 

For those less computer-savvy, imagine you were being dictated
something to write down on paper. Wouldn't it be faster to listen to
the dictation then write it down sentence by sentence, rather than
being told: "'The', write it down. 'Quick' write it down. 'Brown'
write it down. 'Fox' write it down." ... et cetera.

.. figure :: http://blog.opensourcenerd.com/upload/doing-it-wrong

   You are doing it very wrong.

So, the question is "what now?" Being a good programmer, I went back
and fixed my code to *actually* sort. Upon running it, I noticed it
would not finish running for a while, since bubble sort is so
inefficient, so I got a different list of files, this time only about
1000 long. As a result, I got something to this tune:

+-----------------------+---------+
| Method                | Time    |
+=======================+=========+
| Python - Bubble Sort  | 2.856s  |
+-----------------------+---------+
| C++ - Bubble Sort     | 0.742s  |
+-----------------------+---------+

Now *that* is the performance I was talking about. But wait, it gets
better.

.. figure :: http://blog.opensourcenerd.com/upload/ohai-i-upgraded-your-ram

The GNU C compiler (aka GCC) has a command line option (``-O2``) at
compilation time to optimize the generated bytecode of your
program. This is risky on very complicated programs, where it may
break some under the hood things, but for simple programs like this,
it's great. Let's add that optimization to the table.

+-----------------------+---------+
| Method                | Time    |
+=======================+=========+
| Python - Bubble Sort  | 2.856s  |
+-----------------------+---------+
| C++ - Bubble Sort     | 0.742s  |
+-----------------------+---------+
| C++ - Bubble Sort Opt | 0.249s  |
+-----------------------+---------+

That's almost a three-fold increase in performance! I'm not sure quite
what the optimizer does, but I don't think I'm leaving it off of any
of my future programs!

Now, that friend of mine also sent me a C program to do the same
thing, which was *even faster* because it didn't use slow-ish C++
features such as vectors. Here is his code:

.. sourcecode :: c

   #include <stdio.h>
   #include <string.h>
   #include <stdlib.h>

   char *names[155000];
   int nnames;

   bubble(nsort) {
      int switched = 0;
      int i;
      for (i = 0; i < nsort; i++) {
          if (strcmp (names[i], names[i+1]) > 0 ) {
              char *t = names[i];
              names[i] = names[i+1];
              names[i+1] = t;
              switched = 1;
          }
      }
      return switched;
   }

   int main() {
      char buf[512];
      FILE *fin = fopen ("files.txt", "r");
      nnames = 0;
      while (fgets (buf, 512, fin)) {
          names[nnames] = malloc (strlen (buf) + 1);
          strcpy (names[nnames++], buf);
      }
      int nsort = nnames;
      while (nsort && bubble(--nsort))
          ;
      FILE *fout = fopen ("files.out", "w");
      int i;
      for (i = 0; i < nnames; i++)
          fputs (names[i], fout);
      exit (0);
   }

Then I measured the time of that, plus the time with it optimized, and
added it to my table. For fun, I also whipped up two quick solutions
in C++ and Python using the respective built-in sort algorithms -
Quicksort based, lightning fast sorting methods. This is the final
tally:

+--------------------------+-----------+
| Method                   |  Time (s) |
+==========================+===========+
| Python – Bubble Sort     |  2.856    |
+--------------------------+-----------+
| C++ - Bubble Sort        |  0.742    |
+--------------------------+-----------+
| C++ - Bubble Sort Opt    |  0.249    |
+--------------------------+-----------+
| C – Bubble Sort          |  0.130    |
+--------------------------+-----------+
| C – Bubble Sort Opt      |  0.105    |
+--------------------------+-----------+
| Python – Quick Sort      |  0.086    |
+--------------------------+-----------+
| C++ - Quick Sort         |  0.049    |
+--------------------------+-----------+
| C++ - Quick Sort Opt     |  0.042    |
+--------------------------+-----------+

.. figure :: http://blog.opensourcenerd.com/upload/shocked-cat

And, for those who can't quite grasp the difference in performance
here, have a graph:

.. figure :: http://blog.opensourcenerd.com/upload/python-vs-c-performance

So, yeah. My intuition was correct that C++ is faster than Python. By
far. So then, nothing new. Move along, now. Nothing to see here.