優化C函數刪除比較

我一直在剖析我們的應用程序，並發現了一些明顯的，內存分配器被稱爲了很多，消耗顯著時間（幾個百分點）。去年，我使內存分配器速度提高了許多倍，但我仍然認爲我可以加快速度。因此，作爲優化的一部分，我想加快量化分配大小的代碼部分。優化C函數刪除比較

內存分配器保留空閒的內存塊列表。有832個列表的數組。一個列表，每個分配大小從0..128k。所有來自0..128k的分配請求都被轉換爲832個量子之一（量子是正確的詞？）832是任意的，並導致我在下面提出的方案。我正在平衡一種渴望，不要浪費記憶，希望有大量的重複使用。另外，我想盡可能少地使用比特來存儲分配的大小。在我們的應用中，小尺寸要求大於大尺寸 - 即小尺寸的再利用率更高。一切都對齊到8個字節，所以最小的量子是8.我選擇量化低於256個字節的所有分配到8個字節，以不浪費任何更多的內存比所需的對齊。同樣爲了節省空間，當內存被添加到空閒內存列表時，我使用分配內存的前8個字節作爲下一個指針，所以我也不能低於8個字節。從2..8k請求量子是32個字節。從8..32k是128字節。從32..128k是512字節。隨着請求大小的增加，你可以使用更大的量子，並且仍然保持很低的內存百分比。因爲我只有832個大小，所以重用率很高，即使是大/稀有的分配。

這是量化分配請求的函數。 iRecycle是列表數組的索引。它從0 ... 831

void GetAlignedSize(QWORD cb, QWORD& cbPack8, WORD& iRecycle) { 
    // we assume cb is small, so the first 'if' will be hit the most. 
    if (cb < 0x000800 - 0x0007) {  // 0k..2k = 8 byte chunks 
    cb += 0x0007; cbPack8 = cb & (~0x0007); // pad to 8 
    iRecycle = 000 + WORD(cb >> 3); 
    } else if (cb < 0x002000 - 0x001f) { // 2k..8k = 32 byte chunks 
    cb += 0x001f; cbPack8 = cb & (~0x001f); // pad to 32 
    iRecycle = 192 + WORD(cb >> 5); 
    } else if (cb < 0x008000 - 0x007f) { // 8k..32k = 128 byte chunks 
    cb += 0x007f; cbPack8 = cb & (~0x007f); // pad to 128 
    iRecycle = 384 + WORD(cb >> 7); 
    } else if (cb < 0x020000 - 0x01ff) { // 32k..128k = 512 byte chunks 
    cb += 0x01ff; cbPack8 = cb & (~0x01ff); // pad to 512 
    iRecycle = 576 + WORD(cb >> 9); 
    } else { 
    cbPack8 = Pack8(cb); 
    iRecycle = 0; 
    } 
}

這是問題！我怎麼能做一些類似於的操作，只需要位操作。我想擺脫比較陳述，因爲我認爲它打破了CPU流水線。只要量化隨着尺寸的增加而增加，並且低於128k的尺寸的數量很小，則任何方案都是可行的。我預計這會消除最後一種情況，並且iRecycle會無限制地增加，因此我們可以將iRecycle更改爲不同大小的整數。

感謝您的幫助！

來源

2014-07-16 johnnycrash

多久第一種情況下撞到，如所有電話的百分比？此外，這似乎是C++，而不是C，只是參考參數。 – user2357112

您使用哪種編譯器和優化標誌？您是否嘗試過使用最近的[GCC]（http://gcc.gnu.org/）4.9（使用'gcc-4.9 -mtune = native -flto -O3'編譯和鏈接）？ –

249擊中第一個if。 250-256的cb如果點擊第二個，但仍然量化爲256.如果if（cb <0x800）重寫第一個，並且對於所有其他if也是如此。邊際改進，但更容易閱讀。 –

顯而易見的事情是使用一個表。我很懷疑，這樣的方案會更快，但好奇......

...所以，建立一個基線我調整你的函數（在C渲染它）：

