構造体の配列: Sample 2: 構造体のメンバーの和の計算(C)

高速化プログラミング   
トップ  >  メモリジャンプと高速化  >  構造体の配列  >  Sample 2: 構造体のメンバーの和の計算(C)

構造体の配列: Sample 2: 構造体のメンバーの和の計算(C)

言語の変更:   FORTRAN版

■ 概要

ここでは構造体の全部のメンバーの和を別の配列にコピーするサンプルを示します。内容的にはSample 1と似ていますが、違いは配列rに代入するのはあるひとつのメンバーではなくて、全部のメンバーの和です。つまりSample 1ではひつとのメンバーだけにアクセスしますが、このサンプルでは全メンバーにアクセスします。

■ ソースコード


  ◆ Code 1   ◆ Code 2
 
// Program to take the sum of the members of a structure to another array
#include <stdio.h>
#include <time.h>

struct Vector {
  double *a, *b, *c, *d, *e, *f, *g, *h;
};

int main()
{
  int i, k, n;
  Vector vec;
  double *r;
  printf("Array size    Elapsed time [sec] \n");

  for (int k=1; k<=20; k++) {
    // Array size
    int n = k * 2000000;

    // Allocation
    r = new double[n];
    vec.a = new double[n]; vec.b = new double[n];
    vec.c = new double[n]; vec.d = new double[n];
    vec.e = new double[n]; vec.f = new double[n];
    vec.g = new double[n]; vec.h = new double[n];

    // Initialization
    for (i=0; i<n; i++) {
      vec.a[i] = 1.0;
      vec.b[i] = 1.0;
      vec.c[i] = 1.0;
      vec.d[i] = 1.0;
      vec.e[i] = 1.0;
      vec.f[i] = 1.0;
      vec.g[i] = 1.0;
      vec.h[i] = 1.0;
    }

    // Start time
    clock_t time0 = clock();

    // Main calculation: find the sum of all members of vec
    for (i=0; i<n; i++)
      r[i] = vec.a[i] + vec.b[i] + vec.c[i] + vec.d[i]
	+ vec.e[i] + vec.f[i] + vec.g[i] + vec.h[i];

    // Finish time
    clock_t time1 = clock();

    // Output time
    double time = (double)(time1-time0)/CLOCKS_PER_SEC;
    printf("%11d %15.7f\n",n, time);

    // Deallocation
    delete[] r;
    delete[] vec.a; delete[] vec.b;
    delete[] vec.c; delete[] vec.d;
    delete[] vec.e; delete[] vec.f;
    delete[] vec.g; delete[] vec.h;
  }
  return 0;
}

    
 
// Program to take the sum of the members of a structure to another array
#include <stdio.h>
#include <time.h>

struct Vector {
  double a, b, c, d, e, f, g, h;
};

int main()
{
  int i, k, n;
  Vector *vec;
  double *r;
  printf("Array size    Elapsed time [sec] \n");

  for (int k=1; k<=20; k++) {
    // Array size
    int n = k * 2000000;

    // Allocation
    r = new double[n];
    vec = new Vector[n];




    // Initialization
    for (i=0; i<n; i++) {
      vec[i].a = 1.0;
      vec[i].b = 1.0;
      vec[i].c = 1.0;
      vec[i].d = 1.0;
      vec[i].e = 1.0;
      vec[i].f = 1.0;
      vec[i].g = 1.0;
      vec[i].h = 1.0;
    }

    // Start time
    clock_t time0 = clock();

    // Main calculation: find the sum of all members of vec
    for (i=0; i<n; i++)
      r[i] = vec[i].a + vec[i].b + vec[i].c + vec[i].d
	+ vec[i].e + vec[i].f + vec[i].g + vec[i].h;

    // Finish time
    clock_t time1 = clock();

    // Output time
    double time = (double)(time1-time0)/CLOCKS_PER_SEC;
    printf("%11d %15.7f\n",n, time);

    // Deallocation
    delete[] r;
    delete[] vec;



  }
  return 0;
}

    

■ 計算時間の測定結果

Code 1Code 2を実行したときの計算時間をそれぞれ青線と赤線で図1に示します。そして両者の比を緑線で示します。

測定時間
図1 測定時間

■ 考察

Code 1の配列の構造体では配列のメンバーが連続的に配置されているので、構造体の全部のメンバーを順番ににアクセスするとメモリのジャンプが起こります(図2を参照)。一方、Code 2の構造体の配列では構造体の同じメンバーは不連続に配列されているので、このサンプルでは図3のようにメモリのジャンプが起こりません。

Code 1のときのメモリアクセス
図2 Code 1のときのメモリアクセス
Code 2のときのメモリアクセス
図3 Code 2のときのメモリアクセス

図1の実測ではCode 2Code 1より計算時間が1.2倍ぐらい速いです。メモリのジャンプの面ではSample 1と似ていますが、Sample 2の倍率の方が低いです。これは、Sample 2のときの演算数がSample 1より多いためでしょう。



はじめに

演算数を減らす

メモリジャンプを減らす

高性能のアルゴリズム

その他



3 5 5 4 9 2