Content

Erste Tests mit eindimensionalen Arrays

Aufgabe

Ein Test sollte dann

Lösungsvorschlag

#include <stdio.h>
#include <stdlib.h>

void init_vector(double* v, size_t len, size_t incr) {
   for (size_t i = 0; i < len; ++i) {
      v[i*incr] = i + 1;
   }
}

void print_vector(double* v, size_t len, size_t incr) {
   for (size_t i = 0; i < len; ++i) {
      printf(" %4.1lf", v[i*incr]);
   }
   printf("\n");
}

#define MAX_LEN 8
double vector[MAX_LEN];

int main() {
   double* x = vector;
   printf("initialize x as one vector\n");
   size_t len = MAX_LEN;
   init_vector(x, len, 1);
   printf("x =      "); print_vector(x, MAX_LEN, 1);

   printf("using the space for two vectors\n");
   len = MAX_LEN/2;
   double* y = vector + len;
   init_vector(x, len, 1); init_vector(y, len, 1);
   printf("x =      "); print_vector(x, len, 1);
   printf("y =      "); print_vector(y, len, 1);
   printf("vector = "); print_vector(vector, MAX_LEN, 1);

   printf("using the space for two interleaving vectors\n");
   y = vector + 1;
   init_vector(x, len, 2); init_vector(y, len, 2);
   printf("x =      "); print_vector(x, len, 2);
   printf("y =      "); print_vector(y, len, 2);
   printf("vector = "); print_vector(vector, MAX_LEN, 1);
}

Übersetzen und Ausführen

$shell> gcc -Wall -o example1_vector example1_vector.c
$shell> ./example1_vector
initialize x as one vector
x =        1.0  2.0  3.0  4.0  5.0  6.0  7.0  8.0
using the space for two vectors
x =        1.0  2.0  3.0  4.0
y =        1.0  2.0  3.0  4.0
vector =   1.0  2.0  3.0  4.0  1.0  2.0  3.0  4.0
using the space for two interleaving vectors
x =        1.0  2.0  3.0  4.0
y =        1.0  2.0  3.0  4.0
vector =   1.0  1.0  2.0  2.0  3.0  3.0  4.0  4.0

Aufgabe

Um zu sehen, wie die Zugriffszeiten skalieren, sollten Sie diese messen für Vektorlängen für alle Zweierpotenzen beginnend von 8.192 bis 67.108.864. Damit die Messungen sich möglichst wenig gegenseitig beeinflussen, sollten Sie für jede Vektorlänge - zwei doppelt so große Vektoren vector1 und vector2

dynamisch mit Hilfe von malloc belegen,

Lösungsvorschlag

#include <stdio.h>
#include <sys/times.h>
#include <unistd.h>
#include <stdlib.h>

/* return real time in seconds since start of the process */
double walltime() {
#ifndef CLK_TCK
   /* CLK_TCK specifies the number of ticks per second */
   static int CLK_TCK = 0;
   if (!CLK_TCK) {
      CLK_TCK = sysconf(_SC_CLK_TCK);
   }
#endif
   struct tms timebuf;
   /* times returns the number of real time ticks passed since start */
   return (double) times(&timebuf) / CLK_TCK;
}

void init_vector(double* v, size_t len, size_t incr) {
   for (size_t i = 0; i < len; ++i) {
      v[i*incr] = i + 1;
   }
}

void print_vector(double* v, size_t len, size_t incr) {
   for (size_t i = 0; i < len; ++i) {
      printf(" %4.1lf", v[i*incr]);
   }
   printf("\n");
}

#define MAX_LEN 134217728

int main() {
   double* x; double* y; // two vectors living in the space of "vector"
   double t0, t1, t2; // time stamps
   printf("     len t1 (separate) t2 (interleaving)      t2/t1\n");
   for (size_t len = 8192; len <= MAX_LEN/2; len *= 2) {
      printf("%8zd", len);

      /* separate vectors */
      double* vector1 = malloc(sizeof(double) * len * 2);
      x = vector1;
      y = vector1 + len;
      t0 = walltime();
      init_vector(x, len, 1);
      init_vector(y, len, 1);
      t1 = walltime() - t0;
      printf(" %12.2lf", t1);

      /* interleaved vectors */
      double* vector2 = malloc(sizeof(double) * len * 2);
      t0 = walltime();
      x = vector2; y = vector2 + 1;
      init_vector(x, len, 2);
      init_vector(y, len, 2);
      t2 = walltime() - t0;
      printf(" %12.2lf %16.2lf", t2, t2/t1);
      printf("\n");

      free(vector1); free(vector2);
   }
}

Übersetzen und Ausführen

$shell> gcc -Wall -o example2_vector example2_vector.c
$shell> ./example2_vector
     len t1 (separate) t2 (interleaving)      t2/t1
    8192         0.00         0.00             1.00
   16384         0.00         0.00             1.00
   32768         0.00         0.00             1.00
   65536         0.00         0.01      16786438.07
  131072         0.00         0.00             1.00
  262144         0.01         0.01             1.00
  524288         0.01         0.02             2.00
 1048576         0.02         0.05             2.50
 2097152         0.04         0.08             2.00
 4194304         0.10         0.16             1.60
 8388608         0.19         0.34             1.79
16777216         0.38         0.65             1.71
33554432         0.75         1.30             1.73
67108864         1.49         2.62             1.76