5

我需要从 ushort arrayB 中具有相同长度的相应索引值中快速减去 ushort arrayA 中的每个值。

另外,如果差为负,我需要存储一个零,而不是负差。

(确切地说,长度 = 327680,因为我要从另一个相同大小的图像中减去 640x512 图像)。

下面的代码目前需要约 20 毫秒,如果可能的话,我希望将其降低到约 5 毫秒。不安全的代码是可以的,但请提供一个例子,因为我在编写不安全的代码方面并不是很熟练。

谢谢!

public ushort[] Buffer { get; set; }

public void SubtractBackgroundFromBuffer(ushort[] backgroundBuffer)
{
    System.Diagnostics.Stopwatch sw = new System.Diagnostics.Stopwatch();
    sw.Start();

    int bufferLength = Buffer.Length;

    for (int index = 0; index < bufferLength; index++)
    {
        int difference = Buffer[index] - backgroundBuffer[index];

        if (difference >= 0)
            Buffer[index] = (ushort)difference;
        else
            Buffer[index] = 0;
    }

    Debug.WriteLine("SubtractBackgroundFromBuffer(ms): " + sw.Elapsed.TotalMilliseconds.ToString("N2"));
}

更新:虽然它不是严格意义上的 C#,但为了其他阅读本文的人的利益,我最终使用以下代码将 C++ CLR 类库添加到我的解决方案中。它的运行时间约为 3.1 毫秒。如果使用非托管 C++ 库,它会在 ~2.2ms 内运行。由于时差很小,我决定使用托管库。

// SpeedCode.h
#pragma once
using namespace System;

namespace SpeedCode
{
    public ref class SpeedClass
    {
        public:
            static void SpeedSubtractBackgroundFromBuffer(array<UInt16> ^ buffer, array<UInt16> ^ backgroundBuffer, int bufferLength);
    };
}

// SpeedCode.cpp
// This is the main DLL file.
#include "stdafx.h"
#include "SpeedCode.h"

namespace SpeedCode
{
    void SpeedClass::SpeedSubtractBackgroundFromBuffer(array<UInt16> ^ buffer, array<UInt16> ^ backgroundBuffer, int bufferLength)
    {
        for (int index = 0; index < bufferLength; index++)
        {
            buffer[index] = (UInt16)((buffer[index] - backgroundBuffer[index]) * (buffer[index] > backgroundBuffer[index]));
        }
    }
}

然后我这样称呼它:

    public void SubtractBackgroundFromBuffer(ushort[] backgroundBuffer)
    {
        System.Diagnostics.Stopwatch sw = new System.Diagnostics.Stopwatch();
        sw.Start();

        SpeedCode.SpeedClass.SpeedSubtractBackgroundFromBuffer(Buffer, backgroundBuffer, Buffer.Length);

        Debug.WriteLine("SubtractBackgroundFromBuffer(ms): " + sw.Elapsed.TotalMilliseconds.ToString("N2"));
    }
4

6 回答 6

5

一些基准。

  1. SubtractBackgroundFromBuffer:这是问题的原始方法。
  2. SubtractBackgroundFromBufferWithCalcOpt:这是原始方法增加了TTat提高计算速度的想法。
  3. SubtractBackgroundFromBufferParallelFor:来自 Selman22 的答案的解决方案。
  4. SubtractBackgroundFromBufferBlockParallelFor:我的答案。与 3. 类似,但将处理分解为 4096 个值的块。
  5. SubtractBackgroundFromBufferPartitionedParallelForEach:杰夫的第一个答案。
  6. SubtractBackgroundFromBufferPartitionedParallelForEachHack:杰夫的第二个回答。

更新

SubtractBackgroundFromBufferBlockParallelFor有趣的是,我可以通过使用(如 Bruno Costa 建议的那样)获得小幅速度提升(~6% )

Buffer[i] = (ushort)Math.Max(difference, 0);

代替

if (difference >= 0)
    Buffer[i] = (ushort)difference;
else
    Buffer[i] = 0;

结果

请注意,这是每次运行 1000 次迭代的总时间。

