我目前正在编写一个 UCI 国际象棋引擎。在我的引擎中,我有一个将键映射到值的大转置表。
在实现这个的时候,我已经记住了内存并且不想在表格中放置东西时创建新对象所以我开始用空对象填充整个表格。
代码如下所示:
private TranspositionEntry[] entries;
private int size;
private int maxSize;
private long hashMask;
public TranspositionTable(int keyBits){
this.maxSize = (int)(Math.pow(2, keyBits));
this.hashMask = maxSize - 1;
this.entries = new TranspositionEntry[maxSize];
for(int i = 0; i < maxSize; i++){
this.entries[i] = new TranspositionEntry(0,0,0,0,0, new Move(0, 0, 0, 0));
}
}
private int index(long zobrist){
return (int)(zobrist & hashMask);
}
public boolean contains(long key){
int index = index(key);
return entries[index].getZobrist() != 0;
}
public void clear(){
for(int i = 0; i < maxSize; i++){
this.entries[i].setZobrist(0);
}
}
public int size(){
return size;
}
public TranspositionEntry get(long key){
System.out.println("I was called");
int index = index(key);
if(entries[index].getZobrist() == 0) return null;
return entries[index];
}
public void put(long key, double eval, int depthLeft, int node_tpe, int color, Move move){
int index = index(key);
System.out.println("I was called");
TranspositionEntry en = entries[index];
if(en.getZobrist() == 0) size++;
en.setVal(eval);
en.setDepthLeft(depthLeft);
en.setNode_type(node_tpe);
en.setColor(color);
en.getBestMove().setType(move.getType());
en.getBestMove().setFrom(move.getFrom());
en.getBestMove().setTo(move.getTo());
en.getBestMove().setPieceFrom(move.getPieceFrom());
en.getBestMove().setPieceTo(move.getPieceTo());
}
这是一个非常非常基本的哈希算法,但这与这个问题无关。 我通过运行这段代码测试了这个对象消耗了多少内存:
InstrumentationAgent.printMemoryOverview();
TranspositionTable<TranspositionEntry> entryTranspositionTable = new TranspositionTable<>(20);
InstrumentationAgent.printMemoryOverview();
System.out.println(entryTranspositionTable);
这给了我以下输出:
Used Memory : 7 MB
Free Memory : 483 MB
Total Memory : 491 MB
Max Memory : 7268 MB
Used Memory : 100 MB
Free Memory : 390 MB
Total Memory : 491 MB
Max Memory : 7268 MB
ai.tools.transpositions.TranspositionTable@1b6d3586
如您所见,此表本身确实消耗了大约 100MB
的内存。
有趣的部分来了:
When I run my code for finding a best move for a given position, I usually first create the transposition table (or clear it if it already exists). But I disabled ALL accesses to the transposition table except for
size()
. As you can see above, there areget/put
methods in the table with aVisualVM gives me this memory output when searching a position where the transposition table has been created at the start but isnt used at any time.
如您所见,内存使用率一开始很高,然后收敛到一个相当低的水平。
我最初认为搜索本身在开始时会消耗这么多内存(这没有意义)。所以我运行了完全相同的代码,除了this._transpositionTable = new TranspositionTable(20);
输出看起来像这样:
如您所见,搜索本身不会导致这些内存峰值。
所以我的问题是:
- 为什么纯粹存在未使用的数组会导致这些内存峰值,尤其是仅在代码开头
- 这个问题有解决方案吗?
解决这个问题对我来说非常重要,因为在测试时,我需要同时运行许多引擎,所以内存是个问题。对于任何帮助或建议,我都非常非常高兴!
您好, 芬恩
编辑 1:
添加 TranspositionEntry 代码:
private double val;
private long zobrist;
private int depthLeft;
private int node_type;
private int color;
private Move bestMove;
public TranspositionEntry(long zobrist, double val, int depthLeft, int node_type, int color, Move bestMove) {
this.val = val;
this.zobrist = zobrist;
this.depthLeft = depthLeft;
this.node_type = node_type;
this.color = color;
this.bestMove = bestMove;
}
编辑 2
我找到了解决这个问题的方法。
如果最大堆空间一开始就受到限制,那么尖峰似乎就不会出现。
我添加了 xmx1024M
,这似乎解决了问题。
最佳答案
除非表的很大一部分已满(例如 80%),否则您应该按需创建(和删除)条目以节省内存。 Java 中的对象存在,无论它们是否在数组(或其他对象)中被引用,直到垃圾收集器清理它们,在最后一个非弱引用被清除并且最后一个线程失去对该对象的访问权之后。即使那样,垃圾收集器也可能需要很长时间才能清理对象,具体取决于它的设置。最重要的是,一旦分配内存,JVM 就不愿意归还内存,因为重新分配它往往很昂贵。然而,以上所有内容都取决于实现。
填充表的具体建议,编写 ensureEntry
方法,按需在表中创建一个对象,这样您就不必在启动时初始化它:
public TranspositionEntry ensureEntry(int index) {
TranspositionEntry entry = this.entries[index];
if (entry == null) {
entry = new TranspositionEntry(0, 0, 0, 0, 0, new Move(0, 0, 0, 0));
this.entries[index] = entry;
}
return entry;
}
这样的方法在运行时是非常轻量级的,因为编译器很可能会内联它,并且它可以解决你的内存问题。只需使用它来访问您的表格。
如果您需要再次从表中删除条目,则编写一个类似的方法来写入您的表,如果“零大小写”为真,则将数组索引设置为null
。不要害怕 null
!如果做得对,nullary references 就是你的 friend 。只是不要忘记,它们就在那里。
并解决“为什么空数组会占用空间?”这个问题
对象数组(与基本类型数组相反)分配的 vm 内存刚好足以存储它可能包含的所有引用,但不是实际对象的空间。因此,如果您创建一个数组来容纳 100 个 Strings
,那么您的数组将占用其自身开销的内存中大小 + 100 个对象引用(无论它们是否存在)。然而,引用的大小是操作系统和 VM 特定的,并且可能会有所不同,您需要为每个对象引用至少分配 32 位并且(通常)最多 64 位。因此,大小为 100 的字符串数组分配 100 * 64 + 开销位的空间。
关于大型数组的Java纯粹存在导致大量内存尖峰,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/61521585/