Want more features on Pastebin? Sign Up, it's FREE!
Guest

bitmapslow.cpp

By: a guest on Feb 17th, 2012  |  syntax: C++  |  size: 3.22 KB  |  views: 267  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  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. }
clone this paste RAW Paste Data