性能改進我的HashMap的執行

我決定我會嘗試讓我自己的HashMap（here）性能改進我的HashMap的執行

對於讀取它比標準庫的實現慢28％，我不知道是否有可能加快以下代碼，指數（）其是用於查找關鍵：

const numOnes = uint8(20) 
const ones = uint32(1 << numOnes - 1) 

func (m *Map) Index(num uint64) uint32 { 
    part := uint32(num) & ones 
    remaining := num >> numOnes 
    start := m.starts[part] 
    bitsNum := m.bitNums[part] 
    matchedBits := bitsNum & uint16(remaining) 
    offset := BitScoreCache[bitsNum][matchedBits] 
    return start + uint32(offset) 
}

音符BitScoreCache是var BitScoreCache [5000][5000]uint16這應該是隻讀的，多個不同的地圖實例之間共享。

用法示例：

func (pa PrimeAdvancedAnagrammar) GetAnagrams(word string) []string { 
    return pa.m[pa.locator.Index(PrimeProduct(word))] //pa.m is an [][]string 
}

與標準庫：

func (pba PrimeBasicAnagrammar) GetAnagrams(word string) []string { 
    return pba.m[PrimeProduct(word)] //pba.m is a map[uint64][]string 
}

主要有哪些原因，它比爲這麼幾個操作標準庫慢？

來源

2017-03-16 robert king

https://www.youtube.com/watch?v=Tl7mi9QmLns –

那麼，內置映射的實現對Go非常重要，因此它經過了大量優化。優化某些東西是一個難題。例如。你的BitScoreCache非常大，查找內存不友好（這可能是一個瓶頸，雖然看起來很無辜）。 – Volker

由於此問題屬於另一個站點，所以無法正常工作：[codereview]（http://codereview.stackexchange.com/） – icza

將兩個數組組合成一個結構數組可以減少緩存未命中並且是性能最大的改進。

也提前返回的情況下，沒有碰撞提高性能。

來源

2017-03-21 21:53:02

性能改進我的HashMap的執行

回答

相關問題