グラフデータは、次のように持っているが、ここで、点に関する情報の構造体は int 型で3つとなっており、アライメントをそろえることでより改善できるかどうか試してみた。
// 枝に格納する構造体
typedef struct {
int head; // 枝の先の点
int length; // 枝の距離
} arc_t;
// 点に格納する構造体
typedef struct {
int incident; // その頂点から出ている枝数の累計数
int potential; // 始点からの距離
int prevNode; // パスを作るために必要
} node_t;
// 問題を格納する構造体
typedef struct {
int nodeNum; // 問題の点数
int arcNum; // 問題の枝数
int maxLength; // 最長枝
int minLength; // 最短枝
arc_t *arc; // 枝関係
node_t *node; // 点関係
} graph_t;
具体的には、次のようにした。
(改善前)
typedef struct {
int incident; // その頂点から出ている枝数の累計数
int potential; // 始点からの距離
int prevNode; // パスを作るために必要
} node_t;
(改善後)
typedef struct {
int incident; // その頂点から出ている枝数の累計数
int potential; // 始点からの距離
int prevNode; // パスを作るために必要
int dammy;
} node_t;
改善前 24.04 [s]
改善後 25.35 [s]
結果からすると、この改善はしないほうがよいようである。アライメントが 16 byte に揃っていても、不必要なデータのせいでアドレス計算の方に若干のオーバーヘッドがかかってしまっているのではないかと考えている。
// 枝に格納する構造体
typedef struct {
int head; // 枝の先の点
int length; // 枝の距離
} arc_t;
// 点に格納する構造体
typedef struct {
int incident; // その頂点から出ている枝数の累計数
int potential; // 始点からの距離
int prevNode; // パスを作るために必要
} node_t;
// 問題を格納する構造体
typedef struct {
int nodeNum; // 問題の点数
int arcNum; // 問題の枝数
int maxLength; // 最長枝
int minLength; // 最短枝
arc_t *arc; // 枝関係
node_t *node; // 点関係
} graph_t;
具体的には、次のようにした。
(改善前)
typedef struct {
int incident; // その頂点から出ている枝数の累計数
int potential; // 始点からの距離
int prevNode; // パスを作るために必要
} node_t;
(改善後)
typedef struct {
int incident; // その頂点から出ている枝数の累計数
int potential; // 始点からの距離
int prevNode; // パスを作るために必要
int dammy;
} node_t;
改善前 24.04 [s]
改善後 25.35 [s]
結果からすると、この改善はしないほうがよいようである。アライメントが 16 byte に揃っていても、不必要なデータのせいでアドレス計算の方に若干のオーバーヘッドがかかってしまっているのではないかと考えている。