快速執行大量的整數計數器（在C/C++）

生成連續值，使得直到產生所有可能的值中的每個新的以前從未產生。此時，計數器再次開始相同的序列。這裏的要點是，全部可能的值生成沒有重複（直到這段時間耗盡）。順序是簡單的0,1,2,3，...還是以其他順序並不重要。

例如，如果該範圍可以通過簡單地unsigned表示，則

void increment (unsigned &n) {++n;}

就足夠了。但是，整數範圍大於64位。例如，在一個地方，我需要生成256位序列。一個簡單的實現是像下面這樣，只是想說明什麼，我試圖做的，

typedef std::array<uint64_t, 4> 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都會生成二進制文件，第二個文件要快得多。

我的主要問題是，有誰知道是否有更快的方式來實現這樣的計數器？只要該算法生成256位的所有2^256組合，計數器是以增加第一個整數開始，還是作爲整數數組來實現並不重要。

什麼讓事情變得更加複雜，我也需要非統一的增量。例如，每次計數器增加K其中K > 1，但幾乎總是保持不變。我目前的實施與上述類似。

爲了提供更多的上下文，我使用計數器的一個地方是將它們用作AES-NI aesenc指令的輸入。因此，在經過10次（或12或14次，取決於密鑰大小）輪次的指令之後，生成不同的128位整數（加載到__m128i），產生不同的整數。如果我一次生成一個__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]);

每次我需要新的輸出時間，我increment每個block[i] 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塊時，情況顯然不是這樣。

所以要總結，我的主要問題是，如果有人知道一種方法來改善上述櫃檯的執行情況。

來源

2014-03-13 Yan Zhou

你預計64位計數器溢出的速度有多快？？以我的數學計算，如果你能在2GHz更新它將需要300年。一個256位的計數器是令人難以置信的巨大的。 – pat

你試圖對AES256進行蠻力攻擊嗎？ – pat

爲什麼有人低估了這個問題。 – arunmoezhi

它不僅緩慢，而且不可能。宇宙的總能量不足以進行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），如0-9，19,29,39,49,...99 ，199,299,...和1999,2999,3999,..., 9999。

作爲對評論的回覆 - 需要2^64次迭代纔有第一次溢出。慷慨，最多可以在一秒鐘內完成2^32次迭代，這意味着程序應該運行2^32秒才能完成第一次。那大約136年。

編輯

如果用2^66個國家原來實行真的什麼都想，那麼我建議界面和功能更改爲類似：

(*counter) += 1; 
    while (*counter == 0) 
    { 
    counter++; // Move to next word 
    if (counter > tail_of_array) { 
     counter = head_of_array; 
     memset(counter,0, 16); 
     break; 
    } 
    }

的指出，溢出仍然非常罕見。幾乎總是隻有一個詞需要增加。

來源

2014-03-13 06:49:45

傳統上，人們使用帶進位指令來有效地實現多精度添加，但在C或C++中，如果沒有內聯asm，這很遺憾不可用。 –

您的計數器版本都沒有正確遞增。而不是計數到UINT256_MAX，您實際上只計算了UINT64_MAX 4次，然後再次從0開始。這是顯而易見的，因爲您不打算清除已經達到最大值的任何指數，直到所有指數達到最大值。如果您根據計數器達到所有位0的頻率來衡量性能，那麼這就是原因。因此，您的算法不會生成256位的所有組合，這是一個明確的要求。

來源

2014-03-13 08:43:15 jxh

不，它不會。第一次執行可能不會發生數百年。 –

如果你使用GCC

unsigned __int128 H, L; 
L++; 
if (L == 0) H++;

在系統中__int128不可

unsigned long long c[4]; 
c[0]++; 
if (c[0] == 0) 
{ 
    c[1]++; 
    if (c[1] == 0) 
    { 
     c[2]++; 
     if (c[2] == 0) 
     { 
      c[3]++; 
     } 
    } 
}

使用內聯彙編，它更容易做到這一點使用進位標誌。不幸的是，大多數高級語言沒有訪問它的意思。無論如何，這是相當浪費時間，因爲宇宙中的粒子總數只有大約10 而且你甚至不能計數你生活中的64位計數器

來源

2014-03-13 09:41:31

@AkiSuihkonen我編輯了代碼 –

快速執行大量的整數計數器（在C/C++）

回答

相關問題