移植美顏哈希函數Go

我想移植一個最先進的哈希函數MeiYan，從C到Go。（據我所知這是最好的之一，如果不是哈希表在速度和衝突率方面最好的散列函數，它至少擊敗MurMur。）移植美顏哈希函數Go

我是新來的Go，剛剛花了一個週末與它，並提出了這個版本：

func meiyan(key *byte, count int) uint32 { 
    type P *uint32; 
    var h uint32 = 0x811c9dc5; 
    for ;count >= 8; { 
     a := ((*(*uint32)(unsafe.Pointer(key))) << 5) 
     b := ((*(*uint32)(unsafe.Pointer(key))) >> 27) 
     c := *(*uint32)(unsafe.Pointer(uintptr(unsafe.Pointer(key)) + 4)) 
     h = (h^((a | b)^c)) * 0xad3e7 
     count -= 8 
     key = (*byte)(unsafe.Pointer(uintptr(unsafe.Pointer(key)) + 8)) 
    } 
    if (count & 4) != 0 { 
     h = (h^uint32(*(*uint16)(unsafe.Pointer(key)))) * 0xad3e7 
     key = (*byte)(unsafe.Pointer(uintptr(unsafe.Pointer(key)) + 2)) 
     h = (h^uint32(*(*uint16)(unsafe.Pointer(key)))) * 0xad3e7 
     key = (*byte)(unsafe.Pointer(uintptr(unsafe.Pointer(key)) + 2)) 
    } 
    if (count & 2) != 0 { 
     h = (h^uint32(*(*uint16)(unsafe.Pointer(key)))) * 0xad3e7 
     key = (*byte)(unsafe.Pointer(uintptr(unsafe.Pointer(key)) + 2)) 
    } 
    if (count & 1) != 0 { 
     h = (h^uint32(*key)); 
     h = h * 0xad3e7 
    } 
    return h^(h >> 16); 
}

看起來很凌亂，但我不認爲我可以讓它看起來更好。現在我測量速度，速度令人沮喪，比使用gccgo -O3進行編譯時比C/C++慢3倍。這可以做得更快嗎？這是否與編譯器能夠做到的一樣好或者unsafe.Pointer轉換速度如此慢？實際上，這令我感到驚訝，因爲我已經看到一些其他數字處理風格的代碼與C一樣快，甚至更快。我在這裏做一些有益的事情嗎？

這裏是原來的C代碼，我從移植：

u32 meiyan(const char *key, int count) { 
    typedef u32* P; 
    u32 h = 0x811c9dc5; 
    while (count >= 8) { 
     h = (h^((((*(P)key) << 5) | ((*(P)key) >> 27))^*(P)(key + 4))) * 0xad3e7; 
     count -= 8; 
     key += 8; 
    } 
    #define tmp h = (h^*(u16*)key) * 0xad3e7; key += 2; 
    if (count & 4) { tmp tmp } 
    if (count & 2) { tmp } 
    if (count & 1) { h = (h^*key) * 0xad3e7; } 
    #undef tmp 
    return h^(h >> 16); 
}

這是我如何測量速度：

func main(){ 
    T := time.Now().UnixNano()/1e6 
    buf := []byte("Hello World!") 
    var controlSum uint64 = 0 
    for x := 123; x < 1e8; x++ { 
     controlSum += uint64(meiyan(&buf[0], 12)) 
    } 
    fmt.Println(time.Now().UnixNano()/1e6 - T, "ms") 
    fmt.Println("controlSum:", controlSum) 
}

來源

2017-02-28 exebook

爲什麼不使用Go基準？ https://golang.org/pkg/testing/#hdr-Benchmarks –

@GrzegorzŻur簡單，因爲我到目前爲止學習了1.5天。 – exebook

爲什麼你到處使用不安全？ – Flimzy

從NATS實現看起來很不錯！在我的機器上，對於長度爲30（字節）的數據op/sec 157175656.56和nano-sec/op 6.36！看看它。你可能會發現一些想法。

來源

2017-02-28 13:00:22

我已經將它作爲想法的一些源代碼提供，並且該包的許可證是MIT - 位於首頁的底部 - 並且據我所知，它是最自由的OSS許可證之一（https：// github .com/nats-io/sublist），你甚至可以在商業產品中使用它。 –

@KavehShahbazian昨天我對NATS版本進行了基準測試，它比我從C直接的端口慢，我已經忘記了數字，我認爲它慢了3倍左右。它在應該使用指針的地方大量使用片，並且每個索引解引用都是性能殺手。 – exebook

經過一番仔細的研究，我發現，爲什麼我的代碼是緩慢的，並改進它，所以它現在比C版本快是我的測試：

package main 

import (
    "fmt" 
    "time" 
    "unsafe" 
) 

func meiyan(key *byte, count int) uint32 { 
    type un unsafe.Pointer 
    type p32 *uint32 
    type p16 *uint16 
    type p8 *byte 
    var h uint32 = 0x811c9dc5; 
    for ;count >= 8; { 
     a := *p32(un(key)) << 5 
     b := *p32(un(key)) >> 27 
     c := *p32(un(uintptr(un(key)) + 4)) 
     h = (h^((a | b)^c)) * 0xad3e7 
     count -= 8 
     key = p8(un(uintptr(un(key)) + 8)) 
    } 
    if (count & 4) != 0 { 
     h = (h^uint32(*p16(un(key)))) * 0xad3e7 
     key = p8(un(uintptr(un(key)) + 2)) 
     h = (h^uint32(*p16(un(key)))) * 0xad3e7 
     key = p8(un(uintptr(un(key)) + 2)) 
    } 
    if (count & 2) != 0 { 
     h = (h^uint32(*p16(un(key)))) * 0xad3e7 
     key = p8(un(uintptr(un(key)) + 2)) 
    } 
    if (count & 1) != 0 { 
     h = h^uint32(*key) 
     h = h * 0xad3e7 
    } 
    return h^(h >> 16); 
} 

func main() { 
    T := time.Now().UnixNano()/1e6 
    buf := []byte("ABCDEFGHABCDEFGH") 
    var controlSum uint64 = 0 
    start := &buf[0] 
    size := len(buf) 
    for x := 123; x < 1e8; x++ { 
     controlSum += uint64(meiyan(start, size)) 
    } 
    fmt.Println(time.Now().UnixNano()/1e6 - T, "ms") 
    fmt.Println("controlSum:", controlSum) 
}

散列函數本身已經是快，但是提領每次迭代時的數組就是使其變慢的原因：&buf[0]被替換爲start := &buf[0]，然後在每次迭代中使用start。

來源

2017-03-01 14:21:19 exebook

移植美顏哈希函數Go

回答

相關問題