std :: map（和family）查找性能問題

我正在編寫一個位域抽象類，它包裝32位內存（u32 = unsigned int）並提供對該內存中各個位或範圍的訪問。std :: map（和family）查找性能問題

爲了實現這一點，我已經使用一個std ::地圖，其中唯一的密鑰是一個指針（未的std :: string）與C-字符數組表示助記符，並且該值是包含一個結構位字段屬性（例如助記符，起始位置，長度，初始值和字段值）。所有這些屬性都是恆定的，並且在啓動時定義，除了只在底層u32值發生更改時更改的字段值。（另請注意：我剛剛重用了助記符指針值作爲唯一鍵值）。

這是在一個模擬器中使用，其中getBitfieldValue()，返回位域值（只讀），被稱爲每秒多次。

在VS 2015更新3（使用-O2和任何速度優化我可以找到）編譯和分析代碼時，它顯示getBitfieldValue()函數和擴展std::find()佔CPU總數的60-70％左右時間...太慢了。

我嘗試過使用其他地圖實現，例如Boost::flat_map，google::dense_hash_map或std::unordered_map，它們有所幫助，但仍然最終太慢（〜50-60％）。

我的猜測是我使用了一個錯誤目的的地圖，但我不確定考慮只有5-20個位域映射（小查找大小）......它似乎太慢了。大部分時間將用於查找相同的領域。

相關類的源代碼可以在這裏找到：BitfieldMap32

的地圖是如何在啓動initalised一個例子（只運行一次）：

struct Fields 
{ 
    static constexpr char * ADDR = "ADDR"; 
    static constexpr char * SPR = "SPR"; 
}; 
ExampleClass() // constructor 
{ 
    // registerField(mnemonic, start position, length, initial value) 
    registerField(Fields::ADDR, 0, 31, 0); 
    registerField(Fields::SPR, 31, 1, 0); 
}

而且字段值是如何訪問（只讀）：

// getFieldValue definition. 
const u32 & BitfieldMap32_t::getFieldValue(const char* fieldName) 
{ 
    return mFieldMap.find(fieldName)->second.mFieldValue; 
} 

// Field access. 
const u32 value = ExampleClassPointer->getFieldValue(Fields::ADDR)

有關如何減少查找時間的任何想法？還是我需要一起更改實施？

來源

2016-09-29 marco9999

爲什麼不使用std :: bitset？ – Davidbrcz

所以你測量出你的代碼使用了大多數的CPU。但是，它真的*慢*？如果它真的「足夠快」，CPU或運行時間的百分比並不重要。你的程序的運行時間是多少？是否需要等待用戶輸入？如果用戶輸入了某些內容，用戶是否必須等待幾毫秒？用戶需要等多長時間？不到半秒鐘的時間實際上看起來幾乎是瞬間的。你真的想把事情複雜化（可能是很多*），以0.4秒而不是0.5秒運行嗎？ –

也許你應該考慮使用使用哈希的'std :: unordered_map'，並且應該更快，而'std :: map'使用二進制搜索。 –

IIUC，使用字典（std::map或std::unordered_map）是一個巨大的矯枉過正。也許你應該使用以下命令：

類應該只是圍繞一個整數（或最多一std::bitset）的內部存儲的包裝。
助記符應該是enum s，而不是std::string s。
在內部，有一個std::vector有效地將每個enum值映射到bitmask。（如果您使用C++ 11 enum s，請參閱here如何將enum值轉換爲std::vector內的位置）。
每個操作應該只是通過助記符，通過索引查找位掩碼，並將其應用於內部存儲。

來源

2016-09-29 09:00:35

正如我的評論中提到的，我不確定std :: bitset如何在性能上有所幫助，因爲它不提供「範圍」函數（它並不總是單個位），所以我需要遍歷一個位集。我會嘗試枚舉和向量的組合，看看它是怎麼回事。 – marco9999

@ marco9999那麼我會再看看你的代碼。無論如何，我建議你考慮用'enum's替換'std :: string'助記符。 –

使用std :: vector和從0（enum/ints）開始的有序索引鍵結束。效果更好。猜猜地圖對它來說太過分了。 – marco9999

std :: map（和family）查找性能問題

回答

相關問題