最快的字节数组连接方法是什么？

Question

我得到了一个包含n个消息部分的字节数组。在最后一部分成功添加到地图之后，消息必须被串联起来。我发现了两种解决方案，可以满足要求。第一种方法是使用System.arraycopy：

public byte[] getMessageBytes() throws IOException {
    byte[] bytes = new byte[0];
    for (final Map.Entry<Short,byte[]> entry : myMap.entrySet()) {
        byte[] entryBytes = entry.getValue();
        byte[] temp = new byte[bytes.length + entryBytes.length];
        System.arraycopy(bytes, 0, temp, 0, bytes.length);
        System.arraycopy(entryBytes, 0, temp, bytes.length, entryBytes.length);
        bytes = temp;
    }
    return bytes;
}

第二种方法是使用ByteArrayOutputStream：

public byte[] getMessageBytes() throws IOException {
    final ByteArrayOutputStream baos = new ByteArrayOutputStream();
    for (final Map.Entry<Short,byte[]> entry : myMap.entrySet()) {
        baos.write(entry.getValue());
    }
    baos.flush();
    return baos.toByteArray();
}

从性能和内存使用的角度来看，哪种方法更好？是否有更好的连接方式可供选择？

- sebastian

---

你是否进行了基准测试，发现它们速度不够快？ - Poindexter

这真的是你的瓶颈吗？ - ControlAltDel

@Poindexter 我发现如果地图中有很多条目，整个过程需要花费一些时间。因此我在寻找改进方法。 - sebastian

你能否从一开始就删除使用map和concatenate的部分？ - Aidos

@PeterLawrey 我已经有了这个解决方案，但从多个线程访问 ByteArrayOutputStream 是同步和缓慢的。 - sebastian

Answer 1

由于您可以通过将片段的长度相加来找出消息的大小，因此我会：

1. 计算片段的长度，并分配输出数组；
2. 使用循环将每个片段arraycopy()到输出数组的正确位置。

这可能是内存高效和快速的。然而，只有分析才能讲述全貌。

- NPE

Answer 2

这个版本的性能应该比你的第一个版本更好（未经测试）。

public byte[] getMessageBytes() throws IOException {
    long amount = 0L;
    long offset = 0L;
    // no reason to use entrySet() if you just use the values
    for (byte[] arr : myMap.values()) {
        amount += arr.length;
    }
    byte[] dest = new byte[amount];
    for (byte[] arr : myMap.values()) {
        System.arraycopy(arr, 0, dest, offset, arr.length);
        offset += arr.length;
    }
    return dest;
}

(这个答案与aix的差不多)

- Sean Patrick Floyd

---

这是否意味着您希望连接数组的顺序是值集的顺序？我已经很久没有写Java了，但我不认为values() Set有值的顺序保证，对吧？ - Aidos

@Aidos 是的，但既然 OP 使用了它，我也使用了它。虽然顺序不能保证（除非是 SortedMap），但我所知道的所有 map 实现在多次调用时都会按相同的顺序迭代，除非 map 已更改。 - Sean Patrick Floyd

Answer 3

先计算大小，然后一次性分配结果应该是返回字节数组最快的解决方案。

如果您将生成的字节数组稍后用作InputStream，并且根据数组的组合大小，最快的方法可能是根本不进行连接。在这种情况下，您可以创建一个包装多个ByteArrayInputStreams的SequenceInputStream。未经测试的示例代码：

Collection<byte[]> values = map.values();
List<ByteArrayInputStream> streams = new ArrayList<ByteArrayInputStream>(values.size());
for (byte[] bytes : values) {
    streams.add(new ByteArrayInputStream(bytes));
}
return new SequenceInputStream(Collections.enumeration(streams));

- Jörn Horstmann

Answer 4

正确的答案是针对您特定情况进行测试和比较。

那是一个SortedMap，像TreeMap，还是您实际上随机合并字节？

- Mattias Isegran Bergander

Answer 5

你的第一个解决方案每次迭代都创建一个新数组，时间复杂度为O(n^2)，如果有很多条目，则会出现问题。此外，它相当复杂。

使用ByteArrayOutputStream有两个好处：它的时间复杂度为O(n)，而且非常简单。

最可能更快的方法是：如果您首先计算总大小，然后使用System.arraycopy。但只有在ByteArrayOutputStream真的太慢时才这样做。

- Thomas Mueller

Answer 6