SubtractBackgroundFromBuffer(ms):                                 2,062.23 
SubtractBackgroundFromBufferWithCalcOpt(ms):                      2,245.42
SubtractBackgroundFromBufferParallelFor(ms):                      4,021.58
SubtractBackgroundFromBufferBlockParallelFor(ms):                   769.74
SubtractBackgroundFromBufferPartitionedParallelForEach(ms):         827.48
SubtractBackgroundFromBufferPartitionedParallelForEachHack(ms):     539.60

因此,从这些结果看来,最好的方法结合了计算优化以获得小增益和利用Parallel.For对图像块进行操作。您的里程当然会有所不同,并且并行代码的性能对您正在运行的 CPU 很敏感。

测试线束

我在发布模式下为每种方法运行了这个。我以Stopwatch这种方式开始和停止以确保仅测量处理时间。

System.Diagnostics.Stopwatch sw = new System.Diagnostics.Stopwatch();
ushort[] bgImg = GenerateRandomBuffer(327680, 818687447);

for (int i = 0; i < 1000; i++)
{
    Buffer = GenerateRandomBuffer(327680, 128011992);                

    sw.Start();
    SubtractBackgroundFromBuffer(bgImg);
    sw.Stop();
}

Console.WriteLine("SubtractBackgroundFromBuffer(ms): " + sw.Elapsed.TotalMilliseconds.ToString("N2"));


public static ushort[] GenerateRandomBuffer(int size, int randomSeed)
{
    ushort[] buffer = new ushort[327680];
    Random random = new Random(randomSeed);

    for (int i = 0; i < size; i++)
    {
        buffer[i] = (ushort)random.Next(ushort.MinValue, ushort.MaxValue);
    }

    return buffer;
}

方法

public static void SubtractBackgroundFromBuffer(ushort[] backgroundBuffer)
{
    int bufferLength = Buffer.Length;

    for (int index = 0; index < bufferLength; index++)
    {
        int difference = Buffer[index] - backgroundBuffer[index];

        if (difference >= 0)
            Buffer[index] = (ushort)difference;
        else
            Buffer[index] = 0;
    }
}

public static void SubtractBackgroundFromBufferWithCalcOpt(ushort[] backgroundBuffer)
{
    int bufferLength = Buffer.Length;

    for (int index = 0; index < bufferLength; index++)
    {
        if (Buffer[index] < backgroundBuffer[index])
        {
            Buffer[index] = 0;
        }
        else
        {
            Buffer[index] -= backgroundBuffer[index];
        }
    }
}

public static void SubtractBackgroundFromBufferParallelFor(ushort[] backgroundBuffer)
{
    Parallel.For(0, Buffer.Length, (i) =>
    {
        int difference = Buffer[i] - backgroundBuffer[i];
        if (difference >= 0)
            Buffer[i] = (ushort)difference;
        else
            Buffer[i] = 0;
    });
}        

public static void SubtractBackgroundFromBufferBlockParallelFor(ushort[] backgroundBuffer)
{
    int blockSize = 4096;

    Parallel.For(0, (int)Math.Ceiling(Buffer.Length / (double)blockSize), (j) =>
    {
        for (int i = j * blockSize; i < (j + 1) * blockSize; i++)
        {
            int difference = Buffer[i] - backgroundBuffer[i];

            Buffer[i] = (ushort)Math.Max(difference, 0);                    
        }
    });
}

public static void SubtractBackgroundFromBufferPartitionedParallelForEach(ushort[] backgroundBuffer)
{
    Parallel.ForEach(Partitioner.Create(0, Buffer.Length), range =>
        {
            for (int i = range.Item1; i < range.Item2; ++i)
            {
                if (Buffer[i] < backgroundBuffer[i])
                {
                    Buffer[i] = 0;
                }
                else
                {
                    Buffer[i] -= backgroundBuffer[i];
                }
            }
        });
}

