如何高效地在Java中存储小的字节数组？

Question

我所谓的小型字节数组是指长度为10到30的字节数组。

我所说的存储是指将它们存储在RAM中，而不是序列化并持久化到文件系统。

系统macOS 10.12.6，Oracle jdk1.8.0_141 64位，JVM参数-Xmx1g

示例： new byte [200 * 1024 * 1024]的预期行为是占用约200MB的堆空间。

public static final int TARGET_SIZE = 200 * 1024 * 1024;
public static void main(String[] args) throws InterruptedException {
    byte[] arr = new byte[TARGET_SIZE];
    System.gc();
    System.out.println("Array size: " + arr.length);
    System.out.println("HeapSize: " + Runtime.getRuntime().totalMemory());
    Thread.sleep(60000);
}

但对于较小的数组来说，数学并不那么简单

public static final int TARGET_SIZE = 200 * 1024 * 1024;
public static void main(String[] args) throws InterruptedException {
    final int oneArraySize = 20;
    final int numberOfArrays = TARGET_SIZE / oneArraySize;
    byte[][] arrays = new byte[numberOfArrays][];
    for (int i = 0; i < numberOfArrays; i++) {
        arrays[i] = new byte[oneArraySize];
    }
    System.gc();
    System.out.println("Arrays size: " + arrays.length);
    System.out.println("HeapSize: " + Runtime.getRuntime().totalMemory());
    Thread.sleep(60000);
}

更糟糕的是

问题是

这个开销从哪里来？ 如何高效地存储和处理小字节数组（数据块）？

更新1

对于 new byte[200*1024*1024][1]，它占用了

基本数学计算表明，new byte[1] 占用 24 字节。

更新2

根据 Java 中对象的内存消耗是多少？ Java 中对象的最小大小为16字节。从我之前的 "测量" 结果来看，24字节 -4字节表示 int 长度 -1字节实际数据 = 3字节的其他 垃圾 填充。

- kisileno

---

这个“overhead”是从哪里来的？数组对象本身也会占用内存，不仅仅是它们的内容。即使是一个空数组也会占用内存。 - Robby Cornelissen

数组是一个对象，具有超过Typex [N]的头部，类型声明，vtable和块的GC信息，就像所有对象一样。通过艰苦的专业工作，例如移动到“非堆”区域，其中垃圾收集器不起作用，一切都是完全手动的（从操作系统获取几百万字节并进行所需操作）。许多缓存系统具有非堆缓冲区。数字系统？我不知道，理论上可能。 - Jacek Cz

每个数组都有一个名为length的public final字段，它包含数组的元素数量，length可以是正数或零。每个数组最小的开销为4字节（加上从java.lang.Object继承的任何开销），这对于10字节的数组来说是最小的40%的惩罚（每个数组）。你究竟想要实现什么目标？ - Elliott Frisch

如果您仍然对标题中的问题感兴趣：请将其隐藏在接口后面。interface Data { byte get(int x, int y); void set(int x, int y, byte b)}。然后，您可以将所有内容存储在单个数组中。如果更方便，您还可以以ByteBuffer的形式返回此大型数组的“切片”（使用ByteBuffer#slice方法）。 - Marco13

@Eugene 已添加。在这种情况下，我总是不得不克制自己，不去详细阐述所有实现选项以及每种方法的优缺点...然而，关键点可能是当使用（隐藏的）1D数组进行存储时，开销才能（仅？）被避免。 - Marco13

Answer 1

好的，如果我理解正确（如果不是，请询问-我会尽力回答），这里有几件事情。首先是你需要正确的测量工具和JOL是唯一一个我信任的。

让我们开始简单的：

byte[] two = new byte[1];
System.out.println(GraphLayout.parseInstance(one).toFootprint()); 

这将显示24字节(12用于标记和类单词-或对象头+4个字节的填充), 1字节用于实际值和7字节的填充(内存以8字节对齐)。

考虑到这一点，这应该是可预测的输出：

byte[] eight = new byte[8];
System.out.println(GraphLayout.parseInstance(eight).toFootprint()); // 24 bytes

byte[] nine = new byte[9];
System.out.println(GraphLayout.parseInstance(nine).toFootprint()); // 32 bytes

现在让我们转向二维数组：

byte[][] ninenine = new byte[9][9];    
System.out.println(GraphLayout.parseInstance(ninenine).toFootprint()); // 344 bytes

