title: Tail call optimisation seems to slightly worsen performance
body: <p>In a quicksort implementation, the data on left is for pure <code>-O2</code> optimized code, and data on right is <code>-O2</code> optimized code with  <code>-fno-optimize-sibling-calls</code> flag turned on i.e with tail-call optimisation turned off. This is average of 3 different runs, variation seemed negligible. Values were of range 1-1000, time in millisecond. Compiler was MinGW g++, version 6.3.0.</p>
  
  <pre><code>size of array     with TLO(ms)    without TLO(ms)
        8M                35,083           34,051 
        4M                 8,952            8,627
        1M                   613              609
  </code></pre>
  
  <p>Below is my code: </p>
  
  <pre><code>#include &lt;bits/stdc++.h&gt;
  using namespace std;
  
  int N = 4000000;
  
  void qsort(int* arr,int start=0,int finish=N-1){
      if(start&gt;=finish) return ;
      int i=start+1,j = finish,temp;
      auto pivot = arr[start];
      while(i!=j){
          while (arr[j]&gt;=pivot &amp;&amp; j&gt;i) --j;
          while (arr[i]&lt;pivot &amp;&amp; i&lt;j) ++i;
          if(i==j) break;
          temp=arr[i];arr[i]=arr[j];arr[j]=temp; //swap big guy to right side
      }
      if(arr[i]&gt;=arr[start]) --i;
  
      temp = arr[start];arr[start]=arr[i];arr[i]=temp; //swap pivot
      qsort(arr,start,i-1);
      qsort(arr,i+1,finish);
  }
  
  int main(){
      srand(time(NULL));
      int* arr = new int[N];
      for(int i=0;i&lt;N;i++) {arr[i] = rand()%1000+1;}
  
      auto start = clock();
      qsort(arr);
      cout&lt;&lt;(clock()-start)&lt;&lt;endl;
      return 0;
  }
  </code></pre>
  
  <p>I heard <code>clock()</code> isn't the perfect way to measure time. But this effect seems to be consistent.</p>
  
  <p>EDIT: as response to a comment, I guess my question is : Explain how exactly gcc's tail-call optimizer works and how this happened and what should I do to leverage tail-call to speed up my program?</p>