public static void SubtractBackgroundFromBufferPartitionedParallelForEachHack(ushort[] backgroundBuffer)
{
    Parallel.ForEach(Partitioner.Create(0, Buffer.Length), range =>
    {
        for (int i = range.Item1; i < range.Item2; ++i)
        {
            unsafe
            {
                var nonNegative = Buffer[i] > backgroundBuffer[i];
                Buffer[i] = (ushort)((Buffer[i] - backgroundBuffer[i]) *
                    *((int*)(&nonNegative)));
            }
        }
    });
}
于 2014-01-16T01:53:41.567 回答
5

这是个有趣的问题。

只有在测试结果不会为负(如 TTat 和Maximum Cookie所建议的那样)之后才执行减法的影响可以忽略不计,因为这种优化已经可以由 JIT 编译器执行。

并行化任务(如Selman22所建议)是一个好主意,但是当循环在这种情况下尽可能快时,开销最终会超过收益,因此Selman22 的实现在我的测试中实际上运行得更慢。我怀疑nick_w 的基准测试是在附加调试器的情况下产生的,隐藏了这个事实。

将任务并行化为更大的块(如nick_w所建议的那样)可以解决开销问题,并且实际上可以产生更快的性能,但您不必自己计算块 - 您可以使用Partitioner它来为您执行此操作:

public static void SubtractBackgroundFromBufferPartitionedParallelForEach(
    ushort[] backgroundBuffer)
{
    Parallel.ForEach(Partitioner.Create(0, Buffer.Length), range =>
        {
            for (int i = range.Item1; i < range.Item2; ++i)
            {
                if (Buffer[i] < backgroundBuffer[i])
                {
                    Buffer[i] = 0;
                }
                else
                {
                    Buffer[i] -= backgroundBuffer[i];
                }
            }
        });
}

在我的测试中,上述方法始终优于nick_w 的手动分块。

可是等等!不仅如此。

减慢代码的真正罪魁祸首不是赋值或算术。这是if声明。它如何影响性能将主要受您正在处理的数据的性质的影响。

nick_w 的基准测试为两个缓冲区生成相同大小的随机数据。但是,我怀疑后台缓冲区中实际上很可能具有较低的平均幅度数据。由于分支预测,这个细节可能很重要(如this classic SO answer中所述)。

当后台缓冲区中的值通常小于缓冲区中的值时,JIT 编译器会注意到这一点,并相应地针对该分支进行优化。当每个缓冲区中的数据来自同一个随机群体时,无法以if超过 50% 的准确度猜测语句的结果。nick_w正是在后一种情况下进行基准测试,在这种情况下,我们可能会通过使用不安全的代码将布尔值转换为整数并完全避免分支来进一步优化您的方法。(请注意,以下代码依赖于 bool 在内存中的表示方式的实现细节,虽然它适用于您在 .NET 4.5 中的场景,但它不一定是一个好主意,此处显示用于说明目的。)

public static void SubtractBackgroundFromBufferPartitionedParallelForEachHack(
    ushort[] backgroundBuffer)
{
    Parallel.ForEach(Partitioner.Create(0, Buffer.Length), range =>
        {
            for (int i = range.Item1; i < range.Item2; ++i)
            {
                unsafe
                {
                    var nonNegative = Buffer[i] > backgroundBuffer[i];
                    Buffer[i] = (ushort)((Buffer[i] - backgroundBuffer[i]) *
                        *((int*)(&nonNegative)));
                }
            }
        });
}

如果您真的想节省更多时间,那么您可以通过将语言切换到 C++/CLI 以更安全的方式采用这种方法,因为这将允许您在算术表达式中使用布尔值,而无需使用不安全的代码:

UInt16 MyCppLib::Maths::SafeSubtraction(UInt16 minuend, UInt16 subtrahend)
{
    return (UInt16)((minuend - subtrahend) * (minuend > subtrahend));
}

您可以使用公开上述静态方法的 C++/CLI 创建一个纯托管 DLL,然后在您的 C# 代码中使用它:

public static void SubtractBackgroundFromBufferPartitionedParallelForEachCpp(
    ushort[] backgroundBuffer)
{
    Parallel.ForEach(Partitioner.Create(0, Buffer.Length), range =>
    {
        for (int i = range.Item1; i < range.Item2; ++i)
        {
            Buffer[i] = 
                MyCppLib.Maths.SafeSubtraction(Buffer[i], backgroundBuffer[i]);
        }
    });
}

