diff --git a/android/util.go b/android/util.go
index ade851e..e74b64e 100644
--- a/android/util.go
+++ b/android/util.go
@@ -193,6 +193,14 @@
 // FirstUniqueStrings returns all unique elements of a slice of strings, keeping the first copy of
 // each.  It modifies the slice contents in place, and returns a subslice of the original slice.
 func FirstUniqueStrings(list []string) []string {
+	// 128 was chosen based on BenchmarkFirstUniqueStrings results.
+	if len(list) > 128 {
+		return firstUniqueStringsMap(list)
+	}
+	return firstUniqueStringsList(list)
+}
+
+func firstUniqueStringsList(list []string) []string {
 	k := 0
 outer:
 	for i := 0; i < len(list); i++ {
@@ -207,6 +215,20 @@
 	return list[:k]
 }
 
+func firstUniqueStringsMap(list []string) []string {
+	k := 0
+	seen := make(map[string]bool, len(list))
+	for i := 0; i < len(list); i++ {
+		if seen[list[i]] {
+			continue
+		}
+		seen[list[i]] = true
+		list[k] = list[i]
+		k++
+	}
+	return list[:k]
+}
+
 // LastUniqueStrings returns all unique elements of a slice of strings, keeping the last copy of
 // each.  It modifies the slice contents in place, and returns a subslice of the original slice.
 func LastUniqueStrings(list []string) []string {