Guest User

Is C/C++ worth it? -- reply

a guest
Jul 23rd, 2012
524
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1.  
  2. /**
  3. * Fast computations of cumulative sums.
  4. * D. Lemire, July 2012
  5. *
  6. * Best results with:
  7. *
  8.  
  9. $ g++-4.7  -funroll-loops -O3 -o cumulsum cumulsum.cpp
  10.  
  11. $ ./unrolldeltas
  12.  
  13. but we want to avoid the -funroll-loops flag.
  14. */
  15.  
  16.  
  17. // This may require GCC 4.4/
  18.  
  19.  
  20. #include <sys/stat.h>
  21. #include <sys/time.h>
  22. #include <sys/types.h>
  23. #include <iostream>
  24. #include <cassert>
  25. #include <vector>
  26. #include <stdexcept>
  27.  
  28. using namespace std;
  29.  
  30. class WallClockTimer {
  31. public:
  32.     struct timeval t1, t2;
  33.     WallClockTimer() :
  34.         t1(), t2() {
  35.         gettimeofday(&t1, 0);
  36.         t2 = t1;
  37.     }
  38.     void reset() {
  39.         gettimeofday(&t1, 0);
  40.         t2 = t1;
  41.     }
  42.     int elapsed() {
  43.         return ((t2.tv_sec - t1.tv_sec) * 1000) + ((t2.tv_usec - t1. tv_usec)
  44.                 / 1000);
  45.     }
  46.     int split() {
  47.         gettimeofday(&t2, 0);
  48.         return elapsed();
  49.     }
  50. };
  51.  
  52.  
  53.  
  54.  
  55. vector<int>  givemeanarray(size_t N) {
  56.     vector<int> bigarray;
  57.     bigarray.reserve(N);
  58.     for(unsigned int k = 0; k<N; ++k)
  59.       bigarray.push_back(k+k/3);
  60.     return bigarray;
  61. }
  62.  
  63.  
  64. void slowishSum(vector<int> & data) {
  65.       size_t s = data.size();
  66.       if(s == 0) return;
  67.       int* ptr = &data[0];
  68.       for (size_t i = 1; i != s; ++i) {
  69.          ptr[i] += ptr[i - 1] ;
  70.       }
  71. }
  72.  
  73.  
  74.  
  75. // By Vasily Volkov, improved by Daniel Lemire
  76. void fastSum(vector<int> & data) {
  77.     size_t s = data.size();
  78.     int* ptr = &data[0];
  79.     if(s == 0) return;
  80.  
  81.     const size_t UnrollQty = 4;
  82.     size_t sz0 = (s / UnrollQty)  * UnrollQty; // equal to 0, if data.size() < UnrollQty
  83.     size_t i = 1;
  84.  
  85.     if (sz0>=UnrollQty) {
  86.         int a = ptr[0];
  87.         for (; i < sz0 - UnrollQty ; i += UnrollQty) {
  88.           a = (ptr[i] += a);
  89.           a = (ptr[i + 1] += a);
  90.           a = (ptr[i + 2] += a);
  91.           a = (ptr[i + 3] += a);
  92.        }
  93.     }
  94.     for (; i != s; ++i) {
  95.        ptr[i] += ptr[i- 1] ;
  96.     }
  97. }
  98.  
  99. // loop unrolling helps avoid the need for -funroll-loops
  100. void sum(vector<int> & data) {
  101.       size_t s = data.size();
  102.       int* ptr = &data[0];
  103.       if(s == 0) return;
  104.       size_t i = 1;
  105.       for (; i < s - 1; i+=2) {
  106.          ptr[i] += ptr[i - 1];
  107.          ptr[i+1] += ptr[i ];
  108.        }
  109.       for (; i != s; ++i) {
  110.          ptr[i] += ptr[i - 1];
  111.       }
  112. }
  113.  
  114.  
  115.  
  116. void test(size_t N ) {
  117.     WallClockTimer time;
  118.     for(int t = 0; t<2;++t) {
  119.       cout <<" test # "<< t<<endl;
  120.       vector<int> data = givemeanarray(N) ;
  121.       vector<int> copydata(data);
  122.      
  123.       time.reset();
  124.       slowishSum(data);
  125.       cout<<"basic sum "<<N/(1000.0*time.split())<<endl;  
  126.      
  127.       data = copydata;
  128.  
  129.       time.reset();
  130.       sum(data);
  131.       cout<<"smarter sum "<<N/(1000.0*time.split())<<endl;  
  132.  
  133.       data = copydata;
  134.  
  135.       time.reset();
  136.       fastSum(data);
  137.       cout<<"fast sum "<<N/(1000.0*time.split())<<endl;  
  138.  
  139.       cout<<endl<<endl<<endl;
  140.     }
  141.  
  142. }
  143.  
  144.  
  145.  
  146. int main() {
  147.     cout << "reporting speed in million of integers per second "<<endl;
  148.     size_t N = 50 * 1000 * 1000 ;
  149.     test(N);
  150.     cout<<"============"<<endl;
  151.     test(N);
  152. }
RAW Paste Data