这里是本地代码。

    /*
     * public static void arraycopy(Object src, int srcPos, Object dest,
     *      int destPos, int length)
     *
     * The description of this function is long, and describes a multitude
     * of checks and exceptions.
     */
    static void Dalvik_java_lang_System_arraycopy(const u4* args, JValue* pResult)
    {
        ArrayObject* srcArray = (ArrayObject*) args[0];
        int srcPos = args[1];
        ArrayObject* dstArray = (ArrayObject*) args[2];
        int dstPos = args[3];
        int length = args[4];
        /* Check for null pointers. */
        if (srcArray == NULL) {
            dvmThrowNullPointerException("src == null");
            RETURN_VOID();
        }
        if (dstArray == NULL) {
            dvmThrowNullPointerException("dst == null");
            RETURN_VOID();
        }
        /* Make sure source and destination are arrays. */
        if (!dvmIsArray(srcArray)) {
            dvmThrowArrayStoreExceptionNotArray(((Object*)srcArray)->clazz, "source");
            RETURN_VOID();
        }
        if (!dvmIsArray(dstArray)) {
            dvmThrowArrayStoreExceptionNotArray(((Object*)dstArray)->clazz, "destination");
            RETURN_VOID();
        }
        /* avoid int overflow */
        if (srcPos < 0 || dstPos < 0 || length < 0 ||
            srcPos > (int) srcArray->length - length ||
            dstPos > (int) dstArray->length - length)
        {
            dvmThrowExceptionFmt(gDvm.exArrayIndexOutOfBoundsException,
                "src.length=%d srcPos=%d dst.length=%d dstPos=%d length=%d",
                srcArray->length, srcPos, dstArray->length, dstPos, length);
            RETURN_VOID();
        }
        ClassObject* srcClass = srcArray->clazz;
        ClassObject* dstClass = dstArray->clazz;
        char srcType = srcClass->descriptor[1];
        char dstType = dstClass->descriptor[1];
        /*
         * If one of the arrays holds a primitive type, the other array must
         * hold the same type.
         */
        bool srcPrim = (srcType != '[' && srcType != 'L');
        bool dstPrim = (dstType != '[' && dstType != 'L');
        if (srcPrim || dstPrim) {
            if (srcPrim != dstPrim || srcType != dstType) {
                dvmThrowArrayStoreExceptionIncompatibleArrays(srcClass, dstClass);
                RETURN_VOID();
            }
            if (false) ALOGD("arraycopy prim[%c] dst=%p %d src=%p %d len=%d",
                srcType, dstArray->contents, dstPos,
                srcArray->contents, srcPos, length);
            switch (srcType) {
            case 'B':
            case 'Z':
                /* 1 byte per element */
                memmove((u1*) dstArray->contents + dstPos,
                    (const u1*) srcArray->contents + srcPos,
                    length);
                break;
            case 'C':
            case 'S':
                /* 2 bytes per element */
                move16((u1*) dstArray->contents + dstPos * 2,
                    (const u1*) srcArray->contents + srcPos * 2,
                    length * 2);
                break;
            case 'F':
            case 'I':
                /* 4 bytes per element */
                move32((u1*) dstArray->contents + dstPos * 4,
                    (const u1*) srcArray->contents + srcPos * 4,
                    length * 4);
                break;
            case 'D':
            case 'J':
                /*
                 * 8 bytes per element.  We don't need to guarantee atomicity
                 * of the entire 64-bit word, so we can use the 32-bit copier.
                 */
                move32((u1*) dstArray->contents + dstPos * 8,
                    (const u1*) srcArray->contents + srcPos * 8,
                    length * 8);
                break;
            default:        /* illegal array type */
                ALOGE("Weird array type '%s'", srcClass->descriptor);
                dvmAbort();
            }
        } else {
            /*
             * Neither class is primitive.  See if elements in "src" are instances
             * of elements in "dst" (e.g. copy String to String or String to
             * Object).
             */
            const int width = sizeof(Object*);
            if (srcClass->arrayDim == dstClass->arrayDim &&
                dvmInstanceof(srcClass, dstClass))
            {
                /*
                 * "dst" can hold "src"; copy the whole thing.
                 */
                if (false) ALOGD("arraycopy ref dst=%p %d src=%p %d len=%d",
                    dstArray->contents, dstPos * width,
                    srcArray->contents, srcPos * width,
                    length * width);
                move32((u1*)dstArray->contents + dstPos * width,
                    (const u1*)srcArray->contents + srcPos * width,
                    length * width);
                dvmWriteBarrierArray(dstArray, dstPos, dstPos+length);
            } else {
                /*
                 * The arrays are not fundamentally compatible.  However, we
                 * may still be able to do this if the destination object is
                 * compatible (e.g. copy Object[] to String[], but the Object
                 * being copied is actually a String).  We need to copy elements
                 * one by one until something goes wrong.
                 *
                 * Because of overlapping moves, what we really want to do
                 * is compare the types and count up how many we can move,
                 * then call move32() to shift the actual data.  If we just
                 * start from the front we could do a smear rather than a move.
                 */
                Object** srcObj;
                int copyCount;
                ClassObject*   clazz = NULL;
                srcObj = ((Object**)(void*)srcArray->contents) + srcPos;
                if (length > 0 && srcObj[0] != NULL)
                {
                    clazz = srcObj[0]->clazz;
                    if (!dvmCanPutArrayElement(clazz, dstClass))
                        clazz = NULL;
                }
                for (copyCount = 0; copyCount < length; copyCount++)
                {
                    if (srcObj[copyCount] != NULL &&
                        srcObj[copyCount]->clazz != clazz &&
                        !dvmCanPutArrayElement(srcObj[copyCount]->clazz, dstClass))
                    {
                        /* can't put this element into the array */
                        break;
                    }
                }
                if (false) ALOGD("arraycopy iref dst=%p %d src=%p %d count=%d of %d",
                    dstArray->contents, dstPos * width,
                    srcArray->contents, srcPos * width,
                    copyCount, length);
                move32((u1*)dstArray->contents + dstPos * width,
                    (const u1*)srcArray->contents + srcPos * width,
                    copyCount * width);
                dvmWriteBarrierArray(dstArray, 0, copyCount);
                if (copyCount != length) {
                    dvmThrowArrayStoreExceptionIncompatibleArrayElement(srcPos + copyCount,
                            srcObj[copyCount]->clazz, dstClass);
                    RETURN_VOID();
                }
            }
        }
        RETURN_VOID();
    }

- KUTAY ZORLU