我可以通过 CPU 分析器看到,compute_variances()
是我项目的瓶颈。
% cumulative self self total
time seconds seconds calls ms/call ms/call name
75.63 5.43 5.43 40 135.75 135.75 compute_variances(unsigned int, std::vector<Point, std::allocator<Point> > const&, float*, float*, unsigned int*)
19.08 6.80 1.37 readDivisionSpace(Division_Euclidean_space&, char*)
...
这是函数体:
void compute_variances(size_t t, const std::vector<Point>& points, float* avg,
float* var, size_t* split_dims) {
for (size_t d = 0; d < points[0].dim(); d++) {
avg[d] = 0.0;
var[d] = 0.0;
}
float delta, n;
for (size_t i = 0; i < points.size(); ++i) {
n = 1.0 + i;
for (size_t d = 0; d < points[0].dim(); ++d) {
delta = (points[i][d]) - avg[d];
avg[d] += delta / n;
var[d] += delta * ((points[i][d]) - avg[d]);
}
}
/* Find t dimensions with largest scaled variance. */
kthLargest(var, points[0].dim(), t, split_dims);
}
kthLargest()
似乎不是问题,因为我看到了:
0.00 7.18 0.00 40 0.00 0.00 kthLargest(float*, int, int, unsigned int*)
compute_variances()
采用浮点 vector 的 vector (即 Points
的 vector ,其中 Points
是我实现的类) 并计算它们在每个维度上的方差(关于 Knuth 的算法)。
下面是我调用函数的方式:
float avg[(*points)[0].dim()];
float var[(*points)[0].dim()];
size_t split_dims[t];
compute_variances(t, *points, avg, var, split_dims);
问题是,我能做得更好吗?我真的很乐意在速度和方差的近似计算之间进行权衡。或者也许我可以使代码对缓存更友好什么的?
我是这样编译的:
g++ main_noTime.cpp -std=c++0x -p -pg -O3 -o eg
请注意,在编辑之前,我使用了 -o3
,而不是大写的“o”。感谢 ypnos,我现在使用优化标志 -O3
进行编译。我确信它们之间存在差异,因为我使用 these methods 之一进行了时间测量。在我的伪网站中。
请注意,现在 compute_variances
支配着整个项目的时间!
[编辑]
copute_variances()
被调用了 40 次。
每 10 次调用,以下情况成立:
points.size() = 1000 and points[0].dim = 10000
points.size() = 10000 and points[0].dim = 100
points.size() = 10000 and points[0].dim = 10000
points.size() = 100000 and points[0].dim = 100
每个调用处理不同的数据。
问:访问 points[i][d]
的速度有多快?
A:point[i]
只是 std::vector 的第 i 个元素,其中第二个 []
是这样实现的,在 点
类。
const FT& operator [](const int i) const {
if (i < (int) coords.size() && i >= 0)
return coords.at(i);
else {
std::cout << "Error at Point::[]" << std::endl;
exit(1);
}
return coords[0]; // Clear -Wall warning
}
其中 coords
是 float
值的 std::vector
。这似乎有点沉重,但编译器不应该足够聪明以正确预测分支总是正确的吗? (我的意思是在冷启动之后)。此外,std::vector.at()
应该是常数时间(如 ref 中所述)。我将其更改为函数主体中只有 .at()
,并且时间测量值几乎保持不变。
compute_variances()
中的除法 肯定很重!然而,Knuth 的算法是一个数值稳定的算法,我无法找到另一种算法,既能实现数值稳定又不除法。
请注意,我现在不对并行感兴趣。
[编辑.2]
Point
类的最小示例(我想我没有忘记展示一些东西):
class Point {
public:
typedef float FT;
...
/**
* Get dimension of point.
*/
size_t dim() const {
return coords.size();
}
/**
* Operator that returns the coordinate at the given index.
* @param i - index of the coordinate
* @return the coordinate at index i
*/
FT& operator [](const int i) {
return coords.at(i);
//it's the same if I have the commented code below
/*if (i < (int) coords.size() && i >= 0)
return coords.at(i);
else {
std::cout << "Error at Point::[]" << std::endl;
exit(1);
}
return coords[0]; // Clear -Wall warning*/
}
/**
* Operator that returns the coordinate at the given index. (constant)
* @param i - index of the coordinate
* @return the coordinate at index i
*/
const FT& operator [](const int i) const {
return coords.at(i);
/*if (i < (int) coords.size() && i >= 0)
return coords.at(i);
else {
std::cout << "Error at Point::[]" << std::endl;
exit(1);
}
return coords[0]; // Clear -Wall warning*/
}
private:
std::vector<FT> coords;
};
最佳答案
<强>1。 SIMD
一个简单的加速方法是使用 vector 指令 (SIMD) 进行计算。在 x86 上,这意味着 SSE、AVX 指令。根据您的字长和处理器,您可以获得大约 x4 甚至更多的加速。这里的代码:
for (size_t d = 0; d < points[0].dim(); ++d) {
delta = (points[i][d]) - avg[d];
avg[d] += delta / n;
var[d] += delta * ((points[i][d]) - avg[d]);
}
可以通过使用 SSE 一次计算四个元素来加快速度。由于您的代码在每次循环迭代中实际上只处理一个元素,因此不存在瓶颈。如果你使用 16 位 short 而不是 32 位 float (当时的近似值),你可以在一条指令中容纳八个元素。如果使用 AVX,它会更多,但你需要一个最新的处理器。
它不是您的性能问题的解决方案,而只是其中的一个,也可以与其他解决方案结合使用。
<强>2。微并行化
当你有那么多循环时,第二个简单的加速是使用并行处理。我通常使用 Intel TBB,其他人可能会建议使用 OpenMP。为此,您可能必须更改循环顺序。因此,在外循环中对 d 进行并行化,而不是对 i 进行并行化。
您可以将这两种技术结合起来,如果操作正确,在具有 HT 的四核上,您可以将组合的速度提高 25-30,而不会损失任何准确性。
<强>3。编译器优化
首先,也许这只是 SO 上的错字,但它需要是 -O3
,而不是 -o3
!
作为一般注意事项,如果您在实际使用它们的范围内声明变量 delta, n,编译器可能更容易优化您的代码。您还应该尝试 -funroll-loops
编译器选项以及 -march
。后者的选项取决于你的 CPU,但现在通常 -march core2
很好(也适用于最近的 AMD),并且包括 SSE 优化(但我不相信编译器还没有这样做你的循环)。
关于c++ - 需要更快地计算(近似)方差,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/23935166/