如何加速C#数学代码

Question

如何加速C#数学代码

c#performancewindows-phone-7optimizationxna

17

我有一些3D插值代码，它占据了我的项目运行时间的90％，且无法预先计算。

有什么技术可以用来加速？是算法优化还是微观优化？

这是代码，供感兴趣的人参考。

基本上，它获取放置在2个3D数组中的数据并插值剩余的数据。

编辑：我已经在更高层级上将其分成线程以提高性能，但这对单核心的Windows Phone没有帮助...

我可能会做类似于（Single[] DensityMap = new Single [128 * 128 * 128];）这样的事情来避免多维数组的影响。我在100个地方访问该数组，并希望不必这样做（封装在函数中不起作用，因为Windows Phone不会内联函数调用，这样不会帮助性能...）

float[, ,] DensityMap = new float[128, 128, 128];
float[, ,] PressureMap = new float[128, 128, 128];

unchecked
{
    for (int x = 0; x < g_CraftWorldConstants.RegionSizeX; x++)
    {
        int offsetX = (x / SAMPLE_RATE_3D_HOR) * SAMPLE_RATE_3D_HOR;
        int plusOffsetX = SAMPLE_RATE_3D_HOR + offsetX;
        int poxox = plusOffsetX - offsetX;
        double poxxpoxox = ((plusOffsetX - x) / (double)poxox);
        double xoxpoxox = ((x - offsetX) / (double)poxox);

        for (int y = 0; y < g_CraftWorldSettings.GET.RegionSizeY; y++)
        {
            int offsetY = (y / SAMPLE_RATE_3D_VERT) * SAMPLE_RATE_3D_VERT;
            int plusOffsetY = SAMPLE_RATE_3D_VERT + offsetY;
            int poyoy = plusOffsetY - offsetY;
            double poyypoyoy = ((plusOffsetY - y) / (double)poyoy);
            double yoypoyoy = ((y - offsetY) / (double)poyoy);

            for (int z = 0; z < g_CraftWorldConstants.RegionSizeZ; z++)
            {
                if (!(x % SAMPLE_RATE_3D_HOR == 0 && y % SAMPLE_RATE_3D_VERT == 0 && z % SAMPLE_RATE_3D_HOR == 0))
                {
                    int offsetZ = (z / SAMPLE_RATE_3D_HOR) * SAMPLE_RATE_3D_HOR;
                    int plusOffsetZ = SAMPLE_RATE_3D_HOR + offsetZ;
                    int pozoz = plusOffsetZ - offsetZ;
                    double pozzpozoz = ((plusOffsetZ - z) / (double)pozoz);
                    double zozpozoz = ((z - offsetZ) / (double)pozoz);

                    double x00 = poxxpoxox * in_DensityMap[offsetX, offsetY, offsetZ] + xoxpoxox * in_DensityMap[plusOffsetX, offsetY, offsetZ];
                    double x10 = poxxpoxox * in_DensityMap[offsetX, offsetY, plusOffsetZ] + xoxpoxox * in_DensityMap[plusOffsetX, offsetY, plusOffsetZ];
                    double x01 = poxxpoxox * in_DensityMap[offsetX, plusOffsetY, offsetZ] + xoxpoxox * in_DensityMap[plusOffsetX, plusOffsetY, offsetZ];
                    double x11 = poxxpoxox * in_DensityMap[offsetX, plusOffsetY, plusOffsetZ] + xoxpoxox * in_DensityMap[plusOffsetX, plusOffsetY, plusOffsetZ];

                    double r0 = poyypoyoy * x00 + yoypoyoy * x01;
                    double r1 = poyypoyoy * x10 + yoypoyoy * x11;
                    in_DensityMap[x, y, z] = (float)(pozzpozoz * r0 + zozpozoz * r1);

                    double x02 = poxxpoxox * in_CaveDensity[offsetX, offsetY, offsetZ] + xoxpoxox * in_CaveDensity[plusOffsetX, offsetY, offsetZ];
                    double x12 = poxxpoxox * in_CaveDensity[offsetX, offsetY, plusOffsetZ] + xoxpoxox * in_CaveDensity[plusOffsetX, offsetY, plusOffsetZ];
                    double x03 = poxxpoxox * in_CaveDensity[offsetX, plusOffsetY, offsetZ] + xoxpoxox * in_CaveDensity[plusOffsetX, plusOffsetY, offsetZ];
                    double x13 = poxxpoxox * in_CaveDensity[offsetX, plusOffsetY, plusOffsetZ] + xoxpoxox * in_CaveDensity[plusOffsetX, plusOffsetY, plusOffsetZ];

                    double r2 = poyypoyoy * x02 + yoypoyoy * x03;
                    double r3 = poyypoyoy * x12 + yoypoyoy * x13;
                    in_CaveDensity[x, y, z] = (float)(pozzpozoz * r2 + zozpozoz * r3);
                }
            }
        }
    }
}

