碎片化数组在动态字节存储中的缺点

Question

默认的ByteArrayOutputStream实现似乎是一种浪费资源的做法，我想知道是否有特定的原因。首先，它在后端保留了1个固定数组。如果该数组已满，则创建一个新数组并将旧数组复制到其中（更多内存 + 更多开销）。然后，如果您运行toByteArray()，它实际上再次复制数组。

字节缓冲区很好，但大小也是固定的，它们仅在单个数组上提供一些缓冲功能，除此之外没有其他作用。

我在思考是否可以创建一个类（或者如果它已经存在，请指向它），使用一个或多个后备数组。而不是每次都复制数组来扩展它，只需添加一个新的后备数组即可。要读取，可以轻松创建像输入流一样的接口，而要写入，则可以公开像输出流一样的接口。

请问是否已经存在这样的东西，如果不存在：为什么？它有一些我没看到的缺点吗？

- nablex

---

“我在想创建一个课程是否有意思…” - “是的，创建这样的课程会很有趣。加油！” - Stephen C

Answer 1

这实际上是一个很好的想法，特别是对于大数据。

在堆上分配巨大的数组时，您可能会快速遇到内存问题，因为它们需要连续的空闲内存来分配。我们曾经遇到过这样的情况，经常分配大小为10-50MB的字节数组，并遇到OutOfMemoryException，不是因为可用内存太少（通常有90％或900MB空闲），而是由于堆碎片化，没有单个连续的内存块可以用于此数组。

我们最终创建了一个Blob类，它将数据作为链式（List）较小的数组块存储在内部。数组具有固定大小（对于快速查找至关重要，因此您可以快速计算给定索引的涉及数组和偏移量），并且我们为此Blob创建了InputStream和OutputStream类。后来，我们将其扩展为可与磁盘交换。

• 缺点？除了一点简单的编程工作外，没有其他问题。
• 好处？高效地存储大型数据，不再出现堆碎片化问题。

我只能鼓励您尝试一下！

- Peter Walser

---

听起来你的应用程序也可能受益于内存映射文件。从FileOutputStream.getChannel()和FileChannel.read(ByteBuffer)开始。文件的映射部分可以几乎像直接数组一样快速访问，而不消耗任何Java堆空间。这种方法具有良好的可扩展性，Java GC不会负担过重，你的应用程序可能会更好地与系统上的其他软件“协作”。 - Luke Usherwood

Answer 2

C++标准库有向量类（类似于Java的ArrayList）和双端队列类（另一种类似类）。后者提供了高效的前置和后置操作。我看到的实现保持了固定长度数组块的列表。所以，有点像你感兴趣的情况。因此，这是可行的。

缺点是代码的复杂性大大增加。我猜JRE中的实现可以改为执行您建议的操作，使用toByteArray方法从片段收集数据。但是，进行此操作的优先级非常低，因为简单的实现非常快。任何进行IO操作的代码都应该假设读取和写入是慢速操作，可能会阻塞。ByteArrayOutputStream则非常快，因为它执行内存操作而不是真正的外部IO。将这些字节数组复制到周围可能比外部IO快得多。当前实现的缺点是在用于大输出流时创建大型垃圾数组。但是该类的用例是小流；如果您想暂时存储大输出流的字节，则应使用临时文件。因此，您的建议的复杂性在实践中可能没有太大帮助。

- Raedwald

Answer 3

看起来你已经知道了它的好处。相比于单个缓冲区，缓冲区列表的缺点包括：

• 如果缓冲区是固定大小的，则需要 O(n) 的内存分配来写入 n 个字节，而 ByteArrayOutputStream 则是 O(log n)，因为缓冲区呈指数增长
• 实现更加复杂：您必须跟踪活动缓冲区，可能需要在写入过程中切换缓冲区（取决于设计）
• 切换缓冲区时会导致缓存未命中

如果这对你的应用程序有意义，你可以自由地编写这样的数据结构。

- Joni

Answer 4

由于似乎没有真正的实现，我已经快速编写了一个初始实现来测试速度：

public class Buffer {

    private int size;

    private int writeIndex, writeOffset,
        readIndex, readOffset;

    private List<byte[]> backingArrays = new ArrayList<byte[]>();

    public Buffer() {
        this(10240);
    }

    public Buffer(int size) {
        this.size = size;
    }

    public int read(byte [] bytes) {
        return read(bytes, 0, bytes.length);
    }

    public int read(byte [] bytes, int offset, int length) {
        int read = 0;
        while(length > 0) {
            byte [] input = getInput();
            // no more data
            if (input == null) {
                if (read == 0)
                    return -1;
                else
                    return read;
            }
            int readLength = Math.min(length, (readIndex == writeIndex ? writeOffset : size) - readOffset);
            System.arraycopy(input, readOffset, bytes, offset, readLength);
            length -= readLength;
            offset += readLength;
            readOffset += readLength;
            read += readLength;
        }
        return read;
    }

    public void write(byte [] bytes) {
        write(bytes, 0, bytes.length);
    }

    public void write(byte [] bytes, int offset, int length) {
        while (length > 0) {
            byte [] output = getOutput();
            int writeLength = Math.min(length, output.length - writeOffset);
            System.arraycopy(bytes, offset, output, writeOffset, writeLength); 
            length -= writeLength;
            offset += writeLength;
            writeOffset += writeLength;
        }
    }

    private byte[] getOutput() {
        // if we have filled an array, move to the next one
        if (writeOffset >= size) {
            writeIndex++;
            writeOffset = 0;
        }
        // create it if it doesn't exist yet
        if (backingArrays.size() <= writeIndex)
            backingArrays.add(new byte[size]);

        return backingArrays.get(writeIndex);
    }

    private byte [] getInput() {
        // nothing written yet
        if (backingArrays.size() == 0)
            return null;

        if (readOffset >= size) {
            readIndex++;
            readOffset = 0;
        }
        // can not read past where it is written
        if (readIndex > writeIndex || (readIndex == writeIndex && readOffset >= writeOffset))
            return null;
        else
            return backingArrays.get(readIndex);
    }

    public long size() {
        return (long) size * (long) writeIndex + writeOffset;
    }
}

我正在通过复制一个36兆字节的文件进行测试。当然，很多取决于文件交互，但总体而言，它似乎比bytearrayinputstream读取速度快40％，写入速度略快（增加了5-20％）

我很快就把它放在一起了，所以如果你发现任何错误，请告诉我。

编辑：

添加了一个功能，即默认情况下释放已读取的数组以供垃圾回收。

- nablex