这优于上面的 hacky 不安全的 C# 代码。事实上,它是如此之快,以至于您可以使用 C++/CLI 编写整个方法而无需考虑并行化,而且它的性能仍然优于其他技术。

使用nick_w 的测试工具,上述方法将优于迄今为止在此发布的任何其他建议。这是我得到的结果(1-4 是他尝试的案例,5-7 是此答案中概述的案例):

1. SubtractBackgroundFromBuffer(ms):                               2,021.37
2. SubtractBackgroundFromBufferWithCalcOpt(ms):                    2,125.80
3. SubtractBackgroundFromBufferParallelFor(ms):                    3,431.58
4. SubtractBackgroundFromBufferBlockParallelFor(ms):               1,401.36
5. SubtractBackgroundFromBufferPartitionedParallelForEach(ms):     1,197.76
6. SubtractBackgroundFromBufferPartitionedParallelForEachHack(ms):   742.72
7. SubtractBackgroundFromBufferPartitionedParallelForEachCpp(ms):    499.27

但是,在我希望您实际拥有的场景中,背景值通常较小,成功的分支预测可以全面提高结果,而避免该if语句的“hack”实际上更慢:

以下是我使用nick_w 的测试工具获得的结果,当我将后台缓冲区中的值限制在范围内0-6500(大约 10% 的缓冲区)时:

1. SubtractBackgroundFromBuffer(ms):                                 773.50
2. SubtractBackgroundFromBufferWithCalcOpt(ms):                      915.91
3. SubtractBackgroundFromBufferParallelFor(ms):                    2,458.36
4. SubtractBackgroundFromBufferBlockParallelFor(ms):                 663.76
5. SubtractBackgroundFromBufferPartitionedParallelForEach(ms):       658.05
6. SubtractBackgroundFromBufferPartitionedParallelForEachHack(ms):   762.11
7. SubtractBackgroundFromBufferPartitionedParallelForEachCpp(ms):    494.12

您可以看到结果 1-5 都得到了显着改善,因为它们现在受益于更好的分支预测。结果 6 和 7 没有太大变化,因为它们避免了分支。

数据的这种变化完全改变了事情。在这种情况下,即使是最快的全 C# 解决方案现在也只比原始代码快 15%。

底线:请务必使用代表性数据测试您选择的任何方法,否则您的结果将毫无意义。

于 2014-01-16T08:51:27.540 回答
1

你可以试试Parallel.For

Parallel.For(0, Buffer.Length, (i) =>
{
    int difference = Buffer[i] - backgroundBuffer[i];
    if (difference >= 0)
          Buffer[i] = (ushort) difference;
    else
         Buffer[i] = 0;
}); 

更新:我已经尝试过了,我发现您的情况差异很小,但是当数组变大时,差异也会变大

在此处输入图像描述

于 2014-01-16T00:59:45.277 回答
1

通过在实际执行减法之前先检查结果是否为负,您可能会获得轻微的性能提升。这样,如果结果为负,则无需执行减法。例子:

if (Buffer[index] > backgroundBuffer[index])
    Buffer[index] = (ushort)(Buffer[index] - backgroundBuffer[index]);
else
    Buffer[index] = 0;
于 2014-01-16T01:14:43.857 回答
0

关于什么,

Enumerable.Range(0, Buffer.Length).AsParalell().ForAll(i =>
    {
         unsafe
        {
            var nonNegative = Buffer[i] > backgroundBuffer[i];
            Buffer[i] = (ushort)((Buffer[i] - backgroundBuffer[i]) *
                *((int*)(&nonNegative)));
        }
    });
于 2014-01-16T10:58:20.693 回答
0

这是一个使用的解决方案Zip()

Buffer = Buffer.Zip<ushort, ushort, ushort>(backgroundBuffer, (x, y) =>
{
    return (ushort)Math.Max(0, x - y);
}).ToArray();

它的性能不如其他答案,但它绝对是最短的解决方案。

于 2014-01-16T10:35:34.487 回答