title: how fast is thrust::sort and what is the fastest radix sort implementation
body: <p>I'm a newbie to GPU programming. Recently, I'm trying to implement the gpu bvh construction algorithm based on an tutorial: <a href="http://devblogs.nvidia.com/parallelforall/thinking-parallel-part-iii-tree-construction-gpu/" rel="nofollow">http://devblogs.nvidia.com/parallelforall/thinking-parallel-part-iii-tree-construction-gpu/</a>. In the first step of this algorithm, the morton code(unsigned int) of every primitive is computed and sorted. The tutorial gives a reference time cost of the morton code computing and sorting for 12K objects:</p>
  
  <ol>
  <li>0.02 ms, one thread per object: Calculate bounding box and assign Morton code.</li>
  <li>0.18 ms, parallel radix sort: Sort the objects according to their Morton codes.
  ...</li>
  </ol>
  
  <p>In my implementation, the first step cost 0.1ms and the sorting step costs 1.8ms. I'm using thrust to do the sorting. So what is the fastest implementation of radix sort on GPU? </p>
  
  <p>I'm using a Geforce Titan GPU which should faster than the Geforce GTX690 used by the author of the tutorial.
  Here is my test code for sorting, it costs about 1.5ms even when the size is 10. </p>
  
  <pre><code>void testSort()
  {
      int sz = 10;
      thrust::host_vector&lt;unsigned int&gt; h_keys(sz);
      for(int i=0; i&lt;sz; i++)
          h_keys[i] = rand();
      thrust::device_ptr&lt;unsigned int&gt; keys = thrust::device_malloc&lt;unsigned int&gt;(sz);
      thrust::copy(h_keys.begin(),h_keys.end(),keys);
      cudaEvent_t estart, estop;
      cudaEventCreate( &amp;estart );
      cudaEventCreate( &amp;estop );
      cudaEventRecord( estart, 0 );
      thrust::stable_sort(keys,keys+sz);
      cudaEventRecord( estop, 0 ) ;
      cudaEventSynchronize( estop );
      float elapsedTime;
      cudaEventElapsedTime( &amp;elapsedTime,
          estart, estop ) ;
      printf( "Time to sort: %3.1f ms\n", elapsedTime );
      cudaEventDestroy( estart ) ;
      cudaEventDestroy( estop ) ;
  }
  </code></pre>