title: Optmization for quicksort in x86 32-bit assembly
body: <p>I'm trying to learn some basic x86 32-bit assembly programming. So in pursuing this I decided to implement quicksort in assembly (sorting only integers). First I made a C-version of the sorting function and then I made an assembly version.</p>
  
  <p>However, when comparing my assembly version with the my C-version (compiled with gcc on Debian), the C-version performs more then 10 times faster on a array of 10000 integers. </p>
  
  <p>So my question is if anybody can give some feedback on obvious optimizations that can be made on my quick sort assembly routine. It's purely for educational purposes and I'm not expecting to beat the compiler makers in terms of producing high speed code but I'm interested in knowing if I'm making any obvious mistakes that hampers speed.</p>
  
  <p>The C-version:</p>
  
  <pre><code>void myqsort(int* elems, int sidx, int eidx)
  {
  
      if (sidx &lt; eidx)
      {
          int pivot = elems[eidx];
          int i = sidx;
          for (int j = sidx; j &lt; eidx; j++)
          {
              if (elems[j] &lt;= pivot)
              {
                  swap(&amp;elems[i], &amp;elems[j]);
                  i = i + 1;
              }
          }
          swap(&amp;elems[i], &amp;elems[eidx]);
          myqsort(elems, sidx, i - 1);
          myqsort(elems, i + 1, eidx);
      }
  }
  void swap(int* a, int* b)
  {
      int tmp = *a;
      *a = *b;
      *b = tmp;
  }
  </code></pre>
  
  <p>Assembly version (NASM):</p>
  
  <pre><code>;
  ; void asm_quick_sort(int* elems, int startindex, int endindex)
  ; Params:
  ;       elems - pointer to elements to sort - [ebp + 0x8]
  ;       sid - start index of items - [ebp + 0xC]
  ;       eid - end index of items - [ebp + 0x10]
  asm_quick_sort:
  
      push ebp
      mov ebp, esp
  
      push edi
      push esi
      push ebx
  
      mov eax, dword [ebp + 0xC]  ; store start index,  = i
      mov ebx, dword [ebp + 0x10] ; store end index
      mov esi, dword [ebp + 0x8]  ; store pointer to first element in esi
  
      cmp eax, ebx
      jnl qsort_done
  
      mov ecx, eax                        ; ecx = j, = sid
      mov edx, dword [esi + (0x4 * ebx)]  ; pivot element, elems[eid], edx = pivot
  qsort_part_loop:
      ; for j = sid; j &lt; eid; j++
      cmp ecx, ebx                    ; if ecx &lt; end index
      jnb qsort_end_part
      ; if elems[j] &lt;= pivot
      cmp edx, dword [esi + (0x4*ecx)]
      jb qsort_cont_loop
      ; do swap, elems[i], elems[j]
      push edx ; save pivot for now
      mov edx, dword [esi + (0x4*ecx)]        ; edx = elems[j]
      mov edi, dword [esi + (0x4*eax)]        ; edi = elems[i]
      mov dword [esi + (0x4*eax)], edx        ; elems[i] = elems[j]
      mov dword [esi + (0x4*ecx)], edi        ; elems[j] = elems[i]
      pop edx ; restore pivot
      ; i++
      add eax, 0x1
  qsort_cont_loop:
      add ecx, 0x1
      jmp qsort_part_loop
  qsort_end_part:
      ; do swap, elems[i], elems[eid]
      mov edx, dword [esi + (0x4*eax)]        ; edx = elems[i]
      mov edi, dword [esi + (0x4*ebx)]        ; edi = elems[eid]
      mov dword [esi + (0x4*ebx)], edx        ; elems[eidx] = elems[i]
      mov dword [esi + (0x4*eax)], edi        ; elems[i] = elems[eidx]
  
      ; qsort(elems, sid, i - 1)
      ; qsort(elems, i + 1, eid)
      sub eax, 0x1
      push eax
      push dword [ebp + 0xC]  ; push start idx
      push dword [ebp + 0x8]  ; push elems vector
      call asm_quick_sort
      add esp, 0x8
      pop eax
      add eax, 0x1
      push dword [ebp + 0x10] ; push end idx
      push eax
      push dword [ebp + 0x8]  ; push elems vector
      call asm_quick_sort
      add esp, 0xC
  
  
  qsort_done:
      pop ebx
      pop esi
      pop edi
  
      mov esp, ebp
      pop ebp
  
      ret
  </code></pre>
  
  <p>I call the assembly routine from C and I use clock() for timing the routines.</p>
  
  <p><strong>EDIT</strong>
  The difference in performance is no longer an issue after correcting the bugs pointed out by my fellow stackoverflowers. </p>