static uint 
GetAlignedSize(size_t size, size_t* rsize) 
{ 
    size_t sx = size - 1 ; 

    if (size <= 0x00800) 
    { 
     *rsize = (sx | 0x007) + 1 ; 
     return (sx >> 3) + ((256 - 64) * 0) ; 
    } ; 

    if (size <= 0x02000) 
    { 
     *rsize = (sx | 0x01F) + 1 ; 
     return (sx >> 5) + ((256 - 64) * 1) ; 
    } ; 

    if (size <= 0x08000) 
    { 
     *rsize = (sx | 0x07F) + 1 ; 
     return (sx >> 7) + ((256 - 64) * 2) ; 
    } ; 

    if (size <= 0x20000) 
    { 
     *rsize = (sx | 0x1FF) + 1 ; 
     return (sx >> 9) + ((256 - 64) * 3) ; 
    } ; 

    *rsize = 0 ; 
    return 64 + ((256 - 64) * 4) ; 
} ;

注意到本確定尺寸高達，包括 0x800與8字節單位等，並返回所有已知尺寸的「索引」0..831，和外部尺寸（不是1..832和0）的832。順帶一提，我想知道是否真的有用知道圓形大小？要解鎖塊，你需要「索引」，如果你需要可以擡頭的圓形尺寸？ [披露：這還假定傳入請求大小不爲零......這使得在時序一個微小的改進！]

無論如何，最普遍的做法是，以錶帶動整個事情：

