快速实现大整数计数器（在C / C ++中）
我的目标如下，
生成连续值，以便之前从未生成每个新值，直到生成所有可能的值。 此时，计数器再次启动相同的序列。 这里的要点是， 所有可能的值都是在不重复的情况下生成的（直到周期耗尽）。 如果序列是简单的0,1,2,3 ……，或者以其他顺序，则无关紧要。
例如，如果范围可以简单地用unsigned表示，那么
void increment (unsigned &n) {++n;}
足够。 但是，整数范围大于64位。 例如，在一个地方，我需要生成256位序列。 一个简单的实现如下，只是为了说明我想要做的事情，
typedef std::array ctr_type; static constexpr uint64_t max = ~((uint64_t) 0); void increment (ctr_type &ctr) { if (ctr[0] < max) {++ctr[0]; return;} if (ctr[1] < max) {++ctr[1]; return;} if (ctr[2] < max) {++ctr[2]; return;} if (ctr[3] < max) {++ctr[3]; return;} ctr[0] = ctr[1] = ctr[2] = ctr[3] = 0; }
因此，如果ctr以全零开始，则第一个ctr[0]逐个增加，直到达到max ，然后是ctr[1] ，依此类推。 如果设置了所有256位，则我们将其重置为全零，然后重新开始。
问题在于，这种实施方式非常缓慢。 我目前的改进版本等同于以下内容，
void increment (ctr_type &ctr) { std::size_t k = (!(~ctr[0])) + (!(~ctr[1])) + (!(~ctr[2])) + (!(~ctr[3])) if (k < 4) ++ctr[k]; else memset(ctr.data(), 0, 32); }
如果计数器仅使用上述increment函数进行操作，并始终以零开始，则ctr[k] == 0如果ctr[k - 1] == 0 。 因此，值k将是小于最大值的第一个元素的索引。
我预计第一个更快，因为分支误预测每2 ^ 64次迭代只发生一次。 第二种，虽然误预测只发生在每2 ^ 256次迭代中，但它不会有所作为。 除了分支之外，它还需要四个按位否定，四个布尔否定和三个加法。 哪个可能比第一个花费更多。
但是， clang ， gcc或intel icpc生成二进制文件，第二个更快。
我的主要问题是，是否有人知道是否有更快的方法来实施这样的计数器？ 如果计数器通过增加第一个整数开始，或者它是否实现为整数数组，则无关紧要，只要该算法生成所有2 ^ 256个256位组合。
是什么让事情变得更复杂，我还需要非均匀增量。 例如，每次计数器增加K ，其中K > 1 ，但几乎总是保持不变。 我目前的实现类似于上面的实现。
为了提供更多的上下文，我使用计数器的一个地方是使用它们作为AES-NI aesenc指令的输入。 如此不同的128位整数（加载到__m128i ），在经过10（或12或14，取决于密钥大小）轮数的指令后，生成一个不同的128-bits整数。 如果我一次生成一个__m128i整数，则increment成本很小。 但是，由于aesenc有相当长的延迟，我按块生成整数。 例如，我可能有4个块， ctr_type block[4] ，初始化等效于以下，
block[0]; // initialized to zero block[1] = block[0]; increment(block[1]); block[2] = block[1]; increment(block[2]); block[3] = block[2]; increment(block[3]);
每次我需要新输出时，我将每个block[i] increment 4，并立即生成4 __m128i输出。 通过交错指令，总体而言我能够增加吞吐量，并且当使用2个64位整数作为计数器和8个块时，将每字节输出（cpB）的周期从6减少到0.9。 但是，如果使用4个32位整数作为计数器，则以每秒字节数测量的吞吐量减少到一半。 我知道在x86-64上，在某些情况下，64位整数可能比32位快。 但我没想到这种简单的增量操作会产生如此大的差异。 我已经仔细地对应用程序进行了基准测试，并且increment确实是减慢程序的速度。 由于加载到__m128i并将__m128i输出存储为可用的32位或64位整数是通过对齐指针完成的，因此32位和64位版本之间的唯一区别是计数器的递增方式。 我希望AES-NI在将整数加载到__m128i后预期会占据主导地位。 但是当使用4或8个区块时，情况显然不是这样。
总而言之，我的主要问题是，如果有人知道改进上述计数器实现的方法。
它不仅缓慢，而且不可能。 宇宙的总能量不足以进行2 ^ 256位的变化。 这需要灰色计数器。
优化之前的下一件事是修复原始实现
void increment (ctr_type &ctr) { if (++ctr[0] != 0) return; if (++ctr[1] != 0) return; if (++ctr[2] != 0) return; ++ctr[3]; }
如果不允许每个ctr[i]溢出到零，则周期将仅为4 *（2 ^ 32），如19,29,39,49,...99 199,299,...和1999,2999,3999,..., 9999 。
作为对评论的回复 – 第一次溢出需要2 ^ 64次迭代。 慷慨，最多可以在一秒内完成2 ^ 32次迭代，这意味着程序应该运行2 ^ 32秒才能完成第一次执行。 这大约是136年。
编辑
如果具有2 ^ 66个状态的原始实现真的是想要的，那么我建议将接口和function更改为：
(*counter) += 1; while (*counter == 0) { counter++; // Move to next word if (counter > tail_of_array) { counter = head_of_array; memset(counter,0, 16); break; } }
关键是，溢出仍然非常罕见。 几乎总是只有一个词要增加。
如果您正在使用GCC
unsigned __int128 H = 0, L = 0; L++; if (L == 0) H++;
在__int128不可用的系统上
unsigned long long c[4] = { 0 }; c[0]++; if (c[0] == 0) { c[1]++; if (c[1] == 0) { c[2]++; if (c[2] == 0) { c[3]++; } } }
使用内联汇编，使用进位标志更容易实现。 不幸的是，大多数高级语言都没有办法访问它。
无论如何，这是浪费时间，因为宇宙中的粒子总数只有大约10 80 ，你甚至无法计算你生活中的64位计数器
您的计数器版本都没有正确递增。 你实际上只计算UINT64_MAX 4次，然后再次从0开始计数，而不是计算到UINT256_MAX 。 这很明显，因为您不必清除任何已达到最大值的索引，直到所有索引都达到最大值。 如果您根据计数器达到所有位0的频率来测量性能，那么这就是原因。 因此，您的算法不会生成256位的所有组合，这是一个明确的要求。
你提到“生成连续的值，这样每个新的值都不会在之前生成”
要生成一组这样的值，请查看线性同余生成器https://en.wikipedia.org/wiki/Linear_congruential_generator
-
序列x =（x * 1 + 1）％（power_of_2），你想到了，这只是序号。
-
序列x =（x * 13 + 137）％（2的幂），这产生具有可预测周期（power_of_2-1）的唯一数字，并且唯一数字看起来更“随机”，类型为伪随机。 您需要求助于任意精度算术才能使其工作，并且还需要使用常量乘法的所有技巧。 这将为您提供一个很好的开始方式。
您还抱怨您的简单代码“慢”
在4.2 Ghz频率下，每个周期运行4个指令并使用AVX512矢量化，在64位计算机上，你的程序的multithreading版本除了增量之外什么都不做，你每秒只能获得64x8x4 * 2 ^ 32 = 8796093022208的增量，在25天内达到2 ^ 64增量。 这篇文章很老了，你可能已经到了841632698362998292480，在这样的机器上运行这样的程序，你将在2年内光荣地达到1683265396725996584960。
您还需要“直到生成所有可能的值” 。
您只能生成有限数量的值，具体取决于您愿意为计算机供电所需的费用。 正如其他回复中所提到的，即使是世界上最富有的人，即使是128位或256位数字，在第一个条件出现之前，你永远不会回头：
- 没钱了
- 人类的终结（没有人会得到你的软件的结果）
- 从宇宙的最后一个粒子燃烧能量