What's the fastest way to check if a list contains an item in Go?

Question

I have a project where performance is very important. The function I have to check if a list contains an item is being called hundreds of thousand to millions of times per second, and is costing me a lot of time. It is responsible for 60% of the runtime of my program.

Currently, it looks like this:

func byteContains(list[]byte,item byte)bool{
    for _,value:=range list{
        if value==item{return true}
    }
    return false
}

This works, but it's slow. Is there a faster way to do this?

Answer 1

If you can afford to allocate 256 bytes for your byte set, you can simplify your linear look-up to a direct memory lookup by offset:

type Set [256]bool

func (s *Set) Contains(b byte) bool {
    return s[b]
}

func (s *Set) Add(b byte) {
    s[b] = true
}

func (s *Set) Remove(b byte) {
    s[b] = false
}

Possible performance concerns:

• Contains will work equivalently with Set and *Set as the receiver type. It's possible that one of these will be faster, but it would likely depend on how you use the function and what optimizations the compiler applies. So, try both ways if performance is critical.
• If your byte values are all less than a certain value, you could reduce the size of the Set array to save some memory. However, keeping the size at (least) 256 will prevent the need for index bounds checking, which might save you some run-time overhead. Again, try it both ways if performance is essential.