Optimization for countCommonPrefix

[adlerjohn]

As per this comment, we can replace the logic of countCommonPrefix to use XOR followed by bits.LeadingZeros8. This should reduce the cost of the function approximately 8-fold, since you can loop over whole bytes at a time instead of bit by bit.

[liamsi]

Trying this:

func countCommonPrefix(data1 []byte, data2 []byte) int {
    count := 0
    for i := 0; i < len(data1); i++ {
        count += bits.LeadingZeros8(data1[i]^data2[i])
    }
    return count
}

and writing a little benchmark specifically for that little helper yielded:

name                   old time/op    new time/op    delta
_countCommonPrefix-12    2.15ns ±10%    9.86ns ± 9%  +358.17%  (p=0.008 n=5+5)

name                   old alloc/op   new alloc/op   delta
_countCommonPrefix-12     0.00B          0.00B           ~     (all equal)

name                   old allocs/op  new allocs/op  delta
_countCommonPrefix-12      0.00           0.00           ~     (all equal)

Also closing.