Pastebin launched a little side project called VERYVIRAL.com, check it out ;-) Want more features on Pastebin? Sign Up, it's FREE!
Guest

bitpacking.cpp

By: a guest on Mar 8th, 2012  |  syntax: C++  |  size: 10.49 KB  |  views: 34  |  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.  * bitpacking.cpp
  3.  *
  4.  *     Original 6199 line source by Daniel Lemire, http://lemire.me/blog/
  5.  *         Question: if you pack and unpack bits, is it much faster if you
  6.  *         pack into 8 or 16 bits than, say, 31 or 7 bits?
  7.  *
  8.  *     Modified  354 line source by willcodeforfood@reddit
  9.  *         g++ -DMAIN -DBENCH -O3 bitpacking.cpp -o bench
  10.  *         g++ -DMAIN -DSPECS -O1 bitpacking.cpp -o specs
  11.  *         g++ -O3 bitpacking.cpp -c -o bitpack.o
  12.  */
  13.  
  14. extern "C" {
  15. #    include <sys/time.h>
  16. }
  17. #include <cassert>
  18. #include <cstdlib>
  19. #include <iostream>
  20. #include <vector>
  21.  
  22. #ifdef __USE_GNU
  23. #    define RESTRICT __restrict__
  24. #    define NOINLINE __attribute__ ((noinline))
  25. #else
  26. #    define RESTRICT
  27. #    define NOINLINE
  28. #endif
  29.  
  30. #define PARAMS cuint * RESTRICT i, uint * RESTRICT o
  31. #define FOREACH_1to31(F) \
  32.     F (1)  F (2)  F (3)  F (4)  F (5)  F (6)  F (7)  F (8) \
  33.     F (9)  F (10) F (11) F (12) F (13) F (14) F (15) F (16) \
  34.     F (17) F (18) F (19) F (20) F (21) F (22) F (23) F (24) \
  35.     F (25) F (26) F (27) F (28) F (29) F (30) F (31)
  36.  
  37. #define FOREACH_1to32(F) FOREACH_1to31(F) F (32)
  38. #define SUB(a, b) ((a) - (b))
  39. #define LSH(a, b) ((a) << (b))
  40. #define RSH(a, b) ((a) >> (b))
  41. #define MASK(x, k) ((x) % (1U << (k)))
  42. #define die(why) do { cerr << why << endl; assert(0); \
  43.                       exit(EXIT_FAILURE); } while(0)
  44.  
  45. using namespace std;
  46. typedef const bool cbool;
  47. typedef const uint cuint;
  48. typedef vector<uint> vuint;
  49. typedef const vuint cvuint;
  50.  
  51. // P = pack, U = unpack, S = spec
  52. // defines 96 functions: {p,u}{1..32}(PARAMS) and s{1..32}()
  53. namespace metaprog {
  54. #define TPAR cuint * RESTRICT &i, uint * RESTRICT &o
  55. #define TCALL(f) (f (i, o))
  56. #define IGNORE(x) ((void)x)
  57. // in this context, dirty means that some bits weren't processed.
  58. // [PU][CD][CD] = (pack|unpack) start:(clean|dirty) end:(clean|dirty)
  59. // [PU]Dx = called when dirty at the start; handles remainders
  60. // [PU]Rx = adds the remainder bits to the output
  61. // these functional macros aren't fully general; some aren't expr-safe,
  62. // and some evaluate their params more than once.
  63. #define PCD(n, k) do { (*o) |= LSH (MASK ((*i), n), k); } while (0)
  64. #define UCD(n, k) do { (*o) = MASK (RSH ((*i), k), n); } while (0)
  65. #define PCC(n, k) do { PCD(n, k); (++i); } while (0)
  66. #define UCC(n, k) do { UCD(n, k); (++o); } while (0)
  67. #define PRx(n, k) do { (*o) |= RSH (MASK ((*i), n), SUB (n, k)); } while (0)
  68. #define URx(n, k) do { (*o) |= LSH (MASK ((*i), k), SUB (n, k)); } while (0)
  69. #define PDx(n, k) do { (++o); PRx(n, k); (++i); } while (0)
  70. #define UDx(n, k) do { (++i); URx(n, k); (++o); } while (0)
  71. #define PDD(n, k) do { PDx(n, k); PCD(n, k); } while (0)
  72. #define UDD(n, k) do { UDx(n, k); UCD(n, k); } while (0)
  73. #define PDC(n, k) do { PDD(n, k); (++i); } while (0)
  74. #define UDC(n, k) do { UDD(n, k); (++o); } while (0)
  75.  
  76.     // before and after refer to dirty state relative to X
  77.     template <cuint n, cuint b, cbool before, cbool after>
  78.         struct X {
  79.             static inline void P (TPAR);
  80.             static inline void U (TPAR);
  81.         };
  82.  
  83. #define SPECIALIZE_X(x, y, F) \
  84.     template <cuint n, cuint b> \
  85.         struct X <n, b, (x), (y)> { \
  86.             static inline void P (TPAR) { P##F (n, b); } \
  87.             static inline void U (TPAR) { U##F (n, b); } \
  88.             static inline void S () { cout << "    " << #F << " (" << n \
  89.                 << ", " << b << ");" << endl; } \
  90.         }
  91.  
  92.     // real execution work hides here
  93.     SPECIALIZE_X(true,  true,  CC);
  94.     SPECIALIZE_X(true,  false, CD);
  95.     SPECIALIZE_X(false, true,  DC);
  96.     SPECIALIZE_X(false, false, DD);
  97.  
  98.     static inline void nop(TPAR) {
  99.         IGNORE(i);
  100.         IGNORE(o);
  101.     }
  102.  
  103.     template <cbool end>
  104.         struct E {
  105.             static inline void P(TPAR) {
  106.                 TCALL(nop);
  107.             }
  108.  
  109.             static inline void U(TPAR) {
  110.                 TCALL(nop);
  111.             }
  112.  
  113.             static inline void S() { }
  114.         };
  115.  
  116.     // end states advance the input or output
  117.     template <>
  118.         struct E<true> {
  119.             static inline void P(TPAR) {
  120.                 IGNORE(i);
  121.                 ++o;
  122.             }
  123.  
  124.             static inline void U(TPAR) {
  125.                 IGNORE(o);
  126.                 ++i;
  127.             }
  128.  
  129.             static inline void S() {
  130.                 cout << "    EE ();" << endl;
  131.             }
  132.         };
  133.  
  134.     template <cuint n, cuint prev, cuint current, cuint next>
  135.         struct W {
  136. // WX = execute single step
  137. // WE = end at alignment 0 (mod 32)
  138. #define WX X<n, current, before, after>
  139. #define WE E<end>
  140.             // dirty state before and after the W routine
  141.             static cbool before = (current == 0 || prev < current);
  142.             static cbool end = (next == 0);
  143.             static cbool after = (end || current < next);
  144.  
  145.             static inline void P (TPAR) {
  146.                 TCALL(WX::P);
  147.                 TCALL(WE::P);
  148.             }
  149.  
  150.             static inline void U (TPAR) {
  151.                 TCALL(WX::U);
  152.                 TCALL(WE::U);
  153.             }
  154.  
  155.             static inline void S () {
  156.                 WX::S();
  157.                 WE::S();
  158.             }
  159.         };
  160.  
  161.     // recursive metaprogram; assumes 0th step is specialized
  162.     template <cuint n, cuint step>
  163.         struct R {
  164. // RR = recursion
  165. // RW = does the work for this step
  166. #define RR R<n, (step - 1)>
  167. #define RW W<n, prev, current, next>
  168.             static cuint prev = ((step - 1) * n) % 32U;
  169.             static cuint current = (step * n) % 32U;
  170.             static cuint next = ((step + 1) * n) % 32U;
  171.  
  172.             static inline void P (TPAR) {
  173.                 TCALL(RR::P);
  174.                 TCALL(RW::P);
  175.             }
  176.  
  177.             static inline void U (TPAR) {
  178.                 TCALL(RR::U);
  179.                 TCALL(RW::U);
  180.             }
  181.  
  182.             static inline void S () {
  183.                 RR::S ();
  184.                 RW::S ();
  185.             }
  186.         };
  187.  
  188. // each bit size recurses from 31 to 0
  189. #define FR(n) R<n, 31>
  190. #define SPECIALIZE_R(n) \
  191.     void p##n (PARAMS) { TCALL(FR(n)::P); } \
  192.     void u##n (PARAMS) { TCALL(FR(n)::U); } \
  193.     void s##n () { FR(n)::S(); } \
  194.     template<> struct R <(n), 0> { \
  195.         static inline void P (TPAR) { PCC (n, 0); } \
  196.         static inline void U (TPAR) { UCC (n, 0); } \
  197.         static inline void S () { \
  198.              cout << "    CC (" << n << ", 0);" << endl; } };
  199.  
  200.     // primarily defines {p,u}{1..31}
  201.     FOREACH_1to31(SPECIALIZE_R)
  202.  
  203.     // {p,u}32 calls slowcpy
  204.     static void slowcpy (PARAMS) {
  205.         for (int j = 0; j < 32; ++j)
  206.             *o++ = *i++;
  207.     }
  208.  
  209.     void p32(PARAMS) {
  210.         TCALL(slowcpy);
  211.     }
  212.  
  213.     void u32(PARAMS) {
  214.         TCALL(slowcpy);
  215.     }
  216.  
  217.     void s32() {
  218.         for (int j = 0; j < 32; ++j)
  219.             cout << "    *o++ = *i++;" << endl;
  220.     }
  221. }
  222.  
  223. namespace switchfns {
  224. // pack and unpack switch functions call the recursive metaprograms
  225. #define CASE_P(n) case (n): do { TCALL(metaprog::p##n); return; } while(0);
  226. #define CASE_U(n) case (n): do { TCALL(metaprog::u##n); return; } while(0);
  227. #define CASE_S(n) case (n): do { metaprog::s##n(); return; } while (0);
  228. #define DEF_SWITCH(fname, cases) \
  229.     void fname (PARAMS, cuint bit) { \
  230.         switch (bit) { \
  231.             FOREACH_1to32 (cases); \
  232.             default: die("invalid case"); } }
  233.  
  234.     DEF_SWITCH(pack, CASE_P)
  235.     DEF_SWITCH(unpack, CASE_U)
  236.  
  237.     void spec (cuint bit) {
  238.         switch (bit) {
  239.             FOREACH_1to32 (CASE_S);
  240.         default:
  241.             die("invalid case");
  242.         }
  243.     }
  244. }
  245.  
  246. #ifdef BENCH
  247. namespace bench {
  248.     struct ZTimer {
  249.         struct timeval t1, t2;
  250.  
  251.         ZTimer() : t1(), t2() {
  252.             reset();
  253.         }
  254.  
  255.         int elapsed () {
  256.             return ((t2.tv_sec - t1.tv_sec) * 1000) +
  257.                    ((t2.tv_usec - t1.tv_usec) / 1000);
  258.         }
  259.  
  260.         void reset () {
  261.             gettimeofday (&t1, 0);
  262.             t2 = t1;
  263.         }
  264.  
  265.         int split () {
  266.             gettimeofday (&t2, 0);
  267.             return elapsed ();
  268.         }
  269.     };
  270.  
  271.     NOINLINE void fast_pack (cvuint & i, vuint & o, cuint bit) {
  272.         cuint N = i.size () / 32;
  273.         for (uint k = 0; k < N; ++k)
  274.             switchfns::pack (&i[0] + 32 * k,
  275.                 &o[0] + (32 * bit) * k / 32, bit);
  276.     }
  277.  
  278.     NOINLINE void fast_unpack (cvuint & i, vuint & o, cuint bit) {
  279.         cuint N = o.size () / 32;
  280.         for (uint k = 0; k < N; ++k)
  281.             switchfns::unpack (&i[0] + (32 * bit) * k / 32,
  282.                 &o[0] + 32 * k, bit);
  283.     }
  284.  
  285.     bool validate (cvuint & i, cvuint & o, cuint bit) {
  286.         if (bit == 32)
  287.             return i == o;
  288.         cuint N = i.size ();
  289.         for (uint k = 0; k < N; ++k)
  290.             if (MASK(i[k], bit) != MASK(o[k], bit)) {
  291.                 cerr << " Error at k = " << k << " i[k]= " << i[k]
  292.                      << " o[k]=" << o[k] << endl;
  293.                 return false;
  294.             }
  295.         return true;
  296.     }
  297.  
  298.     vuint generateArray (cuint N) {
  299.         vuint ans (N);
  300.         for (uint k = 0; k < N; ++k)
  301.             ans[k] = rand ();
  302.         return ans;
  303.     }
  304.  
  305.     void simplebenchmark (cuint N = 1U << 26, cuint T = 5) {
  306.         ZTimer z;
  307.         cvuint data = generateArray (N);
  308.         vuint compressed (N, 0), recovered (N, 0);
  309.         cout << "bits" << "\t" << "pack" << "\t" << "unpack" << endl;
  310.         for (uint bit = 1; bit <= 32; ++bit) {
  311.             double packtime = 0, unpacktime = 0;
  312.             for (uint t = 0; t < T; ++t) {
  313.                 compressed.clear ();
  314.                 compressed.resize (N * bit / 32, 0);
  315.                 recovered.clear ();
  316.                 recovered.resize (N, 0);
  317.                 z.reset ();
  318.                 fast_pack (data, compressed, bit);
  319.                 packtime += z.split ();
  320.                 z.reset ();
  321.                 fast_unpack (compressed, recovered, bit);
  322.                 unpacktime += z.split ();
  323.                 if (!validate (data, recovered, bit))
  324.                     die("failed validation");
  325.             }
  326.             cout << bit << "\t" << packtime << "\t" << unpacktime << endl;
  327.         }
  328.     }
  329. }
  330. #endif
  331.  
  332. #ifdef SPECS
  333. namespace specs {
  334.     void print() {
  335.         for (uint bit = 1; bit<= 32; ++bit) {
  336.             cout << "SPEC(" << bit << ") {" << endl;
  337.             switchfns::spec(bit);
  338.             cout << "}" << endl;
  339.         }
  340.     }
  341. }
  342. #endif
  343.  
  344. #ifdef MAIN
  345. int main () {
  346. #ifdef SPECS
  347.     specs::print();
  348. #endif
  349. #ifdef BENCH
  350.     bench::simplebenchmark ();
  351. #endif
  352.     return 0;
  353. }
  354. #endif
clone this paste RAW Paste Data