Java纯粹存在大数组会导致大量内存峰值

Question

我目前正在编写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的内存。

---

现在是有趣的部分：

当我运行代码以找到给定位置的最佳移动时，我通常首先创建转置表（如果清除，则将其清除已经存在）。但是我禁用了[[ALL对换位的访问表格，size()除外。如上所示，表中有get/put个方法带有print语句，并且它们在任何时候都不会被调用。

VisualVM在搜索以下位置时向我提供此内存输出换位表是在开始时创建的，但并未在任何时候。

如您所见，开始时内存使用率很高，并且收敛到相当低的水平。我最初以为搜索本身在开始时就消耗了这么多的内存（这是没有道理的）。所以我运行了[[exact same代码，除了this._transpositionTable = new TranspositionTable(20);

输出看起来像这样：

如您所见，搜索本身确实会导致[[NOT

导致这些内存峰值。

所以我的问题是：

为什么未使用的数组纯存在，导致这些内存峰值，尤其是仅在代码开头

是否有解决此问题的方法？

对我来说解决这个问题非常重要，因为在测试时，我需要同时运行多个引擎，因此内存成为问题。我很高兴能提供任何帮助或建议！

问候，芬兰

编辑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，这似乎可以解决问题。

Answer 1

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;
}

这种方法在运行时方面非常轻巧，因为编译器很可能会内联它，并且它在解决内存问题方面也起了很大作用。只需使用它即可访问您的表。

如果需要再次从表中删除条目，请编写类似的方法来写入表，如果'zero-case'为true，则将arrayindex设置为null。不要害怕null！如果操作正确，无效引用将是您的朋友。只是不要忘记，他们在那里。

并解决'为什么一个空数组会占用空间？'
对象数组（与原始类型的数组相反）分配的vm内存仅够存储它可能包含的所有引用，但不存储实际对象的空间。因此，如果您创建一个数组以容纳100 Strings，则您的数组将采用其自身开销+ 100个对象引用（无论它们是否存在）的内存大小。但是，引用的大小是特定于OS和VM的，并且可以变化，您需要为每个对象引用至少分配32位，并且（通常）最多分配64位。因此，大小为100的String数组分配100 * 64 +开销的空间位。