Portierung MeiYan Hash-Funktion zu Go

Question

Ich wollte eine State-of-the-Art-Hash-Funktion MeiYan von C zu Go portieren. (Soweit ich weiß, ist dies eine der besten, wenn nicht nur die beste Hash-Funktion für Hashtabellen in Bezug auf Geschwindigkeit und Kollisionsrate, es schlägt mindestens MurMur.)

Ich bin neu in Go, nur eine ausgegeben Wochenende mit ihm, und kam mit dieser Version auf:

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); 
} 

Sieht chaotisch, aber ich glaube nicht, ich kann es besser aussehen. Jetzt messe ich die Geschwindigkeit und es ist frustrierend langsam, 3 mal langsamer als C/C++, wenn mit gccgo -O3 kompiliert. Kann das schneller gemacht werden? Ist das genauso gut, wie der Compiler es machen kann oder unsafe.Pointer Konvertierung ist genauso langsam wie es geht? In der Tat hat mich das überrascht, weil ich gesehen habe, dass ein anderer Code-Code ähnlich wie C oder noch schneller war. Mache ich hier etwas intimes?

Hier ist das Original-C-Code ich aus bin Portierung:

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); 
} 

Hier ist, wie ich messen Geschwindigkeit:

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) 
} 

Answer 1

Die Implementierung von NATS sieht beeindruckend! Auf meinem Gerät, für eine Daten der Länge 30 (Bytes) op/sec 157175656.56 und nano-sec/op 6,36! Schau es dir an. Sie könnten einige Ideen finden.

Answer 2

Nachdem einige sorgfältiger Recherche fand ich heraus, warum mein Code langsam war, und verbessert, damit er jetzt schneller als die C-Version in meinen Tests ist:

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) 
} 

Die Hash-Funktion selbst war schon schnell, aber dereferencing Das Array bei jeder Iteration hat es langsam gemacht: &buf[0] wurde durch start := &buf[0] ersetzt und dann start bei jeder Iteration verwendet.