Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Why strings.HasPrefix is faster than bytes.HasPrefix?

In my code, I have such benchmark:

const STR = "abcd"
const PREFIX = "ab"
var STR_B = []byte(STR)
var PREFIX_B = []byte(PREFIX)

func BenchmarkStrHasPrefix(b *testing.B) {
    for i := 0; i < b.N; i++ {
        strings.HasPrefix(STR, PREFIX)
    }
}

func BenchmarkBytHasPrefix(b *testing.B) {
    for i := 0; i < b.N; i++ {
        bytes.HasPrefix(STR_B, PREFIX_B)
    }
}

And I am little bit confused about results:

BenchmarkStrHasPrefix-4    300000000    4.67 ns/op
BenchmarkBytHasPrefix-4    200000000    8.05 ns/op

Why there is up to 2x difference?

Thanks.

like image 851
Sergey Kamardin Avatar asked Dec 01 '15 12:12

Sergey Kamardin


1 Answers

The main reason is the difference in calling cost of bytes.HasPrefix() and strings.HasPrefix(). As @tomasz pointed out in his comment, strings.HashPrefix() is inlined by default while bytes.HasPrefix() is not.

Further reason is the different parameter types: bytes.HasPrefix() takes 2 slices (2 slice descriptors). strings.HasPrefix() takes 2 strings (2 string headers). Slice descriptors contain a pointer and 2 ints: length and capacity, see reflect.SliceHeader. String headers contain only a pointer and an int: the length, see reflect.StringHeader.

We can prove this if we manually inline the HasPrefix() functions in the benchmark functions, so we eliminate the calling costs (zero both). By inlining them, no function call will be made (to them).

HasPrefix() implementations:

// HasPrefix tests whether the byte slice s begins with prefix.
func HasPrefix(s, prefix []byte) bool {
    return len(s) >= len(prefix) && Equal(s[0:len(prefix)], prefix)
}

// HasPrefix tests whether the string s begins with prefix.
func HasPrefix(s, prefix string) bool {
    return len(s) >= len(prefix) && s[0:len(prefix)] == prefix
}

Benchmark functions after inlining them:

func BenchmarkStrHasPrefix(b *testing.B) {
    s, prefix := STR, PREFIX
    for i := 0; i < b.N; i++ {
        _ = len(s) >= len(prefix) && s[0:len(prefix)] == prefix
    }
}

func BenchmarkBytHasPrefix(b *testing.B) {
    s, prefix := STR_B, PREFIX_B
    for i := 0; i < b.N; i++ {
        _ = len(s) >= len(prefix) && bytes.Equal(s[0:len(prefix)], prefix)
    }
}

Running these you get very close results:

BenchmarkStrHasPrefix-2 300000000                5.88 ns/op
BenchmarkBytHasPrefix-2 200000000                6.17 ns/op

The reason for the small difference in the inlined benchmarks may be that both functions test the presence of the prefix by slicing the string and []byte operand. And since strings are comparable while byte slices are not, BenchmarkBytHasPrefix() requires an additional function call to bytes.Equal() compared to BenchmarkStrHasPrefix() (and the extra function call also includes making copies of its parameters: 2 slice headers).

Other things that may slightly contribute to the original different results: arguments used in BenchmarkStrHasPrefix() are constants, while parameters used in BenchmarkBytHasPrefix() are variables.

You shouldn't worry much about the performance difference, both functions complete in just a few nanoseconds.

Note that the "implementation" of bytes.Equal():

func Equal(a, b []byte) bool // ../runtime/asm_$GOARCH.s

This may be inlined in some platforms resulting in no additional call costs.

like image 97
icza Avatar answered Nov 04 '22 00:11

icza