如何使动态数组或矢量以与标准阵列相似的速度运行?C++



我对C++仍然缺乏经验,我正在尝试编写总和代码来精确地添加数字。这是一个用于某些有限差分软件的dll插件,代码在运行过程中被调用了数百万次。我想编写一个函数,其中可以传入任意数量的参数并返回总和。我的代码如下所示:

#include <cstdarg>
double SumFunction(int numArgs, ...){ // this allows me to pass any number 
                                      // of arguments to my function.
va_list args;
va_start(args,numArgs); //necessary prerequisites for using cstdarg
double myarray[10];
for (int i = 0; i < numArgs; i++) {
    myarray[i] = va_arg(args,double);
}       // I imagine this is sloppy code; however i cannot create
        // myarray{numArgs] because numArgs is not a const int.
sum(myarray); // The actual method of addition is not relevant here, but
              //for more complicated methods, I need to put the summation 
              // terms in a list.
vector<double> vec(numArgs); // instead, place all values in a vector
for (int i = 0; i < numArgs; i++) {
    vec.at(i) = va_arg(args,double);
}
sum(vec); //This would be passed by reference, of course. The function sum
          // doesn't actually exist, it would all be contained within the 
          // current function. This is method is twice as slow as placing 
          //all the values in the static array.
double *vec;
vec =  new double[numArgs];
for (int i = 0; i < (numArgs); i++) {
    vec[i] = va_arg(args,double);
}
sum(vec); // Again half of the speed of using a standard array and 
          // increasing in magnitude for every extra dynamic array!
delete[] vec;
va_end(args);
}

所以我遇到的问题是使用超大的静态数组是草率的编程,但是使用向量或动态数组会大大减慢程序的速度。所以我真的不知道该怎么办。请问谁能帮忙?

加快代码速度的一种(以使其更复杂为代价)是在调用之间重用动态数组或向量,这样您将避免每次调用函数时产生内存分配和释放的开销。

例如,在函数外部将这些变量声明为全局变量或某个类内的成员变量。为了便于解释,我只是将它们设为全局变量:

double* sumArray = NULL;
int sumArraySize = 0;

在 SumFunction 中,检查数组是否存在,如果没有分配它,并在必要时调整大小:

double SumFunction(int numArgs, ...){ // this allows me to pass any number 
                                  // of arguments to my function.
    va_list args;
    va_start(args,numArgs); //necessary prerequisites for using cstdarg
    // if the array has already been allocated, check if it is large enough and delete if not:
    if((sumArray != NULL) && (numArgs > sumArraySize))
    {
        delete[] sumArray;
        sumArray = NULL;
    }
    // allocate the array, but only if necessary:
    if(sumArray == NULL)
    {
        sumArray = new double[numArgs];
        sumArraySize = numArgs;
    }
    double *vec = sumArray;   // set to your array, reusable between calls
    for (int i = 0; i < (numArgs); i++) {
        vec[i] = va_arg(args,double);
    }
    sum(vec, numArgs); // you will need to pass the array size
    va_end(args);
    // note no array deallocation
}

问题是你需要记住在某个时候通过调用一个类似于这样的函数来释放数组(就像我说的,你为速度付出额外的复杂性):

void freeSumArray()
{
    if(sumArray != NULL)
    {
        delete[] sumArray;
        sumArray = NULL;
        sumArraySize = 0;
    }
}

你可以对向量采取类似(更简单/更干净)的方法,如果它不存在,则第一次分配它,或者如果它存在,则使用 numArgs 调用 resize()。

使用 std::vector 优化程序必须考虑重新定位是可能的,这引入了额外的间接寻址。

换句话说,代码

v[index] += value;

其中v例如,std::vector<int>扩展到

int *p = v._begin + index;
*p += value;

即从向量,您首先需要获取字段_begin(包含内容在内存中开始的位置),然后应用索引,然后取消引用以获取值并改变它。

如果循环中对向量元素执行计算的代码调用任何未知的非内联代码,则优化器将被迫假设未知代码可能会改变向量的_begin字段,这将需要对每个元素执行两步间接寻址。

(注意:向量是用cost std::vector<T>&引用传递的完全无关紧要的:const引用并不意味着向量是const的,而只是限制了使用该引用允许的操作;外部代码可以有一个非const引用来访问向量,const也可以合法地丢弃...... const引用的性质基本上被优化器忽略)。

删除此额外查找的一种方法(如果您知道在计算过程中未调整向量的大小)是将此地址缓存在本地并使用它而不是向量运算符[]来访问元素:

int *p = &v[0];
for (int i=0,n=v.size(); i<n; i++) {
    /// use p[i] instead of v[i]
}

这将生成几乎与静态数组一样有效的代码,因为给定p的地址未发布,循环主体中的任何内容都无法更改它,并且可以假定p的值为常量(这是无法为v._begin完成的,因为优化器无法知道其他人是否知道_begin的地址)。

我之所以说"几乎",是因为静态数组只需要索引,而使用动态分配的区域需要"基本+索引"访问;然而,大多数CPU都提供这种内存访问,无需额外费用。此外,如果您按顺序处理元素,索引寻址将变为顺序内存访问,但前提是您可以假设起始地址常数(即不是在std::vector<T>::operator[]的情况下)。

假设"所需的最大存储量级"在 10-50 之间,我会说使用本地数组是完全可以的。

使用 vector<T> 将使用 3 * sizeof(*T)(至少)来跟踪向量的内容。因此,如果我们将其与 double arr[10];数组进行比较,那么在大小相等的堆栈上(或 8.5 位构建中的 32 个)上多了 32 个元素。但是你还需要调用 new ,这需要一个大小参数。因此,这至少占用了一个,更有可能是 2-3 个堆栈空间元素,并且new的实现很可能并不简单,因此需要进一步的调用,这会占用更多的堆栈空间。

如果你"不知道"元素的数量,并且需要处理相当多的元素,那么使用混合解决方案,其中你有一个基于堆栈的小本地数组,如果numargs > small_size使用vector,然后vec.data()传递给函数sum

最新更新