- Daniel Armstrong

1

也许你可以近似计算 - 例如，每个轴上只取1/10的值，并插值缺失的值。 - Oliver

“Parallel.For” 可以大大加快速度。 - cjk

如果您选择并行化，请确保仅在一个级别上进行并行化 - 可能是外部for语句。因此，您将在一个并行for循环内有两个顺序for循环。请参阅http://msdn.microsoft.com/en-us/library/dd997392.aspx了解原因。 - Olly

你有一些可以简化的计算（我相信编译器会自动完成这个过程，因此它不会提高性能），例如 (x / SAMPLE_RATE_3D_HOR) * SAMPLE_RATE_3D_HOR 可以简单地变成 x，这样可以消除一些冗余变量。 - Lukazoid

@Lukazoid-这些是整数计算，所以可能无法简化，即 (1234 / 100) * 100 = 1200。 - hatchet - done with SOverflow

5个回答

8

以下是加速您的代码的一些方法:

避免使用多维数组，因为它们较慢
使用多线程
将要转换为double类型的变量存储在double变量中
尽可能预先计算（见hatchet的帖子）

数组

要模拟3D数组，可以按照以下方式进行：

Single[] DensityMap = new Single[128 * 128 * 128];
DensityMap[z + (y * 128) + (x * 128 * 128)] = ...;

- Felix K.

多线程如何在单核CPU上发挥作用？它会使情况变得更糟，因为存在上下文切换和同步问题。 - dowhilefor

抱歉，我没有注意到Xbox的问题。确保不会死锁您的线程，如果您使用多个线程。因此，如果他实际上可以使用多个核心，那么处理同步问题可能值得一试，但我只考虑了一个核心，使用多个线程性能会大大降低。同步也有代价。 - dowhilefor

1

你是对的。但通常值得考虑这种情况可能会出现。无论如何，好答案+1。 - dowhilefor

@Felix K.我已经在更高层次上将其分成线程以提高性能，但这对Windows手机没有帮助，因为它们都是单核的... - Daniel Armstrong

@Felix K. 我可能会这样做（Single[] DensityMap = new Single[128 * 128 * 128];），以消除多维数组的影响。我在100个地方访问该数组，希望不必这样做（将其包装在函数中无济于事，因为Windows手机不会内联函数调用，这对性能没有帮助...）。 - Daniel Armstrong

显示剩余2条评论

2

使用锯齿数组而不是多维数组，即：

float[][][] DensityMap = new float[128][][];

然后使用for循环或LINQ语法（可能不是最优选择）创建内部数组。

这种方法的性能比使用多维数组好得多，且与使用单维数组并自行计算偏移量的性能相当甚至更好。除非初始化交错数组的成本显著；毕竟它将创建128^2个数组。我会进行基准测试，并在成本真正显著时才转回单一维数组。

- Asik

不久之前我进行了一个简单的基准测试，结果显示初始化锯齿数组比多维数组要慢（我记不清具体差距有多大），但是访问锯齿数组的元素速度在15-20%之间更快。因此，在这种情况下（只需初始化一次，但需要频繁访问元素），除了其他回复中提到的提示外，这确实可以帮助优化代码。 - Patryk Ćwiek

