1. /**
  2. *
  3. * Daniel Lemire, February 2012, http://lemire.me/
  4. *
  5. * Suppose that you want to copy an array over
  6. * another, except for some exceptions.
  7. * What is faster?
  8. *
  9. *
  10. */
  11.  
  12.  
  13. #include <iostream>
  14. #include <vector>
  15. #include <cstdlib>
  16. #include <cstring>
  17. #include <sys/stat.h>
  18. #include <sys/time.h>
  19. #include <sys/types.h>
  20.  
  21. using namespace std;
  22.  
  23. typedef unsigned int uint;
  24.  
  25.  
  26.  
  27.  
  28. class ZTimer
  29. {
  30. public:
  31.     struct timeval t1, t2;
  32. public:
  33.     ZTimer() :  t1(), t2() { gettimeofday(&t1,0); t2 = t1; }
  34.     void reset() {gettimeofday(&t1,0); t2 = t1;}
  35.     int elapsed() { return ((t2.tv_sec - t1.tv_sec) * 1000) + ((t2.tv_usec - t1.
  36. tv_usec) / 1000); }
  37.     int split() { gettimeofday(&t2,0); return elapsed(); }
  38. };
  39.  
  40. /**
  41. * This copies the data from begin to end, except at some locations
  42. * given by exceptionpos where it must use the values from
  43. * exceptionval. We write to "out".
  44. */
  45. __attribute__ ((noinline)) void patchedcopy(const uint * const  __restrict__ begin,
  46.         const uint * const  end,
  47.         const  uint * __restrict__ exceptionval,
  48.         const vector<uint> & exceptionpos,
  49.     uint * __restrict__ out) {
  50.     uint * __restrict__ tmpout = out;
  51.     for(const uint *  __restrict__ i = begin; i<end;++i) {
  52.         *(tmpout++) = *i;
  53.     }
  54.     for(vector<uint>::const_iterator pos = exceptionpos.begin(); pos!= exceptionpos.end();++pos) {
  55.         *(out + *pos) = *(exceptionval++);
  56.     }
  57. }
  58.  
  59.  
  60.  
  61. /**
  62. * This copies the data from begin to end, except at some locations
  63. * given by exceptionbitmap where it must use the values from
  64. * exceptionval. We write to "out".
  65. */
  66. __attribute__ ((noinline)) void bitmapcopy(const uint * const  __restrict__ begin,
  67.         const uint * const  end,
  68.         const  uint * __restrict__ exceptionval,
  69.         const vector<uint> & exceptionbitmap,
  70.     uint * __restrict__ out) {
  71.     vector<uint>::const_iterator j = exceptionbitmap.begin();
  72.     for(const uint *  __restrict__ i = begin; i<end;++i) {
  73.         for(uint k = 0; k<32;++k,++i)
  74.             *(out++) = ((*j) & (1U<<k))? *(exceptionval++) : *i;
  75.         ++j;
  76.     }
  77. }
  78.  
  79.  
  80. vector<uint> generateArray(uint N) {
  81.     vector<uint> ans(N);
  82.     for(uint k = 0; k<N;++k)
  83.       ans[k] = rand();
  84.     return ans;
  85. }
  86.  
  87. pair<vector<uint>, vector<uint> > generateExceptLocations(uint N, uint density) {
  88.     vector<uint> positions;
  89.     vector<uint> bitmap(N/32);
  90.     for(uint k = 0; k<N;k+= density) {
  91.         positions.push_back(k);
  92.         bitmap[k/32] &= (1<<(k%32));
  93.     }
  94.     return pair<vector<uint>, vector<uint> >(positions,bitmap);
  95. }
  96. int main() {
  97.     uint N = 1000000*32;//1024*1024*100;
  98.     uint density = 100;
  99.     vector<uint> data = generateArray(N);
  100.     vector<uint> out(N);
  101.     ZTimer z;
  102.  
  103.     vector<uint> exceptionvals = generateArray(N);// more than we need
  104.     cout <<" density(%)\t time with patching \t time with bitmaps"<<endl;
  105.     for(uint density = 1; density<50; density+=5) {
  106.         pair<vector<uint>, vector<uint> > exceptionpos = generateExceptLocations( N, density);
  107.    
  108.         cout<<100.0/density<<"\t\t\t";
  109.  
  110.        
  111.         z.reset();
  112.         patchedcopy(& data[0],
  113.         (& data[0]) + N,
  114.         &  exceptionvals[0],
  115.         exceptionpos.first,
  116.         &out[0]);
  117.         cout<<z.split()<<"\t\t\t";
  118.  
  119.         z.reset();
  120.         bitmapcopy(& data[0],
  121.         (& data[0]) + N,
  122.         &  exceptionvals[0],
  123.         exceptionpos.second,
  124.         &out[0]);  
  125.         cout<<z.split()<<"\t";
  126.  
  127.        
  128.         cout<<endl;
  129.     }
  130.     return 0;
  131. }