2015-08-30 62 views
-2
unsigned int lookup_bloom(unsigned char (*id)[HEXXID], unsigned int len, 
     void *bf) 
{ 
    int i; 
    struct bloom_structure *filter = (struct bloom_structure *) bf; 
    unsigned int *nexthop = NULL; 
    // The returned values of counting_bloom_check() are 0 if found else 1 
    unsigned char matchvec[WDIST] = {1}; 
    unsigned char tmp1[HEXXID + 1] = {0}; 
    unsigned char tmp2[HEXXID] = {0}; 

    memcpy(tmp1, id, HEXXID); 
    memcpy(tmp2, tmp2, HEXXID); 
    // Although the paper suggests to perform parallel membership queries 
    for (i = len; i >= MINLENGTH; i--) { 
     tmp1[i/BYTE] = tmp1[i/BYTE] >> (BYTE - i % BYTE) << 
          (BYTE - i % BYTE); 
     if (!filter->flag[i - MINLENGTH]) 
      continue; 
     matchvec[i - MINLENGTH] = 
     counting_bloom_check(filter->bloom[i - MINLENGTH], tmp1, 
           HEXXID); 
    } 
    // Parse the matchvec from longest to shortest to perform table search 
    for (i = len; i >= MINLENGTH; i--) { 
     tmp2[i/BYTE] = tmp2[i/BYTE] >> (BYTE - i % BYTE) << 
          (BYTE - i % BYTE); 
     if (matchvec[i - MINLENGTH] || !filter->flag[i - MINLENGTH]) 
      continue; 
     nexthop = hashit_lookup(filter->hashtable[i - MINLENGTH], 
        tmp2); 
     if (nexthop) 
      return *nexthop; 
    } 

    return 0; 
} 

下面是在代碼中使用的一些定義:我對這個函數做了哪些改變來優化執行時間?

#define WDIST 140 
#define MINLENGTH 20 

struct bloom_structure { 
    bool flag[WDIST]; 
    unsigned int length[WDIST]; 
    int low[WDIST]; 
    int high[WDIST]; 
    counting_bloom_t *bloom[WDIST]; 
    hash_t hashtable[WDIST]; 
}; 

我測量這個函數的執行時間。 有人能幫我優化這個例程嗎?

如果有人可以建議任何更改以編寫循環以減少執行時間,那將會很棒。

謝謝您提前!

+0

分析。並測量每一段代碼,看看瓶頸在哪裏(這基本上是分析)。 –

回答

0

取決於此功能的重要性,您可以儘量減少執行的分區數(/和%),因爲它們是CPU成本最高的操作。

你可能會合並你的兩個循環,因爲他們使用相同的範圍。這樣你就可以在一個變量中使用相同的索引計算(暗示分割)。

如果你真的想推這個,你可以預先計算所有暗示除法計算的索引,以便從數組或任何被認爲合適的容器中訪問這些值。

相關問題