static uint 
get_aligned_size_1(size_t size, size_t* rsize) 
{ 
    static const uint tb[0x40] = 
    { 
    /* 0x00 */ (0x007 << 16) + ((256 - 64) * 0) + 3, 

    /* 0x01 */ (0x01F << 16) + ((256 - 64) * 1) + 5, 
    /* 0x02 */ (0x01F << 16) + ((256 - 64) * 1) + 5, 
    /* 0x03 */ (0x01F << 16) + ((256 - 64) * 1) + 5, 

    /* 0x04 */ (0x07F << 16) + ((256 - 64) * 2) + 7, 
    /* 0x05 */ (0x07F << 16) + ((256 - 64) * 2) + 7, 
    /* 0x06 */ (0x07F << 16) + ((256 - 64) * 2) + 7, 
    /* 0x07 */ (0x07F << 16) + ((256 - 64) * 2) + 7, 
    /* 0x08 */ (0x07F << 16) + ((256 - 64) * 2) + 7, 
    /* 0x09 */ (0x07F << 16) + ((256 - 64) * 2) + 7, 
    /* 0x0A */ (0x07F << 16) + ((256 - 64) * 2) + 7, 
    /* 0x0B */ (0x07F << 16) + ((256 - 64) * 2) + 7, 
    /* 0x0C */ (0x07F << 16) + ((256 - 64) * 2) + 7, 
    /* 0x0D */ (0x07F << 16) + ((256 - 64) * 2) + 7, 
    /* 0x0E */ (0x07F << 16) + ((256 - 64) * 2) + 7, 
    /* 0x0F */ (0x07F << 16) + ((256 - 64) * 2) + 7, 

    /* 0x10 */ (0x1FF << 16) + ((256 - 64) * 3) + 9, 
    /* 0x11 */ (0x1FF << 16) + ((256 - 64) * 3) + 9, 
    /* 0x12 */ (0x1FF << 16) + ((256 - 64) * 3) + 9, 
    /* 0x13 */ (0x1FF << 16) + ((256 - 64) * 3) + 9, 
    /* 0x14 */ (0x1FF << 16) + ((256 - 64) * 3) + 9, 
    /* 0x15 */ (0x1FF << 16) + ((256 - 64) * 3) + 9, 
    /* 0x16 */ (0x1FF << 16) + ((256 - 64) * 3) + 9, 
    /* 0x17 */ (0x1FF << 16) + ((256 - 64) * 3) + 9, 
    /* 0x18 */ (0x1FF << 16) + ((256 - 64) * 3) + 9, 
    /* 0x19 */ (0x1FF << 16) + ((256 - 64) * 3) + 9, 
    /* 0x1A */ (0x1FF << 16) + ((256 - 64) * 3) + 9, 
    /* 0x1B */ (0x1FF << 16) + ((256 - 64) * 3) + 9, 
    /* 0x1C */ (0x1FF << 16) + ((256 - 64) * 3) + 9, 
    /* 0x1D */ (0x1FF << 16) + ((256 - 64) * 3) + 9, 
    /* 0x1E */ (0x1FF << 16) + ((256 - 64) * 3) + 9, 
    /* 0x1F */ (0x1FF << 16) + ((256 - 64) * 3) + 9, 

    /* 0x20 */ (0x1FF << 16) + ((256 - 64) * 3) + 9, 
    /* 0x21 */ (0x1FF << 16) + ((256 - 64) * 3) + 9, 
    /* 0x22 */ (0x1FF << 16) + ((256 - 64) * 3) + 9, 
    /* 0x23 */ (0x1FF << 16) + ((256 - 64) * 3) + 9, 
    /* 0x24 */ (0x1FF << 16) + ((256 - 64) * 3) + 9, 
    /* 0x25 */ (0x1FF << 16) + ((256 - 64) * 3) + 9, 
    /* 0x26 */ (0x1FF << 16) + ((256 - 64) * 3) + 9, 
    /* 0x27 */ (0x1FF << 16) + ((256 - 64) * 3) + 9, 
    /* 0x28 */ (0x1FF << 16) + ((256 - 64) * 3) + 9, 
    /* 0x29 */ (0x1FF << 16) + ((256 - 64) * 3) + 9, 
    /* 0x2A */ (0x1FF << 16) + ((256 - 64) * 3) + 9, 
    /* 0x2B */ (0x1FF << 16) + ((256 - 64) * 3) + 9, 
    /* 0x2C */ (0x1FF << 16) + ((256 - 64) * 3) + 9, 
    /* 0x2D */ (0x1FF << 16) + ((256 - 64) * 3) + 9, 
    /* 0x2E */ (0x1FF << 16) + ((256 - 64) * 3) + 9, 
    /* 0x2F */ (0x1FF << 16) + ((256 - 64) * 3) + 9, 

    /* 0x30 */ (0x1FF << 16) + ((256 - 64) * 3) + 9, 
    /* 0x31 */ (0x1FF << 16) + ((256 - 64) * 3) + 9, 
    /* 0x32 */ (0x1FF << 16) + ((256 - 64) * 3) + 9, 
    /* 0x33 */ (0x1FF << 16) + ((256 - 64) * 3) + 9, 
    /* 0x34 */ (0x1FF << 16) + ((256 - 64) * 3) + 9, 
    /* 0x35 */ (0x1FF << 16) + ((256 - 64) * 3) + 9, 
    /* 0x36 */ (0x1FF << 16) + ((256 - 64) * 3) + 9, 
    /* 0x37 */ (0x1FF << 16) + ((256 - 64) * 3) + 9, 
    /* 0x38 */ (0x1FF << 16) + ((256 - 64) * 3) + 9, 
    /* 0x39 */ (0x1FF << 16) + ((256 - 64) * 3) + 9, 
    /* 0x3A */ (0x1FF << 16) + ((256 - 64) * 3) + 9, 
    /* 0x3B */ (0x1FF << 16) + ((256 - 64) * 3) + 9, 
    /* 0x3C */ (0x1FF << 16) + ((256 - 64) * 3) + 9, 
    /* 0x3D */ (0x1FF << 16) + ((256 - 64) * 3) + 9, 
    /* 0x3E */ (0x1FF << 16) + ((256 - 64) * 3) + 9, 
    /* 0x3F */ (0x1FF << 16) + ((256 - 64) * 3) + 9, 
    } ; 

    size_t sx = size - 1 ; 

    if (size <= 0x20000) 
    { 
     uint tx ; 

     tx = tb[sx >> 11] ; 

     *rsize = (sx | (tx >> 16)) + 1 ; 
     return (sx >> (tx & 0xF)) + (tx & 0xFFF0) ; 
    } ; 

    *rsize = 0 ; 
    return 64 + ((256 - 64) * 4) ; 
} ;

其中掩模輪尺寸時，在「索引」基礎和以創建「索引」所要求的換擋都在表...手動填充到UINT。

我通過隨機選擇的請求大小定義了兩個函數：80％1..0x800,15％0x801..0x2000,4％0x2001..0x8000,0.9％0x8001..0x20000和0。1％外尺寸：

Setup:  15.610 secs: user 15.580 system 0.000 -- 500 million 
Branches: 1.910 secs: user 1.910 system 0.000 
Table 1: 1.840 secs: user 1.830 system 0.000

的設置循環是：

