labels.Compare: use github.com/grailbio/base/simd package

bboreham · bboreham · commit 06f8bc778743 · 2023-06-13T15:20:55.000Z
diff --git a/go.mod b/go.mod
@@ -28,6 +28,7 @@ require (
 	github.com/google/pprof v0.0.0-20230406165453-00490a63f317
 	github.com/gophercloud/gophercloud v1.3.0
 	github.com/grafana/regexp v0.0.0-20221122212121-6b5c0a4cb7fd
+	github.com/grailbio/base v0.0.10
 	github.com/grpc-ecosystem/grpc-gateway v1.16.0
 	github.com/hashicorp/consul/api v1.20.0
 	github.com/hashicorp/nomad/api v0.0.0-20230418003350-3067191c5197
diff --git a/go.sum b/go.sum
@@ -399,6 +399,8 @@ github.com/gorilla/mux v1.7.3/go.mod h1:1lud6UwP+6orDFRuTfBEV8e9/aOM/c4fVVCaMa2z
 github.com/gorilla/websocket v0.0.0-20170926233335-4201258b820c/go.mod h1:E7qHFY5m1UJ88s3WnNqhKjPHQ0heANvMoAMk2YaljkQ=
 github.com/gorilla/websocket v1.5.0 h1:PPwGk2jz7EePpoHN/+ClbZu8SPxiqlu12wZP/3sWmnc=
 github.com/gorilla/websocket v1.5.0/go.mod h1:YR8l580nyteQvAITg2hZ9XVh4b55+EU/adAjf1fMHhE=
+github.com/grailbio/base v0.0.10 h1:FL7DEolplFFhvxNn9T6WQejBRZOcQWb92SBTHcPLX74=
+github.com/grailbio/base v0.0.10/go.mod h1:lzK85oI6emqHxO2Cy+xzPzEAC/GcbfH3dqGgZCD3dA4=
 github.com/grafana/regexp v0.0.0-20221122212121-6b5c0a4cb7fd h1:PpuIBO5P3e9hpqBD0O/HjhShYuM6XE0i/lbE6J94kww=
 github.com/grafana/regexp v0.0.0-20221122212121-6b5c0a4cb7fd/go.mod h1:M5qHK+eWfAv8VR/265dIuEpL3fNfeC21tXXp9itM24A=
 github.com/grpc-ecosystem/go-grpc-middleware v1.0.1-0.20190118093823-f849b5445de4/go.mod h1:FiyG127CGDf3tlThmgyCl78X/SZQqEOJBCDaAfeWzPs=
diff --git a/model/labels/labels_stringlabels.go b/model/labels/labels_stringlabels.go
@@ -23,6 +23,7 @@ import (
 	"unsafe"
 
 	"github.com/cespare/xxhash/v2"
+	"github.com/grailbio/base/simd"
 	"github.com/prometheus/common/model"
 	"golang.org/x/exp/slices"
 )
@@ -425,24 +426,12 @@ func FromStrings(ss ...string) Labels {
 // TODO: replace with Less function - Compare is never needed.
 // TODO: just compare the underlying strings when we don't need alphanumeric sorting.
 func Compare(a, b Labels) int {
-	if len(a.data) == 0 {
-		return -len(b.data)
-	} else if len(b.data) == 0 {
-		return len(a.data)
-	}
 	// Find the first byte in the string where a and b differ.
-	shorter, longer := a.data, b.data
-	if len(b.data) < len(a.data) {
-		shorter, longer = b.data, a.data
-	}
-	i := 0
-	_ = longer[len(shorter)-1] // Get compiler to do bounds-check on longer just once here.
-	for ; i < len(shorter); i++ {
-		if shorter[i] != longer[i] {
-			break
-		}
+	shorter, longer := yoloBytes(a.data), yoloBytes(b.data)
+	if len(longer) < len(shorter) {
+		shorter, longer = longer, shorter
 	}
-	firstCharDifferent := i
+	firstCharDifferent := simd.FirstUnequal8Unsafe(shorter, longer[:len(shorter)], 0)
 	if firstCharDifferent == len(shorter) {
 		if len(shorter) == len(longer) {
 			return 0
@@ -456,7 +445,7 @@ func Compare(a, b Labels) int {
 
 	// Now we know that there is some difference before the end of a and b.
 	// Go back through the fields and find which field that difference is in.
-	i = 0
+	i := 0
 	for {
 		size, nextI := decodeSize(a.data, i)
 		if nextI+size > firstCharDifferent {