为什么锯齿状数组更快？它们应该更慢，因为它们需要更多的内存访问。 - mafu

这取决于多维数组的实现方式。早期，它们没有像单维数组那样受益于相同的优化。不过这可能已经改变了，因为这个答案已经有8年了。 - Asik

1

你可以改变你的for循环，因为你不需要处理所有这些中间值

for (int x = 0; x < 128; x+= SAMPLE_RATE_3D_HOR) {
   for (int y = 0; y < 128; y+= SAMPLE_RATE_3D_VERT) {
      for (int z = 0; z < 128; z+= SAMPLE_RATE_3D_HOR) {

同时进行这些操作会更好。

通过这种方式，您可以消除600万个模数%计算和60,000多个乘法运算。

--编辑-- 抱歉，我错过了您在3个模数上的“！”。您仍然可以跳过其中一些计算。请参见下面的评论。

- GeekyMonkey

实际上我已经这样做了，这个函数外面还有另一个W循环 :) 它在线程360中的所有6个线程中被分配。 - Daniel Armstrong

“With this you can eliminate the 6 million mod % calculations and 60+ thousand multiplies.” 这句话的意思是什么？ - Daniel Armstrong

抱歉，我误读了这一行 if (!(x % SAMPLE_RATE_3D_HOR == 0 && y % SAMPLE_RATE_3D_VERT == 0 && z % SAMPLE_RATE_3D_HOR == 0))我错过了"!"。如果您跳过其中 (X % SAMPLE_RATE_3D_HOR == 0) 的 Y 和 Z 循环，并跳过 (Y % SAMPLE_RATE_3D_VERT == 0) 的 z 循环，则仍然可以消除最内层循环中的某些模运算。 - GeekyMonkey

0

1) 你真的需要使用双精度浮点数吗？特别是当你混合使用了一些浮点数、双精度浮点数和整型数据时。

2) 你应该预先计算出 k / SAMPLE_RATE_3D_HOR * SAMPLE_RATE_3D_HOR 这个模式。

int pre_calc[128];
for( int i = 0; i < 128; ++i )
    pre_calc[i] = (i / SAMPLE_RATE_3D_HOR) * SAMPLE_RATE_3D_HOR;

- Christopher

我曾经认为在Windows 7手机上，双精度浮点数比单精度浮点数快40-50％？这显然是因为clr无论如何都会将float转换为double。 - Daniel Armstrong

双精度浮点数速度较慢。当参数之一为双精度浮点数时，clr会将浮点数（和整数）在运算符中提升为双精度浮点数。 - Christopher

我刚在手机硬件上对一个程序进行了基准测试，双精度数学运算（加法、乘法、减法、除法）似乎快了约35%。但是我可能做错了什么，也可能与缓存有关？ - Daniel Armstrong

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- hatchet - done with SOverflow · Accepted Answer

看起来您有很多优化代码的机会。您的x循环执行128次，y循环执行128*128=16,384次，z循环执行128^3=2,097,152 次。在z循环内有许多项仅依赖于x或y的迭代，但它们在每个z迭代时都被重新计算。例如，

int poxox = plusOffsetX - offsetX;

并且

double poxxpoxox = ((plusOffsetX - x) / (double)poxox);

这两个术语被计算超过200万次，但如果我对您的函数进行了粗略扫描而言，只需要计算128次。将术语移到适当的循环级别，以便不会浪费计算重复值的时间。

这是经过基本优化的代码。我很想知道这对运行时间的影响。有几个术语仅取决于迭代值，并且对于x、y和z是相同的。因此，我将它们完全提出并预先计算一次。我还将外部mod操作移出内部循环，并修改了逻辑以确保评估的短路，应该消除之前执行的大部分mod操作。