System.out.println(ClassLayout.parseInstance(ninenine).toPrintable());

由于Java没有真正的二维数组，每个嵌套数组本身都是一个带有头和内容的对象 (byte[])。因此，单个byte[9]具有32个字节 (12个字节+4个字节填充)和16个字节的内容(实际内容9个字节+7个字节填充)。

ninenine 对象共有56个字节: 16个字节头+36个字节保存对九个对象的引用+4个字节填充。

---

看这里产生的示例:

byte[][] left = new byte[10000][10];
System.out.println(GraphLayout.parseInstance(left).toFootprint()); // 360016 bytes

byte[][] right = new byte[10][10000];
System.out.println(GraphLayout.parseInstance(right).toFootprint()); // 100216 bytes

这是一个260%的增加，只需将工作方式改为相反的方向即可节省大量空间。

但更深层次的问题在于，Java中的每个对象都有这些头信息，目前还没有无头对象。它们可能会出现并被称为值类型。当实现这一点时，至少基本数组不会有这种开销。

- Eugene

---

一个旁注： “Value Types” 是一个非常古老的提议，很可能以某种形式出现。 特别是，在 Project Panama 中有关使用这些类型的“矢量 API”的讨论已经进行了广泛。 尽管，不幸的是，我最近没能深入跟进讨论和建议，但这可能与其有关（请参见 http://mail.openjdk.java.net/pipermail/panama-dev/2017-July/000622.html 周围的消息 - 有很多），至少当假设这些小字节数组最终应该是“某种向量”时。 - Marco13

Answer 2

Eugene的回答解释了为什么在大量数组中观察到内存消耗增加的原因。那么标题中的问题，"如何高效地存储Java中的小字节数组？" 的答案可能是：完全不需要。 ¹ 然而，可能有方法可以实现您的目标。像往常一样，这里的“最佳”解决方案取决于这些数据将如何被使用。一个非常实用的方法是：为您的数据结构定义一个接口。

在最简单的情况下，此接口可能只需是：

interface ByteArray2D 
{
    int getNumRows();
    int getNumColumns();
    byte get(int r, int c);
    void set(int r, int c, byte b);
}

提供一个“2D字节数组”的基本抽象。根据应用情况，可能有必要在此处提供其他方法。这里可以使用的模式通常与处理“2D矩阵”（通常是float值）的矩阵库相关，并且它们经常提供以下方法：

interface Matrix {
    Vector getRow(int row);
    Vector getColumn(int column);
    ...
}

然而，当主要目的是处理一组byte[]数组时，访问每个数组（即2D数组的每一行）的方法可能已经足够：

ByteBuffer getRow(int row);

---

有了这个接口，创建不同的实现就非常简单。例如，您可以创建一个简单的实现，只是在内部存储一个 2D 的 byte[][] 数组：

class SimpleByteArray2D implements ByteArray2D 
{
    private final byte array[][];
    ...
}

或者，您可以创建一个存储1Dbyte[]数组或类似的ByteBuffer的实现来内部存储：

class CompactByteArray2D implements ByteArray2D
{
    private final ByteBuffer buffer;
    ...
}

这个实现只需要在调用访问二维数组的某一行/列的方法时计算(1D)索引即可。 下面是一个MCVE，展示了这个接口和两个实现，介绍了接口的基本用法，并使用JOL进行内存占用分析。 该程序的输出为：

For 10 rows and 1000 columns:
Total size for SimpleByteArray2D : 10240
Total size for CompactByteArray2D: 10088

For 100 rows and 100 columns:
Total size for SimpleByteArray2D : 12440
Total size for CompactByteArray2D: 10088

For 1000 rows and 10 columns:
Total size for SimpleByteArray2D : 36040
Total size for CompactByteArray2D: 10088

展示：

• 当行数增加时（即使数组的总大小保持不变），基于简单2D byte[][]数组的SimpleByteArray2D实现需要更多的内存。

• CompactByteArray2D的内存消耗与数组的结构无关。

整个程序：

package stackoverflow;

import java.nio.ByteBuffer;

import org.openjdk.jol.info.GraphLayout;

public class EfficientByteArrayStorage
{
    public static void main(String[] args)
    {
        showExampleUsage();
        anaylyzeMemoryFootprint();
    }

