I thought it to be O(1), but this is from a pprof output:
140 140 176: var lastSB byte = s[lenSMinusOne]
88 88 177: var lastSuffixB byte = suffix[lenSuffixMinusOne]
and by average length of s is greater than length of suffix. Thus, this shows that accessing an element takes longer if the slice is bigger?
The function is:
func hasSuffix(s, suffix []byte) bool {
lenSMinusOne := len(s) - 1
lenSuffixMinusOne := len(suffix) - 1
var lastSB byte = s[lenSMinusOne]
var lastSuffixB byte = suffix[lenSuffixMinusOne]
if lenSMinusOne < lenSuffixMinusOne {
return false
} else if lastSB != lastSuffixB {
return false
} else {
for i := 0; i < lenSuffixMinusOne ; i++ {
if suffix[i] != s[lenSMinusOne-lenSuffixMinusOne+i] {
return false
}
}
}
return true
}
UPDATE: To reproduce the results install fetch which uses go-porterstemmer fork with a large corpus(I use a 440mb file).
pprof collects samples during program execution to illuminate hotspots. Use the testing package and go test to run benchmarks.
As you should expect, the following benchmark shows that there is no difference between reading the 2nd element of a slice on average and reading the 2691st element of a slice on average, 13439773 ns/op versus 13460864 ns/op for 904,061 byte slice elements. Both benchmarks use the same underlying data arrays. Indexing a slice is O(1).
In your example, you are reading from two different underlying data arrays with different access patterns (outer versus inner loop). On modern processors, which have sophisticated memory management and optimization, you shouldn't expect the same results.
$ go version
go version devel +3ae7a530dd4e Sat Dec 28 09:37:54 2013 -0800 linux/amd64
$ go test -bench=IndexWord
904061 2 2690.8131199111563
testing: warning: no tests to run
PASS
BenchmarkIndexWordLong 100 13460864 ns/op
BenchmarkIndexWordShort 100 13439773 ns/op
ok bench 7.814s
$
.
package main
import (
"bytes"
"fmt"
"io/ioutil"
"testing"
)
var (
Words [][]byte
ShortLen = 2
)
func IndexWord(b *testing.B, words [][]byte) {
b.ResetTimer()
b.StartTimer()
var char byte
for i := 0; i < b.N; i++ {
for _, word := range words {
char = word[len(word)-1]
}
}
_ = char
}
func BenchmarkIndexWordLong(b *testing.B) {
words := make([][]byte, len(Words))
for i, word := range Words {
words[i] = word
}
IndexWord(b, words)
}
func BenchmarkIndexWordShort(b *testing.B) {
words := make([][]byte, len(Words))
for i, word := range Words {
if len(word) > ShortLen {
word = word[:ShortLen]
}
words[i] = word
}
IndexWord(b, words)
}
func init() {
// The Complete Works of William Shakespeare
// http://www.gutenberg.org/cache/epub/100/pg100.txt
text, err := ioutil.ReadFile(`/home/peter/pg100.txt`)
if err != nil {
panic(err)
}
var n, short, long int64
Words = bytes.Fields(text)
for i, word := range Words {
word = bytes.Repeat(word, 600) // Requires 4GB memory
Words[i] = word
n++
long += int64(len(word))
shortLen := ShortLen
if len(word) < ShortLen {
shortLen = len(word)
}
short += int64(shortLen)
}
fmt.Println(n, float64(short)/float64(len(Words)), float64(long)/float64(len(Words)))
}
The code for your hasSuffix function looks like a direct port from another language; it doesn't look like it is written for Go. Here's my rewrite.
func hasSuffix(s, suffix []byte) bool {
if len(s) < len(suffix) {
return false
}
s = s[len(s)-len(suffix):]
for i, x := range suffix {
if x != s[i] {
return false
}
}
return true
}
Also, Go has a bytes.HasSuffix function.
func HasSuffix(s, suffix []byte) boolHasSuffix tests whether the byte slice s ends with suffix.