"
有没有一种方法可以在不通过枚举循环的情况下执行 data1-data2 = data3?
不,这在技术上是不可能的。
最好(或者说最坏)的情况是,您可以调用一个函数来为您枚举。但这会使速度变慢。在LINQ的情况下,速度非常慢。
对于我目前正在使用的机器,对于4KB表(1024个整数),其他答案的结果如下:
"
- 23560 滴答声 - Giannis Paraskevopoulos。数组可枚举数组转换不太快,通过ToList() .ToArray()链复制数组大约要慢25倍Array.Copy()。
- 10198 滴答声 - Selman22。速度提高了2倍,但仍然很慢。Lambda是为了使创建事件更漂亮而不是更快的眼睛糖果。最终你会得到一些匿名方法在那里游荡,它所花费的CPU时间比其操作还要多(记住我们在这里所做的数学CPU可以在几个周期内完成)。
- 566 滴答声 - Tim Schmelter GetDifference()函数(主要原因是JIT,在本地代码和/或更频繁的使用中差异将是可以忽略的)
- 27 滴答声 - 只是一个循环。比Zip快400倍,比将数组转换为列表并返回快800倍。
循环代码:
for (int i = 0; i < data3.Length; i++)
{
data3[i] = Math.Abs(data1[i] - data2[i]);
}
这些基本的内存操作可以直接翻译成机器代码,而不需要使用LINQ带来的性能问题和巨大的内存占用。
故事的寓意是:LINQ适用于可读性(在这种情况下有争议),而不适用于性能(在这种情况下很明显)。
优化时间!让我们稍微滥用一下CPU。
- 展开循环。或者不要展开。您的体验可能会有所不同。即使在汇编语言中,循环展开的性能增益或损失也因处理器系列而异。新的CPU和编译器已经了解到旧技巧,并且会自行实现它们。对于i3-3220,我测试了展开4行代码的循环,在32位代码上得到了更快的执行速度,但在64位上稍微慢了一点,而展开8则相反。
- 编译为x64。由于我们在这里处理32位数据,因此我们不会使用64位寄存器...或者我们会吗?在x86上,只有不到一半的寄存器真正可用于生成的代码(在手写汇编中,您总是可以挤出更多),但在x64上,您获得了八个额外的寄存器可供使用。越多操作不需要访问内存,您的代码就越快。在这种情况下,速度提高约20%。
- 关闭Visual Studio。不要在32位IDE中进行64位代码的速度测试(目前还没有64位版本,而且可能很长时间都不会有)。由于架构不匹配,它将使x64代码大约变慢两倍。(嗯...无论如何,您都不应该在调试器下测试代码的速度...)
- 不要过多使用内置函数。在这种情况下,Math.Abs中有隐藏的开销。由于某些原因(需要分析IL才能找出),使用?:检查负值比If-Else更快。这样的检查节省了大量时间。
更新: ?: 比 If-Else 更快,因为它们的机器码有所不同...至少在比较两个值时是如此。 它的机器码比 If-Else 简单得多(看起来不像你手写的代码)。 显然,它不仅是 If-Else 语句的不同形式,而且是针对简单条件赋值进行优化的完全独立的命令。
生成的代码大约比使用 Math.Abs() 的简单循环快8倍;请记住,您只能将循环展开到数据集大小的除数。 您编写的数据集大小为25920,因此8是可以的(最大为64,但我怀疑这样做是否有任何意义)。 我建议将此代码隐藏在某个函数中,因为它非常丑陋。
int[] data3 = new int[data1.Length];
for (int i = 0; i < data1.Length; i += 8)
{
int b;
b = (data1[i + 0] - data2[i + 0]);
data3[i + 0] = b < 0 ? -b : b;
b = (data1[i + 1] - data2[i + 1]);
data3[i + 1] = b < 0 ? -b : b;
b = (data1[i + 2] - data2[i + 2]);
data3[i + 2] = b < 0 ? -b : b;
b = (data1[i + 3] - data2[i + 3]);
data3[i + 3] = b < 0 ? -b : b;
b = (data1[i + 3] - data2[i + 4]);
data3[i + 4] = b < 0 ? -b : b;
b = (data1[i + 5] - data2[i + 5]);
data3[i + 5] = b < 0 ? -b : b;
b = (data1[i + 6] - data2[i + 6]);
data3[i + 6] = b < 0 ? -b : b;
b = (data1[i + 7] - data2[i + 7]);
data3[i + 7] = b < 0 ? -b : b;
}
这甚至还不是它的最终形态。我将尝试对其进行更多异端邪术。
BitHack,低级作弊!
正如我所提到的,还有改进的空间。
在剪切LINQ之后,主要ticks munchkin是Abs()。当它从代码中删除时,我们只剩下IF-ELSE和shorthand ?: 运算符之间的竞争。
两者都是分支运算符,在过去曾被广泛认为比线性代码慢。目前,舒适性/编写容易性往往优先于性能(有时正确,有时不正确)。
因此,让我们使我们的分支条件成为线性的。通过滥用这段代码中包含的仅针对单个变量进行数学操作的事实,这是可能的。那么让我们制作与
this等效的代码。
现在,你还记得如何否定二进制补码吗?取反所有位并加一。然后让我们在不使用条件的情况下完成它!
现在是位运算符发光的时候了。OR和AND很无聊,真正的男人使用XOR。 XOR有什么很酷的地方?除了它的通常行为外,您还可以将其转换为NOT(否定)和NOP(无操作)。
1 XOR 1 = 0
0 XOR 1 = 1
使用只包含1的值进行XOR操作可以实现NOT运算。
1 XOR 0 = 1
0 XOR 0 = 0
所以,使用只填充0值的值进行异或操作没有任何效果。
我们可以从我们的数字中获取符号。对于32位整数,它非常简单,即x>>31
。它将位符移动到最低位。正如维基百科所说,插入的位从左侧插入将为零,因此对于负数(x<0),x>>31
的结果将为1,对于非负数(x>=0)则为0,对吗?
不是这样的。对于带符号的值,使用算术移位而不是纯位移。因此,根据符号,我们将获得-1或0....这意味着对于负数和非负数来说,'x>>31'将分别给出111...111和000...000。如果您将原始x与这种移位的结果进行异或运算,则会执行NOT或NOP,具体取决于值的符号。另一个有用的事情是,0将导致加法/否定的NOP,因此我们可以根据值的符号添加/减去-1。
所以'x^(x>>31)'将翻转负数的位,而对非负数不做任何更改,'x-(x>>31)'将给负数x加1(否定的负值给出正值),并对非负值不做任何更改。
当组合在一起时,你会得到'(x ^ (x >> 31)) - (x >> 31)'... 这可以翻译为:
IF X<0
X=!X+1
而且这只是
IF X<0
X=-X
如何影响性能?
我们的XorAbs()只需要四个基本整数操作,一个加载和一个存储。分支运算符本身需要大约相同数量的CPU时钟周期。虽然现代CPU在进行分支预测方面表现出色,但当输入连续代码时,它们仍然通过简单地不执行分支来提高速度。
得分情况如何?
1.比内置的Abs()快约四倍;
2.比以前的代码(未展开循环的版本)快约两倍;
3.根据CPU的不同,可以在不展开循环的情况下获得更好的结果。由于消除了代码分支,CPU可以自行“展开”循环。(Haswell处理器在展开循环方面表现奇怪)
生成的代码:
for (int i = 0; i < data1.Length; i++)
{
int x = data1[i] - data2[i];
data3[i] = (x ^ (x >> 31)) - (x >> 31);
}
并行性和缓存使用
CPU拥有超快的缓存内存,当按顺序处理数组时,它会将整个块复制到缓存中。
但是,如果你编写糟糕的代码,就会出现缓存未命中。你可以通过 搞乱嵌套循环的顺序 轻易地陷入这个陷阱。
并行性(多线程,同样的数据)必须按顺序分块处理,以充分利用CPU缓存。
手动编写线程将允许你手动选择线程的块,但这是一个麻烦的方法。
自4.0版本起,.NET提供了帮助程序,但默认的 Parallel.For 会搞乱缓存。
因此,由于 缓存未命中,这段代码实际上比单线程版本更慢。
Parallel.For(0, data1.Length,
fn =>
{
int x = data1[fn] - data2[fn];
data3[fn] = (x ^ (x >> 31)) - (x >> 31);
}
通过在缓存数据中执行顺序操作,可以手动利用缓存数据。例如,您可以展开循环,但这是一种不良的技巧,并且展开具有自己的性能问题(这取决于CPU型号)。
Parallel.For(0, data1.Length >> 3,
i =>
{
int b;
b = (data1[i + 0] - data2[i + 0]);
data3[i + 0] = b < 0 ? (b ^ -1) + b : b;
b = (data1[i + 1] - data2[i + 1]);
data3[i + 1] = b < 0 ? (b ^ -1) + b : b;
b = (data1[i + 2] - data2[i + 2]);
data3[i + 2] = b < 0 ? (b ^ -1) + b : b;
b = (data1[i + 3] - data2[i + 3]);
data3[i + 3] = b < 0 ? (b ^ -1) + b : b;
b = (data1[i + 3] - data2[i + 4]);
data3[i + 4] = b < 0 ? (b ^ -1) + b : b;
b = (data1[i + 5] - data2[i + 5]);
data3[i + 5] = b < 0 ? (b ^ -1) + b : b;
b = (data1[i + 6] - data2[i + 6]);
data3[i + 6] = b < 0 ? (b ^ -1) + b : b;
b = (data1[i + 7] - data2[i + 7]);
data3[i + 7] = b < 0 ? (b ^ -1) + b : b;
}
然而,.NET也有
Parrarel.ForEach和
Load Balancing Partitioners。使用它们两个可以获得最佳效果:
- 数据集大小独立的代码
- 简短、整洁的代码
- 多线程
- 良好的缓存使用
所以最终的代码将是:
var rangePartitioner = Partitioner.Create(0, data1.Length);
Parallel.ForEach(rangePartitioner, (range, loopState)
=>
{
for (int i = range.Item1; i < range.Item2; i++)
{
int x = data1[i] - data2[i];
data3[i] = (x ^ (x >> 31)) - (x >> 31);
}
});
它远未达到最大CPU使用率(这比仅仅将时钟加速更为复杂,有多个缓存级别、多条流水线等等),但它易读、快速且平台无关(除了整数大小,但C# int是System.Int32的别名,所以我们在这里是安全的)。
在这里,我认为我们应该停止优化。这篇文章不仅仅是一个答案,希望没有人因此清除我。