数组遍历:并行性能比非并行慢
array traversing: parallel performance is slower than non parallel
在我的程序中,我想用这个循环确定有多少数字有 9 位数字,有多少数字有 8 位数字等等:
for (int i = 0; i < 60000000; i++)
{
if (a[i] >= 1000000000) { p[10] += 1; }
else if (a[i] >= 100000000) { p[9] += 1; }
else if (a[i] >= 10000000) { p[8] += 1; }
else if (a[i] >= 1000000) { p[7] += 1; }
else if (a[i] >= 100000) { p[6] += 1; }
else if (a[i] >= 10000) { p[5] += 1; }
else if (a[i] >= 1000) { p[4] += 1; }
else if (a[i] >= 100) { p[3] += 1; }
else if (a[i] >= 10) { p[2] += 1; }
else { p[1] += 1; }
}
我像这样并行化了循环:
void partiton(int f, int l, int[] p)
{
Parallel.Invoke(()=>calc(f,l/2,p),()=>calc(l/2,l,p));
}
void calc(int f, int l, int[] p)
{
for (int i = f; i < l; i++)
{
if (a[i] >= 1000000000) { p[10] += 1; }
else if (a[i] >= 100000000) { p[9] += 1; }
else if (a[i] >= 10000000) { p[8] += 1; }
else if (a[i] >= 1000000) { p[7] += 1; }
else if (a[i] >= 100000) { p[6] += 1; }
else if (a[i] >= 10000) { p[5] += 1; }
else if (a[i] >= 1000) { p[4] += 1; }
else if (a[i] >= 100) { p[3] += 1; }
else if (a[i] >= 10) { p[2] += 1; }
else { p[1] += 1; }
}
}
private void button1_Click(object sender, EventArgs e)
{
Stopwatch w = new Stopwatch();
w.Restart();
int f = 0;
int l = 60000000;
Parallel.Invoke(() => calc(f, l/2, p), () => calc(l/2, l, p));
w.Stop();
label1.Text = w.Elapsed.ToString();
}
但基准是:
顺序:0.3834
并行:0.6864
为什么并行代码比较慢?我的代码有问题吗?我的 cpu 是 AMD Phenom™ II X4。型号, 955.
- 这段代码不会给你正确的数字,因为它在没有同步的情况下增加了来自多个线程的相同变量。当不同的 CPU 核心处理同一个变量时,每个核心都有自己的版本,对该版本的修改不会立即流向其他缓存。因此,其他核心在旧版本上工作。例如,一个核可能将 p[0] 从 0 增加到 1,但另一个核仍然认为它是 0。因此当它增加它时,值再次变为 1。稍后这个1将出现在主存中而不是2。
- 回答你的问题,问题是你使用来自两个线程的同一块内存,这会减慢内存访问速度。数据通常被缓存,但是当一个核心写入内存区域时,其他核心迟早会检测到这一点,并且它们需要从速度很慢的主内存中重新加载它。 (早晚对你来说很重要,它不会立即发生,所以你需要同步,当你做对时,这会让一切变得更慢)。由于这些重新获取,多线程版本较慢。
当您尝试使算法成为多线程时,您需要尝试以不使用共享内存的方式分离任务。作为一种微优化 - 这是不好的 - 你可以尝试以它们不相邻的方式分配内存,否则前面提到的缓存问题会减慢处理速度。
都在变量里
以您的 p
对象为例。您将相同的 p
对象传递给 两个 线程。现在,我不确定 Parallel.Invoke
是否能够检测到这一点,因此是否可以串行执行它们(尽管开销很大),但我 do 知道如果它没有检测到这一点,那么您有 很多 次尝试 read/write 同一线程中的相同值。
现在,我使用您的代码作为基础构建了一个具体的小示例,这是它的副本。 (粘贴到任何新的控制台项目中,根据需要将 _Main
重命名为 Main
和 运行。)
static int[] a = new int[100000000];
static void calc(int f, int l, int[] p, int[] a)
{
for (int i = f; i < l; i++)
{
if (a[i] >= 1000000000) { p[10] += 1; }
else if (a[i] >= 100000000) { p[9] += 1; }
else if (a[i] >= 10000000) { p[8] += 1; }
else if (a[i] >= 1000000) { p[7] += 1; }
else if (a[i] >= 100000) { p[6] += 1; }
else if (a[i] >= 10000) { p[5] += 1; }
else if (a[i] >= 1000) { p[4] += 1; }
else if (a[i] >= 100) { p[3] += 1; }
else if (a[i] >= 10) { p[2] += 1; }
else { p[1] += 1; }
}
}
public static void _Main(string[] args)
{
for (int i = 0; i < a.Length; i++)
{
a[i] = i;
}
int f = 0;
int l = a.Length;
int[] p = new int[10];
int[] p1 = new int[10];
int[] p2 = new int[10];
int[] p3 = new int[10];
int[] p4 = new int[10];
int[] a1 = new int[l / 2];
int[] a2 = new int[l / 2];
int[] a11 = new int[l / 4];
int[] a12 = new int[l / 4];
int[] a13 = new int[l / 4];
int[] a14 = new int[l / 4];
for (int i = 0; i < a.Length; i++)
if (i >= l / 2)
a2[i - l / 2] = a[i];
else
a1[i] = a[i];
for (int i = 0; i < a.Length; i++)
if (i >= l / 4 * 3)
a14[i - l / 4 * 3] = a[i];
else if (i >= l / 4 * 2)
a13[i - l / 4 * 2] = a[i];
else if (i >= l / 4 * 1)
a12[i - l / 4] = a[i];
else
a14[i] = a[i];
int rc = 5;
for (int d = 0; d < rc; d++)
{
Stopwatch w = new Stopwatch();
w.Start();
Parallel.Invoke(() => calc(f, l / 2, p1, a1), () => calc(f, l / 2, p2, a2));
w.Stop();
Console.WriteLine("Attempt {0}/{1}: {2}", 1, d, w.ElapsedMilliseconds);
w.Reset();
w.Start();
Parallel.Invoke(() => calc(f, l / 4, p1, a11), () => calc(f, l / 4, p2, a12), () => calc(f, l / 4, p3, a13), () => calc(f, l / 4, p4, a14));
w.Stop();
Console.WriteLine("Attempt {0}/{1}: {2}", 2, d, w.ElapsedMilliseconds);
w.Reset();
w.Start();
Parallel.Invoke(() => calc(f, l / 2, p, a), () => calc(l / 2, l, p, a));
w.Stop();
Console.WriteLine("Attempt {0}/{1}: {2}", 3, d, w.ElapsedMilliseconds);
w.Reset();
w.Start();
calc(f, l, p, a);
w.Stop();
Console.WriteLine("Attempt {0}/{1}: {2}", 4, d, w.ElapsedMilliseconds);
}
}
我确定我可以进行更多优化 运行。 (例如,将 if
转换为 while
循环。)我也无法保证它的准确性。我只是接受了你的逻辑并对其进行了适当的调试。
但是当我在我的电脑上 运行 这个确切的例子时,我得到了以下结果:
- 第一次尝试平均耗时 327.8 毫秒。此尝试将
a
和 p
变量拆分为 两个 个单独的变量。
- 第二次尝试平均耗时 306 毫秒。此尝试将
a
和 p
变量拆分为 四个 个单独的变量。
- 尝试 3 平均耗时 703 毫秒。这与您所做的完全相同。 (尽管在
calc
方法上有一个局部变量。
- 第 4 次尝试平均耗时 347.6 毫秒。这是 运行同步
calc
方法。
为什么差别这么大?尝试 1 和 2 将处理后的数据拆分为不需要线程同步的变量,而尝试 3 强制两个线程使用相同的变量,造成冲突,正如 Ron Beyer 所说,上下文切换。
基本上,如果您要尝试并行写入相同的 任何内容,您应该本地化每个线程正在写入的数据并在最后合并更改。
在我的程序中,我想用这个循环确定有多少数字有 9 位数字,有多少数字有 8 位数字等等:
for (int i = 0; i < 60000000; i++)
{
if (a[i] >= 1000000000) { p[10] += 1; }
else if (a[i] >= 100000000) { p[9] += 1; }
else if (a[i] >= 10000000) { p[8] += 1; }
else if (a[i] >= 1000000) { p[7] += 1; }
else if (a[i] >= 100000) { p[6] += 1; }
else if (a[i] >= 10000) { p[5] += 1; }
else if (a[i] >= 1000) { p[4] += 1; }
else if (a[i] >= 100) { p[3] += 1; }
else if (a[i] >= 10) { p[2] += 1; }
else { p[1] += 1; }
}
我像这样并行化了循环:
void partiton(int f, int l, int[] p)
{
Parallel.Invoke(()=>calc(f,l/2,p),()=>calc(l/2,l,p));
}
void calc(int f, int l, int[] p)
{
for (int i = f; i < l; i++)
{
if (a[i] >= 1000000000) { p[10] += 1; }
else if (a[i] >= 100000000) { p[9] += 1; }
else if (a[i] >= 10000000) { p[8] += 1; }
else if (a[i] >= 1000000) { p[7] += 1; }
else if (a[i] >= 100000) { p[6] += 1; }
else if (a[i] >= 10000) { p[5] += 1; }
else if (a[i] >= 1000) { p[4] += 1; }
else if (a[i] >= 100) { p[3] += 1; }
else if (a[i] >= 10) { p[2] += 1; }
else { p[1] += 1; }
}
}
private void button1_Click(object sender, EventArgs e)
{
Stopwatch w = new Stopwatch();
w.Restart();
int f = 0;
int l = 60000000;
Parallel.Invoke(() => calc(f, l/2, p), () => calc(l/2, l, p));
w.Stop();
label1.Text = w.Elapsed.ToString();
}
但基准是: 顺序:0.3834 并行:0.6864
为什么并行代码比较慢?我的代码有问题吗?我的 cpu 是 AMD Phenom™ II X4。型号, 955.
- 这段代码不会给你正确的数字,因为它在没有同步的情况下增加了来自多个线程的相同变量。当不同的 CPU 核心处理同一个变量时,每个核心都有自己的版本,对该版本的修改不会立即流向其他缓存。因此,其他核心在旧版本上工作。例如,一个核可能将 p[0] 从 0 增加到 1,但另一个核仍然认为它是 0。因此当它增加它时,值再次变为 1。稍后这个1将出现在主存中而不是2。
- 回答你的问题,问题是你使用来自两个线程的同一块内存,这会减慢内存访问速度。数据通常被缓存,但是当一个核心写入内存区域时,其他核心迟早会检测到这一点,并且它们需要从速度很慢的主内存中重新加载它。 (早晚对你来说很重要,它不会立即发生,所以你需要同步,当你做对时,这会让一切变得更慢)。由于这些重新获取,多线程版本较慢。
当您尝试使算法成为多线程时,您需要尝试以不使用共享内存的方式分离任务。作为一种微优化 - 这是不好的 - 你可以尝试以它们不相邻的方式分配内存,否则前面提到的缓存问题会减慢处理速度。
都在变量里
以您的 p
对象为例。您将相同的 p
对象传递给 两个 线程。现在,我不确定 Parallel.Invoke
是否能够检测到这一点,因此是否可以串行执行它们(尽管开销很大),但我 do 知道如果它没有检测到这一点,那么您有 很多 次尝试 read/write 同一线程中的相同值。
现在,我使用您的代码作为基础构建了一个具体的小示例,这是它的副本。 (粘贴到任何新的控制台项目中,根据需要将 _Main
重命名为 Main
和 运行。)
static int[] a = new int[100000000];
static void calc(int f, int l, int[] p, int[] a)
{
for (int i = f; i < l; i++)
{
if (a[i] >= 1000000000) { p[10] += 1; }
else if (a[i] >= 100000000) { p[9] += 1; }
else if (a[i] >= 10000000) { p[8] += 1; }
else if (a[i] >= 1000000) { p[7] += 1; }
else if (a[i] >= 100000) { p[6] += 1; }
else if (a[i] >= 10000) { p[5] += 1; }
else if (a[i] >= 1000) { p[4] += 1; }
else if (a[i] >= 100) { p[3] += 1; }
else if (a[i] >= 10) { p[2] += 1; }
else { p[1] += 1; }
}
}
public static void _Main(string[] args)
{
for (int i = 0; i < a.Length; i++)
{
a[i] = i;
}
int f = 0;
int l = a.Length;
int[] p = new int[10];
int[] p1 = new int[10];
int[] p2 = new int[10];
int[] p3 = new int[10];
int[] p4 = new int[10];
int[] a1 = new int[l / 2];
int[] a2 = new int[l / 2];
int[] a11 = new int[l / 4];
int[] a12 = new int[l / 4];
int[] a13 = new int[l / 4];
int[] a14 = new int[l / 4];
for (int i = 0; i < a.Length; i++)
if (i >= l / 2)
a2[i - l / 2] = a[i];
else
a1[i] = a[i];
for (int i = 0; i < a.Length; i++)
if (i >= l / 4 * 3)
a14[i - l / 4 * 3] = a[i];
else if (i >= l / 4 * 2)
a13[i - l / 4 * 2] = a[i];
else if (i >= l / 4 * 1)
a12[i - l / 4] = a[i];
else
a14[i] = a[i];
int rc = 5;
for (int d = 0; d < rc; d++)
{
Stopwatch w = new Stopwatch();
w.Start();
Parallel.Invoke(() => calc(f, l / 2, p1, a1), () => calc(f, l / 2, p2, a2));
w.Stop();
Console.WriteLine("Attempt {0}/{1}: {2}", 1, d, w.ElapsedMilliseconds);
w.Reset();
w.Start();
Parallel.Invoke(() => calc(f, l / 4, p1, a11), () => calc(f, l / 4, p2, a12), () => calc(f, l / 4, p3, a13), () => calc(f, l / 4, p4, a14));
w.Stop();
Console.WriteLine("Attempt {0}/{1}: {2}", 2, d, w.ElapsedMilliseconds);
w.Reset();
w.Start();
Parallel.Invoke(() => calc(f, l / 2, p, a), () => calc(l / 2, l, p, a));
w.Stop();
Console.WriteLine("Attempt {0}/{1}: {2}", 3, d, w.ElapsedMilliseconds);
w.Reset();
w.Start();
calc(f, l, p, a);
w.Stop();
Console.WriteLine("Attempt {0}/{1}: {2}", 4, d, w.ElapsedMilliseconds);
}
}
我确定我可以进行更多优化 运行。 (例如,将 if
转换为 while
循环。)我也无法保证它的准确性。我只是接受了你的逻辑并对其进行了适当的调试。
但是当我在我的电脑上 运行 这个确切的例子时,我得到了以下结果:
- 第一次尝试平均耗时 327.8 毫秒。此尝试将
a
和p
变量拆分为 两个 个单独的变量。 - 第二次尝试平均耗时 306 毫秒。此尝试将
a
和p
变量拆分为 四个 个单独的变量。 - 尝试 3 平均耗时 703 毫秒。这与您所做的完全相同。 (尽管在
calc
方法上有一个局部变量。 - 第 4 次尝试平均耗时 347.6 毫秒。这是 运行同步
calc
方法。
为什么差别这么大?尝试 1 和 2 将处理后的数据拆分为不需要线程同步的变量,而尝试 3 强制两个线程使用相同的变量,造成冲突,正如 Ron Beyer 所说,上下文切换。
基本上,如果您要尝试并行写入相同的 任何内容,您应该本地化每个线程正在写入的数据并在最后合并更改。