What's the slice element access complexity in Go?

Question

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).

Answer 1

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.

Package bytes

func HasSuffix

func HasSuffix(s, suffix []byte) bool

HasSuffix tests whether the byte slice s ends with suffix.

Answer 2

Slice access is O(1), but memory access on modern computers can take orders of magnitude more or less time depending on whether the value is cached. Without seeing your code, most likely this is why one memory access is slower than another.

Another possibility are that one of your slices is an array and the index is constant, meaning that bounds checking isn't necessary.