Thread: I can't figure out why this C code is running so slow...

Hi,

I recently learned a fair amount of inline assembly and decided to do a little test. I wrote a selection sort in C that sorts 100,000 integers. I then wrote a inline assembly version of the same thing. I figured that the assembly version was going to be a little slower (I was pretty sloppy and didn't worry about optimization too much), but when I ran the tests I was shocked to find out that the assembly version was running twice as fast!

The C code is

Code:

   for (i = 0; i < n-1; ++i) {
      min = i;
      
      for (j = i+1; j < n; ++j)
         if (data[j] < data[min])
            min = j;
      
      if (i != min) {
         j = data[i];
         data[i] = data[min];
         data[min] = j;
      }
   }

I wrote the assembly code by looking at the C code and working my way through it. It's not heavily optimized, but it's not written extremely poorly either. My compiler is gcc 4.2.1, and I'm compiling both the C and inline assembly versions with -Wall -arch i386 -O2.

time ./test_asm < randfile.txt > outfile.txt
real 0m6.431s
user 0m6.381s
sys 0m0.012s

time ./test_c < randfile.txt > outfile.txt
real 0m13.518s
user 0m13.477s
sys 0m0.016s

Is assembly really THAT much faster??

EDIT: I am not attempting to start a flame war...

If you want provide both codes and we can cross those results.

EDIT: C produces assembly code, so you can check that as well and compare it with yours

Code:

/*******************************************************************************
 * Use this file to compare the amount of time it takes to run selection sort  *
 * code written in pure C to that of pure assembly. Use the linux command time *
 * in combination with this program to produce results.                        *
 ******************************************************************************/
#include <stdio.h>
#define SIZE 100000

/* Uncomment the following line to use the assembly code. */
#define USE_ASSEMBLY_CODE

/*******************************************************************************
 * main - Read data from standard input, sort it, write it to standard output. *
 ******************************************************************************/
int main() {
   int n, i, j, min;
   int data[SIZE];

   /* Read in the data */
   n = 0;
   while (scanf("%d", &data[n]) == 1)
      ++n;
   
#ifndef USE_ASSEMBLY_CODE  
   for (i = 0; i < n-1; ++i) {
      min = i;
      
      for (j = i+1; j < n; ++j)
         if (data[j] < data[min])
            min = j;
      
      if (i != min) {
         j = data[i];
         data[i] = data[min];
         data[min] = j;
      }
   }
   
#else
   __asm__ ("pushl   %%ebx\n\t"
            "xorl    %%eax, %%eax\n\t"
            "movl    %1, %%edx\n\t"
            "decl    %%edx\n\t"
            
            "check_outer:\n\t"
            "cmpl    %%edx, %%eax\n\t"
            "jge     done\n\t"
            
            "outer_loop:\n\t"
            "movl    %%eax, %%ecx\n\t"

                  "pushl   %%eax\n\t"
                  "incl    %%eax\n\t"
                  "check_inner:\n\t"
                  "cmpl    %1, %%eax\n\t"
                  "jge     resume_outer\n\t"
            
                  "inner_loop:\n\t"
                  "movl    (%0, %%eax, 4), %%ebx\n\t"
                  "cmpl    (%0, %%ecx, 4), %%ebx\n\t"
                  "jge     skip_inner_fix\n\t"
                  "movl    %%eax, %%ecx\n\t"
            
                  "skip_inner_fix:\n\t"
                  "incl    %%eax\n\t"
                  "jmp     check_inner\n\t"
            
            "resume_outer:\n\t"
            "popl    %%eax\n\t"
            
            "cmpl    %%eax, %%ecx\n\t"
            "je      skip_swap\n\t"
            "movl    (%0, %%eax, 4), %%ebx\n\t"
            "xchgl   %%ebx, (%0, %%ecx, 4)\n\t"
            "movl    %%ebx, (%0, %%eax, 4)\n\t"
            
            "skip_swap:\n\t"
            "incl    %%eax\n\t"
            "jmp     check_outer\n\t"
            
            "done:\n\t"
            "popl    %%ebx"
            :/* nothing to output */
            :"r" (&data), "r" (n)
            :"eax", "edx", "ecx"
           );
#endif
   
   /* Print out the data */
   for (i = 0; i < n; ++i)
      printf("%d\n", data[i]);
   
   return 0;
}

I generated the numbers using

Code:

#include <cstdlib> 
#include <iostream>

using namespace std;

int main() 
{ 
   for (int i = 0; i < 100000; i++)
      cout << rand() << endl;
   
   cout << "a";
}

Thanks for the help! I'm wondering if it's just my old GNU toolchain?

EDIT: I noticed that the C code is hammering the memory. They're about the same number of instructions, though.

I would also like to see your compiler switches...

Originally Posted by jeffcobb

I would also like to see your compiler switches...

So would I. I'm guessing he is compiling the c version without optimizations.
Compiling his code under mvsc with full optimizations enabled and the c version is almost twice as fast as the inline assembler.

Edit:
Reran the tests with gcc under cygwin

Code:

$ time ./asm_sort_gcc3 < in.txt > out.txt

real    0m5.082s
user    0m5.015s
sys     0m0.030s

$ time ./asm_sort_gcc4 < in.txt > out.txt

real    0m5.088s
user    0m4.984s
sys     0m0.046s

$ time ./c_sort_gcc3 < in.txt > out.txt

real    0m3.660s
user    0m3.578s
sys     0m0.015s

$ time ./c_sort_gcc4 < in.txt > out.txt

real    0m9.596s
user    0m9.530s
sys     0m0.015s

$ gcc-3 --version
gcc-3 (GCC) 3.4.4 (cygming special, gdc 0.12, using dmd 0.125)


$ gcc-4 --version
gcc-4 (GCC) 4.3.4 20090804 (release) 1

All versions of the binary compiled with "-Wall -O3"
I don't know much about gcc so it might be that I'm using the wrong switches, but if not then there seems to be a bug in gcc4's optimization because the gcc3 version is almost 3 times faster.