将两个半字节打包成一个字节的最快方法

Question

将两个字节打包成一个的最快方法是什么？我有一个很大的字节数组。每个字节代表一个不大于 15 的数字（4 位数字）。因此，我可以将两个字节合并为一个，将第一个字节放入高半字节，将后面的字节放入低半字节。

我目前的方法是创建一个原始数组一半大小的第二个数组，然后迭代原始数组移动它和 | 得到小点心。这有效，但是根据数组的大小需要一段时间。数组从几千个条目到几百万个条目不等。这不是灾难性的，但任何优化都会有所帮助

Answer 1

如果您的数组很大，这显然需要一段时间 - 您需要遍历所有数组。

我要做的第一件事是创建一个从两个字节到一个字节的查找表，这样您就不需要移位和或 - 获取接下来的两个字节，查找它们的偏移量并获取结果字节。

该查找表应该有 2^12 个条目（从最高有效字节开始只需要 4 个字节），并且非常适合 CPU 的 L1 缓存。它可能比移位和或更快。

另一方面，如果您一次加载 8 个字节（在 64 位 CPU 上，就像现在一样），您可以将其转换为 4 个字节并存储它们。您将能够并行化它（将阵列分为 4 个部分，并让每个核心处理一个部分）。

如果有一条指令从 64 位寄存器中获取字节 0、2、4 和 6，并将它们放入 32 位寄存器中，那么您就完成了。

更新：您在问题中提到您有几百万字节。在这种情况下，请不要打扰。高度优化的汇编和 C 中的简单实现之间的区别不值得这么麻烦。只需一次加载两个字节的数据，将和/或两个半字节转换为一个字节并存储在目标数组中。处理 1MB 的数据应该是即时的。