int[] offsets = new int[128];
int[] plusOffsets = new int[128];
double[] poii = new double[128];
double[] ioip = new double[128];
for (int i = 0; i < 128; i++) {
    offsets[i] = (i / SAMPLE_RATE_3D_HOR) * SAMPLE_RATE_3D_HOR;
    plusOffsets[i] = SAMPLE_RATE_3D_HOR + offsets[i];
    double poioi = (double) (plusOffsets[i] - offsets[i]);
    poii[i] = ((plusOffsets[i] - i) / poioi);
    ioip[i] = ((i - offsets[i]) / poioi);
}

float[, ,] DensityMap = new float[128, 128, 128];
float[, ,] PressureMap = new float[128, 128, 128];

for (int x = 0; x < g_CraftWorldConstants.RegionSizeX; x++)
{
    int offsetX = offsets[x];
    int plusOffsetX = plusOffsets[x];
    double poxxpoxox = poii[x];
    double xoxpoxox = ioip[x];
    bool xModNot0 = !(x % SAMPLE_RATE_3D_HOR == 0);

    for (int y = 0; y < g_CraftWorldConstants.RegionSizeY; y++)
    {
        int offsetY = offsets[y];
        int plusOffsetY = plusOffsets[y];
        double poyypoyoy = poii[y];
        double yoypoyoy = ioip[y];
        bool yModNot0 = !(y % SAMPLE_RATE_3D_VERT == 0);

        for (int z = 0; z < g_CraftWorldConstants.RegionSizeZ; z++)
        {
            //if (!(x % SAMPLE_RATE_3D_HOR == 0 && y % SAMPLE_RATE_3D_VERT == 0 && z % SAMPLE_RATE_3D_HOR == 0))
            if (xModNot0 || yModNot0 || !(z % SAMPLE_RATE_3D_HOR == 0))
            {
                int offsetZ = offsets[z];
                int plusOffsetZ = plusOffsets[z];
                double pozzpozoz = poii[z];
                double zozpozoz = ioip[z];

                double x00 = poxxpoxox * DensityMap[offsetX, offsetY, offsetZ] + xoxpoxox * DensityMap[plusOffsetX, offsetY, offsetZ];
                double x10 = poxxpoxox * DensityMap[offsetX, offsetY, plusOffsetZ] + xoxpoxox * DensityMap[plusOffsetX, offsetY, plusOffsetZ];
                double x01 = poxxpoxox * DensityMap[offsetX, plusOffsetY, offsetZ] + xoxpoxox * DensityMap[plusOffsetX, plusOffsetY, offsetZ];
                double x11 = poxxpoxox * DensityMap[offsetX, plusOffsetY, plusOffsetZ] + xoxpoxox * DensityMap[plusOffsetX, plusOffsetY, plusOffsetZ];

                double r0 = poyypoyoy * x00 + yoypoyoy * x01;
                double r1 = poyypoyoy * x10 + yoypoyoy * x11;
                DensityMap[x, y, z] = (float)(pozzpozoz * r0 + zozpozoz * r1);

                double x02 = poxxpoxox * PressureMap[offsetX, offsetY, offsetZ] + xoxpoxox * PressureMap[plusOffsetX, offsetY, offsetZ];
                double x12 = poxxpoxox * PressureMap[offsetX, offsetY, plusOffsetZ] + xoxpoxox * PressureMap[plusOffsetX, offsetY, plusOffsetZ];
                double x03 = poxxpoxox * PressureMap[offsetX, plusOffsetY, offsetZ] + xoxpoxox * PressureMap[plusOffsetX, plusOffsetY, offsetZ];
                double x13 = poxxpoxox * PressureMap[offsetX, plusOffsetY, plusOffsetZ] + xoxpoxox * PressureMap[plusOffsetX, plusOffsetY, plusOffsetZ];

                double r2 = poyypoyoy * x02 + yoypoyoy * x03;
                double r3 = poyypoyoy * x12 + yoypoyoy * x13;
                PressureMap[x, y, z] = (float)(pozzpozoz * r2 + zozpozoz * r3);
            }
        }
    } 
}