位运算性能，如何提高

Question

我有一个简单的任务：确定将一些数字（字节数组长度）编码为字节数组所需的字节数，并编码最终值（实现本文：编码长度和值字节）。

最初，我编写了一个快速完成任务的方法：

public static Byte[] Encode(Byte[] rawData, Byte enclosingtag) {
    if (rawData == null) {
        return new Byte[] { enclosingtag, 0 };
    }
    List<Byte> computedRawData = new List<Byte> { enclosingtag };
    // if array size is less than 128, encode length directly. No questions here
    if (rawData.Length < 128) {
        computedRawData.Add((Byte)rawData.Length);
    } else {
        // convert array size to a hex string
        String hexLength = rawData.Length.ToString("x2");
        // if hex string has odd length, align it to even by prepending hex string
        // with '0' character
        if (hexLength.Length % 2 == 1) { hexLength = "0" + hexLength; }
        // take a pair of hex characters and convert each octet to a byte
        Byte[] lengthBytes = Enumerable.Range(0, hexLength.Length)
                .Where(x => x % 2 == 0)
                .Select(x => Convert.ToByte(hexLength.Substring(x, 2), 16))
                .ToArray();
        // insert padding byte, set bit 7 to 1 and add byte count required
        // to encode length bytes
        Byte paddingByte = (Byte)(128 + lengthBytes.Length);
        computedRawData.Add(paddingByte);
        computedRawData.AddRange(lengthBytes);
    }
    computedRawData.AddRange(rawData);
    return computedRawData.ToArray();
}

这是一段旧的代码，写得非常糟糕。

现在我正试图通过使用位运算符或者BitConverter类来优化代码。以下是一个按位运算的例子：

public static Byte[] Encode2(Byte[] rawData, Byte enclosingtag) {
    if (rawData == null) {
        return new Byte[] { enclosingtag, 0 };
    }
    List<Byte> computedRawData = new List<Byte>(rawData);
    if (rawData.Length < 128) {
        computedRawData.Insert(0, (Byte)rawData.Length);
    } else {
        // temp number
        Int32 num = rawData.Length;
        // track byte count, this will be necessary further
        Int32 counter = 1;
        // simply make bitwise AND to extract byte value
        // and shift right while remaining value is still more than 255
        // (there are more than 8 bits)
        while (num >= 256) {
            counter++;
            computedRawData.Insert(0, (Byte)(num & 255));
            num = num >> 8;
        }
        // compose final array
        computedRawData.InsertRange(0, new[] { (Byte)(128 + counter), (Byte)num });
    }
    computedRawData.Insert(0, enclosingtag);
    return computedRawData.ToArray();
}

使用BitConverter类进行最终实现：

public static Byte[] Encode3(Byte[] rawData, Byte enclosingtag) {
    if (rawData == null) {
        return new Byte[] { enclosingtag, 0 };
    }
    List<Byte> computedRawData = new List<Byte>(rawData);
    if (rawData.Length < 128) {
        computedRawData.Insert(0, (Byte)rawData.Length);
    } else {
        // convert integer to a byte array
        Byte[] bytes = BitConverter.GetBytes(rawData.Length);
        // start from the end of a byte array to skip unnecessary zero bytes
        for (int i = bytes.Length - 1; i >= 0; i--) {
            // once the byte value is non-zero, take everything starting
            // from the current position up to array start.
            if (bytes[i] > 0) {
                // we need to reverse the array to get the proper byte order
                computedRawData.InsertRange(0, bytes.Take(i + 1).Reverse());
                // compose final array
                computedRawData.Insert(0, (Byte)(128 + i + 1));
                computedRawData.Insert(0, enclosingtag);
                return computedRawData.ToArray();
            }
        }
    }
    return null;
}

所有的方法都按预期工作。我使用了来自Stopwatch类页面的示例来测量性能。性能测试让我感到惊讶。我的测试方法对一个具有100,000个元素的字节数组（实际上只有数组大小）进行了1,000次运行，并且平均时间如下：

• Encode -- 约为200毫秒
• Encode2 -- 约为270毫秒
• Encode3 -- 约为320毫秒

我个人喜欢Encode2方法，因为代码看起来更易读，但它的性能并不那么好。

问题是：你会建议如何改进Encode2方法的性能或者改进Encode的可读性？

非常感谢您的帮助。

更新：感谢所有参与本主题讨论的人。我考虑了所有的建议，最终得出了这个解决方案：

public static Byte[] Encode6(Byte[] rawData, Byte enclosingtag) {
    if (rawData == null) {
        return new Byte[] { enclosingtag, 0 };
    }
    Byte[] retValue;
    if (rawData.Length < 128) {
        retValue = new Byte[rawData.Length + 2];
        retValue[0] = enclosingtag;
        retValue[1] = (Byte)rawData.Length;
    } else {
        Byte[] lenBytes = new Byte[3];
        Int32 num = rawData.Length;
        Int32 counter = 0;
        while (num >= 256) {
            lenBytes[counter] = (Byte)(num & 255);
            num >>= 8;
            counter++;
        }
        // 3 is: len byte and enclosing tag
        retValue = new byte[rawData.Length + 3 + counter];
        rawData.CopyTo(retValue, 3 + counter);
        retValue[0] = enclosingtag;
        retValue[1] = (Byte)(129 + counter);
        retValue[2] = (Byte)num;
        Int32 n = 3;
        for (Int32 i = counter - 1; i >= 0; i--) {
            retValue[n] = lenBytes[i];
            n++;
        }
    }
    return retValue;
}

