Implementing a Cuckoo Filter in Go

https://medium.com/@meeusdylan/implementing-a-cuckoo-filter-in-go-147a5f1f7a9

by Insanity • 7 years ago

66 5 7 years ago

sagichmal• 7 years ago

The global hasher var makes this code unsafe for concurrent use by multiple goroutines.

voidlogic• 7 years ago

This code should just call sha1.New(). If for some reason these allocations are a performance issue it is very simple to fix that will a little pooling:

    package main

    import (
        "crypto/sha1"
        "hash"
        "sync"
    )

    func main() {
        hasher := getHasher()
        defer poolHasher(hasher)
    }

    var hasherPool sync.Pool = sync.Pool{
        New: func() interface{} {
            return sha1.New()
        },
    }

    func getHasher() hash.Hash {
        return hasherPool.Get().(hash.Hash)
    }

    func poolHasher(hasher hash.Hash) {
        hasher.Reset()
        hasherPool.Put(hasher)
    }

dchest• 7 years ago

Or just use sha1.Sum https://golang.org/pkg/crypto/sha1/#Sum

aksx• 7 years ago

I am all for the Go idiom that variable name length should be directly proportional to it's scope, the code samples in the post have take it a bit too far and make the code harder to read.

it would be so much more readable if the struct had more descriptive names

    type Cuckoo struct {
       buckets           []bucket
       numBuckets        uint
       entriesPerBucket  uint 
       fingerprintLength uint
       capacity          uint
    }

Insanity• 7 years ago

It's a good point - and I wasn't entirely sure what to go with.

In the end, I went with the shorter variable names as they are used in the paper I've linked: https://www.pdl.cmu.edu/PDL-FTP/FS/cuckoo-conext2014.pdf

In a production version of this, longer variable names would be a good thing. :)

Implementing a Cuckoo Filter in Go

Related Stories