我正在使用box2d在Java中创建一个物理游戏。
我正在编写一个AI类,并希望在考虑内存对齐的情况下确保尽可能高效地存储我的数据。
最小的增加可能会产生巨大的变化,因为我实际上正在“尽可能多地运行AI对象”,直到系统变慢为止。该程序已经在碰撞检测上使用了大量内存,因为我想再次能够支持尽可能多的代理商。
到目前为止,我所了解的是,最小的Java类型是8bytes,并且对象被填充为8的倍数。我已经将我的AI控件构造为布尔数组,表示运动:x +/- 1,y +/- 1和顺时针方向/ CCW旋转用于某些灯具。
由于Java没有为布尔值设置空值,因此我将控件嵌套在具有bool值on_off和pos_neg的命令对象中。通过移动和旋转,我每个“默认”操作(例如向右移动)处理大约7个命令对象。所以我为每个动作创建Command数组。
我的问题是:我能有效地做到这一点吗?
我还没有完成设计,所以我不确定每个数组的大小。但是,考虑到内存对齐的要求,我猜我至少 会有一些 填充,这最终会浪费内存,我正在考虑做一些事情,例如削减对象大小以适合填充限制,然后将剩余数据从多个对象变成“溢出”对象…之类的东西。
这样会加快速度吗?为什么或者为什么不?
我还考虑使用位集,尽管我认为我的命令对象可能已经达到了类似的结果,并且有人告诉我位移很慢。
public class Command { boolean on_off = false; boolean pos_neg = false; } public class DefaultMoves { //Note: these arrays are 2d in the event multiples are necessary //to complete a single action, I may change this later. Command[][] mvRight = { { new Command(false, false), // new Command(false, false), // new Command(false, false), // new Command(false, false), // new Command(false, false), // new Command(true, true), //moveX new Command(false, false) // }, }; Command[][] mvLeft = { { new Command(false, false), // new Command(false, false), // new Command(false, false), // new Command(false, false), // new Command(false, false), // new Command(true, false), //moveX new Command(false, false) // }, }; }
这只是一个评论,但是有点冗长,我不想把它写成3条评论。
由于这是另一个后续问题,因此我将从“停止担心填充”开始。担心您如何存储数据。
而且,如果您担心自己的东西要占用多少空间,请分配7个对象而不是7个单个对象的数组。我确定Java每次分配都有开销。在典型的C或C ++实现中,每个带有new或malloc超过16-32个字节的分配都超出分配的实际数据的大小,并且大小四舍五入为16或32个字节。在Java中,这里有一个建议,即对象的内存开销为8字节- 这可能不适用于所有Java VM和实现。
new
malloc
此外,所有时空优化都是时空之间的折衷(至少几乎总是如此),因此以更紧凑的形式存储数据将节省时间以节省空间。例如,我可以认为在较大的整数结构中具有on_off和pos_neg为两个位。因此,您的7个命令将存储在一个整数中。但是,现在您必须进行移位和屏蔽才能获取正确的数据。同样,如果要存储某些内容,请转移和操作。(由于我不太了解Java,因此我将其编写为C)。
on_off
pos_neg
/* This is big enough for 16 pairs of on_off and pos_neg */ /* In a pair of bits, bit 0 = on_off, bit 1 = pos_neg */ uint32_t cmdData; /* Get values of on_off and pos_neg for element number n */ void getData(int n, bool& on_off, bool& pos_neg) { uint32_t shifted = cmdData >> (2 * n); on_off = (shifted & 1) != 0; pos_neg = (shifted & 2) != 0; } /* Store values for element n */ void setData(int n, bool on_off, bool pos_neg) { uint32_t bits = (int)on_off + (2 * (int)pos_neg); uint32_t mask = 3 << (n * 2); cmdData &= ~mask; /* Clear bits */ cmdData |= bits << (n * 2); }
如您所见,这可以更有效地存储数据,因为我们可以{on_off, pos_neg}在4个字节中存储16对数据,而不是每个(可能)占用一个字节。但是,要深入了解每种方法,您每次都必须执行一些额外的操作(并且代码变得更加混乱)。是否“值得拥有”在很大程度上取决于情况,访问这些对象的频率与系统的内存量有多低(假设这些对象的内存使用量是造成问题的原因- 如果您有100个命令结构,并且使用该命令的40000000个对象,那么这些命令就不会成为问题。
{on_off, pos_neg}
我存储方向/移动命令的方式可能是两个整数值(如果空间狭窄,则在int8_t[ bytejava中]),按住a +1可以例如向右或向下-1移动,向左或向上移动。这不是最紧凑的形式,但是它使您可以轻松访问和轻松计算新职位。
int8_t
byte
+1
-1
然后可以使用该对描述所有可能的方向:
struct direction { int x, y; }; direction directions[] = { { 0, 0 }, // Don't move. { 0, 1 }, // Right. { 0, -1 }, // Left. { 1, 0 }, // Down. { -1, 0 }, // Up. };
如果您也想对角移动,则必须添加另外四对,并结合{ 1, 1 }, {-1, 1},等等。
{ 1, 1 }, {-1, 1}
可以将其作为一对xDir, yDir值应用于可以移动的对象。
xDir, yDir
但关键是您首先要对更重要的内容(空间或计算)有一个很好的了解。从中,找出哪些对象占用了大部分空间(计数最高的对象)。摆弄一个或几十个物体的大小不会有太大的不同,有些东西你有数百万个意志。如果空间不是问题(为了公平起见,在具有千兆字节RAM的系统中,编写代码有效地使用足够大量的数据确实很困难- 如果您使用内存,通常是CPU耗尽了内存才耗尽速度对每一帧的每个对象做一些事情。
手提箱类比:
想象一下,您有一个手提箱,可以在其宽度上正好容纳4个小盒子(在长度上可以容纳任何数字- 这是一个奇怪的手提箱!),而您有一个大盒子,它们是1个,2个,3个或4个小盒子。盒子是用“魔术贴”制成的,所以它们可以粘在一起,可以随意拆分,但是您必须跟踪它们属于哪个,每次“拆分”或“放回”这些单元时,额外的时间。
如果您想变得懒惰并且简单易用,只需将三盒装的行李箱放进手提箱,每个箱子旁边都留一个空白。
1 2 3 4 a a a x b b b x c c c x d d d x
等等。
如果要紧紧包装,请先取一个3个单位的盒子,然后再切下一个,再将其粘贴在第一个旁边,然后将剩余的两个单位放在下一个空间,然后切成两个单位从下一个开始,并将其粘贴到数据包2旁边,依此类推。
1 2 3 4 a a a b b b c c c d d d
现在,您已经使用了25%的空间来存储它们,但是您花了一些时间将它们拆分,并且当您以后需要使用数据时,您不得不花时间再次将它们分成三个单元。
现在,想像一下您拿钱将东西放进手提箱,然后按所放物品的钱领取,您选择哪种方法?
然后,您不必为每件商品付费,而必须为行李箱空间付费(因为您是公司的所有者)。现在,您想尽可能地挤入空间。但这需要额外的时间,对吗?如果手提箱很贵,那也许值得。如果不是那么贵,您可能更希望节省时间而不是空间。这是一个妥协。
[我们可以以更实际的单位8、32或64进行相同的操作,但是我认为那只会使阅读变得更困难,并且打字也变得更加困难]