4

My question is slightly different from this question that asks about how to check equality of Go slices.

Like this article suggests, a Go slice is a value consisting of three things: a pointer to the array, the length of the segment, and its capacity (the maximum length of the segment). Is it then possible to (cheaply) check if two such slices are equal because they point to the same underlying array and have the same values for length and capacity (preferably without traversing the two slices checking for equality of individual elements)? It appears that the == operator is not defined on slices.

The question came while I was implementing a bit vector (IntSet) that internally uses a []uint64 to represent the elements and I stumbled upon implementing a method func (*IntSet) Equals(that *IntSet) bool which could be called like s.Equals(s).

(It appears that I could optimize for that case as shown below, but the question remains:

func (this *IntSet) Equals(that *IntSet) bool {
    if this == that { // use equality of pointers!
        return true
    }
// omitted for brevity 
}
Kedar Mhaswade
  • 4,535
  • 2
  • 25
  • 34
  • By that definition, `[]int{1, 2, 3} == []int{1, 2, 3}` is false. It seems the language authors decided to leave the equality operator undefined on slices rather than having that particular point of potential error. –  Oct 26 '18 at 13:23
  • 1
    @TimCooper I think that is understandable because these are actually two different slice _values_ that happen to have the same elements. – Kedar Mhaswade Oct 26 '18 at 13:35
  • 1
    https://golang.org/ref/spec#Comparison_operators talks about what can be `==`d (slices can be checked `== nil` but not each other). As a language designer I'd also guess people might expect two slices to be `==` if they have the same values (even in totally separate arrays), and even a naïve value comparison could have inconsistent behavior in some cases where the underlying array may or may not be reallocated. – David Maze Oct 26 '18 at 13:42

1 Answers1

9

Using the address of the first element

The easiest way is to simply get the address of the first element of the slices, and compare them (pointers are comparable). We can get the address of the first element by simply using the address operator, e.g. &s[0]. If the slices are empty, there is no first element, in which case we only check if both are empty. We also have to compare the lengths of the slices:

func identical(s1, s2 []int) bool {
    if len(s1) != len(s2) {
        return false
    }

    return len(s1) == 0 || &s1[0] == &s2[0]
}

I purposefully left out comparing the capacity as that only plays a role if the slices are resliced.

This identical() function only checks if the slices are identical. 2 non-identical slices may be equal (they may contain equal elements) even if they are not identical.

Testing it:

s := []int{1, 2, 3}
fmt.Println(identical(s, s))

s2 := []int{1, 2, 3}
fmt.Println(identical(s, s2))

Output is (try it on the Go Playground):

true
false

Using reflect.SliceHeader

We may opt to obtain and use the slice descriptors which contain the pointer, length and capacity. This is modeled by reflect.SliceHeader:

type SliceHeader struct {
        Data uintptr
        Len  int
        Cap  int
}

To obtain a reflect.SliceHeader, we may use package unsafe and the unsafe.Pointer type like this:

var s []int = ... // s is a slice

// and h will be its descriptor, of type *reflect.SliceHeader
h := (*reflect.SliceHeader)(unsafe.Pointer(&s))

A simple comparator function which checks if 2 slices are identical, meaning they point to the same backing array and have the same length (regardless of their capacity):

func identical(s1, s2 []int) bool {
    h1 := (*reflect.SliceHeader)(unsafe.Pointer(&s1))
    h2 := (*reflect.SliceHeader)(unsafe.Pointer(&s2))

    return h1.Data == h2.Data && h1.Len == h2.Len
}

Testing it:

s := []int{1, 2, 3}
fmt.Println(identical(s, s))

s2 := []int{1, 2, 3}
fmt.Println(identical(s, s2))

Output (try it on the Go Playground):

true
false
icza
  • 389,944
  • 63
  • 907
  • 827