perf(coderd/util/slice): refactor unique method for large lists (coder#8925)

beyazit · web-flow · commit 1d4a72f43f80 · 2023-08-08T10:02:52.000-05:00
diff --git a/coderd/util/slice/slice.go b/coderd/util/slice/slice.go
@@ -38,17 +38,19 @@ func Overlap[T comparable](a []T, b []T) bool {
 }
 
 // Unique returns a new slice with all duplicate elements removed.
-// This is a slow function on large lists.
-// TODO: Sort elements and implement a faster search algorithm if we
-// really start to use this.
 func Unique[T comparable](a []T) []T {
 	cpy := make([]T, 0, len(a))
+	seen := make(map[T]struct{}, len(a))
+
 	for _, v := range a {
-		v := v
-		if !Contains(cpy, v) {
-			cpy = append(cpy, v)
+		if _, ok := seen[v]; ok {
+			continue
 		}
+
+		seen[v] = struct{}{}
+		cpy = append(cpy, v)
 	}
+
 	return cpy
 }
 

Original file line number	Diff line number	Diff line change
`@@ -38,17 +38,19 @@ func Overlap[T comparable](a []T, b []T) bool {`
`38`	`38`	`}`
`39`	`39`
`40`	`40`	`// Unique returns a new slice with all duplicate elements removed.`
`41`		`-// This is a slow function on large lists.`
`42`		`-// TODO: Sort elements and implement a faster search algorithm if we`
`43`		`-// really start to use this.`
`44`	`41`	`func Unique[T comparable](a []T) []T {`
`45`	`42`	`cpy := make([]T, 0, len(a))`
	`43`	`+ seen := make(map[T]struct{}, len(a))`
	`44`	`+`
`46`	`45`	`for _, v := range a {`
`47`		`- v := v`
`48`		`- if !Contains(cpy, v) {`
`49`		`- cpy = append(cpy, v)`
	`46`	`+ if _, ok := seen[v]; ok {`
	`47`	`+ continue`
`50`	`48`	`}`
	`49`	`+`
	`50`	`+ seen[v] = struct{}{}`
	`51`	`+ cpy = append(cpy, v)`
`51`	`52`	`}`
	`53`	`+`
`52`	`54`	`return cpy`
`53`	`55`	`}`
`54`	`56`