Guest User

Decay-based count

a guest
Aug 1st, 2017
244
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /* Copyright (c) 2017, Qrator Labs */
  2. /* All rights reserved. */
  3.  
  4. /* Redistribution and use in source and binary forms, with or without */
  5. /* modification, are permitted provided that the following conditions are met: */
  6.  
  7. /* 1. Redistributions of source code must retain the above copyright notice, this */
  8. /*    list of conditions and the following disclaimer. */
  9. /* 2. Redistributions in binary form must reproduce the above copyright notice, */
  10. /*    this list of conditions and the following disclaimer in the documentation */
  11. /*    and/or other materials provided with the distribution. */
  12.  
  13. /* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND */
  14. /* ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED */
  15. /* WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE */
  16. /* DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR */
  17. /* ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES */
  18. /* (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; */
  19. /* LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND */
  20. /* ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT */
  21. /* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS */
  22. /* SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. */
  23.  
  24. /* The views and conclusions contained in the software and documentation are those */
  25. /* of the authors and should not be interpreted as representing official policies, */
  26. /* either expressed or implied, of the FreeBSD Project. */
  27.  
  28. #include <stdio.h>
  29. #include <stdlib.h>
  30. #include <stdint.h>
  31. #include <unistd.h>
  32. #include <math.h>
  33.  
  34. static inline uint64_t rdtsc(void) {
  35.   union {
  36.     uint64_t tsc_64;
  37.     struct {
  38.       uint32_t lo_32;
  39.       uint32_t hi_32;
  40.     };
  41.   } tsc;
  42.   asm volatile("rdtsc" :
  43.                "=a" (tsc.lo_32),
  44.                "=d" (tsc.hi_32));
  45.   return tsc.tsc_64;
  46. }
  47.  
  48. /* global config and other global stuff */
  49. struct {
  50.   double tau;
  51.   uint64_t tVanish;
  52.   uint16_t *rho_table; /* NB: tau must be no more than (1<<16) */
  53.  
  54. #if !defined(DECAY_MODEL)
  55.   double powers[64];
  56.   double beta_1;
  57. #endif
  58. } g;
  59.  
  60. int ratedet_init(double tau);
  61. void ratedet_finalize();
  62.  
  63. int main(int argc, char **argv) {
  64.   int nIters = 100000000;
  65.   int nRounds = 1;
  66.   switch(argc) {
  67.   case 3:
  68.     nRounds = atoi(argv[2]);
  69.   case 2:
  70.     nIters = atoi(argv[1]);
  71.   case 1:
  72.     break;
  73.   default:
  74.     printf("usage: %s [nIters] [nRounds]\n", argv[0]);
  75.     exit(1);
  76.   }
  77.  
  78.   if(ratedet_init(1<<16))
  79.     exit(1);
  80.  
  81.   printf("tau: %lf", g.tau);
  82. #ifdef DECAY_MODEL
  83.   printf(", tVanish: %lu; %u...%u", g.tVanish, g.rho_table[0], g.rho_table[g.tVanish-1]);
  84. #else
  85. #ifdef MAXDELTA
  86.   printf(", maxDelta: %u, accuracy: %lg", MAXDELTA, exp(-MAXDELTA/g.tau)/g.beta_1);
  87. #else
  88.   printf(", maxDelta: <unused>");
  89. #endif
  90. #endif
  91.   printf("\n");
  92.  
  93.   uint64_t t = rdtsc();
  94.   sleep(1);
  95.   t = rdtsc() - t;
  96.   const double freq = (double)t;
  97.  
  98.   uint64_t minT = ~0UL;
  99.   double sT = 0.;
  100.  
  101.   int iter, round;
  102.   for(round=0; round<nRounds; ++round) {
  103. #ifdef DECAY_MODEL
  104.     uint64_t currTime = g.tVanish;
  105.     uint64_t value = 0;
  106. #else
  107.     uint64_t currTime = 0;
  108.     uint64_t accTime = 0;
  109.     double accValue = 0.;
  110. #endif
  111.     t = rdtsc();
  112.     uint64_t tStep = 1000;
  113.     for(iter=0; iter<nIters; ++iter) {
  114.       /* FIXME: rdtsc() is too slow for this test */
  115. #if 0
  116.       currTime = rdtsc();
  117. #else
  118.       currTime = currTime + tStep;
  119.       tStep = (tStep + 123) & 0xfff;
  120. #endif
  121. #ifdef DECAY_MODEL
  122.       /* update */
  123.       {
  124.         const int64_t dt = labs(value - currTime);
  125.         const int64_t offset = dt > g.tVanish ? g.tVanish : dt;
  126.         const uint64_t maxt = value < currTime ? currTime : value;
  127.         value = maxt + g.rho_table[offset];
  128.       }
  129. #else
  130.       /* update */
  131.       {
  132.         uint64_t delta = currTime - accTime;
  133.         accTime = currTime;
  134.  
  135. #ifdef MAXDELTA
  136.         if(delta >= MAXDELTA)
  137.           {
  138.             accValue = g.beta_1;
  139.           }
  140.         else
  141. #endif
  142.           {
  143.             const double *ppow = g.powers;
  144.             for (; delta != 0; ++ppow, delta >>= 1) {
  145.               if (delta & 1)
  146.                 accValue *= *ppow;
  147.             }
  148.             accValue += g.beta_1;
  149.           }
  150.       }
  151. #endif
  152.     }
  153.     t = rdtsc() - t;
  154.  
  155.     if(0 == round) {
  156.       /* This should be approximately the same for both versions */
  157.       const double total =
  158. #ifdef DECAY_MODEL
  159.         exp((value-currTime)/(double)g.tau)
  160. #else
  161.         accValue/g.beta_1
  162. #endif
  163.         ;
  164.       printf("total value: %lf\n", total);
  165.     }
  166.  
  167.     sT += t;
  168.     if(t < minT) minT = t;
  169.   }
  170.  
  171.   const double meanT = sT/nRounds;
  172.   printf("freq: %g MHz, iter time (best/mean): %lf/%lf cycles, rate (best/mean): %g/%g Miter/s\n",
  173.          freq*1e-6,
  174.          (double)minT/nIters, (double)meanT/nIters,
  175.          freq/(double)minT*nIters*1e-6, freq/(double)meanT*nIters*1e-6);
  176.  
  177.   ratedet_finalize();
  178.   return 0;
  179. }
  180.  
  181. static double rho(double x) {
  182.   return log(1. + exp(-x));
  183. }
  184.  
  185. int ratedet_init(double tau) {
  186.   g.tau = tau;
  187.   g.tVanish = - tau * log(exp(.5/tau) - 1.);
  188.   g.rho_table = (uint16_t*)malloc(g.tVanish * sizeof(uint16_t));
  189.   if(!g.rho_table) return -1;
  190.   uint64_t i;
  191.   for(i=0; i<g.tVanish; ++i)
  192.     g.rho_table[i] = .5 + tau * rho((double)i/tau);
  193.  
  194. #if !defined(DECAY_MODEL)
  195.   const double beta = exp(-1./(double)tau);
  196.   g.beta_1 = 1 - beta;
  197.   double tmp = beta;
  198.   for(i=0; i<64;++i) {
  199.     g.powers[i] = tmp;
  200.     tmp *= tmp;
  201.   }
  202. #endif
  203.  
  204.   return 0;
  205. }
  206.  
  207. void ratedet_finalize() {
  208.   if(g.rho_table)
  209.     free(g.rho_table);
  210. }
RAW Paste Data