最终，我从列表转向了固定大小的字节数组。与相同数据集的平均时间现在约为65毫秒。看来，列表（而不是位运算）使我的性能受到了显着的惩罚。

- Crypt32

---

我现在可以确定你没有对这段代码进行分析，因为如果你这样做了，你会看到LINQ查询和列表操作会变成红色。这是一种数量级的潜在浪费。 - usr

这里有一个显而易见的提示，不要在0处插入，而是在末尾添加并反转结果。 - harold

您IP地址为143.198.54.68，由于运营成本限制，当前对于免费用户的使用频率限制为每个IP每72小时10次对话，如需解除限制，请点击左下角设置图标按钮（手机用户先点击左上角菜单按钮）。 - Crypt32

@哈罗德，说得好，但这几乎没有改善任何东西，因为它仍然需要数组调整大小。 - Crypt32

@CryptoGuy 当然可以，但由于摊销成本的原因，总体上是O(n)，而在0处插入n个元素则为O(n^2)，因为每次操作时必须移动已经存在其中的所有项目。 - harold

找出时间消耗最多的地方。如果您没有准备好的分析器，请在负载下暂停调试器10次。它将在占用大部分时间的地方停止最频繁。然后，优化那些热点行。 - usr

Answer 1

主要问题在于List的分配，插入新元素时所需的分配以及最后将列表转换为数组时的分配。这段代码很可能大部分时间都花在垃圾收集器和内存分配器上。与是否使用按位运算符相比，内存分配量的减少可能意义更大。建议先尝试减少分配的内存量。

一种方法是提前分配一个字节数组并发送其引用以及指向数组中位置的索引，而不是分配并返回数据，然后返回一个整数，告诉您已写入了多少字节。在大型数组上工作通常比在许多小对象上工作更有效。正如其他人所提到的，使用分析器（Profiler）查看代码在哪里花费时间。

当然，我提到的优化会使您的代码更加低级，并且更接近于您通常在C中执行的操作，但可读性与性能之间通常存在权衡。

- alephnil

Answer 2

使用“反转、追加、反转”而不是“在前面插入”，并预先分配所有内容，代码可能如下所示：（未经测试）

public static byte[] Encode4(byte[] rawData, byte enclosingtag) {
    if (rawData == null) {
        return new byte[] { enclosingtag, 0 };
    }
    List<byte> computedRawData = new List<byte>(rawData.Length + 6);
    computedRawData.AddRange(rawData);
    if (rawData.Length < 128) {
        computedRawData.InsertRange(0, new byte[] { enclosingtag, (byte)rawData.Length });
    } else {
        computedRawData.Reverse();
        // temp number
        int num = rawData.Length;
        // track byte count, this will be necessary further
        int counter = 1;
        // simply cast to byte to extract byte value
        // and shift right while remaining value is still more than 255
        // (there are more than 8 bits)
        while (num >= 256) {
            counter++;
            computedRawData.Add((byte)num);
            num >>= 8;
        }
        // compose final array
        computedRawData.Add((byte)num);
        computedRawData.Add((byte)(counter + 128));
        computedRawData.Add(enclosingtag);
        computedRawData.Reverse();
    }
    return computedRawData.ToArray();
}

我不确定这样做是否会更快，但这是有意义的——现在昂贵的“在前面插入”操作大多被避免了，除非只有一个这样的操作（可能不足以平衡两个反转）。

另一个想法是通过其他方式仅限制在前面插入一次：收集所有需要在那里插入的内容，然后只执行一次。可能看起来像这样：（未经测试）

public static byte[] Encode5(byte[] rawData, byte enclosingtag) {
    if (rawData == null) {
        return new byte[] { enclosingtag, 0 };
    }
    List<byte> computedRawData = new List<byte>(rawData);
    if (rawData.Length < 128) {
        computedRawData.InsertRange(0, new byte[] { enclosingtag, (byte)rawData.Length });
    } else {
        // list of all things that will be inserted
        List<byte> front = new List<byte>(8);
        // temp number
        int num = rawData.Length;
        // track byte count, this will be necessary further
        int counter = 1;
        // simply cast to byte to extract byte value
        // and shift right while remaining value is still more than 255
        // (there are more than 8 bits)
        while (num >= 256) {
            counter++;
            front.Insert(0, (byte)num);  // inserting in tiny list, not so bad
            num >>= 8;
        }
        // compose final array
        front.InsertRange(0, new[] { (byte)(128 + counter), (byte)num });
        front.Insert(0, enclosingtag);
        computedRawData.InsertRange(0, front);
    }
    return computedRawData.ToArray();
}

如果这不够好或者没有帮助（或者如果这更糟糕-嘿，可能会这样），我会尝试想出更多的想法。

- harold

---

我进行了快速测试。Encode4要慢得多（平均为340毫秒），但Encode5要快一些：平均为240毫秒。我明白你的意思，会尝试按照这种方式工作。 - Crypt32

@CryptoGuy 有趣的结果，它们表明InsertRange是逐个插入的。无论如何，这里有一个完全不同的想法：不要合并原始数据和前面添加的内容。只返回头部信息。但是否是一个好主意取决于你对它的处理方式。如果你要将其写入文件或类似的东西，那应该是相当不错的。 - harold

本意是在运行时构建一个ASN.1树，性能在这种情况下非常重要。我正在尝试在代码可读性和性能之间找到一个合理的折衷方案。感谢您的努力。 - Crypt32

顺便说一下，我之前的评论中读错了时间，所以请忽略那个结论。 - harold

没问题。也许，我需要使用高性能（尽可能）的列表来简化代码。但这是另外一个故事了。 - Crypt32