典型数据结构的性能分析
按照分类标准的不同，数据结构可以分为逻辑结构和存储结构，数据的逻辑结构是指数据对象中的数据元素之间的相互关系，与数据的存储尚未关联，是从具体问题抽象出来的数学模型，主要分为集合结构、线性结构、树形结构、图形结构等。
常用的数据存储结构有数组、栈、队列、链表、树、哈希表、堆、图等，这些数据结构有各自的优缺点，适用的场景也各不相同，这些数据结构的优缺点如下表：
执行效率较快的数据结构复杂程度一般较高，但并不是使用最快的结构就是最好的方案，仍需要根据实际情况进行考虑。
为进一步说明选择不同数据结构对于完成相同的操作会导致程序性能的差异，选用数组、链表结构以查找数据为例进行测试。
使用有序数组数据结构编写查找程序，程序编写完成后，利用gettimeofday这个计时函数对有序数组查找耗时进行测试，数组个数为10^7，结果显示其查找完成花费了0.048ms的时间。
int Bin_Search(int* num, int cnt, int target){
int first = 0, last = cnt - 1, mid;
int counter = 0;
while (first <= last) {
counter++;
mid = (first + last) / 2;//确定中间元素
if (num[mid] > target) {
last = mid - 1; //mid已经交换过了，last往前移一位
}
else if (num[mid] < target) {
first = mid + 1;//mid已经交换过了，first往后移一位
}
else { //判断是否相等
return 1;
}
}
return 0;
}
选取有序链表作为数据存储结构编写程序进行目标数据的查找。程序运行后利用计时函数测试耗时情况如下，完成查找10^7个数据所花费时间为19ms，程序性能不如使用有序数数组数据结构。
int list_search(struct Node* list,int value) {
struct Node* p;
for (p = list->next; p; p = p->next) {
if (p->value == value) {
return 1;
}
}
return 0;
}
void list_visit(struct Node* list) {
for (struct Node* p = list->next; p; p = p->next) {
printf("%d ", p->value);
}
}
在满足精度要求的情况下，不同的数据类型也会对程序的性能有影响，具体包括两个方面，一是选择存储空间更小的数据类型，二是选择更适合硬件结构的数据类型。
通常小尺寸类型数据的访问速度比大尺寸类型数据快，且小尺寸的数据可以在缓存中放更多的数据。为验证上述结论，使用SSE指令对两种数据类型进行加法运算，并测试运行时间进行对比。程序测试结果显示在处理单个数据时，SSE指令处理短整型数据的速度比处理整型数据快2倍左右。
for(int i=0;i<N;i+=4){
x = _mm_loadu_si128((__m128i*)&op3[i]);
y = _mm_loadu_si128((__m128i*)&op4[i]);
z = _mm_add_epi32(x, y);
_mm_store_si128((__m128i*)&result2[i], z);
}
不同的数据类型的程序在相同架构上的性能也有所不同。此时在满足正确性以及计算精度的要求下，可以对数据类型进行转换，帮助发挥硬件平台特性，提升程序的运算性能。
当使用256*256大小的矩阵规模进行测试时，单精度矩阵乘测试结果为0.036s，双精度为0.068s，加速比为1.88倍。
for (int k = n - 4; k >= 0; k -= 4) {
t1 = _mm_loadu_ps(a[i] + k);
t2 = _mm_loadu_ps(b[j] + k);
t1 = _mm_mul_ps(t1, t2);
sum = _mm_add_ps(sum, t1);
}
sum = _mm_hadd_ps(sum, sum);
sum = _mm_hadd_ps(sum, sum);
_mm_store_ss(c[i] + j, sum);
for (int k = (n % 4) - 1; k >= 0; --k){
c[i][j] += a[i][k] * b[j][k];
}
选择适合的数据结构
在解决具体问题时选择合适的数据结构是非常重要的，以稀疏矩阵向量乘法为例进一步说明数据结构选择的重要性。稀疏矩阵向量乘是科学工程计算的核心算法，为了提升稀疏矩阵向量乘法的性能，将采用坐标存储、行压缩、对角存储以及埃尔帕克存储四种稀疏矩阵存储格式实现稀疏矩阵向量乘法并进行测试对比。
坐标存储。坐标存储格式也称为三元组存储格式，其分别存储每个非零元素的行索引row、列索引col以及数值data。这种存储方式的主要优点是灵活、简单、易于按行和按列访问稀疏矩阵。
当稀疏矩阵存储格式为坐标存储格式时，向量乘法部分代码实现如下。
void spmv(int row[NNZ], int col[NNZ],DTYPE values[NNZ], DTYPE y[SIZE], DTYPE x[SIZE]) {//坐标存储的矩阵向量乘
int i;
for (i = 0; i < SIZE; i++) {
y[i] = 0;
}
for ( i = 0; i < NNZ; i++)
y[row[i]] += values[i] * x[col[i]];
}
行压缩存储。主要思想是逐行对稀疏矩阵进行压缩，并且记录每行首个非零元素的位置信息。行压缩存储格式由三个数组构成，数值data按行存放非零元素，列号col记录对应于data中每个非零元素位于的列数，指针ptr记录每行第一个非零元素在data中的存储位置。
当稀疏矩阵存储格式为行压缩存储时，向量乘法实现部分代码如下。
void spmv(int ptr[NUM_ROWS + 1], int col[NNZ], DTYPE data[NNZ], DTYPE y[SIZE], DTYPE x[SIZE]) {//行压缩存储的矩阵向量乘
for (int i = 0; i < NUM_ROWS; i++) {
DTYPE y0 = 0;
for (int k = ptr[i]; k < ptr[i + 1]; k++) {
y0 += data[k] * x[col[k]];
}
y[i] = y0;
}
}
对角存储。对角存储格式专为由多条非零对角线组成的稀疏矩阵设计，对角存储格式采用一个二维矩阵和一个向量来存储原矩阵，其中二维矩阵中的每一列用来存储原矩阵中的一条对角线，而向量则用来存储各列对应原矩阵中主对角线的偏移量。
当稀疏矩阵存储格式为对角存储时，向量乘法实现部分代码如下。
void spmv(DTYPE data[12], int offsets[SIZE - 1], DTYPE y[SIZE], DTYPE x[SIZE]) {//对角存储的矩阵向量乘
int i, j, k, N;
int Istart, Jstart, stride = 4;
for (i = 0; i < SIZE - 1; i++) {
k = offsets[i];
Istart = max(0, -k);
Jstart = max(0, k);
N = min(SIZE - Istart, SIZE - Jstart);
for (j = 0; j < N; j++) {
if (data[Istart + i * stride + j] != X)////其中X对应源数组的*表示不存在该数
y[Istart + j] += data[Istart + i * stride + j] * x[Jstart + j];}
}
ELLPACK存储。对于一个m*n的矩阵，每行最多有k个非零值元素，ELLPACK格式将非零值存储于一个m*k的稠密矩阵Data中。相应的列指针被存储在指数矩阵 Indices中，然后用0或者其它的哨兵值来填补空缺。与对角存储格式一样，indices和data矩阵都是按列顺序来存储的，当稀疏矩阵存储格式为ELLPACK时，向量乘法实现如下。
当稀疏矩阵存储格式为ELLPACK时，向量乘法实现如下。
void spmv(DTYPE data[12], int indices[12], DTYPE y[SIZE], DTYPE x[SIZE]) {//ELLPACK存储的矩阵向量乘
int n, i, k, N;
int max_ncols = SIZE - 1, num_rows = SIZE;
for (n = 0; n < max_ncols; n++)
for (i = 0; i < num_rows; i++)
if (data[n * num_rows + i] != X)
y[i] += data[n * num_rows + i] * x[indices[n * num_rows + i]];
}
当采用对角存储格式时，其性能往往好于其它格式。缺点是采用对角格式，非零元素的坐标需要通过计算才能得到，因此通常在稀疏矩阵向量乘法计算中不会采用对角格式。
只有非零元所占比例大于某一阈值时，使用ELLPACK存储格式会取得更好的性能。
对角存储和ELLPACK这两种格式都需要对矩阵进行补零操作，对稀疏矩阵向量乘程序性能有一定影响，而坐标存储和行压缩存储格式则不存在这个问题，它们只存储矩阵中的非零元素，不会引入不必要的开销。
每种稀疏矩阵存储结构的不同将导致在进行优化时必须选择不同的方法，因此需针对每一种方法选择不同的优化策略，以获得最优的性能。
