home *** CD-ROM | disk | FTP | other *** search
/ Source Code 1992 March / Source_Code_CD-ROM_Walnut_Creek_March_1992.iso / usenet / altsrcs / 1 / 1948 < prev    next >
Encoding:
Text File  |  1990-12-28  |  21.2 KB  |  740 lines
  1. Newsgroups: alt.sources
  2. From: chris@mimsy.umd.edu (Chris Torek)
  3. Subject: [comp.lang.c] Re: count of bits in a long
  4. Message-ID: <1990Oct13.181313.25964@math.lsa.umich.edu>
  5. Date: Sat, 13 Oct 90 18:13:13 GMT
  6.  
  7. Archive-name: bct/13-Oct-90
  8. Original-posting-by: chris@mimsy.umd.edu (Chris Torek)
  9. Original-subject: Re: count of bits in a long
  10. Reposted-by: emv@math.lsa.umich.edu (Edward Vielmetti)
  11.  
  12. [Reposted from comp.lang.c.
  13. Comments on this service to emv@math.lsa.umich.edu (Edward Vielmetti).]
  14.  
  15. In article <26881@mimsy.umd.edu> I posted a modified version of
  16. Peter Miller's bit-count timing program.  Unfortunately, my version
  17. had a bug that effectively makes the results worthless (depending
  18. on compiler vagaries; it `just happens' to compile to working code
  19. on some systems).
  20.  
  21. Remarkably few people noted the bug (or rather, sent me mail about it).
  22. Two people sent me additional functions, however.  Arthur Olson added
  23. four (all variants on table lookup); Mike Weaver added one.  Gene Olson
  24. has also posted a different modified version of Peter Miller's original
  25. program; this contains a better version of the latter.
  26.  
  27. So, here are new results for the new set of (now 17) functions on the
  28. same set of machines, along with the new program.  Noteworthy facts:
  29.  
  30.   - hackmem invariably loses to some other technique, always including
  31.     Gene Olson's, though sometimes not by much;
  32.   - the fastest is usually (but not always) one of the table lookups;
  33.   - tiny differences in ratios (less than .1) are usually insignificant.
  34.  
  35.   name              technique used
  36.   ----              --------------
  37. hackmemmod        HACKMEM 169, using % operator
  38. hackmemloop        HACKMEM 169, using loop to implement %
  39. hackmemunrolled        HACKMEM 169, with 5-step % (loop unrolled)
  40. rmlsbsub        remove lsb with `n -= (n & -n)'
  41. rmlsbmask        remove lsb with `n &= n - 1'
  42. testlsb            test n&1, then n>>=1
  43. testmsb            test n&MSB, then n+=n (rather than n<<=1)
  44. testsignandshift    test n<0, then n<<=1
  45. testeachbit        test n&mask, then mask+=mask
  46. testeachbit1shl        test n&(1<<bit) for bit in [0..32)
  47. tableshift        nbits[n>>24] + nbits[(n>>16)&255] ...
  48. tableuchar        set p=&n, nbits[p[0]] + nbits[p[1]] ...
  49. tableshiftcast        nbits[n>>24] + nbits[(u_char)(n>>16)] ...
  50. itableshift        same as tableshift, but table datatype is int
  51. itableuchar        ditto
  52. itableshiftcast        ditto (note, nbits table is `char')
  53. sumbits            Gene Olson's function (see code for comments)
  54.  
  55. ------------------------------------------------------------
  56. Results:
  57.  
  58. ::::::::::::::
  59. time.ds3100
  60. ::::::::::::::
  61. function                   time          ratio
  62. hackmemmod               3.0992432e-06   3.250
  63. hackmemloop              2.5330353e-06   2.656
  64. hackmemunrolled          1.7619495e-06   1.848
  65. rmlsbsub                 4.9207935e-06   5.160
  66. rmlsbmask                3.9522800e-06   4.145
  67. testlsb                  1.0545622e-05  11.059
  68. testmsb                  1.0608948e-05  11.125
  69. testsignandshift         1.0497196e-05  11.008
  70. testeachbit              1.0839901e-05  11.367
  71. testeachbit1shl          1.6718033e-05  17.531
  72. tableshift               1.0243893e-06   1.074
  73. tableuchar               9.5361328e-07   1.000
  74. tableshiftcast           1.1063404e-06   1.160
  75. itableshift              1.2814178e-06   1.344
  76. itableuchar              1.2031918e-06   1.262
  77. itableshiftcast          1.3223934e-06   1.387
  78. sumbits                  1.2106419e-06   1.270
  79. ::::::::::::::
  80. time.encore
  81. ::::::::::::::
  82. function                   time          ratio
  83. hackmemmod               8.0387573e-06   4.522
  84. hackmemloop              7.2727394e-06   4.091
  85. hackmemunrolled          4.3494453e-06   2.447
  86. rmlsbsub                 1.0656597e-05   5.994
  87. rmlsbmask                1.1298252e-05   6.355
  88. testlsb                  3.1122246e-05  17.506
  89. testmsb                  2.2745319e-05  12.794
  90. testsignandshift         1.9783443e-05  11.128
  91. testeachbit              2.3917282e-05  13.454
  92. testeachbit1shl          2.9880619e-05  16.808
  93. tableshift               3.9419632e-06   2.217
  94. tableuchar               2.6934662e-06   1.515
  95. tableshiftcast           2.3953590e-06   1.347
  96. itableshift              3.0450325e-06   1.713
  97. itableuchar              1.7777634e-06   1.000
  98. itableshiftcast          2.1755104e-06   1.224
  99. sumbits                  1.9636650e-06   1.105
  100. ::::::::::::::
  101. time.sun3
  102. ::::::::::::::
  103. function                   time          ratio
  104. hackmemmod               1.0604858e-05   2.106
  105. hackmemloop              1.2664795e-05   2.515
  106. hackmemunrolled          1.0833740e-05   2.152
  107. rmlsbsub                 2.2430420e-05   4.455
  108. rmlsbmask                1.7318726e-05   3.439
  109. testlsb                  4.3182373e-05   8.576
  110. testmsb                  3.8909912e-05   7.727
  111. testsignandshift         4.0664673e-05   8.076
  112. testeachbit              4.4479370e-05   8.833
  113. testeachbit1shl          5.9432983e-05  11.803
  114. tableshift               9.9945068e-06   1.985
  115. tableuchar               1.0910034e-05   2.167
  116. tableshiftcast           1.4877319e-05   2.955
  117. itableshift              7.9345703e-06   1.576
  118. itableuchar              1.1672974e-05   2.318
  119. itableshiftcast          1.1520386e-05   2.288
  120. sumbits                  5.0354004e-06   1.000
  121. ::::::::::::::
  122. time.sun4
  123. ::::::::::::::
  124. function                   time          ratio
  125. hackmemmod               1.3427734e-05  19.288
  126. hackmemloop              1.6689301e-06   2.397
  127. hackmemunrolled          1.0585785e-06   1.521
  128. rmlsbsub                 3.9768219e-06   5.712
  129. rmlsbmask                3.4236908e-06   4.918
  130. testlsb                  8.4209442e-06  12.096
  131. testmsb                  8.4686279e-06  12.164
  132. testsignandshift         8.4018707e-06  12.068
  133. testeachbit              8.5353851e-06  12.260
  134. testeachbit1shl          1.1539459e-05  16.575
  135. tableshift               6.9618225e-07   1.000
  136. tableuchar               1.1348724e-06   1.630
  137. tableshiftcast           7.8201294e-07   1.123
  138. itableshift              9.7274780e-07   1.397
  139. itableuchar              1.2016296e-06   1.726
  140. itableshiftcast          8.8691711e-07   1.274
  141. sumbits                  8.3923340e-07   1.205
  142. ::::::::::::::
  143. time.vax.gcc
  144. ::::::::::::::
  145. function                   time          ratio
  146. hackmemmod               1.5449524e-05   7.364
  147. hackmemloop              1.3847351e-05   6.600
  148. hackmemunrolled          8.6975098e-06   4.145
  149. rmlsbsub                 1.8386841e-05   8.764
  150. rmlsbmask                1.4266968e-05   6.800
  151. testlsb                  5.3215027e-05  25.364
  152. testmsb                  3.4332275e-05  16.364
  153. testsignandshift         2.6550293e-05  12.655
  154. testeachbit              2.9983521e-05  14.291
  155. testeachbit1shl          4.7454834e-05  22.618
  156. tableshift               5.3405762e-06   2.545
  157. tableuchar               2.4414062e-06   1.164
  158. tableshiftcast           6.0272217e-06   2.873
  159. itableshift              4.3106079e-06   2.055
  160. itableuchar              2.0980835e-06   1.000
  161. itableshiftcast          5.6076050e-06   2.673
  162. sumbits                  5.7983398e-06   2.764
  163. ::::::::::::::
  164. time.vax.ucbcc
  165. ::::::::::::::
  166. function                   time          ratio
  167. hackmemmod               7.6293945e-06   3.774
  168. hackmemloop              1.6746521e-05   8.283
  169. hackmemunrolled          1.3504028e-05   6.679
  170. rmlsbsub                 2.0332336e-05  10.057
  171. rmlsbmask                1.8882751e-05   9.340
  172. testlsb                  5.6457520e-05  27.925
  173. testmsb                  3.7384033e-05  18.491
  174. testsignandshift         2.9602051e-05  14.642
  175. testeachbit              3.8681030e-05  19.132
  176. testeachbit1shl          5.8860779e-05  29.113
  177. tableshift               5.6838989e-06   2.811
  178. tableuchar               2.2888184e-06   1.132
  179. tableshiftcast           5.1879883e-06   2.566
  180. itableshift              4.3487549e-06   2.151
  181. itableuchar              2.0217896e-06   1.000
  182. itableshiftcast          4.5394897e-06   2.245
  183. sumbits                  6.1798096e-06   3.057
  184.  
  185. ------------------------------------------------------------
  186. The program (and I used lint this time...):
  187.  
  188. #ifndef lint
  189. static char rcsid[] = "$Id: bct.c,v 1.5 90/10/13 08:44:12 chris Exp $";
  190. #endif
  191.  
  192. /*
  193.  * bct - bitcount timing
  194.  *
  195.  * Runs a bunch of different functions-to-count-bits-in-a-longword
  196.  * (many assume 32 bits per long) with a timer around each loop, and
  197.  * tries to calcuate the time used.
  198.  */
  199. #include <stdio.h>
  200. #include <sys/types.h>
  201.  
  202. #ifdef FD_SETSIZE
  203. # define USE_GETRUSAGE
  204. # include <sys/time.h>
  205. # include <sys/resource.h>
  206. #else
  207. # include <sys/times.h>
  208. #endif
  209.  
  210. #define SIZEOF(a) (sizeof(a)/sizeof(a[0]))
  211.  
  212.  
  213. /*
  214.  * This function is used to calibrate the timing mechanism.
  215.  * This way we can subtract the loop and call overheads.
  216.  */
  217. int
  218. calibrate(n)
  219.     register unsigned long n;
  220. {
  221.     return 0;
  222. }
  223.  
  224.  
  225. /*
  226.  * This function counts the number of bits in a long.
  227.  * It is limited to 63 bit longs, but a minor mod can cope with 511 bits.
  228.  *
  229.  * It is so magic, an explanation is required:
  230.  * Consider a 3 bit number as being
  231.  *    4a+2b+c
  232.  * if we shift it right 1 bit, we have
  233.  *    2a+b
  234.  * subtracting this from the original gives
  235.  *    2a+b+c
  236.  * if we shift the original 2 bits right we get
  237.  *    a
  238.  * and so with another subtraction we have
  239.  *    a+b+c
  240.  * which is the number of bits in the original number.
  241.  * Suitable masking allows the sums of the octal digits in a
  242.  * 32 bit number to appear in each octal digit.  This isn't much help
  243.  * unless we can get all of them summed together.
  244.  * This can be done by modulo arithmetic (sum the digits in a number by molulo
  245.  * the base of the number minus one) the old "casting out nines" trick they
  246.  * taught in school before calculators were invented.
  247.  * Now, using mod 7 wont help us, because our number will very likely have
  248.  * more than 7 bits set.  So add the octal digits together to get base64
  249.  * digits, and use modulo 63.
  250.  * (Those of you with 64 bit machines need to add 3 octal digits together to
  251.  * get base512 digits, and use mod 511.)
  252.  *
  253.  * This is HACKMEM 169, as used in X11 sources.
  254.  */
  255. int
  256. t0_hackmemmod(n)
  257.     register unsigned long n;
  258. {
  259.     register unsigned long tmp;
  260.  
  261.     tmp = n - ((n >> 1) & 033333333333) - ((n >> 2) & 011111111111);
  262.     return ((tmp + (tmp >> 3)) & 030707070707) % 63;
  263. }
  264.  
  265.  
  266. /*
  267.  * This is the same as the above, but does not use the % operator.
  268.  * Most modern machines have clockless division, and so the modulo is as
  269.  * expensive as, say, an addition.
  270.  */
  271. int
  272. t1_hackmemloop(n)
  273.     register unsigned long n;
  274. {
  275.     register unsigned long tmp;
  276.  
  277.     tmp = n - ((n >> 1) & 033333333333) - ((n >> 2) & 011111111111);
  278.     tmp = (tmp + (tmp >> 3)) & 030707070707;
  279.     while (tmp > 63)
  280.         tmp = (tmp & 63) + (tmp >> 6);
  281.     return tmp;
  282. }
  283.  
  284. /*
  285.  * Above, without using while loop.  It takes at most 5 iterations of the
  286.  * loop, so we just do all 5 in-line.  The final result is never 63
  287.  * (this is assumed above as well).
  288.  */
  289. int
  290. t2_hackmemunrolled(n)
  291.     register unsigned long n;
  292. {
  293.     register unsigned long tmp;
  294.  
  295.     tmp = n - ((n >> 1) & 033333333333) - ((n >> 2) & 011111111111);
  296.     tmp = (tmp + (tmp >> 3)) & 030707070707;
  297.     tmp = (tmp & 63) + (tmp >> 6);
  298.     tmp = (tmp & 63) + (tmp >> 6);
  299.     tmp = (tmp & 63) + (tmp >> 6);
  300.     tmp = (tmp & 63) + (tmp >> 6);
  301.     tmp = (tmp & 63) + (tmp >> 6);
  302.     return (tmp);
  303. }
  304.  
  305.  
  306. /*
  307.  * This function counts the bits in a long.
  308.  *
  309.  * It removes the lsb and counting the number of times round the loop.
  310.  * The expression (n & -n) yields the lsb of a number,
  311.  * but it only works on 2's compliment machines.
  312.  */
  313. int
  314. t3_rmlsbsub(n)
  315.     register unsigned long n;
  316. {
  317.     register int count;
  318.  
  319.     for (count = 0; n; n -= (n & -n))
  320.         count++;
  321.     return count;
  322. }
  323.  
  324. int
  325. t4_rmlsbmask(n)
  326.     register unsigned long n;
  327. {
  328.     register int count;
  329.  
  330.     for (count = 0; n; count++)
  331.         n &= n - 1;    /* take away lsb */
  332.     return (count);
  333. }
  334.  
  335. /*
  336.  * This function counts the bits in a long.
  337.  *
  338.  * It works by shifting the number down and testing the bottom bit.
  339.  */
  340. int
  341. t5_testlsb(n)
  342.     register unsigned long n;
  343. {
  344.     register int count;
  345.  
  346.     for (count = 0; n; n >>= 1)
  347.         if (n & 1)
  348.             count++;
  349.     return count;
  350. }
  351.  
  352. /*
  353.  * This function counts the bits in a long.
  354.  *
  355.  * It works by shifting the number left and testing the top bit.
  356.  * On many machines shift is expensive, so it uses a cheap addition instead.
  357.  */
  358. int
  359. t6_testmsb(n)
  360.     register unsigned long n;
  361. {
  362.     register int count;
  363.  
  364.     for (count = 0; n; n += n)
  365.         if (n & ~(~(unsigned long)0 >> 1))
  366.             count++;
  367.     return count;
  368. }
  369.  
  370. int
  371. t7_testsignandshift(n)
  372.     register unsigned long n;
  373. {
  374.     register int count;
  375.  
  376.     for (count = 0; n; n <<= 1)
  377.         if ((long)n < 0)
  378.             count++;
  379.     return (count);
  380. }
  381.  
  382.  
  383. /*
  384.  * This function counts the bits in a long.
  385.  *
  386.  * It works by masking each bit.
  387.  * This is the second most intuitively obvious method,
  388.  * and is independent of the number of bits in the long.
  389.  */
  390. int
  391. t8_testeachbit(n)
  392.     register unsigned long n;
  393. {
  394.     register int count;
  395.     register unsigned long mask;
  396.  
  397.     count = 0;
  398.     for (mask = 1; mask; mask += mask)
  399.         if (n & mask)
  400.             count++;
  401.     return count;
  402. }
  403.  
  404.  
  405. /*
  406.  * This function counts the bits in a long.
  407.  *
  408.  * It works by masking each bit.
  409.  * This is the most intuitively obvious method,
  410.  * but how do you a priori know how many bits in the long?
  411.  * (except for ''sizeof(long) * CHAR_BITS'' expression)
  412.  */
  413. int
  414. t9_testeachbit1shl(n)
  415.     register unsigned long n;
  416. {
  417.     register int count;
  418.     register int bit;
  419.  
  420.     count = 0;
  421.     for (bit = 0; bit < 32; ++bit)
  422.         if (n & ((unsigned long)1 << bit))
  423.             count++;
  424.     return count;
  425. }
  426.  
  427. static char nbits[256] = {
  428.     0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
  429.     1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
  430.     1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
  431.     2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
  432.     1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
  433.     2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
  434.     2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
  435.     3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
  436.     1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
  437.     2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
  438.     2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
  439.     3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
  440.     2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
  441.     3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
  442.     3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
  443.     4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8,
  444. };
  445.  
  446. static int inbits[256] = {
  447.     0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
  448.     1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
  449.     1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
  450.     2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
  451.     1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
  452.     2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
  453.     2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
  454.     3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
  455.     1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
  456.     2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
  457.     2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
  458.     3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
  459.     2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
  460.     3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
  461.     3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
  462.     4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8,
  463. };
  464.  
  465. int
  466. tA_tableshift(n)
  467.     register unsigned long n;
  468. {
  469.  
  470.     return (nbits[n & 0xff] + nbits[(n >> 8) & 0xff] +
  471.         nbits[(n >> 16) & 0xff] + nbits[n >> 24]);
  472. }
  473.  
  474. int
  475. tB_tableuchar(n)
  476.     unsigned long n;
  477. {
  478.     register unsigned char *p = (unsigned char *)&n;
  479.  
  480.     return (nbits[p[0]] + nbits[p[1]] + nbits[p[2]] + nbits[p[3]]);
  481. }
  482.  
  483. int
  484. tC_tableshiftcast(n)
  485.     register unsigned long n;
  486. {
  487.  
  488.     return nbits[(unsigned char) n] +
  489.         nbits[(unsigned char) (n >> 8)] +
  490.         nbits[(unsigned char) (n >> 16)] +
  491.         nbits[(unsigned char) (n >> 24)];
  492. }
  493.  
  494. int
  495. tD_itableshift(n)
  496.     register unsigned long n;
  497. {
  498.  
  499.     return (inbits[n & 0xff] + inbits[(n >> 8) & 0xff] +
  500.         inbits[(n >> 16) & 0xff] + inbits[n >> 24]);
  501. }
  502.  
  503. int
  504. tE_itableuchar(n)
  505.     unsigned long n;
  506. {
  507.     register unsigned char *p = (unsigned char *)&n;
  508.  
  509.     return (inbits[p[0]] + inbits[p[1]] + inbits[p[2]] + inbits[p[3]]);
  510. }
  511.  
  512. int
  513. tF_itableshiftcast(n)
  514.     register unsigned long n;
  515. {
  516.  
  517.     return inbits[(unsigned char) n] +
  518.         inbits[(unsigned char) (n >> 8)] +
  519.         inbits[(unsigned char) (n >> 16)] +
  520.         inbits[(unsigned char) (n >> 24)];
  521. }
  522.  
  523. /*
  524.  * Explanation:
  525.  * First we add 32 1-bit fields to get 16 2-bit fields.
  526.  * Each 2-bit field is one of 00, 01, or 10 (binary).
  527.  * We then add all the two-bit fields to get 8 4-bit fields.
  528.  * These are all one of 0000, 0001, 0010, 0011, or 0100.
  529.  *
  530.  * Now we can do something different, becuase for the first
  531.  * time the value in each k-bit field (k now being 4) is small
  532.  * enough that adding two k-bit fields results in a value that
  533.  * still fits in the k-bit field.  The result is four 4-bit
  534.  * fields containing one of {0000,0001,...,0111,1000} and four
  535.  * more 4-bit fields containing junk (sums that are uninteresting).
  536.  * Pictorially:
  537.  *        n = 0aaa0bbb0ccc0ddd0eee0fff0ggg0hhh
  538.  *     n>>4 = 00000aaa0bbb0ccc0ddd0eee0fff0ggg
  539.  *      sum = 0aaaWWWWiiiiXXXXjjjjYYYYkkkkZZZZ
  540.  * where W, X, Y, and Z are the interesting sums (each at most 1000,
  541.  * or 8 decimal).  Masking with 0x0f0f0f0f extracts these.
  542.  *
  543.  * Now we can change tactics yet again, because now we have:
  544.  *        n = 0000WWWW0000XXXX0000YYYY0000ZZZZ
  545.  *     n>>8 = 000000000000WWWW0000XXXX0000YYYY
  546.  * so      sum = 0000WWWW000ppppp000qqqqq000rrrrr
  547.  * where p and r are the interesting sums (and each is at most
  548.  * 10000, or 16 decimal).  The sum `q' is junk, like i, j, and
  549.  * k above; but it is not necessarry to discard it this time.
  550.  * One more fold, this time by sixteen bits, gives
  551.  *        n = 0000WWWW000ppppp000qqqqq000rrrrr
  552.  *    n>>16 = 00000000000000000000WWWW000ppppp
  553.  * so      sum = 0000WWWW000ppppp000sssss00tttttt
  554.  * where s is at most 11000 and t is it most 100000 (32 decimal).
  555.  *
  556.  * Now we have t = r+p = (Z+Y)+(X+W) = ((h+g)+(f+e))+((d+c)+(b+a)),
  557.  * or in other words, t is the number of bits set in the original
  558.  * 32-bit longword.  So all we have to do is return the low byte
  559.  * (or low 6 bits, but `low byte' is typically just as easy if not
  560.  * easier).
  561.  *
  562.  * This technique is also applicable to 64 and 128 bit words, but
  563.  * 256 bit or larger word sizes require at least one more masking
  564.  * step.
  565.  */
  566. int
  567. tG_sumbits(n)
  568.     register unsigned long n;
  569. {
  570.  
  571.     n = (n & 0x55555555) + ((n >> 1) & 0x55555555);
  572.     n = (n & 0x33333333) + ((n >> 2) & 0x33333333);
  573.     n = (n + (n >> 4)) & 0x0f0f0f0f;
  574.     n += n >> 8;
  575.     n += n >> 16;
  576.     return (n & 0xff);
  577. }
  578.  
  579. /*
  580.  * build a long random number.
  581.  * The standard rand() returns at least a 15 bit number.
  582.  * We use the top 9 of 15 (since the lower N bits of the usual rand()
  583.  * repeat with a period of 2^N).
  584.  */
  585. unsigned long
  586. bigrand()
  587. {
  588. #define randbits() ((unsigned long)((rand() >> 6) & 0777))
  589.     register int r;
  590.  
  591.     r = randbits() << 27;
  592.     r |= randbits() << 18;
  593.     r |= randbits() << 9;
  594.     r |= randbits();
  595.     return (r);
  596. }
  597.  
  598. /*
  599.  * Run the test many times.
  600.  * You will need a running time in the 10s of seconds
  601.  * for an accurate result.
  602.  *
  603.  * To give a fair comparison, the random number generator
  604.  * is seeded the same for each measurement.
  605.  *
  606.  * Return value is seconds per iteration.
  607.  */
  608. #ifndef REPEAT
  609. #if defined(mips) || defined(sparc)
  610. #define REPEAT (1L<<20)
  611. #else
  612. #define REPEAT (1L<<18)
  613. #endif
  614. #endif
  615.  
  616. double
  617. measure(func)
  618.     register int    (*func)();
  619. {
  620. #ifdef USE_GETRUSAGE
  621.     struct rusage ru0, ru1;
  622.     register long j;
  623.  
  624.     srand(1);
  625.     (void) getrusage(RUSAGE_SELF, &ru0);
  626.     for (j = 0; j < REPEAT; ++j)
  627.         func(bigrand());
  628.     (void) getrusage(RUSAGE_SELF, &ru1);
  629.     ru1.ru_utime.tv_sec -= ru0.ru_utime.tv_sec;
  630.     if ((ru1.ru_utime.tv_usec -= ru0.ru_utime.tv_usec) < 0) {
  631.         ru1.ru_utime.tv_usec += 1000000;
  632.         ru1.ru_utime.tv_sec--;
  633.     }
  634.     return ((ru1.ru_utime.tv_sec + (ru1.ru_utime.tv_usec / 1000000.0)) /
  635.         (double)REPEAT);
  636. #else
  637.     register long    j;
  638.     struct tms    start;
  639.     struct tms    finish;
  640.  
  641.     srand(1);
  642.     times(&start);
  643.     for (j = 0; j < REPEAT; ++j)
  644.         func(bigrand());
  645.     times(&finish);
  646.     return ((finish.tms_utime - start.tms_utime) / (double)REPEAT);
  647. #endif
  648. }
  649.  
  650. struct table {
  651.     char    *name;
  652.     int    (*func)();
  653.     double    measurement;
  654.     int    trial;
  655. };
  656.  
  657. struct table    table[] =
  658. {
  659.     { "hackmemmod",        t0_hackmemmod },
  660.     { "hackmemloop",     t1_hackmemloop },
  661.     { "hackmemunrolled",    t2_hackmemunrolled },
  662.     { "rmlsbsub",         t3_rmlsbsub },
  663.     { "rmlsbmask",         t4_rmlsbmask },
  664.     { "testlsb",        t5_testlsb },
  665.     { "testmsb",         t6_testmsb },
  666.     { "testsignandshift",     t7_testsignandshift },
  667.     { "testeachbit",     t8_testeachbit },
  668.     { "testeachbit1shl",     t9_testeachbit1shl },
  669.     { "tableshift",     tA_tableshift },
  670.     { "tableuchar",     tB_tableuchar },
  671.     { "tableshiftcast",    tC_tableshiftcast },
  672.     { "itableshift",     tD_itableshift },
  673.     { "itableuchar",     tE_itableuchar },
  674.     { "itableshiftcast",    tF_itableshiftcast },
  675.     { "sumbits",        tG_sumbits },
  676. };
  677.  
  678. main(argc, argv)
  679.     int argc;
  680.     char **argv;
  681. {
  682.     double calibration, v, best;
  683.     int j, k, m, verbose;
  684.  
  685.     verbose = argc > 1;
  686.     /*
  687.      * run a few tests to make sure they all agree
  688.      */
  689.     srand(getpid());
  690.     for (j = 0; j < 10; ++j) {
  691.         unsigned long n;
  692.         int bad;
  693.  
  694.         n = bigrand();
  695.         for (k = 0; k < SIZEOF(table); ++k)
  696.             table[k].trial = table[k].func(n);
  697.         bad = 0;
  698.         for (k = 0; k < SIZEOF(table); ++k)
  699.             for (m = 0; m < SIZEOF(table); ++m)
  700.                 if (table[k].trial != table[m].trial)
  701.                     bad = 1;
  702.         if (bad) {
  703.             printf("wrong: %08lX", n);
  704.             for (k = 0; k < SIZEOF(table); ++k)
  705.                 printf(" %3d", table[k].trial);
  706.             printf("\n");
  707.         }
  708.     }
  709.  
  710.     /*
  711.      * calibrate the timing mechanism
  712.      */
  713.     calibration = measure(calibrate);
  714.     if (verbose)
  715.         printf("calibration: %g\n", calibration);
  716.  
  717.     /*
  718.      * time them all, keeping track of the best (smallest)
  719.      */
  720.     for (j = 0; j < SIZEOF(table); ++j) {
  721.         v = measure(table[j].func) - calibration;
  722.         if (verbose)
  723.             printf("%s: %g\n", table[j].name, v);
  724.         table[j].measurement = v;
  725.         if (!j || v < best)
  726.             best = v;
  727.     }
  728.     (void) printf("%-24s   %-14sratio\n", "function", "time");
  729.     for (j = 0; j < SIZEOF(table); ++j) {
  730.         (void) printf("%-24s %#10.8g  %6.3f\n",
  731.             table[j].name,
  732.             table[j].measurement,
  733.             table[j].measurement / best);
  734.     }
  735.     exit(0);
  736. }
  737. -- 
  738. In-Real-Life: Chris Torek, Univ of MD Comp Sci Dept (+1 301 405 2750)
  739. Domain:    chris@cs.umd.edu    Path:    uunet!mimsy!chris
  740.