    private static void anaylyzeMemoryFootprint()
    {
        testMemoryFootprint(10, 1000);
        testMemoryFootprint(100, 100);
        testMemoryFootprint(1000, 10);
    }

    private static void testMemoryFootprint(int rows, int cols)
    {
        System.out.println("For " + rows + " rows and " + cols + " columns:");

        ByteArray2D b0 = new SimpleByteArray2D(rows, cols);
        GraphLayout g0 = GraphLayout.parseInstance(b0);
        System.out.println("Total size for SimpleByteArray2D : " + g0.totalSize());
        //System.out.println(g0.toFootprint());

        ByteArray2D b1 = new CompactByteArray2D(rows, cols);
        GraphLayout g1 = GraphLayout.parseInstance(b1);
        System.out.println("Total size for CompactByteArray2D: " + g1.totalSize());
        //System.out.println(g1.toFootprint());
    }

    // Shows an example of how to use the different implementations
    private static void showExampleUsage()
    {
        System.out.println("Using a SimpleByteArray2D");
        ByteArray2D b0 = new SimpleByteArray2D(10, 10);
        exampleUsage(b0);

        System.out.println("Using a CompactByteArray2D");
        ByteArray2D b1 = new CompactByteArray2D(10, 10);
        exampleUsage(b1);
    }

    private static void exampleUsage(ByteArray2D byteArray2D)
    {
        // Reading elements of the array
        System.out.println(byteArray2D.get(2, 4));

        // Writing elements of the array
        byteArray2D.set(2, 4, (byte)123);
        System.out.println(byteArray2D.get(2, 4));

        // Bulk access to rows
        ByteBuffer row = byteArray2D.getRow(2);
        for (int c = 0; c < row.capacity(); c++)
        {
            System.out.println(row.get(c));
        }

        // (Commented out for this MCVE: Writing one row to a file)
        /*/
        try (FileChannel fileChannel = 
            new FileOutputStream(new File("example.dat")).getChannel())
        {
            fileChannel.write(byteArray2D.getRow(2));
        }
        catch (IOException e)
        {
            e.printStackTrace();
        }
        //*/
    }

}


interface ByteArray2D 
{
    int getNumRows();
    int getNumColumns();
    byte get(int r, int c);
    void set(int r, int c, byte b);

    // Bulk access to rows, for convenience and efficiency
    ByteBuffer getRow(int row);
}

class SimpleByteArray2D implements ByteArray2D 
{
    private final int rows;
    private final int cols;
    private final byte array[][];

    public SimpleByteArray2D(int rows, int cols)
    {
        this.rows = rows;
        this.cols = cols;
        this.array = new byte[rows][cols];
    }

    @Override
    public int getNumRows()
    {
        return rows;
    }

    @Override
    public int getNumColumns()
    {
        return cols;
    }

    @Override
    public byte get(int r, int c)
    {
        return array[r][c];
    }

    @Override
    public void set(int r, int c, byte b)
    {
        array[r][c] = b;
    }

    @Override
    public ByteBuffer getRow(int row)
    {
        return ByteBuffer.wrap(array[row]);
    }
}

class CompactByteArray2D implements ByteArray2D
{
    private final int rows;
    private final int cols;
    private final ByteBuffer buffer;

    public CompactByteArray2D(int rows, int cols)
    {
        this.rows = rows;
        this.cols = cols;
        this.buffer = ByteBuffer.allocate(rows * cols);
    }

    @Override
    public int getNumRows()
    {
        return rows;
    }

    @Override
    public int getNumColumns()
    {
        return cols;
    }

    @Override
    public byte get(int r, int c)
    {
        return buffer.get(r * cols + c);
    }

    @Override
    public void set(int r, int c, byte b)
    {
        buffer.put(r * cols + c, b);
    }

    @Override
    public ByteBuffer getRow(int row)
    {
        ByteBuffer r = buffer.slice();
        r.position(row * cols);
        r.limit(row * cols + cols);
        return r.slice();
    }
}

再次强调，这主要是一个草图，展示一种可能的方法。界面的细节将取决于预期的应用程序模式。

---

¹ 一个附注：

内存开销的问题在其他语言中也很相似。例如，在C/C++中，最接近“2D Java数组”的结构将是手动分配指针的数组：

char** array;
array = new (char*)[numRows];
array[0] = new char[numCols];
...

在这种情况下，您还有一个与行数成比例的开销——通常为每行一个（通常为4个字节）指针。

- Marco13