Don't like ads? PRO users don't see any ads ;-)
Public Pastes
Guest

Untitled

By: AlexMatveev on Oct 7th, 2012  |  syntax: C  |  size: 2.79 KB  |  hits: 171  |  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. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. long long TimeValue=0;
  5.  
  6. unsigned long long time_RDTSC(){
  7.   union ticks{
  8.         unsigned long long tx;
  9.     struct dblword { long tl,th; } dw; // little endian
  10.   } t;
  11.   asm("rdtsc\n": "=a"(t.dw.tl),"=d"(t.dw.th));
  12.   return t.tx;
  13. } // for x86 only!
  14.  
  15. void time_start() { TimeValue=time_RDTSC(); }
  16.  
  17. long long time_stop() { return time_RDTSC()-TimeValue; }
  18.  
  19. void swap(int *a, int *b){
  20.         int c = *a;
  21.         *a = *b;
  22.         *b = c;
  23. }
  24. void Snuffle(int array[], int n){
  25.         int i;
  26.         for (i = 0; i < n; i++)
  27.                 swap(array + i, array + (rand() % n));
  28. }
  29.  
  30. void ForwardInit(int array[], int n){
  31.         int i;
  32.         array[n-1] = 0;
  33.         for(i = 0; i < n -1; i++)
  34.                 array[i]=i+1;
  35. }
  36.  
  37. void BackwardInit(int array[], int n){
  38.         int i;
  39.         array[0] = n-1;
  40.         for (i = 0; i < n; i++)
  41.                 array[i+1] = i;
  42. }
  43.  
  44. void RandomInit(int array[],  int n){
  45.         int i;
  46.         int *TempArray;
  47.         TempArray = (int *)calloc(n,  sizeof(int));
  48.         ForwardInit(TempArray, n);
  49.         Snuffle(TempArray, n);
  50.         for(i = 0; i < n; i++)
  51.                 array[TempArray[i]] = TempArray[i+1];
  52.         array[TempArray[n-1]] = TempArray[0];
  53.         free(TempArray);
  54. }
  55.  
  56. long long CalculateSum(int array[], int n){
  57.         long long sum = 0;
  58.         long long x = array[0];
  59.         int count = 0;
  60.         while(count < n){
  61.           sum+=array[x];
  62.           x = array[x];
  63.           if (x==array[0])
  64.                 count++;
  65.         }
  66.         return sum;
  67. }
  68.  
  69. int main(){
  70.         int cycles = 10;
  71.         int n=10;
  72.         long long sum;
  73.         long long time;
  74.         int i;
  75.         int *array;
  76.         for(n = 1024/sizeof(int); n <1024*1024/(sizeof(int)); n+=1024/sizeof(int)){
  77.                 array = (int *)calloc(n, sizeof(int));
  78.        
  79.                 CalculateSum(array,  1);
  80.  
  81.                 ForwardInit(array, n);
  82.                 time_start();
  83.                 sum = CalculateSum(array, cycles);
  84.                 time = time_stop();
  85.                 printf("%lld ",  time/(n*sizeof(int)));
  86.                 printf("%lld ", sum);
  87.  
  88.                 BackwardInit(array, n);
  89.                 time_start();
  90.                 sum = CalculateSum(array, cycles);
  91.                 time = time_stop();
  92.                 printf("%lld ",  time/(n*sizeof(int)));
  93.                 printf("%lld ", sum);
  94.  
  95.                 RandomInit(array, n);
  96.                 time_start();
  97.                 sum = CalculateSum(array, cycles);
  98.                 time = time_stop();
  99.                 printf("%d %lld ",  n, time/(n*sizeof(int)));
  100.                 printf("%lld\n", sum);
  101.  
  102.                 free(array);
  103.         }
  104.         for(;n < 4*1024*1024/(sizeof(int)); n+=256*1024/sizeof(int)){
  105.                 array = (int *)calloc(n, sizeof(int));
  106.        
  107.                 CalculateSum(array,  1);
  108.  
  109.                 ForwardInit(array, n);
  110.                 time_start();
  111.                 sum = CalculateSum(array, cycles);
  112.                 time = time_stop();
  113.                 printf("%lld ",  time/(n*sizeof(int)));
  114.                 printf("%lld ", sum);
  115.  
  116.                 BackwardInit(array, n);
  117.                 time_start();
  118.                 sum = CalculateSum(array, cycles);
  119.                 time = time_stop();
  120.                 printf("%lld ",  time/(n*sizeof(int)));
  121.                 printf("%lld ", sum);
  122.  
  123.                 RandomInit(array, n);
  124.                 time_start();
  125.                 sum = CalculateSum(array, cycles);
  126.                 time = time_stop();
  127.                 printf("%d %lld ",  n, time/(n*sizeof(int)));
  128.                 printf("%lld\n", sum);
  129.  
  130.                 free(array);
  131.         }
  132.         return 0;
  133. }
create a new version of this paste RAW Paste Data