srand(314159) ; 
    for (int i = 0 ; i < trial_count ; ++i) 
    { 
     int r ; 
     size_t mx, mn ; 

     r = rand() % 1000 ; 
     if  (r < 800) 
     { 
      mn = 1 ; 
      mx = 0x00800 ; 
     } 
     else if (r < 950) 
     { 
      mn = 0x00801 ; 
      mx = 0x02000 ; 
     } 
     else if (r < 990) 
     { 
      mn = 0x02001 ; 
      mx = 0x08000 ; 
     } 
     else if (r < 999) 
     { 
      mn = 0x08001 ; 
      mx = 0x20000 ; 
     } 
     else 
     { 
      mn = 0x20001 ; 
      mx = 0x80000 ; 
     } ; 

     test_values[i] = (rand() % (mx - mn + 1)) + mn ; 
    } ;

觀察非常仔細地考慮設置5個億測試值的時間。表格版本的運行速度稍微快一點...（gcc 4.8，-O3）...但這是一個簡單功能的4％改進！請注意，表驅動版本更加靈活，並且可以在不更改代碼或運行時間的情況下添加更多的量子。

FWIW，掩模可以（明顯）被從移位構造，所以：

static uint 
get_aligned_size_5(size_t size, size_t* rsize) 
{ 
    static const uint8_t ts[0x40] = 
    { 
    /*    0 1 2 3 4 5 6 7 8 9 A B C D E F 
    /* 0x00  */ 3, 
    /* 0x01..0x03 */  5, 5, 5, 
    /* 0x04..0x0F */    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 
    /* 0x10..0x1F */ 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 
    /* 0x20..0x2F */ 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 
    /* 0x30..0x3F */ 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 
    } ; 

    static const uint tb[16] = 
    { 
    /* 0 */ 0, 
    /* 1 */ 0, 
    /* 2 */ 0, 
    /* 3 */ ((256 - 64)/2) * (3 - 3), 
    /* 4 */ 0, 
    /* 5 */ ((256 - 64)/2) * (5 - 3), 
    /* 6 */ 0, 
    /* 7 */ ((256 - 64)/2) * (7 - 3), 
    /* 8 */ 0, 
    /* 9 */ ((256 - 64)/2) * (9 - 3), 
    /* 10 */ 0, 
    /* 11 */ 0, 
    /* 12 */ 0, 
    /* 13 */ 0, 
    /* 14 */ 0, 
    /* 15 */ 0, 
    } ; 

    size_t sx = size - 1 ; 

    if (size <= 0x20000) 
    { 
     uint8_t s ; 

     s = ts[sx >> 11] ; 
     *rsize = (sx | (((size_t)1 << s) - 1)) + 1 ; 
     return (sx >> s) + tb[s] ; 
    } ; 

    *rsize = 0 ; 
    return 64 + ((256 - 64) * 4) ; 
} ;

我發現是最快我嘗試了變化：

Setup:  15.610 secs: user 15.580 system 0.000 -- 500 million 
Branches: 1.910 secs: user 1.910 system 0.000 
Table 1: 1.840 secs: user 1.830 system 0.000 
Table 5: 1.750 secs: user 1.750 system 0.000

在一個整體（閱讀和嘆息）8％的速度:-(。

很好啊，我很無聊。

來源

2014-07-17 13:37:49

哇，我沒有不要考慮一張桌子。我可以在與代碼相同的段中找到該表，因此我不必額外使用TLB。如果表非常小，由於其命中數很高，它可能會留在L2緩存整個執行。這可能是一個非常好的候選人查表。 – johnnycrash

我們不必完全匹配原始功能。我在想我們使表32條目，並使用msb作爲索引。 msb有一個單一的指令。這將擺脫<0x20000 cmp。稍後在代碼中進行比較，查找零索引。我可以將其更改爲index> max回收列表。 – johnnycrash

那麼...'<= 0x20000'比較會停止它讀取'ts []'表的末尾。由於「大小不一」的分配（假設）是母雞罕見的，所以分支預測器會在早餐時分配它。我確實嘗試了'__builtin_clz（）'，但在2.4秒時運行速度較慢。我不得不說，我認爲改善太小以致難以衡量 - 但是如果你想要更大的靈活性，那麼至少不會讓事情變得更糟。 –

優化C函數刪除比較

回答

相關問題