在执行某些任务之后,我有一段代码以每秒约120万次的速度运行,其中最大的代码是设置uint8_t数组,其中包含来自两个uint32_t数据段的移位数据。摘录代码如下:
static inline uint32_t RotateRight(uint32_t val, int n)
{
return (val >> n) + (val << (32 - n));
}
static inline uint32_t CSUInt32BE(const uint8_t *b)
{
return ((uint32_t)b[0] << 24) | ((uint32_t)b[1] << 16) | ((uint32_t)b[2] << 8) | (uint32_t)b[3];
}
static uint32_t ReverseBits(uint32_t val) // Usually just static, tried inline/static inline
{
// uint32_t res = 0;
// for (int i = 0; i<32; i++)
// {
// res <<= 1;
// res |= val & 1;
// val >>= 1;
// }
// Original code above, benched ~220k l/s
//val = ((val & 0x55555555) << 1) | ((val >> 1) & 0x55555555);
//val = ((val & 0x33333333) << 2) | ((val >> 2) & 0x33333333);
//val = ((val & 0x0F0F0F0F) << 4) | ((val >> 4) & 0x0F0F0F0F);
//val = ((val & 0x00FF00FF) << 8) | ((val >> 8) & 0x00FF00FF);
//val = (val << 16) | (val >> 16);
// Option 0, benched ~770k on MBP
uint32_t c = 0;
c = (BitReverseTable256[val & 0xff] << 24) |
(BitReverseTable256[(val >> 8) & 0xff] << 16) |
(BitReverseTable256[(val >> 16) & 0xff] << 8) |
(BitReverseTable256[val >> 24]); // was (val >> 24) & 0xff
// Option 1, benched ~970k l/s on MBP, Current, minor tweak to 24
//unsigned char * p = (unsigned char *)&val;
//unsigned char * q = (unsigned char *)&c;
//q[3] = BitReverseTable256[p[0]];
//q[2] = BitReverseTable256[p[1]];
//q[1] = BitReverseTable256[p[2]];
//q[0] = BitReverseTable256[p[3]];
// Option 2 at ~970k l/s on MBP from http://stackoverflow.com/questions/746171/best-algorithm-for-bit-reversal-from-msb-lsb-to-lsb-msb-in-c
return c; // Current
// return val; // option 0
// return res; // original
//uint32_t m;
//val = (val >> 16) | (val << 16); // swap halfwords
//m = 0x00ff00ff; val = ((val >> 8) & m) | ((val << 8) & ~m); // swap bytes
//m = m^(m << 4); val = ((val >> 4) & m) | ((val << 4) & ~m); // swap nibbles
//m = m^(m << 2); val = ((val >> 2) & m) | ((val << 2) & ~m);
//m = m^(m << 1); val = ((val >> 1) & m) | ((val << 1) & ~m);
//return val;
// Benches at 850k l/s on MBP
//uint32_t t;
//val = (val << 15) | (val >> 17);
//t = (val ^ (val >> 10)) & 0x003f801f;
//val = (t + (t << 10)) ^ val;
//t = (val ^ (val >> 4)) & 0x0e038421;
//val = (t + (t << 4)) ^ val;
//t = (val ^ (val >> 2)) & 0x22488842;
//val = (t + (t << 2)) ^ val;
//return val;
// Benches at 820k l/s on MBP
}
static void StuffItDESCrypt(uint8_t data[8], StuffItDESKeySchedule *ks, BOOL enc)
{
uint32_t left = ReverseBits(CSUInt32BE(&data[0]));
uint32_t right = ReverseBits(CSUInt32BE(&data[4]));
right = RotateRight(right, 29);
left = RotateRight(left, 29);
//Encryption function runs here
left = RotateRight(left, 3);
right = RotateRight(right, 3);
uint32_t left1 = ReverseBits(left);
uint32_t right1 = ReverseBits(right);
data[0] = right1 >> 24;
data[1] = (right1 >> 16) & 0xff;
data[2] = (right1 >> 8) & 0xff;
data[3] = right1 & 0xff;
data[4] = left1 >> 24;
data[5] = (left1 >> 16) & 0xff;
data[6] = (left1 >> 8) & 0xff;
data[7] = left1 & 0xff;
这是实现此目标的最佳方法吗?我也有一个uint64_t版本:
uint64_t both = ((uint64_t)ReverseBits(left) << 32) | (uint64_t)ReverseBits(right);
data[0] = (both >> 24 & 0xff);
data[1] = (both >> 16) & 0xff;
data[2] = (both >> 8) & 0xff;
data[3] = both & 0xff;
data[4] = (both >> 56);
data[5] = (both >> 48) & 0xff;
data[6] = (both >> 40) & 0xff;
data[7] = (both >> 32) & 0xff;
我测试了如果我完全跳过此分配(ReverseBits函数仍然完成)会发生什么,并且代码以每秒约650万次运行的速度运行。此外,如果我也只做一个,那么即使在不涉及其他7个任务的情况下也达到120万,这种速度的打击就会发生。
我不愿意因为这项工作而使此操作的速度大幅度降低了80%,并且无法提高速度。
这是在Windows Visual Studio 2015上进行的(尽管我尝试将源尽可能保持对macOS和Linux的可移植性)。
编辑:完整的基本代码位于Github。我不是该代码的原始作者,但是我将其 fork 并使用经过修改的Speed版本维护密码恢复解决方案。您可以看到我在ReverseBits中以各种解决方案和基准速度提高了速度。
这些文件已有20多年的历史,并且已经成功恢复了文件,尽管这些年来速度很慢。参见blog post。
最佳答案
当然,您要做的工作比需要做的还要多。请注意ReverseBits()
函数如何努力以正确的顺序放置反转单词的字节,以及接下来发生的事情(归因于减速的部分)是如何对这些相同的字节重新排序。
您可以编写和使用ReverseBits()
的修改版本,该版本将反向表示的字节直接放入数组的正确位置,而不是将它们打包为整数只是为了再次对其进行打包。这应该至少要快一点,因为您将严格删除操作。
关于c++ - 优化位移入阵列,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/41797566/