StackOverflow 如果使用 Parallel.For
StackOverflow if using Parallel.For
我目前正在尝试编写代码,这将有助于计算为游戏 StarMade 设置的高效反应器。
我正在使用递归方法来探索 3d 元素树并找到所有相关组。对于前。组 - 它是一组元素,彼此靠近。
在图片上是这样的:
XOX
OOX
XXO
其中 O 什么都不是,X 是反应器(元素)。
在这张图片上有 3 组元素。 [0,0], [2,0]-[2,1], [0,2]-[1,2]
另一种变体:
XXX
OOX
XXX
这里只有一组,因为所有元素都靠得很近。
这是我的代码:
void CheckGroup(int x, int y, int z, Group group)
{
if(x >= maxz || x < 0 || y >= maxy || y < 0 || z >= maxz || z < 0)
{
return;
}
if (reactorsChecked[x, y, z])
{
return;
}
reactorsChecked[x, y, z] = true;
if (reactors[x, y, z])
{
if (group == null)
{
group = new Group();
group.MaxX = x;
group.MaxY = y;
group.MaxZ = z;
group.MinX = x;
group.MinY = y;
group.MinZ = z;
group.Blocks = 1;
}
else
{
group.MaxX = Math.Max(group.MaxX, x);
group.MaxY = Math.Max(group.MaxY, y);
group.MaxZ = Math.Max(group.MaxZ, z);
group.MinX = Math.Min(group.MinX, x);
group.MinY = Math.Min(group.MinY, y);
group.MinZ = Math.Min(group.MinZ, z);
group.Blocks += 1;
}
CheckGroup(x + 1, y, z, group);
CheckGroup(x - 1, y, z, group);
CheckGroup(x, y + 1, z, group);
CheckGroup(x, y - 1, z, group);
CheckGroup(x, y, z + 1, group);
CheckGroup(x, y, z - 1, group);
if (!groups.Contains(group))
{
groups.Add(group);
}
}
}
group - 对于集群来说很简单class,它存储有关该集群中元素计数和该集群边界框的数据。
reactorsChecked - 是简单的 bool[] 数组,它存储关于元素的信息,我们已经检查过,以避免双打
reactor - 随机元素的简单 bool[] 数组。
首先我将随机值插入反应器数组,然后调用 CheckGroup(x,y,z,null)。如果反应器阵列大小小于 25x25x25,则一切正常。在单线程中,数组的大小可以是 100x100x100,一切都可以。但是如果我尝试使用 Parallel.For,那么在将近 9000 次递归之后我得到了 Whosebug...
这是完整的代码:
Parallel.For(0, Environment.ProcessorCount, (i) =>
{
Calculator calc = new Calculator(x, y, z, max, cycles);
calcs.Add(calc);
});
public class Calculator
{
Random rnd = new Random();
//List<Group> groups = new List<Group>();
HashSet<Group> groups = new HashSet<Group>();
bool[, ,] reactors;
public bool[, ,] reactorsMax;
bool[, ,] reactorsChecked;
public double maxEnergy = 0;
public string result = "";
public string resultPic = "";
int maxx, maxy, maxz;
public Calculator(int x, int y, int z, int max, int cycles)
{
maxx = x;
maxy = y;
maxz = z;
maxEnergy = max;
for (int i = 0; i < cycles; i++)//check few variants per thread
{
Calculate(x,y,z);
}
}
private void Calculate(int X, int Y, int Z)
{
//groups = new List<Group>();
groups = new HashSet<Group>();
reactors = new bool[X, Y, Z];
for (int x = 0; x < X; x++)
{
for (int y = 0; y < Y; y++)
{
for (int z = 0; z < Z; z++)
{
reactors[x, y, z] = rnd.Next(2)==1;//fill array with random values
}
}
}
reactorsChecked = new bool[X, Y, Z];
for (int x = 0; x < X; x++)
{
for (int y = 0; y < Y; y++)
{
for (int z = 0; z < Z; z++)
{
CheckGroup(x, y, z, null);//start calculations
}
}
}
double sum = 0;
int blocks = 0;
foreach(Group g in groups)
{
float dims = g.MaxX - g.MinX + g.MaxY - g.MinY + g.MaxZ - g.MinZ + 3;
sum += (2000000.0f / (1.0f + Math.Pow(1.000696f, (-0.333f * Math.Pow((dims / 3.0f), 1.7)))) - 1000000.0f + 25.0f * g.Blocks);
blocks += g.Blocks;
}
if (sum > maxEnergy)
{
maxEnergy = sum;
reactorsMax = reactors;
}
}
void CheckGroup(int x, int y, int z, Group group)
{
if(x >= maxz || x < 0 || y >= maxy || y < 0 || z >= maxz || z < 0)
{
return;
}
if (reactorsChecked[x, y, z])
{
return;
}
reactorsChecked[x, y, z] = true;
if (reactors[x, y, z])
{
if (group == null)
{
group = new Group();
group.MaxX = x;
group.MaxY = y;
group.MaxZ = z;
group.MinX = x;
group.MinY = y;
group.MinZ = z;
group.Blocks = 1;
}
else
{
group.MaxX = Math.Max(group.MaxX, x);
group.MaxY = Math.Max(group.MaxY, y);
group.MaxZ = Math.Max(group.MaxZ, z);
group.MinX = Math.Min(group.MinX, x);
group.MinY = Math.Min(group.MinY, y);
group.MinZ = Math.Min(group.MinZ, z);
group.Blocks += 1;
}
CheckGroup(x + 1, y, z, group);
CheckGroup(x - 1, y, z, group);
CheckGroup(x, y + 1, z, group);
CheckGroup(x, y - 1, z, group);
CheckGroup(x, y, z + 1, group);
CheckGroup(x, y, z - 1, group);
if (!groups.Contains(group))
{
groups.Add(group);
}
}
}
}
所以主要问题 - 是否可以在 Parallel.For 中避免 Whosebug,或者将其重写为迭代循环?
Parallel.For 使用默认的 stackSize 值,即使您将使用
Thread(()=>
{
Parallel.For(...);
},stackSize).Start()
它将使用默认值...
我不喜欢这样的变体:
for(int i = 0; i < cpuCount; i++)
{
Thread t = new Thread(()=>{calculate();},stackSize).Start()
}
因为我必须管理所有线程,等待所有线程完成,所以它使代码变得非常复杂...可能有更简单的事情吗?
有两个选项:
使用递归并尝试增加堆栈大小(通过使用 Thread(ThreadStart, maxStackSize)
constructor). The stack in applications is usually set to 1MB (see this link 了解详细信息)。特别是在没有优化的 DEBUG 模式下(没有完成内联优化),这是一个非常有限的值。每个 Paralllel.For()
语句都有一个带有单独堆栈的线程
可能有帮助。
使用迭代查找而不是递归来自行处理堆栈深度。
我个人会选择选项 1。(有或没有单独的堆栈)仅在我知道递归的最大深度的情况下。
在像您这样的大多数情况下,我的首选解决方案是迭代方法。
@LordXaosa 编辑:
我试过了,一切正常
int stackSize = 1024*1024*1024;//1GB limit
ManualResetEvent[] mre = new ManualResetEvent[Environment.ProcessorCount];
Parallel.For(0, Environment.ProcessorCount, (i) =>
{
mre[i] = new ManualResetEvent(false);
Thread t = new Thread((object reset) =>
{
Calculator calc = new Calculator(x, y, z, max, cycles);
calcs.Add(calc);
ManualResetEvent m = (ManualResetEvent)reset;
m.Set();
}, stackSize / (Environment.ProcessorCount * 4));
t.Start(mre[i]);
});
WaitHandle.WaitAll(mre);
但也有一个限制...50x50x50 数组工作正常,但更多 - 堆栈溢出...在原始游戏中它可以处理 1000x1000x1000 组,所以可能有另一种算法。
感谢您的帮助!
我目前正在尝试编写代码,这将有助于计算为游戏 StarMade 设置的高效反应器。 我正在使用递归方法来探索 3d 元素树并找到所有相关组。对于前。组 - 它是一组元素,彼此靠近。 在图片上是这样的:
XOX
OOX
XXO
其中 O 什么都不是,X 是反应器(元素)。 在这张图片上有 3 组元素。 [0,0], [2,0]-[2,1], [0,2]-[1,2] 另一种变体:
XXX
OOX
XXX
这里只有一组,因为所有元素都靠得很近。 这是我的代码:
void CheckGroup(int x, int y, int z, Group group)
{
if(x >= maxz || x < 0 || y >= maxy || y < 0 || z >= maxz || z < 0)
{
return;
}
if (reactorsChecked[x, y, z])
{
return;
}
reactorsChecked[x, y, z] = true;
if (reactors[x, y, z])
{
if (group == null)
{
group = new Group();
group.MaxX = x;
group.MaxY = y;
group.MaxZ = z;
group.MinX = x;
group.MinY = y;
group.MinZ = z;
group.Blocks = 1;
}
else
{
group.MaxX = Math.Max(group.MaxX, x);
group.MaxY = Math.Max(group.MaxY, y);
group.MaxZ = Math.Max(group.MaxZ, z);
group.MinX = Math.Min(group.MinX, x);
group.MinY = Math.Min(group.MinY, y);
group.MinZ = Math.Min(group.MinZ, z);
group.Blocks += 1;
}
CheckGroup(x + 1, y, z, group);
CheckGroup(x - 1, y, z, group);
CheckGroup(x, y + 1, z, group);
CheckGroup(x, y - 1, z, group);
CheckGroup(x, y, z + 1, group);
CheckGroup(x, y, z - 1, group);
if (!groups.Contains(group))
{
groups.Add(group);
}
}
}
group - 对于集群来说很简单class,它存储有关该集群中元素计数和该集群边界框的数据。 reactorsChecked - 是简单的 bool[] 数组,它存储关于元素的信息,我们已经检查过,以避免双打 reactor - 随机元素的简单 bool[] 数组。 首先我将随机值插入反应器数组,然后调用 CheckGroup(x,y,z,null)。如果反应器阵列大小小于 25x25x25,则一切正常。在单线程中,数组的大小可以是 100x100x100,一切都可以。但是如果我尝试使用 Parallel.For,那么在将近 9000 次递归之后我得到了 Whosebug... 这是完整的代码:
Parallel.For(0, Environment.ProcessorCount, (i) =>
{
Calculator calc = new Calculator(x, y, z, max, cycles);
calcs.Add(calc);
});
public class Calculator
{
Random rnd = new Random();
//List<Group> groups = new List<Group>();
HashSet<Group> groups = new HashSet<Group>();
bool[, ,] reactors;
public bool[, ,] reactorsMax;
bool[, ,] reactorsChecked;
public double maxEnergy = 0;
public string result = "";
public string resultPic = "";
int maxx, maxy, maxz;
public Calculator(int x, int y, int z, int max, int cycles)
{
maxx = x;
maxy = y;
maxz = z;
maxEnergy = max;
for (int i = 0; i < cycles; i++)//check few variants per thread
{
Calculate(x,y,z);
}
}
private void Calculate(int X, int Y, int Z)
{
//groups = new List<Group>();
groups = new HashSet<Group>();
reactors = new bool[X, Y, Z];
for (int x = 0; x < X; x++)
{
for (int y = 0; y < Y; y++)
{
for (int z = 0; z < Z; z++)
{
reactors[x, y, z] = rnd.Next(2)==1;//fill array with random values
}
}
}
reactorsChecked = new bool[X, Y, Z];
for (int x = 0; x < X; x++)
{
for (int y = 0; y < Y; y++)
{
for (int z = 0; z < Z; z++)
{
CheckGroup(x, y, z, null);//start calculations
}
}
}
double sum = 0;
int blocks = 0;
foreach(Group g in groups)
{
float dims = g.MaxX - g.MinX + g.MaxY - g.MinY + g.MaxZ - g.MinZ + 3;
sum += (2000000.0f / (1.0f + Math.Pow(1.000696f, (-0.333f * Math.Pow((dims / 3.0f), 1.7)))) - 1000000.0f + 25.0f * g.Blocks);
blocks += g.Blocks;
}
if (sum > maxEnergy)
{
maxEnergy = sum;
reactorsMax = reactors;
}
}
void CheckGroup(int x, int y, int z, Group group)
{
if(x >= maxz || x < 0 || y >= maxy || y < 0 || z >= maxz || z < 0)
{
return;
}
if (reactorsChecked[x, y, z])
{
return;
}
reactorsChecked[x, y, z] = true;
if (reactors[x, y, z])
{
if (group == null)
{
group = new Group();
group.MaxX = x;
group.MaxY = y;
group.MaxZ = z;
group.MinX = x;
group.MinY = y;
group.MinZ = z;
group.Blocks = 1;
}
else
{
group.MaxX = Math.Max(group.MaxX, x);
group.MaxY = Math.Max(group.MaxY, y);
group.MaxZ = Math.Max(group.MaxZ, z);
group.MinX = Math.Min(group.MinX, x);
group.MinY = Math.Min(group.MinY, y);
group.MinZ = Math.Min(group.MinZ, z);
group.Blocks += 1;
}
CheckGroup(x + 1, y, z, group);
CheckGroup(x - 1, y, z, group);
CheckGroup(x, y + 1, z, group);
CheckGroup(x, y - 1, z, group);
CheckGroup(x, y, z + 1, group);
CheckGroup(x, y, z - 1, group);
if (!groups.Contains(group))
{
groups.Add(group);
}
}
}
}
所以主要问题 - 是否可以在 Parallel.For 中避免 Whosebug,或者将其重写为迭代循环?
Parallel.For 使用默认的 stackSize 值,即使您将使用
Thread(()=>
{
Parallel.For(...);
},stackSize).Start()
它将使用默认值...
我不喜欢这样的变体:
for(int i = 0; i < cpuCount; i++)
{
Thread t = new Thread(()=>{calculate();},stackSize).Start()
}
因为我必须管理所有线程,等待所有线程完成,所以它使代码变得非常复杂...可能有更简单的事情吗?
有两个选项:
使用递归并尝试增加堆栈大小(通过使用
Thread(ThreadStart, maxStackSize)
constructor). The stack in applications is usually set to 1MB (see this link 了解详细信息)。特别是在没有优化的 DEBUG 模式下(没有完成内联优化),这是一个非常有限的值。每个Paralllel.For()
语句都有一个带有单独堆栈的线程 可能有帮助。使用迭代查找而不是递归来自行处理堆栈深度。
我个人会选择选项 1。(有或没有单独的堆栈)仅在我知道递归的最大深度的情况下。
在像您这样的大多数情况下,我的首选解决方案是迭代方法。
@LordXaosa 编辑: 我试过了,一切正常
int stackSize = 1024*1024*1024;//1GB limit
ManualResetEvent[] mre = new ManualResetEvent[Environment.ProcessorCount];
Parallel.For(0, Environment.ProcessorCount, (i) =>
{
mre[i] = new ManualResetEvent(false);
Thread t = new Thread((object reset) =>
{
Calculator calc = new Calculator(x, y, z, max, cycles);
calcs.Add(calc);
ManualResetEvent m = (ManualResetEvent)reset;
m.Set();
}, stackSize / (Environment.ProcessorCount * 4));
t.Start(mre[i]);
});
WaitHandle.WaitAll(mre);
但也有一个限制...50x50x50 数组工作正常,但更多 - 堆栈溢出...在原始游戏中它可以处理 1000x1000x1000 组,所以可能有另一种算法。 感谢您的帮助!